Spectral braids turn eigenvalue crossings into features for directed networks
Original title: Spectral Braids: A Topological Descriptor for Dynamic Directed Networks
Burau features from tracked complex eigenvalues reach 97.1% accuracy on four synthetic classes, versus 44.5% without eigenvalue tracking.
Spectral braids treat the movement of complex eigenvalues of community-level transition matrices on dynamic directed networks as topological braids. Each snapshot's eigenvalues are tracked, the braid is recorded as a word, and the Burau representation maps that word to a fixed-size classifier feature. On synthetic online-community networks labeled by how they evolved between the same start and end states, the features reach 97.1% accuracy on four classes, against 44.5% for the best set that does not track eigenvalues. Burau features also separate networks with the same events in a different order, which crossing counts cannot.
Unconfirmed: The claim of being the first braid-and-monodromy study on graph data is the authors' own assessment.
- Each snapshot becomes a community-level transition matrix.
- Eigenvalue crossings are read as a braid word.
- The Burau representation yields a fixed-size feature vector.
- Accuracy is 97.1% versus 44.5% without eigenvalue tracking.
- The authors say this is the first braid feature study on graph data.
From the original article
1 min read at arxiv.orgEigenvalues 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.
By Mehmet Emin Aktas · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.