ChainGram: Discovering A Structural Grammar for Knowledge Graph Foundation Models

Knowledge graph foundation models (KGFMs) are emerging as a promising paradigm for transferable reasoning over knowledge graphs. By learning invariant patterns, they enable zero-shot inference on new KGs with unseen entities and relations. Existing KGFMs capture these patterns through relational interactions. However, these patterns are often implicitly encoded in learned representations, making them difficult to identify, organize, and reuse explicitly. Inspired by natural language grammar, we ask whether invariant patterns across KGs can be explicitly abstracted and organized into a transferable structural grammar. To this end, we propose ChainGram, a chain-based KGFM that learns such a grammar from relational chains across KGs for query-specific reasoning. Specifically, we propose a hierarchical codebook encoder to learn word-level structural codes and chain-level prototypes from relational chains. These prototypes are further aggregated into a relation-specific structural grammar. A grammar-guided reasoner then selects relevant patterns based on query-specific chains and aggregates pattern-consistent evidence for entity prediction. Experimental results across 54 KGs demonstrate that ChainGram achieves the best performance across all six evaluation settings, improving overall MRR over the strongest baseline by 2.82% under zero-shot inference and 5.84% with full fine-tuning. Our code is available at https://anonymous.4open.science/r/ChainGram-2857/.