This approach is based on the theory of permutation invariant neural networks. For example, an aggregation function with the following form is a universal set function approximator:

$$m_{N(u)}=MLP_{\theta}(\sum_{v\in N(u)}MLP_{\phi}(h_{v}))$$
Any permutation-invariant function that maps a set of embeddings to a single embedding can be approximated to an arbitrary accuracy by a model following this equation.

Set pooling approaches based on the above equation often lead to small increases in performance, though they also introduce an increased risk of overfitting, depending on the depth of the MLPs used. 

If set pooling is used, it is common to use MLPs that have only a single hidden layer, since these models are sufficient to satisfy the theory, but are not so over parameterized so as to risk catastrophic overfitting.

Set Aggregators: Set pooling

Janossy pooling is a method for neighborhood aggregation that is more powerful than simply taking a sum or mean of the neighbor embeddings. Instead of using a permutation-invariant reduction, Janossy pooling applies a permutation-sensitive function and averages the result over many possible permutations. Let $$\pi_{i} \in \Pi$$ denote a permutation function that maps the set $$\left\{ h_{v}, \forall v \in N(u) \right\}$$ to a specific sequence $$(h_{v1}, h_{v2}, \dots, h_{v|N(u)|})_{\pi_{i}}$$. The Janossy pooling approach performs neighborhood aggregation by: $$m_{N(u)} = MLP_{\theta} \left( \frac{1}{|\Pi|} \sum_{\pi_{i} \in \Pi} \rho_{\phi} (h_{v1}, h_{v2}, \dots, h_{v|N(u)|})_{\pi_{i}} \right)$$, where $$\Pi$$ denotes a set of permutations and $$\rho_{\phi}$$ is a permutation-sensitive function.

Janossy Pooling

The neighborhood aggregation operation is fundamentally a set function. Given a set of neighbor embeddings $$\left\{h_{v}, \forall v \in N(u)\right\}$$, there is no natural ordering of a node's neighbors, and any aggregation function we define must thus be permutation invariant.

University of Michigan - Ann Arbor

Google

There are several ways of generalizing or improving the “AGGREGATE” operator:

1)	Neighborhood Normalization

2)	Set Aggregators

3)	Neighborhood Attention


Generalized Neighborhood Aggregation

Hamilton, W.L. Graph Representation Learning. *Synthesis Lectures on Artificial Intelligence and Machine Learning*. 2020, 14(3), 1–159. https://doi.org/10.2200/S01045ED1V01Y202009AIM046

Graph Representation Learning by William Hamilton

The most basic neighborhood aggregator takes a sum of a node’s neighbors. One drawback of this is that it’s highly sensitive to the node degrees. So there’s several ways of normalizing the aggregator.

Although it solves the degree sensitivity problem, it also caused loss of information. Indeed, it has been proven that an normalized GNN is less powerful than an not normalized GNN.


Neighborhood Normalization

In addition to more general forms of set aggregation, a popular strategy for improving the aggregation layer in GNNs is to apply attention. The basic idea is to assign an attention weight or importance to each neighbor, which is used to weigh this neighbor’s influence during the aggregation step. The first GNN model to apply this style of attention was Graph Attention Network (GAT), which uses attention weights to define a weighted sum of the neighbors: $$m_{N(u)}=\sum _{v \in N(u)} \alpha _{u,v} h_{v}$$, where $$\alpha _{u,v}$$ denotes the attention on neighbor $$v \in N(u)$$ when we are aggregating information at node $$u$$.

Learn Before

Related

Learn After