Linear algebra and symmetry
Needed to reason about invariance, equivariance, and aggregation.
Graph and geometric learning
Graph learning begins with the data unit and its symmetries. This chapter traces what messages can represent, how they scale, and which transformations must hold.
10 maintained papers · literature reviewed through 2 October 2026
Graph networks must respect permutation structure; geometric networks additionally encode translation, rotation, or reflection behavior. Neighborhood sampling, aggregation, depth, coordinates, and readout determine both scalability and what distinctions a model can represent.
Prerequisite contract
Neural-network optimization
Graph layers inherit normalization, depth, and optimization failures.
How the field developed
2017
Spectral and sampled neighborhood learning
GCN approximates localized spectral propagation; GraphSAGE samples and aggregates neighborhoods for inductive transfer.
Key papers in this section
Order Primary paper · authors · year · venue/status Core idea and why to read it Official resources 01.01 Semi-Supervised Classification with Graph Convolutional Networks A GCN layer mixes each node's features with its neighbors through a symmetrically degree-normalized adjacency matrix with self-loops, then applies one shared linear map and nonlinearity. Stacking two such layers lets labels on a small subset supervise representations across a fixed graph without adding an explicit Laplacian penalty to the loss. — 01.02 Inductive Representation Learning on Large Graphs GraphSAGE learns a shared function that generates a node embedding from its attributes and sampled local neighborhoods, rather than storing a separate trainable vector for every training node. The learned samplers, aggregators, and weight matrices can therefore embed unseen nodes—and, when feature meaning is shared, nodes in entirely unseen graphs. — Work: Implement both on the same graph and vary normalization and neighbor sampling.
Exit evidence: Trace tensor shapes and information paths for one node.
2017–2019
Message passing, attention, and expressivity
MPNN gives a common abstraction, GAT learns neighbor weights, and GIN connects aggregation injectivity to Weisfeiler–Lehman expressivity.
Key papers in this section
Order Primary paper · authors · year · venue/status Core idea and why to read it Official resources 02.01 Neural Message Passing for Quantum Chemistry Message Passing Neural Networks factor graph prediction into three learned operations: edges and neighboring states create messages, each node updates its hidden state from their sum, and a permutation-invariant readout maps the final set of states to a graph-level output. This common interface reveals that many earlier molecular graph networks differ mainly in those functions. — 02.02 Graph Attention Networks A Graph Attention Network replaces a fixed degree-based neighbor mixture with masked self-attention: each node scores its permitted neighbors from transformed endpoint features, normalizes scores within that neighborhood, and takes their weighted sum. Shared scoring parameters make the layer applicable to variable degrees and unseen graphs. — 02.03 How Powerful are Graph Neural Networks? GIN characterizes message-passing GNN expressivity through the one-dimensional Weisfeiler–Lehman test. If neighborhood aggregation, node update, and graph readout are injective over the relevant multisets, a sufficiently deep GNN distinguishes every graph pair that WL distinguishes. GIN approximates this condition with sum aggregation and MLPs, then concatenates or combines graph summaries across depths. The result is a tight expressivity benchmark for this GNN class—not a solver for graph isomorphism. Official code Work: Compare sum, mean, max, and attention aggregation on graphs with controlled symmetries.
Exit evidence: Construct one pair of graphs the chosen network cannot distinguish.
2021
Coordinate-aware equivariance
EGNN uses relative geometry to preserve E(n)-equivariance without expensive higher-order representations.
Key papers in this section
Order Primary paper · authors · year · venue/status Core idea and why to read it Official resources 03.01 E(n) Equivariant Graph Neural Networks EGNN builds translation-, rotation-, reflection-, and permutation-equivariant graph layers without spherical harmonics or higher-order tensor features. Edge messages depend on invariant node features and squared pairwise distance; coordinate updates are weighted sums of relative displacement vectors with scalar, invariant weights. Node features stay E(n)-invariant while coordinates transform equivariantly. This simple scalar–vector contract supports dynamics, graph autoencoding, and molecular property prediction. Official code Work: Rotate, translate, and reflect inputs and verify the expected output transformation numerically.
Exit evidence: State which outputs are invariant and which are equivariant.
2021–2026
Structural bias in graph Transformers
Graphormer encodes centrality, shortest paths, and edges inside full attention; the later GP-limit analysis asks which structural benefits survive a stated infinite-width/head regime.
Key papers in this section
Order Primary paper · authors · year · venue/status Core idea and why to read it Official resources 04.01 Do Transformers Really Perform Bad for Graph Representation?Published in the NeurIPS 2021 proceedings. Core mechanism: centrality, spatial, and edge encodings. Graphormer keeps a standard transformer-style global self-attention backbone but supplies graph inductive bias through node-degree centrality embeddings, shortest-path spatial biases, and edge features accumulated along paths. This reading boundary matters: the architecture demonstrates that transformers can be competitive graph encoders when structure is encoded explicitly, not that unrestricted dense attention is always efficient or superior to message passing. Official implementation 04.02 Gaussian Process Limit Reveals Structural Benefits of Graph TransformersPublished in Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337. Core mechanism: infinite-width and infinite-head kernels. The paper derives Gaussian-process kernels for GAT, Graphormer, and Specformer families and uses those limits to analyze when graph structure and community information survive depth rather than being smoothed away. This reading boundary matters: the results characterize declared infinite-width/head regimes and structural models, not universal behavior of trained finite graph transformers. — Work: Implement Graphormer structural encodings and matched message-passing baselines, then compare finite-width experiments with the precise width/head/scaling assumptions used by the Gaussian-process limit.
Exit evidence: Report graph split, positional/edge information, compute, finite-model accuracy, and which asymptotic structural benefits are theorem-backed rather than empirically assumed.
2025–2026
Boundary tokens and camera-aware relative position
PuzLM converts regular puzzle borders into discrete sequences for a language model, whereas URoPE transports calibrated camera geometry into relative positional features. Both change the representation interface, but neither is a general claim that language models discover geometry without suitable inputs.
Key papers in this section
Order Primary paper · authors · year · venue/status Core idea and why to read it Official resources 05.01 URoPE: Universal Relative Position Embedding across Geometric SpacesECCV 2026 Spotlight verified in the official Vision-Language Models & Visual Foundation Models session; manuscript #11480 checked on 2026-09-12. Publisher version of record was not independently verified. URoPE extends rotary position embedding to tokens from different cameras or geometric spaces. A key image patch is lifted along its camera ray at fixed candidate depths, then projected into the query camera. Ordinary two-dimensional RoPE operates on the resulting positions. Geometry changes the positional interface without adding a learned depth predictor. ECCV Spotlight program · Conference manuscript · Official project or implementation Work: What geometric information is preserved in the interface, and which calibration or discretization assumptions make that possible?
Exit evidence: Square-piece puzzle reconstruction is not arbitrary fracture recovery. Parameter-free positional encoding still needs trained host models and known camera parameters.
2026
Generative geometry: separate pairing cost, endpoint normalization and trajectory
SOT-CFM changes optimal-transport pairing to an angular cost. Spherical Flow Matching additionally places noise and data on a common sphere and regresses geodesic tangent velocities. These interventions expose whether the gain comes from pairing, removed radial variation, or the path itself.
Key papers in this section
Order Primary paper · authors · year · venue/status Core idea and why to read it Official resources 06.01 Geometry-Aware Image Flow Matching This paper asks whether image generation can benefit from separating direction from magnitude. SOT-CFM changes the optimal-transport pairing cost to an angular distance; Spherical Flow Matching additionally projects both endpoints to a sphere and learns geodesic tangent dynamics. These are two different interventions, not two names for the same normalization trick. Final proceedings PDF · Author manuscript Work: Which geometric assumption changes, and what information could normalization discard?
Exit evidence: ImageNet results use separately tuned guidance and radius; precision need not improve with gFID. Extreme norms and domains where magnitude carries meaning require explicit checks before transfer.
Research branches
Node and link learning
How far must information travel and what sampling bias enters?
Semi-Supervised Classification with Graph Convolutional Networks · Inductive Representation Learning on Large Graphs · Graph Attention Networks
Graph-level representation
Is aggregation injective enough for the structures of interest?
Neural Message Passing for Quantum Chemistry · How Powerful are Graph Neural Networks?
Geometric equivariance
Which physical symmetry should constrain intermediate and final states?
Structure-aware graph attention and asymptotic analysis
Which graph structure enters attention explicitly, and which conclusions survive only under an infinite-width or infinite-head limit?
Do Transformers Really Perform Bad for Graph Representation? · Gaussian Process Limit Reveals Structural Benefits of Graph Transformers
Boundary tokens and camera-aware relative position
What geometric information is preserved in the interface, and which calibration or discretization assumptions make that possible?
URoPE: Universal Relative Position Embedding across Geometric Spaces
Generative geometry: separate pairing cost, endpoint normalization and trajectory
Which geometric assumption changes, and what information could normalization discard?
Comparison table
| Family or stage | Scientific distinction | Main risk | Anchors |
|---|---|---|---|
| Normalized propagation | Smooths transformed neighbor features through a fixed rule. | Oversmoothing and degree shift erase useful distinctions. | 2017 |
| Learned aggregation | Samples or weights neighbors according to features. | Attention weights are not automatically causal explanations. | 2017 · 2018 |
| Equivariant geometry | Constrains coordinate transformations by construction. | The assumed symmetry may not match measurements or labels. | 2021 |
| Structural bias in graph Transformers | Graphormer injects centrality, shortest-path distance, and edge information into global attention; the GP-limit work analyzes structural behavior in a declared asymptotic regime. | Global attention cost, unavailable structural metadata, finite-network optimization, and theorem assumptions can invalidate a simple “Transformer beats message passing” conclusion. | 2021 · 2026 |
| Boundary tokens and camera-aware relative position | PuzLM converts regular puzzle borders into discrete sequences for a language model, whereas URoPE transports calibrated camera geometry into relative positional features. Both change the representation interface, but neither is a general claim that language models discover geometry without suitable inputs. | Square-piece puzzle reconstruction is not arbitrary fracture recovery. Parameter-free positional encoding still needs trained host models and known camera parameters. | 2026 |
| Generative geometry: separate pairing cost, endpoint normalization and trajectory | SOT-CFM changes optimal-transport pairing to an angular cost. Spherical Flow Matching additionally places noise and data on a common sphere and regresses geodesic tangent velocities. These interventions expose whether the gain comes from pairing, removed radial variation, or the path itself. | ImageNet results use separately tuned guidance and radius; precision need not improve with gFID. Extreme norms and domains where magnitude carries meaning require explicit checks before transfer. | 2026 |
Concept lineage
Semi-Supervised Classification with Graph Convolutional NetworksNeural Message Passing for Quantum Chemistry
A specific propagation rule becomes part of a general message–update–readout abstraction.
How Powerful are Graph Neural Networks?E(n) Equivariant Graph Neural Networks
Permutation expressivity is extended with explicit constraints for Euclidean coordinate transformations.
Failure modes to audit
- Leaking test nodes through transductive preprocessing.
- Confusing permutation invariance with geometric invariance.
- Ignoring disconnected components and degree shift.
- Comparing models with different neighborhood or positional information.
Questions for every paper
- What is a node, edge, and graph-level target?
- Which symmetries should hold?
- How many hops carry valid signal?
- What split prevents structural leakage?
Complete maintained paper route
Section titled “Complete maintained paper route”10 canonical readings · 2017–2026· route reviewed through October 2, 2026.
This is the complete structured list for this chapter, ordered chronologically from earlier foundations toward current work. The explanatory ladder above highlights the shortest conceptual route; this list also includes important branches, benchmarks, and current endpoints. It is generated from the same deduplicated catalog used by the AI background registry and My Library, so a future catalog update appears here automatically.
Show all 10 readings in maintained order
Semi-Supervised Classification with Graph Convolutional Networks
Thomas N. Kipf and Max Welling
Metadata checked
Inductive Representation Learning on Large Graphs
William L. Hamilton, Rex Ying, and Jure Leskovec
Metadata checked
Neural Message Passing for Quantum Chemistry
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl
Metadata checked
Graph Attention Networks
Petar Veličković et al.
Metadata checked
How Powerful are Graph Neural Networks?
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka
Official artifacts: Official code
Metadata checked
E(n) Equivariant Graph Neural Networks
Víctor Garcia Satorras, Emiel Hoogeboom, and Max Welling
Official artifacts: Official code
Metadata checked
Do Transformers Really Perform Bad for Graph Representation?
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu
Published in the NeurIPS 2021 proceedings.
Official artifacts: Official implementation
Metadata checked
Gaussian Process Limit Reveals Structural Benefits of Graph Transformers
Nil Ayday, Lingchu Yang, and Debarghya Ghoshdastidar
Published in Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337.
Metadata checked
URoPE: Universal Relative Position Embedding across Geometric Spaces
Yichen Xie, Depu Meng, Chensheng Peng, Yihan Hu, Quentin Herau, Masayoshi Tomizuka, and Wei Zhan
ECCV 2026 Spotlight verified in the official Vision-Language Models & Visual Foundation Models session; manuscript #11480 checked on 2026-09-12. Publisher version of record was not independently verified.
Official artifacts: ECCV Spotlight program · Conference manuscript · Official project or implementation
Metadata checked
Geometry-Aware Image Flow Matching
Junho Lee, Kwanseok Kim, and Joonseok Lee
Official artifacts: Final proceedings PDF · Author manuscript
Metadata checked