Alessio Borgi

Alessio Borgi

PhD in Graph Neural Networks and Generative AI 👨🏻‍💻🤖

The Graph Adjacency Matrix: A Graph in Matrix Form

3 minute read

Published:

TL;DR: The adjacency matrix A of a graph with N nodes is an N×N matrix where A[i][j] = 1 if nodes i and j are connected, and 0 otherwise. It's the primary mathematical representation used inside GNNs.

What Is the Adjacency Matrix?

Take a graph with N nodes. The adjacency matrix A is an N×N grid where:

A[i][j] = 1    if there is an edge between node i and node j
A[i][j] = 0    otherwise
Graph G 1 2 3 4 Adjacency Matrix A – 1 2 3 4 1 2 3 4 0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0 A is symmetric (undirected graph): A = Aᵀ
Figure 1: A graph with 4 nodes and 5 edges (left) and its 4×4 adjacency matrix (right). Green cells indicate edges; 0 cells indicate no edge. The diagonal is 0 (no self-loops by default).

Key Properties

Symmetry: For undirected graphs, A[i][j] = A[j][i] always — the matrix is symmetric. Directed graphs have asymmetric adjacency matrices.

Degree: The degree of node i is the number of edges it has. It equals the sum of row i in A: deg(i) = Σⱼ A[i][j]. The degree matrix D is a diagonal matrix where D[i][i] = deg(i).

Sparsity: Real-world graphs are sparse — most node pairs have no edge. A social network with 1M users has O(10M) edges, not O(10¹²). Sparse matrix representations (edge lists, COO format) are crucial for efficiency.

Powers of A: A²[i][j] counts the number of paths of length 2 from i to j. More generally, Aᵏ[i][j] counts paths of length k. This is the mathematical basis for why GNN layers with k layers capture k-hop neighbourhoods.

Weighted Graphs

In a weighted graph, A[i][j] = w_{ij} — the weight of the edge between i and j (0 if no edge). For molecules, this could be bond strength; for road networks, road capacity; for social networks, interaction frequency.

Self-Loops

Some GNN formulations add self-loops by modifying the adjacency matrix: Ã = A + I (where I is the identity matrix). This ensures each node “sees itself” during aggregation — without this, a node’s own features might be ignored.

This is exactly what GCN does (see the GCN post).

In GNNs: Matrix Multiplication = Neighbourhood Aggregation

The most important use of A in GNNs: multiplying A by the feature matrix H performs one round of neighbourhood aggregation:

H_new = A · H

Row i of A·H is a sum of feature vectors of all neighbours of node i. This is precisely message passing: aggregate all neighbour features.

Normalising by degree: D⁻¹ · A · H gives the mean of neighbour features — the basis for many GNN designs.

✅ Key Takeaways

  • The adjacency matrix A encodes the graph's connectivity: A[i][j] = 1 if (i,j) is an edge.
  • For undirected graphs, A is symmetric. The degree matrix D has degrees on the diagonal.
  • Matrix-vector multiplication A·H aggregates neighbour features — the mathematical core of GNNs.
  • Adding the identity (Ã = A+I) creates self-loops so each node includes its own features during aggregation.

You May Also Enjoy

GraphSAGE: Inductive Learning on Large Graphs

3 minute read

Published:

GCN and GAT learn embeddings for fixed graphs — add a new node and you’re stuck. GraphSAGE (Hamilton et al., 2017) learns an aggregation function instead, so it can generate embeddings for entirely new nodes at inference time.

GAT: Graph Attention Networks

3 minute read

Published:

GCN assigns the same (degree-based) weight to every neighbour. GAT learns which neighbours actually matter — using attention coefficients on edges. More expressive, more interpretable.

GCN: Graph Convolutional Networks

3 minute read

Published:

GCN (Kipf & Welling, 2016) is the ‘hello world’ of GNNs. It simplifies spectral graph convolution into a single elegant layer: normalised neighbourhood averaging with a learned linear transformation.