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 \times N\) matrix where \(A_{ij} = 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 \(G = (V, E)\) with \(N = \lvert V \rvert\) nodes. The adjacency matrix \(A \in \{0,1\}^{N\times N}\) is defined by

\[ A_{ij} = \begin{cases} 1 & \text{if } (i,j) \in E,\\[2pt] 0 & \text{otherwise.} \end{cases} \]
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_{ij} = A_{ji}\) always — that is, \(A = A^{\top}\). Directed graphs have asymmetric adjacency matrices.

Degree: The degree \(d_i\) of node \(i\) is the number of edges incident to it. It equals the sum of row \(i\) of \(A\):

\[ d_i = \sum_{j=1}^{N} A_{ij} = \lvert \mathcal{N}(i) \rvert, \]

where \(\mathcal{N}(i)\) denotes the neighbourhood of node \(i\). The degree matrix \(D = \mathrm{diag}(d_1,\ldots,d_N)\) carries these degrees on its diagonal and zeros elsewhere.

Sparsity: Real-world graphs are sparse — most node pairs have no edge. A social network with \(10^6\) users typically has on the order of \(10^7\) edges, not the \(10^{12}\) entries of the dense matrix. Sparse representations (edge lists, COO format) are crucial for efficiency.

Powers of \(A\): the entry \((A^2)_{ij}\) counts the number of walks of length 2 from \(i\) to \(j\), and more generally \((A^k)_{ij}\) counts walks of length \(k\). (A walk may repeat nodes and edges; a path may not, and there is no simple matrix formula for counting paths.) This is the mathematical basis for why a \(k\)-layer GNN captures the \(k\)-hop neighbourhood: \((A^k)_{ij} > 0\) exactly when \(j\) is reachable from \(i\) in \(k\) steps.

Weighted Graphs

In a weighted graph, \(A_{ij} = w_{ij}\) — the weight of the edge between \(i\) and \(j\), and \(0\) if there is no edge. For molecules this could be bond strength; for road networks, road capacity; for social networks, interaction frequency. The degree generalises to the weighted degree \(d_i = \sum_j w_{ij}\).

Self-Loops

Some GNN formulations add self-loops by modifying the adjacency matrix:

\[ \tilde{A} = A + I, \]

where \(I\) is the \(N \times N\) identity matrix. This ensures each node “sees itself” during aggregation — without it, a node’s own features would be dropped from the sum. The corresponding degree matrix is \(\tilde{D} = D + I\).

This is exactly what GCN does, which then symmetrically normalises to form the propagation matrix \(\hat{A} = \tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}\) (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 \in \mathbb{R}^{N \times d}\) (row \(v\) holds node \(v\)’s feature vector \(h_v\)) performs one round of neighbourhood aggregation:

\[ H_{\text{new}} = A H, \qquad \text{so} \qquad (H_{\text{new}})_v = \sum_{u \in \mathcal{N}(v)} h_u . \]

Row \(v\) of \(AH\) is the sum of the feature vectors of all neighbours of node \(v\). This is precisely message passing: aggregate all neighbour features.

Normalising by degree gives the mean of neighbour features — the basis for many GNN designs:

\[ D^{-1} A H, \qquad \text{row } v = \frac{1}{d_v}\sum_{u \in \mathcal{N}(v)} h_u . \]

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 \(\tilde{A} = 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_{ij} = 1\) if \((i,j)\) is an edge.
  • For undirected graphs \(A\) is symmetric, \(A = A^{\top}\). The degree matrix \(D = \mathrm{diag}(d_1,\ldots,d_N)\) has the degrees on its diagonal.
  • Matrix multiplication \(AH\) aggregates neighbour features — the mathematical core of GNNs — and \(D^{-1}AH\) averages them.
  • \((A^k)_{ij}\) counts walks (not paths) of length \(k\) from \(i\) to \(j\).
  • Adding the identity, \(\tilde{A} = 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

The Standard Library Modules Worth Knowing Before You pip install

8 minute read

Published:

Python ships with a counter, a queue, a memoiser, a CLI parser, a test framework’s smaller cousin, and a JSON-safe date library already installed — most of what people reach for a package to solve is one import away.

Files and Context Managers: Why with Is Not Optional

9 minute read

Published:

A file object that falls out of scope without with does get closed eventually — but ‘eventually’ means whenever the garbage collector gets around to it, which is not a promise any program handling more than a handful of files can live with.

Errors and Exceptions: EAFP, the Hierarchy, and Reading a Traceback

9 minute read

Published:

Exceptions in Python are not exceptional. They are a normal control-flow mechanism that the language leans on so heavily that the idiomatic style is to try the operation and handle the failure, rather than check first — which is faster, shorter, and free of race conditions.