Node Classification

A Graph Convolutional Network, or GCN, is an approach for semi-supervised learning on graph-structured data. It is based on an efficient variant of convolutional neural networks which operate directly on graphs. The choice of convolutional architecture is motivated via a localized first-order approximation of spectral graph convolutions. The model scales linearly in the number of graph edges and learns hidden layer representations that encode both local graph structure and features of nodes.

Laplacian eigenvectors represent a natural generalization of the Transformer positional encodings (PE) for graphs as the eigenvectors of a discrete line (NLP graph) are the cosine and sinusoidal functions. They help encode distance-aware information (i.e., nearby nodes have similar positional features and farther nodes have dissimilar positional features). Hence, Laplacian Positional Encoding (PE) is a general method to encode node positions in a graph. For each node, its Laplacian PE is the k smallest non-trivial eigenvectors.

Diffusion-convolutional neural networks (DCNN) is a model for graph-structured data. Through the introduction of a diffusion-convolution operation, diffusion-based representations can be learned from graph structured data and used as an effective basis for node classification. Description and image from: Diffusion-Convolutional Neural Networks

A Graph Attention Network (GAT) is a neural network architecture that operates on graph-structured data, leveraging masked self-attentional layers to address the shortcomings of prior methods based on graph convolutions or their approximations. By stacking layers in which nodes are able to attend over their neighborhoods’ features, a GAT enables (implicitly) specifying different weights to different nodes in a neighborhood, without requiring any kind of costly matrix operation (such as inversion) or depending on knowing the graph structure upfront. See here for an explanation by DGL.

GraphSAGE is a general inductive framework that leverages node feature information (e.g., text attributes) to efficiently generate node embeddings for previously unseen data. Image from: Inductive Representation Learning on Large Graphs

node2vec is a framework for learning graph embeddings for nodes in graphs. Node2vec maximizes a likelihood objective over mappings which preserve neighbourhood distances in higher dimensional spaces. From an algorithm design perspective, node2vec exploits the freedom to define neighbourhoods for nodes and provide an explanation for the effect of the choice of neighborhood on the learned representations. For each node, node2vec simulates biased random walks based on an efficient network-aware search strategy and the nodes appearing in the random walk define neighbourhoods. The search strategy accounts for the relative influence nodes exert in a network. It also generalizes prior work alluding to naive search strategies by providing flexibility in exploring neighborhoods.

There are at least eight notable examples of models from the literature that can be described using the Message Passing Neural Networks (MPNN) framework. For simplicity we describe MPNNs which operate on undirected graphs $G$ with node features $x_{v}$ and edge features $e_{vw}$. It is trivial to extend the formalism to directed multigraphs. The forward pass has two phases, a message passing phase and a readout phase. The message passing phase runs for $T$ time steps and is defined in terms of message functions $M_{t}$ and vertex update functions $U_{t}$. During the message passing phase, hidden states $h_{v}^{t}$ at each node in the graph are updated based on messages $m_{v}^{t+1}$ according to $$ m_{v}^{t+1} = \sum_{w \in N(v)} M_{t}(h_{v}^{t}, h_{w}^{t}, e_{vw}) $$ $$ h_{v}^{t+1} = U_{t}(h_{v}^{t}, m_{v}^{t+1}) $$ where in the sum, $N(v)$ denotes the neighbors of $v$ in graph $G$. The readout phase computes a feature vector for the whole graph using some readout function $R$ according to $$ \hat{y} = R(\\{ h_{v}^{T} | v \in G \\}) $$ The message functions $M_{t}$, vertex update functions $U_{t}$, and readout function $R$ are all learned differentiable functions. $R$ operates on the set of node states and must be invariant to permutations of the node states in order for the MPNN to be invariant to graph isomorphism.

DeepWalk learns embeddings (social representations) of a graph's vertices, by modeling a stream of short random walks. Social representations are latent features of the vertices that capture neighborhood similarity and community membership. These latent representations encode social relations in a continuous vector space with a relatively small number of dimensions. It generalizes neural language models to process a special language composed of a set of randomly-generated walks. The goal is to learn a latent representation, not only a probability distribution of node co-occurrences, and so as to introduce a mapping function $\Phi \colon v \in V \mapsto \mathbb{R}^{|V|\times d}$. This mapping $\Phi$ represents the latent social representation associated with each vertex $v$ in the graph. In practice, $\Phi$ is represented by a $|V| \times d$ matrix of free parameters.

Per the authors, Graph Isomorphism Network (GIN) generalizes the WL test and hence achieves maximum discriminative power among GNNs.

The ARMA GNN layer implements a rational graph filter with a recursive approximation.

Mixture model network (MoNet) is a general framework allowing to design convolutional deep architectures on non-Euclidean domains such as graphs and manifolds. Image and description from: Geometric deep learning on graphs and manifolds using mixture model CNNs

An RGCN, or Relational Graph Convolution Network, is a an application of the GCN framework to modeling relational data, specifically to link prediction and entity classification tasks. See here for an in-depth explanation of RGCNs by DGL.

Deep Graph Infomax (DGI), a general approach for learning node representations within graph-structured data in an unsupervised manner. DGI relies on maximizing mutual information between patch representations and corresponding high-level summaries of graphs—both derived using established graph convolutional network architectures. The learnt patch representations summarize subgraphs centered around nodes of interest, and can thus be reused for downstream node-wise learning tasks. In contrast to most prior approaches to unsupervised learning with GCNs, DGI does not rely on random walk objectives, and is readily applicable to both transductive and inductive learning setups. Description and image from: DEEP GRAPH INFOMAX

Transformer neural networks have achieved state-of-the-art results for unstructured data such as text and images but their adoption for graph-structured data has been limited. This is partly due to the difficulty of incorporating complex structural information in the basic transformer framework. We propose a simple yet powerful extension to the transformer - residual edge channels. The resultant framework, which we call Edge-augmented Graph Transformer (EGT), can directly accept, process and output structural information as well as node information. It allows us to use global self-attention, the key element of transformers, directly for graphs and comes with the benefit of long-range interaction among nodes. Moreover, the edge channels allow the structural information to evolve from layer to layer, and prediction tasks on edges/links can be performed directly from the output embeddings of these channels. In addition, we introduce a generalized positional encoding scheme for graphs based on Singular Value Decomposition which can improve the performance of EGT. Our framework, which relies on global node feature aggregation, achieves better performance compared to Convolutional/Message-Passing Graph Neural Networks, which rely on local feature aggregation within a neighborhood. We verify the performance of EGT in a supervised learning setting on a wide range of experiments on benchmark datasets. Our findings indicate that convolutional aggregation is not an essential inductive bias for graphs and global self-attention can serve as a flexible and adaptive alternative.

Neural message-passing algorithms for semi-supervised classification on graphs have recently achieved great success. However, for classifying a node these methods only consider nodes that are a few propagation steps away and the size of this utilized neighbourhood is hard to extend. This paper uses the relationship between graph convolutional networks (GCN) and PageRank to derive an improved propagation scheme based on personalized PageRank. We utilize this propagation procedure to construct a simple model, personalized propagation of neural predictions (PPNP), and its fast approximation, APPNP. Our model's training time is on par or faster and its number of parameters is on par or lower than previous models. It leverages a large, adjustable neighbourhood for classification and can be easily combined with any neural network. We show that this model outperforms several recently proposed methods for semi-supervised classification in the most thorough study done so far for GCN-like models.

DiffPool is a differentiable graph pooling module that can generate hierarchical representations of graphs and can be combined with various graph neural network architectures in an end-to-end fashion. DiffPool learns a differentiable soft cluster assignment for nodes at each layer of a deep GNN, mapping nodes to a set of clusters, which then form the coarsened input for the next GNN layer. Description and image from: Hierarchical Graph Representation Learning with Differentiable Pooling

GCNII is an extension of a Graph Convolution Networks with two new techniques, initial residual and identify mapping, to tackle the problem of oversmoothing -- where stacking more layers and adding non-linearity tends to degrade performance. At each layer, initial residual constructs a skip connection from the input layer, while identity mapping adds an identity matrix to the weight matrix.

Scalable method to train large scale GNN models via sampling small subgraphs.

ChebNet involves a formulation of CNNs in the context of spectral graph theory, which provides the necessary mathematical background and efficient numerical schemes to design fast localized convolutional filters on graphs. Description from: Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

Principal Neighbourhood Aggregation (PNA) is a general and flexible architecture for graphs combining multiple aggregators with degree-scalers (which generalize the sum aggregator).

Graph Contrastive Coding is a self-supervised graph neural network pre-training framework to capture the universal network topological properties across multiple networks. GCC's pre-training task is designed as subgraph instance discrimination in and across networks and leverages contrastive learning to empower graph neural networks to learn the intrinsic and transferable structural representations.

Please enter a description about the method here

Cluster-GCN is a novel GCN algorithm that is suitable for SGD-based training by exploiting the graph clustering structure. Cluster-GCN works as the following: at each step, it samples a block of nodes that associate with a dense subgraph identified by a graph clustering algorithm, and restricts the neighborhood search within this subgraph. This simple but effective strategy leads to significantly improved memory and computational efficiency while being able to achieve comparable test accuracy with previous algorithms. Description and image from: Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks

Gated Attention Networks (GaAN) is a new architecture for learning on graphs. Unlike the traditional multi-head attention mechanism, which equally consumes all attention heads, GaAN uses a convolutional sub-network to control each attention head’s importance. Image credit: GaAN: Gated Attention Networks for Learning on Large and Spatiotemporal Graphs

AdaGPR is an adaptive, layer-wise graph convolution model. AdaGPR applies adaptive generalized Pageranks at each layer of a GCNII model by learning to predict the coefficients of generalized Pageranks using sparse solvers.

TL;DR: CT-Layer is a GNN Layer which is able to rewire a graph in an inductive an parameter-free way according to the commute times distance (or effective resistance). We address it learning a differentiable way to compute the CT-embedding of the graph. ### Summary CT-Layer is able to Learn the Commute Times distance between nodes (i.e. effective resistance distance) in a differentiable way, instead of the common spectral version, and in a parameter free manner, which is not the cased of the heat kernel. This approach allow to solve it as an optimization problem inside a GNN, leading to have a new layer which is able to learn how rewire a given graph in an optimal, and inductive way. In addition, CT-Layer also is able to learn Commute Times embeddings, and then calculate it for any graph in an inductive way. The Commute Times embedding is also related with the eigenvalues and eigenvectors of the Laplacian of the graph, because CT embedding is just the eigenvectors scaled. Therefore, CT-Layer is also able to learn hot to calculate the spectrum of the Laplacian in a differentiable way. Therefore, this embedding must satisfy orthogonality and normality. Finally, recent connections has been found between commute times distance and curvature (which is non-differentiable), establishing equivalences between them. Therefore, CT-Layer can also be seen as the differentiable version of the curvature rewiring. **We are going through a quick overview of the layer, but I suggest go to the paper for a detailed explanation. ** ### Spectral CT- Embedding downsides CT-embedding $\mathbf{Z}$ is computed spectrally in the literature (until the proposal of this method) or it is approximated using the heat kernel (very dependent on hyperparameter $t$). This fact does not allow us to propose differentiable methods using that measure: $$ \mathbf{Z}=\sqrt{vol(G)}\mathbf{\Lambda}^\frac{1}{2}\mathbf{F}^T \textrm{ given } \mathbf{L}=\mathbf{F}\mathbf{\Lambda}\mathbf{F}^T $$ Then, CT-distance is given by the Euclidean distances between the embeddings $CT_{uv} = ||\mathbf{z_u}-\mathbf{z_v}||^2$. The spectral form is: $$ \frac{CT_{uv}}{vol(G)} = \sum_{i=2}^n \frac{1}{\lambda_i} (\mathbf{f}(u)-\mathbf{f}(v))^2 $$ being $\mathbf{f}$ the eigenvectors of the graph Laplacian. This embedding and distances gives us desirable properties of the graph, such an understanding of the structure, or an embedding based on the spectrum which minimizes Dirichlet energies. However, the spectral computation is not differentiable. ### CT-Layer as an optimization problem: Differentiable, learnable and inductive CT-Layer Giving that $\mathbf{Z}$ minimizes Dirichlet energies s.t. being orthogonal and normalized, we can formulate this problem as constraining neighboring nodes to have a similar embeddings s.t. $\mathbf{Z}\mathbf{Z}^T=\mathbf{I}$. $$ \mathbf{Z} = \arg\min_{\mathbf{Z}^T\mathbf{Z}=\mathbf{I}} \frac{\sum\_{u,v} ||\mathbf{z_u}-\mathbf{z_v}||^2\mathbf{A}\_{uv}}{\sum\_{u,v} \mathbf{Z}^2\_{uv} d_u}=\frac{Tr[\mathbf{Z}^T\mathbf{L}\mathbf{Z}]}{Tr[\mathbf{Z}^T\mathbf{D}\mathbf{Z}]} $$ With the above elements we have a definition of CT-Layer, our rewiring layer: Given the matrix $\mathbf{X}\_{n\times F}$ encoding the features of the nodes after any message passing (MP) layer, $\mathbf{Z}\_{n\times O(n)}=\tanh(\textrm{MLP}(\mathbf{X}))$ learns the association $\mathbf{X}\rightarrow \mathbf{Z}$ while $\mathbf{Z}$ is optimized according to the loss $$ L\_{CT} = \frac{Tr[\mathbf{Z}^T\mathbf{L}\mathbf{Z}]}{Tr[\mathbf{Z}^T\mathbf{D}\mathbf{Z}]} + \left\|\frac{\mathbf{Z}^T\mathbf{Z}}{\|\mathbf{Z}^T\mathbf{Z}\|\_F} - \mathbf{I}\_n\right\|\_F $$ This results in the following resistance diffusion $\mathbf{T}^{CT} = \mathbf{R}(\mathbf{S})\odot \mathbf{A}$ (Hadamard product between the resistance distance and the adjacency) which provides as input to the subsequent MP layer a learnt convolution matrix. As explained before, $\mathbf{Z}$ is the commute times embedding matrix and the pairwise euclidian distance of that learned embeddings are the commute times distances or resistance distances. Therefore, once trained this layer, it will be able to calculate the commute times embedding for a new graph, and rewire that new and unseen graph in a principled way based on the commute times distance. ## Preservation of Structure Does this rewiring preserve the original structure? Let $G' = \textrm{Sparsify}(G, q)$ be a sampling algorithm of graph $G = (V, E)$, where edges $e \in E$ are sampled with probability $q\propto R_e$ (proportional to the effective resistance, i.e. commute times). Then, for $n = |V|$ sufficiently large and $1/\sqrt{n}< \epsilon\le 1$, we need O(n\log n/\epsilon^2)$ samples to satisfy: $$ \forall \mathbf{x}\in\mathbb{R}^n:\; (1-\epsilon)\mathbf{x}^T\mathbf{L}\_G\mathbf{x}\le\mathbf{x}^T\mathbf{L}\_{G'}\mathbf{x}\le (1+\epsilon)\mathbf{x}^T\mathbf{L}\_G\mathbf{x} $$ The intuitions behind is that Dirichlet energies in $G'$ are bounded in $(1\pm \epsilon)$ of the Dirichlet energies of the original graph $G$.

The core ingredient of CayleyNet is a new class of parametric rational complex functions (Cayley polynomials) allowing to efficiently compute spectral filters on graphs that specialize on frequency bands of interest. The model generates rich spectral filters that are localized in space, scales linearly with the size of the input data for sparsely-connected graphs, and can handle different constructions of Laplacian operators. Description adapted from: CayleyNets: Graph Convolutional Neural Networks with Complex Rational Spectral Filters

TL;DR: GAP-Layer is a GNN Layer which is able to rewire a graph in an inductive an parameter-free way optimizing the spectral gap (minimizing or maximizing the bottleneck size), learning a differentiable way to compute the Fiedler vector and the Fiedler value of the graph. ## Summary GAP-Layer is a rewiring layer based on minimizing or maximizing the spectral gap (or graph bottleneck size) in an inductive way. Depending on the mining task we want to perform in our graph, we would like to maximize or minimize the size of the bottleneck, aiming to more connected or more separated communities. ## GAP-Layer: Spectral Gap Rewiring #### Loss and derivatives using $\mathbf{L}$ or $\mathbf{\cal L}$ For this explanation, we are going to suppose we want to minimize the spectral gap, i.e. make the graph bottleneck size smaller. For minimizing the spectral GAP we minimize this loss: $$ L\_{Fiedler} = \|\tilde{\mathbf{A}}-\mathbf{A}\| \_F + \alpha(\lambda\_2)^2 $$ The gradients of this cost function w.r.t each element of $\mathbf{A}$ are not trivial. Depending on if we use the Laplacian, $\mathbf{L}$, or the normalized Laplacian, $\cal L$, the derivatives are going to be different. For the former case ($\mathbf{L}$), we will use the derivatives presented in Kang et al. 2019. In the latter scenario ($\cal L$), we present the Spectral Gradients: derivatives from the spectral gap w.r.t. the Normalized Laplacian. However, whatever option we choose, $\lambda_2$ can seen as a function of $\tilde{\mathbf{A}}$ and , hence, $\nabla\_{\tilde{\mathbf{A}}}\lambda\_2$, the gradient of $\lambda\_2$ wrt each component of $\tilde{\mathbf{A}}$ (how does the bottleneck change with each change in our graph?), comes from the chain rule of the matrix derivative $Tr\left[\left(\nabla\_{\tilde{\mathbf{L}}}\lambda\_2\right)^T\cdot\nabla\_{\tilde{\mathbf{A}}}\tilde{\mathbf{L}}\right]$ if using the Laplacian or $Tr\left[\left(\nabla\_{\tilde{\mathbf{\cal L}}}\lambda\_2\right)^T\cdot\nabla\_{\tilde{\mathbf{A}}}\tilde{\mathbf{\cal L}}\right]$ if using the normalized Laplacian. Both of this derivatives, relies on the Fiedler vector (2nd eigenvector: $\mathbf{f}\_2$ if we use $\mathbf{L}$ and $\mathbf{g}\_2$ if using $\mathbf{\cal L}$ instead). For more details on those derivatives, and for the sake of simplicity in this blog explanation, I suggest go to the original paper. #### Differentiable approximation of $\mathbf{f}_2$ and $\lambda_2$ Once we have those derivatives, the problem is still not that trivial. Note that our cost function $L\_{Fiedler}$, relies on an eigenvalue $\lambda\_2$. In addition, the derivatives also depends on the Fiedler vector $\mathbf{f}\_2$ or $\mathbf{g}\_2$, which is the eigenvector corresponding to the aforementioned eigenvalue. However, we DO NOT COMPUTE IT SPECTRALLY, as its computation has a complexity of $O(n^3)$ and would need to be computed in every learning iteration. Instead, we learn an approximation of $\mathbf{f}\_2$ and use its Dirichlet energy ${\cal E}(\mathbf{f}\_2)$ to approximate the $\lambda_2$. $$ \mathbf{f}\_2(u) = \begin{array}{cl} +1/\sqrt{n} & \text{if}\;\; u\;\; \text{belongs to the first cluster} \\ -1/\sqrt{n} & \text{if}\;\; u\;\; \text{belongs to the second cluster} \end{array} $$ In addition, if using $\mathbf{\cal L}$, since $\mathbf{g}\_2=\mathbf{D}^{1/2}\mathbf{f}_2$, we first approximate $\mathbf{g}_2$ and then approximate $\lambda_2$ from ${\cal E}(\mathbf{g}\_2)$. With this approximation, we can easily compute the node belonging to each cluster with a simple MLP. In addition, such as the Fiedler value must satisfy orthogonality and normality, restrictions must be added to that MLP Clustering. ### GAP-Layer To sum up, GAP-Layer can be defined as the following. Given the matrix $\mathbf{X}\_{n\times F}$ encoding the features of the nodes after any message passing (MP) layer, $\mathbf{S}\_{n\times 2}=\textrm{Softmax}(\textrm{MLP}(\mathbf{X}))$ learns the association $\mathbf{X}\rightarrow \mathbf{S}$ while $\mathbf{S}$ is optimized according to the loss: $$ L\_{Cut} = -\frac{Tr[\mathbf{S}^T\mathbf{A}\mathbf{S}]}{Tr[\mathbf{S}^T\mathbf{D}\mathbf{S}]} + \left\|\frac{\mathbf{S}^T\mathbf{S}}{\|\mathbf{S}^T\mathbf{S}\|\_F} - \frac{\mathbf{I}\_n}{\sqrt{2}}\right\|\_F $$ Then, the $\mathbf{f}\_2$ is approximated from $\mathbf{S}$ using $\mathbf{f}\_2(u)$ equation. Once calculated $\mathbf{f}\_2$ and $\lambda\_2$ we consider the loss: $$ L\_{Fiedler} = \|\tilde{\mathbf{A}}-\mathbf{A}\|\_F + \alpha(\lambda\_2)^2 $$ $$\mathbf{\tilde{A}} = \mathbf{A} - \mu \nabla_\mathbf{\tilde{A}}\lambda\_2$$ returning $\tilde{\mathbf{A}}$. Then the GAP diffusion $\mathbf{T}^{GAP} = \tilde{\mathbf{A}}(\mathbf{S}) \odot \mathbf{A}$ results from minimizing $$L_{GAP}= L\_{Cut} + L\_{Fiedler}$$ References (Kang et al. 2019) Kang, J., & Tong, H. (2019, November). N2n: Network derivative mining. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management (pp. 861-870).