Michaël Fanuel (Université de Lille)

Title : Sparsification of the magnetic Laplacian with statistical guarantees

Abstract :

Laplacian matrices are discrete analogues of Laplacian differential operators, which have applications in several areas of applied mathematics such as network science, machine learning, control, etc.
A Laplacian matrix is in general associated with a graph.
In this talk, we consider the problem of finding a controlled approximation of a Laplacian matrix — called a sparsifier — which only has a few non-zero entries.
This (sparse) matrix is associated with a graph with fewer edges, and is often cheaper to inverse.

More specifically, we consider a U(1)-connection graph, that is, a graph where each oriented edge is endowed with a unit modulus complex number which is simply conjugated under orientation flip. A natural replacement for the usual graph Laplacian is then the so-called magnetic Laplacian, a Hermitian matrix which includes information about the graph’s connection. Connection graphs and magnetic Laplacians appear, e.g., in the problem of angular synchronization (signal processing).In the context of large and dense graphs, we study spectral sparsifiers of the magnetic Laplacian, i.e., spectral approximations based on subgraphs with few edges. Our approach relies on sampling variants of spanning forests using a custom determinantal point process, a distribution over edges that favours diversity (and which originates from quantum physics).
In a word, the connected components of our spanning forests 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 information contained in the connection.
One of our contributions is to provide statistical guarantees for a choice of natural estimators of the connection Laplacian based on batches of spanning forests.

Interestingly, when the connection graph has weakly inconsistent cycles, samples of this distribution can be obtained by using a loop-erased random walk.
This sampling algorithm is called CyclePopping and is actually rather performant in practice. The law of the number of steps to complete CyclePopping is also known exactly if the connection graph has weakly inconsistent cycles.
We shall briefly discuss our contribution in the analysis of this algorithm.

This is a joint work with Rémi Bardenet (CNRS & ULille) https://arxiv.org/abs/2208.14797.