Aggregation-based message-passing graph neural networks

Fix a finite vertex-labeled simple undirected graph $G=(V,E,\mathrm{\ell })$, a finite nonnegative depth $K$, feature sets $H_0,\dots ,H_K$, and an initial map $\eta :\mathrm{\Sigma }\to H_0$. For each $k=1,\dots ,K$, choose a set $Z_k$, an aggregation function $A_k:{\mathsf{M}}_{\mathrm{f}\mathrm{i}\mathrm{n}}(H_{k-1})\to Z_k$ on finite multisets, and an update function $U_k:H_{k-1}\times Z_k\to H_k$. Initialize $h_v^0=\eta (\mathrm{\ell }(v))$ and recursively set

$$a_v^k=A_k\text{\hspace{0.17em}⁣}(\{\text{\hspace{0.17em}⁣}\{h_u^{k-1}:u\in N_G(v)\}\text{\hspace{0.17em}⁣}\}),h_v^k=U_k(h_v^{k-1},a_v^k)\mathrm{.}$$

For a chosen output set $Y$, a graph readout is a function $R:{\mathsf{M}}_{\mathrm{f}\mathrm{i}\mathrm{n}}(H_K)\to Y$; the graph output is $z_G=R(\{\text{\hspace{0.17em}⁣}\{h_v^K:v\in V\}\text{\hspace{0.17em}⁣}\})$. The same maps are used on every graph being compared. The model has no vertex-identity input and uses no graph-wide information before the readout. It distinguishes two graphs when their outputs differ.

finite vertex-labeled simple undirected graphs and neighborhoods

finite multisets with multiplicities

Xu, Hu, Leskovec, and Jegelka, “How Powerful are Graph Neural Networks?”, §2

Morris et al., “Weisfeiler and Leman Go Neural,” §3

Li and Leskovec, Graph Representation Learning, Chapter 5 §5.3.2