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

2025/10/01 by Kim, Jinwoo, Xingyue Huang, Krzysztof Olejniczak +9 · 2 citations
Computer Science · Physics and Astronomy · #Advanced Graph Neural Networks #Complex Network Analysis Techniques #FOS: Computer and information sciences #Graph Theory and Algorithms #Machine Learning (cs.LG)

paper · pdf · doi:10.48550/arxiv.2510.01510

openalex publication_date 2025/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

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.

Citations

• TRIX: A More Expressive Model for Zero-shot Domain Transfer in Knowledge Graphs
• How Expressive are Knowledge Graph Foundation Models?
• A Prompt-Based Knowledge Graph Foundation Model for Universal In-Context Reasoning
• Non-convolutional Graph Neural Networks
• Revisiting Random Walks for Learning on Graphs
• Learning Long Range Dependencies on Graphs via Random Walks
• Towards Foundation Models for Knowledge Graph Reasoning
• Cooperative Graph Neural Networks
• A Multi-Task Perspective for Link Prediction with New Relation Types and Nodes
• InGram: Inductive Knowledge Graph Embedding via Relation Graphs
• A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Tests
• A Theory of Link Prediction via Relational Weisfeiler-Leman on Knowledge Graphs
• Double Equivariance for Inductive Link Prediction for Both New Nodes and New Relation Types
• Weisfeiler and Leman Go Relational
• Relational Message Passing for Fully Inductive Knowledge Graph Completion
• A*Net: A Scalable Path-based Reasoning Approach for Knowledge Graphs
• AdaProp: Learning Adaptive Propagation for Graph Neural Network based Knowledge Graph Reasoning
• DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks
• Equivariant Subgraph Aggregation Networks
• Relation Prediction as an Auxiliary Training Objective for Improving Multi-Relational Graph Representations
• Reconstruction for Powerful Graph Representations
• NodePiece: Compositional and Parameter-Efficient Representations of Large Knowledge Graphs
• Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction
• Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges
• Walking Out of the Weisfeiler Leman Hierarchy: Graph Learning Beyond Message Passing
• Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning
• Dynamic Anticipation and Completion for Multi-Hop Reasoning over Sparse Knowledge Graph
• The Surprising Power of Graph Neural Networks with Random Node Initialization
• CoDEx: A Comprehensive Knowledge Graph Completion Benchmark
• BoxE: A Box Embedding Model for Knowledge Base Completion
• Object-Centric Learning with Slot Attention
• GLU Variants Improve Transformer
• Inductive Relation Prediction by Subgraph Reasoning
• Composition-based Multi-Relational Graph Convolutional Networks
• Root Mean Square Layer Normalization
• Commonsense Knowledge Base Completion with Structural and Semantic Context
• Walking Randomly, Massively, and Efficiently
• Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks
• How Powerful are Graph Neural Networks?
• RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space
• Improving Knowledge Graph Embedding Using Simple Constraints
• DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning
• Convolutional 2D Knowledge Graph Embeddings
• Modeling Relational Data with Graph Convolutional Networks
• node2vec: Scalable Feature Learning for Networks
• On the Properties of Neural Machine Translation: Encoder-Decoder Approaches
• DeepWalk

Cited by

• Empowering LLMs with Structural Role Inference for Zero-Shot Graph Learning
• Half a Link can Be Enough to Predict a Whole Link: Understanding Generalization in Knowledge Graph Foundation Models

Related

• Towards Foundation Models for Knowledge Graph Reasoning
• Half a Link can Be Enough to Predict a Whole Link: Understanding Generalization in Knowledge Graph Foundation Models
• Beyond Transduction: A Survey on Inductive, Few Shot, and Zero Shot Link Prediction in Knowledge Graphs
• KGEx: Explaining Knowledge Graph Embeddings via Subgraph Sampling and Knowledge Distillation
• Walk-and-Relate: A Random-Walk-based Algorithm for Representation Learning on Sparse Knowledge Graphs