# Flock: A Knowledge Graph Foundation Model via Learning on Random Walks

arXiv: https://arxiv.org/abs/2510.01510 · HTML: https://mlsanity.com/paper/2510.01510/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 49 of its 62 references that are in the map.
- First posted on arXiv 1 Oct 2025.

## Builds on (most cited first, 30 of 49)

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [GLU Variants Improve Transformer](https://mlsanity.com/paper/2002.05202/) (2020)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Root Mean Square Layer Normalization](https://mlsanity.com/paper/1910.07467/) (2019)
- [On the Properties of Neural Machine Translation: Encoder-Decoder Approaches](https://mlsanity.com/paper/1409.1259/) (2014)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space](https://mlsanity.com/paper/1902.10197/) (2019)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Object-Centric Learning with Slot Attention](https://mlsanity.com/paper/2006.15055/) (2020)
- [Convolutional 2D Knowledge Graph Embeddings](https://mlsanity.com/paper/1707.01476/) (2017)
- [Composition-based Multi-Relational Graph Convolutional Networks](https://mlsanity.com/paper/1911.03082/) (2019)
- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)
- [DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning](https://mlsanity.com/paper/1707.06690/) (2017)
- [Inductive Relation Prediction by Subgraph Reasoning](https://mlsanity.com/paper/1911.06962/) (2019)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Equivariant Subgraph Aggregation Networks](https://mlsanity.com/paper/2110.02910/) (2021)
- [Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning](https://mlsanity.com/paper/2010.16103/) (2020)
- [DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks](https://mlsanity.com/paper/2111.06283/) (2021)
- [BoxE: A Box Embedding Model for Knowledge Base Completion](https://mlsanity.com/paper/2007.06267/) (2020)
- [CoDEx: A Comprehensive Knowledge Graph Completion Benchmark](https://mlsanity.com/paper/2009.07810/) (2020)
- [Knowledge Graph Reasoning with Relational Digraph](https://mlsanity.com/paper/2108.06040/) (2021)
- [Towards Foundation Models for Knowledge Graph Reasoning](https://mlsanity.com/paper/2310.04562/) (2023)
- [Graph Neural Networks for Link Prediction with Subgraph Sketching](https://mlsanity.com/paper/2209.15486/) (2022)
- [NodePiece: Compositional and Parameter-Efficient Representations of Large Knowledge Graphs](https://mlsanity.com/paper/2106.12144/) (2021)
- [Reconstruction for Powerful Graph Representations](https://mlsanity.com/paper/2110.00577/) (2021)
- [A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Tests](https://mlsanity.com/paper/2302.07090/) (2023)
- [Commonsense Knowledge Base Completion with Structural and Semantic Context](https://mlsanity.com/paper/1910.02915/) (2019)
- [InGram: Inductive Knowledge Graph Embedding via Relation Graphs](https://mlsanity.com/paper/2305.19987/) (2023)

## Built on by (most cited first, 9 of 9)

- [RelAgent: LLM Agents as Data Scientists for Relational Learning](https://mlsanity.com/paper/2605.07840/) (2026)
- [KGPFN: Unlocking the Potential of Knowledge Graph Foundation Model via In-Context Learning](https://mlsanity.com/paper/2605.14907/) (2026)
- [Riemannian Geometry Speaks Louder Than Words: From Graph Foundation Model to Next-Generation Graph Intelligence](https://mlsanity.com/paper/2603.21601/) (2026)
- [Half a Link can Be Enough to Predict a Whole Link: Understanding Generalization in Knowledge Graph Foundation Models](https://mlsanity.com/paper/2606.18001/) (2026)
- [Boosting Knowledge Graph Foundation Models via Enhanced Negative Sampling](https://mlsanity.com/paper/2605.27023/) (2026)
- [SPR: Toward a Graph Foundation Model for Transferable Graph Cognition via Spectral Patterns and Relational Geometry](https://mlsanity.com/paper/2606.03315/) (2026)
- [Reification as a Transferable Vocabulary: Zero-Shot Link Prediction with Vanilla GNNs](https://mlsanity.com/paper/2609.11347/) (2026)
- [The Universal Classifier for Graph Learning](https://mlsanity.com/paper/2609.36302/) (2026)
- [MERIT: Scaling KG Foundation Models with Relation Transformers](https://mlsanity.com/paper/2610.15638/) (2026)

## Abstract (arXiv)

We study the problem of zero-shot link prediction on knowledge graphs (KGs), which requires models to generalize to novel entities and novel relations. Knowledge graph foundation models (KGFMs) address this task by enforcing equivariance over both nodes and relations, which enables them to learn structural properties of nodes and relations that transfer to novel KGs with similar structure. However, the conventional notion of deterministic equivariance inherently limits the expressive power of KGFMs, as it prevents them from distinguishing relations that are structurally similar but semantically distinct. To overcome this limitation, we propose to leverage probabilistic node-relation equivariance, which preserves equivariance in distribution while using structured randomness to break symmetries at inference time. Building on this principle, we present Flock, a KGFM that iteratively samples random walks, encodes them into sequences, embeds them with a sequence model, and aggregates node and relation representations through learned pooling. Flock respects probabilistic node-relation equivariance and, crucially, is a universal approximator for isomorphism-invariant link-level functions over KGs. Empirically, Flock perfectly solves our new diagnostic dataset Petals on which current KGFMs fail, and achieves state-of-the-art performance on entity and relation prediction tasks across 54 KGs from diverse domains. Code is available at https://github.com/jw9730/flock.