Powers of Magnetic Graph Matrix: Fourier Spectrum, Walk Compression, and Applications
Yinan Huang, David F. Gleich, Pan Li · 2025
Read Powers of Magnetic Graph Matrix: Fourier Spectrum, Walk Compression, and Applications by Yinan Huang, David F. Gleich, Pan Li (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-07343.txt.
Introduction
Yinan Huang, David Gleich, and Pan Li find a hidden pattern in the powers of a matrix built for directed networks. Magnetic graphs encode direction by adding phases to a graph's matrix, a trick borrowed from quantum physics. Past work used the matrix's spectrum to read global traits, but its powers, which capture local behavior over steps, were little explored. Their paper appeared in 2025.
The team shows that the powers count walks on the graph, sorted by how many edges each walk runs against the arrows. Those walk profiles turn out to be a Fourier transform of the matrix powers, so profiles can be rebuilt exactly from powers at a few phase settings. In real networks even fewer settings give a good rebuild, which means the data compress well. They show uses in spotting frustrated directed loops and in predicting missing links.
Catalog record
| CREATOR | Yinan Huang, David F. Gleich, Pan Li |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 60 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-07343
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Powers of Magnetic Graph Matrix: Fourier Spectrum, Walk Compression, and Applications Yinan Huang, David F. Gleich, Pan Li Abstract Abstract Magnetic graphs, originally developed to model quantum systems under magnetic fields, have recently emerged as a powerful framework for analyzing complex directed networks. Existing research has primarily used the spectral properties of the magnetic graph matrix to study global and stationary network features. However, their capacity to model local, non-equilibrium behaviors, often described by matrix powers, remains largely unexplored. We present a novel combinatorial interpretation of the magnetic graph matrix powers through directed walk profiles—counts of graph walks indexed by the number of edge reversals. Crucially, we establish that walk profiles correspond to a Fourier transform of magnetic matrix powers. The connection allows exact reconstruction of walk profiles from magnetic matrix powers at multiple discrete potentials, and more importantly, an even smaller number of potentials often suffices for accurate approximate reconstruction in real networks. This shows the empirical compressibility of the information captured by the magnetic matrix. This fresh perspective suggests new applications; for example, we illustrate how powers of the magnetic matrix can identify frustrated directed cycles (e.g., feedforward loops) and can be effectively employed for link prediction by encoding local structural details in directed graphs. Magnetic graphs are complex-weighted graphs in which each edge is assigned a complex phase. Originally developed to model the effects of external magnetic fields on electrons in lattice systems ( 1 ; 2 ; 3 ; 4 ; 5 ; 6 ) , magnetic graphs have recently proven to be powerful tools for analyzing complex systems with asymmetric interactions ( 7 ; 8 ; 9 ; 10 ) . These graphs encode edge directionality through complex phases in their matrix representations, such as adjacency or Laplacian matrix. For instance, the spectrum of magnetic graph Laplacians has been used to reveal community structures in directed cycles ( 11 ) and to enhance visualization of directed networks ( 12 ; 13 ) . More recently, magnetic graphs have inspired novel signal processing and machine learning models tailored to directed graphs ( 14 ; 15 ; 16 ) . Additionally, magnetic graph Laplacians can be interpreted as connection graph Laplacians associated with the SO(2) group ( 17 ) , enabling further applications in angular synchronization ( 18 ; 19 ) and high-dimensional data analysis via diffusion maps ( 20 ) . Previous studies on the magnetic graph matrix have primarily focused on how their eigenvalues and eigenvectors encode the topological properties of directed graphs ( 11 ; 12 ; 13 ; 21 ) . Such spectral information is widely recognized for capturing global and stationary characteristics of graphs ( 22 ) . In contrast, modeling local or non-equilibrium behaviors often requires the analysis of random walks, quantum walks, or diffusion processes ( 23 ; 22 ; 24 ) , which are often characterized by the powers of the graph matrix. For undirected graphs, these processes have been extensively studied and proven effective for detecting local communities and node clusters ( 25 ; 26 ; 27 ; 28 ) , quantifying node centrality (e.g., PageRank ( 29 ; 30 ) , Katz index ( 31 ) ) and measuring node proximity ( 32 ; 33 ) . However, their counterparts on magnetic graphs remain relatively underexplored. This stems not only from the complex-valued nature of the magnetic matrix, whose powers resist straightforward application of standard Markov process theory ( 11 ) , but also critically, from the lack of a clear combinatorial interpretation that links the matrix power to the underlying directed network topology. In this article, we investigate the powers of the magnetic graph matrix to uncover properties of local network behaviors encoded in directed graph topologies. Our primary finding is that the m -th power of the magnetic graph adjacency matrix with magnetic potential q naturally corresponds to the Fourier transform of a bidirectional walk statistic, which we term the Walk Profile . Specifically, the m -step walk profile consists of bidirectional walk counts of length m , indexed by the number of edge reversals. These ideas also give probabilistic interpretations when using the normalized adjacency matrix, in which case, these walk counts become the corresponding bidirectional random walk landing probabilities. This result is significant as it reveals a fundamental connection between the behaviors on magnetic graphs captured by powers of the magnetic matrix and the combinatorial structure of the underlying directed graphs, described by walk profiles. It also offers a novel physical interpretation of the magnetic potential q as the Fourier transform frequency. Importantly, this connection implies that by evaluating magnetic matrix powers at a finite set of discrete potentials, one can reconstruct the entire m -step bidirectional walk profiles via inverse Fourier transforms, thereby enabling the expression of magnetic matrix powers at arbitrary values of potential q . In theory, to exactly reconstruct the m -step walk profiles, evaluating magnetic matrix powers at \lfloor m/2\rfloor+1 distinct frequencies q is required. However, for most random and real-world graphs, we demonstrate that significantly fewer frequencies often provide an accurate approximate reconstruction, as the energy of the walk profiles predominantly concentrates in the low-frequency region. The accuracy of this compression depends on the spectral radius of the magnetic graph matrix, which is related to the smallest eigenvalue of the magnetic graph Laplacian and its associated frustration index ( 21 ) . This relationship enables us to characterize directed graphs whose walk profiles are either easily compressible or resistant to compression, by analyzing the eigenvalues of their corresponding magnetic graph matrix. Regarding practical applications, we further explore the feasibility of capturing diverse directed motifs using magnetic matrix powers with a varying number of potentials. In particular, we demonstrate that these representations can detect minimally frustrated directed cycles , i.e., directed cycles perturbed by a single reversed edge, which extend beyond purely directed cycles emphasized in previous spectral analyses of magnetic Laplacians ( 11 ) . The minimally frustrated directed cycles include feedforward loops, a prominent three-node motif prevalent in control systems and biological networks ( 34 ) . Finally, we employ magnetic matrix powers as structural features for directed graphs in link prediction tasks, aimed at inferring missing directed edges in incomplete networks. The strong performance of these features highlights their effectiveness in encoding local structural information of directed graphs. Magnetic graph matrix and walk profiles Figure 1: Illustrations of walk profiles and its Fourier transforms. a , An example of computing walk profiles \Phi_{1,4}(3,2) , the number of 3 -step bidirectional walks from node 1 to node 4 with 2 forward edges and 1 backward edges. The graph is given in the left figure and the three repetitions show the three different paths counted in \Phi_{1,4}(3,2) . b , The collection of walk profiles \Phi_{u,v}(3,k),k=0,...,3 on the same graph, and how its Fourier transform relates to the powers of the magnetic adjacency matrix. We first define Walk Profiles that captures bidirectional walk patterns of a directed graph, and we will then show how powers of the magnetic matrix are inherently connected to walk profiles (see Figure 1 ). Let \mathcal{G} be a directed graph with asymmetric adjacency matrix A , where A_{u,v}=1 if u connects to