🤖 machine learning

Neural Message Passing on Structural Interaction Graphs for Fully-Inductive Graph Neural Networks

This paper introduces SIGIL, a fully-inductive framework that overcomes input heterogeneity in graph foundation models by mapping arbitrary attributed graphs to a unified structural interaction graph, enabling the transfer of learned feature representations across diverse graphs and unifying existing knowledge graph reasoning approaches.

Original authors: Omer Yom Tov, Avigdor Gal

Published 2026-08-11

📖 3 min read☕ Coffee break read

CC BY 4.0

Original authors: Omer Yom Tov, Avigdor Gal

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot to understand the world. In the world of text, we have a massive dictionary of words that everyone agrees on; once the robot learns what "cat" or "run" means, it can read a new book about cats or running without needing a new lesson. But in the world of graphs—networks of connected things like social media friends, chemical molecules, or citation networks—there is no universal dictionary. Every graph comes with its own unique set of "features" (like the specific attributes of a person or a molecule) that might be completely different from the last one. A model trained to understand a network of scientists might be completely confused when handed a network of online shoppers because the "words" (features) don't match. This makes it incredibly hard to build a single, smart "foundation model" that can jump from one type of network to another without being retrained from scratch. The big question researchers are asking is: Can we build a universal translator for these messy, different networks that works on anything, anywhere, without needing a dictionary for every single new job?

This paper introduces a clever new framework called Sigil (which stands for Structural Interaction Graphs for Inductive Learning) to solve exactly that problem. Think of Sigil as a master chef who doesn't care about the specific ingredients you hand them (whether it's apples, carrots, or alien fruit). Instead of trying to memorize every possible ingredient, Sigil looks at how the ingredients interact with each other. It takes a messy, complex network and lifts it up to a new, simplified level called a "Structural Interaction Graph" (SIG). In this new view, the "nodes" aren't the people or molecules anymore; they are the features themselves (like "height," "price," or "color"). The connections in this new graph show how these features tend to align or clash based on how the original network is connected.

By running a special message-passing game on this new feature-map, Sigil learns a universal language for features. It translates any graph, no matter how weird or different its features are, into a standard, fixed-size format that a downstream AI can easily understand. The paper shows that this isn't just a new trick; it's a unifying theory. When the features are simple "one-hot" codes (like discrete relationship types in a knowledge graph), Sigil perfectly recovers existing powerful models. But when the features are continuous numbers (like real-valued sensor data), Sigil goes where those old models couldn't. The authors tested this on a wide variety of tasks, including predicting missing links in networks and classifying nodes. They found that a single Sigil model, trained on just one graph (like the Cora citation network), could perform incredibly well on completely unseen graphs with different features, often beating other "fully inductive" models that try to generalize. It's like teaching a student to read one book, and then having them ace a test on a book written in a completely different language, simply because they learned the underlying grammar of how ideas connect, rather than memorizing the words.

Technical Summary: Neural Message Passing on Structural Interaction Graphs for Fully-Inductive Graph Neural Networks

1. Problem Statement

The development of Graph Foundation Models (GFMs) faces a central obstacle: input heterogeneity. Unlike natural language, where a shared token vocabulary allows models to encode any text, graphs arrive with unique node-feature spaces that differ in dimensionality, coordinate semantics, and label sets. Consequently, a model trained on one graph generally cannot "read" another.

Existing approaches address parts of this challenge but fail to unify them:

Node Classification GFMs: Methods like GraphAny handle arbitrary feature and label spaces but are designed solely for node classification, lacking mechanisms for link prediction or relational reasoning.
Knowledge Graph Foundation Models (KGFMs): Models like ULTRA achieve zero-shot transfer on knowledge graphs by constructing a "relation graph" over discrete relation types. However, this approach is fundamentally discrete; it presumes a finite vocabulary of relations and lacks mechanisms for continuous node or edge features.

The core challenge is to design a fully-inductive graph model that generalizes across three axes simultaneously: unseen graph structures, unseen feature spaces (arbitrary dimensionality and semantics), and unseen label spaces.

2. Methodology: The Sigil Framework

The authors propose Sigil (Structural Interaction Graphs for Inductive Learning), a framework that maps any attributed graph to a unified, fixed-dimensional representation space. The core innovation is the Structural Interaction Graph (SIG).

2.1 Constructing the Structural Interaction Graph (SIG)

Given an input graph $G=(V, E)$ with node features $X \in \mathbb{R}^{n \times d}$ , Sigil "lifts" the graph from the node domain to the feature dimension domain.

Multi-Order Propagation: Features are propagated over increasing neighborhood orders $k$ (from $0$ to $K$ ) using non-parameterized propagation: $X^{(k)} = A^k X$ .
Interaction Operators: For each order $k$ , an interaction operator $g$ (e.g., subtraction or element-wise multiplication) is applied to the features of adjacent nodes to create edge features.
Role Aggregation: These edge features are aggregated back to nodes, separated by role (head/tail for directed graphs), creating summary matrices $\bar{X}^{(k)}_h$ and $\bar{X}^{(k)}_t$ . These matrices characterize how feature values instantiate across local neighborhoods.
Gram Matrix Construction: The alignment between feature dimensions is captured by computing Gram matrices (inner products) of these summary vectors: $\bar{A}^{(k)} = (\bar{X}^{(k)})^\top \bar{X}^{(k)}$ .
The SIG: The resulting matrices $\bar{A}^{(k)}$ $\overset{ˉ}{A}^{(k)}$ form a Structural Interaction Graph $G_{struct}$ $G_{s t r u c t}$ . In this graph:
- Nodes are the input feature dimensions $[d]$ .
- Edges are weighted and typed, encoding how pairs of features align across different orders of connectivity.
- For directed graphs, the construction yields four slices per order (head-head, tail-tail, head-tail, tail-head), capturing directional interactions.

2.2 Learning Representations via Relational Message Passing

Once the SIG is constructed, a Relational Message Passing Network (RMPNN) operates on it:

Embedding: The RMPNN embeds each feature dimension $f \in [d]$ into a fixed-size hidden space $d_h$ .
Transformation: The learned feature embeddings $\Theta^{(T)} \in \mathbb{R}^{d \times d_h}$ are used to transform the original node features of any graph into a unified representation: $H = X \Theta^{(T)}$ .
Inductive Property: Because the RMPNN parameters act only on the fixed hidden width $d_h$ and never on the input dimension $d$ , a single trained Sigil model can process graphs with arbitrary feature dimensionalities.

2.3 Downstream Tasks

Link Prediction: The unified node representations are fed into expressive link prediction GNNs (e.g., NBFNet) to perform zero-shot inference.
Node Classification: The unified representations serve as inputs to a downstream decoder (e.g., a lightweight MLP or closed-form analytical solution) to predict labels.

3. Key Contributions and Theoretical Properties

3.1 Strict Generalization of KGFMs

The paper proves that Sigil is a strict generalization of existing Knowledge Graph Foundation Models (like ULTRA).

Theorem 1: When the input features are one-hot indicators of discrete relations, the SIG construction exactly recovers the relation graph used by KGFMs.
Extension: Unlike KGFMs, Sigil accepts continuous features. The Gram matrices become continuous feature-alignment matrices rather than integer co-occurrence counts. Furthermore, Sigil's multi-order propagation encodes higher-order interactions between features that KGFMs (limited to single-hop motifs) miss.

3.2 Symmetry and Equivariance

Sigil satisfies the symmetries required for fully-inductive generalization:

Node Permutation Equivariance: The output node representations are equivariant to permutations of the input nodes.
Feature Permutation Invariance: The unified representation is invariant to the ordering or identity of the input feature dimensions. This allows the model to read graphs with feature spaces it has never seen.
Label Permutation Equivariance: When paired with an equivariant decoder, the model respects label permutations.

4. Experimental Results

The authors evaluate Sigil across three regimes, using a single model pre-trained on the Cora dataset (for link prediction and node classification) or a mixture of knowledge graphs (for KG reasoning).

4.1 Link Prediction (Continuous Features)

Evaluated on 11 benchmarks (7 attributed, 4 non-attributed).

Attributed Graphs: Sigil-lp is the strongest fully-inductive method on every dataset, outperforming baselines like UniLP and TFMLinker. Notably, it significantly outperforms UniLP on datasets like CiteSeer and AmazonPhotos, demonstrating that leveraging feature spaces via SIG is superior to discarding them.
Non-Attributed Graphs: Sigil-lp remains competitive, ranking second among fully-inductive methods and showing high stability.
Efficiency: Sigil-lp completes inference in minutes, whereas in-context baselines like UniLP exceed 24-hour time budgets.

4.2 Knowledge Graph Reasoning

Evaluated on the ULTRA benchmark (inductive settings with unseen entities and relations).

Reproduction: Sigil(0) (order 0 SIG) reproduces ULTRA's performance within a small margin (e.g., matching MRR exactly on pretraining graphs).
Expressivity: Higher-order SIGs (Sigil(1), Sigil(2)) show variable performance depending on the dataset, suggesting that while higher-order interactions add expressivity, they do not uniformly improve performance across all tasks.

4.3 Node Classification

Evaluated on 26 benchmarks with varying feature dimensions and class counts.

Performance: Sigil-nc is competitive, ranking best or second-best on 10 of 26 datasets. It trails specialized models like RGVT and TAG (which are optimized for specific tasks) but outperforms GraphAny and TS-MEAN.
Analysis: The authors attribute the performance gap to the "cost of unification": compressing arbitrary feature spaces into a fixed dimension $d_h$ makes original coordinates inaccessible to the decoder, requiring more supervision. However, the results confirm that learning on SIGs is a valid approach for node classification foundation models.

5. Significance and Claims

The paper claims that Sigil unifies several previously separate regimes in graph foundation model design:

Unification: It bridges the gap between node-classification GFMs (handling arbitrary features) and KGFMs (handling relational reasoning), providing a single mechanism for both.
Transferability: It demonstrates that a single model, trained on one graph, can deliver strong zero-shot performance on graphs with entirely different feature spaces and structures.
Generalization: By formalizing the relation graph as a discrete instance of a Structural Interaction Graph, the work provides a theoretical foundation for extending relational reasoning to continuous input spaces.

The authors conclude that transferability, relational reasoning, and edge-level tasks can arise from a single mechanism (SIG construction and message passing) rather than requiring separate designs for different graph types. Future work is suggested in refining architectures for learning on SIGs and studying their expressive power.