Estimating a graph’s spectrum via random Kirchhoff forests

Simon, Fabienne, Alexandre, Clothilde, Matteo, Nicolas · 2025

Read Estimating a graph’s spectrum via random Kirchhoff forests by Simon, Fabienne, Alexandre, Clothilde, Matteo, Nicolas (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-24236.txt.

Introduction

Finding every eigenvalue of a huge graph matrix is hopeless, but Simon Barthelmé and five co-authors argue the overall shape of the spectrum is within reach. Standard estimators work through the spectrum's moments, global averages that Monte Carlo methods can sample. Their twist uses Kirchhoff forests, random collections of trees drawn on the graph itself.

Those forests give access to certain non-linear moments of the graph's Laplacian matrix, which moment-based methods could not reach before. Combined in the right way, the moments sketch the spectral density, the curve showing where eigenvalues bunch and thin. When modest precision suffices, the approach could estimate a graph's spectrum in time growing more slowly than the number of its links.

Catalog record

CREATORSimon, Fabienne, Alexandre, Clothilde, Matteo, Nicolas
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE24 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-24236

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Estimating a graph’s spectrum via random Kirchhoff forests Simon, Fabienne, Alexandre, Clothilde, Matteo, Nicolas Abstract Pour des matrices de grande taille, la décomposition spectrale exacte est trop coûteuse, et on ne peut calculer toutes les valeurs propres. Un objectif plus modeste consiste à approcher la loi empirique des valeurs propres, pour connaître approximativement leur répartition. Les approches classiques utilisent des estimateurs de Monte Carlo pour obtenir une estimation des moments de la loi des valeurs propres. Dans cet article, nous introduisons une nouvelle approche pour ce problème, basée sur des forêts aléatoires sur graphes dites forêts de Kirchhoff. Nous montrons comment certaines observables de ces forêts peuvent être exploitées pour obtenir des estimateurs de la densité spectrale empirique de laplaciens de grands graphes. Si la précision souhaitée de l’estimation n’est pas trop importante, notre approche ouvre la voie à des estimations spectrales de graphes en temps sous-linéaire en le nombre de liens. † † address: [email protected] † † email: 1 † † address: [email protected] † † email: 2 † † address: [email protected] † † email: 3 † † address: [email protected] † † email: 2 † † address: [email protected] † † email: 4 † † address: [email protected] † † email: 1,5 † † affiliation: CNRS, Univ Grenoble-Alpes, Grenoble-INP, GIPSA-lab, Grenoble, France Aix-Marseille Univ, I2M, Marseille, France CNRS & Aix-Marseille Univ, I2M, Marseille, France Department of Mathematics & Physics, Università di Roma Tre, Rome, Italy Department of Mathematics & Statistics, UiT the Arctic University of Norway, Tromsø, Norway 1 Introduction Computing † † footnotetext: Work partially funded by the ANR project GRANOLA (ANR-21-CE48-0009) and the European Union (Marie Curie project Rand4TrustPool, 101148828). the exact eigenvalue decomposition of a large symmetric matrix \bm{L}\in\mathbb{R}^{n\times n} has cost \mathcal{O}(n^{3}) in general, and becomes quickly out of reach for matrices with n>10^{4} . In some cases, all that is needed is an estimate of the p largest or smallest eigenvalues, and this can be achieved using a variety of Krylov subspace methods [ 15 ] . In other cases, what is required is an estimate of the distribution of all eigenvalues, an important quantity in various applications [ 17 ] . Specifically, letting \lambda_{1}\dots\lambda_{n} stand for the eigenvalues of \bm{L} , the goal is to estimate: c(\tau)=\frac{1}{n}\sum_{i=1}^{n}\bm{\mathds{I}}(\lambda_{i}\leq\tau) (1) for all \tau . Here c(\tau) measures the fraction of eigenvalues that are smaller than the threshold \tau . In what follows, it is useful to think of the function c(\tau) as the cumulative density function of the empirical distribution of the eigenvalues, i.e. the discrete measure \mu=\frac{1}{n}\sum_{i}\delta_{\lambda_{i}}. (2) To estimate the c.d.f. c(\tau) , the standard approach is to first estimate moments of the empirical distribution (the estimation step) then to reconstruct the cumulative density function from the estimated moments (the reconstruction step). In the existing literature, the estimation step takes advantage of the fact that moments of the empirical measure \mu correspond to traces of powers of \bm{L} : \mu(\lambda^{j})\stackrel{{\scriptstyle\textrm{def}}}{{=}}\int^{j}\lambda^{j}\text{d}\mu(x)=\frac{1}{n}\sum_{i}\lambda_{i}^{j}=\frac{1}{n}Tr(\bm{L}^{j}) (3) Computing \Tr(\bm{L}^{j}) is expensive in general, but stochastic trace estimators [ 17 , 11 ] like the Hutchinson-Girard estimator can be used. For any random vector \bm{z} with \mathbb{E}(\bm{z})=0 and \mathbb{E}(\bm{z}\bm{z}^{t})=\bm{I} , we have: \mathbb{E}(\bm{z}^{t}\bm{L}^{j}\bm{z})=Tr(\bm{L}^{j}) (4) and in this way traces can be computed by taking successive matrix-vector products starting from a random vector \bm{z} . In the reconstruction step, one tries to reconstruct the cdf of \mu from knowledge of its p first moments. Various techniques are available, the most effective are Jackson-Chebyshev expansions [ 6 ] and the stochastic Lanczos quadrature [ 4 ] . The cost of these techniques scales with the cost of a matrix-vector product \bm{L}\bm{z} , which itself scales with |\mathcal{E}| , the number of edges of the graph. For the very sparse systems that arise from discretising Partial Differential Equations, they are very effective, but in denser systems they can be quite costly. In what follows we describe a graph-theoretic approach for this problem that is based on a specific random process called the “Kirchhoff forest”. Kirchhoff forests are a certain kind of random forests on graphs, with a range of applications in randomised linear algebra and graph signal processing [ 13 , 8 , 2 ] . We follow the same idea of estimating expectations under the empirical distribution \mu , followed by a reconstruction step. However, our method is conceptually different from the literature: instead on relying on the computation of quadratic forms \bm{z}^{t}\bm{L}^{j}\bm{z} which prevents existing methods to improve the |\mathcal{E}| term in the total computation cost, our method is based on sampling random forests of the graph and, under certain assumptions, scales in \mathcal{O}(n) rather than |\mathcal{E}| . The downside of this is that, at this stage, our method is only competitive if one only needs a medium-accuracy estimation of the graph’s spectrum. Section 2 introduces Kirchoff forests and how they can be used to estimate certain spectral expectations. Section 3 outlines the reconstruction method. Section 4 gives some numerical results illustrating how our method outperforms the state-of-the-art if one only requires medium accuracy. 2 Forests for moment estimation In what follows we assume that \bm{L} is the Laplacian matrix of a weighted, undirected graph G=(\mathcal{V},\mathcal{E}) with n nodes and |\mathcal{E}| edges: \bm{L}=\bm{D}-\bm{A} (5) where \bm{A} is the adjacency matrix and \bm{D} the degree matrix. See [ 3 ] for how to extend this to diagonally-dominant \bm{L} . We denote by \mu(f) the expectation of function f under the empirical spectral measure: \mu(f)=\frac{1}{n}\sum_{i}f(\lambda_{i}) (6) Kirchhoff forests are random spanning forests on graphs that are particularly easy to sample, and enable efficient estimators of various quantities tied to the graph Laplacian [ 3 , 13 , 9 ] . In the context of graph theory, a spanning forest is a subgraph of G , made up of disjoint trees (acyclic subgraphs), and such that every node belongs to the forest (the spanning part). The concept is illustrated on fig. 1 (left). Figure 1: (Left) Illustration of a rooted spanning forest on the 5x5 grid graph, containing 4 trees, the smallest of which is a trivial tree of size 1. Each tree contains a distinguished node called the root. Kirchhoff Forests (KFs) produce random rooted spanning forests with distribution given by eq. ( 7 ). (Right) Illustration of a cdf estimation of a graph’s spectrum , using our KF-based algorithm (for l=1,2,3 moments), on a Barabasi-Albert graph, with n=10^{3} and \bar{d}=20 . A Kirchoff Forest (KF) is a distribution on rooted spanning forests. A forest is said to be rooted if every tree has a distinguished node called the root (see fig. 1 ). If the tree contains a single node, then the root of the tree is the node itself. KFs are defined by the following probability mass function: p_{q}(\phi)=\frac{|R(\phi)|^{q}}{Z_{q}}\prod_{ij\in\mathcal{E}(\phi)}w_{ij} (7) Here \phi is a forest with edge set \mathcal{E}(\phi) and roots R(\phi) . Z_{q} is a normalisation constant, and q is a parameter that governs the average number of roots in the random forest. Large values of q favor a large number of roots. In fact, as shown in [ 1 ] : \mathbb{E}(|R(\phi)|)=\sum_{i=1}^{n}\frac{q}{q+\lambda_{i}}=n\;\mu(q/(q+\cdot)) (8) [ 3 ] used this relationship to define inverse trace estimators. Here we go further and show how to estimate various non-linear expectations under \mu . KFs have the

Read the complete text