Technical Summary: Structure-Centric Graph Foundation Model via Geometric Bases

1. Problem Statement

Graph Foundation Models (GFMs) aim to learn transferable representations across diverse graph domains. However, existing approaches face two primary limitations:

1. Structural Heterogeneity: Graphs vary significantly in topology, scale, and induced metrics across domains. Unlike text or images, graphs are relational objects defined only up to isomorphism, lacking a shared geometric reference.
2. Feature Incompatibility: Node feature spaces often differ in dimensionality and semantics across datasets. Current GFMs typically enforce fixed feature dimensions via dataset-specific projections, padding, or adapters. While this aligns feature spaces, it fails to align the underlying graph structures, leading to representations that poorly reflect intrinsic graph similarity and limiting cross-domain transfer.

Existing alternatives, such as graph tokenization, impose artificial orderings on inherently unordered structures, violating permutation invariance and failing to capture intrinsic graph geometry.

2. Methodology: SCGFM

The authors propose Structure-Centric Graph Foundation Models (SCGFM), which treat graph topology as the primary source of transferable knowledge. The core insight is to model graphs as metric measure spaces (mm-spaces) and learn a shared structural coordinate system.

2.1. Geometric Perspective

SCGFM assumes real-world graphs lie within a totally bounded subset of the space of mm-spaces. Based on Gromov's compactness theorem, any graph can be approximated by its distances to a finite set of canonical geometric patterns (bases).

2.2. Core Components

The framework consists of two stages: Geometric Bases Pre-training and Downstream Projection.

A. Learnable Geometric Bases

SCGFM learns a finite set of $K$ geometric bases $\{B_k\}_{k=1}^K$. Each base $B_k$ is defined as a finite mm-space $( [M], d_k, \mu_k )$:

• Metric ($d_k$): Represented by a learnable symmetric, hollow matrix $B_k \in [0, 1]^{M \times M}$, parameterizing the edge weights of a canonical graph structure with $M$ nodes.
• Measure ($\mu_k$): Fixed to a uniform distribution to ensure well-defined couplings.

These bases collectively form a shared structural coordinate system.

B. Structural Alignment via Gromov–Wasserstein (GW)

Input graphs $G$ are aligned to the bases using Gromov–Wasserstein (GW) distances. To ensure scalability, the method employs Sliced Gromov–Wasserstein (SGW), which reduces computational complexity from $O(N^3)$ to quasi-linear $O(N \log N)$ by projecting metric structures onto 1D slices.

For a graph $G$, the structural discrepancy to each base $B_k$ is computed as $\delta_k = d_{GW}(G, B_k)$. These distances are converted into a structural coordinate vector $w$ (weights) via a softmax function:
$$w_k = \frac{\exp(-\delta_k / \tau)}{\sum_j \exp(-\delta_j / \tau)}$$
This vector $w$ serves as the graph's representation in the shared geometric space.

C. Feature Re-encoding

To address feature incompatibility without assuming fixed dimensions, SCGFM employs a structure-aware feature re-encoding mechanism:

1. Transport Plan: The optimal transport plan $T_{ik}$ obtained during GW computation maps nodes from the input graph to the geometric base.
2. Projection: Node features are aggregated and projected onto the bases using $T_{ik}$, resulting in a unified feature matrix $H(G)$.
3. Unification: This process unifies node representations anchored to the structure, remaining agnostic to the original feature dimensionality.

D. Training Objectives

The pre-training objective minimizes a weighted sum of three losses:

1. GW Reconstruction Loss ($L_{gw}$): Minimizes the distance between the input graph and a linear surrogate of the GW barycenter (a weighted combination of bases).
2. Statistical Reconstruction Loss ($L_{rec}$): A decoder $f(\cdot)$ reconstructs graph-level statistics (degree histogram, clustering, motifs) from $w$ to ensure structural fidelity.
3. Diversity Regularization ($L_{div}$): Enforces pairwise separation between bases to prevent collapse and ensure they span the structural space.

2.3. Downstream Representation

The final graph embedding $z(G)$ is a concatenation of:

1. Structural coordinates $w$.
2. Reconstructed statistics $f(w)$.
3. Projected features $vec(H(G))$.

This unified embedding is used for downstream tasks (node or graph classification) via a frozen encoder and a lightweight classifier (e.g., Prototypical Network).

3. Key Contributions

1. Structure-Centric GFM: A novel framework that enables transfer across heterogeneous graph datasets without dataset-specific architectures or feature preprocessing, relying instead on a shared geometric coordinate system.
2. Geometric Bases & Latent Space: The introduction of learnable geometric bases that induce a geometry-aligned latent space. The authors demonstrate that distances in this space correlate strongly with intrinsic GW graph geometry.
3. Feature Flexibility: A mechanism to unify heterogeneous node features through structural alignment, eliminating the need for fixed feature dimensions or domain-specific preprocessing.
4. Theoretical Guarantees: Proof that the learned structural coordinates and reconstructed statistics are Lipschitz continuous with respect to the GW distance, ensuring stability.

4. Experimental Results

The authors evaluated SCGFM on 12 datasets across 5 domains (Molecules, Social Networks, Academic, E-commerce, Synthetic) for both graph-level and node-level classification under a 5-shot few-shot learning protocol.

• Performance: SCGFM consistently outperformed strong baselines, including vanilla GNNs (GCN, GIN, GAT), self-supervised methods (GraphCL, GraphMAE), and existing GFMs (GCOPE, RiemannGFM, GIT).
  • Graph Classification: Achieved superior in-domain and cross-domain accuracy, particularly on the COLORS-3 dataset where baselines degraded to near-chance levels due to large structural shifts.
  • Node Classification: Demonstrated near source-independent behavior. For example, on the Reddit dataset, performance remained high (~84%) regardless of the pre-training domain, attributed to the model's ability to project high-dimensional semantic features into a space where linear separability is guaranteed (Cover's Theorem).
• Scalability: SCGFM scaled smoothly to graphs with 5 million nodes, maintaining the lowest peak memory consumption (~12 GB) among all methods. Competing methods (GAT, GIT) encountered out-of-memory errors at lower scales.
• Ablation Studies:
  • On feature-dominant datasets (e.g., Cora), the projected features $vec(H)$ were critical; removing them caused a catastrophic drop in performance.
  • On structure-dominant datasets (e.g., PROTEINS, MUTAG), the geometric coordinates $w$ were the primary drivers of performance.
  • Both reconstruction and diversity losses were essential for stable training across all modalities.
• Interpretability: Visualizations showed that learned bases specialized in distinct geometric motifs (e.g., dense clusters, ring-and-tail patterns) and evolved from unstructured patterns to sharp topological primitives during training.
• Isometry: The latent Euclidean distances showed a strong linear correlation ($\rho \approx 0.70$) with true GW distances, confirming the embedding preserves intrinsic graph geometry.

5. Significance and Claims

The paper claims that SCGFM offers a principled alternative to graph tokenization and domain-dependent GFMs. By modeling graphs as metric measure spaces and utilizing GW distances, SCGFM successfully decouples topology from semantics.

The authors emphasize that their approach:

• Generalizes robustly across disparate domains without architectural modifications.
• Provides theoretical stability through Lipschitz continuity guarantees.
• Scales efficiently to massive graphs, overcoming the computational bottlenecks of exact GW computation via the SGW approximation.
• Adapts to data modality, effectively leveraging either structural or semantic signals depending on the dataset characteristics.

The work positions itself as a step toward a unified, structure-centric paradigm for graph foundation models that overcomes the limitations of feature-centric and token-based approaches.