# Sparsification of the regularized magnetic Laplacian with multi-type spanning forests

arXiv: https://arxiv.org/abs/2208.14797 · HTML: https://mlsanity.com/paper/2208.14797/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 84 references that are in the map.
- First posted on arXiv 31 Aug 2022.

## Builds on (most cited first, 21 of 21)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [FALKON: An Optimal Large Scale Kernel Method](https://mlsanity.com/paper/1705.10958/) (2017)
- [Near-optimal bounds for phase synchronization](https://mlsanity.com/paper/1703.06605/) (2017)
- [Uniform Sampling for Matrix Approximation](https://mlsanity.com/paper/1408.5099/) (2014)
- [Magnetic Eigenmaps for the Visualization of Directed Networks](https://mlsanity.com/paper/1606.08266/) (2016)
- [Robust Group Synchronization via Cycle-Edge Message Passing](https://mlsanity.com/paper/1912.11347/) (2019)
- [Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time](https://mlsanity.com/paper/1508.03261/) (2015)
- [Sync-Rank: Robust Ranking, Constrained Ranking and Rank Aggregation via Eigenvector and Semidefinite Programming Synchronization](https://mlsanity.com/paper/1504.01070/) (2015)
- [Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates](https://mlsanity.com/paper/1506.04838/) (2015)
- [Exact Sampling of Determinantal Point Processes without Eigendecomposition](https://mlsanity.com/paper/1802.08429/) (2018)
- [Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions](https://mlsanity.com/paper/1805.12051/) (2018)
- [Sparsified Cholesky and Multigrid Solvers for Connection Laplacians](https://mlsanity.com/paper/1512.01892/) (2015)
- [Sampling Random Spanning Trees Faster than Matrix Multiplication](https://mlsanity.com/paper/1611.07451/) (2016)
- [An almost-linear time algorithm for uniform random spanning tree generation](https://mlsanity.com/paper/1711.06455/) (2017)
- [A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees](https://mlsanity.com/paper/1810.08345/) (2018)
- [Fast Generation of Random Spanning Trees and the Effective Resistance Metric](https://mlsanity.com/paper/1501.00267/) (2015)
- [Graph Tikhonov Regularization and Interpolation via Random Spanning Forests](https://mlsanity.com/paper/2011.10450/) (2020)
- [Fundamentals of Partial Rejection Sampling](https://mlsanity.com/paper/2106.07744/) (2021)
- [Unsupervised Ensembling of Multiple Software Sensors with Phase Synchronization: A Robust Approach For Electrocardiogram-derived Respiration](https://mlsanity.com/paper/2006.13054/) (2020)
- [Tight bounds for popping algorithms](https://mlsanity.com/paper/1807.01680/) (2018)
- [Approximately counting bases of bicircular matroids](https://mlsanity.com/paper/1808.09548/) (2018)

## Built on by (most cited first, 1 of 1)

- [Graph Neural Networks for Edge Signals: Orientation Equivariance and Invariance](https://mlsanity.com/paper/2410.16935/) (2024)

## Abstract (arXiv)

In this paper, we consider a rm U(1)-connection graph, that is, a graph where each oriented edge is endowed with a unit modulus complex number that is conjugated under orientation flip. A natural replacement for the combinatorial Laplacian is then the magnetic Laplacian, an Hermitian matrix that includes information about the graph's connection. Magnetic Laplacians appear, e.g., in the problem of angular synchronization. In the context of large and dense graphs, we study here sparsifiers of the magnetic Laplacian Delta, i.e., spectral approximations based on subgraphs with few edges. Our approach relies on sampling multi-type spanning forests (MTSFs) using a custom determinantal point process, a probability distribution over edges that favours diversity. In a word, an MTSF is a spanning subgraph whose connected components are either trees or cycle-rooted trees. The latter partially capture the angular inconsistencies of the connection graph, and thus provide a way to compress the information contained in the connection. Interestingly, when the connection graph has weakly inconsistent cycles, samples from the determinantal point process under consideration can be obtained `a la Wilson, using a random walk with cycle popping. We provide statistical guarantees for a choice of natural estimators of the connection Laplacian, and investigate two practical applications of our sparsifiers: ranking with angular synchronization and graph-based semi-supervised learning. From a statistical perspective, a side result of this paper of independent interest is a matrix Chernoff bound with intrinsic dimension, which allows considering the influence of a regularization -- of the form Delta + q mathbbI with q>0 -- on sparsification guarantees.