Powers of Magnetic Graph Matrix: Fourier Spectrum, Walk Compression, and Applications

Yinan Huang, David F. Gleich, Pan Li

Abstract

Directed graphs (digraphs) are fundamental to modeling complex systems but present challenges for classical spectral analysis due to their asymmetric adjacency matrices. Magnetic graphs address this by introducing complex phases to edges, yielding Hermitian matrices. This paper establishes a formal link between the powers of magnetic matrices and classical combinatorics, proving that these powers are Discrete Fourier Transforms of bidirectional walk counts, termed "Walk Profiles." This theoretical bridge enables efficient walk compression and enhances performance in directed motif detection and link prediction across diverse real-world networks.

Introduction

Directed graphs underpin diverse domains, from neural circuits to social networks. However, their analysis is complicated by the asymmetry of their adjacency matrices, which precludes the use of standard spectral tools. Magnetic graphs were proposed as a solution, assigning complex phases to edges to create a Hermitian matrix. While the spectral properties of these matrices have been studied, the combinatorial interpretation of their powers remained elusive. This work reveals that the $m$-th power of a magnetic matrix $A_q^m$ encodes local graph structure through a Fourier relationship with bidirectional walks.

The core innovation is the definition of Walk Profiles, $\Phi_{u,v}(m, k)$, which count the number of $m$-step bidirectional walks between nodes $u$ and $v$ consisting of exactly $k$ forward edges and $m-k$ backward edges.

Walk profiles $\Phi_{u,v}(m, k)$ represent the count of bidirectional walks between node pairs based on the number of forward edges $k$.

The authors prove that the $m$-th power of the magnetic adjacency matrix $A_q$ is the Discrete Fourier Transform (DFT) of these walk profiles, where the magnetic potential $q$ acts as the frequency. This provides a rigorous mathematical grounding for why magnetic graphs are effective: the magnetic potential $q$, often treated as a tuning parameter, is formally revealed to be a Fourier frequency.

Powers of the magnetic matrix $A_q^m$ for different magnetic potentials $q$, representing the Fourier-transformed state of the walk profiles.

Using this connection, the authors develop methods for exact reconstruction of walk profiles and "Walk Compression." Much like natural images can be compressed because they contain mostly low-frequency information, walk profiles in real-world graphs are highly compressible, with structural "energy" concentrated in low frequencies.

Applications and Results

The study evaluates its findings on a suite of 26 real-world networks across biological, social, and computational domains.

Walk Compression

For many real-world networks, using only $m/5$ magnetic potentials (e.g., 10 potentials for a 50-step walk) is sufficient to reconstruct the walk profile with less than 5% error. The compressibility is tied to a graph's "frustration index"—how much directed edges conflict with a global ordering.

Magnetic matrix features significantly outperform standard undirected walk baselines in detecting directed motifs. For instance, in identifying cycles with one backward edge (common in biological control systems), the method achieved near-perfect AUC scores. Furthermore, on datasets like Bio-drug and Cora-ML, features derived from magnetic walk profiles consistently outperformed traditional methods like Personalized PageRank and Common Neighbors for link prediction.

Discussion and Limitations

While powerful, walk profiles have an inherent "ordering ambiguity": they count the number of backward edges but not their sequence. Consequently, they cannot distinguish between different non-isomorphic cycles if they share the same total count of forward and backward edges. Additionally, calculating high powers of large matrices for multiple $q$ values remains computationally intensive for web-scale graphs. Future work may explore non-backtracking walks to provide cleaner structural signals by removing redundant information.

Conclusion

By revealing the Fourier nature of magnetic graph matrices, this work provides a rigorous mathematical foundation for their use in network science. The ability to compress and reconstruct directed walk information opens new avenues for scalable graph analysis and machine learning on directed structures.

Summary updated

BibTeX
@inproceedings{huang2026powers,
  author = {Yinan Huang and David F. Gleich and Pan Li},
  title = {{Powers of Magnetic Graph Matrix: Fourier Spectrum, Walk Compression, and Applications}},
  booktitle = {Proceedings of the National Academy of Sciences},
  year = {2026},
  doi = {10.1073/pnas.2516664123},
}
Figure