Graph Neural Networks and Structured Data

Introduction and Context

Many important machine-learning problems involve entities that are related to one another. Users interact with products, accounts transfer money, proteins bind to other proteins, documents cite documents, and organizations share directors. Representing each entity independently often discards the relational structure that determines the phenomenon of interest. Graph neural networks (GNNs) address this limitation by learning representations that combine information from a node with information propagated through its graph neighborhood.

A graph is written as G = (V, E), where V is a set of nodes and E is a set of edges. Nodes may represent users, molecules, transactions, webpages, devices, or concepts. Edges may represent friendship, purchase, chemical bonding, money transfer, citation, or semantic relation. A graph can be homogeneous, with one node and edge type, or heterogeneous, with multiple node and relation types. It may be directed or undirected, weighted or unweighted, static or temporal.

GNNs are particularly valuable when the prediction depends on both attributes and structure. Typical tasks include node classification, link prediction, graph classification, recommendation, fraud detection, knowledge-graph completion, molecular property prediction, and community or anomaly analysis.

Learning Objectives

By the end of this chapter, the reader should be able to:

1. Model structured data as homogeneous, heterogeneous, directed, weighted, and temporal graphs.
2. Explain the message-passing framework underlying modern GNNs.
3. Derive and interpret graph convolutional and graph-attention layers.
4. Distinguish node-level, edge-level, and graph-level prediction tasks.
5. Design GNN pipelines for recommendation, fraud detection, knowledge graphs, molecular analysis, and network analytics.
6. Evaluate computational, statistical, ethical, and deployment limitations of graph learning.

1. Graph Representations and Their Semantics

For a graph with n nodes, an adjacency matrix A ∈ ℝⁿˣⁿ records connectivity. In an unweighted undirected graph, Aᵢⱼ = 1 when an edge connects nodes i and j, and Aᵢⱼ = 0 otherwise. For a weighted graph, Aᵢⱼ may be a non-negative interaction strength. In a directed graph, Aᵢⱼ and Aⱼᵢ can differ. Node attributes are represented by X ∈ ℝⁿˣᵈ, where row xᵢ is the d-dimensional feature vector of node i.

The degree of node i is the number of incident edges in an unweighted graph:

For a weighted graph, the same expression gives weighted degree, sometimes called strength. The degree matrix D is diagonal, with Dᵢᵢ = dᵢ. These quantities are important because aggregation should account for the different numbers of neighbors. Without normalization, a high-degree node can produce an embedding whose scale is determined mainly by degree.

A graph may also contain edge features eᵢⱼ, such as transaction amount, bond type, timestamp, or distance. In a heterogeneous graph, node type and relation type must be retained. For example, a knowledge graph may contain person, organization, and location nodes, together with works-for, located-in, and founded-by relations. Collapsing all relations into one undifferentiated edge can destroy important semantics.

Graph learning tasks

A central distinction is between transductive and inductive learning. In transductive learning, the graph and its nodes are largely known during training, although some labels are hidden. In inductive learning, the model must generalize to new nodes or graphs. A recommender serving newly registered users requires inductive capability; a fixed citation-network benchmark may be transductive.

Figure: A message-passing layer combines neighbor information to update a target-node representation.

2. The Message-Passing Framework

Most spatial GNNs can be expressed through a message-passing layer. Let hᵢˡ be the representation of node i at layer l, with hᵢ⁰ = xᵢ. A general layer is:

Here, 𝒩(i) is the neighborhood of i, eᵢⱼ is an optional edge feature, and AGGREGATE must usually be permutation invariant: sum, mean, maximum, or a learned attention-weighted sum. Permutation invariance is necessary because the ordering of neighbors has no intrinsic meaning.

A simple message-passing layer is:

Wₗ and Uₗ are trainable matrices, bₗ is a bias vector, and σ is an activation function such as ReLU. The first term preserves the node’s own information; the second incorporates its neighborhood. Self-loops are often added explicitly so that the node is included in aggregation.

After L layers, node i can receive information from nodes at graph distance up to L, assuming the implementation propagates one hop per layer. This is both a strength and a limitation: shallow networks have limited receptive fields, whereas very deep networks may suffer from oversmoothing, in which node representations become too similar.

Permutation equivariance and invariance

A node-level GNN should be permutation equivariant. If node indices are rearranged, the output representations should be rearranged in the same way, not changed semantically. A graph-level model should additionally use a permutation-invariant readout, such as:

where READOUT may be sum, mean, maximum, or a learned set function. Sum pooling preserves information about graph size more directly than mean pooling, while mean pooling reduces sensitivity to the number of nodes. The choice must reflect the application.

3. Graph Convolutional Networks

The graph convolutional network (GCN) uses a normalized adjacency operator. With self-loops, define à = A + I and D̃ᵢᵢ = ∑ⱼ Ãᵢⱼ. The standard layer is:

Hˡ contains all node representations at layer l, Wˡ is trainable, and I is the identity matrix. The symmetric normalization D̃⁻¹ᐟ²ÃD̃⁻¹ᐟ² prevents uncontrolled scale changes and treats source and target degrees symmetrically in an undirected graph.

For a node i, the expression is equivalent to a weighted average of transformed neighboring representations, including itself. The formula is most directly applicable to finite graphs represented by a sparse adjacency matrix and is commonly used for undirected or symmetrized relational structure. Directed graphs require a deliberate choice: preserve direction with separate operators, reverse edges, or use a directed architecture rather than silently symmetrizing.

Worked example: one GCN aggregation

Consider three nodes in a chain 1–2–3, with scalar initial features x₁ = 2, x₂ = 1, x₃ = 3. Add self-loops. The augmented adjacency is:

The augmented degrees are 2, 3, and 2. If W = 1 and σ is the identity, the updated value for node 2 is:

The two endpoint contributions use the symmetric normalization factor 1/√6, while node 2’s self-contribution uses 1/3. This is not an ordinary arithmetic mean; it is degree-normalized message aggregation.

4. Graph Attention Networks

GCNs use fixed normalization weights determined by graph structure. Graph attention networks (GATs) learn the relative importance of neighbors. A common single-head formulation first transforms node states:

An unnormalized attention score is computed for each edge:

where W is a trainable linear transformation, a is a trainable vector, ∥ denotes concatenation, and LeakyReLU is a piecewise-linear activation. Scores are normalized over the neighborhood using softmax:

The update is:

For multi-head attention, K attention heads can be concatenated in intermediate layers or averaged in an output layer. Attention improves adaptivity, but its coefficients should not automatically be interpreted as causal explanations. They indicate learned weighting within a model, not proof that a feature or neighbor caused the prediction.

Attention is useful when not all relationships are equally informative, such as distinguishing a trusted transaction contact from a suspicious high-risk neighbor. It can, however, add computational cost and may be unstable when neighborhoods are extremely large.

5. Heterogeneous Graphs, Knowledge Graphs, and Relational Models

A relation-aware model distinguishes edge types. A relational GCN can be written as:

ℛ is the set of relation types, 𝒩ᵢʳ is the neighbors of i under relation r, Wᵣˡ is relation-specific, and cᵢ,ᵣ is a normalization constant, often related to the number of neighbors of relation r. Relation-specific parameters can be expensive when there are many relation types, motivating basis or block decompositions and parameter sharing.

Knowledge graphs commonly represent facts as triples (s, r, o): subject, relation, and object. Link prediction estimates whether a missing triple is plausible. A bilinear score such as DistMult is:

where eₛ and eₒ are entity embeddings and wᵣ is a relation embedding. DistMult is computationally simple but symmetric in subject and object, so it cannot represent asymmetric relations well. Translational models such as TransE instead score:

where p is commonly 1 or 2. The negative distance is higher for more plausible triples. These models require careful negative sampling and evaluation protocols because random negatives may be too easy and may accidentally include true but unobserved facts.

6. Training Objectives and Evaluation

For a C-class node-classification problem, the cross-entropy loss over labeled nodes 𝒱ₗ is:

where yᵢ꜀ is 1 when node i belongs to class c and pᵢ꜀ is the predicted probability. Class weighting or focal loss may be appropriate for severe imbalance, but weights must be selected without leaking test information.

For link prediction, positive and negative edges are often trained with binary cross-entropy. Evaluation may use ROC-AUC, average precision, Hits@K, mean reciprocal rank, or recall@K. Accuracy alone is often misleading in fraud and recommendation because the positive class is rare and the operational objective is usually ranking or resource allocation.

Graph data creates special leakage risks. A random edge split can place structurally related information from the future or test period into training. Temporal tasks should use chronological splitting. In recommendation, interactions after the prediction timestamp must not be used to construct historical features. In fraud, labels may become available only after investigation; this delay must be reflected in validation.

7. Applications

Recommendation

A user–item graph connects users to items through clicks, ratings, purchases, or views. Collaborative filtering can be formulated as link prediction: estimate a score for an unobserved user–item edge. GNNs can incorporate side information such as item category, price, textual embedding, and user context. Bipartite structure should be preserved, and popularity bias should be measured explicitly. Candidate generation may use a lightweight embedding model, followed by a richer ranking model.

Fraud detection

Fraud is often relational. A suspicious account may share a device, address, payment instrument, or beneficiary with other suspicious accounts. A heterogeneous graph can represent these different entities and relations. Node, edge, or subgraph prediction can be used, depending on whether the target is an account, transaction, or coordinated ring. Temporal modeling is essential because using later transactions to classify an earlier transaction produces leakage. Anomaly scores should support human investigation rather than automatically determine adverse action without safeguards.

Molecular analysis

In a molecular graph, atoms are nodes and chemical bonds are edges. Node features can include atomic number, valence, aromaticity, and formal charge; edge features can encode bond type and stereochemistry. Message passing produces a molecular embedding for property prediction. Physically meaningful models should respect symmetries: translating or rotating a molecule in three-dimensional space should not change scalar properties. Three-dimensional geometric GNNs therefore use distances, angles, or equivariant representations rather than treating coordinates as arbitrary features.

Network analytics

In communication, transportation, power, and social networks, GNNs can support traffic forecasting, fault detection, influence estimation, and dynamic community analysis. Domain constraints matter. A power-grid model, for example, should not merely correlate nodes; it should incorporate topology and, where appropriate, physical equations. A high predictive score does not establish that a discovered relation is causal.

8. Illustrative Case: Graph-Based Payment Fraud Detection

Background

The following is an illustrative case, not a report of a specific company. A digital-payment provider processes millions of transfers daily. Fraudulent transactions are rare, labels arrive after manual review, and fraud rings reuse devices, bank accounts, telephone numbers, and merchant identities.

Problem

A transaction-only classifier performs well on isolated features such as amount, country, and time, but misses coordinated rings. The provider needs a model that ranks transactions for investigation while controlling false positives for legitimate customers.

Analysis

The data team constructs a heterogeneous temporal graph. Transaction nodes connect payer and payee accounts; account nodes connect to devices, cards, telephone numbers, and addresses. Edge attributes include amount, currency, channel, and event time. The graph used for a prediction at time t contains only information available at or before t.

A relation-aware message-passing model produces account and transaction embeddings. For a transaction edge, the model combines the embeddings of the payer, payee, shared infrastructure, and transaction attributes. A prediction head estimates fraud probability or an investigation-priority score. Training uses historical labels with a time-based split rather than a random split.

Approach and solution

The system uses a two-stage design. First, a scalable model generates candidate risk scores for all transactions. Second, a calibrated ranking layer incorporates investigator capacity, case severity, and policy constraints. Evaluation includes precision at the daily review budget, recall of confirmed fraud rings, false-positive rate by customer segment, calibration, and performance drift over time.

A graph explanation interface displays influential relation types and nearby entities, but it labels these as model evidence rather than causal proof. Investigators can provide feedback, while access to sensitive attributes is restricted and audited.

Outcome

In a realistic deployment, success would not be defined solely by an offline AUC increase. It would require improved precision within the review budget, stable performance under temporal shift, reduced investigation time, and no unacceptable disparity in false-positive rates. The model should be monitored for graph-construction errors, adversarial adaptation, and changes in payment behavior.

Learning points

1. The graph schema is a substantive modeling decision, not merely a software detail.
2. Time-aware data construction is necessary to prevent leakage.
3. Heterogeneous relations can expose coordinated behavior invisible to tabular models.
4. Operational metrics and governance are as important as predictive metrics.
5. Explanations must distinguish correlation, model attention, and causation.

9. Scalability and Systems Design

Full-batch training can be expensive because a layer may touch a large fraction of the graph. Neighbor sampling limits computation by sampling a fixed number of neighbors per layer, but introduces sampling variance and can miss important rare neighbors. Cluster-based methods partition the graph and train on subgraphs. For high-degree nodes, importance sampling, cached representations, or specialized aggregators may be necessary.

Sparse matrix operations are central to GNN efficiency. If a graph has |E| edges and hidden dimension d, a basic message-passing layer is often approximately O(|E|d) for sparse aggregation, plus the cost of linear transformations. Actual performance depends on memory movement, feature dimension, number of layers, sampling strategy, and hardware. Large-scale systems commonly separate offline embedding generation from online scoring, or use approximate nearest-neighbor search for retrieval.

Deep architectures require residual connections, normalization, jumping-knowledge methods, or carefully designed propagation to mitigate oversmoothing and oversquashing. Oversquashing occurs when information from an exponentially growing receptive field is compressed into a fixed-size representation across narrow graph bottlenecks. Increasing depth does not necessarily solve this problem; graph rewiring, positional encodings, and architectural changes may help.

10. Limitations, Ethics, and Governance

Graph data is not neutral. A graph can encode sensitive relationships, reveal social associations, or amplify historical surveillance. In recommendation, optimizing engagement can reinforce popularity and reduce exposure for minority creators. In credit or fraud settings, relational features may act as proxies for protected characteristics. A person may be penalized because of another person’s behavior despite having no control over it.

Important controls include purpose limitation, data minimization, access control, retention limits, provenance tracking, and documented lawful basis for processing. Organizations should test subgroup performance, calibration, and error costs. Human review is particularly important when predictions affect access to financial services, employment, education, or essential services. Model cards and data documentation should describe graph construction, missingness, temporal coverage, intended use, and known failure modes.

Adversaries may manipulate graph structure through fake accounts, purchased interactions, malicious links, or strategically chosen features. Robustness testing should include edge injection, node injection, feature perturbation, and distribution shift. Privacy-preserving approaches such as aggregation, pseudonymization, secure computation, and differential privacy may reduce risk, although each can reduce utility and must be evaluated quantitatively.

11. Contemporary Directions and Best Practices

Current research explores temporal GNNs, graph transformers, self-supervised pretraining, neural operators for physical systems, multimodal knowledge graphs, and foundation models that combine text with graph structure. Graph transformers can model long-range interactions, but naïve global attention is expensive; sparse or structural attention is often required. Self-supervised objectives include masked-node prediction, contrastive learning, and link reconstruction, but pretext-task success does not guarantee downstream fairness or robustness.

A disciplined project workflow is:

1. Define the prediction target, decision time, and unit of analysis.
2. Specify node, edge, feature, and relation semantics before selecting an architecture.
3. Establish a non-graph baseline, such as a calibrated linear or tree-based model.
4. Use temporal, entity-aware, or inductive splits that match deployment.
5. Select aggregation and sampling strategies according to graph scale and heterogeneity.
6. Report ranking, calibration, subgroup, and operational metrics—not only accuracy.
7. Test ablations to determine whether gains come from structure, features, or leakage.
8. Monitor drift, graph-quality failures, adversarial behavior, and feedback loops.
9. Maintain reproducible schemas, feature lineage, random seeds, and model documentation.

Chapter Summary

Graph neural networks learn from entities and their relationships by repeatedly transmitting, aggregating, and transforming neighborhood information. The general message-passing framework supports node, edge, and graph-level tasks while respecting the fact that graph neighborhoods have no natural ordering. GCNs use normalized structural propagation; GATs learn neighbor-specific attention weights; relational and heterogeneous models preserve relation semantics. Knowledge-graph methods score missing triples, while molecular and physical applications require attention to domain symmetries.

Effective graph learning depends on more than architecture. Graph schema, temporal boundaries, negative sampling, train–test splitting, scalability, calibration, fairness, privacy, and adversarial robustness determine whether a model is valid and deployable. Recommendation, fraud detection, molecular analysis, knowledge graphs, and network analytics illustrate the breadth of applications, but each requires task-specific evaluation and governance.

Key Terms

Graph: A structure consisting of nodes and edges.

Node: An entity represented in a graph.

Edge: A relationship between two nodes.

Adjacency matrix: A matrix encoding graph connectivity or edge weights.

Degree matrix: A diagonal matrix containing node degrees.

Message passing: Iterative exchange and aggregation of neighborhood information.

Permutation equivariance: Outputs reorder consistently when node indices are permuted.

Permutation invariance: An output remains unchanged when an unordered set is reordered.

GCN: A graph convolutional network using normalized adjacency propagation.

GAT: A graph attention network that learns neighbor weights.

Self-loop: An edge from a node to itself.

Heterogeneous graph: A graph with multiple node or edge types.

Knowledge graph: A graph of typed factual relations, often represented as triples.

Link prediction: Estimating whether a relationship exists or should be ranked highly.

Oversmoothing: Loss of distinction among node representations in deep GNNs.

Oversquashing: Compression of excessive long-range information into limited representations.

Neighbor sampling: Selecting a subset of neighbors for scalable training.

Transductive learning: Learning on a largely fixed graph whose nodes are known.

Inductive learning: Generalizing to new nodes or graphs.

Graph readout: A permutation-invariant operation producing a graph-level representation.

Review Questions

Short Answer Questions

1. What are the principal components of a graph representation, and how can edge attributes enrich it?
2. Why must neighborhood aggregation generally be permutation invariant?
3. What problem is addressed by the normalization in a GCN layer?
4. Distinguish transductive from inductive graph learning.
5. Why can random train–test splitting cause leakage in temporal fraud detection?

Long Answer Questions

1. Explain the message-passing framework and compare sum, mean, maximum, and attention-based aggregation.
2. Derive the normalized GCN update and discuss the role of self-loops and the degree matrix.
3. Compare GCNs, GATs, and relational GNNs in terms of inductive bias, expressive behavior, and computational implications.
4. Design an end-to-end GNN pipeline for a heterogeneous recommendation system, including graph schema, objective, evaluation, and governance.
5. Discuss oversmoothing, oversquashing, neighbor sampling, and temporal leakage as barriers to reliable large-scale GNN deployment.

Analytical / Application Questions

1. A payment provider has account, device, address, and transaction entities. Propose a heterogeneous graph schema and explain which relations should be directional, weighted, or time-stamped.
2. Design an evaluation protocol for a molecular graph-regression model that must generalize to previously unseen chemical scaffolds. Justify the split and metrics.
3. A GAT assigns high attention to a neighbor in a high-stakes decision. Explain why this does not establish causation, and propose additional tests for explanation reliability and fairness.

Multiple Choice Questions with Answers

Question 1

Which property is required of a standard neighborhood aggregation function because graph neighbors have no canonical order?

A. Permutation invariance

B. Temporal monotonicity

C. Orthogonal sparsity

D. Class balance

Correct Answer: A. Permutation invariance

Question 2

In the normalized GCN update, what does D̃ represent after self-loops are added?

A. The diagonal matrix of augmented node degrees

B. The matrix of node labels

C. The learned attention-score matrix

D. The matrix of edge timestamps

Correct Answer: A. The diagonal matrix of augmented node degrees

Question 3

What is the principal distinction between a GAT and a basic GCN?

A. A GAT learns neighbor-specific weighting coefficients

B. A GAT cannot use node features

C. A GAT operates only on complete graphs

D. A GAT always removes self-loops

Correct Answer: A. A GAT learns neighbor-specific weighting coefficients

Question 4

Which task predicts whether an unobserved user–item relationship should receive a high score?

A. Link prediction

B. Graph pooling

C. Node normalization

D. Edge deletion

Correct Answer: A. Link prediction

Question 5

Why is a chronological split especially important in fraud detection?

A. It prevents future information from entering historical predictions

B. It guarantees that every class has equal frequency

C. It eliminates the need for negative examples

D. It makes the graph undirected

Correct Answer: A. It prevents future information from entering historical predictions

Question 6

In a knowledge graph, a fact is commonly represented as which structure?

A. Subject–relation–object triple

B. Mean–variance–covariance tuple

C. Input–activation–gradient tuple

D. Source–code–compiler tuple

Correct Answer: A. Subject–relation–object triple

Question 7

What does oversmoothing refer to in deep GNNs?

A. Node representations becoming increasingly indistinguishable

B. Edge weights becoming physically dimensioned

C. Training labels becoming perfectly balanced

D. Attention coefficients becoming causal explanations

Correct Answer: A. Node representations becoming increasingly indistinguishable

Question 8

Which graph representation is most appropriate for modeling atoms connected by chemical bonds?

A. Atoms as nodes and bonds as edges

B. Atoms as edges and bonds as graph labels only

C. Molecules as isolated scalar features with no structure

D. Bond types as training examples and atoms as test labels

Correct Answer: A. Atoms as nodes and bonds as edges

Question 9

For a graph with |E| edges and hidden dimension d, what is the commonly cited leading aggregation cost of a sparse message-passing layer?

A. Approximately O(|E|d)

B. Approximately O(1) regardless of graph size

C. Approximately O(d/|E|)

D. Approximately O(|E| + d)² in every implementation

Correct Answer: A. Approximately O(|E|d)

Question 10

Why should high attention weights not automatically be interpreted as causal explanations?

A. They are learned weighting coefficients, not interventions establishing causality

B. They are always random by definition

C. They are unrelated to the model computation

D. They exist only during data preprocessing

Correct Answer: A. They are learned weighting coefficients, not interventions establishing causality