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 Standard Machine Learning Struggles With Graphs
Conventional neural networks (feedforward networks, CNNs, RNNs) all assume a fixed, regular input structure — a vector of a fixed size, a grid of pixels, a sequence in a fixed order. Graphs violate every one of these assumptions: different vertices can have wildly different numbers of neighbors, there is no inherent "ordering" of neighbors to feed into a fixed-size input, and the same underlying graph can be drawn or labeled in many equivalent ways (recall the graph isomorphism problem from Part 18) — any valid graph learning architecture must produce the same output regardless of how vertices happen to be labeled.
Graph Neural Networks
A Graph Neural Network (GNN) learns a vector representation ("embedding") for each vertex by aggregating information from its local neighborhood, then stacking multiple such aggregation layers so that information from increasingly distant vertices gradually propagates inward — a vertex's final representation, after \(k\) layers, has effectively "seen" every vertex within \(k\) hops (directly recalling BFS layering from Part 5).
Message Passing
The dominant modern GNN framework is message passing: at each layer, every vertex (1) collects "messages" from each of its neighbors (typically some function of the neighbor's current embedding and the edge connecting them), (2) aggregates those messages with a function that must be order-independent (like a sum, mean, or max — critical, since neighbors have no inherent ordering), and (3) updates its own embedding based on the aggregated message and its previous embedding.
Key Insight
Requiring an order-independent aggregation function is not a minor implementation detail — it is the mathematical guarantee that the network's output does not depend on an arbitrary vertex-labeling choice, directly addressing the graph isomorphism concern above. This single design constraint is what separates legitimate graph neural network architectures from a naive (and broken) approach that simply concatenates neighbor features in some arbitrary order.
Knowledge Graphs
A knowledge graph represents facts as directed, labeled edges — "(subject, relation, object)" triples, such as (Marie Curie, won, Nobel Prize) or (Paris, capital-of, France) — forming a large heterogeneous graph where both vertices (entities) and edges (relation types) carry meaning. This structure enables powerful reasoning: multi-hop queries can be answered by traversing paths through the graph (e.g., "who are the collaborators of collaborators of a given scientist"), and missing facts can sometimes be inferred from the graph's existing structure.
Knowledge Graph Embeddings
Knowledge graph embedding methods (like TransE) learn a vector representation for every entity and relation type such that true (subject, relation, object) triples satisfy a simple geometric relationship in the embedding space — TransE's core idea is disarmingly simple: learn embeddings such that \(\mathbf{e}_{\text{subject}} + \mathbf{e}_{\text{relation}} \approx \mathbf{e}_{\text{object}}\) for every true fact, which then allows predicting missing facts (a task called link prediction) by checking which candidate objects best satisfy that same approximate equation for a given subject and relation.
Real-World Applications
Drug Discovery via Molecular Graph Neural Networks
Pharmaceutical researchers represent candidate drug molecules directly as graphs — atoms as vertices, chemical bonds as edges — and train graph neural networks to predict properties like toxicity, binding affinity, or solubility directly from this molecular graph structure, without needing to hand-engineer chemical descriptor features. This graph-native approach has become a standard tool in modern computational drug discovery pipelines, directly connecting the message-passing GNN architecture described above to real pharmaceutical research.
Exercises
- Explain in your own words why a standard feedforward neural network cannot directly accept a graph with a variable number of vertices as input.
- Describe why the message-passing aggregation function (e.g., summing neighbor messages) must be order-independent, connecting this to the graph isomorphism problem from Part 18.
- Represent 3 simple facts (e.g., about family relationships) as knowledge graph triples, and identify one additional fact that could plausibly be inferred by traversing a multi-hop path through the graph.
- Challenge: Research the TransE embedding equation \(\mathbf{e}_{\text{subject}} + \mathbf{e}_{\text{relation}} \approx \mathbf{e}_{\text{object}}\) and explain, at a high level, why this simple additive structure struggles to represent certain relation types (like symmetric relations, e.g., "is married to").
Conclusion & Next Steps
Graph machine learning extends this series' algorithmic toolkit into the domain of learned, data-driven models — letting graphs power modern AI systems rather than only classical deterministic algorithms. With theory, algorithms, and machine learning all covered, the series turns next to where graph theory shows up across the sciences beyond computer science itself.
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.