Chapter 11: Graph representation learning and graph neural networks

Introduction

The introduction explains why graph representation learning can replace hard-to-scale manual feature engineering with learned embeddings and introduces GNNs as a way to learn them.

• Manual feature engineering tradeoff: Explain why manual graph features are useful but difficult to scale to large knowledge graphs.
  Why it matters: This tradeoff motivates learning graph features automatically rather than designing every feature by hand.
• Learned graph embeddings: Explain how graph representation learning replaces hand-designed features with embeddings and what those embeddings provide.
  Why it matters: Embeddings let graph structure and attributes become usable inputs for downstream ML without specifying every feature manually.
• Neighbor-based GNN learning: Describe, at the introductory level, how GNNs learn graph representations and why that helps downstream tasks.
  Why it matters: Neighbor information is the basic intuition behind the GNN approach developed later in the chapter.

Key terms: manual feature engineering, interpretability, knowledge graphs, graph representation learning, embeddings, graph structure, node attributes, dense vector representations, graph neural networks, neighboring nodes

11.1 Embeddings in graph representation learning

This section traces three generations of graph representation learning, from simplifying graph structure to learning meaningful node representations and patterns automatically.

• Three generations of graph representation: Describe how graph representation learning progressed from traditional graph embeddings through Node2Vec to graph neural networks, and distinguish what each generation sought to capture.
  Why it matters: The progression clarifies how the graph representations discussed later differ in what they learn from a graph.

Key terms: graph representation learning, traditional graph embedding, dimensionality reduction, Node2Vec, graph neural networks

11.1.1 Understanding graph embeddings: From discrete to continuous

This section introduces graph embeddings and explains how graph structure, geometric space, preserved patterns, new-node requirements, and supervision shape embedding choices.

• Discrete graphs to vectors: Explain that a graph embedding turns a discrete structure of nodes and relationships into continuous vectors, making relationships easier to represent and calculate with.
  Why it matters: This is the basic purpose behind the embedding approaches discussed in the chapter.
• Irregular graph neighborhoods: Explain why graphs call for approaches different from those used directly on regularly structured image or text data.
  Why it matters: Graph-specific methods need to accommodate varying connections rather than assume a uniform layout.
• Euclidean and hyperbolic embeddings: Distinguish Euclidean from hyperbolic embedding space and explain when a graph’s hierarchy might make hyperbolic space useful.
  Why it matters: The chosen geometry affects which graph relationships an embedding preserves and how its distances are interpreted.
• Positional and structural patterns: Distinguish embeddings that preserve a node’s position in the broader network from embeddings that capture similar local connectivity patterns.
  Why it matters: The distinction helps clarify which aspect of graph structure an embedding is meant to retain.
• Transductive and inductive learning: Distinguish embeddings optimized for a fixed set of known nodes from learned mappings that can generate embeddings for unseen nodes.
  Why it matters: Whether new users, products, or other nodes will appear affects which learning approach is useful.
• Supervision in embedding learning: Distinguish discovering patterns from graph structure alone from using additional information to guide embedding learning toward a specific goal.
  Why it matters: The information available to guide learning changes the purpose of the resulting embeddings.

Key terms: graph embeddings, discrete graph structures, continuous vector representations, neighborhood structure, irregularity, Euclidean space, non-Euclidean space, hyperbolic space, hierarchical structure, positional embeddings

11.1.2 Real-world applications and examples

The section uses social, biological, and medical networks to show how embedding choices depend on a problem’s structure, available data, and goals.

• Embedding choices for network structure: Explain how the examples match embedding approaches to network structure: structural embeddings find similar roles or concepts, positional embeddings identify influencers and bridge-builders, and hyperbolic embeddings suit hierarchies.
  Why it matters: It connects the kind of graph pattern you care about to the embedding approach you choose.
• Learning choices for changing data: Explain why the examples call for inductive learning when new users or discoveries must be incorporated, and how labeled information can support supervised learning to improve accuracy.
  Why it matters: It shows that practical embedding choices also depend on changing data and the evidence available for training.

Key terms: structural embeddings, positional embeddings, hyperbolic embeddings, inductive learning, supervised learning, expert-labeled data

11.2 The encoder–decoder model

This section introduces the encoder–decoder model as a way to understand how graph embeddings represent graph structure and reconstruct meaningful properties.

• Encoder–decoder graph representation: Explain how the encoder–decoder model first converts discrete graph information into compact, continuous vector representations and then uses those representations to reconstruct meaningful graph properties.
  Why it matters: This model gives you a way to understand what graph embedding methods do.

Key terms: encoder–decoder model, graph embedding, discrete graph structure, continuous vector representations

11.2.1 The encoder: Converting graph structure to vectors

This section explains how an encoder turns graph structure and node features into node embeddings, and how encoding methods differ.

• Encoder inputs and outputs: Explain that an encoder converts graph structure and any additional node features into a dense vector embedding for each node. Describe the adjacency matrix as a representation of which nodes are connected.
  Why it matters: This is the basic input-to-output role of an encoder in graph representation learning.
• Encoding methods and priorities: Distinguish encoding methods by what they emphasize: global structure and relative node positions or local neighborhood patterns. Describe the range from assigning each node a vector with a lookup table to using a neural network that processes structure and features.
  Why it matters: It explains why different encoders can produce different representations of the same graph.

Key terms: encoder, graph structure, adjacency matrix, node features, embeddings, global structure, relative positions, local neighborhood patterns, lookup table, neural network

11.2.2 The decoder: Reconstructing graph properties

The section explains how a decoder tests what graph information embeddings preserve and provides a signal for improving the encoder.

• Graph property reconstruction: Explain that the decoder uses embeddings from the encoder to reconstruct properties of the original graph, with the target depending on what the method aims to preserve.
  Why it matters: What the decoder predicts determines which information the embeddings are encouraged to retain.
• Reconstruction as training signal: Explain how comparing decoder predictions with actual graph properties helps train the encoder.
  Why it matters: The decoder does more than inspect embeddings; its prediction error guides improvement of the encoder.

Key terms: decoder, embeddings, graph structure, node similarity, neighborhood overlap, node labels, reconstruction task, training signal, decoder’s predictions, actual graph properties

11.2.3 The power of the framework

The section presents the encoder–decoder framework as a common way to understand and compare graph representation learning methods.

• Common encode–decode pattern: Explain how the encoder–decoder framework unifies different approaches to graph representation learning.
  Why it matters: A shared pattern makes otherwise different graph learning methods easier to compare.
• Encoder complexity trade-offs: Describe the trade-off the section draws between simpler and more sophisticated encoders.
  Why it matters: This trade-off is one reason the shared framework is useful for comparing methods.

Key terms: encoder–decoder framework, GRL, encode–decode pattern, simpler encoders, neural network-based encoders, representations

11.2.4 Node2Vec: An example of an encoder–decoder framework

The section uses the karate club network to show how Node2Vec encodes graph structure as vectors and decodes those vectors to predict relationships.

• Random walks and node vectors: Explain how Node2Vec uses random walks through friendships to create a vector for each club member, with members who frequently appear near each other receiving similar vectors.
  Why it matters: It explains how paths through the graph become a numerical representation of each member.
• Vector-based relationship prediction: Explain what Node2Vec’s decoder predicts from two member vectors and how the section describes its softmax-based prediction.
  Why it matters: The prediction task gives the vectors a reason to preserve meaningful social relationships.
• Social patterns in embeddings: Describe how the resulting vectors reflect faction membership and members’ positions in the karate club network, and connect those patterns to the encoder–decoder framework.
  Why it matters: The club example shows that embeddings can reflect more than individual friendship links.

Key terms: Node2Vec, encoder, random walks, vector representations, decoder, softmax function, community structure, bridge members, faction membership, encoder–decoder framework

11.3 Shallow embeddings: A first approach to graph representation

Introduces shallow embeddings as the simplest implementation of the graph embedding encoder–decoder framework and notes that their limitations motivated more sophisticated approaches.

• Shallow embeddings and their tradeoff: Explain that shallow embeddings are a straightforward way to implement the encoder–decoder framework for graph embeddings, but that their simplicity brings important limitations.
  Why it matters: This positions shallow embeddings as a useful starting point without implying they solve every graph representation problem.

Key terms: shallow embeddings, graph embeddings, encoder–decoder framework

11.3.1 Understanding shallow embeddings

This subsection explains how shallow embeddings assign each node a learned vector through a lookup table and use graph-property reconstruction to train those vectors.

• Shallow encoder lookup: Explain how a shallow encoder represents a node by returning its dedicated vector from an embedding matrix, without further input transformation.
  Why it matters: The lookup operation distinguishes this approach from encoders that process node inputs.
• Reconstruction guided vector training: Describe how the decoder’s attempt to reconstruct graph properties helps adjust shallow embedding vectors, using the karate club example to illustrate the resulting similarities.
  Why it matters: Reconstruction explains how separately stored node vectors can come to reflect relationships in the graph.

Key terms: shallow embeddings, encoder, embedding vector, matrix, decoder, reconstruct, embedding vectors, graph structure

11.3.2 Limitations of shallow embeddings

This section explains four limitations of shallow embeddings and why they remain useful as a baseline for small, static graphs.

• Parameter scaling and sharing: Explain why assigning a separate vector to every node makes shallow embeddings costly on large graphs and prevents them from reusing patterns across nodes.
  Why it matters: These limitations explain why a large graph or repeated node roles can make a lookup-table approach inefficient.
• Features and unseen nodes: Distinguish the inability to naturally incorporate node attributes from the inability to embed nodes absent during training.
  Why it matters: The distinction shows why both rich node information and a changing graph challenge shallow embeddings.
• Remaining value of shallow embeddings: Explain why shallow embeddings remain useful despite these limitations.
  Why it matters: The limitations do not make shallow embeddings unsuitable for every graph or purpose.

Key terms: shallow embeddings, parameter inefficiency, no parameter sharing, feature blindness, node features, transductive nature, lookup table, GRL, baseline

11.4 Embeddings in knowledge graphs

This section explains why embeddings for knowledge graphs must represent relationship types, not just connections between entities.

• Relationship-aware knowledge graph embeddings: Explain why embeddings for a multirelational knowledge graph must capture how entities are related, not merely whether they are connected, and relate this need to predicting missing relationships.
  Why it matters: The kind of relationship is part of what a knowledge graph embedding needs to preserve.

Key terms: multirelational graphs, embeddings, KG completion

11.4.1 Loss function

This subsection explains why knowledge graph embedding losses use negative sampling, how the loss scores true and sampled relationships, and why the choice of negative examples matters.

• Limits of exhaustive comparison: Explain why directly comparing predictions against every possible node pair is impractical for large, sparse graphs, and why training instead uses existing edges and sampled negatives.
  Why it matters: This explains why the loss is designed around samples rather than the entire set of possible relationships.
• Positive and negative loss terms: Describe how the loss encourages high decoder scores for true relationships and low scores for sampled alternatives, and explain what γ controls.
  Why it matters: It connects the loss calculation to the scores the relationship decoder learns to produce.
• Quality of negative examples: Distinguish simple random sampling from type-constrained and adversarial sampling, and describe why replacing both source and destination nodes can matter.
  Why it matters: The negatives chosen for training affect whether a model learns meaningful relationship distinctions.

Key terms: loss function, sparsity, negative sampling, decoder, positive part, negative part, cross-entropy loss, γ, false negatives, type-constrained sampling

11.4.2 Multirelationship decoder

This section explains the relationship patterns knowledge graph embedding decoders must represent and compares three approaches to decoding them.

• Knowledge graph relationship patterns: Describe the symmetric, asymmetric, compositional, and inverse relationship patterns that a knowledge graph decoder may need to capture, using the section’s examples.
  Why it matters: These patterns explain why a decoder must account for relationship types rather than treating every edge alike.
• Decoder approaches and tradeoffs: Explain how TransE, RESCAL, and semantic-matching decoders represent or compare entities and relationships, and describe the tradeoffs the section identifies for TransE, RESCAL, and ComplEx.
  Why it matters: Decoder choice determines which knowledge graph patterns an embedding model can capture effectively.

Key terms: symmetric, asymmetric, compositional patterns, inverse relations, TransE, RESCAL, DistMult, ComplEx, translation-based, matrix-based

11.5 Message passing and graph neural networks

Introduces GNNs as an alternative to shallow embeddings when graphs are large or relationship patterns are complex.

• GNNs and shallow embedding limits: Explain why the section turns from shallow embeddings to GNNs, and describe neural message passing at the level introduced here.
  Why it matters: This connects the motivation for GNNs to the basic idea behind their approach.

Key terms: shallow embeddings, GNNs, neural message passing, neighborhoods

11.5.1 The message-passing framework: A neural conversation

This subsection explains how GNN nodes update their representations by exchanging information with neighbors over successive rounds.

• Neighbor message aggregation and update: Describe how a node collects messages from its neighbors, combines them with AGGREGATE, and uses UPDATE to change its representation.
  Why it matters: These two functions describe the basic operation behind the node updates discussed later.
• Information reach across rounds: Explain how repeated rounds let a node’s representation reflect information from progressively farther away, using the social-network example.
  Why it matters: The number of rounds explains how local exchanges can reflect a wider graph neighborhood.

Key terms: message passing, AGGREGATE, UPDATE, node’s representation, rounds, iterative updates, friends-of-friends, broader graph structure

11.5.2 Motivation and intuition: Why message passing works

This section explains why repeated message passing gives nodes representations that reflect both graph structure and neighboring features.

• Progressive neighborhood information: Explain how repeated message passing expands the information in a node’s representation and why that is useful. After k iterations, the representation includes information from the node’s k-hop neighborhood, capturing structural patterns and neighbors’ features.
  Why it matters: It explains why a node’s representation can express more than that node’s own features.

Key terms: message passing, k-hop neighborhood, graph topology, features of their neighbors

11.5.3 The basic GNN model

This section introduces the basic GNN node-update rule and explains how summing neighbor representations lets it handle nodes with different numbers of neighbors.

• Basic node update rule: Describe how the basic GNN updates a node’s representation at each iteration using its own representation, a sum of its neighbors’ representations, trainable parameter matrices, and a nonlinear activation.
  Why it matters: This rule is the starting point for understanding how a GNN turns graph neighborhoods into updated node representations.
• Variable neighborhood sizes: Explain why summing neighbor representations allows the basic GNN layer to process nodes with different numbers of neighbors.
  Why it matters: Graphs contain nodes with different neighborhood sizes, so the update must work without requiring every node to have the same number of neighbors.

Key terms: node representation, Wself, Wneigh, nonlinear activation function, bias term, summation operation, varying numbers of neighbors, fixed-size inputs

11.5.4 Message passing with self-loops

This section explains how self-loops simplify neural message passing and when that simplification is worth its trade-off.

• Self-loop message passing: Explain how adding self-loops changes the basic message-passing framework: each node is treated as its own neighbor during aggregation, combining the separate AGGREGATE and UPDATE steps.
  Why it matters: This is the change that makes the self-loop variant simpler than the basic framework.
• Self-loop benefits and trade-off: Describe the benefits of the self-loop variant and explain when retaining separate treatment of a node’s features and its neighbors’ features may be preferable.
  Why it matters: The simpler variant is not automatically the better choice for every task.

Key terms: self-loops, AGGREGATE, UPDATE, message passing, parameter sharing, overfitting, model stability, standard message passing, self-loop variant

11.6 Generalized aggregation and update methods

This section introduces architectural enhancements that help GNNs aggregate neighborhood information and update node representations despite the irregular structure of graphs.

• Skip connections in GNNs: Explain how skip connections help GNNs preserve earlier node features across message-passing layers and support deeper architectures.
  Why it matters: This explains why a GNN might retain information from earlier layers rather than relying only on its latest node representation.
• Attention-weighted neighbor aggregation: Describe how attention changes the way a GNN combines information from a node’s neighbors.
  Why it matters: Neighbor contributions need not count equally when the graph contains complex relationships.
• Normalization for uneven neighborhoods: Explain why normalization is useful in GNNs when nodes have different numbers of neighbors.
  Why it matters: Graph nodes do not all have the same number of neighbors, which can make stable training harder.

Key terms: skip connections, residual connections, over-smoothing, gradient flow, attention mechanisms, neighborhood aggregation, importance weights, normalization layers, layer normalization, batch normalization

11.6.1 Neighborhood normalization

This section explains how neighborhood normalization keeps graph message aggregation on a manageable scale, compares mean and symmetric normalization, and identifies a tradeoff between stability and structural information.

• Mean neighborhood normalization: Explain why summing neighbor features can be problematic when nodes have different numbers of neighbors, and how taking their mean addresses that problem.
  Why it matters: It explains why neighborhood size affects what a graph model learns from aggregated features.
• Symmetric degree normalization: Describe how symmetric normalization uses the degrees of both connected nodes to affect message strength, and give the section’s citation-network motivation.
  Why it matters: It shows why a simple average is not the only useful way to scale messages.
• Normalization and structural information: Explain when normalization is especially helpful and what information it can make harder to retain in learned embeddings.
  Why it matters: It helps the reader weigh more stable aggregation against the loss of potentially useful graph structure.

Key terms: neighborhood normalization, mean normalization, neighbor features, symmetric normalization, source and target nodes’ degrees, message strength, learned embedding, node degrees, structural information, lossy operation

11.6.2 Neighborhood attention

This section explains how neighborhood attention lets a GNN give more weight to relevant neighbors during aggregation instead of treating their normalized contributions equally.

• Learned neighbor importance weights: Explain how attention changes neighborhood aggregation by learning weights for different neighbors and using them in a weighted sum.
  Why it matters: It explains how a GNN can avoid giving every neighbor the same influence on a node’s representation.
• Useful contexts for attention: Describe when learning different neighbor weights is particularly valuable.
  Why it matters: It helps explain why equal treatment of neighbors may be a poor fit for some graphs and tasks.

Key terms: attention mechanisms, attention weights, weighted sum, neighborhood aggregation, task or context, noisy or irrelevant connections, complex, nonlinear relationships

11.6.3 Multihead attention and transformer connections

This section connects graph attention to transformer attention, explaining multihead attention and the use of structural encodings in GNNs.

• Graph and transformer attention: Distinguish what attends to what in transformers and graph attention networks, and describe the stated role of query, key, and value matrices.
  Why it matters: The comparison shows how a familiar attention idea changes when the input is a graph rather than a sentence.
• Parallel specialized attention heads: Explain why GNNs use multiple attention heads and how those heads work together.
  Why it matters: Multiple heads let a GNN attend to different kinds of relationships in the same neighborhood.
• Structural encodings for topology: Describe the analogy between transformer positional encodings and structural or positional encodings in some GNNs.
  Why it matters: The analogy identifies a way some GNNs represent where information sits in a graph.

Key terms: transformers, graph attention networks, query (Q), key (K), value (V), attention weights, multihead attention, attention head, neighborhood relationships, positional encodings

11.6.4 Generalized update methods

This section explains how GNN update methods balance a node’s existing representation with neighborhood information, and what affects the choice among them.

• GraphSAGE skip connections: Explain how GraphSAGE uses a concatenation-based update to retain a node’s previous state alongside aggregated neighborhood information, and why that helps.
  Why it matters: The update can preserve useful node-specific information even as neighborhood information is added.
• Selective gated updates: Explain how a gated update controls the balance between preserving a node’s existing representation and incorporating neighborhood information.
  Why it matters: A node need not treat every neighborhood update as equally valuable.
• Jumping knowledge representations: Describe how jumping knowledge networks use representations from multiple layers and what this lets different nodes capture.
  Why it matters: Useful structural context may come from different distances for different nodes.
• Update strategy tradeoffs: Justify a choice of update method using the task, graph properties, and computational cost, while explaining its relationship to aggregation.
  Why it matters: A sophisticated update is not automatically the right one for every graph or task.

Key terms: GraphSAGE, skip connections, concatenation-based update, gradient flow, gated updates, gating mechanism, node representation, neighborhood information, jumping knowledge networks, multiple layers

11.7 The synergy of GNNs and LLMs

The section explains why GNNs and LLMs complement each other and describes three ways to combine them for knowledge graph tasks.

• Complementary model strengths: Explain what GNNs and LLMs each contribute to a combined system, and why neither naturally handles both graph structure and rich text.
  Why it matters: The reason to combine the models is to use each where it is strongest.
• LLMs as final predictors: Describe the predictor arrangement, including the LLM's final role and the graph information it can use.
  Why it matters: This arrangement puts the LLM's generation ability at the end of a graph-informed task.
• LLMs as text encoders: Trace how the encoder arrangement uses an LLM's representations of node or edge text in a GNN.
  Why it matters: This arrangement adds information from text without giving up the GNN's structural processing.
• Parallel text structure alignment: Describe the aligner arrangement and why it can help when both textual content and graph connections matter.
  Why it matters: Alignment offers a way to retain distinct text and graph representations while using both in one task.

Key terms: GNNs, LLMs, message passing, graph structure, LLMs as predictors, graph embeddings, LLMs as encoders, feature representations, structural processing, LLMs as aligners

11.8 Summary