Alessio Borgi

Alessio Borgi

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

The Graph Adjacency Matrix: A Graph in Matrix Form

4 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

Intuition First: Think of the adjacency matrix as a truth table for "are these two nodes friends?" Row i, column j answers: did node i and node j shake hands? For undirected graphs the handshake is mutual, so the table is mirrored across the diagonal.

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.

Step-by-step worked example. Consider a 3-node path graph: 1—2—3.

Adjacency matrix A:        Feature matrix H (each node has 1 feature):
  1  2  3                    node 1: [2]
1[0  1  0]                   node 2: [4]
2[1  0  1]                   node 3: [6]
3[0  1  0]

A · H:
  row 1 = 0·[2] + 1·[4] + 0·[6] = [4]   ← node 1 collects from node 2
  row 2 = 1·[2] + 0·[4] + 1·[6] = [8]   ← node 2 collects from nodes 1 and 3
  row 3 = 0·[2] + 1·[4] + 0·[6] = [4]   ← node 3 collects from node 2

With à = A + I (self-loops added), node 2 would collect [2+4+6] = [12] — including its own feature.

Key Insight: Matrix multiplication with A is simultaneously performing neighbourhood aggregation for every node in one shot. This is why GNNs can be implemented so efficiently — the entire graph is processed with a single sparse matrix multiply.

✅ 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.

References

  • Hamilton, W. L. (2020). Graph Representation Learning. Synthesis Lectures on Artificial Intelligence and Machine Learning.
  • Bondy, J. A., & Murty, U. S. R. (2008). Graph Theory. Springer.

You May Also Enjoy

Modern Activation Functions: GELU, SiLU, Mish, and Smooth Gating

11 minute read

Published:

Once ReLU became the default, researchers started asking a better question: can we keep the easy optimization while making the activation smoother, softer, and more expressive? This chapter covers the modern answers.

Activation Functions in Neural Networks: Why Non-Linearity Matters

11 minute read

Published:

Activation functions are the reason neural networks can model curved decision boundaries instead of collapsing into one giant linear map. This chapter builds the intuition first, then walks through the classical functions that shaped deep learning.

FoPE: Fourier Position Embedding for Length Generalization

6 minute read

Published:

FoPE rethinks long-context positional encoding from a frequency-domain perspective. Instead of only stretching RoPE heuristically, it explicitly improves attention’s periodic extension so Transformers generalize more gracefully to longer sequences.