Graph Clustering

Follow this topic Ask about this topic

Momentum

7 papers in the last four weeks, up 133% on the four weeks before. 0.1% of all new papers.

Jul 13Week of Sep 28

Latest papers 53

Oct 6, 2026cs.LG

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

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.

Yunhui Liu, Xudong Jin, Kang Zhang +5

State Key Laboratory for Novel Software Technology Nanjing University Nanjing, China

Graph Representation Learning Graph Foundation Models Graph Clustering

Oct 5, 2026cs.LG

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

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.

Eraldo Pereira Marinho, Caetano Mazzoni Ranieri, Fabricio Aparecido Breve

Department of Statistics, Applied Mathematics and Computing, S˜ao Paulo State University (UNESP), Institute of Geosciences and Exact Sciences, Av. 24-A, 1515, Rio Claro, S˜ao Paulo, Brazil.

Clustering Hierarchical Clustering Graph Clustering k-Nearest Neighbors

Oct 1, 2026cs.AI

Neither Black nor White: Balancing Semantic and Collaborative Signals with Graph-Informed Semantic IDs (GrIS)

Existing work on Semantic IDs (SIDs) for generative recommendation treats SID construction as a representation learning problem: encode items into a quantised latent space and read off codes. We argue this view is incidental. SID construction is, at heart, a recursive clustering problem, and once stated this way the natural object to cluster is a graph whose nodes carry semantic content and whose edges carry collaborative signal; SID assignment becomes a hierarchical graph partition. This reframing yields a unified framework, Graph-Informed Semantic IDs (GrIS), that subsumes prior approaches rather than displacing them. RQ-VAE and RQ-KMeans are recovered as the special case where the graph is empty, exposing content-only quantisation as one corner of a larger design space along two so-far-collapsed axes: graph construction and recursive partition algorithm. We explore two contrasting instantiations: RecDMoN, which performs hierarchical assignment via differentiable graph pooling, and RQ-GAE, which extends RQ-VAE with graph-aware item representations and a graph reconstruction objective. On multiple real-world datasets, GrIS consistently improves over CF-aware SOTA, with gains of up to +52% Hit@10. Because graph construction and partition are explicit, separately configurable components, improvements on either axis can be combined and evaluated systematically.

Aleksei Medvedev, Alejandro Ariza-Casabona, Steven Derby +3

Huawei Ireland Research Centre Dublin, Ireland

Semantic ID Recommendation Graph Clustering Collaborative Filtering Generative Recommendation

Oct 1, 2026cs.SI

Degree-Corrected Joint Matrix Factorization for Multilayer Community Detection

Multilayer networks allow the modeling of interactions between the same entities across different contexts, such as temporal observations, varying settings, or interactions of different types. The goal of community detection in multilayer networks is to identify groups of nodes exhibiting similar connectivity patterns, which may vary across layers. We propose a method based on a joint nonnegative symmetric matrix trifactorization for community detection in multilayer networks, where each graph is approximated by a nonnegative symmetric matrix trifactorization. Our approach enforces constraints on the factor matrices so that communities are disjoint and shared across layers, while allowing each layer to have its own connectivity patterns and node degrees. This flexibility enables the model to capture both local and global structural variations across layers. We also develop an algorithm to efficiently solve this problem. We evaluate multilayer community detection methods using the multilayer degree-corrected stochastic block model (MDCBM), a flexible framework for generating realistic multilayer graphs with heterogeneous degrees and varying connectivity patterns. Experiments show that our method reliably detects communities across diverse regimes, whereas existing state-of-the-art approaches are often limited by restrictive structural assumptions.

Alexandra Dache, Manon Rustin, Arnaud Vandaele +1

Department of Mathematics and Operational Research, University of Mons, Mons, Belgium

Non-Negative Matrix Factorization Graph Clustering

Sep 28, 2026eess.SP

Hierarchical Clustering and Signal Denoising on Digraphs

In this paper, we propose a representation of a digraph (directed graph) as a Hermitian matrix derived from its adjacency matrix. This representation characterizes both the connectivity and the edge orientation of the digraph. Based on the spectral decomposition of the Hermitian matrix, a digraph clustering algorithm with

k

-means is introduced to produce a partition on the graph. Applying this algorithm (bottom-up) recursively to a digraph with partially labeled vertices yields a spectral hierarchical digraph clustering (\myproj) algorithm that produces consistent nested partitions of the digraph, or equivalently, a tree structure. Furthermore, based on the in-degree and out-degree of each cluster in the digraph clustering, a pair of hierarchical interval partitions (filtrations) can be derived in a top-down manner to produce a pair of nested knot sequences. These knot sequences facilitate the construction of multilevel spline quasi-interpolants, enabling a noisy graph signal to be decomposed into a coarse approximation and inter-level details, followed by adaptive thresholding and reconstruction. Experiments on synthetic and real-world digraphs demonstrate the superiority of our {\myproj} algorithm for digraph clustering across diverse graph structural properties (homophily and heterophily) and supervision settings. Moreover, experiments on digraph signal processing using multilevel spline quasi-interpolants further demonstrate the effectiveness of signal recovery on digraphs in terms of RMSE and SNR.

Yi Wang, Sippanon Kitimoon, Hrushikesh N. Mhaskar +1

Department of Mathematics, City University of Hong Kong, Hong Kong, SAR China · Data Science Research Center, Faculty of Science, Chiang Mai University, Chiang Mai 50200, Thailand · Institute of Mathematical Sciences, Claremont Graduate University, Claremont, CA 91711, USA

Graph Signal Processing Hierarchical Clustering Graph Clustering Spectral Methods

Sep 22, 2026cs.SI

Diffusion-Induced Spatial Attention Overlapping Community Detection

Detection of overlapping communities is essential for modelling networks in which nodes participate simultaneously in multiple structural or functional groups. Existing graph neural network approaches commonly rely on local message passing, which can obscure community boundaries through smoothing and limit the representation of structurally relevant long-range dependencies. We introduce Diffusion-Induced Spatial Attention Community Detection (DISCO), a deep-learning framework that combines a structural prior derived from influence spreading dynamics, sparse multi-head attention, and non-negative community-affiliation learning. The prior identifies candidate interactions beyond immediate graph neighbours and biases attention according to their structural proximity, while a Bernoulli-Poisson edge-reconstruction objective enables overlapping community inference from node attributes and structural profiles, or both. Benchmark experiments show that DISCO performs competitively against established graph convolutional and graph attention approaches across different input configurations. To demonstrate its practical applicability, we present a proof-of-concept cybersecurity use case in which changes between community assignments inferred from consecutive communication-network snapshots provide an interpretable anomaly signal. Temporal community similarity identifies structural deviations, while node-level contributions help locate the devices associated with them. DISCO therefore provides both a flexible method for overlapping community detection and a foundation for analysing structural change in dynamic networks.

Kosti Koistinen, Vesa Kuikka, Joni Herttuainen +3

Aalto University School of Science Computer Science Department P.O.Box 11000, 00076 AALTO, Finland · Lockheed Martin USA

Graph Attention Networks Graph Clustering

Sep 21, 2026cs.LG

G-NAC: Graph Neural Automata Clustering via Emergent Domain Formation

We introduce Graph Neural Automata Clustering (G-NAC), an unsupervised clustering method in which observations interact as cells on a fixed neighborhood graph. A shared recurrent graph-neural cellular rule evolves latent domain states through local interactions, which are converted into a rank-based spectral affinity for partitioning. Across 73 clustering tasks from 57 benchmark datasets, G-NAC achieved a mean adjusted Rand index (ARI) of 0.7951, comparable to Genie at 0.7941 and higher than the other evaluated baselines. Empirical training time and GPU memory scaled approximately linearly from 5,000 to 100,000 nodes. Learned transition rules also transferred from smaller source graphs to independent 100,000-node samples generated under matched conditions. These results demonstrate a recurrent graph-clustering formulation while identifying dependencies on graph quality, readout design, and source-target similarity.

Keith Miller, Tristan Crawford

Graph Neural Networks Unsupervised Clustering Graph Clustering

Sep 14, 2026cs.LG

When Connected Does Not Mean Similar: Charting the Homophily Boundary of SNAP-KG for Streaming Entity Integration

SNAP-KG is a framework for assigning newly arriving entities to semantic communities in a growing knowledge graph (KG) using only their raw features, with no graph access and no retraining at inference time. It was evaluated on five multi-view benchmarks and a 2.4M-node OGB-WikiKG2 KG. In each of these datasets, at least one graph view is homophilous, meaning that connected nodes usually belong to the same class, and SNAP-KG performs well on all of them. This paper asks what happens outside that setting. We extend the evaluation to three heterophilous graphs (Texas, Wisconsin, Chameleon) and measure the edge homophily of every view. When no homophilous view is available, clustering quality drops sharply for both SNAP-KG and the transductive baselines used in its original evaluation. What decides this is the homophily of the relation, not the number of relations. Multi-view fusion still helps, but only when at least one homophilous relation provides a reliable foundation. The homophily assumption is therefore shared by the whole method family, not specific to SNAP-KG. We argue that heterophilous multi-view clustering is a separate research problem, outside the scope of this work. As future work, we outline how a heterophily-aware teacher could be distilled into SNAP-KG's projector to serve both homophilous and heterophilous KGs.

Jui-Chien Lin, Oshani Seneviratne

Rensselaer Polytechnic Institute, Troy, NY 12180, USA

Multi-View Clustering Graph Clustering Knowledge Graphs Graph Heterophily

Sep 14, 2026cs.AI

Geometric Flow enhanced Graph Coarsening

Recently, researchers have proposed a graph pooling operation, akin to the pooling process in conventional convolutional neural networks (CNN), aimed at reducing the computation cost of Graph convolutional neural networks (GCNNs). While most GCNN-based methods treat graph pooling as a node clustering problem and propose learning a cluster assignment matrix, existing clustering-based pooling methods tend to focus solely on the rough topology information of graphs, neglecting the exploitation of higher-order mutual connections among neighbors. In terms of message passing on graph, the ease of information passing on edges reflects the closeness between neighboring nodes, which significantly relies on the interconnectivity among neighbors. In this study, we address this gap by considering such local connection information and introducing a novel graph pooling method named RicciPool. We introduce discrete graph curvature, particularly Ollivier-Ricci curvature, as a measure of higher-order connectivity around an edge. Subsequently, we construct an Ollivier-Ricci flow formula to reweigh edge weights, leveraging the crucial information provided by Ricci curvature, particularly vital for extracting clusters in graphs. Building upon this foundation, we utilize the spectral clustering technique to learn a new cluster assignment matrix. Experimental results on multiple bioinformatics protein datasets and social networks underscore the effectiveness of our proposed method.

Chaoqun Fei, Guoxuan Li, Tinglve Zhou +2

Graph Neural Networks Graph Coarsening Graph Pooling Clustering Graph Clustering

Sep 3, 2026cs.LG

Selective Hypergraph Refinement for Frozen Graph Clustering

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.

Zimo Si

Department of Mathematics, Faculty of Science, University of Macau · Macao SAR, China

Clustering Graph Clustering

Sep 1, 2026cs.LG

Refining Heuristic-Based Bitcoin Address Clustering with Graph Neural Networks

Bitcoin's pseudonymous nature makes it challenging to analyze user-level activity, since a single user may control multiple identifiers (addresses). Existing heuristic-based methods attempt to identify addresses belonging to the same user, but they often produce flat cluster assignments with limited modularity and are prone to errors such as merging different users together. In this work, we propose a method for refining heuristic-obtained clusters by grounding our clustering on contrastive embeddings yielded by graph neural networks. Our contributions are threefold: (i) we release a publicly available dataset of Bitcoin transaction graphs containing a substantial number of clusters; (ii) we propose a methodology for learning address embeddings consistent with heuristics, and back it up with theoretical guiding intuitions; (iii) through hierarchical clustering, we enable a finer analysis of heuristic clusters and provide a quantitative criterion for flagging suspicious merges.

Hugo Schnoering, Roman Bresson, Michalis Vazirgiannis

École Polytechnique, Institut Polytechnique de Paris, France · Mohamed bin Zayed University of Artificial Intelligence, Abu Dhabi, UAE

Graph Neural Networks Graph Representation Learning Clustering Graph Clustering

Aug 11, 2026cs.SI

Spectral graph clustering with inhomogeneous latent geometry

We study spectral clustering in the presence of a confounding latent geometry. The leading eigenvectors may then be dominated by the latent geometry rather than by the communities. Nevertheless, we show in a block latent-space model that communities can be recovered from eigenvectors deeper in the spectrum. We analyze the spectral properties of the adjacency matrix through a limiting integral operator and use its structure to develop DBSPEC, a density-based spectral clustering algorithm that requires only approximate localization of the informative eigenvalue and is robust to poor eigenvalue separation. Crucially, this approach handles general latent geometries, overcoming restrictions to homogeneous toroidal models in prior works. Our theoretical predictions for the location of the informative eigenvalue notably align with observations in real-world experiments.

Konstantin Avrachenkov, Lucas S. Sibemberg, Alexander Van Werde

Inria Sophia Antipolis, France · Federal University of Rio Grande do Sul, Brazil · University of Münster, Germany

Spectral Clustering Graph Clustering Spectral Methods

Aug 7, 2026cs.LG

Density-aware Hierarchical Clustering Based on Element-Categorized Connection Subgraphs

Clustering is a fundamental data mining technique for pattern recognition through unsupervised learning. Among various clustering methods, hierarchical clustering, density-based clustering, and graph clustering stand out as representative approaches. For hierarchical clustering, it can be categorized into agglomerative and divisive modes to construct clusters in a recursive manner. The key aspect of both modes is the calculation of inter-cluster similarity, which determines whether to merge the sub-clusters into one cluster or divide a current cluster into sub-clusters. Traditionally, the similarity is derived from pairwise distances, often overlooking density variations and structural connectivity in graphs. To address this, we propose a density-aware hierarchical clustering method based on element-categorized connection subgraphs (DHC-ECS), which effectively integrates the hierarchical clustering, density-based clustering, and graph clustering. Particularly, a novel inter-cluster similarity metric is introduced that considers not only distances but also the element categorization in the KNN connection subgraphs, kernel density estimation, and local connectivity within sub-clusters. Extensive evaluations on heterogeneous benchmark datasets demonstrate that DHC-ECS exhibits superior overall performance in terms of clustering accuracy and parameter robustness compared with the baseline methods (including AChameleon, RNN-DBSCAN, McDPC, and G-RMS). The work indicates the great potential of the proposed clustering algorithm for low-dimensional datasets by leveraging local density and graph-structured connectivity (i.e., the duality of vertices and edges), as well as the possibility to determine an intrinsic threshold, reducing the reliance on manual parameter tuning.

Yuning Yu, José Rodríguez-Piñeiro, Xuefeng Yin +1

Tongji University, Shanghai, China · RadioSky (Shanghai) Communication Technology Co., Ltd, Shanghai, China

Clustering Hierarchical Clustering Graph Clustering

Aug 4, 2026cs.LG

Learning and Clustering on Temporal Graphs: Principles, Primitives, and Pooling

This work focuses on the problem of learning on temporal graphs, with particular emphasis on the task of clustering: obtaining coarse-grained representations by aggregating information from nodes, edges, and temporal dynamics - a task related to pooling in machine learning on graphs, or community detection in network science. Although graph neural networks reach state-of-the-art performance across many downstream graph tasks, their advantage over established descriptive and inferential clustering algorithms is far less settled, especially under demands of efficiency and recovery accuracy. We frame this tension through three linked perspectives: principles, connecting graph learning and community detection through shared spectral foundations and detectability thresholds in stochastic block model regimes; primitives, making spectral clustering and multislice modularity optimization tractable through GPU-accelerated temporal backends; and pooling, viewing principled community detection as a theory-grounded coarse-graining operator for temporal graphs. Our results indicate that algorithmic methods remain the appropriate tool where attributes are absent or weak - scalability rather than accuracy being the binding obstacle - while neural models are most compelling when structural, temporal, and attribute signals align. By making temporal clustering scalable, GPU-accelerated primitives suggest a route toward theory-grounded pooling, while raising a central question: when does community-based coarse-graining preserve the dynamics needed for downstream learning tasks?

Nelson Aloysio Reis de Almeida Passos, Emanuele Carlini, Salvatore Trani

University of Pisa, Dept. of Computer Science, 56127 Pisa PI, Italy · National Research Council, 56124 Pisa PI, Italy

Graph Neural Networks Graph Pooling Clustering Spectral Clustering Stochastic Block Model Graph Clustering

Aug 4, 2026cs.DC

Accelerating Dynamic Graph Clustering on GPU Architectures with cuGraph

This work addresses community detection in temporal networks through GPU-accelerated extensions of spectral clustering and modularity-based algorithms originally designed for static graphs. Built on the NVIDIA RAPIDS ecosystem, the framework enables the characterization and tracking of communities in snapshot-based dynamic graphs, either by Leiden greedy optimization with multi-GPU support via Dask-based workload distribution, or eigendecomposition of a symmetric Bethe-Hessian operator. Our multislice modularity backend achieves up to roughly three orders of magnitude speedup over the CPU reference under an equal-work budget, depending on graph density and snapshot count, while preserving compatibility with existing graph analytics pipelines. We demonstrate its applicability on real-world and synthetic datasets, facilitating exploratory analysis of structural network properties over time. Such capabilities are relevant across several application domains, such as epidemic spreading, financial systems, cybersecurity, and trajectory and mobility analysis. We release our implementation as free and open-source software, including Python bindings through the NetworkX-Temporal library for ease of use and zero-code acceleration with existing codebases.

Nelson Aloysio Reis de Almeida Passos, Emanuele Carlini, Salvatore Trani

University of Pisa, Dept. of Computer Science, 56127 Pisa PI, Italy · National Research Council, 56124 Pisa PI, Italy

GPU Acceleration Clustering Dynamic Graph Learning Spectral Clustering Graph Clustering

Aug 2, 2026cs.AI

Interpretable Unsupervised Community Detection with LLM-Symbolized Structured Processes

Community detection is a fundamental task in graph analytics that aims to identify cohesive groups of entities with similar behaviors or interests. Classic objective-driven methods struggle with complex graph structures, while deep-learning approaches improve performance at the expense of interpretability and rely on labeled data and training. Large language models (LLMs), with strong reasoning capabilities and world knowledge, are promising for interpretable, label-free community detection. To leverage these strengths, we propose LUCID, an LLM-guided, interpretable, training-free, and unsupervised community detection method. Inspired by phase-transition kinetics in natural systems, where complex structures emerge through initialization, merging, refinement, and selection, LUCID is designed as a four-stage pipeline. Within this pipeline, the LLM induces formal rules that translate implicit knowledge into explicit and interpretable logical structures. Specifically, (1) the Local-View Community Initialization stage encodes local graph structures using k-ego contexts and unsupervised node roles; (2) the Multi-factor Community Merge stage uses LLM-induced rules to iteratively merge local communities; (3) the Multi-grain Community Refinement stage applies LLM-induced coarse-to-fine rules in parallel to reduce boundary noise; and (4) the Global-view Community Selection stage identifies high-quality communities based on topological compactness and boundary clarity. Extensive experiments on real-world datasets demonstrate that LUCID, as an unsupervised approach, achieves state-of-the-art performance and consistently outperforms leading unsupervised and semi-supervised baselines.

Aoting Zeng, Kai Wang, Jianwei Wang +3

Shanghai Jiao Tong University Shanghai, China · University of New South Wales Sydney, Australia

Unsupervised Learning Interpretable ML Graph Clustering LLMs for Graph Learning

Aug 1, 2026cs.LG

RHEA: Reliability-Harmonized Reconstruction and Assignment for Robust Multimodal-Attributed Graph Clustering

Multimodal-attributed graphs (MAGs), whose nodes carry heterogeneous attributes such as text and images over a relational structure, have become a fundamental substrate for label-free entity grouping tasks, including community discovery and product segmentation. Existing MAG clustering methods effectively integrate complementary modalities when attributes are clean and complete, but degrade substantially under noisy or missing attributes because they implicitly assume equal modality reliability across all nodes. In practice, modality reliability is inherently node-specific: images may be corrupted or absent, while textual descriptions are incomplete or noisy. We argue that, under attribute homophily, graph neighborhoods naturally provide supervision-free evidence for estimating node-specific modality reliability. Based on this insight, we propose RHEA, a reliability-aware framework for MAG clustering that estimates node-specific modality reliability from neighborhood consensus and propagates this signal throughout the clustering pipeline. RHEA reconstructs unreliable or missing modalities from graph neighborhoods, adaptively weights modalities during reliability-aware fusion, and performs topology-aware optimal transport clustering with reliability-aware transport assignment and neighbor-consensus assignment distillation. Furthermore, the confidence of reconstructed representations is incorporated into the clustering objective, allowing uncertain reconstructions to contribute proportionally during optimization. Experiments on four MAG benchmarks under five attribute conditions show that RHEA consistently outperforms the strongest baseline, with NMI gains increasing as attribute quality deteriorates.

Yinlin Zhu, Di Wu, Ziyu Han +4

Sun Yat-sen University, Guangzhou, China1 · Shandong University, Weihai, China2 · Beijing Institute of Technology, Beijing, China3

Multimodal Robustness Clustering Graph Clustering Multimodal Fusion

Jul 29, 2026cs.LG

MPP-GNN: Subject-Adaptive Community Detection for fMRI-Based Alzheimer's Disease Classification

Functional magnetic resonance imaging (fMRI) is a widely used technique for studying the brain. Recent methods that utilize graph neural networks (GNNs) for analysis of brain functional connectivity have shown great potential for the classification of brain disorders, such as Alzheimer's disease (AD). However, these methods often assume a preset number of functional modules across all subjects, which overlooks inter-subject variability. In addition, the discovered modules are rarely used to directly guide the learned connectivity patterns. Here, to address these issues, we propose a Meta Probabilistic Pooling GNN (MPP-GNN). We frame the model's task as a coupled, bilevel optimization that performs adaptive graph partitioning hierarchically to discover subject-specific modules and then uses the discovered brain modules as an explicit prior to guide edge refinement and representation learning. We validate MPP-GNN on two public datasets for AD classification, achieving the highest AUC in comparison to established baselines for both datasets. Furthermore, our analysis demonstrates that MPP-GNN shows significant alignment with the canonical functional-network organization defined by the Yeo brain atlas and reveals a network-level dedifferentiation pattern for AD.

Yang Zhang, Xiao Zhou, Jonathan Warrell +3

Graph Neural Networks Graph Pooling Medical Image Classification Graph Clustering Alzheimer's Disease Classification Neuroimaging

Jul 27, 2026math.OC

A Foundational Perspective for Partitional Clustering on Networks

This study presents a theoretical analysis of partitional clustering on networks, analyzing both hard and soft assignment schemes with different objective functions. Cluster centers are not restricted to vertices but can also be located along the edges. We examine four key models: P-Median (PMP) and Sum of Squares Clustering (SSC) under hard assignment, and Probabilistic Distance Clustering (PDC) and Fuzzy C-Means (FCM) under soft assignment. Through mathematical analysis, we uncover structural properties that differentiate these models, such as the significance of assignment bottleneck points and the role of vertex-restricted solutions in determining optimal cluster centers. Our findings reveal that, while SSC and FCM can yield optimal centers along edges, PMP and PDC inherently favor vertex placement, leading to insights into clustering behavior on networks. These insights offer new directions for designing efficient algorithms and have implications ranging from facility location and network design to clustering on the embedding graphs that power similarity search in modern retrieval systems.

Derya Ipek Eroglu, Cem Iyigun

Computing Sciences, SUNY Brockport, 350 New Campus Drive, Brockport, 14420, New York, USA · Industrial Engineering, Middle East Technical University, Üniversiteler Mahallesi, Dumlupınar Bulvarı No:1, 06800, Ankara, Turkey

Clustering Combinatorial Optimization Graph Clustering

Jul 23, 2026cs.LG

Regularized Optimization on Grassmann Manifold: Theory, Algorithm and Applications

Spectral methods are among the most widely used techniques for community detection, clustering, and graph learning. Their performance, however, critically depends on the accurate estimation of the underlying spectral subspace and can deteriorate substantially in the presence of noise, outliers, or model perturbations. To address this limitation, we propose a Regularized Projection Matrix Approximation (RPMA) framework for robust estimation of rank-

K

projection matrices. RPMA extends classical spectral projection by incorporating a regularization term, producing projection estimates that are more robust, sparse, and interpretable. We formulate the proposed model as an optimization problem on the manifold of rank-

K

projection matrices and exploit its geometric equivalence to the Grassmann manifold. Based on this manifold characterization, we derive the first- and second-order optimality conditions, establish the local stability of the regularized leading eigenspace, and characterize the stability of the critical-point landscape under sufficiently small regularization. To efficiently solve the resulting nonconvex optimization problem, we develop a Riemannian gradient projection algorithm with backtracking line search, together with a more efficient Cayley--Sherman--Morrison--Woodbury (Cayley--SMW) gradient method that avoids repeated eigendecompositions. Extensive experiments on both synthetic and real-world datasets demonstrate that RPMA substantially improves the recovery accuracy of projection matrices and consistently outperforms conventional spectral projection methods for community detection and clustering under noisy environments.

Zhuan Liang, Zheng Zhai

Department of Statistics, Faculty of Arts and Sciences at Beijing Normal University, Zhuhai

Spectral Regularization Riemannian Optimization Nonconvex Optimization Graph Clustering Spectral Methods

Jul 17, 2026cs.CV

DS@GT ARC at AnimalCLEF 2026: Species-Aware Graph Construction for Multi-Species Animal Re-Identification

Automated individual animal re-identification is essential for large-scale biodiversity monitoring; however, field imagery complicates separating identity cues from nuisance variation in pose, illumination, background, resolution, and species-specific morphology. The DS@GT ARC submission to AnimalCLEF 2026 introduces a multi-species image-clustering system for re-identifying Eurasian lynx, fire salamanders, loggerhead sea turtles, and Texas horned lizards. Instead of relying on a single descriptor or nearest-neighbor retrieval, this approach formulates re-identification as species-aware graph construction over candidate image pairs. The pipeline integrates tailored preprocessing, global candidate retrieval, LightGlue-based local verification with multiple keypoint families, LightGBM pair scoring, conservative edge admission, and Leiden community detection. This design directly addresses a primary failure mode of clustering-based re-identification: high-scoring false pairs that act as bridge edges and merge distinct individuals through transitive closure. Across species, ablation studies demonstrate that local feature support, foreground-aware preprocessing, and species-specific backbone selection enhance pair evidence, while graph operating points determine the trade-off between fragmentation and over-merging. The selected submission achieved a public ARI of 0.733 and a private ARI of 0.674, ranking fifth among 230 teams. These results indicate that robust wildlife re-identification requires not only strong visual representations but also calibrated integration of global similarity, local identity markings, neighborhood context, and graph-level constraints. The code can be found at https://github.com/dsgt-arc/animalclef-2026.

Evan Sinclair Smith, Anthony Miyaguchi, Snigdha Palamari +1

1Georgia Institute of Technology, North Ave NW, Atlanta, GA 30332

Animal Re-Identification Image Matching Graph Clustering Wildlife Monitoring

Jul 15, 2026stat.ML

Spectral Concentration and Recovery in Sparse High-Dimensional Random Geometric Graphs

We study sparse random geometric graphs generated by connecting pairs of high-dimensional vectors whose inner product exceeds a threshold. The latent vectors are sampled either uniformly from the sphere or from a standard Gaussian distribution. Although every edge appears with probability

p

, the edges are dependent through their shared latent vectors. For the spherical model, at the connectivity scale

np=Ω(\log n)

, we prove

\|A-\mathbb E A\|=O\left(\sqrt{np\log n}+npτ\right)

, with high probability, where

τ

is the cap threshold. This sharpens the spectral norm bound of Liu, Mohanty, Schramm, and Yang (2023) under weaker assumptions. An analogous result holds for the Gaussian model after removing the fluctuations of the vector norms, yielding improved global synchronization guarantees for the homogeneous Kuramoto model. We then recover the latent geometry from the leading eigenspace. When

np\gg\log n

, both the latent vector and relative Gram matrix errors vanish provided

d\ll np\log(1/p)/\log n

. The required lower dimension is only

d\gg\log(1/p)

for the spherical model and

d\gg\log^2(1/p)\log n

for the Gaussian model, improving the recovery guarantees of Li and Schramm (2023). Finally, we prove the first exact recovery result for the Gaussian mixture block model of Li and Schramm (2023). At the optimal connectivity scale

np=Ω(\log n)

, a polynomial-time semidefinite program exactly recovers all labels in a moderate-separation regime, whereas larger separation makes exact recovery impossible because isolated vertices appear with high probability. Our proofs combine orthogonal polynomial expansions, decoupling, and matrix concentration, avoiding the trace-moment arguments used in previous work.

Manuel Fernandez, Yizhe Zhu

Department of Mathematics, University of Southern California

Graph Clustering Spectral Methods

Jul 14, 2026cs.DS

Hierarchical $\mathcal{F}$ -Clustering: Approximation and Hardness of Clustering into Trees and Bounded Diameter Graphs

Consider the following variation on the Hierarchical Clustering problem: Usually, while building a hierarchical clustering, one recursively partitions the data until each cluster becomes a singleton. We relax the halting condition of the recursive process to stop whenever the remaining cluster is a graph belonging to a class

\mathcal{F}

. We call this problem Hierarchical

\mathcal{F}

-Clustering and we measure the quality of any solution using adapted Dasgupta's clustering objective. We study two natural choices of

\mathcal{F}

: trees and graphs of bounded diameter. We present the first polynomial time

\mathcal{O}(\log n\cdot\log\log n)

and

\mathcal{O}(\log n)

-approximation algorithms for clustering into trees and bounded diameter graphs respectively. Our main technical contribution is a framework for approximating such problems based on linear programming. In fact, we characterize graphs classes

\mathcal{F}

for which our approach can be applied and show that it includes both trees and bounded diameter graphs. However, our ideas are not limited to them and might be useful for other structures as well. Broadly speaking, our framework applies whenever the corresponding flat clustering problem, which we call

p_{\mathcal{F}}

-Partitioning, admits a natural ILP formulation together with a rounding procedure with provable approximation guarantees. Intuitively, given a set of vertices called terminals, the problem is to find an edge set whose removal results in satisfying certain vertex-dependent structural predicate for each terminal. We then use these ingredients to build clustering trees with the aforementioned approximation guarantees. To complement these results, we show that both Hierarchical Clustering into trees and into bounded diameter graphs cannot be approximated within any constant factor under the Small Set Expansion Hypothesis.

Michał Szyfelbein, Dariusz Dereniowski

Gda´nsk University of Technology

Hierarchical Clustering Graph Clustering Approximation Algorithms

Jul 6, 2026cs.LG

Breaking Structural Isolation: Scalable Graph Clustering via Community-Aware Sampling and Structural Entropy

Unsupervised graph clustering is a fundamental technique for uncovering underlying semantic patterns in large-scale networks. Although Graph Contrastive Learning has demonstrated promising performance, existing methods often suffer from the "structural isolation" issue during mini-batch training, making it challenging to capture cohesive community structures that characterize the global topological distribution. To address these challenges, we propose SCISE, a Scalable unsupervised graph Clustering framework that preserves structural Integrity by synergizing community-aware sampling with constrained Structural Entropy. Specifically, we first introduce the Structural Entropy Community Constraint operator (SECC), which optimizes structural information within a constrained solution space to mitigate community fragmentation and enhance partition cohesion. Second, to prevent global information loss during batch training, we design a Community-Aware Sampling Expansion (CSampE) mechanism that incorporates the community context of target nodes into sampling batches, effectively breaking structural barriers and preserving topological integrity. Finally, we devise a Structural Contrastive Learning (StructCL) module that refines edge weights based on intra-batch structural similarity, guiding the encoder to learn representations in a higher-order structural space. Extensive experiments on six mainstream benchmark datasets demonstrate that SCISE significantly outperforms state-of-the-art algorithms, with ablation studies and robustness analyses further validating its effectiveness and reliability for real-world large-scale graphs.

Jingyun Zhang, Hao Peng, Jianxin Li +2

Beihang University Beijing, China · Hangzhou Innovation Institute, Beihang University Hangzhou, China · University of Illinois at Chicago Chicago, USA

Graph Clustering Graph Contrastive Learning

Jul 3, 2026stat.ME

CaSPECT: Discovering Causally Homogeneous Subgroups via Directed Spectral Clustering

We propose \textbf{CaSPECT}, a causal spectral clustering framework for discovering causally homogeneous subgroups from observational data. Rather than clustering in covariate space, CaSPECT defines similarity through the topology of a learned directed acyclic graph (DAG); a bootstrap-stabilised PC algorithm recovers the causal skeleton; a novel \emph{Orientation Validation Score} (OVS) combines PC bootstrap evidence with DirectLiNGAM to orient edges robustly; directed edges are weighted by backdoor-identified average treatment effects estimated via OLS or double machine learning. Chung's directed Laplacian provides a spectral embedding in which individuals close together share the same causal propagation pathways. We establish almost-sure consistency of the full pipeline and validate the method through a controlled simulation study and on LaLonde CPS1, IHDP, and 401(k) datasets, where CaSPECT recovers a positive and statistically significant treatment effect within the causally comparable subpopulation and corrects for severe confounding without requiring a pre-specified propensity score model.

Arghya Pratihar, Shinjon Chakraborty, Swagatam Das

1*Electronics and Communication Sciences Unit, Indian Statistical Institute, India. · 2Indian Statistical Institute, India.

Causal Effect Estimation Causal Structure Learning Spectral Clustering Graph Clustering Causal Inference

Jun 29, 2026cs.LG

Curvature-Guided Sheaf Diffusion for Unsupervised Community Detection on Heterophilic Graphs

Detecting communities in heterophilic graphs -- where connected nodes often belong to different classes -- is hard for unsupervised methods: classical modularity and spectral methods are feature agnostic, while deep graph-clustering methods rely on contrastive or generative machinery that is opaque. We propose Curvature-Guided Sheaf Diffusion (CGSD), a fully unsupervised community-detection algorithm that uses the discrete Forman--Ricci curvature of each edge as its single topological signal, propagated through every stage of an end-to-end pipeline. CGSD makes three concrete contributions: (i)~a curvature-gated sheaf-diffusion encoder that gates edge messages by

σ(κ_e)

and is trained from three label-free structural losses (modularity, anti-collapse, curvature-weighted reconstruction); (ii)~a curvature-aware spectral clusterer (CSpec) that re-weights the

k

-NN affinity of the embedding by

σ(ακ_{e^*})

before Ng--Jordan--Weiss; and (iii)~a unified label-free evaluation against nine truly-unsupervised baselines. On five heterophilic benchmarks (Cora, Cornell, Texas, Wisconsin, Chameleon), CGSD wins outright on Wisconsin and Chameleon and is competitive on the remaining three against nine unsupervised baselines. The gain over the strongest baseline is driven by the clusterer, not the encoder: on the same embedding, CSpec improves mean NMI from

0.091

with

K

-Means to

0.107

(

+15\%

, paired

t

-test

p=0.008

). The mechanism is interpretable: intra-community and inter-community curvature distributions are visibly separated. Code is open-sourced at https://github.com/woodywff/cgsd.

Feifan Wang

School of Artificial Intelligence Xiamen Institute of Technology No. 1251, Sunban South Road, Jimei District Xiamen, Fujian 361021, China

Graph Representation Learning Graph Clustering Graph Heterophily Graph Diffusion

Jun 29, 2026cs.CV

Progressive Self-Supervised Learning with Individualized Community Assignment for Brain Network Analysis

Brain networks exhibit a modular community structure that varies across individuals and neurological conditions. However, existing self-supervised learning (SSL) methods often overlook this heterogeneity, relying on generic masking strategies that fail to capture subject-specific functional organization. We propose BrainPICM, a self-supervised framework for brain network analysis via progressive individualized community aware masking. BrainPICM formulates ROI-to-community mapping as a progressive unbalanced optimal transport process, yielding soft assignments and per-ROI confidence scores. Guided by these confidence estimates, a curriculum-style masking strategy gradually incorporates low-confidence, potentially pathological regions into training, enabling the model to learn both stable modular structures and individual variations. Additionally, a deviation-aware aggregation module quantifies functional reorganization by measuring mass redistribution relative to a population template, enhancing interpretability and downstream prediction. Experiments on three fMRI datasets (ABIDE-I, ADHD-200, ADNI) show that BrainPICM consistently outperforms state-of-the-art supervised and SSL methods in diagnostic accuracy, indicating that explicitly injecting modular community structure into masked modeling yields more functionally consistent and generalizable representations. The source code for this approach will be released at https://github.com/Hrychen7/BrainPICM.

Hairui Chen, Yanwu Yang, Jianfeng Cao +3

Harbin Institute of Technology at Shenzhen, Shenzhen, China · Peng Cheng Laboratory, Shenzhen, China · University of Tübingen, Tübingen, Germany +1

Self-Supervised Learning Graph SSL Graph Clustering Neuroimaging Brain Network Analysis

Jun 26, 2026cs.LG

scKDGM: KAN-guided Dynamic Graph Masked Learning for Single-Cell RNA-seq Clustering

Single-cell RNA sequencing (scRNA-seq) clustering is essential for identifying cell types, but high dimensionality, sparsity, dropout, and technical noise hinder robust expression representation and cell graph construction. Existing masked autoencoders mainly use expression recovery for feature reconstruction, while graph clustering methods usually depend on fixed KNN graphs and do not feed recovered expression back into graph optimization. We propose scKDGM, a KAN-guided dynamic graph masked learning framework for scRNA-seq clustering. scKDGM uses graph-aware distribution preserving gene masking (GDP-Mask) to perturb cell identity, a KAN-based TAKGCN encoder to learn masked-view representations, mask-guided expression recovery to construct a dynamic graph, and cross-view contrastive learning to transfer recovery signals into topology updates. A ZINB loss models overdispersion and zero inflation. Experiments on 12 real scRNA-seq datasets show that scKDGM outperforms 10 baselines in average NMI and ARI.

Jun Tang, Pengwei Hu, Sicong Gao +3

College of Computer and Information Science, Southwest University, Chongqing, China · Xinjiang Technical Institute of Physics and Chemistry, Chinese Academy of Sciences, Urumqi, China

Graph SSL Clustering Dynamic Graph Learning Graph Clustering Single-Cell RNA Sequencing

Jun 22, 2026cs.LG

Collapsed Effective Operators for Higher-order Structures

Higher-order structures are powerful relational modeling tools, yet existing spectral operators decompose the topology into separate ranks, leaving practitioners to fuse the information back to vertices through ad hoc choices. We introduce Collapsed Effective Operators, which condense higher-order degrees of freedom into a single vertex-level operator via Schur complementation of a graded Laplacian. This yields a (generally dense) operator that encodes long-range interactions mediated by topology and is applicable to arbitrary higher-order constructs. We show it preserves positive semi-definiteness with a spectral upper bound relative to the rank-0 Hodge Laplacian, effectively lowering system energy under higher-order connectivity. Empirically, our operator improves spectral clustering, signal smoothing, and enables the inclusion of topological features in neural network architectures via positional encoding. The project page can be found http://circle-group.github.io/research/CollapsedEffectiveOperators

Maximilian Krahn, Lennart Bastian, Vikas Garg +2

Department of Computing, Imperial College London, London, UK · Chair of Health Informatics, Technical University of Munich, Germany · Munich Center for Machine Learning, Germany +2

Graph Clustering Spectral Methods Topological Data Analysis

Jun 22, 2026cs.LG

Bridge the Gaps: Heterogeneous Attributed Graph Clustering via Quaternion Representation Learning

Attributed graph clustering partitions nodes by jointly exploiting node attributes and graph topology. It remains challenging due to attribute heterogeneity and representation degradation during graph learning. Real-world datasets often contain heterogeneous attributes, i.e., numerical and categorical attributes, complicating unified representation learning. This challenge becomes more complex in attributed graphs, where constructing a clustering-friendly graph structure from attributes and topology remains difficult. Under deep graph architectures, repeated graph propagation causes node embeddings to become overly similar, leading to the over-smoothing (OS) effect. Meanwhile, graph representation learning amplifies topological influence, making discriminative attribute information harder to exploit for clustering, an effect we refer to as over-dominating (OD). To bridge these gaps, an end-to-end framework, Any-type attributed Graph REpresentation lEarning (AGREE), is proposed. It unifies attributed graphs and any-type attributed data through multi-level alignment and similarity-based graph construction. Quaternion-based graph convolution strengthens attribute interaction to alleviate OD, while shallow graph architectures help relieve OS. The learned embeddings are jointly optimized for graph reconstruction and clustering, without requiring a predefined number of clusters during training. Experiments on diverse benchmarks show that AGREE achieves strong overall performance in accuracy, robustness, and adaptability.

Xinxi Chen, Junyang Chen, Yiqun Zhang +2

School of Computer Science and Technology, Guangdong University of Technology, Guangzhou 510006, China

Graph Structure Learning Graph Neural Networks Graph Representation Learning Graph Clustering