CS Paper Radar

Degree-Corrected Joint Matrix Factorization for Multilayer Community Detection

Alexandra Dache, Manon Rustin, Arnaud Vandaele, Nicolas Gillis

cs.SI cs.LG ·submitted 2026-10-01 09:31 UTC · v1

Abstract

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.

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.75
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

Exact Community Recovery in Bipartite Networks

cs.SI math.STstat.ML ·2026-09-11 ·Huan Qing
theory similarity 0.69
Abstract · 39 pages, 4 figures

Community detection in bipartite networks is a fundamental problem in modern data analysis, with applications in recommendation systems, biological networks, and social network analysis. Unlike conventional unipartite graphs, bipartite networks consist of two distinct types of nodes with edges only connecting across types, so recovering latent communities requires estimating labels on the two node types. The stochastic co-blockmodel is a classical probabilistic framework for such networks, yet theoretical guarantees for exact community recovery in this setting remain limited, especially when the number of communities grows, the community sizes are unbalanced, or the degrees are heterogeneous. In this work, we prove that a simple spectral clustering algorithm based on the diagonal-deleted Gram matrix achieves exact recovery with high probability under mild conditions on sparsity, community balance, and the number of clusters. We further extend the result to the degree-corrected stochastic co-blockmodel, where each node carries its own degree heterogeneity parameter, and show that a row-normalized version of the same algorithm maintains the exact recovery guarantee. Extensive experiments validate our theoretical findings.

0.15

Federated Community Detection in Bipartite Networks

cs.LG stat.MLstat.COstat.ME ·2026-10-19 ·Wanjie Wang
similarity 0.66
Abstract · 47 pages, 10 figures, 6 tables

We study federated spectral estimation when a large matrix is horizontally partitioned across servers that cannot share raw data. We propose FLICKER, a target-specific gradient-based power iteration that recovers a singular direction associated with a prescribed spectral target using only matrix-vector products on local blocks. Different target directions can be recovered independently and in parallel. We establish non-asymptotic convergence guarantees and provide a recursive grid-search procedure for spectral target selection. Building on FLICKER, we develop BiFLICKER for federated community detection in bipartite networks, together with a sequential projected variant for nearby or repeated singular directions. Under a sparse bipartite stochastic block model, we show that properly rescaled leading singular values from a reference server provide valid global targets, and that Sequential BiFLICKER achieves a vanishing misclustering rate and exact recovery under stronger sparsity conditions. Simulations show that BiFLICKER remains close to centralized spectral clustering and is more robust than existing federated spectral baselines when local sample sizes are small. On a LastFM user-artist network naturally partitioned by country, Sequential BiFLICKER attains an overall ARI of 0.94 against centralized clustering while revealing cross-country communities with distinct listening profiles.

0.22

WCCS: Efficient Wedge Conductance Community Search over Large Temporal Bipartite Graphs (Full Paper)

cs.SI ·2026-09-15 ·Longlong Lin, Wei Chen, Pingpeng Yuan, Ruikun Luo, Qiangqiang Dai +1 more
similarity 0.65
Abstract

Bipartite graphs are ubiquitous for modeling complex interactions between two distinct entity types across numerous practical applications such as e-commerce, academic networks, and social systems. Despite significant progress in community search over bipartite graphs, most prior work is limited to static settings and ignores the rich temporal dynamics present in real-world networks. Moreover, existing methods typically adopt edge-centric measures and strict consecutivity constraints, failing to capture higher-order interactions and frequent yet non-consecutive activities. More importantly, they often neglect the crucial community-quality requirements of both internal cohesiveness and external sparsity, failing to identify critical nodes or including many irrelevant nodes. To address these dilemmas, we propose the novel problem of \emph{Wedge Conductance Community Search (WCCS)}, which aims to identify a query-dependent community that is not only structurally and temporally cohesive but also well-separated from the rest of the network over non-consecutive timestamps. We formalize WCCS by generalizing the classical $(α,β)$-core to a higher-order $(α,β,τ)$-wedge core, and by proposing a novel temporal wedge conductance metric that explicitly balances internal density and external sparsity. To solve WCCS efficiently, we first develop an online priority-driven filter-and-expand framework with several effective pruning techniques and a powerful geometric slope optimization for rapid temporal wedge conductance calculation. Subsequently, to further improve scalability, we propose an offline compressed index to accelerate search. Finally, comprehensive experiments on seven real-world datasets demonstrate the effectiveness, efficiency, and scalability of our solutions compared to eight competitors.

0.11

Scalable dynamic community detection on temporal graphs using graph neural networks

cs.SI ·2026-08-28 ·Peijie Zhong, Raul Mondragon, Richard G. Clegg
similarity 0.64
Abstract · Submitted to Trans KDD

Dynamic community detection on temporal graphs seeks to identify evolving community structures while allowing node memberships to change over time. In this work, we formulate dynamic community detection over observed node-time instances, where each node-time instance in the temporal interaction stream is assigned a cluster label. We propose a diffusion-guided contrastive learning framework that uses a local temporal diffusion affinity matrix to construct positive and negative node-time pairs and organise the learned representations according to their temporal structural relationships. We then apply a clustering algorithm to the resulting embedding space to detect dynamic communities. Experiments on synthetic temporal networks show that the proposed method outperforms static community detection baselines and achieves competitive or better performance than existing dynamic community detection methods in terms of AMI and ARI, while maintaining good scalability. We further apply the method to a large-scale OpenAlex computer science collaboration network from 2016 to 2025, revealing persistent and evolving collaboration communities in real scientific data. These results suggest that time-node-level representation learning provides an effective framework for scalable dynamic community detection on temporal graphs.

0.25

Diffusion-Induced Spatial Attention Overlapping Community Detection

cs.SI cs.LG ·2026-09-22 ·Kosti Koistinen, Vesa Kuikka, Joni Herttuainen, Matthew Hendren, Brian Holt +1 more
benchmark similarity 0.62
Abstract

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.

0.07

Representation-Aware Modularity with a Distance-Calibrated Null Model

cs.SI ·2026-10-05 ·Taejoon Han, Dahee Kim, Junghoon Kim, Taeho Ha
top venue similarity 0.61
Abstract

Modularity is a standard objective for community detection, comparing observed intra-community connectivity with its null-model expectation. Modern node embeddings capture structural and semantic proximity beyond raw topology, but replacing adjacency with representation-induced affinity while retaining the classical degree-based null model makes the observed term geometry-dependent and the expected term geometry-agnostic. This creates a null-model mismatch: the objective may reward affinity already expected from representation proximity. This paper introduces RAM, a representation-aware modularity objective with a distance-calibrated null model. RAM preserves the observed-minus-expected principle by calibrating expected affinity with both degree heterogeneity and representation distance. We analyse its relation to classical modularity and develop divisive and multi-level greedy optimisers. Experiments on seven real-world datasets and synthetic scalability tests show that RAM improves over topology-only, direct embedding-clustering, and deep learning-based baselines, remains competitive under classical modularity while improving community quality on large graphs, and scales efficiently. Ablations confirm that both degree correction and distance calibration are essential.

0.37

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

cs.LG stat.ML ·2026-08-11 ·John Park, Ning Hao
theory similarity 0.61
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