Cavity and replica methods for the spectral density of sparse symmetric random matrices

Submission summary

 As Contributors: Pierpaolo Vivo Arxiv Link: https://arxiv.org/abs/2101.08029v4 (pdf) Date accepted: 2021-07-16 Date submitted: 2021-07-08 15:40 Submitted by: Vivo, Pierpaolo Submitted to: SciPost Physics Lecture Notes Academic field: Physics Specialties: Statistical and Soft Matter Physics Approach: Theoretical

Abstract

We review the problem of how to compute the spectral density of sparse symmetric random matrices, i.e. weighted adjacency matrices of undirected graphs. Starting from the Edwards-Jones formula, we illustrate the milestones of this line of research, including the pioneering work of Bray and Rodgers using replicas. We focus first on the cavity method, showing that it quickly provides the correct recursion equations both for single instances and at the ensemble level. We also describe an alternative replica solution that proves to be equivalent to the cavity method. Both the cavity and the replica derivations allow us to obtain the spectral density via the solution of an integral equation for an auxiliary probability density function. We show that this equation can be solved using a stochastic population dynamics algorithm, and we provide its implementation. In this formalism, the spectral density is naturally written in terms of a superposition of local contributions from nodes of given degree, whose role is thoroughly elucidated. This paper does not contain original material, but rather gives a pedagogical overview of the topic. It is indeed addressed to students and researchers who consider entering the field. Both the theoretical tools and the numerical algorithms are discussed in detail, highlighting conceptual subtleties and practical aspects.

Published as SciPost Phys. Lect. Notes 33 (2021)

Dear Editor,

we would like to resubmit our paper \textit{Cavity and replica methods for the spectral density of sparse symmetric random matrices} for publication in Sci Post Lecture Notes series.

After reviewing our revised version, one of the referees (Report 2 received 25th May 2021) has provided additional comments that we would like to address in this letter.

\begin{enumerate}

\item \textit{After eq. (128), the authors say that the normalization of the spectral density is fulfilled at any order in $1/c$, since the $1/c$ correction is even. It gives
the impression that this is a sufficient condition, which is not really precise. It is more correct to say that normalization implies that the integral of $\rho_1(x)$ over [-2,2] is zero. An analogous counterexample appears in the calculation of the $1/N$ correction to the spectral density of regular random graphs: the $1/N$ correction to the Kesten-McKay distribution is not an even function around $x=0$, but its integral is zero.}

We agree with the referee. To this purpose we have modified the main text after Eq. (128).

\item \textit{Below eq. (164), the authors argue that this equation may cease to be valid above the percolation transition, because of the presence of cycles. If this is correct and the tree-like assumption fails, why does the spectral density is well captured by the cavity equations above percolation? Besides that, there is plenty of evidence in other fields (spin-glasses, information science, etc) that the tree-like assumption holds above the percolation threshold, so the argument of the authors is not really supported by evidence. }

In the paragraph below Eq.\,(164), we did not wish to imply that the cavity method fails entirely above the percolation threshold due to the presence of loops. Indeed its continued usefulness is clearly demonstrated by its ability to capture the spectral density of sparse matrices, as extensively demonstrated and discussed in the review. Instead, what we meant to be saying is that Eq.\,(164), i.e.

{\rm Im}\, G(\lambda_\varepsilon)_{ii} = \mathrm{Re}\left[ \frac{1}{\omega_i}\right] = \pi \sum_\alpha \delta_\varepsilon(\lambda-\lambda_\alpha) u_{i\alpha}^2

may in the $\varepsilon\to0$-limit not allow one to correctly infer the statistics of squared eigenvector components $u_{i\alpha}^2$, when evaluated using the cavity method in situations where it is only approximate, despite the fact that its summed version

\rho_J(\lambda)=\lim_{\varepsilon\to 0^+}\frac{1}{\pi N} \mathrm{Im} \sum_{i=1}^N G(\lambda_\varepsilon)_{ii}
\label{eq:sum_identity}

apparently does reproduce the spectral density rather well.

This need not be a contradiction, as the sum (2) may very well be robust against the approximations induced by the cavity method (which fails to be exact above the percolation threshold), even though its individual contributions Eq. (1) may not.

One possible, and indeed plausible mechanism is that an approximate evaluation of Eq.\,(1) using the cavity method may --- for quasi-degenerate eigenvalues in the continuous part of the spectrum --- effectively replace the eigenvector components appearing in Eq.\,(1) (and thus (2)) by components of vectors which are in fact superpositions or hybridizations of eigenvectors corresponding to several quasi-degenerate eigenvalues, i.e. by

{\rm Im}\, G(\lambda_\varepsilon)_{ii} = \mathrm{Re}\left[ \frac{1}{\omega_i}\right] \simeq \pi \sum_\alpha \delta_\varepsilon(\lambda-\lambda_\alpha) \tilde u_{i\alpha}^2\ ,

in which the $\tilde u_{i\alpha}$ are linear superpositions of the form $\tilde u_{i\alpha} = \sum_{\mu \in I_\alpha} c_{\mu\alpha} u_{i\alpha}$. Assuming these superpositions to respect normalization, one immediately sees, that such a mechanism can induce even large discrepancies between the $u_{i\alpha}$ and the $\tilde u_{i\alpha}$ while leaving the spectral density as evaluated in terms of Eq. (2) unmodified due to orthonormality of the true eigenvectors.

We have modified the text after Eq.\,(164) to make this issue clearer in the revised manuscript.
\end{enumerate}

We trust that with these clarifications the paper is now ready to be accepted for publication in Sci Post Lecture Notes series.

Yours faithfully,

Vito Antonio Rocco Susca, Pierpaolo Vivo and Reimer K\"uhn