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

The walk matrices of real data are often highly compressible

These plot how accurately we recover the walk profiles from fewer frequencies than required.

Why does this work

sometimes (ER with high degree) and not others (ER with low degree) ?

What determines compressibility?

It’s the spectral radius !

If this is near 1 (for the random walk veresions), then we get no convergence, whereas if this is smaller, we get rapid decay.

Why does this work

sometimes (ER with high degree) and not others (ER with low degree) ?

What determines compressibility?

It’s the spectral radius !

If this is near 1 (for the random walk veresions), then we get no convergence, whereas if this is smaller, we get rapid decay.

It’s the spectral radius that determines how compressible a walk profile is

Computational and Program Graphs are the least compressible here (along with a few biological graphs). That’s because they are _almost_ directed trees and trees have

Can we use powers of the magnetic adjacency matrix to find cycles?

- Yes, if there is only one backward edge and we don’t count repeated nodes

- No if there is more than one backward edge and we don’t count repeated nodes

What about in practice?

We train a classifier to predict if node is involved in a length cycle using

- Magnetic adjacency powers

- "Drop direction” graph powers

- Unidirectional walks: or

The blue line shows what happens with powers of the magnetic adjacency as we use more potentials. The other lines are fixed.

Walk profiles (red) does well. The magnetic potentials quickly converge to that behavior.

rw is undirected walks

rw+ is unidirectional walks

wp is

walk profiles

These magnetic Adjacency matrices also help improve a link prediction task

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

Fourier spectrum・Walk compression ・Applications

POWERS OF THE MAGNETIC GRAPH MATRIX

We present a combinatorial interpretation of powers of magnetic graph matrices that fundamentally reveals how these matrices encode local network structure.