CS Paper Radar

T-ARC: Topology-Aware Randomized Clustering via Distributionally Robust Stochastic Block Models

Serena Grazia De Benedictis, Andersen Ang, Nicoletta Del Buono, Flavia Esposito, Laura Selicato

cs.LG math.ATmath.OC ·submitted 2026-09-30 10:30 UTC · v2

Abstract

In this work, we introduce a new clustering method, namely T-ARC (Topology-Aware Randomized Clustering), that corrects the geometric bias of K-means by embedding topological information directly into the optimization objective. Building on the assumption that the data admits an underlying hidden structure modeled via a latent graph, the idea is to uncover this information through the interplay between the standard K-means data-fidelity term and a graph-cut penalty, which discourages cluster assignments inconsistent with the connectivity structure of the data. To render this coupling tractable, the latent graph is modeled as a random realization from a Stochastic Block Model (SBM), whose scalar parameter is optimized within a Distributionally Robust Optimization (DRO) framework, yielding a closed-form proximal update. Both SBM and DRO are informed by a persistence-based similarity matrix derived from zero-dimensional persistent homology ($H_0$), which translates the multiscale connectivity structure of the data into a pairwise topological prior. The overall optimization proceeds via Block Coordinate Descent; convergence is established through a global Lyapunov functional: the deterministic blocks satisfy monotonic descent, while the stochastic graph update satisfies descent in expectation, so that the expected energy converges. Experiments on synthetic datasets with non-convex geometries and on random subsets of Fashion-MNIST show that T-ARC recovers latent topological structures where K-means fails, achieving the highest accuracy on curved and interleaved clusters while remaining competitive, and markedly more stable than K-means, on real data.

Comment
20 pages, 17 figures. Preprint

Closest papers

Nearest neighbours by meaning across the whole index.

Dual-Corrected Stochastic Block Model ($\text{DC}^2\text{SBM}$): A Generalized Structure Detection Method for Attributed Networks

cs.SI cs.LGstat.ML ·2026-10-23 ·Zhenhai Chang, Shuo Wang, Yumeng Liu, Wei Liu
similarity 0.63
Abstract · 24 pages, 8 figures

Community detection in attributed networks is one of the core tasks of complex network analysis. The stochastic block model (SBM) and its variants are able to detect generalized network structures such as assortative, disassortative and mixed structures. However, existing generative methods either ignore node heterogeneity, or characterize node activity in the topological and attribute dimensions by one and the same factor, making it difficult to correctly model node activity when the two kinds of activity are decoupled. In this paper, we propose the Dual-Corrected Stochastic Block Model ($\text{DC}^2\text{SBM}$), which introduces independent correction factors---a topological degree factor and an attribute abundance factor---into the link-generation and attribute-generation channels, respectively, thereby effectively decoupling node activity from membership inference, and which further introduces a global scaling parameter to resolve the mismatch between the normalization constraints and the network scale. The model is inferred by the expectation--maximization (EM) algorithm, and the newly introduced factors cancel out completely in the posterior computation, so that no additional computational cost is incurred. Experiments on synthetic and real attributed networks show that DC^2SBM outperforms state-of-the-art methods in community detection accuracy, with an especially pronounced advantage when the topological signal is weak. The two correction factors can be recovered independently from their respective channels without cross-talk. Analytical as well as controlled experiments further demonstrate that modeling with a single shared factor fails when the two kinds of activity are decoupled---a regime that is prevalent in real networks---thereby validating the necessity of dual independent correction.

0.09

Spectral graph clustering with inhomogeneous latent geometry

cs.SI cs.LGmath.PRstat.ML ·2026-08-11 ·Konstantin Avrachenkov, Lucas S. Sibemberg, Alexander Van Werde
similarity 0.60
Abstract · 28 pages, 11 figures

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.

0.10

Spectral Embeddings of Degree-$α$ Laplacians in Random Dot Product Graphs

cs.LG stat.ML ·2026-08-11 ·John Park, Ning Hao
theory similarity 0.60
Abstract

Spectral clustering methods for network data are commonly based on a few matrix representations, such as the adjacency matrix and the symmetric Laplacian. We study a continuum of degree-normalized spectral embeddings that includes these commonly used choices as special cases. Under a random dot product graph model, we establish a row-wise central limit theorem for this family of embeddings. The result provides an explicit description of how degree normalization affects both population geometry and the local uncertainty of embedded nodes. We use the limiting distributions to compare different normalizations in two-community stochastic block models through a projected-Gaussian Bayes-error diagnostic. These comparisons show that no single normalization is uniformly preferred. Instead, the favored normalization depends on network density, community imbalance, and block-probability structure. Typically, stronger normalization is favored in lower-density or more imbalanced settings. These results provide a unified distributional understanding of when and why alternative normalizations may improve spectral clustering.

0.04

Learning Continuous Neural Representation of Stochastic Hybrid Systems

cs.LG cs.AIeess.SY ·2026-09-30 ·Sangli Teng, Hang Liu, Koushil Sreenath
theory similarity 0.59
Abstract

A stochastic hybrid system (SHS) is governed by a stochastic differential equation (SDE) describing the continuous dynamics and a Markov reset kernel triggered on the guard surface. Its probability evolution can be described by a hybrid Fokker-Planck (HFP) equation with a partial differential term corresponding to the SDE and an integral term arising from the reset kernel. This work shows that such an SHS can be approximated by an SDE in a higher-dimensional latent space where the sample paths are continuous. The key to this result is to encode different branches of the reset kernel using auxiliary variables, transforming the resets into deterministic ones that enable topological gluing. By the embedding theorem, the glued manifold can then be embedded into a higher-dimensional Euclidean space. We show that the probability evolution on the embedded image no longer requires explicit reset terms in the HFP equation. Building on this theorem, we design a loss that matches the evolving state distributions, enabling a single latent SDE to recover the probability evolution of the SHS without mode labeling, trajectory segmentation, or event-based simulations.

0.29

Topology-induced Operators Reveal Complementary Graph Representations without Training

cs.LG cs.SI ·2026-09-08 ·Meng Qin, Jinqiang Cui, Hongwei Zheng, Weihua Li, Sen Pei
similarity 0.59
Abstract

Graph representation learning has largely focused on designing increasingly sophisticated models to transform graph topology into vector representations, or embeddings. However, the extent to which embedding quality depends on model learning, rather than on the underlying topological transformations, remains unclear. Here, we show that informative embeddings can be derived without complicated model design and gradient-based training. Propagating random features through implicit hierarchical structures induced by random walks and anonymous walks yields embeddings that capture node proximity and structural role, respectively. These two training-free embeddings preserve complementary aspects of graph organization and perform competitively with classic and recent methods across various node-, edge-, and graph-level tasks. They often require substantially less computation, resulting in a favorable quality-efficiency trade-off. Combining the two types of embeddings further improves inference quality of some tasks compared with using either embedding type alone. Our results suggest that informative graph embeddings can arise from carefully chosen topological transformations before any learning operation is applied.

0.04

Topological Equivalence of Spectral and Density Cluster Hierarchies

cs.LG ·2026-10-22 ·Sajjad Hashemian
similarity 0.58
Abstract

We compare two canonical ways to recover hierarchical clustering from an underlying density $f$: the \emph{density cluster tree} given by connected components of superlevel sets $\{f\geλ\}$, and a \emph{spectral hierarchy} obtained by applying single linkage to diffusion distances induced by a Laplacian operator. We give conditions under which, at an appropriate diffusion time, the diffusion hierarchy is \emph{topologically equivalent} to the density cluster tree up to a monotone rescaling of heights. It further shows that a $k$-NN graph implementation inherits this equivalence from uniform approximation of diffusion distances, yielding a finite-sample reduction from spectral graph constructions to density-level-set topology.

0.25

Learning Topology-Aware Representations for Mechanics-Relevant TPMS Metamaterials

cs.LG cs.CEcs.CVstat.ML ·2026-10-14 ·Songlin Duan, Shuo Yang, Yujia Zheng, Tobin Filleter
similarity 0.58
Abstract · 29 pages, 10 figures

Learning informative representations of mechanical Triply Periodic Minimal Surface (TPMS) metamaterials is important for mechanics analysis and structural design, yet existing methods have rarely explicitly supervised learned representations with information about global structural connectivity that is relevant to mechanical response. We propose a topology-aware representation learning framework that integrates persistent homology into a DMAE backbone to explicitly encode global structural connectivity. A persistence-guided masking strategy prioritizes patches associated with persistent topological features, while an auxiliary persistent-homology decoder encourages the latent representation to retain information about topological feature counts across connected components, tunnels, and voids. We evaluate the learned representations on two complementary TPMS datasets using family classification, mechanical-property classification, unsupervised clustering, and regression. Across the two datasets, our method demonstrates strong performance in both structural family and mechanical-property classification, improving family classification by up to 3.9% while achieving the best linear-probe performance. More notably, unsupervised property-clustering performance improves by up to 26.7% and 51.5% across the two datasets, while strong regression performance is retained with $R^2=0.993$. These results establish persistent topology as an effective inductive bias for representation learning of complex three-dimensional mechanical metamaterials.

0.21

Beyond Static Graph World Models: Learning Stochastic Latent Dynamics over Evolving Topologies

cs.LG cs.AIcs.SI ·2026-09-23 ·Alex Schutz, Nick Hawes, Victor-Alexandru Darvariu
similarity 0.58
Abstract

Graph-based world models have recently emerged as a means of learning transitions over relational state representations. However, existing approaches are largely limited to fixed-topology graphs or deterministic, fully observable environments. We propose the Graph Dynamics Model (GDM), a world model for graph-structured observations that is designed to handle the more general setting of evolving topologies in stochastic and partially observable environments. The GDM uses a sparse recurrent adjacency matrix to model topology updates and perform message passing, together with a recurrent state-space architecture for modelling stochastic transitions. Furthermore, we identify a gap in the evaluation of graph-based world models, as existing methods do not provide a means of comparing predicted and true distributions over the joint graph state comprising the interdependent topology, node features, and graph features. We therefore introduce the Graph Distribution Distance (GDD) metric, which uses maximum mean discrepancy with a graph kernel to comprehensively compare joint next-state distributions. We evaluate the GDM across several environments, including stochastic and partially observable settings. We demonstrate that GDM outperforms baseline models and displays zero-shot generalisation on large graphs.

0.47