A Bit of History
Franco Scarselli and colleagues introduced the foundational "Graph Neural Network Model" in a 2009 paper, formalizing how a neural network could operate directly on graph-structured input. The field accelerated dramatically after Thomas Kipf and Max Welling published "Semi-Supervised Classification with Graph Convolutional Networks" in 2017, introducing an efficient, scalable "graph convolutional network" (GCN) architecture that made graph neural networks practical at real scale. On the knowledge-graph side, Google's 2012 public announcement of its own "Knowledge Graph" product brought the decades-older idea of structured, graph-based knowledge representation into mainstream visibility, and Antoine Bordes and colleagues' 2013 "TransE" paper introduced one of the first widely-adopted knowledge graph embedding techniques.
Why Graphs Need Different Machine Learning
Ordinary machine-learning pipelines are happiest when every example has the same shape: one row with a fixed number of columns, one image on a fixed pixel grid, or one sequence with an explicit order. A graph breaks that regularity in three ways at once: its size can vary, each vertex can have a different number of neighbors, and those neighbors have no canonical left-to-right order. More importantly, the examples are not independent rows — the edges say which examples should influence one another.
Same Information, Very Different Geometry
The mathematical version of that requirement is permutation symmetry. If we merely rename the vertices, node-level outputs should be renamed in exactly the same way (permutation equivariance), while a single graph-level prediction should stay unchanged (permutation invariance).
Memory Hook: Relabel, Then Recompute
If changing vertex IDs changes the graph-level answer, the model has learned the bookkeeping rather than the graph. A graph-native architecture should care about who is connected to whom, not whether a vertex happened to be stored as row 3 or row 3003.
Graph Neural Networks
A Graph Neural Network (GNN) replaces the fixed receptive field of a CNN with a graph-defined receptive field: each vertex updates itself using information from its neighbors. The learned vector at vertex \(v\), usually written \(h_v\), is an embedding — a compact set of coordinates that the model learns because those coordinates are useful for the prediction task.
A useful way to think about a GNN layer is: look one hop farther, summarize what you saw, then revise your state. Stack two layers and a vertex can be influenced by vertices up to two hops away; stack \(k\) layers and its structural receptive field reaches up to \(k\) hops. That is similar to BFS layers, except the GNN is learning what information to propagate and how to combine it.
Neighbors Send Evidence; the Target Updates
Message Passing
The dominant modern framework writes each layer as two conceptual functions: a message function decides what one neighbor should send, and an update function decides how the receiving vertex should combine the neighborhood summary with its previous state. A generic layer can be written as:
The crucial word is AGG. Sum, mean, max, attention-with-symmetric pooling, and similar constructions do not depend on the order in which neighbors are listed. Shared message/update functions plus a permutation-invariant aggregator produce the desired permutation-equivariant node computation.
Key Insight: Symmetric Aggregation Is the Relabeling Guarantee
If a vertex has neighbors \(\{a,b,c\}\), the model should get the same neighborhood summary whether the data structure presents them as \((a,b,c)\), \((c,a,b)\), or any other ordering. The graph has a set of neighbors, not a meaningful sequence of neighbors.
How the Receptive Field Grows
What “Seen” Really Means
A \(k\)-layer GNN has a \(k\)-hop receptive field, but that does not mean it perfectly preserves every fact in that neighborhood. Aggregation compresses many messages into fixed-size vectors, which becomes important when we discuss oversquashing and other limits below.
What Does a GNN Predict?
Once embeddings have been computed, the final prediction head depends on the unit you care about. Graph machine learning is not one task; it is a family of tasks that differ mainly in where the output lives.
The graph-level READOUT must also be permutation-invariant — common choices are sum, mean, max, or learned pooling. Training then looks familiar: make predictions, compare them with known targets using a loss function, and use backpropagation to adjust the message, update, and prediction parameters.
Limits of Message Passing
GNNs are powerful, but “more layers” is not automatically better. The same compression that makes message passing scalable also creates characteristic failure modes.
Two Ways Information Can Degrade
Other challenges include heterophily (neighbors may be deliberately different rather than similar), very large neighborhoods, and limited structural expressiveness. Many standard message-passing GNNs are closely connected to the 1-dimensional Weisfeiler-Lehman graph-refinement test, so some non-isomorphic structures remain indistinguishable to them.
Do Not Read a GNN Embedding as a Literal Map
An embedding is a learned coordinate system optimized for a task. Nearby vectors often indicate similar learned representations, but the axes usually do not have a direct human meaning, and geometric proximity alone is not a proof of causal or semantic equivalence.
Knowledge Graphs
A knowledge graph makes relation types first-class data. Instead of a plain unlabeled edge \(u-v\), each fact is a directed triple \((h,r,t)\): a head entity, a relation, and a tail entity. The same pair of entities may participate in several different relation types, and direction can matter.
Knowledge graphs support symbolic traversal (“follow these relation types”), learned link prediction, and hybrids of the two. One important modeling convention is the open-world assumption: a missing triple often means “unknown,” not automatically “false.” That is why completing a knowledge graph is different from simply classifying every absent edge as a negative fact.
Knowledge Graph Embeddings
Knowledge graph embeddings compress entities and relation types into vectors so that plausible triples receive better scores than implausible ones. TransE is the classic geometric example: treat a relation as a translation in vector space.
A Relation as a Learned Translation
Training typically contrasts observed triples with corrupted triples created by replacing a head or tail entity. The model learns to give true facts lower distance scores than these negative candidates.
Why TransE Is Elegant but Limited
A single translation vector struggles with relations whose geometry is not one-to-one. For a symmetric relation such as “married_to,” requiring both \(h+r\approx t\) and \(t+r\approx h\) pushes the same relation vector toward contradictory behavior. One-to-many, many-to-one, and many-to-many relations can create similar pressure. Later embedding families use richer transformations to represent these patterns.
GNNs and Knowledge-Graph Embeddings Solve Different Problems
| Approach | Main computation | Natural strength | Typical output |
|---|---|---|---|
| Message-passing GNN | Aggregate neighborhood features | Uses attributes + local topology | Node, edge, or graph predictions |
| KG embedding | Score typed triples geometrically | Multi-relational link prediction | Entity/relation vectors + triple scores |
| Relational GNN | Message passing conditioned on relation type | Combines both views | Contextual entity embeddings |
Real-World Applications
Drug Discovery via Molecular Graph Neural Networks
Pharmaceutical researchers represent candidate molecules directly as graphs — atoms as vertices, chemical bonds as edges — and use message passing to turn local chemical environments into learned atom embeddings. A permutation-invariant readout then combines those atom states into a molecule-level embedding, which can feed a predictor for properties such as solubility, toxicity, or binding-related targets.
- Why GNNs?Graphs have variable size, unordered neighborhoods, and relational dependence.
- Message passingCollect neighbor messages, aggregate symmetrically, update the target.
- Depth\(k\) layers give a structural receptive field of up to \(k\) hops.
- Prediction levelOutputs can live on vertices, edges/links, or the whole graph.
- Knowledge graphFacts are typed directed triples \((h,r,t)\), not plain edges.
- Embedding viewLearn coordinates that make useful structural or relational patterns easy to score.
Exercises
- Take a vertex with three neighbors and write one message-passing update using a mean aggregator. Then permute the order of those neighbors and explain why the result should be unchanged.
- Draw a small graph around a target vertex and shade its 1-hop, 2-hop, and 3-hop neighborhoods. Relate those regions to the receptive field of a 1-, 2-, and 3-layer message-passing GNN.
- For each task — fraud detection on users, friend recommendation, and molecule toxicity prediction — decide whether the output is node-level, link-level, or graph-level, and justify your choice.
- Represent four facts as knowledge-graph triples and write one multi-hop query whose answer depends on the sequence of relation types, not just graph connectivity.
- Challenge: Using the TransE equations above, explain algebraically why a symmetric relation can be awkward for a single translation vector. What would have to be true of \(r\) if both \(h+r\approx t\) and \(t+r\approx h\)?
Conclusion & Next Steps
Graph machine learning keeps the core lesson of graph theory intact: relationships change the problem. GNNs turn neighborhoods into learned representations while respecting permutation symmetry; graph-level readouts turn many node states into one prediction; knowledge graphs make relation types explicit; and embedding models translate symbolic facts into geometry that can be scored and completed. The recurring question is no longer only “what paths or cuts exist?” but also “what representation should a model learn from this structure?”
With theory, algorithms, large-scale processing, network science, and graph-native machine learning now connected, the series turns next to the sciences where graph abstractions have been useful for much longer than modern AI — chemistry, biology, and physics.
Next in the Series
In Part 27: Graph Applications in Science, we'll explore graph theory's surprisingly deep roots in chemistry, biology, and physics.