2025-02-24 graphs lecture 10

[[lecture-data]]

Summary

last time

• graph isomorphism problem
  • GNNs cannot distinguish graphs with identical eigenvalues
  • But many non-isomorphic graphs share spectra
  • This problem is not solvable in polynomial time
• One heuristic is the Weisfeiler-Leman Graph Isomorphism Test

Today

• Are GNNs as powerful as the Weisfeiler-Leman Graph Isomorphism Test?
• computational graphs
• requirements for a powerful GNN
• graph isomorphism networks (last architecture we will discuss)

Much of the content from today from “How Powerful are GNNs” by Xu et al 2019 - created this architecture

• measure expressive power wrt WL test

1. Graph Signals and Graph Signal Processing

Recall from last class that we discussed the Weisfeiler-Leman Graph Isomorphism Test, which uses the

Color refinement algorithm

The color refinement algorithm is an algorithm to assign colorings to nodes.

Given graph $G=(V,E)$ with node features $x$

let $c_i(0)=f(\cdot ,\{x_i\})\forall i\in V$ (assign colors based on node feature values) let $t=0$

while True:

1. let $c_i(t)=f(c_i(t-1),\{\{c_j(t-1),j\in N(i)\}\})\forall i\in V$

• assign colors based on previously assigned colors

2. if $c_i(t)==c_i(t-1)\forall i$, break. else, $t=t+1$

Here, $f$ is a hash function that assigns colors.

Today, we will finish up the example that we began last class.

Example

Color refinement for $G_1$

No node features, so assume all 1. First, Assign colors based on node features.

step $t=0$: $c_{1}(0) = c_{2}(0)=c_{3}(0) = f(\cdot, 1) = k_{1}$$

step $t=1$: $\begin{aligned} c_{1}(1) &= f(k_{1}, { k_{1} }) &= k_{1} \ c_{3}(1) &= f(k_{1}, { k_{1} }) &= k_{1} \ c_{2}(1) &= f(k_{1}, { k_{1}, k_{1} }) &= k_{2} \end{aligned}$$ Evaluate: did the colors change?

• Yes: continue!

step $t=2$: $\begin{aligned} c_{1}(2) &= f(k_{1}, { k_{1} }) &= k_{1} \ c_{3}(2) &= f(k_{1}, { k_{1} }) &= k_{1} \ c_{2}(2) &= f(k_{2}, { k_{1}, k_{1} }) &= k_{2} \end{aligned}$$ Evaluate: did the colors change?

• No - so we are done!
• This is the final coloring.

return $\{k_1,k_1,k_2\}$

Color refinement for $G_2$ Again, there are no node features, so we assume the signals are all $1$.

step $t=0$: assign colors based on node features: c_{1}(0) = c_{2}(0)=c_{3}(0) = f(\cdot, 1) = k_{1}$$ `step` t=1$:$\begin{aligned} c_{1}(1) = c_{2}(1) = c_{3}(1) = f(\cdot, { k_{1}, k_{1} }) = k_{1} \end{aligned}$$

evaluate: did the colors change?

• No - so we are done
• This is the final coloring

return $\{k_1,k_1,k_1\}$

Since the outputs of the algorithm are different, we can conclude that $G_1$ and $G_2$ are not isomorphic.

Note

There are other better algorithms that perform similar tests, but they often come at the expense of more computations

Today, we want to know: Are GNNs as powerful as the Weisfeiler-Leman Graph Isomorphism Test?

Proposition

If a GNN can distinguish between graphs $G_1$ and $G_2$, then so can the WL test.

Proof

Consider the $\text{AGGREGATE-COMBINE}$ representation of GNNs (recall graph SAGE for something similar) where each layer consists of

1. aggregation step on the neighborhood of each node $a_{\ell ,i}=\text{AGGREGATE}(\{(x_{\ell -1}{)}_u:u\in N(i)\})$

2. combine step $(x_{\ell }{)}_i=\text{COMBINE}(a_{\ell ,i},(x_{\ell -1}{)}_i)$

And with a permutation invariant readout layer $X_G=\text{READOUT}(\{(x_{\ell }{)}_i:i\in V\})$ (these are typically like the mean, max, sum, etc)

Suppose after $\ell$ iterations in the WL test and $\ell$ layers as described above,

1. the embeddings $X_{G_1}\ne X_{G_2}$
2. the WL test cannot decide if $G_1$ and $G_2$ are non-isomorphic

If the WL test cannot decide, then every previous iteration $j=0,1,\dots ,\ell$ in the test, then

• $G_1$ and $G_2$ must have the same color multisets, call them $\{(c_j{)}_v\}$, and
• the color neighborhoods $\{(c_j{)}_u:u\in N(v)\}$ are also the same for all $v$

---

NTS that if WL test for $v\in G_1$ and $v^{\prime }\in G_2$ gives the same color, then the GNN gives the same embedding.

want to show $(\ast )$ if the WL test gives $(c_j{)}_v=(c_j{)}_{v^{\prime }}$ for all $v,v^{\prime }$, then the GNN always produces $(x_j{)}_v=(x_j{)}_{v^{\prime }}$

Since there are no node features, impute $1$ as the feature for all nodes in each graph.

• The color refinement algorithm will assign the same colors to all nodes at the initial step as we saw in the example
• The 0th layer of the GNN assigns $(x_0{)}_v=(x_0{)}_{v^{\prime }}$ for all $v,v^{\prime }$ since all feature values are the same

Induction Hypothesis Suppose $(\ast )$ holds for iteration/layer $j$.

• the WL test outputs the same colors $(c_{j+1}{)}_v$ and $(c_{j+1}{)}_{v^{\prime }}$ for all $v,v^{\prime }$. That is, $[(c_j{)}_v,\{(c_j{)}_u|u\in N(v)\}]=[(c_j{)}_{v^{\prime }},\{(c_j{)}_{u^{\prime }}:u^{\prime }\in N(v^{\prime })\}]$

• By the induction hypothesis, we have that $[(x_j{)}_v,\{[x_j{]}_u:u\in N(v)\}]=[(x_j{)}_{v^{\prime }},\{[x_j{]}_{u^{\prime }}:u^{\prime }\in N(v^{\prime })\}]$ Since the same $\text{AGGREGATE}$ and $\text{COMBINE}$ functions are applied to both graphs, then we automatically get that $(x_{j+1}{)}_v=(x_{j+1}{)}_{v^{\prime }}\forall v,v^{\prime }$ Thus, by induction, if the colors $(c_j{)}_v=(c_j{)}_{v^{\prime }}$ for all $v,v^{\prime }$, the the embeddings $(x_j{)}_v=(x_j{)}_{v^{\prime }}$ at any $j$.

$(x_j{)}_v=g((c_j{)}_v)$ for all $v$ between the embeddings of the nodes and the coloring assignment.

This creates a valid map

We can extend this mapping to include the multiset of embeddings/colors of the neighbors as well, and say that the multiset of all embeddings and neigeborhood embedding pairs also has a map $\{(x_j{)}_v,\{(x_j{)}_u:u\in N(v)\}\}=\{g((c_j{)}_v),\{g((c_j{)}_u):u\in N(v)\}\}$ And these are each the same for the two graphs.

Thus, the $(x_j{)}_v$ and $(x_j{)}_{v^{\prime }}$ are the same for all $j$. And, due to the permutation invariance of the readout layer as defined above, we must have $X_{G_1}=X_{G_2}$.

$⟹⟸$ we assumed that the embeddings were NOT equal! Thus, it must be the case that the WL test CAN decide if $G_1$ and $G_2$ are non-isomorphic.

see the WL test is at least as powerful as a GNN for detecting graph non-isomorphism

What have we shown here?

• the WL test is at least as powerful as GNNs

We want to know if GNNs are at least as powerful as the WL test. ie if the WL test tells $G_1$ and $G_2$ apart, does there exist a GNN that can tell $G_1$ and $G_2$ apart?

ie, are GNNs as powerful as the WL test at telling non-isomorphic graphs apart?

Example

Can a GCN tell these apart? Recall

Graph Convolutional Networks graph convolutional network layer is given by (x_{\ell})_{i} = \sigma\left[ \sum_{j \in N(i)} \frac{(x_{\ell-1})_{j}}{\lvert N(i) \rvert } H_{\ell}\right]$$ Note that H_{\ell}$ are row vectors. We can think of each layer as a "degree normalized aggregation"

Introduced by Kipf and Willing, 2017, a

In AGGREGATE-COMBINE form, a GCN layer is given by $(x_j{)}_v=\text{ReLU}(W,\text{mean}\{(x_{j-1}{)}_u:u\in N(v)\cup \{\}\})$ WLOG, assume $W=1$. The first layer with readout gives us But then we get the same output for every layer and this GNN fails for permutation invariant readouts.

Takeaway

By the example above, we can see easily that not every GNN is as powerful as the WL test. However, there are some GNNs that can do better, and which can be at least as powerful.

Exercise

Check if graph SAGE with the $\max$ aggregation: $(x_j{)}_v=\max (\{\text{ReLU}(W.(x_j{)}_u),\forall u\in N(v)\})$ Can tell these graphs apart.

In the example above, where did things break? Pros: GCNs and any permutation equivariant GNN does not distinguish between nodes 1 and 3. This is an implicit data augmentation mechanism! Cons: The GCN cannot distinguish between (1 and 3) and 2, but the structure at 1 or 3 is different from at node 2.

Let’s define the computational graph

computational graph

The computational graph tracks the communications that each node makes at each layer or iteration of an algorithm/network.

Example

Since 1 and 3 are symmetric, their computational graph is symmetric

$L=2$ is sufficient because the diameter (or the longest shortest path between two nodes) is of length 2.

see computational graph

We can imagine that we are mapping computational graphs to some embedding space. The issue with the GCN is that it is mapping all three computational graphs to a single embedding space.

We need functions/embeddings/maps that are injective. ie, which map different computational graphs (or different multisets of embeddings) to different values in embedding space.

Theorem

Let $G_1$ and $G_2$ be two graphs that the Weisfeiler-Leman Graph Isomorphism Test determines are non-isomorphic. A GNN $\Phi$ maps $G_1$ and $G_2$ to $\Phi (G_1)\ne \Phi (G_2)$ if the following hold:

1. $\Phi$ aggregates and updates as $(x_{\ell }{)}_v=\varphi \left((x_{\ell -1}{)}_v,\phi (\{(x_{\ell -1}{)}_u:u\in N(v)\})\right)$ Where $\varphi ,\phi$ are injective.
2. The readout function is (permutation invariant) and injective.

Proof (sketch)

In the proof showing that the WL test is at least as powerful as a GNN for detecting graph non-isomorphism, we showed that if the color refinement algorithm gives $(c_j{)}_v=(c_j{)}_{v^{\prime }}\forall v,v^{\prime }$, then the embeddings $(x_j{)}_v=(x_j{)}_{v^{\prime }}\forall v,v^{\prime }$ and that that there is a valid map $(x_j{)}_v=g((c_j{)}_v)\forall v$ We need $g$ to be injective. Why? We don’t want it to be the case that there are different colors $c_v,c_w$ that map to the same embedding $x_v$.

Let $f$ be the hash function in the WL test. Recall that is is bijective for color multisets. We can write the embedding at layer $j$ as follows:

(x_{j})_{v} &= g(f[(c_{j-1})_{v}, \{ (c_{j-1})_{u} : u \in N(v) \}]) \\ (x_{j})_{v} &= g(f[g^{-1}((x_{j-1})_{v}), \{ g^{-1}((x_{j-1})_{u}) : u \in N(v) \}]) \\ &\approx \phi(\cdot, \varphi(\cdot)) \;\;\;\text{the GNN} \end{aligned}$$ So to have $g$ injective, we need the [[Concept Wiki/Graph Neural Networks\|GNN]] to be injective. Thus, $\phi, \varphi \implies$ the GNN is injective $\implies g$ is invective $\implies$ the GNN is as powerful as the [[Concept Wiki/Weisfeiler-Leman Graph Isomorphism Test\|WL test]]

see injective GNNs are as powerful as the WL test