CS Paper Radar

Selective Hypergraph Refinement for Frozen Graph Clustering

Zimo Si

cs.LG ·submitted 2026-09-03 01:47 UTC · v1

Abstract

Existing graph-clustering methods typically improve clustering performance by optimizing model parameters and node representations. Effective means of further improving the clustering results of an already trained and frozen model, however, remain limited. We study post-processing for frozen graph clustering. After checkpoint fixation, the procedure uses no labels and updates neither model parameters, node representations, nor the original graph structure. Instead, it exploits an attribute hypergraph to supplement higher-order relations that ordinary graphs cannot readily express, thereby refining existing cluster assignments. Because global hypergraph refinement can yield both performance gains and erroneous updates, we propose Selective Hypergraph Refinement (SHR). The method generates candidate residual directions from the hypergraph and evaluates their reliability using graph structure, node attributes, and matched-null evidence. It updates only nodes with sufficient support and otherwise retains their original assignments. Further analysis shows that whether a node changes cluster is jointly governed by its native assignment gap and the directional strength of the refinement. In a controlled common-suite evaluation, 13 of 15 backbone-dataset cells had a positive mean macro gain, one produced exact no-action, and one was negative. The cell-equal macro gain was 0.066 pp (95% bootstrap CI, [0.030, 0.107] pp), while only 0.209% of hard assignments changed on average. A broader 15-combination native-interface evaluation yielded a macro gain of 0.137 pp at a mean change ratio of 0.375%. These results indicate that frozen clustering outputs retain a limited but measurable refinement space after training. The effect is heterogeneous across backbone-dataset pairs, and broader coverage also increases exposure to negative transfer.

Comment
36 pages, 9 figures; includes appendices

Closest papers

Nearest neighbours by meaning across the whole index.

Towards One-for-All Foundation Model for Attributed Graph Clustering

cs.LG cs.AI ·2026-10-06 ·Yunhui Liu, Xudong Jin, Kang Zhang, Danshuo An, Yu Xing +3 more
code/data similarity 0.68
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 https://github.com/Cloudy1225/OFAG, allowing practitioners to directly apply OFAG to their own attributed graph datasets without additional training or tuning.

0.57

Scalable Approximate Algorithm for Dynamic Densest Subhypergraphs with Solution-Guided Maintenance

cs.DB ·2026-09-30 ·Jingbang Chen, Chenhao Ma, Yingli Zhou
similarity 0.65
Abstract · 19 pages

Hypergraphs model interactions involving groups of entities, and finding highly connected groups is a fundamental task in analyzing these data. When interactions arrive and expire, maintaining a dense group can require frequent and expensive changes to the underlying representation. We propose CAP, a scalable algorithm that explicitly maintains a $(1+ε)$-approximate densest subhypergraph under hyperedge insertions and deletions. The algorithm keeps a solution candidate together with an endpoint allocation that bounds the optimum density. The candidate's density guides maintenance: an update triggers repair only when this bound is too large to establish the required approximation. Local searches redistribute load or find a denser candidate, allowing CAP to retain useful solutions across many updates. We give an analysis that relates maintenance work to the size of the regions searched and the density lost by the maintained solution. It identifies conditions under which local repair remains inexpensive and provides a theoretical explanation for the observed efficiency. Experiments on real-world hypergraphs show speedups of up to nearly four orders of magnitude over the evaluated dynamic baselines, while supporting frequent queries and high accuracy. CAP also remains competitive with specialized dynamic graph methods on ordinary graphs, with speedups of up to approximately $64\times$ on the tested workloads.

0.26

Scalable Hierarchical Graph Generation via Soft Community Structure

cs.LG cs.AI ·2026-10-08 ·Ahmet Tüzen, Helge Langseth, Kjetil Nørvåg
similarity 0.60
Abstract

Generating large attributed graphs requires reproducing the topology, generating attributes jointly with the structure, and remaining scalable. Many real-world graphs exist as a single large graph, so a generative model has to generalize from the one graph it is fit on, without independent samples. We present Schema, which recursively decomposes a reference graph into a hierarchy of soft communities, assigning each node a membership distribution. Generation is then split into three stages, each trained independently: (1) synthesizing node attributes conditioned on soft memberships, (2) generating intra-community edges from local structural context, and (3) modeling inter-community connections over bridge nodes whose membership mass is distributed across several communities. No stage forms the full adjacency matrix, and each stage operates on a subgraph bounded by the community size. We also introduce an evaluation protocol that covers structural fidelity, memorization, downstream utility, and scalability. On four real-world attributed graphs, Schema recovers the balance between local and long-range structure more closely than any other model that generates attributes, while reproducing only a small fraction of the reference edges. It retains the downstream accuracy of the reference graph without raising it artificially above that level. Baselines that match its structural fidelity memorize the reference, while those with higher downstream accuracy either exceed the reference accuracy or fail to complete on the larger graphs. We measure scalability on six additional graphs with up to 10 million nodes.

0.23

To Learn is to Wander: Learning Across Graphs and Tasks with Random Walks

cs.LG ·2026-10-05 ·Louis Tichelman, Xingyue Huang, Jinwoo Kim, İsmail İlkan Ceylan
similarity 0.60
Abstract

Graph foundation models aim to transfer across graphs, feature spaces, relational schemas, and prediction tasks, yet existing approaches typically generalize only within particular graph modalities or tasks. We propose Wander, a graph foundation model designed to operate across these settings within a single pretrained checkpoint. Following the prior-predictive perspective, we formulate graph learning as completion of a partially observed graph. We realize this task-general view through a common interface based on random walks, allowing the same model to operate across homogeneous and multi-relational graphs with varying features, labels, and relational schemas. Wander can increase its structural context at inference time without changing its learned parameters and, under suitable assumptions, universally approximates the corresponding Bayes-optimal predictor on bounded connected graphs. Empirically, a single pretrained checkpoint achieves state-of-the-art or highly competitive results across node classification, homogeneous link prediction, and knowledge-graph link prediction. Moreover, joint pretraining across graph modalities and tasks preserves performance in specialized settings while enabling positive transfer and the composition of separately learned capabilities at inference time.

0.10

NodeGround: A Node Classification Benchmark in the Graph Foundation Model Era

cs.LG ·2026-09-30 ·Jinmo Lee, Dooho Lee, Minho Jeong, Jaemin Yoo
benchmarkcode/data similarity 0.59
Abstract

Can a pretrained graph model replace training and tuning a separate predictor for each dataset? Answering this requires evaluating prediction quality alongside computational cost. We present NodeGround, a node classification benchmark that puts graph foundation models (GFMs) and dataset-specific supervised learning under a common evaluation framework. The benchmark spans 51 datasets and evaluates six GFMs alongside 15 supervised methods under two label-availability regimes. Shared data partitions, validation-only model selection, controlled hyperparameter searches, and multiple predictive metrics make comparisons systematic, while workflow measurements account for adaptation, training, tuning, and inference. The results favor carefully tuned graph neural networks overall. GraphPFN reaches third place by Elo when more labels are available, yet its relative strengths vary substantially with dataset properties. Efficiency comparisons further qualify the benefits of pretrained reuse: GVT and GraphPFN appear on the Pareto frontiers when supervised methods are represented by their default and fully tuned configurations. Adding intermediate tuning budgets removes this advantage for GVT and leaves GraphPFN extending the estimated frontier in the label-rich setting alone. Thus, reusing pretrained parameters does not yet provide a broadly reliable route to either stronger predictions or cheaper workflows. We release the evaluation pipeline, run-level records, and an open leaderboard at https://github.com/nums-ai/nodeground.

0.45

Round-Trip KNN Clustering: multiscale hierarchical cluster detection on directed nearest-neighbour graphs

cs.LG stat.ML ·2026-10-05 ·Eraldo Pereira Marinho, Caetano Mazzoni Ranieri, Fabricio Aparecido Breve
benchmark similarity 0.59
Abstract · Submitted to Knowledge and Information Systems (KAIS). 32 pages, 6 figures

We introduce Round-Trip KNN Clustering (RTKNNC), a graph-based method for finding cluster structure at several neighbourhood scales without requiring the number of clusters in advance. Unlike approaches that first make a $k$-nearest-neighbour (KNN) graph undirected, RTKNNC keeps both directions of the neighbour relation: which points a given point selects and which points select it. Incoming selections are treated as weighted votes that help decide which local connections remain visible during a recursive forward-and-reverse traversal. Repeating the procedure for increasing $K$ reveals how groups persist or merge as the neighbourhood scale grows; for the reference inverse-square model before structural refinement, clusters can merge but do not split. Because graph connectivity can occasionally join distinct groups through a sparse bridge or a small region of overlap, we add an optional label-free refinement. It first tests whether an already formed component is better described by two or three Gaussian subpopulations, and accepts a subdivision only when the proposed groups are large enough and consistent with the visible KNN graph. Across eight synthetic datasets and $K=2,\ldots,16$, independent C and Python implementations produced identical partitions in all 120 reference runs. Refinement increased adjusted Rand index from $0.7817$ to $0.9627$ on a variable-density benchmark and from $0.8083$ to $0.9853$ on a sparse-bridge benchmark. Comparisons with seven external clustering methods show competitive performance while preserving a label-free cluster-construction process.

0.32

AutoHGNN: Robust and Efficient Neural Architecture Search for Hypergraph Neural Networks

cs.LG cs.AI ·2026-09-27 ·Sirui Li, Pietro Liò b, Xinsheng Li, Baisong Liu, Chengbin Peng
publishedbenchmark similarity 0.59
Abstract

Hypergraph neural networks have achieved significant success in recent years. However, manual architecture crafting is labor-intensive and often fails to capture complex, higher-order relations, making the automation of hypergraph neural network structure design crucial. To improve the automation and adaptability of hypergraph learning, this paper proposes AutoHGNN, a neural architecture search framework tailored for hypergraph neural networks. First, we introduce a Hyper-Interaction Module (HIM) into the search space to address the mismatch between conventional graph neural network designs and hypergraph data. Second, we propose Hypergraph Stable Topological Distance (HyperSTD) as a structural selection criterion to identify architectures that best preserve the intrinsic structural affinities of the original hypergraph during differentiable search. Extensive experiments on various benchmark datasets demonstrate that AutoHGNN consistently outperforms manually designed and automatically searched baselines in classification accuracy and time efficiency, proving that the discovered architectures are significantly more effective.

0.40

What Remains Without Leaking Test Labels? Exposing Evaluation Flaws in Graph-Level Anomaly Detection

cs.LG cs.SI ·2026-10-16 ·Yujie Lu, Da Yan
benchmark similarity 0.59
Abstract · v2: Retitled. Adds a replication in UB-GOLD's Type III scenario, two extra training seeds, and three analyses of where the checkpoint-select…

Graph-level anomaly detection (GLAD) identifies unusual graphs in applications such as molecular screening, often using only normal graphs for training. Yet the evaluations of some detectors select models with test labels, and high benchmark scores alone do not show whether detectors recognize structural changes. We audit released code and compare the area under the receiver operating characteristic curve (AUROC) for model states (checkpoints) chosen with and without test labels from the same training run. We separately compare test-tuned hyperparameters with repository defaults and test sensitivity to structural changes while controlling graph size. We evaluate 21 detectors on the UB-GOLD benchmark and on synthetic and molecular graphs with controlled structural changes. About half of the checkpoint-selection gain is linked to choosing a checkpoint and reporting its performance on the same labeled test set. The mean gap persists across training seeds and when normal and anomalous graphs come from different datasets. Most detectors miss many tested structural changes that simple counts detect. With tuned hyperparameters, the two leaders remain the top two by AUROC under every checkpoint rule. Across nine main datasets, test-label checkpoint selection raises the mean AUROC of UB-GOLD's 12 detectors by 5.12 points relative to the final checkpoint.

0.18