CS Paper Radar

Diffusion-Induced Spatial Attention Overlapping Community Detection

Kosti Koistinen, Vesa Kuikka, Joni Herttuainen, Matthew Hendren, Brian Holt, Kimmo K. Kaski

cs.SI cs.LG ·submitted 2026-09-22 17:25 UTC · v1
benchmark

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.

Closest papers

Nearest neighbours by meaning across the whole index.

CSBA-Net: Learning Cross-Scale Structural Dependencies for Influential Node Identification in Complex Networks

cs.SI ·2026-10-13 ·Rihab Boukheche, Mohammed Lalou, Nardjes Bouchemal
similarity 0.71
Abstract

Identifying influential nodes is a fundamental task in complex network analysis, with applications in epidemic control, information diffusion, and network robustness. Existing centrality-based and learning-based methods often provide limited integration of structural information across different network scales. To address this limitation, we propose CSBA-Net, for Cross-Scale Structural BiGRU Attention Network, a multi-scale structural representation learning framework that jointly captures local, community-level, and global structural patterns. The extracted representations are processed by CNNs and integrated through a BiGRU with multi-head self-attention to model dependencies across structural scales. Influential-node scores are learned through regression using SIR-based diffusion simulations as reference targets. We conduct experiments on 24 real-world and 12 synthetic networks from social, biological, technological, and knowledge domains, and show that CSBA-Net achieves Kendall's tau=0.802, Spearman's rho=0.943, NDCG10 =0.898, and NDCG20 =0.916, outperforming the considered centrality-, CNN-, and GNN-based baselines. The results demonstrate the effectiveness of combining complementary structural scales for accurate influential-node ranking across diverse network structures.

0.12

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

SynCo: Synthetic Community-Aware Attributed Graph Generator for Graph Neural Network Benchmarking

cs.SI cs.LG ·2026-09-09 ·Guilherme Henrique Messias, Mariana Caravanti de Souza, Sylvia Iasulaitis, Alan Demétrius Baria Valejo
benchmark similarity 0.66
Abstract · 15 pages

Graph Neural Networks (GNNs) are powerful models for handling attributed graphs in tasks such as classification, link prediction, and community detection, as they enable the aggregation of information from both structural and semantic sources. However, progress in community detection is hindered by the lack of high-quality datasets, since ground-truth community labels are often unavailable and most algorithms proposed in recent literature rely on the same benchmark datasets for model training and evaluation. To address this issue, attributed random graph generators are commonly employed to create synthetic graphs for assessing the strengths and limitations of GNN-based models. Nevertheless, most existing generators rely heavily on power-law degree distributions, despite recent evidence indicating that scale-free networks are rare, particularly in social network contexts. Moreover, state-of-the-art attributed graph generators provide limited flexibility, as they do not allow users to construct communities with varying densities, degree distributions, and sub-community structures. To overcome these limitations, we introduce the Synthetic Community-Aware Attributed Graph Generator (SynCo), a graph generation algorithm that allows users to control the node degree distribution and sub-community structure. We evaluate SynCo across three different tasks: graph mimicking, hyperparameter evaluation, and node clustering tuning. The results show that our model outperforms state-of-the-art approaches in synthetic graph generation and data augmentation, while preserving the original distributions of duplicated and augmented datasets, as confirmed by statistical tests well know in literature. We also demonstrate the ability of SynCo to generate nodes in large scale, up to 2.1 million nodes.

0.13

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

Disparity in Influence: A Fairness Evaluation of Centrality Measures in Complex Networks

cs.SI ·2026-11-15 ·Kirtidev Mohapatra, Harsh Vardhan Singh, Rishi Ranjan Singh, Akrati Saxena
similarity 0.65
Abstract

Social networks are shaped by homophily-driven connections, which naturally lead to the emergence of communities with uneven sizes and influence. Such structural imbalances impact the fairness of network analysis tools, particularly centrality measures that are widely used to identify influential nodes for tasks like information diffusion and network robustness. In this work, we conduct a comprehensive assessment of fairness in centrality measures, using influence spreading across networks with heterogeneous community structures. We first analytically show that disparity is bounded by outreach; cross-community outreach is bounded by the inter-community cut; and when all seeds lie in one community, disparity approaches the normalized outreach within that community as cross-community transmission vanishes. This explains why attenuation concentrates influence in the community where diffusion starts. We further evaluate a broad spectrum of centrality measures, including local, semi-local, global, and community-aware measures, on both synthetic network generative models and real-world datasets, using the Independent Cascade and Linear Threshold Models. The results consistently show that influence tends to concentrate within larger communities, with disparities becoming more pronounced under constrained or deterministic diffusion settings. We further observe that fairness is highly sensitive to the choice of centrality measure rather than its general category. In particular, fairness-aware adaptations of PageRank demonstrate a strong balance between maximizing influence reach and maintaining equitable distribution across communities. On real networks, these conclusions are largely stable under random removal or addition of up to 3% of the edges. Our findings highlight the need to explicitly account for fairness when designing and selecting centrality-based strategies in networked systems.

0.19

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

Dual Spatial-Temporal Attribution: Architecture-Aligned Post-Hoc Explainability for Recurrent Graph Anomaly Detection

cs.LG cs.AI ·2026-08-12 ·Iyad Assaad Nekka, Hamida Seba, Khaled Walid Hidouci, Karima Amrouche
benchmark similarity 0.64
Abstract · Under Review : The International Conference on Cooperative Information Systems (CoopIS)

Deep learning detectors for anomalies in dynamic graphs have reached strong accuracy, yet they remain opaque: when an edge is flagged, the analyst receives a score but no reason. This opacity is untenable in the cooperative, regulated information systems where such detectors are deployed, where automated decisions must be auditable and trustworthy. We address this gap for AddGraph, the foundational GCN+GRU framework for edge-level anomaly detection in dynamic graphs, which to our knowledge has never been equipped with any form of explainability. We present a strictly post-hoc explainability framework, X-AddGraph, built on a Dual Spatial-Temporal Attribution (DSTA) mechanism whose three components are each aligned with one of AddGraph's architectural modules: a gradient-based relevance attribution over the current adjacency structure (spatial), a direct reading of the contextual attention weights already computed during inference (short-term temporal, at zero additional cost), and a gradient rollback through the recurrent hidden states (long-term temporal). Because the detector is frozen, detection performance is preserved exactly (Delta AUC = 0, verified empirically to ten decimal places). On the UCI Message benchmark, our trained AddGraph baseline reaches an average per-snapshot AUC of 0.8705, exceeding the originally published result; X-AddGraph reproduces every score identically while adding explanations where none existed. Evaluated across four edge populations - confident true positives, low-confidence true positives, false positives, and random samples - the long-term attribution identifies historical snapshots carrying significantly more counterfactual signal than random selection (0.127 vs. 0.074), a capability that no spatially-blind explainer can provide. We release our implementation for full reproducibility.

0.06

A Network Science Perspective on Evaluating Deep Graph Generative Models

cs.SI cs.AI ·2026-09-01 ·Tianrui Mao, Abele Malan, Megha Khosla, Lydia Chen, Huijuan Wang
similarity 0.63
Abstract

Traditional network models from network science, such as the Erdos-Renyi and configuration models, generate random networks that reproduce few selected topological properties observed in real-world networks. Deep graph generative models emerge as a data-driven approach, leveraging deep neural network architectures to learn complex structural distributions directly from real-world networks to generate more realistic synthetic networks. Because real social contact networks cannot be shared due to privacy risks, synthetic networks serve as an alternative for developing and evaluating epidemic mitigation strategies. In this work, we evaluate deep graph generative models as well as the configuration from a network science perspective by assessing both the topological similarity between generated and real-world networks and their utility in identifying effective node immunization strategies to sup- press epidemic/misinformation spreading. It is found that two deep graph generative models produce synthetic networks that closely resemble the structural properties of real-world networks, enabling them to identify effective immunization strategies.

0.15