CS Paper Radar

Federated Community Detection in Bipartite Networks

Wanjie Wang

cs.LG stat.MLstat.COstat.ME ·submitted 2026-10-19 08:21 UTC · v1

Abstract

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.

Comment
47 pages, 10 figures, 6 tables

Closest papers

Nearest neighbours by meaning across the whole index.

Exact Community Recovery in Bipartite Networks

cs.SI math.STstat.ML ·2026-09-11 ·Huan Qing
theory similarity 0.72
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

Degree-Corrected Joint Matrix Factorization for Multilayer Community Detection

cs.SI cs.LG ·2026-10-01 ·Alexandra Dache, Manon Rustin, Arnaud Vandaele, Nicolas Gillis
similarity 0.66
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.

0.10

Revisiting the Objective of Echo Chamber Detection

cs.LG ·2026-09-16 ·Abylaikhan Bexeit, Kushani Perera, Shanika Karunasekera, Jean Honorio
position similarity 0.60
Abstract

In this paper, we study the detection of an echo chamber in a social network, i.e., the identification of a set of nodes that agree on a topic, while disagreeing with the rest of nodes. We argue that this problem is different from other social network analysis problems such as community detection, and from other graph problems such as maximum graph cut and maximum clique. To the best of our knowledge, we are the first to formalize the objective function of echo chamber detection, by using the theory of Fourier transforms of set functions (Stobbe and Krause, 2012). We propose scalable semidefinite relaxation, solved via an interior point method and sparse linear algebra. Experimentally, our algorithm recovers the ground truth echo chamber better than competing methods on small synthetic experiments. Our algorithm produces echo chambers with better network properties than competing methods on large real-world datasets. To independently validate our proposed objective function, we show that our algorithm finds echo chambers with more agreements with suspended users than competing methods on a small real-world dataset.

0.24

Connectivity-Aware Client Selection in Decentralized Federated Learning

cs.AI ·2026-10-30 ·Usevalad Milasheuski, Monica Nicoli, Stefano Savazzi
similarity 0.59
Abstract

Decentralized federated learning (DFL) has emerged as a scalable alternative to centralized federated learning, removing the single point of failure and communication bottleneck at the server. However, most existing decentralized approaches rely on full-neighborhood broadcasting, where each client transmits its model update to all of its neighbors in each communication round. While effective, this results in significant communication overhead and high energy consumption. This paper applies spectral graph tools as lightweight client selection methods that leverage the graph topology by analyzing the spectral properties of the graph Laplacian over a fixed communication graph. Specifically, we exploit eigenvector embeddings and heat/diffusion kernel similarities to guide each client in selecting only a subset of structurally relevant neighbors, i.e., those that are most beneficial for the convergence of the federation process. This topology aware randomization matches or outperforms uniform neighborhood subsampling and approaches the accuracy of full broadcasting. The largest gains, about $3$ percentage points, emerge under strong data heterogeneity on larger, structurally rich graphs, while the total number of transmitted messages is reduced by $50\%$ compared to naive broadcasting.

0.20

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

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

Exact Selective Inference for Spectral Clustering via Piecewise-Constant Graph Perturbation

cs.LG stat.ML ·2026-11-03 ·Naotoshi Nakamura
published similarity 0.57
Abstract · 31 pages, including supplementary material. Accepted at ACML 2026

Cluster labels are often used twice: first to discover groups, and then to test whether the discovered groups differ. This double use of the data makes ordinary two-sample $p$-values anti-conservative. Selective inference fixes this by conditioning on the clustering event, but for spectral clustering the event appears difficult because the algorithm combines an affinity map, an eigendecomposition, and a rounding step. We show that, for spectral clustering based on unweighted $\varepsilon$- or $k$-nearest-neighbor graphs, the obstruction is the affinity construction rather than the eigendecomposition. Along the one-dimensional perturbation used by the truncated-$χ$ selective test, graph changes occur only at finitely many real roots of data-dependent quadratic distance comparisons. Between these breakpoints, the graph, Laplacian spectrum, embedding, rounding, and reported cluster pair are deterministic functions of a finite graph state. Consequently, in real arithmetic and under a known-scale spherical Gaussian model, the selection set is an exact finite union of intervals, yielding finite-sample selective $p$-values for selected spectral-cluster pairs. The same argument gives feature-wise truncated-normal tests. We also record direct extensions to known feature covariance, eigengap-selected $K$, and auxiliary-coordinate graphs. We validate null and partial-null calibration, operational power, numerical sensitivity, and model-scope diagnostics, and give a working-model PBMC algorithmic illustration. Smooth kernels such as RBF affinities fall outside the finite-state guarantee.

0.29

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.57
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 Efficiency Centrality: An Efficient Spectral Approach for Influential Node Identification in Temporal Networks

cs.SI ·2026-08-14 ·Aksa Urooj, Iqra Altaf Gillani
similarity 0.56
Abstract · 23 pages, 16 figures, 11 tables, journal paper

Centrality measures play a vital role in identifying influential nodes in evolving networks. While existing temporal centrality measures primarily rely on local structural properties or temporal paths, spectral node-removal approaches have been largely limited to static networks. To bridge this gap, we propose Spectral Efficiency Centrality (SEC), a temporal spectral centrality framework that quantifies node importance by evaluating the change in spectral radius caused by node removal across temporal snapshots. By capturing the global structural influence of nodes throughout network evolution, SEC identifies nodes that are critical for preserving the structural connectivity and efficiency of temporal networks. To improve computational scalability, we further develop an efficient approximation, ASEC, based on Perron-Frobenius theory and first-order eigenvalue perturbation. ASEC requires only the leading eigenpair and avoids repeated eigendecomposition, making it suitable for large temporal networks. Extensive experiments on multiple real-world temporal datasets demonstrate that SEC and ASEC outperform existing baseline centrality measures in identifying influential nodes under SI, SIS, and IC diffusion models. Statistical significance and robustness analyses further confirm their effectiveness, while ASEC offers a computationally efficient solution for large-scale temporal networks.

0.10