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

• URL: http://arxiv.org/abs/2510.01510v1
• Date: Wed, 01 Oct 2025 23:09:46 GMT
• Title: Flock: A Knowledge Graph Foundation Model via Learning on Random Walks
• Authors: Jinwoo Kim, Xingyue Huang, Krzysztof Olejniczak, Kyungbin Min, Michael Bronstein, Seunghoon Hong, İsmail İlkan Ceylan,
• Abstract summary: We study the problem of zero-shot link prediction on knowledge graphs (KGs)<n>We present Flock, a KGFM that iteratively samples random walks, encodes them into sequences via a recording protocol, embeds them with a sequence model, and aggregates representations of nodes and relations via learned pooling.<n>Flock perfectly solves our new diagnostic dataset Petals where current KGFMs fail, and achieves state-of-the-art performances on entity- and relation prediction tasks on 54 KGs from diverse domains.
• Score: 26.568227939080703
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of zero-shot link prediction on knowledge graphs (KGs), which requires models to generalize over novel entities and novel relations. Knowledge graph foundation models (KGFMs) address this task by enforcing equivariance over both nodes and relations, learning from structural properties of nodes and relations, which are then transferable to novel graphs with similar structural properties. However, the conventional notion of deterministic equivariance imposes inherent limits on the expressive power of KGFMs, preventing them from distinguishing structurally similar but semantically distinct relations. To overcome this limitation, we introduce probabilistic node-relation equivariance, which preserves equivariance in distribution while incorporating a principled randomization to break symmetries during inference. Building on this principle, we present Flock, a KGFM that iteratively samples random walks, encodes them into sequences via a recording protocol, embeds them with a sequence model, and aggregates representations of nodes and relations via learned pooling. Crucially, Flock respects probabilistic node-relation equivariance and is a universal approximator for isomorphism-invariant link-level functions over KGs. Empirically, Flock perfectly solves our new diagnostic dataset Petals where current KGFMs fail, and achieves state-of-the-art performances on entity- and relation prediction tasks on 54 KGs from diverse domains.

Related papers

• Topology Identification and Inference over Graphs [61.06365536861156]
  Topology identification and inference of processes evolving over graphs arise in timely applications involving brain, transportation, financial, power, as well as social and information networks.<n>This chapter provides an overview of graph topology identification and statistical inference methods for multidimensional data.
  arXiv  Detail & Related papers  (2025-12-11T00:47:09Z)
• QGraphLIME - Explaining Quantum Graph Neural Networks [0.48998185508205744]
  Quantum graph neural networks offer a powerful paradigm for learning on graph-structured data.<n>QuantumGraphLIME treats model explanations as distributions over local surrogates fit on structure-preserving perturbations of a graph.
  arXiv  Detail & Related papers  (2025-10-07T08:39:13Z)
• ReDiSC: A Reparameterized Masked Diffusion Model for Scalable Node Classification with Structured Predictions [64.17845687013434]
  We propose ReDiSC, a structured diffusion model for structured node classification.<n>We show that ReDiSC achieves superior or highly competitive performance compared to state-of-the-art GNN, label propagation, and diffusion-based baselines.<n> Notably, ReDiSC scales effectively to large-scale datasets on which previous structured diffusion methods fail due to computational constraints.
  arXiv  Detail & Related papers  (2025-07-19T04:46:53Z)
• Score-Based Model for Low-Rank Tensor Recovery [49.158601255093416]
  Low-rank tensor decompositions (TDs) provide an effective framework for multiway data analysis.<n>Traditional TD methods rely on predefined structural assumptions, such as CP or Tucker decompositions.<n>We propose a score-based model that eliminates the need for predefined structural or distributional assumptions.
  arXiv  Detail & Related papers  (2025-06-27T15:05:37Z)
• Causal Models for Growing Networks [4.055489363682199]
  We first enumerate the 96 causal directed acyclic graph (DAG) models over pairs of nodes.<n>We then partition them into 21 classes with ancestral sets that are closed under node marginalization.
  arXiv  Detail & Related papers  (2025-04-01T17:52:24Z)
• Nonparametric Partial Disentanglement via Mechanism Sparsity: Sparse Actions, Interventions and Sparse Temporal Dependencies [58.179981892921056]
  This work introduces a novel principle for disentanglement we call mechanism sparsity regularization. We propose a representation learning method that induces disentanglement by simultaneously learning the latent factors. We show that the latent factors can be recovered by regularizing the learned causal graph to be sparse.
  arXiv  Detail & Related papers  (2024-01-10T02:38:21Z)
• ER: Equivariance Regularizer for Knowledge Graph Completion [107.51609402963072]
  We propose a new regularizer, namely, Equivariance Regularizer (ER) ER can enhance the generalization ability of the model by employing the semantic equivariance between the head and tail entities. The experimental results indicate a clear and substantial improvement over the state-of-the-art relation prediction methods.
  arXiv  Detail & Related papers  (2022-06-24T08:18:05Z)
• Sparse Communication via Mixed Distributions [29.170302047339174]
  We build theoretical foundations for "mixed random variables" Our framework suggests two strategies for representing and sampling mixed random variables. We experiment with both approaches on an emergent communication benchmark.
  arXiv  Detail & Related papers  (2021-08-05T14:49:03Z)
• Explicit Pairwise Factorized Graph Neural Network for Semi-Supervised Node Classification [59.06717774425588]
  We propose the Explicit Pairwise Factorized Graph Neural Network (EPFGNN), which models the whole graph as a partially observed Markov Random Field. It contains explicit pairwise factors to model output-output relations and uses a GNN backbone to model input-output relations. We conduct experiments on various datasets, which shows that our model can effectively improve the performance for semi-supervised node classification on graphs.
  arXiv  Detail & Related papers  (2021-07-27T19:47:53Z)
• Machine Learning and Variational Algorithms for Lattice Field Theory [1.198562319289569]
  In lattice quantum field theory studies, parameters defining the lattice theory must be tuned toward criticality to access continuum physics. We introduce an approach to "deform" Monte Carlo estimators based on contour deformations applied to the domain of the path integral. We demonstrate that flow-based MCMC can mitigate critical slowing down and observifolds can exponentially reduce variance in proof-of-principle applications.
  arXiv  Detail & Related papers  (2021-06-03T16:37:05Z)
• Disentangling Observed Causal Effects from Latent Confounders using Method of Moments [67.27068846108047]
  We provide guarantees on identifiability and learnability under mild assumptions. We develop efficient algorithms based on coupled tensor decomposition with linear constraints to obtain scalable and guaranteed solutions.
  arXiv  Detail & Related papers  (2021-01-17T07:48:45Z)
• Residual Correlation in Graph Neural Network Regression [39.54530450932135]
  We show that conditional independence assumption severely limits predictive power. We address this problem with an interpretable and efficient framework. Our framework achieves substantially higher accuracy than competing baselines.
  arXiv  Detail & Related papers  (2020-02-19T16:32:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.