CS Paper Radar

Spectral Braids: A Topological Descriptor for Dynamic Directed Networks

Mehmet Emin Aktas, Esra Akbas

cs.SI cs.LG ·submitted 2026-10-27 17:21 UTC · v1
published

Abstract

Eigenvalues are a workhorse of graph machine learning: spectral clustering, spectral graph neural networks, and graph kernels all summarize a network by the eigenvalues of a matrix. These eigenvalues are almost always treated as a static list of numbers. When a graph changes, however, its eigenvalues move, and when the matrix is not symmetric, they move in the complex plane, where they can wind around each other. The pattern of this winding is a braid, a classical object from topology. We propose spectral braids, a methodology for dynamic directed networks: each snapshot is aggregated into a community-level transition matrix, its complex eigenvalues are tracked over time, and the braid they trace is read off as a word. The word is then mapped to a matrix by the Burau representation, which gives a fixed-size feature vector for any classifier. The braid has a concrete meaning: each eigenvalue describes how a group of communities behaves, and each crossing records one group overtaking another. We evaluate the method on dynamic network classification, using synthetic networks of online communities whose labels describe how the network evolved between the same starting and ending states. Our experimental results show that the proposed features reach 97.1% accuracy on four classes, against 44.5% for the best feature set that does not track eigenvalues, and that the Burau features also separate networks containing the same events in a different order, which simple counts of crossings cannot do. To the best of our knowledge, this is the first study that defines braids and braid monodromy on graph data and uses them as features for learning on dynamic networks.

Comment
15 pages, 5 figures, 2 tables. Accepted at the 2026 IEEE International Conference on Big Data (IEEE BigData 2026)

Closest papers

Nearest neighbours by meaning across the whole index.

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

Message-passing graph persistence

cs.LG cs.AIstat.ML ·2026-11-04 ·Jorge Luiz Franco, Arthur Queiroz Moura, Moacir Ponti, Amauri Souza
benchmarktheory similarity 0.60
Abstract

Message-passing graph neural networks (GNNs) are limited in expressive power by the one-dimensional Weisfeiler-Leman test. Persistent homology (PH) provides topological descriptors that can complement GNN representations, but existing approaches typically compute persistence separately from the representation learning process. In this paper, we introduce Message-Passing Graph Persistence (MGP), a family of topological descriptors that incorporates message passing into graph filtrations. At each filtration step, node embeddings are updated using the current subgraph and associated with persistence events. These embeddings also determine the representatives of connected components during persistence computation. We prove that MGP is invariant under graph isomorphism and that it is strictly more expressive than the PH-based descriptors it extends. We evaluate MGP on an expressivity benchmark and on several graph classification and regression datasets. Experiments show that MGP outperforms other PH-based descriptors on most of these datasets.

0.17

HyperFuse: Fast Self-Supervised Node Embeddings for Attributed Hypergraphs

cs.LG ·2026-10-02 ·Megha P, Harshit Kumar, Srajan Agarwal, Anirban Banerjee, Olaf Wolkenhauer +1 more
similarity 0.59
Abstract

Self-supervised hypergraph representation learning can produce informative node embeddings, but existing methods often require deep encoders trained for hundreds of epochs, making embedding generation costly even for hypergraphs with a few thousand nodes. This limits applications requiring embeddings for many or evolving hypergraphs. We present HyperFuse, a label-free pipeline for fast hypergraph representation learning. HyperFuse (i) computes structural node coordinates by maximizing a spectral relaxation of hypergraph modularity using Banerjee's hypergraph adjacency and a matrix-free operator with cost linear in node-hyperedge incidences; (ii) constructs multi-scale feature summaries and assigns bounded utility weights to hyperedges based on member stability under feature and membership masking; and (iii) trains a lightweight utility-weighted hypergraph encoder for 100 epochs using an invariance-decorrelation objective. We compare HyperFuse with TriCL, SE-HSSL, VilLain, and HypeBoy on nine public hypergraphs using six downstream classifiers and k-means clustering. On the eight datasets where all methods completed, HyperFuse required 8.7 s per dataset on average, achieving 13-179x geometric-mean speed-ups over the baselines. It achieved the highest average accuracy with five of six classifiers, while classification and clustering performance was not significantly different from TriCL and SE-HSSL. Compared with HypeBoy, HyperFuse was 13x faster and 2.1-4.1 percentage points more accurate across all classifiers. HyperFuse provides a practical approach for fast, repeated hypergraph embedding generation.

0.23

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

Spectral Fingerprints of Street-Network Morphology: A Size-Adjusted Graph-Laplacian Descriptor of Urban Fabric

cs.SI physics.soc-ph ·2026-08-17 ·Piotr C. Kaminski
similarity 0.58
Abstract · 18 pages, 7 figures. Under review at Journal of Complex Networks (Oxford University Press)

Decades of space-syntax research have established that the topology of the street network conditions movement, co-presence and urban activity. The standard vocabulary for this -- integration, choice and connectivity -- summarises each street's position as a scalar centrality, yet two streets with identical centrality can sit in radically different morphological fabric. We introduce a compact, comparable, machine-learning-ready encoding of that local fabric: the spectral fingerprint, a fixed-dimensional kernel-density representation of the graph-Laplacian eigenvalue distribution of each node's k-hop ego subgraph, computed on the COINS dual graph of the street network. From it we derive two interpretable scalar readouts: the Mesh Index (MI), a normalised spectral entropy, and the Connectivity Resilience Index (CRI), the algebraic connectivity (Fiedler value). Both are corrected for an ego-subgraph-size confound that dominates raw spectral statistics. Applied to the full street network of Poznan, Poland (1,908 continuity-based strokes), the descriptor is robust to its encoding hyperparameters (spectral resolution and kernel bandwidth; Spearman rho >= 0.98) while remaining scale-dependent in its neighbourhood radius. The size adjustment leaves the Mesh Index near-orthogonal to integration (r = 0.06), carrying information classical centrality does not. The fingerprint separates morphological tissue types without supervision, and the Mesh Index is associated with the functional diversity of street-adjacent activity at the neighbourhood scale (r ~ 0.19, on open OpenStreetMap data). We delineate the method's scope honestly: it characterises what kind of activity a street's position affords, not the price that activity commands. It offers an information-theoretic morphological descriptor that complements space syntax and is directly consumable by modern graph-learning pipelines.

0.25

Ollivier's Ricci Curvature on Complex-weighted Graphs

cs.SI math.MGphysics.soc-ph ·2026-08-10 ·Yu Tian, Eleanor Wiesler, Melanie Weber
similarity 0.58
Abstract · 32 pages, 11 figures

Understanding the geometry of complex networks is critical for effective modeling and analysis across domains. While discrete notions of Ricci curvature have emerged as powerful tools for characterizing both local and global network structure, existing formulations are largely confined to undirected networks with real-valued weights. This limits the use of curvature-based analysis of directional and complex-weighted relations that arise naturally in many applications, from social and biological systems to quantum and signal-processing networks. In this work, we introduce a principled extension of Ollivier's Ricci curvature to complex-weighted graphs, which encompasses directed graphs as a special case. We establish fundamental theoretical properties of this new notion, including relations to the magnetic Laplacian and combinatorial upper and lower bounds that relate curvature to cycle structure in local neighborhoods. We further develop computational methods for curvature estimation and demonstrate their utility in community detection on directed networks.

0.10

Path Laplacian Encodings for Directed Graphs

cs.LG ·2026-10-03 ·Lydia Mezrag, Semih Cantürk, Michael Perlmutter, Bastian Rieck, Guy Wolf
benchmark similarity 0.58
Abstract

Directed graphs naturally model many real-world systems in which interactions are asymmetric, such as citation networks, web graphs, and information-flow networks. However, graph learning methods commonly rely on message passing with symmetrized graph representations or positional encodings that only partially exploit edge directionality. We introduce PathLapPE, a novel spectral positional encoding (PE) derived from the path Laplacian on directed graphs. PathLapPE provides node- and edge-level features that encode directional higher-order structure and can be incorporated into standard graph learning architectures. Empirical results on node- and graph-level benchmark tasks show that PathLapPE yields consistent improvements across several architectures, especially when combined with direction-aware message passing. Compared with magnetic Laplacian positional encodings, a widely studied spectral positional encoding for directed graphs, PathLapPE does not require additional fine-tuning of directionality hyperparameters while offering competitive runtime and performance.

0.16

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