Graph Neural Networks and Network Science

Friendships on Facebook, roads between Lahore and Islamabad, atoms in a drug molecule and links between web pages all share one structure: they are networks. Network science gives us the mathematics to describe these connections, and graph neural networks (GNNs) let machine learning models learn directly from them. This article builds both ideas from the ground up, with calculations you can check by hand.

Graphs: The Basic Language

A graph \( G = (V, E) \) is a set of nodes (vertices) \( V \) and a set of edges \( E \) connecting pairs of nodes. Graphs can be:

• Undirected (friendship) or directed (one web page linking to another).
• Weighted (road length in km) or unweighted.
• Attributed, where each node carries a feature vector, such as a user's age and interests or an atom's type and charge.

The most useful representation for computation is the adjacency matrix \( A \), where \( A_{ij} = 1 \) if nodes \( i \) and \( j \) are connected and 0 otherwise. For an undirected graph, \( A \) is symmetric.

Our Running Example

Consider four people with edges 1–2, 1–3, 2–3 and 3–4. People 1, 2 and 3 form a triangle, and person 4 only knows person 3. The adjacency matrix is

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

Measuring Networks

Network science asks questions such as: Who is most connected? Do friends of friends know each other? How far apart are typical nodes?

• Degree \( k_i \): the number of neighbours of node \( i \), equal to the sum of row \( i \) of \( A \).
• Clustering coefficient \( C_i \): the fraction of pairs of \( i \)'s neighbours that are themselves connected.
• Path length: the fewest edges needed to travel between two nodes.
• Centrality: measures such as betweenness and PageRank that rank how important a node is.

The local clustering coefficient for a node with degree \( k_i \) and \( T_i \) edges among its neighbours is

$$ C_i = \frac{T_i}{\binom{k_i}{2}} = \frac{2T_i}{k_i(k_i - 1)}. $$

Worked Example 1: Degrees and Clustering

Step 1: Degrees. Summing each row of \( A \): \( k_1 = 2 \), \( k_2 = 2 \), \( k_3 = 3 \), \( k_4 = 1 \). The total is 8, which is twice the number of edges (4), as the handshake lemma requires.

Step 2: Clustering of node 1. Its neighbours are 2 and 3. There is \( \binom{2}{2} = 1 \) possible pair, and the edge 2–3 exists, so \( T_1 = 1 \) and \( C_1 = 1/1 = 1 \).

Step 3: Clustering of node 3. Its neighbours are 1, 2 and 4. There are \( \binom{3}{2} = 3 \) possible pairs: (1, 2), (1, 4) and (2, 4). Only 1–2 is an edge, so \( T_3 = 1 \) and

$$ C_3 = \frac{1}{3} \approx 0.333. $$

Step 4: Node 4. With only one neighbour, there are no pairs, so \( C_4 \) is undefined (conventionally set to 0).

Interpretation: node 3 has the highest degree and acts as a bridge to node 4, but its neighbourhood is less tightly knit. Real social networks typically show high clustering together with short average path lengths, the famous small-world property described by Watts and Strogatz in 1998.

From Network Science to Graph Neural Networks

Classical machine learning expects inputs of fixed size arranged in a fixed order, such as a row in a spreadsheet. Graphs break both rules: they vary in size, and their nodes have no natural order. A GNN solves this with message passing: each node updates its representation by aggregating information from its neighbours.

A general message-passing layer can be written as

$$ \mathbf{h}_i^{(\ell+1)} = \sigma\!\left( W^{(\ell)} \cdot \text{AGG}\left\{ \mathbf{h}_j^{(\ell)} : j \in \mathcal{N}(i) \cup \{i\} \right\} + \mathbf{b}^{(\ell)} \right), $$

where \( \mathcal{N}(i) \) is the set of neighbours, AGG is a permutation-invariant function such as sum, mean or max, \( W \) and \( \mathbf{b} \) are learned parameters, and \( \sigma \) is a non-linearity such as ReLU, \( \sigma(z) = \max(0, z) \). Because sum, mean and max ignore order, relabelling the nodes does not change the output, an essential mathematical property called permutation equivariance.

Worked Example 2: One Layer of Mean-Aggregation Message Passing

Give each node in our graph a single scalar feature: \( h_1 = 1 \), \( h_2 = 2 \), \( h_3 = 3 \), \( h_4 = 4 \). Use mean aggregation over each node and its neighbours, with weight \( w = 2 \), bias \( b = -1 \) and ReLU.

Step 1: Collect neighbourhoods (including self).

• Node 1: \( \{1, 2, 3\} \)
• Node 2: \( \{1, 2, 3\} \)
• Node 3: \( \{1, 2, 3, 4\} \)
• Node 4: \( \{3, 4\} \)

Step 2: Compute means.

• Node 1: \( (1 + 2 + 3)/3 = 2 \)
• Node 2: \( (1 + 2 + 3)/3 = 2 \)
• Node 3: \( (1 + 2 + 3 + 4)/4 = 2.5 \)
• Node 4: \( (3 + 4)/2 = 3.5 \)

Step 3: Apply \( h' = \text{ReLU}(2m - 1) \).

• Node 1: \( 2(2) - 1 = 3 \)
• Node 2: \( 2(2) - 1 = 3 \)
• Node 3: \( 2(2.5) - 1 = 4 \)
• Node 4: \( 2(3.5) - 1 = 6 \)

All values are positive, so ReLU leaves them unchanged. The new features are \( (3, 3, 4, 6) \).

Interpretation: nodes 1 and 2 now have identical representations because they have identical neighbourhoods; structurally, they are interchangeable. After \( L \) layers, each node's representation depends on all nodes within \( L \) hops, so stacking layers widens each node's view of the network.

The Graph Convolutional Network

The widely used GCN of Kipf and Welling (2017) writes one layer in matrix form:

$$ H^{(\ell+1)} = \sigma\!\left( \tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2} H^{(\ell)} W^{(\ell)} \right), $$

where \( \tilde{A} = A + I \) adds self-loops and \( \tilde{D} \) is the diagonal degree matrix of \( \tilde{A} \). The symmetric normalisation stops high-degree nodes from producing huge values. Our mean-aggregation example corresponds to the simpler row normalisation \( \tilde{D}^{-1}\tilde{A} \).

Where GNNs Are Used

• Drug discovery: predicting molecular properties, with atoms as nodes and bonds as edges.
• Recommendation systems: users and products form a bipartite graph.
• Fraud detection: suspicious accounts cluster together in transaction networks.
• Traffic forecasting: road sensors form a graph, and GNNs predict congestion.
• Physics and weather: mesh-based GNNs simulate fluids and forecast weather.

Research Frontiers

Open problems include over-smoothing (after many layers, node features become nearly identical), expressive power (standard message-passing GNNs are at most as powerful as the Weisfeiler–Leman graph isomorphism test), scaling to graphs with billions of edges, and combining GNNs with transformers.

Did You Know?

• Graph theory began in 1736, when Leonhard Euler proved that no walk could cross each of the seven bridges of Königsberg exactly once.
• Google's original PageRank algorithm is an eigenvector calculation on the web's link graph.
• Many real networks have "hubs" with enormous degree, following approximately power-law degree distributions.

Key Takeaways

• Networks are encoded by adjacency matrices; degree and clustering summarise local structure.
• Message passing updates each node using an order-independent aggregate of its neighbours.
• GCNs normalise the adjacency matrix to keep feature scales stable.
• GNNs power applications in chemistry, finance, transport and recommendation, with open questions on depth and expressiveness.

Need help with graph theory, network analysis or a GNN thesis chapter? Amathify's experts and PhD scholars offer step-by-step solutions via WhatsApp or the Ask a Question form.