Most models we have examined implicitly assume that the entire dataset is i.i.d.—independent and identically distributed. In other words, every sample in a modality exists independently and is unaffected by other samples during inference. Neural networks over graphs take a different approach.

What Is a Graph?

As shown above, a graph consists of individual vertices or nodes (points) and the edges (lines) connecting them. Each node or vertex represents an item or entity, while an edge represents the relationship between two of them.

What Is a Euclidean Domain?

A Euclidean function $f : R \rightarrow \mathbb{N}$ defined over a domain $R$ must satisfy the following property.

$$\begin{aligned} \text{For arbitrary }&a\in R \text{ and }b \in R, \newline &a = bq+r \newline \text{there exist }&q, r \in R\text{ such that }r = 0 \text{ or }f(r) < f(b). \end{aligned}$$

A Euclidean domain is simply an integral domain for which at least one such Euclidean function exists. The terminology may seem difficult in isolation, but examples of datasets in Euclidean domains make the idea easier to understand.

An image like the one above can be represented as data on a 2D grid. A 2D grid is a representative Euclidean domain—ordinary coordinate systems fall into this category—so image data can be called Euclidean. Likewise, tokenizing a sentence or speech signal and processing it as embeddings places the data on a 1D grid, another Euclidean domain.

A graph structure, however, is non-Euclidean. A 3D mesh whose faces are connected through vertices and edges is one example, as is a social network defined by relationships among users. On Instagram, users A, B, C, and so on may be connected as friends, close friends, frequent DM correspondents, or even non-friends who exchange DMs. Each user can also have properties such as a private account, public account, or an account that posts stories frequently.

Structures used for pose estimation are another example. In general, non-Euclidean data that cannot be placed on a grid includes any modality defined by relationships between points.

Graph Notation

Before continuing, let us define the notation used throughout the discussion.

• $V$ : A set of vertices(node)
• $N$ : The number of vertices in a set of vertices $V$
• $v_i$ : The $i^{th}$ vertex in a set of vertices $V$
• $v_i^F$ : The feature vector of vertex $v_i$
• $ne(v_i)$ : The set of vertex indices for the vertices that are direct neighbors of $v_i$
• $E$ : A set of edges
• $M$ : The number of edges in a set of edges $E$
• $e_{i,j}$ : The edge between the $i^{th}$ vertex and the $j^{th}$ vertex, in a set of edges $E$.
• $e_{i,j}^F$ : The feature vector of edge $e_{i,j}$
• $h_i^k$ : The $k^{th}$ hidden layer's representation of the $i^{th}$ vertex's local neighborhood.
• $o_i$ : The $i^{th}$ output of GNN(indexing is framework dependent)
• $G = G(V, E)$ : A graph defined by the set of vertices $V$ and the set of edges $E$

A vertex feature vector describes the properties of that node. It may include the vertex number or index; for a person, it might include their name, nationality, and age.

We also need representations of graph connectivity.

• $A$ : The adjacency matrix; each element $A_{i, j}$ represents if the $i^{th}$ vertex is connected to the $j^{th}$ vertex by a weight
• $W$ : The weight matrix; each element $W_{i,j}$ represents the 'weight' of the edge between the $i^{th}$ vertex and the $j^{th}$ vertex. The 'weight' typically represents some real concept of property. For example, the weight between two given vertices could be inversely proportional to their distance from one another(i.e., close vertices have a higher weight between them). Graphs with a weight matrix are referred to as weighted graphs, but not all graphs are weighted graphs.
• $D$ : The degree matrix; a diagonal matrix of vertex degrees or valencies(the number of edges incident to a vertex). Formally defined as $D_{i,j} = \sum_j A_{i, j}$
• $L$ : The non-normalized graph Laplacian; defined as $L = D-W$. For unweighted graphs, $W = A$. Using these definitions, we can derive each component of the graph above.

$$D = \begin{bmatrix} 2 & 0 & 0 & 0 & 0 & 0 \newline 0 & 3 & 0 & 0 & 0 & 0 \newline 0 & 0 & 2 & 0 & 0 & 0 \newline 0 & 0 & 0 & 3 & 0 & 0 \newline 0 & 0 & 0 & 0 & 3 & 0 \newline 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}$$

First, $D$ is a diagonal matrix containing only $d_{i,j}$ where $i=j$. Each element gives the number of other nodes connected to that node.

$$A = \begin{bmatrix} 0 & 1 & 0 & 0 & 1 & 0 \newline 1 & 0 & 1 & 0 & 1 & 0 \newline 0 & 1 & 0 & 1 & 0 & 0 \newline 0 & 0 & 1 & 0 & 1 & 1 \newline 1 & 1 & 0 & 1 & 0 & 0 \newline 0 & 0 & 0 & 1 & 0 & 0 \end{bmatrix}$$

For $A$, element $a_{i,j}$ indicates whether vertex $i$ and vertex $j$ are connected, using $0$ or $1$. The matrix is therefore symmetric, as shown.

$$L = \begin{bmatrix} 2 & -1 & 0 & 0 & -1 & 0 \newline -1 & 3 & -1 & 0 & -1 & 0 \newline 0 & -1 & 2 & -1 & 0 & 0 \newline 0 & 0 & -1 & 3 & -1 & -1 \newline -1 & -1 & 0 & -1 & 3 & 0 \newline 0 & 0 & 0 & -1 & 0 & 1 \end{bmatrix}$$

For an unweighted graph, the unnormalized Laplacian is simply the degree matrix minus the adjacency matrix. Several other Laplacian matrices can also be defined.

• $I_n$ : An $n \times n$ identity matrix; all zeros except for ones along the diagonal.
• $L^{sn}$ : The symmetric normalized graph Laplacian; defined as $L = I_n - D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$
• $L^{rw}$ : The random-walk normalized graph Laplacian; defined as $L = I_n - D^{-1}A$

Graph Neural Networks (GNNs)

A graph neural network (GNN) is a trainable architecture for processing graphs; the graph structure itself enters the neural network during training and evaluation. Because the number of vertices and edges can vary, the architecture does not impose a fixed size. Most importantly, a GNN can process both data in structured Euclidean domains and data in non-Euclidean domains.

A GNN plays a role analogous to an MLP in an ordinary neural network: through repeated feature extraction, it obtains meaningful high-level feature representations from a graph. The resulting high-level feature representation resembles a decoder output in a familiar deep-learning framework.
The goals of a GNN can therefore be divided into two parts.

1. Compute a high-level hidden feature vector for each vertex using transition function $f$.
2. Produce meaningful outputs from the resulting hidden feature vectors $f(\cdot)$ using output function $g$. Let us examine each process.

Step 1: Transition

Consider the nodes adjacent to each vertex $v_i$, denoted above by $ne(v_i)$. We must use these neighborhoods to compute a hidden representation of the target node. Since each vertex can have a different number of neighbors, the transition process computes an aggregation of the neighbors $ne(v_i)$. This gives every vertex a hidden feature vector of the same size. The hidden state $h$, or embedding, of vertex $v_i$ at state $k$ is formulated as follows.

$$h_i^k = \sum_{j \in ne(v_i)} f(v_i^F, e_{i,j}^F, v_j^F, h_j^{k-1}), \text{Where all }h_i^0 \text{ are defined upon initialization}$$

As the expression shows, aggregation is represented by summation. The function takes as input the target vertex's features, each adjacent vertex's features, the edge features describing their relationship, and the adjacent vertex's hidden state. One might ask why it does not include the target vertex's own previous hidden state; the answer is simply that this particular formulation omits it. A concrete formulation may vary by application. Function $f$ is a nonlinear transformation, such as a simple MLP with an activation function.

In this transition process, the $k^{th}$ state means the following.

Nodes have features $v_i^F$ at every layer. At the zeroth layer, the $0^{th}$ state of vertex $A=v_A^F$ is hidden state $h_A^0$. Continuing this process, state $n$ aggregates information from vertices up to $n$ hops away from the target. A GNN transition stage therefore measures how far through the graph the information used to represent the current vertex has traveled.
$k$ can be arbitrarily large; in general, transition function $f$ is applied repeatedly until the $k^{th}$ state becomes stable.

Step 2: Output

After applying function $f$ for $k$ steps until convergence, the graph implicitly contains computed feature vectors. The output function uses these converged hidden states to produce a meaningful output.
Outputs fall into three categories—vertex-level, edge-level, and graph-level—each suited to different tasks.

First, a vertex-level framework uses only vertex information to produce its output: the vertex feature vector $v_i^F$ and hidden state $h_i^{kmax}$.

$$o_i = g(v_i^F,~h_i^{kmax})$$

Typical tasks are node classification or regression, such as labeling an unlabeled node from its neighbors.

Second, an edge-level framework requires five inputs. Because an edge connects two vertices, it needs their two feature vectors $v_i^F$ and $v_j^F$, their hidden states $h_i^{kmax}$ and $h_j^{kmax}$, and the edge feature vector $e_{ij}^F$.

$$o_i = g(v_i^F,~h_i^{kmax},~v_j^F,~h_j^{kmax},~e_{ij}^F)$$

Typical tasks include edge classification—classifying relationships—and, by extension, link prediction. Link prediction asks whether two nodes may develop a meaningful relationship in the future. An online marketplace such as Amazon uses a similar idea when it recommends items you may want after a purchase; many content-recommendation platforms can use it as well.

Third, a graph-level framework uses information from the network as a whole. It need not include every graph feature; depending on the design, it may use final vertex or edge hidden states, or even initial states.

One typical task is graph classification, which assigns different graphs to groups as shown above.

It can also construct a graph over the pixels of an image—data in a Euclidean domain—and classify from that graph.

Reformulation to Neural Network form

The earlier expressions denote transition and output functions abstractly as $f$ and $g$ without showing their neural-network formulation.
Following the perceptron definition, a neural network computes an affine transform for the next state using trainable weights and biases, then applies nonlinear activations so that multiple layers increase functional complexity.

$$\begin{aligned} h_v^0 =& x_v \newline h_v^k =& \sigma\left( W_k \sum_{u \in N(v)} \frac{h_u^{k-1}}{\vert N(v) \vert} \right),~\forall k \in (1, \cdots, K) \newline z_v =& h_v^K \end{aligned}$$

To compute state $k$, $h_v^k$, for vertex $v$, average the $(k-1)^{th}$ hidden states $h_u^{k-1}$ of its adjacent vertices $u$ and multiply by weight $W_k$. Add the previous hidden state $h_v^{k-1}$ of $v$ multiplied by bias term $B_k$, then apply the activation function to the result.

$$\begin{aligned} H^{(l+1)} =& \sigma(H^{(l)}W_0^{(l)}+\tilde{A}H^{(l)}W_1^{(l)}) \newline \text{with } \tilde{A} =& D^{-\frac{1}{2}}AD^{-\frac{1}{2}} \end{aligned}$$

This can also be written in vector form as above. A loss function over the resulting hidden states or embeddings enables gradient-based optimization of trainable weight and bias parameters.

Graph embedding

A trained neural network can map data into an embedding space: a node, a graph substructure, or an entire graph structure can become a vector. Embedding quality is primarily measured by whether similarities in the original graph, such as node similarity, are preserved in the $d$-dimensional embedding space. The resulting embeddings can support many downstream tasks.

Convolutional GNNs

The discussion so far has explained how neural networks infer over graph structures. We now turn to convolutional architectures. Convolutional GNNs, or CGNNs, fall into two types: those in the spatial domain and those in the spectral (frequency) domain.

CGNNs in spatial domain

Consider a digit image with the following graph structure.

Treat the image as a specially structured graph. Convolution multiplies a fixed-size filter, here $3 \times 3$, over the input and aggregates the result, then shifts the filter and repeats.

Ordinary convolution works on modalities such as images, but is difficult to apply to other graphs with spatial order. Unlike images designed around a grid, non-Euclidean datasets can give each vertex a different number of neighbors, preventing uniform aggregation.

In the example above, the target vertices are colored red, green, and blue, with dotted boxes defining their respective neighborhoods. Spatial convolution selects a neighborhood and aggregates its vertex feature vectors. The aggregate determines the target vertex's next embedding. Repeating this process for every neighborhood produces embeddings used by the next spatial-convolution layer, enabling hierarchical feature extraction. The procedure is:

1. Using spatial connectivity, define graph neighborhoods around all vertices and select the first neighborhood in the input graph.
2. Aggregate the values in that neighborhood using an operation such as a sum or mean.
3. Update the vertex hidden state, or embedding, with the resulting value.
4. Repeat for every neighborhood.

The GraphSAGE paper extracts node embeddings and is useful when nodes have rich attribute information.

This operates almost identically to the GNN aggregation expression. Spatial CGNNs use aggregators such as the following.

CGNNs differ from conventional GNNs in one key respect. A GNN repeatedly applies transition function $f$ until its embedding stabilizes, optimizing through $h_v^{kmax}$. A CGNN instead has a fixed number of layers and often uses a single layer for a simple update ($k = 2$).

CGNNs in spectral domain

The spectral domain is the domain of frequency. Frequency is intuitive for temporal signals such as speech because sound transmits information through vibrations in a medium such as air, and the Fourier transform $\mathcal{F}$ is commonly used to analyze it in the frequency domain. Spectral methods can also be applied to image convolution.
After a Fourier transform, image convolution becomes multiplication in the frequency domain.

$$\mathcal{F}(f \ast g) = \mathcal{F}(f) \times \mathcal{F}(g)$$

With this background, let us discuss graph signals.

Graph signals

A graph signal is defined when every vertex maps to a real-valued embedding. A function $f: V \rightarrow \mathbb{R},~\forall V \in G$ over vertices is such a signal. It represents all vertices as a vector of size $N$, where $N$ is the number of vertices and element $i$ is the signal value of vertex $v_i$. Here, $f$ is not a neural network but simply a feature map over vertices.

Laplacian

The Laplacian operator $\Delta$ is the second-order gradient $\nabla^2$. Given graph signal $f$, its gradient is

$$\nabla f(i) = (f(i+1)-f(i))/\delta$$

Here, $\delta$ and $i$ can be replaced by vertex indices $i,j$ and edge weight $w$.

$$\nabla f(i,~j) = (f(i)-f(j))w(i,~j)$$

The Laplacian can then be defined as follows.

$$\begin{aligned} \Delta f(i,~j) =& \sum_j \frac{\partial^2 f(i)}{\partial j^2} \newline \Delta f(i,~j) \simeq& \sum_{j \in \Omega_i} (f(i)-f(j))w(i,~j) \end{aligned}$$

Expanding this into matrix form gives

$$\begin{aligned} \Delta f(i,~j) =& \sum_j \frac{\partial^2 f(i)}{\partial j^2} \newline \simeq& \sum_{j \in \Omega_i} (f(i)-f(j))w(i,~j) \newline =& (\sum_j w_{ij})f(i) - \sum_j w_{ij}f(j) \newline =& (Df)_i - (Wf)_i = ((D-W)f)_i \end{aligned}$$

This explains why the graph Laplacian introduced in the notation section can be expressed using the degree matrix and adjacency—or weight—matrix.

Graph Laplacian

Eigendecomposing $L$ gives $L = U\Lambda U^\top$. Eigenvectors $u_i,~i=0,\cdots,N$ become the Fourier bases of graph $G$, and eigenvalues $\lambda_i,~i=0,\cdots,N$ become its frequency components. The Fourier transform $f \rightarrow \hat{f}$ of graph signal $f$ and its inverse $\hat{f} \rightarrow f$ are then

$$\begin{aligned} \hat{f} =& U^\top f \newline f =& U\hat{f} \end{aligned}$$

as above. Expressing the inner products over the individual Fourier bases gives

$$\begin{aligned} \hat{f} =& U^\top f = \sum_{i=1}^N f(i) u_k^\ast (i) \newline f =& U\hat{f} = \sum_{k=1}^N \hat{f}(k) u_k(i) \end{aligned}$$

The reverse relationship also follows by duality: just as convolution in the spatial domain becomes multiplication in the frequency domain, vertex-wise multiplication corresponds to frequency-domain convolution.

$$(\hat(f) \ast \hat{g})(i) = \sum_{k=1}^N \hat{f}(k) \hat{g}(k) u_k(i)$$

If we can define an arbitrary filter $g$, this enables the following hidden-channel computation. Replacing $g$ with trainable weight $\Theta$ gives

$$\begin{aligned} H_j^k =& \sigma(\sum_{i=1}^{f_{k-1}} U(\Theta^k(U^\top H_i^{k-1}))), \newline \text{where }j =& 1,2, \cdots, f_k \end{aligned}$$

Let us apply this expression to the following graph.

The graph has $N=5$ vertices, $M=5$ edges, and $f_k=2$ graph signals per vertex, where $k$ is the layer index. The feature vectors above are the initial state, so

$$H^0 = \begin{bmatrix} 0.2 & 8 \newline 0.4 & 6 \newline 0.3 & 7 \newline 0.3 & 12 \newline 0.1 & 4 \end{bmatrix}$$

For columns $H^k_1$ and $H^k_2$ to be updated,

$$H^0_1 = \begin{bmatrix} 0.2 & 0.4 & 0.3 & 0.3 & 0.1 \end{bmatrix}^\top$$ $$H^0_2 = \begin{bmatrix} 8 & 6 & 7 & 12 & 4 \end{bmatrix}^\top$$ $$\begin{aligned} H_j^k =& \sigma(\sum_{i=1}^2 U(\Theta^k(U^\top H_i^{k-1}))), \newline \text{where }j =& 1,2 \end{aligned}$$

This is the resulting expression. It requires computing an eigensystem determined by the graph structure. First-generation spectral CGNNs therefore suffered from an eigensystem whose size grew with the node count $N$. Later work addressed this limitation with the second-generation ChebNet and third-generation GCN.

GCN

GCN is the best-known spectral convolutional GNN. It is an $l$-layer network with a more familiar neural-network structure. As shown in the table, its hidden layer uses aggregator $\hat{A}$ as follows.

$$\begin{aligned} H^{(l+1)} =& \sigma(\hat{A}H^{(l)}W^{(l)}), \newline \text{with }\hat{A} =& \tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}X \newline \tilde{D_{ij}} =& \begin{cases} \sum_{k=1} \tilde{A_{ik}} & \text{if }i = j \newline 0 & \text{otherwise} \end{cases} \end{aligned}$$

For the resulting hidden embeddings, the output layer is

$$Z = f(X, A) = softmax(\hat{A}\text{ReLU}(\hat{A}XW^{(0)})W^{(1)})$$

as shown above.

I do not yet fully understand graph-based networks. I may study them further when I have the opportunity, but for now this remains a difficult area for me to explore in depth.