2025-02-19 graphs lecture 9

[[lecture-data]]

2025-02-19

Summary

Last Time

Today

• G(y)ATs
• Expressivity in graph-level tasks
• Graph isomorphism problem

1. Graph Signals and Graph Signal Processing

Graph Attention (GAT)

(x_{\ell})_{i} = \sigma\left( \sum_{j \in N(i)} \alpha_{ij}(x_{\ell-1})_{j} H_{\ell} \right)$$ Where the \alpha_{ij}$ are the ==learned== graph attention coefficients, computed as

\alpha_{ij} = \text{softmax}_{N(i)}(e_{ij}), \;\;\; e_{ij} = \frac{\rho(\vec{a}(x_{i}H' \lvert \rvert x_{j} H'))}{\sum_{j' \in N(i)} \rho(\vec{a} (x_{i}H' \lvert \rvert x_{j'}H' ))}$$ Here, we are learning the [[Concept Wiki/graph]] [[Concept Wiki/unweighted graph\|weight matrix]] E$vialearning$H’$.Wecanthinkofthisascalculatingthe"relativesimilarity"betweentransformedfeaturesof$i$and$j$vsthesimilarityofallneighborsof$i$.

• $(\cdot ||\cdot )$ is the row-wise concatenation operation.
  • so $\vec{a}\in {\mathbb{R}}^{1\times 2d}$
  • and each $x_i{H}^{\prime }\in {\mathbb{R}}^d$
• $\rho$ is a pointwise nonlinearity, typically leaky ReLU

The learnable parameters for this model are $\vec{a},H_{\ell },H^{\prime }$ for $1\le \ell \le L$.

Notes

• This architecture is local because it is still respecting the graph sparsity pattern, and learning the “similarities” of the transformed features at each layer of the network.
• This architecture does not depend on the size of the graph, only the dimension of the features
• It can still be expensive to compute however, if the graph is dense. We need to compute $|E|$ coefficients ${\alpha }_{ij}$, which can be up to $n^2$ in complete graphs.

This additional flexibility increases the capacity of the architecture (less likely to underfit to training data), and this has ben observed empirically. But this comes at the cost of a more expensive forward pass.

This architecture is available and implemented in PyTorch Geometric

Note

We can think of the GAT layer $(x_{\ell }{)}_i=\sigma \left({\sum }_{j\in N(i)}{\alpha }_{ij}(x_{\ell -1}{)}_j{H}_{\ell }\right)$ as a convolutional layer where the GSO $S$, is learned

• however, this architecture is not convolutional since $S$ is changing at each step.
• But it can be useful to see how we can write/think about it as something that looks convolutional (if you squint)

Leaky ReLU

The leaky ReLU is a pointwise nonlinearity that is given as:

x,\;\;x \geq 0 \\ \alpha x, \;x < 0 \end{cases}$$ (see [[Concept Wiki/leaky ReLU]])

the “readout” in graph-level tasks

Idea

In graph-level problems, the output does not need to be a graph signal - it could be a scalar, a class label, or some vector in ${\mathbb{R}}^d$. That is, $y\in \mathbb{R},y\in \{0,1,\dots ,C\},y\in {\mathbb{R}}^d$ are all possible.

Question

How do we map GNN layers to such outputs?

Answer

We can use “readout” layers

Readout Layer

A readout layer is an additional layer added to a GNN to achieve the desired output type/dimension for graph-level tasks or other learning tasks on graphs that require an output that is not a graph signal.

(see readout layer)

Example

In node-level tasks (ex source localization, community detection, citation networks, etc), both the input and the output are graph signals $x\in {\mathbb{R}}^{n\times d_0},y\in {\mathbb{R}}^{n\times d_L}$. Thus, the map ${\Phi }_H$ is composed strictly of GNN layers.

• Benefit: convolutional graph filters are local. This ensures a parameterization that is independent of graph size $n$

GNN layer equation

$X_{\ell} = \sigma(U_{\ell}) = \sigma\left( \sum_{k=0}^{K-1} S^k X_{\ell-1} H_{\ell, k} \right)$$

When we learn our GNN layers, we fix $S$ and learn only $H_{\ell ,k}\in {\mathbb{R}}^{}$ which does not depend on the graph size.

Option 1

fully connected readout layer

In a fully connected readout layer we define $y=\rho (C.\text{vec}(x_{\ell }))$ Where

• $C\in {\mathbb{R}}^{d\times n{d}_L}$
• $\text{vec}(x_{\ell })\in {\mathbb{R}}^{n{d}_L}$
  • in general $\text{vec}(\cdot )$ vectorizes ${\mathbb{R}}^{m\times n}$ matrices into ${\mathbb{R}}^{mn}$ vectors
• $\rho$ can be the identity or some other pointwise nonlinearity (ReLU, softmax, etc)

(see fully connected readout layer)

Note

There are some downsides of a fully connected readout layer

• The number of parameters depends on $n$ - adding $n{d}_{L}d$ learning parameters, which grows with the graph size. This is not amenable to groups of large graphs

• No longer permutation invariant because of the $\text{vec}(\cdot )$ operation

fully connected readout layers are no longer permutation invariant

Verify that

• No longer transferrable across graphs.
  • unlike in GNNs, $C$ depends on $n$. So if the number of nodes $n$ changes, we have to relearn $C$

These make this a not-so-attractive option, so we usually use an aggregation readout layer

Aggregation Readout Layer

The aggregation readout layer is a readout layer given by $y=\text{aggr}(x_{L}C)$

where $C\in {\mathbb{R}}^{d_L\times d}$ and $\text{aggr}:{\mathbb{R}}^{n\times d}\to {\mathbb{R}}^{1\times d}$ is node-level aggregation Typical aggregation functions are the mean, sum, max, min, median, etc

NOTE

• this is now independent of $n$ (my aggregation functions don’t change based on the size of my graph)
• permutation invariant since the aggregation functions are also permutation invariant
• this remains transferrable across graphs, unlike the fully connected readout layer

graph isomorphism problem

Graph Isomorphism

Let $G$ and $G^{\prime }$ be two graphs. A graph isomorphism between $G$ and $G^{\prime }$ is a bijection $M:V(G)\to V(G^{\prime })$ such that for all $i,j\in V(G)$ $(i,j)\in E(G)⟺(M(i),M(j))\in E(G^{\prime })$ (see graph isomorphism)

A graph isomorphism exists exactly when two graphs are equivalent.

Question

Can we train a GNN to detect if graphs are isomorphic?

• ie, to produce identical outputs for graphs in the same equivalence class/graphs which are isomorphic, and different outputs for graphs that are not isomorphic?

Consider two graphs $G$ and $G^{\prime }$ with laplacian $L=V\Lambda V^T$ and $L^{\prime }=V^{\prime }{\Lambda }^{\prime }{V}^{\prime T}$. Assume they do not have node features (but we can impute them)

• Consider the following single-layer (linear) GNN $y={\sum }_{k=0}^{K-1}{h}_k{L}^{k}x(\ast )$ Suppose there is some ${\lambda }_j$ such that ${\lambda }_j\ne {\lambda }_i^{\prime }$ for all $i$ - ie, $L$ has at least one eigenvalue that is different from $L^{\prime }$

We can verify whether graphs without node features and different laplacian eigenvalues are not isomorphic

Theorem

Consider two graphs $G$ and $G^{\prime }$ without node features, with laplacian $L=V\Lambda V^T$ and $L^{\prime }=V^{\prime }{\Lambda }^{\prime }{V}^{\prime T}$. Further suppose that there is some ${\lambda }_j$ such that ${\lambda }_j\ne {\lambda }_i^{\prime }$ for all $i$ - ie, $L$ has at least one eigenvalue that is different from $L^{\prime }$.

Then there exists a graph convolution we can use to verify whether two graphs are NOT isomorphic, ie to test that $G\ne G^{\prime }$

Proof

Consider the following single-layer (linear) GNN $y={\sum }_{k=0}^{K-1}{h}_k{L}^{k}x(\ast )$ Define the graph feature $x$ to be white, ie such that $\mathbb{E}[{\hat{x}}_i]=1\forall i=1,\dots ,n$.

Set $h_k=\{\begin{array}{l}1\text{ if }k=1\\ 0\text{otherwise}\end{array}$

Then we have

\mathbb{E}(\hat{y}) &= \mathbb{E}(V^Ty) \ &= \mathbb{E}(V^Th_{k}Lx) \ &= \mathbb{E}(V^TV\Lambda V^Tx) \ &= \mathbb{E}(\Lambda x) \ \implies \mathbb{E}(\hat{y}) &= \begin{bmatrix} \lambda_{1} \ \lambda_{2} \ \vdots \ \lambda_{n} \end{bmatrix} \end{aligned}$$ And if there is some ${\lambda }_j$ such that ${\lambda }_j\ne {\lambda }_i^{\prime }$ for all $i$ - ie, $L$ has at least one eigenvalue that is different from $L^{\prime }$ as above, then it suffices to compare

$\mathbb{E}(1^T\hat{y})={\sum }_i{\lambda }_i=\mathrm{Tr}(L)\text{to }\mathbb{E}(1^T{\hat{y}}^{\prime })={\sum }_i{\lambda }_i^{\prime }=\mathrm{Tr}(L^{\prime })$ Since the laplacian is positive semidefinite, the sums will be different if and only if we have at least eigenvalue that is different between them.

(see paper GNNs are more powerful than you think)

However, there are many non-isomorphic graphs that share the same eigenvalues

Example

These graphs are clearly non-isomorphic, but their laplacian eigenvalues are the same!

Thus, a strong alternative is the

So our eigenvalue-based heuristic doesn’t work for some graphs, but a simple heuristic that does work is counting degrees. Then the problem amounts to comparing the multisets of node degree counts.

(continuing the example from above) $G_1$ has degrees $\{1,3,3,2,2,3\}$ and $G_2$ has degrees $\{2,2,2,4,2,2\}$

Weisfeiler-Leman Graph Isomorphism Test

The Weisfeiler-Leman graph isomorphism test consists of running the color refinement algorithm for two graphs.

Motivation eigenvalue-based heuristic doesn't work for some graphs, a simple heuristic that does work is counting degrees. Then the problem amounts to comparing the multisets of node degree counts.

Since 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.

Example

Color refinement for $G_1$

No node features, so assume all 1. Assign colors based on node features $c_1(0)=c_2(0)=c_3(0)=f(\cdot ,1)=k_1$

step $t=1$:

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$:

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.