Dynamic network changes tracked by spectral braids for classification
Spectral Braids: A Topological Descriptor for Dynamic Directed Networks
Social and Information NetworksMachine Learning
Summary
Graphs often change over time, and understanding these changes helps us learn about the system they represent. The paper introduces a way to track how the key properties of a network, called eigenvalues, move over time in a directed network. These movements form patterns called braids, which the authors turn into features that help computers classify dynamic networks. This approach works better than previous methods at telling apart different types of network evolution and even distinguishes sequences of events in the network.
What this means in practice
- •For network analysts: Classify evolving online communities by analyzing changes in their dynamic directed network structures using spectral braid features.
- •For security monitoring teams: Detect and distinguish patterns of coordinated activity within changing network systems by interpreting eigenvalue braids over time.
Authors
Mehmet Emin Aktas, Esra Akbas
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.