Graph Neural Networks for Structured Data

Unlocking Insights from Relational Data with Deep Learning on Graphs

Authored by: Loveleen Narang

Date: June 1, 2024

Introduction: Beyond Grids and Sequences

Traditional deep learning models, like Convolutional Neural Networks (CNNs) and Recurrent Neural Networks (RNNs), excel at processing data with regular structures, such as images (grids of pixels) and text/time series (sequences). However, much of the world's data is inherently relational and best represented as **graphs** – structures consisting of nodes (entities) connected by edges (relationships). Examples include social networks, molecular structures, citation networks, knowledge graphs, recommendation systems, and transportation networks.

Applying traditional deep learning directly to such graph-structured data is challenging due to irregular connectivity, variable neighborhood sizes, and the lack of inherent node ordering. Graph Neural Networks (GNNs) have emerged as a powerful class of deep learning models specifically designed to operate directly on graph data. They leverage the graph structure to learn representations (embeddings) of nodes, edges, or entire graphs, enabling tasks like node classification, link prediction, and graph classification.

Representing Graphs Mathematically

To process graphs with algorithms, we need mathematical representations:

• Graph Definition: A graph \( G \) is defined by a set of vertices (nodes) \( V \) and a set of edges \( E \subseteq V \times V \) connecting pairs of nodes. Formulas (1, 2, 3): \( G, V, E \).
• Adjacency Matrix (\( A \)): A square matrix \( A \in \mathbb{R}^{|V| \times |V|} \) where \( A_{ij} = 1 \) if there's an edge from node \( i \) to node \( j \), and \( A_{ij} = 0 \) otherwise (can be weighted for weighted graphs). Formula (4): \( A \).
• Node Features (\( X \)): A matrix \( X \in \mathbb{R}^{|V| \times d} \) where row \( i \) (\( x_i \)) is the \( d \)-dimensional feature vector for node \( i \). Formula (5): \( X \). Formula (6): \( x_i \).
• Degree Matrix (\( D \)): A diagonal matrix where \( D_{ii} \) is the degree (number of connections) of node \( i \). Formula (7): \( D_{ii} = \sum_j A_{ij} \).
• Graph Laplacian (\( L \)): Often used in spectral graph theory and some GNNs. \( L = D - A \) (Formula 8). The normalized Laplacian is also common: \( L_{sym} = I - D^{-1/2} A D^{-1/2} \) (Formula 9). Formula (10): Identity matrix \( I \).
• Edge Features (\( E_{feat} \)): Optionally, a matrix containing features for each edge. Formula (11): \( E_{feat} \).

The Core Idea: Message Passing & Aggregation

Most GNNs operate based on a **neighborhood aggregation** or **message passing** scheme. The intuition is that a node's representation should be influenced by the features of its neighbors. GNNs iteratively update the feature vector (embedding) of each node by aggregating representations from its local neighborhood.

A typical GNN layer (\(k\)) updates the hidden state \( h_v^{(k)} \) for node \( v \) based on its previous state \( h_v^{(k-1)} \) and the states of its neighbors \( \{ h_u^{(k-1)} : u \in \mathcal{N}(v) \} \). This can be conceptually broken down into:

1. Message Computation (Optional): For each neighbor \( u \in \mathcal{N}(v) \), a message \( m_{v \leftarrow u}^{(k)} \) is computed based on \( h_u^{(k-1)} \), \( h_v^{(k-1)} \), and potentially edge features \( e_{uv} \). Formula (12): \( m_{v \leftarrow u}^{(k)} = \text{MESSAGE}^{(k)}(h_u^{(k-1)}, h_v^{(k-1)}, e_{uv}) \).
2. Aggregation: Messages from neighbors (or simply neighbor states \( h_u^{(k-1)} \)) are aggregated into a single vector \( M_v^{(k)} \) using a permutation-invariant function (like sum, mean, max). Formula (13): \( M_v^{(k)} = \text{AGGREGATE}^{(k)}(\{ m_{v \leftarrow u}^{(k)} : u \in \mathcal{N}(v) \}) \).
3. Update: The aggregated information \( M_v^{(k)} \) is combined with the node's own previous state \( h_v^{(k-1)} \) to compute the new state \( h_v^{(k)} \), often using a neural network layer (e.g., MLP) and activation function. Formula (14): \( h_v^{(k)} = \text{UPDATE}^{(k)}(h_v^{(k-1)}, M_v^{(k)}) \).

Stacking multiple such layers allows information to propagate across the graph over larger distances.

Key GNN Architectures

Different GNNs vary mainly in their specific AGGREGATE and UPDATE functions.

Graph Convolutional Networks (GCN)

GCNs simplify graph convolutions, often interpreted spatially as aggregating normalized feature representations from neighboring nodes. A popular layer formulation is:

Where:

• \( H^{(k)} \in \mathbb{R}^{|V| \times d_k} \) is the matrix of node embeddings at layer \( k \). Formula (15): \( H^{(k)} \).
• \( \hat{A} = A + I \) is the adjacency matrix with self-loops added. Formula (16): \( \hat{A} \).
• \( \hat{D} \) is the diagonal degree matrix of \( \hat{A} \). Formula (17): \( \hat{D}_{ii} = \sum_j \hat{A}_{ij} \).
• \( \hat{D}^{-1/2} \hat{A} \hat{D}^{-1/2} \) represents symmetric normalization of the adjacency matrix.
• \( W^{(k)} \in \mathbb{R}^{d_k \times d_{k+1}} \) is the layer-specific learnable weight matrix. Formula (18): \( W^{(k)} \).
• \( \sigma \) is a non-linear activation function (e.g., ReLU). Formula (19): \( \sigma \). Formula (20): \( \text{ReLU}(x) = \max(0,x) \).

This effectively computes a weighted average of the node's own features and its neighbors' features, followed by a linear transformation and activation.

GraphSAGE (Graph SAmple and aggreGatE)

Focuses on **inductive learning** (can generalize to unseen nodes) by sampling a fixed number of neighbors and learning aggregation functions.

• Sampling:** Instead of using all neighbors, sample a fixed-size neighborhood \( \mathcal{N}(v) \).
• Aggregation:** Learnable functions to aggregate neighbor features \( h_u^{(k-1)} \) into \( h_{\mathcal{N}(v)}^{(k)} \). Common aggregators include:
  • Mean Aggregator: Formula (21): \( h_{\mathcal{N}(v)}^{(k)} = \frac{1}{|\mathcal{N}(v)|} \sum_{u \in \mathcal{N}(v)} h_u^{(k-1)} \).
  • Pooling Aggregator (Max/Mean): Apply an MLP to neighbor features then max/mean pool. Formula (22): \( h_{\mathcal{N}(v)}^{(k)} = \max(\{ \sigma(W_{pool} h_u^{(k-1)} + b) : u \in \mathcal{N}(v) \}) \).
  • LSTM Aggregator: Apply LSTM to a random permutation of neighbor features.
• Update:** Concatenate the node's own previous state \( h_v^{(k-1)} \) with the aggregated neighbor vector \( h_{\mathcal{N}(v)}^{(k)} \), pass through a linear layer and activation. Formula (23): \( h_v^{(k)} = \sigma(W^{(k)} \cdot \text{CONCAT}(h_v^{(k-1)}, h_{\mathcal{N}(v)}^{(k)})) \). Formula (24): CONCAT.

GraphSAGE Aggregators (Mean/Pool)

Fig 8 & 9: Different ways GraphSAGE can aggregate neighbor information.

Graph Attention Networks (GAT)

GATs introduce attention mechanisms, allowing nodes to assign different importance weights to different neighbors during aggregation, rather than treating them equally (like GCN mean) or uniformly (like GraphSAGE mean).

• Attention Coefficients (\( \alpha_{ij} \)): Learned weights indicating the importance of node \( j \)'s features to node \( i \). Calculated based on the features of node \( i \) and node \( j \) (often after a linear transformation \( W \)), typically using a shared attention mechanism \( a \). Formula (25): \( e_{ij} = a(W h_i, W h_j) \). These raw scores \( e_{ij} \) are normalized across neighbors using softmax. Formula (26): \( \alpha_{ij} = \text{softmax}_j(e_{ij}) = \frac{\exp(\text{LeakyReLU}(a^T[Wh_i || Wh_j]))}{\sum_{k \in \mathcal{N}_i} \exp(\text{LeakyReLU}(a^T[Wh_i || Wh_k]))} \). Formula (27): LeakyReLU.
• Aggregation/Update:** The updated node representation is a weighted sum (or other combination) of linearly transformed neighbor features, weighted by the attention coefficients. Formula (28): \( h_i' = \sigma(\sum_{j \in \mathcal{N}_i} \alpha_{ij} W h_j) \).
• Multi-Head Attention:** Similar to Transformers, multiple independent attention mechanisms ("heads") are computed in parallel and their results concatenated or averaged to stabilize learning. Formula (29): \( h_i' = \text{AGG}(\|_{k=1}^K \sigma(\sum_{j \in \mathcal{N}_i} \alpha_{ij}^k W^k h_j)) \). Formula (30): Concat \( || \).

GAT Attention Mechanism

Fig 10: GAT uses attention coefficients (\(\alpha\)) to weigh contributions from neighbors differently.

Graph Isomorphism Network (GIN)

Designed to be maximally powerful among message-passing GNNs, approaching the discriminative power of the Weisfeiler-Lehman graph isomorphism test. Uses a Multilayer Perceptron (MLP) to update node features based on the sum of neighbor features, plus the node's own features potentially weighted by a learnable parameter \( \epsilon \).

• Update Rule: Formula (31): \( h_v^{(k)} = \text{MLP}^{(k)}((1 + \epsilon^{(k)}) h_v^{(k-1)} + \sum_{u \in \mathcal{N}(v)} h_u^{(k-1)}) \). Formula (32): Learnable \( \epsilon^{(k)} \).

GIN Layer Operation

Fig 11: GIN updates node 'v' using an MLP applied to a weighted sum of its own and neighbors' features.

Comparison of Common GNN Architectures

Architecture	Aggregation	Update Mechanism	Key Feature
GCN	Normalized Mean	Linear transformation + Activation	Simple, computationally efficient, effective for homophilous graphs
GraphSAGE	Mean/Max/LSTM Pool (Sampled Neighbors)	Concat self + aggregated neighbors -> Linear + Activation	Inductive capability, flexible aggregation
GAT	Weighted Sum (Attention)	Attention-weighted sum -> Linear + Activation	Learns neighbor importance, handles varying degrees
GIN	Sum (+ weighted self)	MLP applied to aggregated features	Theoretically powerful (matches WL test)

Common Tasks for GNNs

GNNs are versatile and applied to various graph-related tasks:

• Node Classification: Predict a label for each node in the graph (e.g., classifying users in a social network, protein functions). Typically uses the final node embeddings \( h_v^{(K)} \) as input to a classifier (e.g., softmax layer). Loss (e.g., Cross-Entropy): Formula (33): \( L = -\sum_{v \in V_{labeled}} y_v \log(\hat{y}_v) \).
• Graph Classification: Predict a label for the entire graph (e.g., classifying molecules as toxic/non-toxic). Requires a **Readout** or **Graph Pooling** layer to aggregate node embeddings into a single graph representation \( h_G \). Formula (34): \( h_G = \text{READOUT}(\{ h_v^{(K)} | v \in V \}) \). READOUT can be sum, mean, or max pooling, or more sophisticated methods.
• Link Prediction: Predict whether an edge exists (or should exist) between two nodes (e.g., recommending friends, predicting protein-protein interactions). Uses embeddings of pairs of nodes (\( h_u^{(K)}, h_v^{(K)} \)) to predict edge probability, e.g., via dot product or MLP. Formula (35): \( \text{score}(u, v) = \sigma(h_u^T h_v) \) or \( \text{MLP}(h_u, h_v) \).
• Graph Generation: Creating new graph structures (e.g., discovering new molecules). Often involves generative models like Graph Autoencoders or GANs adapted for graphs.

GNN Tasks Illustrated

Fig 12, 13, 14: Examples of Node Classification, Link Prediction, and Graph Classification tasks.

Training GNNs

Training GNNs typically involves standard deep learning practices:

• Defining a loss function appropriate for the task (e.g., cross-entropy for classification).
• Using an optimizer (e.g., Adam, SGD) to minimize the loss by adjusting model weights \( W^{(k)} \), \( \epsilon^{(k)} \), etc. Formula (36): Gradient Descent \( \theta \leftarrow \theta - \eta \nabla J \).
• For large graphs where full-batch training is infeasible, sampling techniques are used:
  • Neighbor Sampling (like GraphSAGE): Sample a fixed number of neighbors for each node at each layer.
  • Subgraph Sampling: Train the GNN on smaller sampled subgraphs.

Challenges and Future Directions

Despite their success, GNNs face several challenges:

• Oversmoothing: As GNN layers stack, node representations can become increasingly similar, losing discriminative power. This limits the effective depth of many GNNs.
• Scalability: Applying GNNs to massive graphs (billions of nodes/edges) requires sophisticated sampling or distributed training strategies due to memory and computation constraints.
• Dynamism: Real-world graphs often change over time (nodes/edges added/removed). Developing GNNs that efficiently handle dynamic graphs is an ongoing research area.
• Heterogeneity: Many real-world graphs have different types of nodes and edges (heterogeneous graphs). Standard GNNs often assume homogeneous graphs, requiring extensions like Relational GCNs (R-GCN) or Heterogeneous GATs (HAN).
• Explainability: Understanding why a GNN makes a certain prediction remains challenging, similar to other deep learning models.
• Handling Long-Range Dependencies: Message passing primarily captures local structure. Capturing dependencies between distant nodes efficiently is difficult (addressed partially by deeper models or graph transformers).

Future research focuses on deeper GNN architectures, better scalability, handling dynamic and heterogeneous graphs, combining GNNs with transformers, and improving interpretability.

Oversmoothing Illustration

Fig 15: After many GNN layers, node representations can become overly similar (oversmoothing).

Conclusion

Graph Neural Networks represent a significant advancement in machine learning, providing a powerful framework for learning from structured, relational data that permeates the real world. By effectively leveraging graph topology through message passing and neighborhood aggregation, GNN architectures like GCN, GraphSAGE, GAT, and GIN can learn rich node and graph representations for diverse tasks. While challenges such as oversmoothing, scalability, and dynamism persist, the rapid pace of research is continuously yielding more powerful and efficient GNN models. GNNs are unlocking new possibilities in fields ranging from drug discovery and social network analysis to recommendation systems and beyond, demonstrating the immense value of directly incorporating relational structure into deep learning.

Diagram Note: This article includes 15 illustrative SVG diagrams (Figs 1-15) as requested, covering core concepts and architectures. Due to the complexity and space constraints, these are simplified representations. Further detailed architectural diagrams can be found in the original research papers.

(Formula count check: Includes G=(V,E), V, E, Adj A, Degree D, Laplacian L, Norm Lap Lsym, Node Feats X, Feat x_i, Identity I, Edge Feats Efeat, Message m, Aggregate M, Update h_k, GCN Layer H(k+1), GCN A_hat, GCN D_hat, Activation sigma, Weight Wk, ReLU, SAGE Mean Agg, SAGE Pool Agg, SAGE Update, CONCAT, GAT Attention e_ij, GAT Attention mech a(), GAT Norm Attention alpha_ij, GAT Update h', LeakyReLU, GAT Multi-head ||, GIN Update, GIN Epsilon, Readout h_G, Node Loss L, Link Score. Total > 35).

About the Author, Architect & Developer

Loveleen Narang is an accomplished leader and visionary in Data Science, Machine Learning, and Artificial Intelligence. With over 20 years of expertise in designing and architecting innovative AI-driven solutions, he specializes in harnessing advanced technologies to address critical challenges across industries. His strategic approach not only solves complex problems but also drives operational efficiency, strengthens regulatory compliance, and delivers measurable value—particularly in government and public sector initiatives.

Renowned for his commitment to excellence, Loveleen’s work centers on developing robust, scalable, and secure systems that adhere to global standards and ethical frameworks. By integrating cross-functional collaboration with forward-thinking methodologies, he ensures solutions are both future-ready and aligned with organizational objectives. His contributions continue to shape industry best practices, solidifying his reputation as a catalyst for transformative, technology-led growth.