coordinate representation and compressed sparse row representation - better explanation of CSR:

Last Time

• information theoretic threshold
• community detection
  Today
• See [[School/Archived/Equivariant Machine Learning/course_PDFs/Lecture 8.pdf]]
• Popular GNN architectures that can be expressed in convolutional form
  • MPNN
  • GCN
  • ChebNet
  • graphSAGE
• GATS

This type of network was initially introduced by Gilmer et al. In a message passing neural network, each layer consists of 2 operations: the message and the update.

The message is a function that processes

• the signal at node $i$
• the message /signal at each of the neighbors of $i$
• the edge weights

The update is a function on the signal of the graph from the previous layer to the next, taking into account the message and the current value at each node:

(see message passing neural network)

Consider an MPNN. As long as $M_{\ell }$ is linear, the "message" can be expressed as a graph convolution.

which is a graph convolution with $K=2,S=A,h_0=\alpha ,h_1=\beta$

As long as $U_{\ell }$ is the composition of a pointwise nonlinearity $\sigma$ with a linear function $M_{\ell }$, then $x_{\ell }$ can be expressed as a GNN layer

(see MPNNs can be expressed as graph convolutions)

From the perspective of learning the weights ($h_0,h_1$ vs $\alpha ,{\alpha }^{\prime },\beta ,{\beta }^{\prime }$), what is different?

Introduced by Kipf and Willing, 2017, a graph convolutional network layer is given by

Note that $H_{\ell }$ are row vectors. We can think of each layer as a "degree normalized aggregation"

(see graph convolutional network)

We can write a graph convolutional network layer as a graph convolution. This is easy to see by simply writing

Which is exactly the form of a graph convolution with

• $K=2$
• $S=D_{\text{binary}}^{-1/2}{A}_{\text{binary}}{D}_{\text{binary}}^{-1/2}$
• $H_{\ell ,0}=0,H_{\ell ,1}=H_{\ell }$

And $A_{\text{binary}}$ is the binary adjacency matrix (given as A[A>0] in Python)

(see GCN layers can be written as graph convolutions)

Advantages of GCNs:

• One local diffusion step per layer
• Simple and interpretable
• Neighborhood size normalization prevents vanishing or exploding gradient problem - only one diffusion step

Disadvantages

• no edge weights
• only supports the adjacency $S=A$
• No self loops unless they are present in $A$ (embedding at layer $\ell$ not informed by the embedding at layer $\ell -1$). Even if self-loops are in the graph, there is no ability to weight $(x_{\ell }{)}_i$ and $(x_{\ell -1}{)}_j,j\in N(i)$ differently.

The idea behind ChebNets, which were introduced by Defferrard et al. in 2017, in to create a "fast" implementation of graph convolution in the spectral domain. Each layer of a ChebNet is given by

Where $\overline{L}=\frac{2L}{{\lambda }_{max}}-I$ to ensure $\lambda \in (-1,1)\mathrm{\forall }\lambda$ and the $T_k$ are the Chebyshev Polynomials.

We use the Chebyshev polynomials instead of Taylor polynomials to approximate an analytic function because

1. By the chebyshev equioscillation theorem , they provide a better approximation with fewer coefficients
2. chebyshev polynomials are orthogonal, meaning we can find an orthonormal basis for free. There is no need to implement the filters in the spectral domain.

(see ChebNet)

Recall that we can represent any analytic function with convolutional graph filters, but translating back to the spectral domain is expensive because we need to compute the graph fourier transform $GFT(x)=\hat{x}=V^{T}x$ and also inverse graph fourier transform $h(\lambda )\hat{x},y=Vh(\lambda )\hat{x}$.

This costs 2 additional matrix-vector multiplications, plus the diagonalization of $L$

Let $⟨f,g⟩={\int }_{-1}^{1}f(x)g(x)\frac{1}{\sqrt{1-x^2}}dx$

The Chebyshev Polynomials $T_0,T_1,\dots$ are orthogonal with respect to the inner product $⟨\cdot ,\cdot ⟩$.

(see chebyshev polynomials are orthogonal)

$$\begin{array}{rl}{\int }_{-1}^1{T}_n(x)T_m(x)\frac{1}{\sqrt{1-x^2}}dx& ⟹x=\cos \theta ,\frac{dx}{d\theta }=\sin \theta \\ & ={\int }_{\pi }^2\pi T_n(\cos \theta )T_m(\cos \theta )\frac{d\theta \sin \theta }{\sqrt{1-{\cos }^2\theta }}\\ & ={\int }_{\pi }^2\pi \cos (n\theta )\cos (m\theta )d\theta \text{ since }{T}_n=\cos (n\theta )\\ & ={\int }_{\pi }^2\pi \frac{e^{in\theta }+e^{-in\theta }}{2}+\frac{e^{im\theta }+e^{-im\theta }}{2}d\theta \\ & =\frac{1}{4}{\int }_{\pi }^{2\pi }{e}^{in\theta }+e^{-in\theta }+e^{im\theta }+e^{-im\theta }d\theta \\ & =\{\begin{array}{l}\frac{1}{4}{\int }_{\pi }^{2\pi }4d\theta =\theta {|}_{\pi }^{2\pi }=\pi \text{ if }n=m=0\\ \frac{1}{4}{\int }_{\pi }^{2\pi }2d\theta +\frac{1}{4}{\int }_{\pi }^{2\pi }2\cos ((n+m)\theta )d\theta =\frac{\pi }{2}+0=\frac{\pi }{2}\text{ if }n=m\ne 0\\ \frac{1}{4}{\int }_{\pi }^{2\pi }2\cos ((n+m)\theta )+2\cos ((n-m)\theta )d\theta =0\text{ if }n\ne m\end{array}\end{array}$$

Advantages

• Fast and cheap - easy to calculate polynomials and they are orthogonal for free
• localized spectral filters

Disadvantages

• less stable than Taylor approximations
  • perturbing the adjacency matrix can cause large fluctuations in the chebyshev polynomial approximation, whereas the taylor approximations will remain basically the same
• $S$ is restricted to $L$
• difficult to interpret in the node domain

Introduced by Hamilton-Ying-Leskovee in 2017, each Graph SAGE layer implements the following 2 operations:

Aggregate

Concatenate

The standard $\text{AGGREGATE}$ operation is an average over $N(i)$. Letting $H=[H_0{H}_1{]}^T$, we get

where $A$ is the binary adjacency matrix, which is equivalent to a GCN with nodewise normalization $\frac{(x_{\ell }{)}_i}{||(x_{\ell }{)}_i|{|}_2}$. This normalization helps in some cases (empirically).

(see graph SAGE)

• SAGE implementations allow for a variety of $\text{AGGREGATE}$ functions, including $max$ and LSTMs (which look at $N(i)$ as a sequence, losing permutation equivariance). In these cases, SAGE is no longer a graph convolution.

  • There are both advantages and disadvantages of staying a GCN and using other functions.

• the authors of SAGE popularized the $\text{AGGREGATE}=\text{UPDATE}$ representation of GNNs (with $K=2$) meaning

$S{x}_{\ell }$ is the "aggregate" and $\sigma (\dots H_{\ell })$ is the "update"