Powers of magnetic graph matrix: Fourier spectrum, walk compression, and applications

Yinan Huang, David F. Gleich, Peng Li

TL;DR

This paper introduces a novel way to understand magnetic graph matrices by connecting their powers to "walk profiles," which count directed walks with specific numbers of forward and backward steps. This connection reveals that magnetic matrix powers are essentially Fourier transforms of these walk profiles, allowing for efficient compression and enabling new applications in detecting network motifs and predicting links.

What Problem Does This Paper Address?

Directed networks are crucial for modeling complex systems with asymmetric interactions, but analyzing them with traditional spectral methods has been challenging due to their inherent asymmetry. While magnetic graphs offer a promising framework by using complex-valued edge weights to encode directionality, their analysis has largely focused on global, stationary properties. The authors identify a gap in understanding how magnetic graph matrices can capture local, non-equilibrium behaviors, which are often described by matrix powers. They aim to bridge this gap by providing a combinatorial interpretation of these matrix powers and demonstrating their utility in analyzing directed network structures.

Methods

The core of this paper lies in establishing a connection between the powers of the magnetic graph adjacency matrix ($A_q^m$) and "walk profiles" ($\Phi_{u,v}(m, k)$). Walk profiles quantify the number of $m$-step bidirectional walks between nodes $u$ and $v$ that involve exactly $k$ forward edges and $m-k$ backward edges. The authors demonstrate that the $m$-th power of the magnetic graph matrix is a Fourier transform of the walk profile vector at a specific frequency related to the magnetic potential $q$. This Fourier transform relationship allows for the reconstruction of walk profiles from magnetic matrix powers evaluated at a discrete set of potentials. Crucially, they show that for many real-world networks, only a small subset of these potentials is needed for accurate reconstruction, indicating "compressibility" of the information. They also explore the use of normalized magnetic adjacency matrices for probabilistic interpretations.

Datasets

The authors evaluate their methods on a diverse set of datasets, including:

  • Synthetic Directed Networks:
    • Erdős-Rényi (ER) random graphs with varying degrees.
  • Scale-free random directed graphs.
  • Real-world Directed Networks: 26 networks from 8 domains, including:
  • Biological: Caenorhabditis elegans (Celegans), Figeys, Drug-drug, Drug-target, Bio-functions, Protein-protein.
  • Citation: Cora_ML, Citeseer, Ogbn-arxiv, Arxiv HEP-TH.
  • Social: Adolescent health, High-school, Epinion, Wikipedia vote.
  • Information: Political blogs, Email.
  • Transportation: Air traffic control, US airports.
  • Emerging Domains: Program graphs (Ogbg-code2) and TPU computational graphs (AlexNet, ResNet, Transformer, BERT).

Key Insights and Ideas

  • Walk Profiles as a Combinatorial Interpretation: The paper provides a concrete combinatorial meaning to the powers of magnetic graph matrices by linking them to counts of directed walks with specific forward/backward edge ratios. This is a significant step beyond purely spectral analyses.
  • Magnetic Matrix Powers as Fourier Transforms: The core insight is that $A_q^m$ is a Fourier transform of the walk profile vector. This re-frames the analysis of magnetic matrices and opens up signal processing techniques.
  • Compressibility of Network Information: The finding that walk profiles can be accurately reconstructed from a small number of magnetic matrix powers (i.e., a few potentials) suggests that directed network structures are inherently compressible. This has implications for efficient representation and analysis.
  • Spectral Radius as a Predictor of Compressibility: The spectral radius of the magnetic matrix is shown to be a strong indicator of how compressible the walk profiles are. Networks with a decaying spectral radius tend to have more compressible walk profiles.
  • Detecting "Frustrated" Cycles: The framework allows for the identification of directed cycles with at most one backward edge (e.g., feed-forward loops), which are missed by traditional undirected walk methods.

Key Results

  • Motif Detection: The proposed method, using walk profiles and magnetic matrix powers, achieves competitive or superior performance in detecting minimally frustrated directed cycles (cycles with at most one backward edge) compared to baseline methods. For instance, in Figure 5, the magnetic matrix approach with varying potentials shows strong AUC scores for detecting cycles of different lengths.
  • Link Prediction: Magnetic adjacency matrix powers and walk profiles consistently outperform baseline methods in link prediction tasks. Figure 6 shows that magnetic walk methods (mw) achieve high AUCROC scores across various datasets, often surpassing other techniques. Notably, even with just one potential, the magnetic matrix approach is competitive.
  • Compressibility Validation: Figure 3 and Figure 9 demonstrate that for most networks, a small number of potentials (e.g., less than $m/5$) is sufficient to achieve low reconstruction errors (around 5%) for walk profiles.
  • Correlation between Spectral Radius and Compressibility: Figure 4 and Figure 10 show a strong positive correlation ($r=0.95$) between the spectral radius of the magnetic matrix and the compressibility of walk profiles.

Limitations and Future Work

  • Limitations:
    • The paper notes that walk profiles (and thus magnetic matrix powers) cannot differentiate between directed cycles with two or more backward edges, as they only count the number of backward edges, not their specific ordering.
  • For certain graph structures, like directed trees, the spectral radius is always 1, leading to poor compressibility.
  • Future Work:
    • The authors suggest exploring non-backtracking random walks in relation to their framework.
  • Further investigation into the relationship between graph structure, spectral radius, and compressibility is implied.
  • The potential for applying this framework to other types of network analysis beyond motif detection and link prediction is highlighted.

Summary updated

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, nonequilibrium behaviors, often described by matrix powers, remains largely unexplored. We present a 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 further 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.
BibTeX
@inproceedings{huang2026powers,
  author = {Yinan Huang and David F. Gleich and Peng 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