PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2610.07778v1cs.LGcs.AI

TL;DR

Attributed graph clustering still relies on graph-specific model selection and tuning across graphs with diverse features and structures. OFAG learns a reusable clustering strategy from synthetic attributed graphs and applies a frozen model to new graphs in one forward pass. Across ten datasets, it achieves the best mean score and average rank across NMI, ACC, ARI, and F1 while completing them in 12.43 minutes total.

  • Problem

    Attributed graph clustering still requires per-graph model selection and tuning, while graphs vary in features, structures, and attribute–topology relationships.

    Source: §1 · p. 1

  • Method

    OFAG pre-trains on synthetic attributed graphs to learn a reusable clustering strategy that it applies to new graphs in a single forward pass.

    Source: §1 · p. 2, §5 · p. 8

  • Results

    Across ten datasets, one frozen OFAG model achieves the best mean score and average rank across NMI, ACC, ARI, and F1, completing them in 12.43 minutes total.

    Source: §1 · p. 2

  • Takeaways & Limitations

    A single frozen model can cluster the evaluated real-world graphs without graph-specific training, fine-tuning, or hyperparameter search.

    Source: §5 · p. 9

    Its synthetic-prior conditions assume that both attributes and edges are generated through cluster-dependent mechanisms, without restricting their distribution family or connectivity pattern.

    Source: §3.2 · p. 4

Abstract

from arXiv · show

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 https://github.com/Cloudy1225/OFAG, allowing practitioners to directly apply OFAG to their own attributed graph datasets without additional training or tuning.

1 Introduction

Attributed graph clustering still requires costly per-graph model selection and tuning across graphs that vary in features, structure, and attribute–topology relationships. OFAG is proposed as a one-for-all model trained on synthetic graphs and applied to new graphs without graph-specific training or tuning.

1 Introduction

  • Attributed graphs vary in feature dimensions and types, structural regimes, cluster sizes, and degree distributions, making assumptions that work on one graph liable to fail on another.Without validation labels, model selection has no signal to detect failures, and blind hyperparameter search compounds across graphs.Source: §1 · p. 1
  • OFAG asks whether one model can be trained once and applied to arbitrary attributed graphs without graph-specific training, fine-tuning, or hyperparameter search.It applies to a new graph in a single forward pass, after which a standard algorithm recovers clusters.Source: §1 · p. 2
  • OFAG adapts Prior-data Fitted Networks by pre-training on CAGM synthetic graphs with variable cluster counts and permuted cluster identities, learning from attributes and topology without labeled context.The prior spans feature types, cluster separabilities, structural regimes, and attribute–topology coupling strengths.Source: §1 · p. 2
  • SwiFRT treats each feature channel as a graph signal and models its responses to shared diffusion filters, enabling dimension-agnostic encoding invariant to channel order.A hyperspherical objective shapes embeddings so same-cluster nodes approach shared prototypes and prototypes spread across the unit hypersphere.Source: §1 · p. 2
  • 12.43 minutes total let one frozen OFAG model complete ten datasets; it achieved the best mean score and average rank across NMI, ACC, ARI, and F1.It outperformed dataset-specific baselines; the second-fastest baseline required over 6× more time, and the second-best on clustering quality required nearly 28× more computation.Source: §1 · p. 2

2 Related Work

Prior attributed graph clustering methods remain dataset-specific, while graph foundation models generally address supervised tasks or require adaptation resources unavailable to unsupervised clustering. OFAG adapts prior-data fitting to learn a reusable clustering inference strategy.

2.1 Attributed Graph Clustering

  • Attributed graph clustering methods combine encoding, cluster assignment, and optimization, but remain dataset-specific and may not transfer across feature types, structural regimes, and attribute–topology correlations.OFAG instead learns a reusable strategy for clustering unseen graphs without graph-specific training, fine-tuning, or hyperparameter search.Source: §2.1 · p. 2

2.2 Graph Foundation Models

  • Graph foundation models address heterogeneity through text-space, feature-aligned, or inductive approaches, but may require textual attributes, downstream adaptation, or labeled context; OFAG targets unsupervised clustering.Existing models mainly target supervised graph tasks.Source: §2.2 · pp. 2–3

2.3 Prior-Data Fitted Networks

  • PFNs train on synthetic datasets sampled from a prior to approximate posterior predictive inference on new data in one forward pass; OFAG adapts this principle from label inference to zero-shot clustering.The adaptation learns from synthetic attributed graph priors how attributes and topology jointly reveal latent clusters.Source: §2.3 · p. 3

3 Methodology

OFAG learns reusable clustering geometry from synthetic attributed graphs and applies a frozen model to unseen graphs. Its prior, encoder, and objective address heterogeneous graph inputs and label-free clustering.

3 Methodology

  • OFAG combines a synthetic graph prior, a dimension-agnostic encoder, and a hyperspherical objective to learn representations suited to zero-shot clustering.The design targets heterogeneous feature spaces, arbitrary cluster identities and counts, and varying relationships between attributes and topology.Source: §3 · p. 3

3.1 Problem Setup

  • OFAG maps graph features and topology to embeddings where same-cluster nodes are close and different-cluster nodes are separable, without fixed output labels.A label-free algorithm such as k-means can recover clusters from this learned geometry.Source: §3.1 · p. 3

3.2 Synthetic Attributed Graph Prior

  • CAGM samples graph sizes, feature dimensions, and cluster counts broadly, varying cluster balance, attribute types, and homophilous-to-heterophilous structure.Its edges combine cluster affinity, degree propensity, structural proximity, and feature similarity; randomized evidence reliability is intended to encourage adaptive weighting.Source: §3.2 · p. 3
  • Under stated cluster-dependent feature and edge-generation conditions, a CAGM prior and encoder can approximate the real-graph distribution arbitrarily closely.The conditions allow finite mixtures of continuous feature distributions and pairwise edge models whose log-odds depend on clusters and node features.Source: §3.2 · p. 4

3.3 Signal-wise Filter Response Transformer

  • SwiFRT processes each feature channel as a graph signal, encoding its responses across diffusion filters with shared parameters independent of feature semantics.Its Transformer models interactions among filter orders, such as whether a signal remains stable, smooths, or amplifies; its parameter count is independent of feature dimension and it is equivariant to feature-channel permutations.Source: §3.3 · pp. 4–5

3.4 Hyperspherical Clustering Objective

  • The vMF-based objective clusters normalized embeddings while dispersing prototypes; when F≥K−1, dispersion approaches an equiangular tight frame.The two terms concentrate nodes near their own prototypes and spread the prototypes apart on the hypersphere.Source: §3.4 · p. 5

3.5 Connection to Prior-Data Fitted Networks

  • OFAG’s compactness objective is equivalent to prior-data negative log-likelihood minimization for a Bayesian vMF mixture with empty context.At convergence, a sufficiently expressive model approximates the posterior predictive distribution induced by the prior; the dispersion term regularizes prototype geometry without changing this PFN interpretation.Source: §3.5 · p. 5

3.6 Zero-Shot Inference

  • At inference, the frozen model embeds an unseen graph in one forward pass, then a standard clustering algorithm assigns nodes without gradient updates or validation labels.No graph-specific training or fine-tuning is required.Source: §3.6 · p. 6

4 Experiments

Across ten diverse attributed graphs, one frozen OFAG model achieves the strongest overall clustering performance while requiring no graph-specific adaptation. Experiments examine its speed, design choices, pre-training dynamics, and representations.

4.2 Performance Comparison

  • OFAG has the best mean score and lowest average rank across all four metrics, despite using no graph-specific training, fine-tuning, or hyperparameter search.Mean scores are NMI 39.49, ACC 39.59, ARI 26.94, and F1 33.54.Source: §4.2 · p. 7
  • On Reddit, OFAG leads with NMI 85.94 versus S3GC’s 83.45 and F1 81.17 versus SAGSC’s 70.43, but ranks second or third on Cora, Photo, and ArXiv.The reported NMI gap on Cora, Photo, and ArXiv is 2–4 points.Source: §4.2 · p. 7
  • On Flickr, MAG, and WebTopic, OFAG ranks first on reported metrics, while on HM and Pokec it misses the top three on most metrics.The authors suggest dense tabular structure, many fine-grained clusters, and atypical attribute-structure correlations may explain the HM and Pokec results.Source: §4.2 · p. 7

4.3 Efficiency Comparison

  • 12.43 minutes suffices for OFAG to complete all ten datasets, versus 76.19 minutes for DMoN and 345.92 minutes for S3GC.OFAG has Mean NMI 39.49; DMoN has 30.05, and S3GC has 38.08.Source: §4.3 · p. 7, Table 2 · p. 7
  • 12.43 minutes is OFAG’s total benchmark runtime, compared with 76.19 minutes for DMoN and 345.92 minutes for S3GC; the time comparison includes zero-shot inference for OFAG, not its one-time pre-training.The table reports wall-clock clustering time; OFAG ran on CPU for some datasets because of GPU memory constraints.Source: §4.3 · p. 7, §4.1 · p. 7, Table 2 · p. 7

4.4 Ablation: Model Components

  • Mixed binary, categorical, and count-valued attributes and homophily levels from 0.1 to 0.9 each contribute gains across graph types.The authors report that broad homophily coverage particularly benefits heterophilous graphs.Source: §4.4 · p. 8
  • Transformer fusion adds 2.71 NMI over the MLP variant on heterophilous graphs, while ℓ2 normalization gives the largest single gain in the ablation table.The authors associate fusion with modeling non-monotone diffusion responses and normalization with reducing scale variation across graphs and feature dimensions.Source: §4.4 · p. 8, Table 3 · p. 8
  • Ldisp improves heterophilous benchmarks by 2.01 NMI and drives prototypes toward an equiangular arrangement on the hypersphere.The authors describe this separation as especially consequential when attribute-structure agreement is limited.Source: §4.4 · p. 8, Table 3 · p. 8

5 Conclusion

OFAG is presented as a one-for-all foundation model for attributed graph clustering, pretrained on synthetic graphs and applied to real-world graphs in one forward pass. Across ten datasets, a single frozen model achieves the best mean performance and is the fastest method overall.

5 Conclusion

  • A single frozen OFAG model achieves the best mean performance and is the fastest method overall across ten datasets.The model is pretrained on synthetic graphs and applied to real-world graphs in a single forward pass.Source: §5 · pp. 8–9

Ethics and Privacy Statement

OFAG’s pre-training prior is designed to span diverse attributed graph clustering tasks rather than reproduce one real-world graph family. It varies cluster balance, attributes, topology, homophily, and the relative reliability of attributes and structure.

Ethics and Privacy Statement

  • Downstream clustering that groups individuals can reflect and amplify demographic biases in graph structure and attributes, so high-stakes use calls for disparate-impact audits.The work reports no new personal data or human subjects; its pre-training graphs are synthetic and contain no personal information.Source: Ethics and Privacy Statement · p. 10

A Details of Synthetic Attributed Graph Prior

  • CAGM is intended to generate diverse clustering tasks, not exactly reproduce any single real-world graph family.The prior varies attributes, graph structures, cluster imbalances, and modality reliabilities.Source: A Details of Synthetic Attributed… · p. 11

A.1 Latent Cluster Generation

  • Sampling cluster proportions across a broad range of η produces tasks from balanced to highly imbalanced.Cluster size proportions are drawn from a Dirichlet distribution.Source: §A.1 · p. 11

A.2 Attribute Generation

  • Random task-specific decoders and observation transforms yield varied feature types, with irrelevant dimensions, noise, scaling, and missing or sparse entries added.Varying attribute separability also makes attributes strongly, weakly, or nearly uninformative for clustering.Source: §A.2 · p. 11

A.3 Graph Generation

  • Edges depend on cluster assignments, degree propensities, latent structural positions, and optionally attribute similarity; degree variation covers regular graphs through hub-heavy graphs.The edge-generation coefficients control the influence of cluster identity, structural similarity, and attribute similarity.Source: §A.3 · p. 11

A.4 Structural Regimes

  • A continuously sampled homophily level shifts within-cluster versus cross-cluster affinity, covering homophilous, neutral, and heterophilous regimes.The four illustrated examples range from h=0.194 to h=0.863; values below 0.5 suppress diagonal affinities, while values above 0.5 boost them.Source: §A.4 · pp. 11–12, Figure 4 · p. 12

A.5 Modality Reliability

  • The prior varies attribute separability, graph signal strength, edge noise, degree heterogeneity, and coupling to model attribute-dominant, structure-dominant, combined, and misleading-structure tasks.This exposes OFAG during pre-training to different levels of attribute and topology reliability.Source: §A.5 · p. 12

B Proof of Theorem 1

The proof argues that the CAGM prior can approximate attributed graph distributions by separately approximating feature and edge generation, then combining the errors.

Condition (i): node feature approximation

  • The feature argument uses cluster-conditioned neural transformations and Dirichlet-sampled proportions to approximate feature mixtures with arbitrary mixing weights.The latent variables use Student-t distributions, followed by task-specific random decoders.Source: B Proof of Theorem 1 · p. 12

Condition (ii): edge distribution approximation

  • The edge argument uses CAGM’s block affinities, degree propensities, and attribute-similarity term to approximate pairwise edge probabilities under condition (ii).The block affinities span homophilous and heterophilous regimes.Source: B Proof of Theorem 1 · p. 12

Combining

  • For any ε>0, the feature and edge approximation errors can each be bounded by ε/2, giving total variation error at most ε.The final bound follows from the triangle inequality for total variation.Source: B Proof of Theorem 1 · p. 12

C Proof of Proposition 1

These appendices establish properties of OFAG’s encoder, connect its clustering objective to a vMF mixture and PFN inference, and describe the benchmark datasets.

C Proof of Proposition 1

  • The SwiFRT encoder’s parameter count is independent of feature dimension, and independently encoding each node-feature pair makes its outputs equivariant to feature permutations.The shared encoder is applied N×F times, while its parameter count remains fixed as F changes.Source: C Proof of Proposition 1 · p. 12

D Proof of Proposition 2

  • Under a vMF mixture assumption for normalized embeddings and equal mixing weights, minimizing Lcomp is equivalent to maximizing the mixture’s complete-data log-likelihood.The normalization constant cancels because it does not depend on the cluster mean direction.Source: D Proof of Proposition 2 · pp. 13–14

E Proof of Proposition 3

  • With an empty PFN context, each graph node is a query whose embedding is the normalized SwiFRT output, and the predictive distribution is the vMF posterior.The prototypes are computed on the fly from current embeddings and synthetic labels.Source: E Proof of Proposition 3 · p. 14
  • Minimizing Prior-Data NLL is equivalent to minimizing expected KL divergence to the prior-induced posterior predictive distribution.A sufficiently expressive OFAG trained to convergence therefore approximates that posterior predictive distribution.Source: E Proof of Proposition 3 · p. 14

F Dataset Details

  • The benchmark collection spans scales, domains, feature types, and homophily regimes, with ground-truth labels used only for evaluation.The described examples include citation, product, and social graphs.Source: F Dataset Details · p. 14, §F.1 · p. 14, §F.2 · p. 14

F.1 Tiny Scale Datasets

  • Cora is a seven-topic citation network with sparse bag-of-words paper features, while Photo is an eight-category co-purchase graph with review-derived bag-of-words features.Photo nodes represent products and edges connect frequently co-purchased products.Source: §F.1 · p. 14

F.2 Small Scale Datasets

  • HM uses categorical and numerical product attributes for 21 categories, while Flickr uses 500-dimensional tag features to group images into seven classes.HM is a product co-purchasing graph; Flickr links images using shared metadata.Source: §F.2 · p. 14

F.3 Medium Scale Datasets

The medium- and large-scale dataset descriptions extend the benchmark across text and tabular features, many-cluster tasks, and low-homophily graphs. The baseline overview groups methods by their clustering approach.

F.3 Medium Scale Datasets

  • ArXiv, Reddit, and MAG cover medium-scale citation and social graphs, with MAG presenting 349 venue categories and relatively low homophily.Their node features include title and abstract vectors, text-derived representations, and textual embeddings.Source: §F.3 · p. 14

F.4 Large Scale Datasets

  • Pokec, Products, and WebTopic cover large-scale social, product, and web graphs; WebTopic has heterogeneous tabular features and low homophily.Pokec has 183 region classes, while Products groups products into 47 top-level categories.Source: §F.4 · p. 15

G Baseline Details

  • The baselines are organized into traditional and non-parametric methods, deep decoupled methods, and other approaches.The section follows PyAGC for its comparison set.Source: G Baseline Details · p. 15

G.1 Traditional and Non-Parametric Methods

  • Traditional baselines include feature-only KMeans, structure-only Node2Vec, graph-smoothed SSGC, and SAGSC’s smoothing followed by subspace clustering.MS2CAG is described as an efficient rank-constrained subspace graph clustering method.Source: §G.1 · p. 15

G.2 Deep Decoupled Methods

  • Deep decoupled baselines use graph reconstruction, mutual information, augmentation invariance, contrastive learning, reliable node similarity, or modularity maximization.The listed methods are GAE, DGI, CCASSG, S3GC, NS4GC, and MAGI.Source: §G.2 · p. 15

G.3 Deep Joint Methods

The section lists deep joint graph-clustering methods and their distinct optimization objectives.

G.3 Deep Joint Methods

  • DAEGC combines a graph attention autoencoder with reconstruction and clustering objectives [53].Source: §G.3 · p. 15
  • DinkNet learns cluster-aware node representations using dilation and shrink losses for scalable graph clustering [34].Source: §G.3 · p. 15
  • MinCut, DMoN, and Neuromap respectively optimize normalized min-cut, modularity, and map-equation objectives [4] [5].Source: §G.3 · p. 15

H Implementation and Evaluation Details

OFAG is pretrained on a broad synthetic graph prior and evaluated frozen, with checkpoint selection based on synthetic validation loss. Its real-graph learning curves and sensitivity tests motivate multi-scale filters and an active dispersion term.

H Implementation and Evaluation Details

  • OFAG trains for 10,000 steps on 80,000 synthetic graphs, selecting the checkpoint with lowest loss on a fixed 16-graph validation set.Pretraining takes approximately 1.5 hours on one NVIDIA A800 40G GPU; the CAGM prior varies graph size, feature types, cluster balance, degree, homophily, and edge-signal couplings.Source: H Implementation and Evaluation Details · p. 16
  • At zero-shot inference, frozen OFAG produces node representations in one forward pass, followed by k-means using the ground-truth cluster count; labels are reserved for evaluation.Source: H Implementation and Evaluation Details · p. 16

I.1 Pre-training Dynamics on Realistic Graphs

  • NMI rises steeply in early pretraining and then plateaus across homophilous, heterophilous, and combined benchmark graphs.Homophilous graphs retain higher absolute NMI, while heterophilous graphs improve continuously at a broadly similar relative rate; later checkpoints fluctuate, motivating selection by lowest fixed-synthetic-validation loss.Source: §I.1 · p. 16, Figure 5 · p. 17

I.2 Sensitivity to Filter Order

  • All NMI is 37.22 at L=2 versus 38.75 at L=3; performance stabilizes for L∈[3, 12] and peaks at L=10.The authors attribute the low-order drop to insufficient multi-hop context, especially for heterophilous graphs.Source: §I.2 · pp. 16–17, Table 7 · p. 17

I.3 Sensitivity to Dispersion Weight

  • 38.81–39.49 All NMI spans dispersion weights λ∈[0.1, 1.0], while λ=0 yields 14.50 Hetero NMI versus at least 16.18 for every positive weight.The authors use λ=0.1 as the default trade-off.Source: §I.3 · p. 17, Table 8 · p. 17

I.4 Ablation: Homophily Coverage in the Structural Prior

The homophily ablation finds that broad prior coverage outperforms restricted ranges across all evaluation splits, supporting training across the full spectrum ℎ∈[0.1, 0.9].

I.4 Ablation: Homophily Coverage in the Structural Prior

  • Full homophily coverage ℎ∈[0.1, 0.9] dominates every restricted range across all three splits, supporting broad coverage for zero-shot generalization.The comparison reports average NMI/ACC for homophilous, heterophilous, and all ten graphs.Source: §I.4 · pp. 17–18, Table 9 · p. 17
  • With homo-only pretraining, Heterophilous NMI falls from 16.51 to 15.65 (−0.86), while Homophilous NMI shifts from 62.46 to 61.46 (−1.00).The authors attribute the larger heterophilous impact to an implicit same-cluster smoothing bias.Source: §I.4 · p. 18
  • Near-neutral pretraining ℎ∈[0.4, 0.6] yields 57.52/15.15 NMI on the homophilous/heterophilous splits, which the authors link to weak structural signals in that range.Source: §I.4 · p. 18
  • Heterophily-only pretraining ℎ∈[0.1, 0.3] lowers Homophilous NMI to 51.62 (−10.84 versus full range) and overall NMI by 7.12 points.Heterophilous NMI also drops to 13.13 from 16.51 because the benchmark graphs include intermediate-to-mild heterophily.Source: §I.4 · p. 18

J Time Complexity Analysis

OFAG inference combines sparse graph diffusion, SwiFRT encoding, and k-means, with complexity linear in nodes and feature dimension for sparse graphs when filter and hidden dimensions are fixed. Unlike iterative or contrastive baselines, it avoids per-graph optimization and quadratic similarity costs.

J Time Complexity Analysis

Loading 2610.07778v1…