Graph Representations for Machine Learning

To process graph data effectively with machine learning models, especially Graph Neural Networks, converting the graph's structure and associated information into suitable numerical formats is essential. The specific representation of the graph profoundly influences how messages are computed and what properties the model can learn. Standard and more advanced ways graphs are encoded for computation are examined here.

Representing Graph Structure

The most fundamental way to represent the connectivity of a graph $G = (V, E)$, where $V$ is the set of nodes (vertices) and $E$ is the set of edges, is the Adjacency Matrix.

Adjacency Matrix ($A$)

For a graph with $N = |V|$ nodes, the adjacency matrix $A$ is an $N \times N$ matrix where:

$$A_{ij} = \begin{cases} 1 & \text{if } (v_i, v_j) \in E \\ 0 & \text{otherwise} \end{cases}$$

For weighted graphs, $A_{ij}$ can represent the weight of the edge between node $v_i$ and node $v_j$. For undirected graphs, $A$ is symmetric ($A = A^T$).

A simple undirected graph with 5 nodes and 5 edges.

For the graph above, the adjacency matrix (assuming nodes are indexed 0 to 4) would be:

$$A = \begin{pmatrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{pmatrix}$$

"Graphs are often sparse, meaning most entries in $A$ are zero. This sparsity is significant for computational efficiency. Storing and performing operations on dense $N \times N$ matrices becomes prohibitive for large $N$. Therefore, sparse matrix formats (like Coordinate List (COO), Compressed Sparse Row (CSR), or Compressed Sparse Column (CSC)) are typically used in GNN libraries. We will discuss these formats further in Chapter 5. The adjacency matrix directly informs the neighborhood $\mathcal{N}(v)$ used in the message passing framework."

Graph Laplacians

While the adjacency matrix captures direct connections, Graph Laplacians encode information about node degrees and graph structure in a way that's particularly useful for analyzing graph properties and forming the basis of spectral GNNs.

First, we define the Degree Matrix $D$. This is an $N \times N$ diagonal matrix where $D_{ii}$ is the degree of node $v_i$ (the number of edges connected to it), and all off-diagonal entries are zero.

$$D_{ii} = \text{deg}(v_i) = \sum_{j} A_{ij}$$

Using $A$ and $D$, we can define several forms of the Graph Laplacian:

1. Combinatorial Laplacian ($L$):

   $$L = D - A$$

   This is perhaps the most basic form. Its properties are linked to graph connectivity. For example, the number of connected components in the graph is equal to the multiplicity of the eigenvalue 0 of $L$. It's a symmetric positive semi-definite matrix.

2. Symmetric Normalized Laplacian ($\mathcal{L}_{sym}$):

   $$\mathcal{L}_{sym} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} A D^{-1/2}$$

   Here, $I$ is the identity matrix, and $D^{-1/2}$ is the diagonal matrix with entries $(D_{ii})^{-1/2}$. This normalization keeps the matrix symmetric and ensures its eigenvalues are bounded between 0 and 2. This bounding is advantageous when designing spectral filters for GNNs, as it prevents numerical instability. Note that computing $D^{-1/2}$ requires $D_{ii} > 0$. Nodes with degree 0 might need special handling depending on the application.

3. Random Walk Normalized Laplacian ($\mathcal{L}_{rw}$):

   $$\mathcal{L}_{rw} = D^{-1} L = I - D^{-1} A$$

   This version is generally not symmetric. It's closely related to the transition matrix of a random walk on the graph ($P = D^{-1}A$). The term $D^{-1}A$ represents the averaging of neighbor features, weighted inversely by the sending node's degree, which forms the core aggregation step in simple Graph Convolutional Networks (GCNs).

Laplacians capture relational information differently than the adjacency matrix. Their spectral properties (eigenvalues and eigenvectors) reveal significant structural information about the graph, such as connectivity and partitioning, forming the foundation of spectral graph theory and spectral GNNs, which we will explore further in Section 1.3 and Chapter 2.

Representing Node and Edge Attributes

Graphs in machine learning contexts rarely consist of only structure. Nodes and edges often carry attributes or features that provide valuable information.

Node Features ($X$)

Node features are typically represented as an $N \times F$ matrix $X$, where $N$ is the number of nodes and $F$ is the number of features per node. Each row $X_v$ corresponds to the feature vector of node $v$.

$$X = \begin{pmatrix} - & \mathbf{x}_1^T & - \\ - & \mathbf{x}_2^T & - \\ & \vdots & \\ - & \mathbf{x}_N^T & - \end{pmatrix}$$

These features can be:

• Structural: Derived from the graph itself (e.g., node degree, centrality measures, clustering coefficients).
• Content-based: External information associated with nodes (e.g., text profiles of users in a social network, chemical properties of atoms in a molecule, pixel values of superpixels in an image).
• Positional/Temporal: Encodings representing a node's position or role in the graph or its state at a particular time.

The nature and quality of node features are critical for GNN performance. If features are absent, methods like assigning constant values, unique one-hot identifiers, or using structural features might be employed. Feature processing techniques like normalization or standardization are often applied. The initial node feature matrix $X$ typically serves as the input $\mathbf{h}_v^{(0)}$ in the message passing framework.

Edge Features ($E$)

Edges can also possess features, especially in contexts like knowledge graphs (where edges represent relations), molecular graphs (bond types), or transportation networks (road types, travel times). These can be represented in various ways, often as a tensor $E$ of shape $|E| \times F_e$, where $F_e$ is the number of edge features, or integrated directly into the message passing computation based on the specific edge connecting two nodes. Handling edge features requires specific GNN architectures, such as Relational GCN (RGCN), which we will cover in Chapter 4.

Representation Approaches

The choice of representation ($A$, $L$, $\mathcal{L}_{sym}$, etc.) and the handling of features ($X$, $E$) directly impact:

• Computational Efficiency: Sparse representations ($A$ in COO/CSR format) are essential for large graphs. Operations involving dense Laplacians can be bottlenecks.
• Model Design: Spectral GNNs explicitly use Laplacians or their variants. Spatial GNNs often implicitly use $A$ or normalized versions like $D^{-1/2} A D^{-1/2}$ or $D^{-1} A$ within their aggregation steps.
• Information Captured: Different representations emphasize different aspects of graph structure. Laplacians encode smoothness and connectivity information used in spectral methods. The basic adjacency matrix encodes direct neighbor relationships used in spatial message passing.
• Expressive Power: As we'll see in Section 1.5, the ability of standard message passing GNNs (relying primarily on $A$ and $X$) to distinguish non-isomorphic graphs is limited, partly due to the local nature of information encoded in these basic representations. More sophisticated representations or GNN mechanisms are needed to capture higher-order structures.

Understanding these different ways to encode graph structure and features numerically is the first step towards building and analyzing the advanced GNN architectures discussed in the subsequent chapters. We now have the vocabulary to discuss message passing and spectral methods with greater precision.