Summing over all possible permutations is generally intractable. Thus, in practice, Janossy pooling employs one of two approaches:

1. Sample a random subset of possible permutations during each application of the aggregator, and only sum over that random subset.

2. Employ a canonical ordering of the nodes in the neighborhood set; e.g. order the nodes in descending order according to their degree, with ties broken randomly.

University of Michigan - Ann Arbor

This approach is more powerful than simply taking a sum or mean of the neighbor embeddings. Instead of using a permutation-invariant reduction (e.g., a sum or mean), Janossy pooling applies a permutation-sensitive function and average the result over many possible permutations.

Let $\pi _{i} \in \Pi$ denote a permutation function that maps the set $\{ h_{v}, \forall v \in N(u) \}$ to a specific sequence $(h_{v1}, h_{v2}, ..., h_{v|N(u)|})_{\pi _{i}}$. The Janossy pooling approach then performs neighborhood aggregation by
$$m_{N(u)}=MLP_{\theta}(\frac{1}{|\Pi|} \sum_{\pi \in \Pi}\rho_{\phi}) (h_{v1}, h_{v2}, ..., h_{v||N(u)})_{\pi _{i}}$$, 

where $\Pi$ denotes a set of permutations and ρφ is a permutation-sensitive function.

Set Aggregators: Janossy pooling

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

Learn Before

Related