Graph Nueral Network Reading Notes

This is a reading note of Deep Learning on Graphs: A Survey.

Notations

Graph: a graph is represented as $G(E, V)$

• $V =${$v_1,…,v_N$} is a set of $N = \mid{V}\ \mid$ nodes
• $E \subseteq V \times V$ is a set of $M= \mid{E}\ \mid$ edges between nodes

Adjacency Matrix: represented as $\mathbf { A } \in \mathbb{R}^{N×N}$

• $i^{th}$ row, $j^{th}$ column and an element denoted as $\mathbf { A }(i,:)$, $\mathbf { A }(: ,j)$, $\mathbf { A }(i,j)$.
• Unsigned graphs: $\mathbf { A }(i,j) \ge0$.

Feature: $\mathbf{F}^V$ for nodes and $\mathbf{F}^E$ for edges.

Spectral Method: Laplacian Matrix $\mathbf { L } = \mathbf { D } - \mathbf { A }$, where $\mathbf { D } \in \mathbb { R } ^ { N \times N }$ is a diagonal degree matrix.

• Eigen-decomposition: $\mathbf { L } = \mathbf { Q } \mathbf { \Lambda } \mathbf { Q } ^ { \mathrm { T } }$
• Transition Matrix: $\mathbf { P } = \mathbf { D } ^ { - 1 } \mathbf { A }$

GNNs:

Basic Framework:

A recursive definition of states is adopted, lower-dimensional state vector $\mathbf{s}_i$ is:

We can use Jacobi method to reach a stable point. To get the final output, define the output function $\mathcal { O }(\cdot)$:

One step of gradient descend is performed using the Almeida-Pineda algorithm to minimize a task- specific objective function.

For graph-focused tasks, the authors suggest adding a special node with unique attributes corresponding to the whole graph. (It’s similar in BERT).

Variants and Application:

Gated Graph Sequence Neural Networks (GGS-NNs), replace the recursive definition with any other “Gate function” without the need of contraction map:

CommNet, applies GNN to learn multi-agent communication in AI systems by regarding each agent as a node and updating the states of agents by communication with others for several time steps before taking an action. See more about Interaction Network, Relation Networks and VAIN.

GCNs (Spectral)

Basic Framework:

Specifically, the convolution operation on graph $^∗G$ is defined as: $\mathbf { u } _ { 1 } * _ { G } \mathbf { u } _ { 2 } = \mathbf { Q } \left( \left( \mathbf { Q } ^ { T } \mathbf { u } _ { 1 } \right) \odot \left( \mathbf { Q } ^ { T } \mathbf { u } _ { 2 } \right) \right)$ where $\mathbf { u } _ { 1 } , \mathbf { u } _ { 2 } \in \mathbb { R } ^ { N }$ is two signals defined on nodes and $Q$ are eigenvectors of $L$.

Filtering a signal $\mathbf{u}$ can be obtained as: $\mathbf { u } ^ { \prime } = \mathbf { Q } \Theta \mathbf { Q } ^ { T } \mathbf { u }$ where $u’$ is the output signal, $\Theta = \Theta ( \Lambda ) \in \mathbb { R } ^ { N \times N }$ is a diagonal matrix of learnable filters and $Λ$ are eigenvalues of $L$.

So the convolutional layer can be defined as: $\mathbf { u } _ { j } ^ { l + 1 } = \rho \left( \sum _ { i = 1 } ^ { f _ { l } } \mathbf { Q } \Theta _ { i , j } ^ { l } \mathbf { Q } ^ { T } \mathbf { u } _ { i } ^ { l } \right) j = 1 , \dots , f _ { l + 1 }$

• Convolutional Filters: $\Theta _ { i , j } ^ { l } $
• Non-linear Activated function: $\rho(\cdot)$
• Input Layer: $F^V$。

Limitations:

There are two main limitations.

• Scalability: Use Laplacian Matrix and Eigen-decomposition on the whole graph. $O(N^2)$ should be spent to obtain these matrices.
• Multi-Graph: Only use the Eigen Matrix $Q$ of one graph.

Variants:

There are several variants to tackle the problems mentioned before.

ChebNet, to solve the efficiency problem by using polynomial filter, and use Chebyshev expansion to replace the eigen decomposition operation: $\Theta ( \Lambda ) = \sum _ { k = 0 } ^ { K - 1 } \theta _ { k } \Lambda ^ { k } = \sum _ { k = 0 } ^ { K - 1 } \theta _ { k } \mathcal { T } _ { k } ( \tilde { \Lambda } )$

where $\tilde { \boldsymbol { \Lambda } } = 2 \mathbf { \Lambda } / \lambda _ { \max } - \mathbf { I }$ , where $\lambda_{\max}$ is the maximal eigenvalue and $\mathcal { T } _ { k } ( x )$ is the Chebyshev polynomial of order $k$. The update function can be defined as:

• Time Complexity: from $O(N^2)$ to $O(KM)$, where $M$ is the numbere of edges.
• Neighboring: node $v_i$ will only be affected by its K-step neighborhood.

Neural FPs, to solve the multi-graph limitations by using the first-order neighbors.

Since the parameters $\Theta$ can be shared across different graphs and are independent of graph sizes, Neural FPs can handle multiple graphs of arbitrary sizes. This model proposes to learn different parameters $Θ$ for nodes with different degrees.

PATCHY-SAN, adopts a different idea to assign a unique order of nodes using the graph labeling procedure such as the Weisfeiler-Lehman kernel and arranges nodes in a line using this pre-defined order.

GCNs (Spatial)

Basic Framework:

MPNNs propose a unified framework for the graph convolution operation in the spatial domain using a message passing function.

where $\mathbf{m}^{l+1}_i$ is the “messages” passed between nodes. Each node sends messages based on its states and updates its states based on messages received from immediate neighbors.

GraphSAGE also proposed a framework to unify the previous GCNs works:

Mixture model network also did the same thing:

where $u(i,j)$ are the pseudo-coordinates of node pair $v_i$ and $v_j$, $\mathcal { F } _ { k } ^ { l } ( \mathbf { u } )$ is a parametric function to be learned, $h _ { i k } ^ { l }$ is the $k^{th}$ dimension of $h^l$.

GCNs & GNNs:

Basic Framework:

Graph Networks propose a more general framework for both GCNs and GNNs to learn three set of representations: $\mathbf { h } _ { i } ^ { l }, \mathbf { e } _ { i j } ^ { l } , \mathbf { z } ^ { l }$ as representation for nodes, edges and the whole graph respectively.

• Generate the “messages”:

• Update the represenations:

Reachout Operation:

Motivation: to tackle graph-focused tasks, information of nodes need to be aggregated to form a graph-level representation. Attention: Order invariance.

• Statistics (Pooling):

• Hierarchical clustering:

• Others (Special Nodes, etc)

Improvements and Discussions:

Attention Mechanism:

Residual and Jumping Connections:

Edge Features: {Node, Edge} <-> {Node, Edge}

Accelerating by Sampling:

• GraphSAGE uniformly samples a fixed number of neighbors for each node during training.
• PinSage further proposes sampling neighbors using random walks on graphs together with several implementation improvements.
• FastGCN adopts a different sampling strategy. Instead of sampling neighbors of each node, the authors suggest sampling nodes in each convolutional layer.