Message-passing GNNs and the 1-WL ceiling

Fix a set of labels $\mathrm{\Sigma }$. A finite vertex-labeled simple undirected graph is a triple $G=(V,E,\mathrm{\ell })$ in which $V$ is a finite set of vertices, $E$ is a set of two-element subsets of $V$, and $\mathrm{\ell }:V\to \mathrm{\Sigma }$ assigns a label to each vertex. Its neighborhood at $v\in V$ is $N_G(v)=\{u\in V:\{u,v\}\in E\}$. Thus edges have no orientation, loops, or multiplicity. Graphs compared in one labeled-graph statement use the same label set $\mathrm{\Sigma }$.

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

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

Li and Leskovec, Graph Representation Learning, Chapter 5

Let $X$ be a set. A finite multiset on $X$ is a function $m:X\to {\mathbb{N}}_0$ with finite support $\mathrm{supp}(m)=\{x\in X:m(x)>0\}$. The multiplicity $m(x)$ is the number of occurrences of $x$, and the size is $\mathrm{\mid }m\mathrm{\mid }={\sum }_{x\in \mathrm{supp}(m)}m(x)$. Two finite multisets are equal exactly when their multiplicity functions agree at every element of $X$. We write $\{\text{\hspace{0.17em}⁣}\{x_1,\dots ,x_n\}\text{\hspace{0.17em}⁣}\}$ for the multiset whose multiplicity at $x$ is the number of indices $i$ with $x_i=x$; $n=0$ denotes the empty multiset.

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

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

Li and Leskovec, Graph Representation Learning, Chapter 5 §§5.3.3–5.3.4

Let $G=(V,E,\mathrm{\ell })$ and $H=(W,F,m)$ be finite vertex-labeled simple undirected graphs with labels in the same set $\mathrm{\Sigma }$. A label-preserving graph isomorphism from $G$ to $H$ is a bijection $\phi :V\to W$ such that $\mathrm{\ell }(v)=m(\phi (v))$ for every $v\in V$, and for all distinct $u,v\in V$, $\{u,v\}\in E$ if and only if $\{\phi (u),\phi (v)\}\in F$. The graphs are isomorphic when such a bijection exists, and nonisomorphic otherwise.

finite vertex-labeled simple undirected graphs

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

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

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

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

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

Let $G=(V,E,\mathrm{\ell })$ and $H=(W,F,m)$ be finite vertex-labeled simple undirected graphs with labels in a common set $\mathrm{\Sigma }$. Define color sets recursively by $C_0=\mathrm{\Sigma }$ and $C_{t+1}=C_t\times {\mathsf{M}}_{\mathrm{f}\mathrm{i}\mathrm{n}}(C_t)$ for each integer $t\ge 0$. Set $c_0^G(v)=\mathrm{\ell }(v)$ and $c_0^H(w)=m(w)$; for $t\ge 0$, update

$c_{t+1}^G(v)=(c_t^G(v),\{\text{\hspace{0.17em}⁣}\{c_t^G(u):u\in N_G(v)\}\text{\hspace{0.17em}⁣}\}),c_{t+1}^H(w)=(c_t^H(w),\{\text{\hspace{0.17em}⁣}\{c_t^H(z):z\in N_H(w)\}\text{\hspace{0.17em}⁣}\})\mathrm{.}$

The graph color multiset at round $t$ is $C_t(G)=\{\text{\hspace{0.17em}⁣}\{c_t^G(v):v\in V\}\text{\hspace{0.17em}⁣}\}$, and likewise for $H$. One-dimensional Weisfeiler–Leman color refinement distinguishes $G$ and $H$ at round $t$ when $C_t(G)\mathrm{\ne }{C}_t(H)$; it distinguishes the pair when this holds for some finite $t$. If no finite round distinguishes them, they are one-WL-indistinguishable. In the unlabeled case, take $\mathrm{\Sigma }$ to be a singleton. The tuple update is the canonical collision-free color encoding.

finite vertex-labeled simple undirected graphs and neighborhoods

finite multisets and color multiplicities

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

Morris et al., “Weisfeiler and Leman Go Neural,” §2, Eq. (1)

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

Let $\mathcal{X}$ be a countable set and let $M\in {\mathbb{N}}_0$. There is a map $\varphi :\mathcal{X}\to {\mathbb{N}}_{>0}\subset \mathbb{Q}$ such that the sum $S\mapsto {\sum }_{x\in S}\varphi (x)$ is injective on finite multisets $S$ of total multiplicity at most $M$. For every irrational $\epsilon \in \mathbb{R}\setminus \mathbb{Q}$, the map

is injective on pairs with $c\in \mathcal{X}$ and $S$ a finite multiset of total multiplicity at most $M$. For $M=0$, the only allowed neighbor multiset is empty.

Xu, Hu, Leskovec, and Jegelka, “How Powerful are Graph Neural Networks?”, Lemma 5 and Corollary 6

Li and Leskovec, Graph Representation Learning, Chapter 5 §5.3.4, Lemma 5.1

Given a finite vertex-labeled graph $G=(V,E,\mathrm{\ell })$, a finite nonnegative integer $K$, feature spaces and maps of the types in the aggregation-based message-passing definition, compute a graph output as follows. Initialize $h_v^0=\eta (\mathrm{\ell }(v))$ for every $v\in V$. For each $k=1,\dots ,K$, first compute $a_v^k=A_k(\{\text{\hspace{0.17em}⁣}\{h_u^{k-1}:u\in N_G(v)\}\text{\hspace{0.17em}⁣}\})$ for every $v\in V$, then set $h_v^k=U_k(h_v^{k-1},a_v^k)$ for every $v\in V$. Return $R(\{\text{\hspace{0.17em}⁣}\{h_v^K:v\in V\}\text{\hspace{0.17em}⁣}\})$. When $K=0$, return $R(\{\text{\hspace{0.17em}⁣}\{\eta (\mathrm{\ell }(v)):v\in V\}\text{\hspace{0.17em}⁣}\})$ without a layer update.

finite labeled graphs and neighborhoods

the typed aggregation, update, and readout maps

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

Fix a finite depth $K\in {\mathbb{N}}_0$, positive integer dimensions $d_0,\dots ,d_K$, an initial embedding $\eta :\mathrm{\Sigma }\to {\mathbb{R}}^{d_0}$, scalars ${\epsilon }_1,\dots ,{\epsilon }_K\in \mathbb{R}$, and maps $M_k:{\mathbb{R}}^{d_{k-1}}\to {\mathbb{R}}^{d_k}$ for $1\le k\le K$. Each $M_k$ is a multilayer perceptron, meaning a finite composition of affine maps between finite-dimensional real vector spaces and coordinatewise applications of a fixed scalar activation. On a finite vertex-labeled simple undirected graph $G$, initialize $h_v^0=\eta (\mathrm{\ell }(v))$ and update

For a chosen output set $Y$, the graph readout is a map $R:{\mathsf{M}}_{\mathrm{f}\mathrm{i}\mathrm{n}}({\mathbb{R}}^{d_K})\to Y$ on the multiset of final vertex features. The neighbor sum counts each neighbor vertex once, so equal feature vectors at different neighbors contribute with their multiplicity. This definition imposes no injectivity condition on the perceptrons or the readout and makes no claim that a fixed finite architecture realizes an arbitrary injection.

aggregation-based updates and multiset graph readouts

Xu, Hu, Leskovec, and Jegelka, “How Powerful are Graph Neural Networks?”, §4.1, Eq. (4.1)

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

Morris et al., “Weisfeiler and Leman Go Neural,” §3, Eq. (5)

Let $G$ and $H$ be finite vertex-labeled simple undirected graphs with labels in a common set, and let $\phi :G\to H$ be a label-preserving graph isomorphism. At every finite round $t$, corresponding vertices have equal one-dimensional Weisfeiler–Leman colors: $c_t^G(v)=c_t^H(\phi (v))$ for every $v\in V(G)$. Consequently their graph color multisets agree at every round, so the refinement does not distinguish isomorphic graphs.

finite vertex-labeled graphs and neighborhoods

label-preserving graph isomorphisms

multiset equality and multiplicity

one-dimensional color refinement

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

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

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

Let $G,H$ be finite vertex-labeled simple undirected graphs with labels in a common set, and let a depth-$K$ aggregation-based message-passing graph neural network use the same initial embedding, layer maps, and graph readout on both graphs. If one-dimensional Weisfeiler–Leman color refinement has equal graph color multisets on $G$ and $H$ at every round $0,\dots ,K$, then the network gives the same graph output on $G$ and $H$. Equivalently, whenever this network distinguishes the pair, one-dimensional Weisfeiler–Leman distinguishes the pair at some round at most $K$.

finite vertex-labeled graphs and neighborhoods

finite multisets and multiplicities

shared aggregation, update, and graph-readout maps

round colors and graph color multisets

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

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

Li and Leskovec, Graph Representation Learning, Chapter 5 §5.3.3, Theorem 5.2

Let $G,H$ be finite vertex-labeled simple undirected graphs with labels in a common set. Suppose one-dimensional Weisfeiler–Leman distinguishes them at round $K$. Use a shared initial embedding that is injective on the labels occurring in the pair. Assume each message-passing layer's aggregation function is injective on the neighbor multisets encountered and its update function is injective on the center-state/aggregate pairs encountered. Assume also that the graph readout is injective on the final node-state multisets of the pair. Then a depth-$K$ aggregation-based message-passing graph neural network distinguishes $G$ and $H$.

For the GIN sum construction, if the active feature universe is countable and every neighbor multiset has size at most a fixed $\mathrm{\Delta }\in {\mathbb{N}}_0$, the bounded-multiset lemma gives an injective scalar code for the GIN preactivation $(1+\epsilon )h_v+{\sum }_{u\in N(v)}{h}_u$ for any irrational $\epsilon$, when current feature values use that code. If each graph has at most a fixed $N\in {\mathbb{N}}_0$ vertices, the same lemma gives an injective sum encoding for the graph-level readout multiset. This is an existence statement for injective maps on the relevant code sets; it does not assert that every fixed finite MLP realizes an arbitrary such map. The post-MLP update and graph readout must still satisfy the injectivity hypotheses above.

finite vertex-labeled graphs and neighborhoods

finite multisets and multiplicities

aggregation-based updates and graph readout

finite-round WL colors and histograms

GIN update formula and finite-MLP scope

injective sum and irrational self-weight encodings

Xu, Hu, Leskovec, and Jegelka, “How Powerful are Graph Neural Networks?”, Theorem 3

Morris et al., “Weisfeiler and Leman Go Neural,” §3, Theorems 1–2

Li and Leskovec, Graph Representation Learning, Chapter 5 §§5.3.3–5.3.4