Magnetic Matrix Powers

Fourier spectrum・Walk compression ・Applications

POWERS OF THE MAGNETIC GRAPH MATRIX

David F. Gleich

Purdue University

Joint work with Pan Li and Yinan Huang

Georgia Tech

Work supported by NSF, DOE. Main publication is https://doi.org/10.1073/pnas.2516664123. Code available https://github.com/Graph-COM/Walk_Profiles

1. Powers of the Magnetic Matrix

2. The Problem with Directed Graphs

3. The History of the Magenetic Matrix

4. Walk Profiles

5. The Proof of our Main Theorem

6. Walk compression

7. Motifs and Applications

POWERS OF THE ADJACENCY MATRIX

counts walks

Powers of the Probability Matrix

evaluates walk probabilities

evaluates

????

The “magnetic” adjacency matrix that arose from quantum mechanics …

more on this later!

POWERS OF THE MAGNETIC MATRIX

Betweenness Centrality

- the number of paths between between without / number of shortest paths from

Katz Centrality

- the number of walks from where each link in the walk is weighted

PageRank centrality

- the probability of walking from where each link in the walk is weighted by

… and more! communicability, etc. …

Walk Counting is Central to Centrality in Network Analysis

Walk Counting leads to

spectral analysis

Repeated powering of a matrix spectral analysis

… but this only works well for undirected graphs …

Weighted undirected graphs, Laplacians, Random Walks

are all basically the same concept

if we make the graph directed,

then all of this equivalence breaks down

The problem is that spectral analysis has … issues … for directed graph

THE PROBLEM IS THAT SPECTRAL ANALYSIS HAS … ISSUES … FOR DIRECTED GRAPH

Okay, so it’s 2026, What have people done about this and why are you still talking?

Drop direction entirely [ baseline ]

Explicitly symmetrize the matrix [ another baseline ]

Use singular values instead of eigenvalues [Dhillon 2001, Rohe, Qin, Yu 2012 ... even earlier in biliometrics?]

Use directed graph directly [ Boley et al. 2011, Steward 1994 ]

and things like asymmetric Laplacians, hitting times, etc.

Flow-based circulation [Chung 2005]

Benson, Gleich, Leskovec (2016)

Given , enumerate directed motifs in , then analyze the weighted clique projection of the hypergraph where each clique is a hyperedge.

Liu & Li 2015, Guo & Mohar 2017

with 1 for each bidirection edge and for , for for each directed edge

Mohar 2020

with on the unit circle.

… and then some complex ideas …

Benson, Gleich, Leskovec (2016)

Given , enumerate directed motifs in , then analyze the weighted clique projection of the hypergraph where each clique is a hyperedge.

Liu & Li 2015, Guo & Mohar 2017

with 1 for each bidirection edge and for , for for each directed edge

Mohar 2020

with on the unit circle.

… and then some complex ideas …

Other uses for complex values in Network Analysis

see big survey from Mason Porter et al.

Constantine & Gleich, Random Alpha PageRank; (Lemma 6) Gleich & Rossi, PageRank with Dynamic Teleportation

Liu & Li 2015, Guo & Mohar 2017

with 1 for each bidirection edge and for , for for each directed edge

Mohar 2020

with on the unit circle.

We use the Mohar 2020 construction here.

Both are called “magnetic adjacency” matrices.

Where does this come from?

The magnetic Laplacian!

Put an electron in a plane with with a grid-like crystal structure. Where is the electron?

Where does the

Magnetic Laplacian Come from?

for

the standard 5-point Laplacian matrix on a grid-graph.

for

the standard 5-point Laplacian matrix on a grid-graph.

Where does the

Magnetic Laplacian Come from?

Put an electron in a plane with with a grid-like crystal structure. Where is the electron?

Where does the

Magnetic Laplacian Come from?

Citations you’ll see for this.

Harper 1955. Posed the problem of an electron in a magnetic field and all the relevant simplications.

Sunada/Shubin 1994. What if we don’t just use a grid graph and make it more general?

Mohar & Guo 2017, Liu & Li 2015.

for directed edges, for bidrectional.

Mohar 2020.

USES WITH DATA

Fanuel et al. 2017/2018. Magnetic Laplacians for Eigenmaps.

Cloninger 2017. Markov normalized magnetic Eigenmaps.

Cucuringu et al. 2020. Use in community detection.

Where does the

Magnetic Laplacian Come from?

- adjacency matrix for a simple directed graph.

Mohar’s construction

does NOT result in

The Harper operator
The Liu & Li / Mohar& Guo operator

for any choice of

you need to allow allow edge phases or

more topology / algebra in the construction

The same, EQuivalent, And Slightly different when starting from Data

- adjacency matrix for a simple directed graph.

Mohar’s construction

does NOT result in

The Harper operator
The Liu & Li / Mohar& Guo operator

for any choice of

you need to allow allow edge phases or

more topology / algebra in the construction

THE SAME, EQUIVALENT, AND SLIGHTLY DIFFERENT WHEN STARTING FROM DATA

… onto walk profiles …

Let be a graph.

Let be the directed adjacency matrix.

is the number of bidirectional walks

from of length with exactly forward edges.

all edges are forward edges.

all edges are backwards edges.

Walk Profiles are one generalization of Walk Counts to directed Graphs

… and we take a big binomial expansions …

crossterms: all arrangements of choices for and of

Group crossterms by phase

… and then some complex ideas …

… and we take a big binomial expansions …

crossterms: all arrangements of choices for and of

Group crossterms by phase

… and then some complex ideas …

… and we take a big binomial expansions …

crossterms: all arrangements of choices for and of

Group crossterms by phase

… and then some complex ideas …

… and we take a big binomial expansions …

crossterms: all arrangements of choices for and of

Group crossterms by phase

… and then some complex ideas …

THEOREM

Pick values of that give distinct over the unit circle.

Let be a generalized Fourier matrix with

Let be the magnetic matrix powers and let .

Let

Then

Our main Theorem

Walk Counts and the Magnetic Matrix

We can use the standard choice of q’s around the unit circle to get a unitary matrix.

We can simplify much the complex arithmetic

since we know that the walk matrices are real.

with

Variations on our main Theorem

The equivalence can be adapted

for powers of any of the following matrices

- adjacency (what we saw)

- random walk

- normalized adjacency

Using gives the expected probabilistic interpretation and keeps all the “counts” normalized to probabilities

The real data demos use the random walk version.

Variations on our main Theorem

Matrices admit low-rank decompositions

Can we get walk-profiles with fewer than modes?

Spectral density as we vary the magnetic parameter shows a Decay regime

This plots the magnitude of