Spectral Braids: A Topological Descriptor for Dynamic Directed Networks
Authors: Mehmet Emin Aktas, Esra Akbas
Organizations: School of Data Science and Analytics, Kennesaw State University, Kennesaw, GA, USA · Department of Computer Science, Georgia State University, Atlanta, GA, USA
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.
Figures & tables
Figure 1: Braids. (a) Points moving in the plane: points 1 and 2 swap counter-clockwise, then points 1 and 3 swap clockwise. (b) Stacked over time, the paths form strands. (c) Viewed from the front, each swap of neighboring strands is a crossing, written σi (counter-clockwise) or σi−1 (clockwise); this motion is the braid σ1σ2−1 .
Figure 2: Spectral braids on one dynamic network with 13 communities. (a) The community transition matrix of one snapshot. (b) The paths of the four eigenvalues in the upper half-plane over about 60 snapshots. The blue eigenvalue moves from the left end to the right end and passes the three others. (c) The same paths drawn over time: the blue strand crosses the three others one by one, which gives the braid σ1−1σ2σ3−1 . (d) The Burau matrix of this braid.
Figure 3: Example 1 . (a) The six eigenvalues of the transition matrix as group A changes and returns to its starting state; group B does not change. A and B mark the eigenvalues of the two groups at the first snapshot, and Aˉ , Bˉ their mirror images. Black: real eigenvalues. (b) Braid of the eigenvalues in the upper half-plane. (c) Braid of their mirror images.
Figure 4: One random network per label of the History dataset, with five strands: the tracked eigenvalues drawn over time and the braid word read from the data. In all four, the blue strand goes from the bottom to the top; the labels differ only in whether it passes behind or in front of the others.
Figure 5: Accuracy on the History dataset against the number of edges per snapshot, for our descriptors and the three baselines. Exact word: the share of networks whose braid word equals the planted one, with no training. The dotted line is chance.
This work addresses community detection in temporal networks through GPU-accelerated extensions of spectral clustering and modularity-based algorithms originally designed for static graphs. Built on the NVIDIA RAPIDS ecosystem, the framework enables the characterization and tracking of communities in snapshot-based dynamic graphs, either by Leiden greedy optimization with multi-GPU support via Dask-based workload distribution, or eigendecomposition of a symmetric Bethe-Hessian operator. Our multislice modularity backend achieves up to roughly three orders of magnitude speedup over the CPU reference under an equal-work budget, depending on graph density and snapshot count, while preserving compatibility with existing graph analytics pipelines. We demonstrate its applicability on real-world and synthetic datasets, facilitating exploratory analysis of structural network properties over time. Such capabilities are relevant across several application domains, such as epidemic spreading, financial systems, cybersecurity, and trajectory and mobility analysis. We release our implementation as free and open-source software, including Python bindings through the NetworkX-Temporal library for ease of use and zero-code acceleration with existing codebases.
Nelson Aloysio Reis de Almeida Passos, Emanuele Carlini, Salvatore Trani
University of Pisa, Dept. of Computer Science, 56127 Pisa PI, Italy · National Research Council, 56124 Pisa PI, Italy
Several graph data mining, signal processing, and machine learning downstream tasks rely on information related to the eigenvectors of the associated adjacency or Laplacian matrix. Classical eigendecomposition methods are powerful when the matrix remains static but cannot be applied to problems where the matrix entries are updated or the number of rows and columns increases frequently. Such scenarios occur routinely in graph analytics when the graph is changing dynamically and either edges and/or nodes are being added and removed. This paper puts forth a new algorithmic framework to update the eigenvectors associated with the leading eigenvalues of an initial adjacency or Laplacian matrix as the graph evolves dynamically. The proposed algorithm is based on Rayleigh-Ritz projections, in which the original eigenvalue problem is projected onto a restricted subspace which ideally encapsulates the invariant subspace associated with the sought eigenvectors. Following ideas from eigenvector perturbation analysis, we present a new methodology to build the projection subspace. The proposed framework features lower computational and memory complexity with respect to competitive alternatives while empirical results show strong qualitative performance, both in terms of eigenvector approximation and accuracy of downstream learning tasks of central node identification and node clustering.
Mohammad Eini, Abdullah Karaaslanli, Vassilis Kalantzis +1
A central challenge in dynamic network analysis is to represent temporal evolution in a way that is both geometrically meaningful and statistically identifiable. One approach embeds a sequence of network snapshots as trajectories in a Euclidean space and relates these trajectories to node embeddings. In multilayer and unfolded spectral constructions, however, node embeddings and their underlying latent positions are identifiable only up to general linear transformations. Although this ambiguity preserves edge probabilities, it can distort geometry and invalidate distance based temporal comparisons at both the trajectory and node-levels. We develop Multiscale Euclidean Network Trajectories (MENT), a framework for multiscale temporal trajectories based on second-moment geometry. By imposing an isotropic normalization on the anchor latent positions, we reduce the relevant ambiguity to orthogonal transformations and prevent distortion of the second-moment geometry. In this canonical representation, we define a trace variation distance and mode-wise variation distances along orthogonal directions, and use multidimensional scaling to obtain low-dimensional trajectories of time points at both global and mode-wise levels. The resulting trajectories support interpretation and inference. They admit mode-wise decompositions, support attribution of global and mode-wise temporal changes to nodes, and enable change point detection through 1D trajectories. We prove consistency of the proposed unfolded spectral embedding and of the induced temporal trajectories. Experiments on two synthetic and two real dynamic networks illustrate stable and interpretable recovery of temporal structure and show strong performance against existing change point detection baselines.
Haruka Ezoe, Ryohei Hisano
Graduate School of Information Science and Technology The University of Tokyo · The Canon Institute for Global Studies