Sparsification of the regularized magnetic Laplacian with multi-type spanning forests
This work addresses the computational challenge of handling dense magnetic Laplacians in graph-based tasks like angular synchronization, offering a sparsification method with theoretical bounds, though it appears incremental as it builds on existing sparsification and determinantal point process techniques.
The paper tackles the problem of sparsifying the magnetic Laplacian for large, dense graphs with U(1)-connections, using multi-type spanning forests sampled via a determinantal point process to create spectral approximations with few edges. It provides statistical guarantees for estimators and demonstrates applications in ranking and semi-supervised learning.
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 $Δ$, 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 à 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 $Δ+ q \mathbb{I}$ with $q>0$ -- on sparsification guarantees.