CS Paper Radar

Constrained Enumeration Reveals Hidden Optima and Precision-Dependent Degeneracy in Modularity-Based Community Detection

Fabio Morea

cs.SI ·submitted 2026-09-29 08:27 UTC · v1
benchmark

Abstract

Modularity landscapes are often flat near the top: many distinct partitions achieve indistinguishable scores, and repeated runs of heuristic algorithms can still miss accessible optima. We introduce a two-phase workflow that (i) samples partitions until novelty saturates, then (ii) localises instability to a small subset of nodes and enumerates only that residual ambiguity under a locked stable core. Across a simple 50-nodes benchmark network, and a real weighted collaboration network, constrained enumeration systematically expands plateau coverage and can improve modularity beyond extensive Louvain restarts. Finally, we show that edge-weight rounding qualitatively reshapes plateau structure, making precision sensitivity an essential part of solution-space reporting.

Comment
11 pages, 7 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Scaled Null-Adjusted Persistence: A Multiscale Bridge between Modularity and Persistence

cs.SI math.OC ·2026-08-31 ·Alessandro Avellone, Paolo Bartesaghi, Stefano Benati, Rosanna Grassi
similarity 0.70
Abstract

Community detection methods must balance two competing objectives: identifying small, cohesive groups while avoiding excessive fragmentation. Modularity, the most widely adopted optimization criterion, typically merges small communities in large networks due to its resolution limit. In contrast, a persistence-based criterion promotes more granular partitions. We introduce Scaled Null-Adjusted Persistence (Scaled-NAP), a parametric family of quality functions that incorporates both these criteria. The definition exploits the exact identity between a cluster's modularity contribution and its Null-Adjusted Persistence (NAP) multiplied by its relative volume. Raising this volume factor to a parameter $α\in[0,1]$ yields NAP at $α=0$ and modularity at $α=1$, while intermediate values control the scale of the detected partition. We derive conditions under which merging two communities improves the objective function and characterize the emergence of scale dependence, including resolution-limit behaviour on Caveman graphs. We develop the Milano algorithm, a multilevel Louvain-style heuristic for optimizing Scaled-NAP on large networks. Experiments on weighted and unweighted Lancichinetti-Fortunato-Radicchi benchmarks show that Scaled-NAP achieves the highest or tied-highest recovery wherever the ground truth structure is detectable, with its advantage increasing under community-size heterogeneity. Tests on three real networks with up to 1.1 million nodes confirm its capability to identify fine-grained ground-truth communities. The Milano algorithm also turned out to be the fastest method evaluated on large networks. These results show that Scaled-NAP provides an effective and scalable bridge between modularity-based and persistence-based community detection methodologies.

0.26

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

Partition Space Maps for Community Detection: Visualizing Algorithmic Behaviour and Guiding Search

cs.SI ·2026-09-29 ·Fabio Morea
benchmark similarity 0.67
Abstract

Community-detection methods search over possible partitions of a network, but the structure of this partition space is rarely examined directly. This paper introduces two complementary tools that make~$\mathcal{P}$ analytically and visually accessible. First, a canonical labelling scheme based on the Restricted Growth Sequence~(RGS) is adopted, assigning each partition a unique, permutation-invariant identifier and eliminating the need for pairwise similarity measures such as the Normalized Mutual Information. Second, granularity~$Γ$ is defined and combined with modularity~$Q$ to produce a two-dimensional projection: the Partition Space Map~(PSM). Within the $(Γ,Q)$ plane, only a discrete set of integer values of~$Γ$ is attainable, and upper and lower bounds on~$Q$ are derived directly from the deviation matrix. These tools are demonstrated through complete enumeration of~$\mathcal{P}$ for small benchmark graphs, revealing the fine structure of modularity degeneracy and the combinatorial constraints that shape the feasible region. The framework provides an exact, assumption-free reference for evaluating heuristic community detection algorithms and lays the groundwork for geometry-aware exploration of partition space in larger networks.

0.31

Explicit objective functions in modularity-based community detection on multiplex networks

cs.SI ·2026-09-29 ·Elizaveta Evmenova, Petr Chunaev
code/data similarity 0.66
Abstract · Revised exposition of the fusion-objective relationships; added label-free Cora external validation, fixed-weight baselines, and a reproduci…

Early, simultaneous, and late fusion combine network layers at different stages of community detection. Their modularity values consequently need not measure the same property of a partition. For normalized shared-node multiplexes, a unified comparison extends an existing two-layer identity: early fusion equals simultaneous fusion plus a weighted variance of community degree volumes. An elementary simplex argument explains simultaneous fusion's preference for single-layer weights. For a specified late-fusion construction, an additional transformation correction separates changes to the graph from changes to the objective. Exact small-network experiments and Louvain and Leiden experiments illustrate these distinctions. On label-free Cora, all objective-selected weights favor citations alone, while the fixed equal-weight mixtures achieve higher median adjusted Rand agreement with subject categories. The analysis provides a diagnostic for interpreting fusion objectives; higher objective values alone do not establish better recovery of externally defined communities.

0.38

Exact computation of the network modularity with branch-and-bound

cs.SI stat.CO ·2026-10-03 ·Emily Weng, Georg Hahn
publishedbenchmark similarity 0.63
Abstract

We consider the computation of the network modularity, a common measure of the structure of networks or graphs that quantifies the division of a network into modules or clusters. The computation of the network modularity is an NP-hard problem, thus making its exact computation often infeasible in practice. This has resulted in the development of several heuristics in the literature. In this work, we consider the exact computation of the network modularity with the help of a branch-and-bound algorithm. Our algorithm is guaranteed to find the optimal clustering that maximizes the network modularity, however it achieves this without a full exploration of the search space. This is accomplished by bounding partial solutions and discarding them if it can be foreseen that a partial solution will not yield an improvement over an existing solution. We assess our algorithm with respect to accuracy and runtime and compare it to a brute-force approach as well as two benchmark algorithms, simulated annealing and the Louvain method.

0.40

Not Just Oversmoothing: Detecting the Echo Chamber Effect in Graph Neural Networks

cs.LG ·2026-09-06 ·Asela Hevapathige, Ahad N. Zehmakan, Asiri Wijesinghe, Saman Halgamuge
similarity 0.59
Abstract

Oversmoothing is a well-known failure mode of Graph Neural Networks (GNNs). However, most existing diagnostics rely on global aggregation measures that fail to capture the heterogeneous dynamics of message passing. Real-world graphs exhibit pronounced community structure, and message passing operates on two timescales, with representations collapsing rapidly within communities and slowly across them. This creates a critical gap in which intra-community representations can become indistinguishable while inter community separation persists, a failure mode that we refer to as the Echo Chamber Effect. To quantify this effect, we introduce the Echo Chamber Index (ECI), which stratifies pairwise distances by community membership and reveals when global energy diminishes while inter-community separation persists. ECI further shows that feature retention mechanisms can preserve the echo chamber under the conditions of our theoretical analysis. The consequences depend on label structure: when communities align with classes, the echo chamber can sharpen node classification, whereas when they do not, the same collapse makes classification provably harder. Motivated by this analysis, we propose Community-Aware Split Propagation (CASP), a lightweight plugin that decouples intra- and inter-community aggregation and learns their balance from label structure. CASP improves diverse backbone GNNs across most evaluated homophilic and heterophilic settings.

0.10

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

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

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

0.32

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