Paper deep dive
Towards One-for-All Foundation Model for Attributed Graph Clustering
Yunhui Liu, Xudong Jin, Kang Zhang, Danshuo An, Yu Xing, Te Song, Jia Liu, Tieke He
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 10/13/2026, 4:25:05 AM
Summary
The paper introduces OFAG (One-for-All Foundation model for Attributed Graph Clustering), a foundation model designed to perform zero-shot clustering on diverse attributed graphs without graph-specific training, fine-tuning, or hyperparameter search. OFAG is built upon Prior-data Fitted Networks (PFNs) and is trained on synthetic graphs generated via the Coupled Attributed Graph Mixture (CAGM) prior. It utilizes a dimension-agnostic Signal-wise Filter Response Transformer (SwiFRT) encoder to handle heterogeneous feature spaces by treating features as graph signals. The model is optimized with a hyperspherical clustering objective. Experiments on ten datasets demonstrate that OFAG achieves state-of-the-art performance in clustering quality (NMI, ACC, ARI, F1) and is significantly faster than existing baselines.
Entities (10)
Relation Signals (9)
OFAG → solves → Attributed Graph Clustering
confidence 100% · We propose OFAG, a foundation model for attributed graph clustering.
OFAG → uses → Prior-Data Fitted Networks
confidence 95% · Building upon Prior-data Fitted Networks, OFAG learns a reusable clustering inference strategy
OFAG → uses → CAGM
confidence 95% · pre-training OFAG on synthetic attributed graphs drawn from the Coupled Attributed Graph Mixture (CAGM) prior
OFAG → uses → SwiFRT
confidence 95% · OFAG introduces the Signal-wise Filter Response Transformer (SwiFRT)
OFAG → evaluatedon → NMI
confidence 90% · achieves the best mean performance and average rank across NMI, ACC, ARI, and F1
OFAG → evaluatedon → ACC
confidence 90% · achieves the best mean performance and average rank across NMI, ACC, ARI, and F1
OFAG → evaluatedon → ARI
confidence 90% · achieves the best mean performance and average rank across NMI, ACC, ARI, and F1
OFAG → evaluatedon → F1
confidence 90% · achieves the best mean performance and average rank across NMI, ACC, ARI, and F1
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Attributed graph clustering aims to discover node groups by jointly exploiting node attributes and graph topology, yet its unsupervised nature makes model selection and adaptation inherently difficult. Existing methods typically train and tune a separate model for each input graph, leading to costly and fragile pipelines that often fail to transfer across graphs with different feature spaces, structural patterns, and attribute-structure correlations. In this paper, we study a one-for-all alternative: can a single model be trained once and directly applied to diverse attributed graphs without graph-specific training, fine-tuning, or hyperparameter search? We propose OFAG, a foundation model for attributed graph clustering. Building upon Prior-data Fitted Networks, OFAG learns a reusable clustering inference strategy from synthetic attributed graphs generated under broad priors over latent clusters, node attributes, and graph structures. To handle incompatible feature spaces across graphs, OFAG adopts a dimension-agnostic signal-wise graph encoder that treats each feature channel as a graph signal and models its response to shared graph filters. The model is trained with a hyperspherical clustering objective, producing clustering-friendly node representations in a single forward pass at inference time. On ten datasets, one frozen OFAG model achieves the best mean performance and average rank across NMI, ACC, ARI, and F1, while completing all ten datasets in 12.43 minutes total---over 6* faster than the second-fastest baseline and nearly 28* faster than the second-best on clustering quality. Our code and pretrained checkpoint are available at this https URL, allowing practitioners to directly apply OFAG to their own attributed graph datasets without additional training or tuning.
Tags
Links
- Source: https://arxiv.org/abs/2610.07778v1
- Canonical: https://arxiv.org/abs/2610.07778v1
Trouble viewing inline? Open PDF directly →
Full Text
135,100 characters extracted from source content.
Expand or collapse full text
Towards One-for-All Foundation Model for Attributed Graph Clustering DOI: X.XXXXXXXConference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NYISBN: 978-1-4503-X-X/2018/06123-A56-BU3CCS: Computing methodologies Cluster analysis Yunhui Liu Affiliation: State Key Laboratory for Novel Software Technology Nanjing University, Nanjing, China email: lyhcloudy1225@gmail.com , Xudong Jin Affiliation: State Key Laboratory for Novel Software Technology Nanjing University, Nanjing, China , Kang Zhang Affiliation: State Key Laboratory for Novel Software Technology Nanjing University, Nanjing, China , Danshuo An Affiliation: State Key Laboratory for Novel Software Technology Nanjing University, Nanjing, China , Yu Xing Affiliation: State Key Laboratory for Novel Software Technology Nanjing University, Nanjing, China , Te Song Affiliation: State Key Laboratory for Novel Software Technology Nanjing University, Nanjing, China , Jia Liu Affiliation: State Key Laboratory for Novel Software Technology Nanjing University, Nanjing, China and Tieke He Affiliation: State Key Laboratory for Novel Software Technology Nanjing University, Nanjing, China email: hetieke@gmail.com 2018 Abstract. Attributed graph clustering aims to discover node groups by jointly exploiting node attributes and graph topology, yet its unsupervised nature makes model selection and adaptation inherently difficult. Existing methods typically train and tune a separate model for each input graph, leading to costly and fragile pipelines that often fail to transfer across graphs with different feature spaces, structural patterns, and attribute-structure correlations. In this paper, we study a one-for-all alternative: can a single model be trained once and directly applied to diverse attributed graphs without graph-specific training, fine-tuning, or hyperparameter search? We propose OFAG, a foundation model for attributed graph clustering. Building upon Prior-data Fitted Networks, OFAG learns a reusable clustering inference strategy from synthetic attributed graphs generated under broad priors over latent clusters, node attributes, and graph structures. To handle incompatible feature spaces across graphs, OFAG adopts a dimension-agnostic signal-wise graph encoder that treats each feature channel as a graph signal and models its response to shared graph filters. The model is trained with a hyperspherical clustering objective, producing clustering-friendly node representations in a single forward pass at inference time. On ten datasets, one frozen OFAG model achieves the best mean performance and average rank across NMI, ACC, ARI, and F1, while completing all ten datasets in 12.43 minutes total—over 6×6× faster than the second-fastest baseline and nearly 28×28× faster than the second-best on clustering quality. Our code and pretrained checkpoint are available at https://github.com/Cloudy1225/OFAG, allowing practitioners to directly apply OFAG to their own attributed graph datasets without additional training or tuning. 1. Introduction Foundation models have transformed machine learning workflows in language, vision, and now supervised graph tasks: pre-train once on broad data, then apply to diverse inputs without task-specific optimization (Liu et al., 2025a; Wang et al., 2025). Attributed graph clustering, which partitions nodes by jointly exploiting features and topology without labels (Liu et al., 2026a; Liu et al., 2026d), has yet to benefit from this shift. Today, every new graph still demands the same costly ritual: design or select a model, tune hyperparameters blindly on unlabeled data, train from scratch, and hope that choices calibrated on one graph transfer to the next. This per-graph workflow is expensive for a principled reason: real attributed graphs vary substantially and unpredictably. Feature dimensions range from tens to thousands; attributes may be dense, continuous, or bag-of-words; graph structures span homophilous, heterophilous, and weakly-informative connectivity regimes; and cluster sizes and degree distributions may be highly imbalanced. As a result, assumptions that work well on one graph can fail on another. For example, aggressively propagating features along edges can be beneficial when graph structure agrees with clusters, but harmful when edges connect nodes from different groups. Without any validation labels, there is no signal to detect such failures or to guide model selection, and the cost of blind hyperparameter search across these axes compounds with every new graph. Graph foundation models (GFMs) represent a natural starting point, yet existing work leaves attributed graph clustering largely unaddressed (Mao et al., 2024; Liu et al., 2025a; Wang et al., 2025). Text-space GFMs (Liu et al., 2024a; Tang et al., 2024; Kong et al., 2025) unify graphs through natural language but require textual node attributes and dataset-specific templates. Feature-aligned GFMs (Zhao et al., 2024; Yu et al., 2025; Qiao et al., 2025) extend transfer to non-textual graphs but typically require target-graph fine-tuning. Fully inductive GFMs (Zhao et al., 2025; Choi et al., 2026; Eremeev et al., 2026) avoid per-graph training but rely on a labeled context set at inference to anchor predictions, a resource that clustering cannot provide. Beyond the availability of labels, attribution graph clustering poses three tightly coupled challenges that distinguish it from all supervised transfer settings: (i) permutable and variable cluster identities: cluster labels carry no consistent meaning across graphs and the number of clusters K varies, ruling out a shared output head; (i) no inference-time supervision: there are no labels at test time, no validation set for model selection, and no few-shot context to adapt to the target graph; (i) unsupervised feature space bridging: heterogeneous feature spaces are a known challenge for cross-graph transfer, but supervised GFMs address this through labeled fine-tuning or adaptation. Clustering must bridge incompatible feature dimensions and semantics entirely without downstream supervision. Together, these make zero-shot unsupervised transfer genuinely hard in a way that simply repurposing existing GFMs cannot resolve. In this work, we ask whether attributed graph clustering can be made one-for-all: can a single model be trained once and then directly applied to arbitrary attributed graphs without graph-specific training, fine-tuning, or hyperparameter search? We propose OFAG, a One-for-All foundation model for attributed Graph clustering, trained once on synthetic attributed graphs and applied to any new graph in a single forward pass, after which a standard algorithm recovers the clusters. The key idea is to adapt Prior-data Fitted Networks (PFNs) (Müller et al., 2025; Hollmann et al., 2025) to the unsupervised graph setting. PFNs amortize Bayesian inference over a prior on tasks, learning a reusable inference strategy from synthetic data rather than fitting parameters to each new instance. Adapting this paradigm to clustering is non-trivial: unlike supervised PFNs where labeled context nodes ground predictions, OFAG must recover cluster structure from attributes and topology alone, with no context labels and a variable, unlabeled query set. We address challenges (i) and (i) by pre-training OFAG on synthetic attributed graphs drawn from the Coupled Attributed Graph Mixture (CAGM) prior, which generates clustering tasks with variable K and permuted cluster identities, covering diverse feature types, cluster separabilities, structural regimes, and attribute-topology coupling strengths, compelling the model to learn an adaptive inference strategy without relying on any labeled context. To address challenge (i), OFAG introduces the Signal-wise Filter Response Transformer (SwiFRT). Standard GNNs apply feature transformations tied to a fixed feature space, making them incompatible with zero-shot transfer across heterogeneous graphs. SwiFRT instead treats each feature channel as a graph signal and encodes its structural response under a bank of graph diffusion filters (Ortega et al., 2018) (capturing whether a channel smooths uniformly, oscillates, or amplifies with local topology) using shared parameters applied independently to each channel. This makes the model both dimension-agnostic and invariant to feature-channel ordering, while remaining sensitive to graph structure. The model is trained with a hyperspherical clustering objective derived from the von Mises–Fisher distribution (Banerjee et al., 2005), shaping the embedding space so that same-cluster nodes concentrate near shared prototypes and prototypes spread uniformly across the unit hypersphere. We evaluate OFAG on ten benchmark datasets spanning diverse domains, from thousands to millions of nodes and covering both homophilous and heterophilous structures. A single frozen OFAG model achieves the best mean score and the best average rank across all four standard metrics (NMI, ACC, ARI, and F1), outperforming all dataset-specific baselines. Crucially, it is simultaneously the fastest method: OFAG completes all ten datasets in 12.43 minutes total, while the second-fastest baseline requires over 6×6× more time with substantially lower clustering quality, and the second-best baseline on clustering quality requires nearly 28×28× more computation. Since dataset-specific pipelines must also be re-tuned on every new graph without labels, accounting for hyperparameter search pushes the practical time savings to orders of magnitude. These results establish that prior-fitted foundation-model inference is not only conceptually appealing but also a practically superior route to fast and reusable attributed graph clustering. 2. Related Work 2.1. Attributed Graph Clustering Attributed graph clustering (AGC) aims to partition nodes by jointly exploiting node attributes and graph topology. Driven by graph neural networks (Kipf and Welling, 2017) and self-supervised learning (Liu et al., 2023a), recent AGC methods can be broadly viewed through an encode–cluster–optimize pipeline (Liu et al., 2026d). For encoding, methods range from non-parametric graph filters that smooth node features over topology (Zhang et al., 2019; Liu et al., 2024d) to parametric GNN encoders that learn deep structure-aware representations (Devvrit et al., 2022; Liu et al., 2024e). For cluster assignment, existing approaches use neural prototypes (Wang et al., 2019; Liu et al., 2023b), self-expressive subspace coefficients (Fettal et al., 2023; Lin et al., 2025), or differentiable community assignment modules (Tsitsulin et al., 2023; Blöcker et al., 2024). For optimization, objectives have evolved from two-stage embedding followed by k-means to joint training with graph reconstruction (Kipf and Welling, 2016; Wang et al., 2019; Xie et al., 2025), contrastive learning (Liu et al., 2024c; Liu et al., 2026c; Zheng et al., 2026), feature decorrelation (Zhang et al., 2021; Liu et al., 2022; Liu et al., 2025b), or clustering-specific losses (Xie et al., 2016; Liu et al., 2023b; Ju et al., 2026). However, existing methods remain dataset-specific, which is especially limiting without labels for validation, and assumptions tuned on one graph may not transfer across diverse feature types, structural regimes, and attribute-topology correlations. OFAG instead learns a reusable clustering inference strategy, enabling the same frozen model to cluster unseen graphs without graph-specific training, fine-tuning, or hyperparameter search. 2.2. Graph Foundation Models Graph foundation models (GFMs) aim to generalize graph learning beyond individual datasets (Liu et al., 2025a; Wang et al., 2025). Existing GFMs can be broadly grouped by how they handle cross-dataset heterogeneity. Text-space GFMs unify graph datasets through natural language, using LLMs to encode textual node attributes or perform prediction in text space (Tang et al., 2024; Liu et al., 2024a; Kong et al., 2025; Li et al., 2024; Wu et al., 2025b). They support task transfer and few-shot learning, but often rely on textual attributes or dataset-specific graph-to-text templates. Feature-aligned GFMs extend GFMs to non-textual graphs by mapping heterogeneous node features into a shared space, for example through SVD-based alignment or learnable patching (Zhao et al., 2024; He et al., 2025; Yu et al., 2025; Sun et al., 2025; Qiao et al., 2025). These methods improve cross-dataset transfer, but typically still require downstream adaptation or fine-tuning. Fully inductive GFMs further aim to operate on arbitrary graphs without target-graph training. Representative methods include GraphAny (Zhao et al., 2025), which combines predictors over multi-scale propagated features; TS-GNNs (Finkelshtein et al., 2026), which impose permutation equivariance and label invariance; G2T-FM (Eremeev et al., 2025) and TFM4GAD (Liu et al., 2026b), which augment node features with graph-based information and then pass them directly to tabular foundation models (Hollmann et al., 2025); NodePFN (Choi et al., 2026) and GraphPFN (Eremeev et al., 2026), which extend prior-data fitted networks (Müller et al., 2025) to node property prediction. Despite their progress, existing GFMs mainly target supervised graph tasks. OFAG addresses a different and largely unexplored problem: foundation modeling for attributed graph clustering. 2.3. Prior-Data Fitted Networks Prior-data fitted networks (PFNs) provide a learning paradigm for amortizing Bayesian inference over tasks sampled from a prior (Müller et al., 2022; Müller et al., 2025). Consider a task-specific parameter ϕ∼p(ϕ)φ p(φ) and a dataset =(xi,yi)i=1nD=\(x_i,y_i)\_i=1^n generated from p(y∣x,ϕ)p(y x,φ). Given a context set cD_c, Bayesian prediction for a query x is given by the posterior predictive distribution (1) p(y∣x,c)=∫p(y∣x,ϕ)p(ϕ∣c)ϕ.p(y x,D_c)= p(y x,φ)\,p(φ _c)\,dφ. Instead of computing this integral at test time, a PFN trains a neural network qθq_θ on synthetic datasets sampled from a prior p()p(D): (2) ℒPFN(θ)=c∪(x,y)∼p()[−logqθ(y∣x,c)].L_PFN(θ)=E_D_c∪\(x,y)\ p(D) [- q_θ(y x,D_c) ]. Minimizing this prior-data negative log-likelihood trains qθq_θ to approximate the posterior predictive distribution induced by the prior, enabling inference on new datasets in a single forward pass without gradient updates. PFNs have shown strong empirical performance across several domains, such as tabular prediction (Hollmann et al., 2023; Hollmann et al., 2025), time-series forecasting (Dooley et al., 2023; Xie et al., 2026), and node property prediction (Choi et al., 2026; Eremeev et al., 2026). OFAG follows the same high-level principle of prior fitting, but targets a different problem setting. It adapts the PFN philosophy from posterior predictive label inference to zero-shot clustering inference, learning from synthetic attributed graph priors how attributes and topology jointly reveal latent clusters. Figure 1. Overview of OFAG. The model is pre-trained on diverse synthetic attributed graphs using the SwiFRT encoder and a hyperspherical clustering objective. After pre-training, the frozen model can be directly applied to unseen real-world graphs for zero-shot clustering without graph-specific fine-tuning. 3. Methodology As illustrated in Figure 1, OFAG learns a reusable representation geometry from synthetic attributed graphs, enabling zero-shot clustering on arbitrary real graphs. Three challenges drive the design: feature spaces across graphs are heterogeneous in both dimension and semantics; cluster identities carry no consistent meaning across graphs and K varies; and node attributes and graph topology may provide complementary or conflicting evidence for clustering, depending on the graph. We address these through three coupled components: the CAGM prior (§3.2), which generates synthetic tasks that cover the full diversity of real attributed graphs; SwiFRT (§3.3), a dimension-agnostic encoder that operates on structural response patterns rather than raw feature values; and a hyperspherical clustering objective (§3.4), which shapes the embedding space to be directly amenable to label-free clustering algorithms. 3.1. Problem Setup Let =(,ℰ,X)G=(V,E,X) be an attributed graph with N=||N=|V| nodes, adjacency matrix A∈0,1N×NA∈\0,1\^N× N, and feature matrix X∈ℝN×FX ^N× F. Attributed graph clustering aims to assign each node to one of K latent clusters by jointly using A and X. Since cluster identities are arbitrary permutations of group indices and K varies across graphs, OFAG does not learn to output fixed class labels. Instead, it learns a representation geometry: a mapping from (A,X)(A,X) to node embeddings zi\z_i\ in which same-cluster nodes are geometrically close and different-cluster nodes are separable, a structure that any label-free algorithm (e.g., k-means) can exploit at inference without supervision. To acquire this geometry from synthetic supervision, let =(A,X,y)D=(A,X,y) denote one synthetic task, where y=(y1,…,yN)∈1,…,KNy=(y_1,…,y_N)∈\1,…,K\^N are latent cluster assignments available only during pre-training. Given a prior p()p(D), we optimize (3) θ∗=argminθ(A,X,y)∼p()[ℒ(y,fθ(A,X))].θ = _θ\,E_(A,X,y) p(D) [L (y,\,f_θ(A,X) ) ]. At inference, y is unavailable; the frozen fθ∗f_θ maps (A,X)(A,X) to embeddings clustered by a standard algorithm. The design of ℒL and p()p(D), detailed in the following subsections, ensures that minimizing this expectation teaches a reusable geometry rather than a dataset-specific solution. 3.2. Synthetic Attributed Graph Prior One-for-all generalization depends entirely on the breadth of p()p(D): a prior that is too narrow teaches shortcuts that fail on out-of-distribution graphs. We introduce the Coupled Attributed Graph Mixture (CAGM) prior, a latent-variable generative model in which latent cluster memberships are the shared cause of both node attributes and graph edges, framing OFAG as learning to invert a broad family of attributed graph generation processes. Generative structure. Each synthetic task samples N, F, and K from broad marginals; cluster proportions π∼Dirichlet(ηK)π ( 1_K) cover balanced and heavily imbalanced cluster sizes. Node attributes are generated from cluster-conditioned latents hiX|yi=k∼tν(μk,Σk)h_i^X y_i=k t_ν( _k, _k), then decoded by a task-specific random transformation T into continuous, categorical, count-valued, or bag-of-words features—covering the full diversity of real-world node attribute types. Edges are drawn as Aij∼Bernoulli(σ(sij))A_ij (σ(s_ij)), where the log-odds sij=ρ+αθ(θi+θj)+λBByi,yj+λHκ(hiA,hjA)+λXsim(xi,xj)s_ij=ρ+ _θ( _i+ _j)+ _BB_y_i,y_j+ _Hκ(h_i^A,h_j^A)+ _Xsim(x_i,x_j) combines cluster affinity (block matrix B), degree propensities (θi _i), latent structural proximity, and feature similarity. The block affinity matrix B is constructed from a continuously sampled edge homophily level h∼Uniform(0.1,0.9)h\! \!Uniform(0.1,0.9), interpolating smoothly between homophilous and heterophilous structural regimes. Full sampling details are in Appendix A. Design rationale. The diversity of structural regimes is deliberate. If the prior only generated homophilous graphs, OFAG could reduce to a feature-smoothing heuristic; if attributes were always well-separated, it could ignore topology altogether. By independently randomizing attribute separability, edge–cluster coupling, and structural regime across tasks, CAGM compels the model to learn an adaptive strategy that weighs attribute and structural evidence according to their relative reliability in each graph. The following theorem justifies why training on CAGM generalizes to real graphs; the proof is in Appendix B. Theorem 1 (Synthetic-to-real generalization). Let preal()p_real(G) be a distribution over attributed graphs satisfying: (i) the conditional feature distribution p(X∣y)p(X y), given latent cluster labels y, is a finite mixture of continuous distributions with y-dependent parameters; and (i) the edge distribution p(A∣y,X)p(A y,X) follows a pairwise probability model whose log-odds may depend arbitrarily on cluster membership and node features. Then there exist a graph encoder Φ and a CAGM prior psyn()p_syn(G) such that Φ#psyn() _\#p_syn(G) approximates preal()p_real(G) with arbitrarily small total variation distance. Conditions (i) and (i) are mild: they assert that both attributes and edges are generated through cluster-dependent mechanisms, without restricting to any particular distribution family or connectivity pattern. 3.3. Signal-wise Filter Response Transformer A dimension-specific feature transformation XWXW with W∈ℝF×dW ^F× d is incompatible with zero-shot transfer: it binds the model to a fixed feature dimension F and treats feature channels as semantically aligned across graphs, an assumption that fails when graphs come from different domains. OFAG resolves this with the Signal-wise Filter Response Transformer (SwiFRT), which changes what is encoded. Inspired by graph signal processing (Ortega et al., 2018), SwiFRT treats each feature channel X:,fX_:,f as a scalar signal on the graph and learns from its structural response rather than its raw values. The key observation is that the structural response is transferable across feature spaces: a signal that smooths uniformly under diffusion behaves differently from one that oscillates or amplifies with the local topology, regardless of the feature’s semantic content. SwiFRT therefore learns a single encoder operating in this response space, shared across all feature channels and all graphs. Filter response profiles. Let A^=D~−1/2(A+I)D~−1/2 A= D^-1/2(A+I) D^-1/2 be the symmetrically normalized adjacency matrix, where D~ D is the degree matrix of A+IA+I (Kipf and Welling, 2017; Zhu and Koniusz, 2020). For each node i and feature channel f, the filter response profile collects the signal value at each diffusion order ℓ=0,…,L =0,…,L: (4) ri,f=[(A^0X)i,f,(A^1X)i,f,…,(A^LX)i,f]∈ℝL+1.r_i,f= [( A^0X)_i,f,\;( A^1X)_i,f,\;…,\;( A^LX)_i,f ] ^L+1. This profile captures whether the signal at (i,f)(i,f) is locally stable, smoothed by neighbors, or progressively amplified or attenuated across multi-hop neighborhoods. Signal-wise transformer encoding. A shared encoder gθg_θ, applied identically to every (i,f)(i,f) pair, maps each profile ri,fr_i,f to a re-encoded scalar Zi,f=gθ(ri,f)Z_i,f=g_θ(r_i,f). We implement gθg_θ as a Transformer operating along the filter-order dimension. Each scalar response ri,f,ℓr_i,f, is first embedded as a d-dimensional token: (5) ei,f,ℓ=ϕval(ri,f,ℓ)+pℓ,ℓ=0,…,L,e_i,f, = _val(r_i,f, )+p_ , =0,…,L, where ϕval:ℝ→ℝd _val:R ^d embeds the response value and pℓ∈ℝdp_ ^d is a learnable filter-order positional embedding encoding which diffusion step was applied. Prepending a learnable summary token cclsc_cls, we run the sequence [ccls,ei,f,0,…,ei,f,L][c_cls,e_i,f,0,…,e_i,f,L] through the Transformer (Vaswani et al., 2017) and read off the summary-token output: (6) hi,f=Transformer([ccls,ei,f,0,…,ei,f,L])[0]∈ℝd,Zi,f=ϕout(hi,f),h_i,f=Transformer([c_cls,e_i,f,0,…,e_i,f,L])_[0] ^d,Z_i,f= _out(h_i,f), where ϕout:ℝd→ℝ _out:R^d is a shared scalar decoder. The Transformer performs self-attention only among filter-response tokens of the same node-feature pair (i,f)(i,f). Thus, it learns interactions among different filter orders, such as whether a feature value is stable under diffusion, rapidly smoothed by neighbors, amplified at higher orders, or inconsistent with its surrounding graph structure. These patterns characterize the signal’s structural role independently of its semantic content. The node representation is the row-normalized re-encoded feature vector: (7) zi=Zi,:/∥Zi,:∥2∈SF−1.z_i=Z_i,:\,/\,\|Z_i,:\|_2∈ S^F-1. This construction gives SwiFRT two desirable properties for one-for-all clustering. First, it is structure-aware: although the Transformer does not directly attend across nodes, each response profile already contains information aggregated by graph filters, so the scalar re-encoding reflects local and higher-order graph structure. Second, it is dimension-agnostic: because gθg_θ is applied independently to each feature channel, the same model can handle arbitrary input feature dimensions. The dimension-agnosticism and invariance to feature-channel ordering are formalized below; proofs are in Appendix C. Proposition 0 (Dimension-agnosticism and feature-permutation equivariance of SwiFRT). Let σ be any permutation of feature indices 1,…,F\1,…,F\, and let XσX_σ denote X with the f-th column equal to the σ(f)σ(f)-th column of X. SwiFRT satisfies: (i) the number of trainable parameters is independent of the input feature dimension F; and (i) SwiFRTθ(Xσ,A)=SwiFRTθ(X,A)σSwiFRT_θ(X_σ,A)=SwiFRT_θ(X,A)_σ, where the right-hand side denotes reordering the columns of SwiFRTθ(X,A)SwiFRT_θ(X,A) by σ. 3.4. Hyperspherical Clustering Objective We train OFAG with an objective derived from the von Mises–Fisher (vMF) distribution (Banerjee et al., 2005), which is the canonical probability distribution for directional data on the unit hypersphere. Prior work has observed that clustering often becomes more stable and effective when performed on hyperspherical representations, where angular similarity rather than vector magnitude determines the grouping structure (Caron et al., 2020; Wu et al., 2025a). This is suitable for our setting because different graphs may have incompatible feature scales and dimensions. Prototypes. Given normalized embeddings zi\z_i\ from SwiFRT for a synthetic graph with labels yi∈1,…,Ky_i∈\1,…,K\, we compute an episode-specific prototype for each cluster k on the fly: (8) μ^k=∑i:yi=kzi∥∑i:yi=kzi∥2+ε∈SF−1. μ_k= _i:\,y_i=kz_i \| _i:\,y_i=kz_i \|_2+ ∈ S^F-1. Computing prototypes on-the-fly from the current embeddings and known synthetic labels avoids global prototype parameters, accommodates variable K across tasks, and introduces no fixed cluster-identity structure. Compactness loss. Under a vMF mixture with shared concentration κ=1/τκ=1/τ, the posterior assignment probability is (9) qθ(yi=k∣zi)=exp(μ^k⊤zi/τ)∑k′=1Kexp(μ^k′⊤zi/τ),q_θ(y_i=k z_i)= ( μ_k z_i/τ) _k =1^K ( μ_k z_i/τ), and maximizing the likelihood of the synthetic assignments gives the compactness loss (10) ℒcomp=−1N∑i=1Nlogexp(μ^yi⊤zi/τ)∑k=1Kexp(μ^k⊤zi/τ).L_comp=- 1N _i=1^N ( μ_y_i z_i/τ) _k=1^K ( μ_k z_i/τ). This term encourages each representation to align with its cluster prototype while moving away from other prototypes. Proposition 0 (Compactness loss as vMF MLE). Minimizing ℒcompL_comp with respect to θ is equivalent to maximum likelihood estimation of the prototype directions μ^kk=1K\ μ_k\_k=1^K of a K-component vMF mixture with concentration κ=1/τκ=1/τ. Proof sketch. The vMF normalization constant ZF(κ)Z_F(κ) does not depend on the mean direction μk _k, so it cancels identically in Eq. (9), yielding a posterior equivalent to the complete-data log-likelihood of a vMF mixture. The full derivation is in Appendix D. ∎ Dispersion loss. The compactness loss alone does not prevent prototypes from collapsing into a small region of the hypersphere. We therefore add a prototype dispersion term: (11) ℒdisp=1K∑k=1Klog1K−1∑j≠kexp(μ^k⊤μ^j/τ),L_disp= 1K _k=1^K 1K-1 _j≠ k ( μ_k μ_j/τ ), whose minimization reduces pairwise cosine similarities between different prototypes and encourages the clusters to spread across the hypersphere. Remark 1 (Equiangular tight frame optimum). ℒdispL_disp is a log-sum-exp of pairwise cosine similarities between prototypes. When F≥K−1F≥ K-1, its minimizer approaches an equiangular tight frame (ETF): the unique configuration in which all pairwise cosine similarities equal −1/(K−1)-1/(K-1) and prototypes are as uniformly spread across SF−1S^F-1 as possible. This geometry maximizes inter-cluster angular separation and is most favorable for distinguishing unseen nodes between clusters at inference. Remark 2 (Complementarity of ℒcompL_comp and ℒdispL_disp). The two terms regularize complementary aspects of the mixture geometry: ℒcompL_comp concentrates each node near its prototype while repelling it from all other prototypes; ℒdispL_disp spreads the prototypes themselves across the hypersphere. Together they enforce that nodes concentrate within clusters and that clusters are separated from each other. Training objective. The overall prior-data objective is (12) ℒ(θ)=(A,X,y)∼p()[ℒcomp(θ,A,X,y)+λℒdisp(θ,A,X,y)],L(θ)=E_(A,X,y) p(D) [L_comp(θ;A,X,y)+λ\,L_disp(θ;A,X,y) ], where λ>0λ>0 balances the two terms. In practice, this expectation is approximated by Monte Carlo: at each training step we sample a batch of synthetic graphs, encode them with SwiFRT, compute on-the-fly prototypes from the synthetic labels, and back-propagate through the combined loss. Table 1. Clustering performance in NMI and ACC on homophilous and heterophilous attributed graphs. The best, second-best, and third-best results in each column are highlighted. For Avg. Rank, lower is better; for all other columns, higher is better. Model Metric Homophilous Graphs Heterophilous Graphs Mean Avg. Rank Cora Photo ArXiv Reddit Products HM Flickr MAG Pokec WebTopic KMeans NMI 13.89±4.46 ± 4.46 31.70±0.49 ± 0.49 22.59±0.03 ± 0.03 11.08±0.14 ± 0.14 29.24±0.11 ± 0.11 10.17±0.11 ± 0.11 1.21±0.07 ± 0.07 28.32±0.06 ± 0.06 1.41±0.00 ± 0.00 2.45±0.05 ± 0.05 15.21 16.30 ACC 33.09±4.00 ± 4.00 42.54±2.54 ± 2.54 16.95±0.38 ± 0.38 8.59±0.06 ± 0.06 21.23±0.74 ± 0.74 14.12±0.25 ± 0.25 26.02±1.73 ± 1.73 7.09±0.03 ± 0.03 1.91±0.01 ± 0.01 9.63±0.34 ± 0.34 18.12 15.90 Node2Vec NMI 44.95±1.49 ± 1.49 66.02±1.05 ± 1.05 38.93±0.15 ± 0.15 79.23±0.38 ± 0.38 50.97±0.20 ± 0.20 7.60±0.13 ± 0.13 5.59±0.00 ± 0.00 37.73±0.03 ± 0.03 31.92±0.02 ± 0.02 5.80±0.09 ± 0.09 36.87 9.80 ACC 60.52±2.81 ± 2.81 73.08±1.06 ± 1.06 25.97±0.57 ± 0.57 70.67±1.68 ± 1.68 36.59±0.74 ± 0.74 13.28±0.41 ± 0.41 24.44±0.01 ± 0.01 10.86±0.09 ± 0.09 16.62±0.19 ± 0.19 10.71±0.12 ± 0.12 34.27 10.60 SSGC NMI 51.85±1.05 ± 1.05 70.75±1.39 ± 1.39 46.12±0.16 ± 0.16 51.61±0.36 ± 0.36 52.04±0.17 ± 0.17 12.15±0.11 ± 0.11 4.48±0.19 ± 0.19 41.52±0.04 ± 0.04 4.33±0.01 ± 0.01 3.92±0.11 ± 0.11 33.88 7.60 ACC 65.38±1.47 ± 1.47 76.34±4.04 ± 4.04 38.58±0.56 ± 0.56 40.00±1.79 ± 1.79 37.02±0.70 ± 0.70 15.57±0.07 ± 0.07 25.95±0.42 ± 0.42 11.89±0.10 ± 0.10 2.93±0.04 ± 0.04 11.34±0.18 ± 0.18 32.50 9.10 SAGSC NMI 44.35±0.06 ± 0.06 58.40±0.02 ± 0.02 43.27±0.19 ± 0.19 80.02±0.38 ± 0.38 51.78±0.24 ± 0.24 12.47±0.13 ± 0.13 6.86±0.00 ± 0.00 40.15±0.03 ± 0.03 38.33±0.03 ± 0.03 9.11±0.26 ± 0.26 38.47 6.90 ACC 63.45±0.03 ± 0.03 67.91±0.01 ± 0.01 30.87±0.83 ± 0.83 72.79±1.57 ± 1.57 38.11±0.69 ± 0.69 17.83±0.11 ± 0.11 26.72±0.01 ± 0.01 11.90±0.16 ± 0.16 19.86±0.23 ± 0.23 13.66±0.53 ± 0.53 36.31 6.95 MS2CAG NMI 53.64±0.64 ± 0.64 72.49±0.79 ± 0.79 44.20±0.18 ± 0.18 72.85±0.53 ± 0.53 50.71±0.31 ± 0.31 9.75±0.36 ± 0.36 7.32±0.02 ± 0.02 40.39±0.07 ± 0.07 2.77±0.05 ± 0.05 7.77±0.08 ± 0.08 36.19 7.70 ACC 70.29±0.66 ± 0.66 79.13±0.05 ± 0.05 35.85±0.21 ± 0.21 60.40±2.40 ± 2.40 35.41±0.62 ± 0.62 15.06±0.28 ± 0.28 28.29±0.06 ± 0.06 11.70±0.10 ± 0.10 2.27±0.09 ± 0.09 12.38±0.12 ± 0.12 35.08 8.10 DAEGC NMI 46.88±1.71 ± 1.71 63.60±0.02 ± 0.02 39.81±0.29 ± 0.29 40.84±0.76 ± 0.76 9.18±3.05 ± 3.05 11.46±0.09 ± 0.09 4.23±0.03 ± 0.03 29.00±2.17 ± 2.17 3.85±0.21 ± 0.21 4.79±0.29 ± 0.29 25.36 13.40 ACC 64.06±3.18 ± 3.18 77.78±0.01 ± 0.01 28.68±0.64 ± 0.64 27.57±0.33 ± 0.33 14.83±2.09 ± 2.09 17.37±0.31 ± 0.31 28.51±0.35 ± 0.35 10.83±0.51 ± 0.51 3.99±0.03 ± 0.03 16.42±0.61 ± 0.61 29.00 9.20 DinkNet NMI 55.56±0.18 ± 0.18 64.74±0.06 ± 0.06 37.24±0.57 ± 0.57 54.95±0.24 ± 0.24 38.43±0.18 ± 0.18 11.26±0.06 ± 0.06 6.67±0.05 ± 0.05 37.12±0.05 ± 0.05 3.91±0.01 ± 0.01 5.47±0.04 ± 0.04 31.54 11.00 ACC 72.49±0.50 ± 0.50 74.03±0.25 ± 0.25 25.47±0.88 ± 0.88 38.51±0.82 ± 0.82 26.78±0.37 ± 0.37 15.79±0.28 ± 0.28 29.94±0.38 ± 0.38 10.14±0.08 ± 0.08 2.73±0.04 ± 0.04 11.52±0.55 ± 0.55 30.74 10.50 MinCut NMI 40.80±1.83 ± 1.83 62.34±2.39 ± 2.39 39.00±1.02 ± 1.02 48.85±3.58 ± 3.58 35.80±0.71 ± 0.71 7.42±0.37 ± 0.37 7.59±0.19 ± 0.19 38.21±0.12 ± 0.12 5.78±0.18 ± 0.18 6.07±0.52 ± 0.52 29.19 12.10 ACC 52.95±6.65 ± 6.65 69.46±2.22 ± 2.22 27.88±1.20 ± 1.20 34.09±2.08 ± 2.08 24.88±0.74 ± 0.74 13.87±0.43 ± 0.43 27.64±1.87 ± 1.87 11.60±0.32 ± 0.32 3.17±0.09 ± 0.09 11.67±0.95 ± 0.95 27.72 12.60 DMoN NMI 43.84±2.29 ± 2.29 62.74±2.67 ± 2.67 38.77±0.28 ± 0.28 50.66±0.38 ± 0.38 34.80±0.85 ± 0.85 7.59±0.92 ± 0.92 7.89±0.09 ± 0.09 38.30±0.12 ± 0.12 8.42±0.08 ± 0.08 7.49±0.37 ± 0.37 30.05 10.95 ACC 52.99±4.70 ± 4.70 72.68±1.87 ± 1.87 25.89±1.12 ± 1.12 39.29±1.29 ± 1.29 25.40±1.37 ± 1.37 12.32±0.58 ± 0.58 28.64±0.69 ± 0.69 10.81±0.08 ± 0.08 4.40±0.07 ± 0.07 12.70±0.73 ± 0.73 28.51 11.30 Neuromap NMI 46.98±2.61 ± 2.61 61.84±2.34 ± 2.34 40.70±0.80 ± 0.80 47.81±0.28 ± 0.28 34.80±1.46 ± 1.46 7.44±0.17 ± 0.17 7.77±0.57 ± 0.57 39.14±0.20 ± 0.20 8.53±0.25 ± 0.25 7.19±0.51 ± 0.51 30.22 10.85 ACC 56.96±3.98 ± 3.98 71.89±4.19 ± 4.19 33.31±1.07 ± 1.07 32.64±0.20 ± 0.20 31.87±1.93 ± 1.93 12.73±0.25 ± 0.25 28.86±2.39 ± 2.39 15.95±0.32 ± 0.32 5.12±0.21 ± 0.21 16.82±1.69 ± 1.69 30.61 8.40 GAE NMI 50.09±0.07 ± 0.07 61.36±0.14 ± 0.14 40.86±0.15 ± 0.15 45.90±0.27 ± 0.27 42.55±0.09 ± 0.09 13.58±0.12 ± 0.12 4.07±0.05 ± 0.05 39.30±0.03 ± 0.03 3.79±0.04 ± 0.04 3.89±0.14 ± 0.14 30.54 11.70 ACC 67.53±0.13 ± 0.13 71.54±0.08 ± 0.08 24.39±0.31 ± 0.31 34.56±0.81 ± 0.81 27.70±0.43 ± 0.43 16.58±0.32 ± 0.32 38.42±1.07 ± 1.07 11.21±0.07 ± 0.07 2.49±0.02 ± 0.02 11.86±0.06 ± 0.06 30.63 10.40 DGI NMI 56.22±0.87 ± 0.87 67.77±0.54 ± 0.54 42.29±0.08 ± 0.08 72.93±0.14 ± 0.14 41.28±0.13 ± 0.13 11.67±0.06 ± 0.06 6.88±0.01 ± 0.01 39.39±0.03 ± 0.03 4.20±0.01 ± 0.01 5.91±0.02 ± 0.02 34.85 8.00 ACC 72.22±2.92 ± 2.92 77.57±0.28 ± 0.28 30.49±0.64 ± 0.64 62.52±0.34 ± 0.34 28.99±0.52 ± 0.52 15.78±0.32 ± 0.32 24.92±0.17 ± 0.17 10.60±0.11 ± 0.11 2.23±0.02 ± 0.02 11.69±0.10 ± 0.10 33.70 10.15 CCASSG NMI 58.74±0.87 ± 0.87 64.54±3.23 ± 3.23 44.69±0.04 ± 0.04 49.63±0.07 ± 0.07 50.89±0.31 ± 0.31 11.93±0.15 ± 0.15 4.67±0.01 ± 0.01 40.40±0.02 ± 0.02 1.35±0.01 ± 0.01 3.79±0.18 ± 0.18 33.06 9.40 ACC 73.35±1.92 ± 1.92 70.90±2.27 ± 2.27 30.68±0.27 ± 0.27 37.91±0.49 ± 0.49 37.99±0.42 ± 0.42 15.78±0.14 ± 0.14 23.03±0.35 ± 0.35 11.90±0.05 ± 0.05 1.95±0.01 ± 0.01 11.65±0.91 ± 0.91 31.51 10.60 S3GC NMI 55.45±1.12 ± 1.12 68.27±2.22 ± 2.22 47.11±0.12 ± 0.12 83.45±0.39 ± 0.39 53.43±0.16 ± 0.16 11.57±0.08 ± 0.08 7.84±0.00 ± 0.00 39.80±0.03 ± 0.03 6.04±0.00 ± 0.00 7.83±0.02 ± 0.02 38.08 5.10 ACC 70.33±1.98 ± 1.98 75.92±3.26 ± 3.26 35.57±0.60 ± 0.60 81.86±1.59 ± 1.59 40.45±0.62 ± 0.62 16.49±0.22 ± 0.22 28.48±0.00 ± 0.00 12.15±0.05 ± 0.05 2.97±0.03 ± 0.03 12.75±0.07 ± 0.07 37.70 6.00 MAGI NMI 58.94±0.41 ± 0.41 68.65±0.16 ± 0.16 46.53±0.16 ± 0.16 72.53±0.19 ± 0.19 44.58±0.14 ± 0.14 11.24±0.46 ± 0.46 6.31±0.16 ± 0.16 41.34±0.02 ± 0.02 8.76±0.02 ± 0.02 9.27±0.20 ± 0.20 36.82 5.75 ACC 74.22±0.57 ± 0.57 76.66±0.18 ± 0.18 37.32±0.74 ± 0.74 64.78±1.38 ± 1.38 33.15±0.34 ± 0.34 18.49±0.83 ± 0.83 24.28±0.46 ± 0.46 13.25±0.07 ± 0.07 3.90±0.03 ± 0.03 14.37±0.76 ± 0.76 36.04 5.60 NS4GC NMI 59.40±0.48 ± 0.48 72.62±0.79 ± 0.79 48.39±0.24 ± 0.24 56.71±0.05 ± 0.05 54.63±0.14 ± 0.14 15.28±0.17 ± 0.17 6.19±0.01 ± 0.01 41.64±0.01 ± 0.01 7.19±0.04 ± 0.04 10.05±0.04 ± 0.04 37.21 3.40 ACC 74.92±0.59 ± 0.59 79.21±0.03 ± 0.03 39.01±1.07 ± 1.07 43.80±0.52 ± 0.52 41.83±0.40 ± 0.40 18.40±0.42 ± 0.42 24.27±0.06 ± 0.06 13.28±0.09 ± 0.09 3.19±0.01 ± 0.01 15.69±0.14 ± 0.14 35.36 4.40 OFAG NMI 57.06±0.00 ± 0.00 71.45±0.00 ± 0.00 45.08±0.19 ± 0.19 85.94±0.00 ± 0.00 52.77±0.00 ± 0.00 11.61±0.19 ± 0.19 9.27±0.00 ± 0.00 41.78±0.02 ± 0.02 10.63±0.05 ± 0.05 9.27±0.00 ± 0.00 39.49 3.05 ACC 74.04±0.00 ± 0.00 79.05±0.00 ± 0.00 34.75±0.13 ± 0.13 88.68±0.00 ± 0.00 38.51±0.04 ± 0.04 17.38±0.24 ± 0.24 29.02±0.00 ± 0.00 12.57±0.05 ± 0.05 4.78±0.02 ± 0.02 17.15±0.00 ± 0.00 39.59 3.20 3.5. Connection to Prior-Data Fitted Networks The prior-fitted clustering objective is not merely a convenient training recipe; it has a precise Bayesian interpretation that places OFAG within the PFN framework (Müller et al., 2022; Müller et al., 2025). Proposition 0 (OFAG as a Prior-Data Fitted Network). Minimizing (A,X,y)∼p()[ℒcomp(θ,A,X,y)]E_(A,X,y) p(D)[L_comp(θ;A,X,y)] is equivalent to minimizing the Prior-Data Negative Log-Likelihood of a Bayesian model with prior p()p(D) and a vMF mixture likelihood, with empty context c=∅D_c= . Consequently, a sufficiently expressive OFAG trained to convergence approximates the posterior predictive distribution induced by p()p(D). Proof sketch. With c=∅D_c= and all nodes as query points, the Prior-Data NLL equals [−1N∑ilogqθ(yi∣zi)]=[ℒcomp]E [- 1N _i q_θ(y_i z_i) ]=E[L_comp], where qθ(yi∣zi)q_θ(y_i z_i) is the vMF posterior from Proposition 3. By (Müller et al., 2022; Müller et al., 2025), minimizing the Prior-Data NLL is equivalent to minimizing the expected KL divergence between qθq_θ and the true posterior predictive distribution. The full proof is in Appendix E. ∎ The dispersion term ℒdispL_disp is a geometric regularizer preventing prototype collapse; it does not affect the PFN interpretation of ℒcompL_comp. Together, Propositions 3 and 4 establish that OFAG’s training objective is grounded in both probabilistic generative modeling (vMF mixture MLE) and Bayesian inference theory (Prior-Data NLL minimization). 3.6. Zero-Shot Inference After pre-training, all parameters are frozen. Given an unseen attributed graph (A,X)(A,X), OFAG produces node embeddings in a single forward pass, (13) Z=SwiFRTθ∗(X,A),zi=Zi,:/∥Zi,:∥2,Z=SwiFRT_θ (X,A), z_i=Z_i,:/\|Z_i,:\|_2, which are then clustered by a standard algorithm such as k-means. No gradient updates, graph-specific training, or validation labels are required. The entire burden of learning how to combine attribute and structural evidence across diverse feature types, structural regimes, and cluster configurations is absorbed by prior fitting. At inference, OFAG follows a pure foundation-model workflow: pre-train once, freeze, and apply to any new graph. Table 2. Wall-clock clustering time on benchmark datasets. Following PyAGC, all methods are evaluated on a single NVIDIA Tesla V100 GPU with 32GB memory. Cora and Photo are reported in seconds, while the remaining datasets and total time are reported in minutes. Lower is better. The † mark indicates that OFAG is run on CPU due to GPU out-of-memory. Method Cora (s) Photo (s) HM (m) Flickr (m) ArXiv (m) Reddit (m) MAG (m) Pokec (m) Products (m) WebTopic (m) Total (m) Mean NMI Node2Vec 24.57 27.96 1.50 20.97 5.05 22.67 77.58 236.53 64.94 75.92 506.04 36.87 DAEGC 35.80 156.84 1.10 4.87 9.06 14.28 27.52 14.28 37.28 11.11 122.71 25.36 DinkNet 13.31 36.07 0.14 1.40 3.72 4.49 5.46 6.18 85.27 4.27 111.75 31.54 MinCut 5.51 6.78 5.11 0.34 1.00 6.73 16.01 24.15 32.55 8.37 94.46 29.19 DMoN 3.58 6.99 5.08 0.34 1.37 1.22 15.46 22.91 22.88 6.75 76.19 30.05 Neuromap 4.73 12.89 5.17 0.47 1.62 6.73 14.56 23.07 23.00 4.97 79.88 30.22 GAE 32.03 178.93 0.81 2.56 12.77 30.58 26.54 10.16 26.12 6.18 119.24 30.54 DGI 15.50 11.14 0.54 1.12 2.76 1.93 10.54 10.37 50.32 6.16 84.18 34.85 CCASSG 0.46 27.92 0.18 0.09 3.04 1.21 31.14 117.43 45.16 122.30 321.02 33.06 S3GC 124.74 148.44 0.98 15.49 3.91 32.38 41.78 71.17 29.68 145.98 345.92 38.08 MAGI 51.25 18.68 41.84 43.31 28.80 56.98 86.99 176.43 375.99 115.36 926.87 36.82 NS4GC 9.77 64.36 4.47 0.85 22.94 12.84 41.04 55.88 37.24 30.75 207.25 37.21 OFAG 0.40 1.65 0.05 0.05 0.12 0.42 0.96 1.11† 6.21† 3.47† 12.43 39.49 4. Experiments 4.1. Experimental Setup Datasets. We evaluate OFAG following the protocol of PyAGC (Liu et al., 2026e) on ten benchmark datasets spanning citation, co-purchase, social, and web domains: Cora, Photo, HM, Flickr, ArXiv, Reddit, MAG, Pokec, Products, and WebTopic (Bechler-Speicher et al., 2025; Hu et al., 2020; Bazhenov et al., 2025). The benchmark covers diverse graph scales, feature modalities, and homophily levels, with 5 homophilous and 5 heterophilous graphs. Detailed dataset statistics and descriptions are provided in Appendix F. Baselines. We compare against 16 methods spanning traditional clustering, deep decoupled clustering, and deep joint clustering: KMeans (McQueen, 1967), Node2Vec (Grover and Leskovec, 2016), SSGC (Zhu and Koniusz, 2020), SAGSC (Fettal et al., 2023), MS2CAG (Lin et al., 2025), GAE (Kipf and Welling, 2016), DGI (Veličković et al., 2019), CCASSG (Zhang et al., 2021), S3GC (Devvrit et al., 2022), NS4GC (Liu et al., 2024c), MAGI (Liu et al., 2024b), DAEGC (Wang et al., 2019), DinkNet (Liu et al., 2023b), MinCut (Bianchi et al., 2020), DMoN (Tsitsulin et al., 2023), and Neuromap (Blöcker et al., 2024). We follow the official PyAGC implementations and evaluation settings; details are in Appendix G. Metrics. We report NMI, ARI, ACC, and Macro-F1, averaged over 5 runs with different seeds, and wall-clock running time. For baselines, running time covers on-graph learning plus clustering; for OFAG, it covers only zero-shot inference (frozen forward pass and k-means), excluding the one-time pre-training cost. Implementation. OFAG is pre-trained once on 80,000 synthetic graphs (batch size 8, 10,000 steps) using AdamW (lr 10−410^-4, wd 10−410^-4), taking ≈1.5≈ 1.5 hours on a single NVIDIA A800 40G GPU. The SwiFRT hidden dimension is 8, num_heads=4, filter order L=10L=10, temperature τ=1.0τ=1.0, and dispersion weight λ=0.1λ=0.1. A fixed set of 16 synthetic graphs is held out as a validation set to monitor pre-training; the checkpoint with the lowest validation loss is selected. At inference time, all parameters are frozen: OFAG performs a single forward pass followed by k-means, with no graph-specific training, fine-tuning, or hyperparameter search on any benchmark dataset. Our code is available at https://github.com/Cloudy1225/OFAG. More implementation and evaluation details are in Appendix H. 4.2. Performance Comparison Overall performance. Tables 1 and 4 report clustering performance across all ten datasets. OFAG achieves the best mean score on all four metrics (NMI 39.49, ACC 39.59, ARI 26.94, F1 33.54) and the lowest average rank on every metric, demonstrating consistent superiority rather than gains concentrated on a few datasets. The next-best methods on mean NMI and F1 are SAGSC (38.47, 32.36) and S3GC (37.70 ACC, 26.06 ARI), both of which require full per-graph optimization; OFAG surpasses them by a larger margin on mean scores than the gap between any two consecutive dataset-specific methods. Crucially, this is achieved by a single frozen model performing zero-shot inference without any graph-specific training, fine-tuning, or hyperparameter search. Homophilous graphs. OFAG is strongest on Reddit, leading all methods by a wide margin (NMI 85.94 vs. S3GC 83.45; F1 81.17 vs. SAGSC 70.43); the +10.7+10.7 F1 gap suggests that the CAGM prior’s diverse cluster-proportion sampling is especially beneficial for Reddit’s imbalanced community structure. On Cora, Photo, and ArXiv, OFAG ranks second or third, trailing specialized baselines by 2–4 NMI points, a modest gap attributable to dataset-specific optimization advantages that zero-shot inference cannot replicate. Heterophilous graphs. OFAG shows clear advantages where smoothing-based methods degrade. It ranks first on Flickr (NMI 9.27, F1 23.89), MAG (NMI 41.78, F1 10.28), and WebTopic (ACC 17.15), consistent with its pre-training on a comprehensive homophily spectrum that prevents over-reliance on edge propagation. On HM and Pokec, OFAG does not rank in the top three on most metrics. This may be because both datasets are dense tabular graphs with many fine-grained clusters and attribute-structure correlations that diverge from typical prior conditions, where per-graph hyperparameter tuning provides a non-trivial advantage. 4.3. Efficiency Comparison Table 2 jointly reports wall-clock running times and Mean NMI, enabling a direct quality-vs.-cost comparison. OFAG is simultaneously the fastest and the most accurate method: it achieves the best Mean NMI (39.49) while completing all ten datasets in only 12.43 minutes total. The next fastest baseline is DMoN (76.19 minutes, 6.1×6.1× slower) with a Mean NMI of only 30.05; the second-best on NMI is S3GC (38.08) at 345.92 minutes, 27.8×27.8× slower than OFAG. This reveals a sharp Pareto gap: no dataset-specific method comes close to the quality of OFAG at anywhere near its speed. The most extreme case is MAGI (926.87 minutes, 74.6×74.6× slower) which achieves only 36.82 Mean NMI, worse than OFAG by 2.67 points. The efficiency advantage is most pronounced on individual large graphs: on ArXiv, OFAG finishes in 0.12 minutes while NS4GC, the best-performing baseline on that dataset, requires 22.94 minutes (191×191× slower) yet scores lower on average NMI. This gap widens further when accounting for hyperparameter tuning: dataset-specific methods must be tuned on each target graph without labels, often requiring tens of repeated runs, pushing practical speedups to the thousand-fold level. OFAG avoids this cost entirely: its inference consists of a single forward pass followed by k-means, with no per-graph adaptation of any kind. For the three largest datasets (Pokec, Products, WebTopic), OFAG runs on CPU due to GPU memory constraints, yet still finishes faster than all GPU-accelerated baselines in total, further underscoring the practical scalability of prior-fitted inference. A formal time complexity analysis of OFAG is provided in Appendix J. 4.4. Ablation: Model Components Table 3 ablates five design choices grouped into three categories: synthetic prior, backbone encoder, and training objective. Prior. Including mixed attribute types (binary, categorical, count-valued) in CAGM yields consistent gains on both homophilous and heterophilous splits, confirming that broader coverage over real-world feature modalities improves zero-shot generalization. Covering the full homophily spectrum (h∈[0.1,0.9]h\!∈\![0.1,0.9]) is similarly important: it equips the model with an adaptive aggregation strategy rather than a fixed smoothing bias, benefiting heterophilous graphs the most. More prior ablations are provided in Appendix I.4. Backbone. The Transformer fusion in SwiFRT is essential for heterophilous graphs (+2.71+2.71 NMI over the MLP variant), where diffusion responses are non-monotone across orders and cross-order interactions must be explicitly modeled. ℓ2 _2 normalization contributes the largest single gain in the entire table: projecting node embeddings onto the unit hypersphere removes scale variation across graphs and feature dimensions, producing a geometry in which k-means cluster boundaries are well-calibrated. Objective. ℒdispL_disp provides a clear benefit, particularly on heterophilous benchmarks (+2.01+2.01 NMI). As formalized in Remarks 1–2, it drives prototypes toward an equiangular tight frame, maximizing inter-cluster angular separation across the hypersphere. This geometric regularization is most consequential when the compactness signal is weaker—precisely the regime of heterophilous graphs where attribute-structure agreement is limited and inter-prototype spacing must compensate. Table 3. Component ablation. Average NMI/ACC over the five homophilous (Homo), five heterophilous (Hetero), and all ten graphs (All). Variant Homo Avg Hetero Avg All Avg NMI ACC NMI ACC NMI ACC OFAG (full) 62.46 63.01 16.51 16.18 39.49 39.59 Continuous features only 62.02 62.35 16.12 15.83 39.07 39.09 Homophilous graphs only 61.46 59.24 15.65 15.22 38.56 37.23 gθg_θ: Transformer → MLP 60.24 59.41 13.80 14.32 37.02 36.86 w/o ℓ2 _2 normalization 54.72 48.70 14.10 15.27 34.41 31.98 w/o dispersion ℒdispL_disp 61.40 59.54 14.50 14.54 37.95 37.04 4.5. Pre-training Dynamics Figure 2 shows the validation loss and NMI evaluated every 50 steps on a fixed set of 16 synthetic graphs throughout pre-training. Both curves share a consistent two-phase pattern: a steep improvement in the first ∼ 1,000 steps, followed by a gradual plateau that persists for the remainder of training. The monotonically increasing NMI directly reflects that the quality of the learned representations improves over training: the model continuously discovers new structural and attributive patterns in the synthetic prior, yielding progressively better cluster separability. The validation loss decreases in tandem, confirming that the pre-training objective faithfully drives clustering quality rather than reducing a decoupled surrogate. After the initial rapid gains, both metrics stabilize with only low-amplitude fluctuations, indicating that the model has reached a stable convergence point rather than continuing to overfit or drift. Together, these dynamics confirm that the CAGM prior provides a sufficiently diverse and well-structured training signal for the model to learn meaningful clustering representations, laying the foundation for the strong zero-shot performance observed on real-world graphs in Section 4.2. We further evaluate different pre-training checkpoints directly on the benchmark graphs; Figure 5 shows the NMI trajectories on homophilous, heterophilous, and all ten graphs, with detailed analysis provided in Appendix I.1. Figure 2. Validation loss and NMI on the fixed synthetic validation set evaluated every 50 steps during pre-training. 4.6. Representation Visualization To qualitatively assess what OFAG learns, we visualize node representations on the Photo dataset. We run a single frozen forward pass to obtain the hyperspherical node embeddings, project them to 2S^2 via PCA followed by re-normalization, and render the resulting 3D unit-sphere plot; Figure 3 shows the raw node features and the OFAG embeddings side by side. The raw features (Figure 3, left), when projected onto the sphere, form a diffuse, largely undifferentiated cloud with no visible cluster organization. In contrast, the OFAG embeddings (Figure 3, right) exhibit well-separated, compact clusters distributed across the sphere surface. This geometric reorganization is entirely zero-shot: the model has never observed Photo during pre-training, yet its encoder maps nodes from different categories into distinct hyperspherical regions. The result provides direct visual evidence that pre-training on the CAGM prior instills a general inductive bias toward cluster-discriminative geometry, enabling the model to transfer structured representations to unseen real-world graphs without any task-specific adaptation. Figure 3. 3D unit-sphere visualization of node representations on the Photo dataset, obtained by PCA projection and re-normalization. Left: raw node features are scattered uniformly with no discernible cluster structure. Right: OFAG embeddings form compact, well-separated clusters. Additional Results. Please kindly see the appendix for more analyses: Appendix I.1 analyzes how clustering quality on real graphs evolves across pre-training checkpoints; Appendices I.2 and I.3 examine sensitivity to the filter order and dispersion weight; Appendix I.4 ablates the homophily coverage of the structural prior; and Appendix J provides a formal time complexity analysis. 5. Conclusion We presented OFAG, the first one-for-all foundation model for attributed graph clustering. By adapting the Prior-data Fitted Network paradigm to the unsupervised graph setting, OFAG is pre-trained once on synthetic graphs sampled from the CAGM prior and applied to arbitrary real-world graphs in a single forward pass. Experiments on ten datasets show that a single frozen OFAG model achieves the best mean performance while being the fastest method overall. References Banerjee et al. (2005) A. Banerjee, I. S. Dhillon, J. Ghosh, S. Sra, and G. Ridgeway Clustering on the unit hypersphere using von mises-fisher distributions.. Journal of Machine Learning Research 6 (9). Cited by: §1, §3.4. Bazhenov et al. (2025) G. Bazhenov, O. Platonov, and L. Prokhorenkova GraphLand: evaluating graph machine learning models on diverse industrial data. In The Thirty-ninth Annual Conference on Neural Information Processing Systems Datasets and Benchmarks Track, Cited by: §F.2, §F.4, §F.4, §4.1. Bechler-Speicher et al. (2025) M. Bechler-Speicher, B. Finkelshtein, F. Frasca, L. Müller, J. Tönshoff, A. Siraudin, V. Zaverkin, M. M. Bronstein, M. Niepert, B. Perozzi, M. Galkin, and C. Morris Position: graph learning will lose relevance due to poor benchmarks. In Forty-second International Conference on Machine Learning Position Paper Track, Cited by: §4.1. Bianchi et al. (2020) F. M. Bianchi, D. Grattarola, and C. Alippi Spectral clustering with graph neural networks for graph pooling. In International conference on machine learning, p. 874–883. Cited by: 3rd item, §4.1. Blöcker et al. (2024) C. Blöcker, C. Tan, and I. Scholtes The map equation goes neural: mapping network flows with graph neural networks. Advances in Neural Information Processing Systems 37, p. 17428–17456. Cited by: 5th item, §2.1, §4.1. Caron et al. (2020) M. Caron, I. Misra, J. Mairal, P. Goyal, P. Bojanowski, and A. Joulin Unsupervised learning of visual features by contrasting cluster assignments. In Advances in Neural Information Processing Systems, p. 9912–9924. Cited by: §3.4. Choi et al. (2026) J. Choi, J. Kim, W. Kang, and N. Park Learning posterior predictive distributions for node classification from synthetic graph priors. In The Fourteenth International Conference on Learning Representations, Cited by: §1, §2.2, §2.3. Devvrit et al. (2022) F. Devvrit, A. Sinha, I. Dhillon, and P. Jain S3GC: scalable self-supervised graph clustering. Advances in Neural Information Processing Systems 35, p. 3248–3261. Cited by: 4th item, §2.1, §4.1. Dooley et al. (2023) S. Dooley, G. S. Khurana, C. Mohapatra, S. V. Naidu, and C. White Forecastpfn: synthetically-trained zero-shot forecasting. Advances in Neural Information Processing Systems 36, p. 2403–2426. Cited by: §2.3. Eremeev et al. (2025) D. Eremeev, G. Bazhenov, O. Platonov, A. Babenko, and L. Prokhorenkova Turning tabular foundation models into graph foundation models. arXiv preprint arXiv:2508.20906. Cited by: §2.2. Eremeev et al. (2026) D. Eremeev, O. Platonov, G. Bazhenov, A. Babenko, and L. Prokhorenkova GraphPFN: a prior-data fitted graph foundation model. In Forty-third International Conference on Machine Learning, Cited by: §1, §2.2, §2.3. Fettal et al. (2023) C. Fettal, L. Labiod, and M. Nadif Scalable attributed-graph subspace clustering. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 37, p. 7559–7567. Cited by: 4th item, §2.1, §4.1. Finkelshtein et al. (2026) B. Finkelshtein, I. I. Ceylan, M. M. Bronstein, and R. Levie Equivariance everywhere all at once: a recipe for graph foundation models. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, Cited by: §2.2. Grover and Leskovec (2016) A. Grover and J. Leskovec Node2vec: scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, p. 855–864. Cited by: 2nd item, §4.1. Hamilton et al. (2017) W. Hamilton, Z. Ying, and J. Leskovec Inductive representation learning on large graphs. Advances in neural information processing systems 30. Cited by: §F.3. He et al. (2025) Y. He, Y. Sui, X. He, and B. Hooi UniGraph: learning a unified cross-domain foundation model for text-attributed graphs. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 1, p. 448–459. Cited by: §2.2. Hollmann et al. (2023) N. Hollmann, S. Müller, K. Eggensperger, and F. Hutter TabPFN: a transformer that solves small tabular classification problems in a second. In The Eleventh International Conference on Learning Representations, Cited by: §2.3. Hollmann et al. (2025) N. Hollmann, S. Müller, L. Purucker, A. Krishnakumar, M. Körfer, S. B. Hoo, R. T. Schirrmeister, and F. Hutter Accurate predictions on small data with a tabular foundation model. Nature 637 (8045), p. 319–326. Cited by: §1, §2.2, §2.3. Hu et al. (2020) W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovec Open graph benchmark: datasets for machine learning on graphs. Advances in neural information processing systems 33, p. 22118–22133. Cited by: §F.3, §F.3, §F.4, §4.1. Ju et al. (2026) W. Ju, S. Yi, K. Zheng, Y. Wang, Z. Qiao, L. Shen, Y. Zhou, X. Cao, and J. Lv Compactness and consistency: a conjoint framework for deep graph clustering. In The Fourteenth International Conference on Learning Representations, Cited by: §2.1. Kipf and Welling (2016) T. N. Kipf and M. Welling Variational graph auto-encoders. arXiv preprint arXiv:1611.07308. Cited by: 1st item, §2.1, §4.1. Kipf and Welling (2017) T. N. Kipf and M. Welling Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, Cited by: §F.1, §2.1, §3.3. Kong et al. (2025) L. Kong, J. Feng, H. Liu, C. Huang, J. Huang, Y. Chen, and M. Zhang Gofa: a generative one-for-all model for joint graph language modeling. In International Conference on Learning Representations, Vol. 2025, p. 40792–40823. Cited by: §1, §2.2. Li et al. (2024) Y. Li, P. Wang, Z. Li, J. X. Yu, and J. Li Zerog: investigating cross-dataset zero-shot transferability in graphs. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, p. 1725–1735. Cited by: §2.2. Lin et al. (2025) X. Lin, R. Yang, H. Zheng, and X. Ke Spectral subspace clustering for attributed graphs. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 1, p. 789–799. Cited by: 5th item, §2.1, §4.1. Liu et al. (2024a) H. Liu, J. Feng, L. Kong, N. Liang, D. Tao, Y. Chen, and M. Zhang One for all: towards training one graph model for all classification tasks. In International conference on learning representations, Vol. 2024, p. 20188–20210. Cited by: §1, §2.2. Liu et al. (2025a) J. Liu, C. Yang, Z. Lu, J. Chen, Y. Li, M. Zhang, T. Bai, Y. Fang, L. Sun, P. S. Yu, and C. Shi Graph foundation models: concepts, opportunities and challenges. IEEE Transactions on Pattern Analysis and Machine Intelligence, p. 5023–5044. Cited by: §1, §1, §2.2. Liu et al. (2023a) Y. Liu, M. Jin, S. Pan, C. Zhou, Y. Zheng, F. Xia, and P. S. Yu Graph self-supervised learning: a survey. IEEE Transactions on Knowledge and Data Engineering 35 (6), p. 5879–5900. Cited by: §2.1. Liu et al. (2023b) Y. Liu, K. Liang, J. Xia, S. Zhou, X. Yang, X. Liu, and S. Z. Li Dink-net: neural clustering on large graphs. In International conference on machine learning, p. 21794–21812. Cited by: 2nd item, §2.1, §4.1. Liu et al. (2022) Y. Liu, W. Tu, S. Zhou, X. Liu, L. Song, X. Yang, and E. Zhu Deep graph clustering via dual correlation reduction. In Proceedings of the AAAI conference on artificial intelligence, Vol. 36, p. 7603–7611. Cited by: §2.1. Liu et al. (2026a) Y. Liu, J. Xia, B. Wu, S. Zhou, X. Yang, K. Liang, C. Fan, Y. Zhuang, G. Yu, S. Z. Li, et al. A survey of deep graph clustering: taxonomy, challenge, application, and open resource. IEEE Transactions on Knowledge and Data Engineering. Cited by: §1. Liu et al. (2024b) Y. Liu, J. Li, Y. Chen, R. Wu, E. Wang, J. Zhou, S. Tian, S. Shen, X. Fu, C. Meng, et al. Revisiting modularity maximization for graph clustering: a contrastive learning perspective. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, p. 1968–1979. Cited by: 6th item, §4.1. Liu et al. (2024c) Y. Liu, X. Gao, T. He, T. Zheng, J. Zhao, and H. Yin Reliable node similarity matrix guided contrastive graph clustering. IEEE Transactions on Knowledge and Data Engineering. Cited by: 5th item, §2.1, §4.1. Liu et al. (2026b) Y. Liu, T. He, Y. Liu, C. Yi, H. Jin, and C. Hong Tabular foundation models are strong graph anomaly detectors. In Proceedings of the ACM Web Conference 2026, p. 8785–8788. Cited by: §2.2. Liu et al. (2024d) Y. Liu, T. He, Q. Wu, T. Zheng, and J. Zhao Scalable and adaptive spectral embedding for attributed graph clustering. In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, p. 3912–3916. Cited by: §2.1. Liu et al. (2025b) Y. Liu, T. He, T. Zheng, and J. Zhao Negative-free self-supervised gaussian embedding of graphs. Neural Networks 181, p. 106846. Cited by: §2.1. Liu et al. (2026c) Y. Liu, Y. Liu, Y. Chen, C. Hong, T. Zheng, and T. He Learning hierarchical knowledge in text-rich networks with taxonomy-informed representation learning. In Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 1, p. 961–972. Cited by: §2.1. Liu et al. (2026d) Y. Liu, Y. Liu, Y. Liu, T. Zheng, S. Z. Li, X. Liu, and T. He Beyond the academic monoculture: a unified framework and industrial perspective for attributed graph clustering. arXiv preprint arXiv:2603.20829. Cited by: §1, §2.1. Liu et al. (2026e) Y. Liu, P. Qiu, Y. Xing, Y. Liu, P. Du, C. Hong, J. Zheng, T. Zheng, and T. He Bridging academia and industry: a comprehensive benchmark for attributed graph clustering. arXiv preprint arXiv:2602.08519. Cited by: Appendix G, §4.1. Liu et al. (2024e) Y. Liu, H. Zhang, T. He, T. Zheng, and J. Zhao Bootstrap latents of nodes and neighbors for graph self-supervised learning. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, Cited by: §2.1. Mao et al. (2024) H. Mao, Z. Chen, W. Tang, J. Zhao, Y. Ma, T. Zhao, N. Shah, M. Galkin, and J. Tang Position: graph foundation models are already here. In Forty-first International Conference on Machine Learning, Cited by: §1. McQueen (1967) J. B. McQueen Some methods of classification and analysis of multivariate observations. In Proc. of 5th Berkeley Symposium on Math. Stat. and Prob., p. 281–297. Cited by: 1st item, §4.1. Müller et al. (2022) S. Müller, N. Hollmann, S. P. Arango, J. Grabocka, and F. Hutter Transformers can do bayesian inference. In International Conference on Learning Representations, Cited by: Appendix E, Appendix E, §2.3, §3.5, §3.5. Müller et al. (2025) S. Müller, A. Reuter, N. Hollmann, D. Rügamer, and F. Hutter Position: the future of bayesian prediction is prior-fitted. In Forty-second International Conference on Machine Learning Position Paper Track, Cited by: Appendix E, §1, §2.2, §2.3, §3.5, §3.5. Ortega et al. (2018) A. Ortega, P. Frossard, J. Kovačević, J. M. Moura, and P. Vandergheynst Graph signal processing: overview, challenges, and applications. Proceedings of the IEEE 106 (5), p. 808–828. Cited by: §1, §3.3. Qiao et al. (2025) H. Qiao, C. Niu, L. Chen, and G. Pang Anomalygfm: graph foundation model for zero/few-shot anomaly detection. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 2, p. 2326–2337. Cited by: §1, §2.2. Shchur et al. (2018) O. Shchur, M. Mumme, A. Bojchevski, and S. Günnemann Pitfalls of graph neural network evaluation. ArXiv abs/1811.05868. Cited by: §F.1. Sun et al. (2025) Y. Sun, Y. Yang, X. Feng, Z. Wang, H. Zhong, C. Wang, and L. Chen Handling feature heterogeneity with learnable graph patches. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 1, p. 1313–1324. Cited by: §2.2. Tang et al. (2024) J. Tang, Y. Yang, W. Wei, L. Shi, L. Su, S. Cheng, D. Yin, and C. Huang Graphgpt: graph instruction tuning for large language models. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, p. 491–500. Cited by: §1, §2.2. Tsitsulin et al. (2023) A. Tsitsulin, J. Palowitch, B. Perozzi, and E. Müller Graph clustering with graph neural networks. Journal of Machine Learning Research 24 (127), p. 1–21. Cited by: 4th item, §2.1, §4.1. Vaswani et al. (2017) A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin Attention is all you need. Advances in neural information processing systems 30. Cited by: §3.3. Veličković et al. (2019) P. Veličković, W. Fedus, W. L. Hamilton, P. Liò, Y. Bengio, and R. D. Hjelm Deep graph infomax. In International Conference on Learning Representations, Cited by: 2nd item, §4.1. Wang et al. (2019) C. Wang, S. Pan, R. Hu, G. Long, J. Jiang, and C. Zhang Attributed graph clustering: a deep attentional embedding approach. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAI’19, p. 3670–3676. Cited by: 1st item, §2.1, §4.1. Wang et al. (2025) Z. Wang, C. Zhang, J. Li, N. Chawla, and Y. Ye Graph foundation models: challenges, methods, and open questions. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 2, p. 6184–6194. Cited by: §1, §1, §2.2. Wu et al. (2025a) B. Wu, Y. Liu, Q. Tan, X. Liu, W. Du, J. Wang, and G. Yu DGCBench: a deep graph clustering benchmark. In The Thirty-ninth Annual Conference on Neural Information Processing Systems Datasets and Benchmarks Track, Cited by: §3.4. Wu et al. (2025b) Y. Wu, G. Lu, Y. Zuo, H. Zhang, and J. Wu GRAPH-r1: incentivizing the zero-shot graph learning capability in llms via explicit reasoning. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, p. 23920–23938. Cited by: §2.2. Xie et al. (2016) J. Xie, R. Girshick, and A. Farhadi Unsupervised deep embedding for clustering analysis. In International conference on machine learning, p. 478–487. Cited by: §2.1. Xie et al. (2025) K. Xie, R. Yang, and S. Wang Diffusion-based graph-agnostic clustering. In Proceedings of the ACM on Web Conference 2025, p. 1353–1364. Cited by: §2.1. Xie et al. (2026) S. Xie, V. Feofanov, J. Zhang, T. Palpanas, and I. Redko CauKer: classification time series foundation models can be pretrained on synthetic data. In The Fourteenth International Conference on Learning Representations, Cited by: §2.3. Yu et al. (2025) X. Yu, Z. Gong, C. Zhou, Y. Fang, and H. Zhang Samgpt: text-free graph foundation model for multi-domain pre-training and cross-domain adaptation. In Proceedings of the ACM on Web Conference 2025, p. 1142–1153. Cited by: §1, §2.2. Zeng et al. (2020) H. Zeng, H. Zhou, A. Srivastava, R. Kannan, and V. Prasanna GraphSAINT: graph sampling based inductive learning method. In International Conference on Learning Representations, Cited by: §F.2. Zhang et al. (2021) H. Zhang, Q. Wu, J. Yan, D. Wipf, and P. S. Yu From canonical correlation analysis to self-supervised graph neural networks. In Advances in Neural Information Processing Systems, Vol. 34, p. 76–89. Cited by: 3rd item, §2.1, §4.1. Zhang et al. (2019) X. Zhang, H. Liu, Q. Li, and X. Wu Attributed graph clustering via adaptive graph convolution. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, p. 4327–4333. Cited by: §2.1. Zhao et al. (2024) H. Zhao, A. Chen, X. Sun, H. Cheng, and J. Li All in one and one for all: a simple yet effective method towards cross-domain graph pretraining. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, p. 4443–4454. Cited by: §1, §2.2. Zhao et al. (2025) J. Zhao, Z. Zhu, M. Galkin, H. Mostafa, M. M. Bronstein, and J. Tang Fully-inductive node classification on arbitrary graphs. In The Thirteenth International Conference on Learning Representations, Cited by: §1, §2.2. Zheng et al. (2026) H. Zheng, R. Yang, H. Wang, and J. Xu Cross-contrastive clustering for multimodal attributed graphs with dual graph filtering. In Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 1, p. 2020–2030. Cited by: §2.1. Zhu and Koniusz (2020) H. Zhu and P. Koniusz Simple spectral graph convolution. In International conference on learning representations, Cited by: 3rd item, §3.3, §4.1. Ethics and Privacy Statement This work proposes OFAG, a foundation model for unsupervised attributed graph clustering. All benchmark datasets used in our experiments are publicly available and have been widely adopted in prior graph learning research; no new personal data was collected, and no human subjects were involved. The pre-training data consists entirely of synthetic graphs sampled from the CAGM generative prior, which does not contain or encode any personal information. The primary societal benefit of this work is efficiency: by eliminating per-graph model training and hyperparameter tuning, OFAG reduces the computational cost of graph clustering by orders of magnitude, lowering the barrier to deploying unsupervised graph analysis in resource-constrained settings. As with any clustering method, downstream applications that group individuals (e.g., user segmentation or community detection in social networks) carry inherent fairness risks, since unsupervised partitions can reflect and amplify demographic biases present in the underlying graph structure and node attributes. We encourage practitioners to audit clustering outputs for disparate impact before using them in high-stakes decisions. Appendix Overview Appendix A: Details of the Synthetic Attributed Graph Prior Appendix B: Proof of Theorem 1 (Synthetic-to-Real Generalization) Appendix C: Proof of Proposition 1 (Dimension-Agnosticism and Feature-Permutation Equivariance) Appendix D: Proof of Proposition 2 (Compactness Loss as vMF MLE) Appendix E: Proof of Proposition 3 (OFAG as a Prior-Data Fitted Network) Appendix F: Dataset Details Appendix G: Baseline Details Appendix H: Implementation and Evaluation Details Appendix I.1: Pre-training Dynamics on Benchmark Graphs Appendix I.2: Additional Experiments: Sensitivity to Filter Order L Appendix I.3: Additional Experiments: Sensitivity to Dispersion Weight λ Appendix I.4: Additional Experiments: Ablation on Homophily Coverage Appendix J: Time Complexity Analysis (a) N=512, E=3,022, K=4, h=0.194 (b) N=640, E=3,856, K=5, h=0.491 (c) N=768, E=4,688, K=8, h=0.589 (d) N=1,024, E=6,360, K=6, h=0.863 Figure 4. Representative synthetic graphs sampled from the CAGM prior, with varying numbers of nodes (N), edges (E), clusters (K), and edge homophily (h). Node colors indicate ground-truth cluster assignments. The four examples span the full structural spectrum: from strongly heterophilous (h=0.194h=0.194, left) through near-neutral (h=0.491h=0.491) and mildly homophilous (h=0.589h=0.589) to strongly homophilous (h=0.863h=0.863, right), illustrating the broad coverage of homophily regimes. Appendix A Details of Synthetic Attributed Graph Prior This appendix describes the synthetic prior used for pre-training OFAG. The purpose of the prior is not to exactly reproduce any single real-world graph family, but to generate a broad collection of attributed graph clustering tasks with diverse attribute distributions, graph structures, cluster imbalances, and modality reliabilities. Figure 4 visualizes four representative synthetic graphs sampled from the CAGM prior, illustrating the diversity in size, cluster count, and structural regime. A.1. Latent Cluster Generation For each synthetic task, we sample the graph size, feature dimension, and number of clusters: (14) N∼p(N),F∼p(F),K∼p(K).N p(N), F p(F), K p(K). We then sample cluster proportions from a Dirichlet distribution: (15) π∼Dirichlet(ηK),yi∼Categorical(π),π ( 1_K), y_i (π), where η controls cluster imbalance. Sampling η from a broad range allows the prior to generate both balanced and highly imbalanced clustering tasks. A.2. Attribute Generation Given cluster assignments, node attributes are generated from cluster-dependent latent variables. For each cluster k, we sample a latent centroid and scale: (16) μk∼(0,I),Σk∼p(Σ). _k (0,I), _k p( ). For a node i assigned to cluster k, we sample (17) hiX|yi=k∼tν(μk,Σk),h_i^X y_i=k t_ν( _k, _k), where tνt_ν denotes a multivariate Student-t distribution. The heavy-tailed distribution introduces outliers and non-Gaussian feature patterns. Observed attributes are generated through a task-specific random decoder: (18) ui=WhiX+b+ϵi,xi=T(ui),u_i=Wh_i^X+b+ _i, x_i=T(u_i), where W, b, and ϵi _i are sampled for each task, and T is a randomly selected observation transform. Depending on the transform, the observed attributes may be continuous, binary, count-valued, categorical, sparse, or mixed-type. We additionally inject irrelevant dimensions, feature noise, random scaling, and missing or sparse entries to increase heterogeneity. The strength of the attribute signal is controlled by an attribute separability variable. By varying the between-cluster distance relative to within-cluster variation, the prior produces tasks where attributes are strongly informative, weakly informative, or nearly uninformative. A.3. Graph Generation Edges are generated conditionally on cluster assignments, degree propensities, latent structural positions, and optional attribute similarity. For i<ji<j, we sample (19) Aij∼Bernoulli(pij),A_ij (p_ij), where (20) logit(pij)=ρ+αθ(θi+θj)+λBByi,yj+λHκ(hiA,hjA)+λXsim(xi,xj). (p_ij)=ρ+ _θ( _i+ _j)+ _BB_y_i,y_j+ _Hκ(h_i^A,h_j^A)+ _Xsim(x_i,x_j). Here, ρ controls global sparsity, θi _i is a node-specific degree propensity, B is a cluster-pair affinity matrix, hiAh_i^A is a latent structural vector, κ(⋅,⋅)κ(·,·) is a structural similarity function, and sim(⋅,⋅)sim(·,·) is an attribute similarity function. The coefficients λB _B, λH _H, and λX _X control how strongly edges depend on cluster identity, latent structural similarity, and observed attribute similarity. To model degree heterogeneity, we sample (21) θi∼(−12σθ2,σθ2),σθ∼p(σθ). _i (- 12 _θ^2, _θ^2 ), _θ p( _θ). This allows the prior to generate graphs with approximately regular degrees as well as graphs with hubs and heavy-tailed degree distributions. A.4. Structural Regimes The block affinity matrix B∈ℝK×KB ^K× K is constructed from a continuously sampled edge homophily level, providing smooth coverage of both homophilous and heterophilous connectivity without committing to discrete hand-crafted regimes. Homophily sampling. For each synthetic task we first draw (22) h∼Uniform(0.1, 0.9),h (0.1,\,0.9), where h is the target edge homophily, defined as the expected fraction of edges connecting nodes of the same cluster. Affinity matrix construction. Given h, the block affinity matrix is constructed as (23) B=R+β(h)IK,β(h)=s⋅logit(h)=s⋅logh1−h,B=R+β(h)\,I_K, β(h)=s·logit(h)=s· \! h1-h, where R∈ℝK×KR ^K× K is a symmetric random matrix with entries Rkl=Rlk∼iid(0,σR2)R_kl=R_lk iid N(0, _R^2), providing heterogeneous off-diagonal affinities across cluster pairs, and s>0s>0 is a global strength hyperparameter. The diagonal shift β(h)IKβ(h)I_K continuously biases intra-cluster connectivity relative to inter-cluster connectivity: • h>0.5h>0.5 (β>0β>0): diagonal entries are boosted, yielding homophilous graphs in which same-cluster edges are more probable. • h<0.5h<0.5 (β<0β<0): diagonal entries are suppressed, yielding heterophilous graphs in which cross-cluster edges are more probable. • h=0.5h=0.5 (β=0β=0): the matrix reduces to the pure random baseline R with no systematic intra/inter-cluster bias. Coverage and rationale. Because logit(h)logit(h) is monotone and unbounded, small changes in h near 0.50.5 produce mild biases while values close to the boundary produce strong homophilous or heterophilous signals, naturally generating a broad and calibrated distribution over structural regimes. This formulation prevents the model from assuming that connected nodes should always belong to the same cluster, and exposes OFAG during pre-training to the full range of real-world homophily levels observed in attributed graph benchmarks. A.5. Modality Reliability Finally, we explicitly vary the reliability of attributes and topology. Some tasks are attribute-dominant, some are structure-dominant, some require combining both modalities, and some contain misleading or weakly informative graph structure. This is implemented by varying the attribute separability, graph signal strength, edge noise, degree heterogeneity, and the coupling coefficients in (20). Through this construction, OFAG is exposed during pre-training to a broad range of attributed graph clustering scenarios. Table 4. Clustering performance in ARI and F1 on homophilous and heterophilous attributed graphs. The best, second-best, and third-best results in each column are highlighted. For Avg. Rank, lower is better; for all other columns, higher is better. Model Metric Homophilous Graphs Heterophilous Graphs Mean Avg. Rank Cora Photo ArXiv Reddit Products HM Flickr MAG Pokec WebTopic KMeans ARI 6.95±2.61 ± 2.61 20.01±1.01 ± 1.01 7.23±0.15 ± 0.15 2.93±0.05 ± 0.05 9.22±0.33 ± 0.33 2.96±0.09 ± 0.09 1.06±0.15 ± 0.15 2.77±0.03 ± 0.03 0.23±0.00 ± 0.00 0.87±0.04 ± 0.04 5.42 16.30 F1 25.99±2.91 ± 2.91 42.68±3.32 ± 3.32 12.97±0.18 ± 0.18 7.25±0.08 ± 0.08 12.77±0.41 ± 0.41 12.50±0.20 ± 0.20 15.16±0.85 ± 0.85 5.71±0.07 ± 0.07 0.98±0.01 ± 0.01 4.64±0.04 ± 0.04 14.06 16.45 Node2Vec ARI 33.61±2.49 ± 2.49 57.11±1.39 ± 1.39 16.69±0.73 ± 0.73 64.34±1.64 ± 1.64 18.53±1.05 ± 1.05 1.84±0.07 ± 0.07 1.52±0.00 ± 0.00 4.75±0.07 ± 0.07 9.27±0.08 ± 0.08 1.53±0.03 ± 0.03 20.92 10.90 F1 61.66±2.52 ± 2.52 69.33±1.18 ± 1.18 20.96±0.29 ± 0.29 68.61±2.12 ± 2.12 25.41±0.24 ± 0.24 11.65±0.46 ± 0.46 19.68±0.01 ± 0.01 8.90±0.09 ± 0.09 12.66±0.15 ± 0.15 7.40±0.16 ± 0.16 30.63 8.70 SSGC ARI 41.25±1.69 ± 1.69 59.17±3.81 ± 3.81 33.04±0.29 ± 0.29 33.61±1.29 ± 1.29 18.84±0.40 ± 0.40 3.18±0.02 ± 0.02 3.29±0.11 ± 0.11 5.84±0.09 ± 0.09 0.42±0.01 ± 0.01 1.75±0.04 ± 0.04 20.04 8.45 F1 65.16±1.32 ± 1.32 70.17±3.78 ± 3.78 25.44±0.59 ± 0.59 29.15±1.33 ± 1.33 24.01±0.71 ± 0.71 14.84±0.13 ± 0.13 18.64±0.48 ± 0.48 9.78±0.05 ± 0.05 1.60±0.03 ± 0.03 5.66±0.04 ± 0.04 26.45 8.50 SAGSC ARI 38.83±0.02 ± 0.02 43.66±0.01 ± 0.01 20.69±0.69 ± 0.69 65.93±1.44 ± 1.44 19.36±0.29 ± 0.29 4.12±0.08 ± 0.08 3.27±0.00 ± 0.00 4.89±0.11 ± 0.11 11.58±0.18 ± 0.18 2.91±0.10 ± 0.10 21.52 8.00 F1 61.03±0.02 ± 0.02 69.40±0.01 ± 0.01 25.37±0.85 ± 0.85 70.43±1.60 ± 1.60 25.56±0.53 ± 0.53 16.08±0.10 ± 0.10 20.97±0.01 ± 0.01 9.67±0.20 ± 0.20 16.12±0.26 ± 0.26 9.00±0.30 ± 0.30 32.36 4.90 MS2CAG ARI 45.76±0.98 ± 0.98 63.88±0.54 ± 0.54 28.84±0.18 ± 0.18 56.56±2.89 ± 2.89 17.97±0.65 ± 0.65 3.50±0.11 ± 0.11 3.84±0.03 ± 0.03 5.16±0.09 ± 0.09 0.42±0.03 ± 0.03 2.36±0.03 ± 0.03 22.83 7.15 F1 69.17±0.65 ± 0.65 74.94±0.95 ± 0.95 24.58±0.50 ± 0.50 55.37±1.78 ± 1.78 24.67±0.31 ± 0.31 12.95±0.27 ± 0.27 21.81±0.03 ± 0.03 9.97±0.14 ± 0.14 1.51±0.02 ± 0.02 8.52±0.07 ± 0.07 30.35 6.40 DAEGC ARI 38.36±2.67 ± 2.67 56.37±0.02 ± 0.02 17.53±0.40 ± 0.40 13.43±1.24 ± 1.24 2.35±0.90 ± 0.90 3.47±0.07 ± 0.07 4.61±0.10 ± 0.10 4.29±0.36 ± 0.36 0.61±0.04 ± 0.04 2.58±0.38 ± 0.38 14.36 10.85 F1 64.54±2.32 ± 2.32 76.26±0.01 ± 0.01 20.64±0.28 ± 0.28 8.23±0.93 ± 0.93 8.02±1.81 ± 1.81 14.73±0.05 ± 0.05 19.24±0.09 ± 0.09 7.25±0.43 ± 0.43 1.73±0.07 ± 0.07 7.34±0.19 ± 0.19 22.80 10.90 DinkNet ARI 52.45±0.41 ± 0.41 53.54±0.23 ± 0.23 14.93±0.50 ± 0.50 33.70±1.24 ± 1.24 13.67±0.40 ± 0.40 2.96±0.03 ± 0.03 1.56±0.33 ± 0.33 5.10±0.04 ± 0.04 0.29±0.02 ± 0.02 1.86±0.25 ± 0.25 18.01 11.85 F1 70.12±0.59 ± 0.59 67.20±0.27 ± 0.27 16.94±0.73 ± 0.73 27.89±0.94 ± 0.94 14.14±0.12 ± 0.12 14.30±0.26 ± 0.26 16.50±0.40 ± 0.40 7.65±0.11 ± 0.11 1.65±0.01 ± 0.01 5.71±0.10 ± 0.10 24.21 12.40 MinCut ARI 28.60±2.86 ± 2.86 50.99±2.33 ± 2.33 17.47±0.98 ± 0.98 25.42±1.67 ± 1.67 10.64±0.32 ± 0.32 1.22±0.30 ± 0.30 3.73±0.66 ± 0.66 5.56±0.15 ± 0.15 0.61±0.04 ± 0.04 2.00±0.20 ± 0.20 14.62 12.65 F1 51.88±6.97 ± 6.97 66.99±2.97 ± 2.97 21.85±0.73 ± 0.73 26.39±5.74 ± 5.74 17.53±0.54 ± 0.54 9.54±0.68 ± 0.68 21.22±1.17 ± 1.17 8.04±0.12 ± 0.12 2.30±0.05 ± 0.05 6.92±0.46 ± 0.46 23.27 12.00 DMoN ARI 33.35±3.35 ± 3.35 51.55±2.41 ± 2.41 15.44±0.37 ± 0.37 32.39±1.40 ± 1.40 10.93±0.41 ± 0.41 2.05±0.28 ± 0.28 5.01±0.52 ± 0.52 4.93±0.02 ± 0.02 1.17±0.04 ± 0.04 2.43±0.21 ± 0.21 15.93 11.30 F1 49.57±3.84 ± 3.84 70.86±2.44 ± 2.44 20.37±0.61 ± 0.61 26.52±0.76 ± 0.76 16.43±1.13 ± 1.13 10.58±0.44 ± 0.44 22.76±0.48 ± 0.48 8.97±0.14 ± 0.14 3.04±0.04 ± 0.04 7.80±0.21 ± 0.21 23.69 9.95 Neuromap ARI 36.69±3.25 ± 3.25 53.01±3.67 ± 3.67 21.92±1.08 ± 1.08 25.32±0.26 ± 0.26 16.52±1.56 ± 1.56 1.45±0.07 ± 0.07 4.99±1.28 ± 1.28 9.85±0.36 ± 0.36 1.84±0.11 ± 0.11 3.31±0.56 ± 0.56 17.49 8.50 F1 54.69±3.95 ± 3.95 69.13±3.76 ± 3.76 21.29±0.84 ± 0.84 25.70±0.43 ± 0.43 13.09±1.04 ± 1.04 9.37±0.18 ± 0.18 22.39±1.57 ± 1.57 6.20±0.19 ± 0.19 2.62±0.14 ± 0.14 7.96±0.39 ± 0.39 23.24 11.80 GAE ARI 45.63±0.15 ± 0.15 52.39±0.12 ± 0.12 15.95±0.40 ± 0.40 27.88±0.46 ± 0.46 14.49±0.25 ± 0.25 4.21±0.23 ± 0.23 5.53±0.30 ± 0.30 5.34±0.08 ± 0.08 0.34±0.01 ± 0.01 1.98±0.06 ± 0.06 17.37 9.90 F1 64.48±0.11 ± 0.11 67.52±0.09 ± 0.09 18.57±0.22 ± 0.22 26.89±0.50 ± 0.50 18.35±0.47 ± 0.47 15.20±0.22 ± 0.22 18.83±0.13 ± 0.13 8.97±0.09 ± 0.09 1.53±0.02 ± 0.02 5.81±0.14 ± 0.14 24.61 11.25 DGI ARI 52.03±3.22 ± 3.22 58.38±0.46 ± 0.46 22.77±0.28 ± 0.28 59.28±0.54 ± 0.54 14.67±0.21 ± 0.21 3.11±0.06 ± 0.06 4.98±0.01 ± 0.01 5.55±0.07 ± 0.07 0.32±0.00 ± 0.00 2.18±0.06 ± 0.06 22.33 8.50 F1 70.07±2.56 ± 2.56 72.77±1.71 ± 1.71 21.47±0.30 ± 0.30 51.97±0.79 ± 0.79 17.87±0.32 ± 0.32 14.20±0.23 ± 0.23 19.92±0.15 ± 0.15 8.56±0.05 ± 0.05 1.59±0.01 ± 0.01 7.10±0.06 ± 0.06 28.55 9.25 CCASSG ARI 51.84±3.32 ± 3.32 51.80±4.28 ± 4.28 19.18±0.18 ± 0.18 31.28±0.32 ± 0.32 22.43±0.70 ± 0.70 3.20±0.05 ± 0.05 3.34±0.03 ± 0.03 6.11±0.05 ± 0.05 0.23±0.00 ± 0.00 1.40±0.29 ± 0.29 19.08 10.15 F1 72.29±1.48 ± 1.48 69.69±1.95 ± 1.95 23.78±0.25 ± 0.25 30.09±0.32 ± 0.32 22.83±0.39 ± 0.39 14.29±0.24 ± 0.24 16.67±0.26 ± 0.26 8.56±0.06 ± 0.06 0.98±0.01 ± 0.01 5.17±0.16 ± 0.16 26.44 10.50 S3GC ARI 48.12±2.56 ± 2.56 59.09±2.86 ± 2.86 27.08±0.55 ± 0.55 83.27±2.36 ± 2.36 23.57±0.28 ± 0.28 3.30±0.05 ± 0.05 5.45±0.00 ± 0.00 7.51±0.11 ± 0.11 0.67±0.01 ± 0.01 2.56±0.04 ± 0.04 26.06 4.70 F1 69.04±1.57 ± 1.57 70.21±2.55 ± 2.55 24.09±0.70 ± 0.70 71.35±1.60 ± 1.60 25.19±0.41 ± 0.41 14.59±0.29 ± 0.29 23.21±0.00 ± 0.00 7.91±0.05 ± 0.05 2.02±0.01 ± 0.01 8.07±0.02 ± 0.02 31.57 6.50 MAGI ARI 53.51±1.09 ± 1.09 58.53±0.32 ± 0.32 30.38±1.33 ± 1.33 62.27±1.24 ± 1.24 16.67±0.37 ± 0.37 2.46±0.27 ± 0.27 3.16±0.27 ± 0.27 6.44±0.06 ± 0.06 1.06±0.01 ± 0.01 2.92±0.29 ± 0.29 23.74 6.60 F1 72.65±0.36 ± 0.36 70.82±0.15 ± 0.15 25.17±0.59 ± 0.59 55.26±1.62 ± 1.62 21.12±0.19 ± 0.19 14.33±0.78 ± 0.78 20.81±0.36 ± 0.36 9.46±0.06 ± 0.06 2.90±0.02 ± 0.02 9.53±0.27 ± 0.27 30.20 5.40 NS4GC ARI 56.63±1.20 ± 1.20 62.64±0.62 ± 0.62 31.84±2.30 ± 2.30 39.12±0.19 ± 0.19 23.82±0.23 ± 0.23 4.72±0.10 ± 0.10 3.37±0.01 ± 0.01 6.85±0.06 ± 0.06 0.74±0.01 ± 0.01 3.86±0.05 ± 0.05 23.36 3.60 F1 72.81±0.38 ± 0.38 73.73±1.11 ± 1.11 26.67±0.57 ± 0.57 34.95±0.63 ± 0.63 26.52±0.28 ± 0.28 17.23±0.28 ± 0.28 19.44±0.03 ± 0.03 9.14±0.08 ± 0.08 2.33±0.02 ± 0.02 8.80±0.15 ± 0.15 29.16 4.30 OFAG ARI 53.23±0.00 ± 0.00 61.92±0.00 ± 0.00 25.22±0.29 ± 0.29 88.40±0.00 ± 0.00 19.87±0.40 ± 0.40 3.21±0.05 ± 0.05 5.96±0.00 ± 0.00 6.33±0.11 ± 0.11 1.43±0.01 ± 0.01 3.84±0.00 ± 0.00 26.94 3.60 F1 71.72±0.00 ± 0.00 72.93±0.00 ± 0.00 24.38±0.38 ± 0.38 81.17±0.00 ± 0.00 25.02±0.53 ± 0.53 13.54±0.14 ± 0.14 23.89±0.00 ± 0.00 10.28±0.04 ± 0.04 3.12±0.02 ± 0.02 9.34±0.00 ± 0.00 33.54 3.80 Appendix B Proof of Theorem 1 Proof. We establish the approximation separately for condition (i) (node features) and condition (i) (edges), then combine. Condition (i): node feature approximation. Let preal(X∣y)=∑k=1Kπkpk(X)p_real(X y)= _k=1^K _kp_k(X) with y-dependent components pkp_k. By the universal approximation theorem, for each k there exists a neural network Φk _k transforming a Gaussian source into an approximation of pkp_k with arbitrarily small total variation error. A unified Φ can implement all Φk _k conditioned on k, approximating the full mixture. In the CAGM prior, cluster-conditioned latent variables are drawn from tν(μk,Σk)t_ν( _k, _k) and passed through a task-specific random decoder T (Appendix A). Over a sufficiently rich family of decoders (e.g., randomized MLP transformations), T implements Φk _k for each k, and the Dirichlet-sampled proportions π cover arbitrary mixing weights. Condition (i): edge distribution approximation. Any pairwise edge probability model p(Aij=1∣y,X)=σ(sij)p(A_ij=1 y,X)=σ(s_ij) is determined by scores sijs_ij depending on cluster membership and/or node features. The CAGM edge emission (20) parameterizes (24) logit(pij)=ρ+αθ(θi+θj)+λBByi,yj+λHκ(hiA,hjA)+λXsim(xi,xj).logit(p_ij)=ρ+ _θ( _i+ _j)+ _BB_y_i,y_j+ _Hκ(h_i^A,h_j^A)+ _Xsim(x_i,x_j). The block affinity matrix B∈ℝK×KB ^K× K captures arbitrary cluster-conditioned connectivity, spanning homophilous to heterophilous regimes via the construction in Appendix A.4. The degree propensities θi _i model heterogeneous node degrees, and the feature-similarity term λXsim(xi,xj) _Xsim(x_i,x_j) encodes dependence of edges on observed attributes. By setting these coefficients appropriately, any target p(A∣y,X)p(A y,X) satisfying condition (i) can be approximated. Combining. For any ε>0 >0, set approximation errors in each part to at most ε/2 /2. By the triangle inequality for total variation, TV(Φ#psyn(),preal())≤εTV( _\#p_syn(G),\,p_real(G))≤ . ∎ Appendix C Proof of Proposition 2 Proof. (i) Parameter independence from F. The shared encoder gθg_θ consists of: a scalar value embedding ϕval:ℝ→ℝd _val:R ^d; learnable filter-index embeddings pℓ=0L⊂ℝd\p_ \_ =0^L ^d; a Transformer encoder operating over a sequence of length L+2L+2; and a scalar decoder ϕout:ℝd→ℝ _out:R^d . None of these modules depend on F; the total parameter count is |ϕval|+(L+1)d+|Transformer|+|ϕout|,| _val|+(L+1)d+|Transformer|+| _out|, which is fixed regardless of the feature dimension F of the input graph. Although gθg_θ is applied N×FN× F times in total during a forward pass, the parameter count does not change. (i) Feature-permutation equivariance. Let σ be a permutation of 1,…,F\1,…,F\ with (Xσ):,f=X:,σ(f)(X_σ)_:,f=X_:,σ(f). For each node i and feature index f, the filter response profile under the permuted input satisfies (25) ri,f(σ) r_i,f^(σ) =[(Γ0Xσ)i,f,…,(ΓLXσ)i,f] = [( _0X_σ)_i,f,\,…,\,( _LX_σ)_i,f ] =[(Γ0X)i,σ(f),…,(ΓLX)i,σ(f)]=ri,σ(f), = [( _0X)_i,σ(f),\,…,\,( _LX)_i,σ(f) ]=r_i,σ(f), where the second equality holds because the graph filters Γℓ(A)=A^ℓ _ (A)= A act only on the node dimension and are independent of feature indices. Since gθg_θ is applied independently to each (i,f)(i,f) pair without any cross-channel interaction, the re-encoded value for the permuted input is Zi,f(σ)=gθ(ri,f(σ))=gθ(ri,σ(f))=Zi,σ(f)Z_i,f^(σ)=g_θ(r_i,f^(σ))=g_θ(r_i,σ(f))=Z_i,σ(f). Therefore SwiFRTθ(Xσ,A)=SwiFRTθ(X,A)σSwiFRT_θ(X_σ,A)=SwiFRT_θ(X,A)_σ. ∎ Appendix D Proof of Proposition 3 Proof. Let zi∈Sd−1z_i∈ S^d-1 be the ℓ2 _2-normalized embedding of node i, and let μk∈Sd−1 _k∈ S^d-1 be the prototype for cluster k∈1,…,Kk∈\1,…,K\. Von Mises–Fisher mixture model. Assume that embeddings within cluster k are drawn from a von Mises–Fisher (vMF) distribution: (26) p(zi∣yi=k;μk,κ)=Zd(κ)exp(κμk⊤zi),p(z_i y_i=k; _k,κ)=Z_d(κ) (κ _k z_i), where Zd(κ)=κd/2−1/((2π)d/2Id/2−1(κ))Z_d(κ)=κ^d/2-1/ ((2π)^d/2I_d/2-1(κ) ) is the normalization constant with IνI_ν denoting the modified Bessel function of the first kind of order ν. Note that Zd(κ)Z_d(κ) depends only on κ and d, not on μk _k. Posterior probability. Assuming equal mixing weights πk=1/K _k=1/K, the posterior probability of cluster k given ziz_i is: p(yi=k∣zi;μk,κ) p(y_i=k z_i;\ _k\,κ) =πkZd(κ)exp(κμk⊤zi)∑k′=1Kπk′Zd(κ)exp(κμk′⊤zi) = _k\,Z_d(κ) (κ _k z_i) _k =1^K _k \,Z_d(κ) (κ _k z_i) (27) =exp(μk⊤zi/τ)∑k′=1Kexp(μk′⊤zi/τ), = ( _k z_i/τ) _k =1^K ( _k z_i/τ), where τ=1/κτ=1/κ and Zd(κ)Z_d(κ) cancels identically in numerator and denominator (since πk=1/K _k=1/K for all k). This is precisely the form given in Eq. (9). Connection to ℒcompL_comp. The complete-data negative log-likelihood under the vMF mixture is: (28) −1N∑i=1Nlogp(yi∣zi;μk,κ) - 1N _i=1^N p(y_i z_i;\ _k\,κ) =−1N∑i=1Nlogexp(μyi⊤zi/τ)∑k′=1Kexp(μk′⊤zi/τ)=ℒcomp. =- 1N _i=1^N ( _y_i z_i/τ) _k =1^K ( _k z_i/τ)=L_comp. Therefore, minimizing ℒcompL_comp with respect to the encoder parameters θ (which determine zi\z_i\ through the forward pass) is equivalent to maximizing the complete-data log-likelihood under the K-component vMF mixture, i.e., to MLE on μk\ _k\ with concentration κ=1/τκ=1/τ. Remark 3. The cancellation of Zd(κ)Z_d(κ) in Eq. (27) is a distinctive property of the vMF distribution: its normalization constant does not depend on the mean direction μk _k. This property does not hold for Gaussian distributions with class-specific covariances, where the log-determinant log|Σk| | _k| would remain in the objective and introduce additional terms. ∎ Appendix E Proof of Proposition 4 Proof. The Prior-Data Negative Log-Likelihood (Prior-Data NLL) for a PFN is defined as (Müller et al., 2022; Müller et al., 2025): (29) ℒPFN(θ)=c∪(x,y)∼p()[−logqθ(y∣x,c)].L_PFN(θ)=E_D_c∪\(x,y)\ p(D) [- q_θ(y x,D_c) ]. Identifying context and query. Since no cluster labels are available at inference time, the PFN context is c=∅D_c= . The query set is taken to be all nodes in a synthetic graph (A,X,y)∼p()(A,X,y) p(D). Each node i corresponds to a query point x=zix=z_i with label y=yiy=y_i, where zi=Zi,:/∥Zi,:∥2z_i=Z_i,:/\|Z_i,:\|_2 is the ℓ2 _2-normalized output of SwiFRT. Identifying the predictive distribution. The model’s predictive distribution is identified as the vMF posterior derived in Appendix D: (30) qθ(yi∣zi,∅) q_θ(y_i z_i, ) =p(yi∣zi;μ^k,τ) =p(y_i z_i;\ μ_k\,τ) =exp(μ^yi⊤zi/τ)∑k=1Kexp(μ^k⊤zi/τ), = ( μ_y_i z_i/τ) _k=1^K ( μ_k z_i/τ), where the prototypes μ^k\ μ_k\ are computed on-the-fly from the current embeddings and synthetic labels via Eq. (8). Connecting ℒPFNL_PFN to ℒcompL_comp. Substituting into Eq. (29) with c=∅D_c= and averaging over all query nodes: (31) ℒPFN(θ) _PFN(θ) =(A,X,y)∼p()[−1N∑i=1Nlogqθ(yi∣zi)] =E_(A,X,y) p(D) [- 1N _i=1^N q_θ(y_i z_i) ] =(A,X,y)∼p()[ℒcomp(θ,A,X,y)]. =E_(A,X,y) p(D) [L_comp(θ;A,X,y) ]. Consequence for posterior approximation. By the equivalence theorem of Müller et al. (2022), minimizing the Prior-Data NLL is equivalent to minimizing the expected Kullback–Leibler divergence (32) (A,X,y)∼p()[DKL(p(⋅∣z,∅)∥qθ(⋅∣z,∅))]E_(A,X,y) p(D) [D_KL\! (p(· z, )\, \|\,q_θ(· z, ) ) ] between qθq_θ and the true posterior predictive distribution p(⋅∣z,∅)p(· z, ) induced by p()p(D). Therefore, a sufficiently expressive OFAG trained to convergence implicitly performs Bayesian model averaging over the space of vMF mixture clustering hypotheses consistent with p()p(D), without ever computing a posterior explicitly. ∎ Table 5. Summary of the benchmark datasets. The collection spans multiple graph scales, domains, and feature modalities. ℋeH_e and ℋnH_n denote edge homophily and node homophily, respectively. Scale Dataset Domain #Nodes #Edges Avg. Deg. #Feat. Feat. Type #Clus. ℋeH_e ℋnH_n Tiny Cora Citation 2,708 10,556 3.9 1,433 Textual 7 0.81 0.83 Photo Co-purchase 7,650 238,162 31.1 745 Textual 8 0.83 0.84 Small HM Co-purchase 46,563 21,461,990 460.9 120 Tabular 21 0.16 0.35 Flickr Social 89,250 899,756 10.1 500 Textual 7 0.32 0.32 Medium ArXiv Citation 169,343 1,166,243 6.9 128 Textual 40 0.65 0.64 Reddit Social 232,965 23,213,838 99.6 602 Textual 41 0.78 0.81 MAG Citation 736,389 10,792,672 14.7 128 Textual 349 0.30 0.31 Large Pokec Social 1,632,803 44,603,928 27.3 56 Tabular 183 0.43 0.39 Products Co-purchase 2,449,029 61,859,140 25.4 100 Textual 47 0.81 0.82 WebTopic Web 2,890,331 24,754,822 8.6 528 Tabular 28 0.22 0.18 Appendix F Dataset Details Table 5 summarizes the benchmark datasets used in our experiments. The datasets span multiple scales, domains, feature types, and homophily regimes. We use ground-truth labels only for evaluation and do not use them during inference. F.1. Tiny Scale Datasets Cora (Kipf and Welling, 2017). Cora is a citation network where nodes represent scientific papers and edges represent citation links. Node attributes are sparse bag-of-words vectors extracted from paper contents. The clustering task is to group papers into seven research topics. Photo (Shchur et al., 2018). Photo is an Amazon co-purchase graph. Nodes represent products, and edges indicate that two products are frequently purchased together. Node features are bag-of-words representations extracted from product reviews. The clustering objective is to partition products into eight product categories. F.2. Small Scale Datasets HM (Bazhenov et al., 2025). HM is derived from the H&M Kaggle competition. The graph represents a product co-purchasing network, where nodes are products and edges connect products frequently bought by the same customers. Unlike most textual benchmarks, HM contains tabular product features, including categorical product metadata and numerical purchasing statistics. The task is to partition products into 21 product categories. Flickr (Zeng et al., 2020). Flickr is an image-sharing social network. Nodes correspond to images, and edges are constructed based on shared metadata such as location, gallery, or user information. Node features are 500-dimensional bag-of-words vectors based on user-provided tags. The clustering task is to group images into seven classes. F.3. Medium Scale Datasets ArXiv (Hu et al., 2020). ArXiv is a citation network of Computer Science papers from arXiv. Nodes represent papers and edges represent citation links. Node features are 128-dimensional vectors obtained from paper titles and abstracts. The clustering task is to assign papers to 40 subject areas. Reddit (Hamilton et al., 2017). Reddit is a social graph constructed from Reddit posts. Nodes represent posts, and edges connect posts based on common users commenting on both posts. Node features are text-based representations derived from post-related content. The clustering target is the subreddit community associated with each post. MAG (Hu et al., 2020). MAG is a citation network extracted from the Microsoft Academic Graph. Following the benchmark setting, we use the homogeneous paper citation graph, where nodes represent papers and edges represent citation relations. Node features are 128-dimensional textual embeddings derived from paper abstracts. The clustering task is to group papers into 349 venue categories, making MAG a challenging medium-scale benchmark with a large number of clusters and relatively low homophily. F.4. Large Scale Datasets Pokec (Bazhenov et al., 2025). Pokec is a social network dataset where nodes represent users and edges represent friendship relations. Node features are tabular attributes derived from user profile information. The clustering task is to predict users’ regions, resulting in a challenging many-cluster setting with 183 classes. Products (Hu et al., 2020). Products is a large-scale Amazon co-purchase network. Nodes represent products, and edges connect products that are purchased together. Node features are generated from product descriptions. The clustering task is to group products into 47 top-level categories. WebTopic (Bazhenov et al., 2025). WebTopic is a web graph obtained from the Yandex search engine. Nodes correspond to websites, and directed edges indicate that users followed links from one website to another. The features are tabular and heterogeneous, including numerical and categorical website attributes. The clustering goal is to partition websites into 28 topics. This dataset has low homophily, making it a challenging benchmark for methods that rely heavily on edge-based smoothing. Appendix G Baseline Details We follow PyAGC (Liu et al., 2026e) and compare OFAG with representative attributed graph clustering methods. For clarity, we group the baselines into three categories. G.1. Traditional and Non-Parametric Methods • KMeans (McQueen, 1967) clusters the raw node features directly and ignores graph topology. It serves as a basic feature-only baseline. • Node2Vec (Grover and Leskovec, 2016) learns structural node embeddings via biased random walks and then applies k-means. It serves as a structure-only baseline. • SSGC (Zhu and Koniusz, 2020) uses simplified spectral graph convolution to propagate features over the graph before clustering. It is a scalable non-parametric encoder followed by k-means. • SAGSC (Fettal et al., 2023) combines graph smoothing with subspace clustering. It first smooths attributes over the graph and then learns an affinity matrix for spectral clustering. • MS2CAG (Lin et al., 2025) improves scalable subspace graph clustering by avoiding explicit construction of the full self-expressive matrix and solving a rank-constrained formulation efficiently. G.2. Deep Decoupled Methods • GAE (Kipf and Welling, 2016) learns node embeddings with a graph autoencoder by reconstructing graph structure, followed by clustering on the learned embeddings. • DGI (Veličković et al., 2019) maximizes mutual information between local node representations and a global graph summary through contrastive learning. • CCASSG (Zhang et al., 2021) learns graph representations through augmentation-based invariance and feature decorrelation, without requiring explicit negative samples. • S3GC (Devvrit et al., 2022) uses a contrastive objective designed to improve clusterability, with positive relations constructed from graph neighborhoods. • NS4GC (Liu et al., 2024c) introduces semantic-aware reliable node similarity to guide representation learning for graph clustering. • MAGI (Liu et al., 2024b) incorporates modularity maximization into graph contrastive learning, aligning the representation learning objective with community structure. G.3. Deep Joint Methods • DAEGC (Wang et al., 2019) uses a graph attention autoencoder and jointly optimizes reconstruction and clustering objectives. • DinkNet (Liu et al., 2023b) learns cluster-aware node representations with dilation and shrink losses for scalable graph clustering. • MinCut (Bianchi et al., 2020) optimizes a differentiable relaxation of the normalized min-cut objective with additional regularization to avoid degenerate assignments. • DMoN (Tsitsulin et al., 2023) optimizes a differentiable modularity objective for graph clustering. • Neuromap (Blöcker et al., 2024) formulates graph clustering through a differentiable version of the map equation, encouraging partitions that compress graph flow patterns. Table 6. Key hyperparameters of the CAGM synthetic prior. Category Parameter Range / Value Episode size Nodes N [512, 1024][512,\;1024] Feature dim F [8, 128][8,\;128] Clusters K [3, 10][3,\;10] Latent dims Attribute latent dxd_x [4, 32][4,\;32] Structural latent dad_a [4, 32][4,\;32] Cluster proportions Dirichlet concentration η [0.5, 10.0][0.5,\;10.0] (log-uniform) Min. cluster size 11 Graph structure Edge homophily h [0.1, 0.9][0.1,\;0.9] (uniform) Target avg. degree [4, 64][4,\;64] (log-uniform) Attributes Max. irrelevant feature fraction 5%5\% Appendix H Implementation and Evaluation Details OFAG pre-training. We pre-train OFAG on synthetic attributed graphs sampled from the proposed prior. At each step, we sample 8 graphs as a mini-batch. Training lasts for 10,000 steps, so the model observes 80,000 synthetic graphs in total. We optimize the hyperspherical clustering objective using AdamW with learning rate 1×10−41× 10^-4 and weight decay 1×10−41× 10^-4. The SwiFRT hidden dimension is set to 8, and the maximum filter order is set to L=10L=10. The temperature is fixed to τ=1.0τ=1.0, and the dispersion weight is fixed to λ=0.1λ=0.1. To monitor the pre-training process, we synthesize a fixed set of 16 synthetic graphs as a validation set before training begins. At the end of each training step, we compute the loss on this fixed validation set and retain the checkpoint that achieves the lowest validation loss. Pre-training takes approximately 1.5 hours on a single NVIDIA A800 40G GPU. CAGM prior configuration. Table 6 summarizes the key hyperparameters of the CAGM generator used during pre-training. Graph size (N), feature dimension (F), and number of clusters (K) are sampled uniformly from their respective ranges. Cluster proportions are drawn from a Dirichlet distribution with concentration η sampled log-uniformly from [0.5,10.0][0.5,10.0]: small η produces highly imbalanced clusters while large η approaches uniform proportions. Observed node attributes are decoded from Student-t latent vectors through task-specific random linear decoders, and the output dimensions are randomly allocated to five feature types (continuous, binary, count-valued, categorical one-hot, and sparse bag-of-words) with their proportions drawn from a Dirichlet distribution per episode. At most 5% of dimensions may be replaced by cluster-irrelevant nuisance features. The target average degree is sampled log-uniformly from [4,64][4,64], and a binary-search procedure calibrates the global sparsity intercept ρ so that the expected graph density matches the target. Edge homophily h is sampled uniformly from [0.1,0.9][0.1,0.9]; the block affinity matrix diagonal is shifted by s⋅logit(h)s·logit(h) with strength s∼Uniform(0.5,2.0)s (0.5,2.0). The coupling coefficients λB∼Uniform(0.4,2.5) _B (0.4,2.5), λH _H, and λX _X control how strongly edges depend on cluster identity, latent structural similarity, and observed attribute similarity, respectively; λH _H and λX _X are zeroed out with probability 0.25 and 0.35 to produce episodes where graph structure or attributes provide no cross-graph signal. Zero-shot inference. After pre-training, OFAG is frozen and directly applied to each benchmark graph. For a graph (A,X)(A,X), the model computes normalized node representations in one forward pass. We then run k-means with the ground-truth number of clusters K. No benchmark labels are used for training, fine-tuning, early stopping, hyperparameter selection, or model selection. The only use of labels is for computing evaluation metrics. (a) Homophilous graphs (b) Heterophilous graphs (c) All graphs Figure 5. NMI of OFAG at different pre-training checkpoints on homophilous, heterophilous, and all benchmark graphs. Performance improves substantially during the early stage of pre-training and subsequently stabilizes, indicating that OFAG rapidly learns a transferable clustering inference strategy. The inset plots enlarge the early checkpoints to highlight the improvement from initialization to the first evaluated pre-training steps. Appendix I Additional Experiments I.1. Pre-training Dynamics on Realistic Graphs Figure 5 tracks the NMI of OFAG checkpoints when applied directly to the five homophilous datasets, the five heterophilous datasets, and all ten graphs. Two-phase learning. All three curves follow a clear two-phase pattern that mirrors the synthetic validation dynamics reported in Section 4.5. NMI improves steeply during the early stage of training, where the gap between the initial checkpoint and those evaluated after the first few hundred steps is noticeably large, and then enters a gradual plateau for the remainder of training. This indicates that the model rapidly acquires a transferable clustering strategy from the CAGM prior before refining it incrementally. Homophilous vs. heterophilous graphs. Homophilous graphs consistently yield higher absolute NMI throughout training, reflecting that their smoother attribute-structure correlation is closer to typical prior conditions. Heterophilous graphs start from a lower baseline but also improve continuously, demonstrating that the prior’s diverse homophily spectrum endows the model with non-trivial generalization even to graphs where edge propagation is uninformative. The relative improvement rate across the two groups is broadly similar, suggesting that the pre-training signal benefits both graph types proportionally. Checkpoint selection. Although the NMI trajectories stabilize after the initial rapid gains, they do not settle to a perfectly flat line: minor fluctuations persist across later checkpoints, and the overall best performance on the benchmarks does not always coincide with the final training step. This motivates our checkpoint selection strategy (i.e., retaining the snapshot with the lowest loss on the fixed synthetic validation set) rather than simply using the last checkpoint. The validation-loss-based criterion provides a lightweight, label-free proxy that is well-aligned with downstream clustering quality across both graph types. I.2. Sensitivity to Filter Order SwiFRT builds each node-feature response profile by collecting diffusion outputs at orders 0,…,L0,…,L; the choice of L determines the multi-scale context available to the Transformer fusion. Table 7 reports average NMI/ACC as L varies from 2 to 12, with all other settings held fixed. Table 7. Sensitivity to filter order L in SwiFRT. L Homo Avg Hetero Avg All Avg NMI ACC NMI ACC NMI ACC 2 59.54 56.47 14.90 14.49 37.22 35.48 3 61.97 60.32 15.53 15.13 38.75 37.72 5 62.33 61.79 15.80 14.99 39.06 38.39 8 61.77 60.78 16.05 15.20 38.91 37.99 10 62.46 63.01 16.51 16.18 39.49 39.59 12 61.92 61.42 16.39 15.63 39.16 38.53 Two patterns emerge. First, L=2L\!=\!2 causes a marked drop (All NMI 37.2237.22, vs. 38.7538.75 for L=3L\!=\!3), revealing a minimum context threshold: two hops are insufficient to capture multi-scale structural patterns—particularly on heterophilous graphs where same-cluster nodes may not share direct edges and require wider neighborhoods to be jointly identified. Second, performance stabilizes in the range L∈[3,12]L∈[3,12] and peaks at L=10L\!=\!10, with L=12L\!=\!12 yielding only marginal regression (−0.33-0.33 All NMI). This plateau indicates that the Transformer can down-weight redundant high-order responses once the useful multi-hop context has been captured, so adding extra filter orders neither helps substantially nor causes over-smoothing collapse. L=10L\!=\!10 offers the best balance and is used throughout. I.3. Sensitivity to Dispersion Weight The training objective ℒ=ℒcomp+λℒdispL=L_comp+λ\,L_disp (Eq. 12) balances within-cluster compactness against inter-prototype dispersion. Table 8 sweeps λ from 0 to 1.0. Table 8. Sensitivity to dispersion weight λ. λ Homo Avg Hetero Avg All Avg NMI ACC NMI ACC NMI ACC 0 61.40 59.54 14.50 14.54 37.95 37.04 0.1 62.46 63.01 16.51 16.18 39.49 39.59 0.3 61.21 59.07 16.40 15.40 38.81 37.23 0.5 62.43 61.96 16.33 15.38 39.38 38.67 0.8 61.59 60.03 16.18 15.39 38.89 37.71 1.0 62.36 61.07 16.20 15.38 39.28 38.22 The results reveal two regimes. Setting λ=0λ\!=\!0 (no dispersion) produces the worst performance, most notably on heterophilous graphs (Hetero NMI 14.5014.50 vs. ≥16.18≥16.18 for all λ>0λ\!>\!0), confirming that ℒdispL_disp is indispensable for establishing sufficient inter-cluster angular separation, consistent with the component ablation in Section 4.4. Once λ>0λ\!>\!0, performance is broadly stable across λ∈[0.1,1.0]λ∈[0.1,1.0] (All NMI range 38.8138.81–39.4939.49), demonstrating that OFAG is not sensitive to the precise weight as long as dispersion is active. The mild fluctuations in the homophilous split at larger λ reflect an expected tension: an overly strong dispersion term can conflict with the compactness objective by pushing prototypes apart before within-cluster embeddings have fully converged. λ=0.1λ\!=\!0.1 achieves the best trade-off and is used as the default. I.4. Ablation: Homophily Coverage in the Structural Prior Setup. We ablate the range of edge homophily h sampled during pre-training to assess whether broad homophily coverage in the CAGM structural prior is indeed necessary. We compare four variants: the full range h∈[0.1, 0.9]h\!∈\![0.1,\,0.9] used by OFAG, a homophily-only regime h∈[0.7, 0.9]h\!∈\![0.7,\,0.9], a near-neutral regime h∈[0.4, 0.6]h\!∈\![0.4,\,0.6], and a heterophily-only regime h∈[0.1, 0.3]h\!∈\![0.1,\,0.3]. All other pre-training hyperparameters are held fixed; each variant is evaluated zero-shot on the same ten benchmark datasets. Table 9. Ablation of the homophily range sampled during pre-training. Average NMI/ACC over the five homophilous (Homo), five heterophilous (Hetero), and all ten graphs (All). Homophily range Homo Avg Hetero Avg All Avg NMI ACC NMI ACC NMI ACC [0.1, 0.9][0.1,\,0.9] (full, default) 62.46 63.01 16.51 16.18 39.49 39.59 [0.7, 0.9][0.7,\,0.9] (homo-only) 61.46 59.24 15.65 15.22 38.56 37.23 [0.4, 0.6][0.4,\,0.6] (near-neutral) 57.52 54.37 15.15 14.88 36.34 34.63 [0.1, 0.3][0.1,\,0.3] (hetero-only) 51.62 47.34 13.13 13.26 32.37 30.30 Results and analysis. Table 9 shows a consistent ranking across all three evaluation splits: full coverage dominates every restricted range, confirming that broad homophily diversity in the prior is essential for zero-shot generalization. Removing heterophilous pre-training (homo-only, h∈[0.7, 0.9]h\!∈\![0.7,\,0.9]) penalizes heterophilous benchmarks most. Heterophilous NMI drops from 16.51 to 15.65 (−0.86-0.86) while homophilous NMI declines relatively slightly (62.46→ 61.46, −1.00-1.00). This asymmetry is intuitive: without exposure to heterophilous graphs, the model develops an implicit prior that connected nodes share the same cluster, causing it to over-smooth representations when cross-cluster edges dominate. The relative resilience on homophilous graphs further confirms that the model is not merely memorizing low-h patterns; it uses the full range to learn an adaptive aggregation strategy. Restricting to a near-neutral range (h∈[0.4, 0.6]h\!∈\![0.4,\,0.6]) imposes a different failure mode. Despite covering a balanced mixture of intra- and inter-cluster edges, this variant suffers on both splits (57.52/15.15 NMI), underperforming even homo-only pre-training on homophilous graphs. The cause is insufficient signal diversity: graphs near h=0.5h=0.5 carry a weak structural signal, as intra- and inter-cluster edge probabilities are nearly identical, so the model never learns to exploit strong topology cues. At inference time, real homophilous graphs present the model with structural signals it has rarely encountered during pre-training. Restricting to heterophilous pre-training (h∈[0.1, 0.3]h\!∈\![0.1,\,0.3]) is the most damaging configuration. Homophilous NMI collapses to 51.62 (−10.84-10.84 vs. full range) and overall NMI drops by 7.12 points. Because the majority of benchmark graphs are homophilous (ℋe>0.5H_e>0.5), the model is exposed to a distribution that is systematically misaligned with the test domain, and the strongly heterophilous pre-training signal actively encourages the model to route information across cluster boundaries rather than within them. Notably, heterophilous NMI also falls substantially (13.13 vs. 16.51), despite the training regime nominally targeting heterophilous structures. This seemingly paradoxical result arises because real heterophilous benchmarks are not uniformly extreme: their edge homophily spans a moderate range rather than concentrating near zero. Pre-training exclusively on strongly heterophilous graphs (h≤0.3h\!≤\!0.3) therefore covers only a narrow slice of the heterophilous spectrum, leaving the model poorly calibrated for graphs with intermediate-to-mild heterophily that appear in the test set. Taken together, these results validate the design of the CAGM structural prior: covering the full spectrum h∈[0.1, 0.9]h\!∈\![0.1,\,0.9] ensures that the model is neither biased toward smoothing same-cluster signals nor biased toward amplifying cross-cluster signals, enabling reliable zero-shot transfer across diverse real-world homophily regimes. Appendix J Time Complexity Analysis We analyze the time complexity of OFAG at inference, decomposing it into the two stages: (1) graph diffusion pre-computation and (2) SwiFRT encoding, followed by k-means. Throughout, N denotes the number of nodes, |E||E| the number of edges, F the input feature dimension, L the maximum filter order, d the hidden dimension of the Transformer inside SwiFRT, and K the number of clusters. L and d are fixed hyperparameters (L=10L=10, d=8d=8 in our implementation). Graph diffusion pre-computation. SwiFRT requires the diffusion stack A^ℓXℓ=0L\ A X\_ =0^L. Each multiplication A^ℓX=A^⋅(A^ℓ−1X) A X= A·( A -1X) is a sparse-dense matrix product with cost O(|E|⋅F)O(|E|· F). Computing all L powers therefore costs O(L⋅|E|⋅F).O(L·|E|· F). For sparse graphs where |E|=O(N)|E|=O(N) (e.g., citation or social networks), this reduces to O(L⋅N⋅F)O(L· N· F), i.e., linear in the graph size. SwiFRT encoding. For each node–feature pair (i,f)(i,f), the Transformer processes a token sequence of length L+2L+2 (one CLS token plus L+1L+1 filter-response tokens). Self-attention within this fixed-length sequence costs O((L+2)2⋅d)=O(L2d)O((L+2)^2· d)=O(L^2d) per pair. Summing over all N⋅FN· F pairs gives O(N⋅F⋅L2⋅d).O(N· F· L^2· d). Since L and d are constants, this simplifies to O(N⋅F)O(N· F), i.e., linear in both the number of nodes and the feature dimension. Post-encoding k-means. Standard k-means on N embeddings of dimension F for T iterations costs O(N⋅F⋅K⋅T)O(N· F· K· T). In practice K and T are small, so this term is dominated by the encoding stage for large graphs. Total inference complexity. Combining the above, the end-to-end inference complexity of OFAG is O(L⋅|E|⋅F+N⋅F⋅L2d)=O(|E|⋅F+N⋅F)=O((|E|+N)⋅F),O (L·|E|· F\;+\;N· F· L^2d )\;=\;O (|E|· F\;+\;N· F )\;=\;O ((|E|+N)· F ), where the simplification treats L and d as constants. For sparse graphs this is O(N⋅F)O(N· F)—linear in the graph size—which explains the order-of-magnitude speedup over iterative optimization-based baselines observed in Table 2. Comparison with baselines. Dataset-specific clustering methods additionally incur the cost of per-graph optimization. For example, GNN-based methods such as DinkNet and S3GC perform ToptT_opt gradient steps, each of cost O(|E|⋅dmodel)O(|E|· d_model), giving a total optimization overhead of O(Topt⋅|E|⋅dmodel)O(T_opt·|E|· d_model) on top of the encoding. Contrastive learning methods (e.g., MAGI, NS4GC) introduce an additional quadratic term: computing all pairwise node similarities or constructing a full negative-sample matrix costs O(N2)O(N^2) per step, which becomes prohibitive for large batch sizes. Hyperparameter search multiplies all of these costs further. OFAG eliminates both the per-graph optimization overhead and the quadratic contrastive term entirely, reducing inference to a single forward pass followed by k-means.