Localization transition in symmetric random matrices

Effects of clustering heterogeneity on the spectral density of sparse networks

We derive exact equations for the spectral density of sparse networks with an arbitrary distribution of the number of single edges and triangles per node. These equations enable a systematic investigation of the effects of clustering on the spectral properties of the network adjacency matrix. In the case of heterogeneous networks, we demonstrate that the spectral density becomes more symmetric as the fluctuations in the triangle-degree sequence increase. This phenomenon is explained by the small clustering coefficient of networks with a large variance of the triangle-degree distribution. In the homogeneous case of regular clustered networks, we find that both perturbative and nonperturbative approximations fail to predict the spectral density in the high-connectivity limit. This suggests that traditional large-degree approximations may be ineffective in studying the spectral properties of networks with more complex motifs. Our theoretical results are fully confirmed by numerical diagonalizations of finite adjacency matrices.

Statistical physics of principal minors: Cavity approach

Determinants are useful to represent the state of an interacting system of (effectively) repulsive and independent elements, like fermions in a quantum system and training samples in a learning problem. A computationally challenging problem is to compute the sum of powers of principal minors of a matrix which is relevant to the study of critical behaviors in quantum fermionic systems and finding a subset of maximally informative training data for a learning algorithm. Specifically, principal minors of positive square matrices can be considered as statistical weights of a random point process on the set of the matrix indices. The probability of each subset of the indices is in general proportional to a positive power of the determinant of the associated submatrix. We use Gaussian representation of the determinants for symmetric and positive matrices to estimate the partition function (or free energy) and the entropy of principal minors within the Bethe approximation. The results are expected to be asymptotically exact for diagonally dominant matrices with locally treelike structures. We consider the Laplacian matrix of random regular graphs of degree K=2,3,4 and exactly characterize the structure of the relevant minors in a mean-field model of such matrices. No (finite-temperature) phase transition is observed in this class of diagonally dominant matrices by increasing the positive power of the principal minors, which here plays the role of an inverse temperature.

Absence of Mobility Edge in Short-Range Uncorrelated Disordered Model: Coexistence of Localized and Extended States

Unlike the well-known Mott's argument that extended and localized states should not coexist at the same energy in a generic random potential, we formulate the main principles and provide an example of a nearest-neighbor tight-binding disordered model which carries both localized and extended states without forming the mobility edge. Unexpectedly, this example appears to be given by a well-studied β ensemble with independently distributed random diagonal potential and inhomogeneous kinetic hopping terms. In order to analytically tackle the problem, we locally map the above model to the 1D Anderson model with matrix-size- and position-dependent hopping and confirm the coexistence of localized and extended states, which is shown to be robust to the perturbations of both potential and kinetic terms due to the separation of the above states in space. In addition, the mapping shows that the extended states are nonergodic and allows one to analytically estimate their fractal dimensions.

Data-driven emergence of convolutional structure in neural networks

Exploiting data invariances is crucial for efficient learning in both artificial and biological neural circuits. Understanding how neural networks can discover appropriate representations capable of harnessing the underlying symmetries of their inputs is thus crucial in machine learning and neuroscience. Convolutional neural networks, for example, were designed to exploit translation symmetry, and their capabilities triggered the first wave of deep learning successes. However, learning convolutions directly from translation-invariant data with a fully connected network has so far proven elusive. Here we show how initially fully connected neural networks solving a discrimination task can learn a convolutional structure directly from their inputs, resulting in localized, space-tiling receptive fields. These receptive fields match the filters of a convolutional network trained on the same task. By carefully designing data models for the visual scene, we show that the emergence of this pattern is triggered by the non-Gaussian, higher-order local structure of the inputs, which has long been recognized as the hallmark of natural images. We provide an analytical and numerical characterization of the pattern formation mechanism responsible for this phenomenon in a simple model and find an unexpected link between receptive field formation and tensor decomposition of higher-order input correlations. These results provide a perspective on the development of low-level feature detectors in various sensory modalities and pave the way for studying the impact of higher-order statistics on learning in neural networks.

Extended Anderson Criticality in Heavy-Tailed Neural Networks

We investigate the emergence of complex dynamics in networks with heavy-tailed connectivity by developing a non-Hermitian random matrix theory. We uncover the existence of an extended critical regime of spatially multifractal fluctuations between the quiescent and active phases. This multifractal critical phase combines features of localization and delocalization and differs from the edge of chaos in classical networks by the appearance of universal hallmarks of Anderson criticality over an extended region in phase space. We show that the rich nonlinear response properties of the extended critical regime can account for a variety of neural dynamics such as the diversity of timescales, providing a computational advantage for persistent classification in a reservoir setting.

Localization properties of the sparse Barrat-Mézard trap model

Inspired by works on the Anderson model on sparse graphs, we devise a method to analyze the localization properties of sparse systems that may be solved using cavity theory. We apply this method to study the properties of the eigenvectors of the master operator of the sparse Barrat-Mézard trap model, with an emphasis on the extended phase. As probes for localization, we consider the inverse participation ratio and the correlation volume, both dependent on the distribution of the diagonal elements of the resolvent. Our results reveal a rich and nontrivial behavior of the estimators across the spectrum of relaxation rates and an interplay between entropic and activation mechanisms of relaxation that give rise to localized modes embedded in the bulk of extended states. We characterize this route to localization and find it to be distinct from the paradigmatic Anderson model or standard random matrix systems.

Dynamical systems on large networks with predator-prey interactions are stable and exhibit oscillations

We analyze the stability of linear dynamical systems defined on sparse, random graphs with predator-prey, competitive, and mutualistic interactions. These systems are aimed at modeling the stability of fixed points in large systems defined on complex networks, such as ecosystems consisting of a large number of species that interact through a food web. We develop an exact theory for the spectral distribution and the leading eigenvalue of the corresponding sparse Jacobian matrices. This theory reveals that the nature of local interactions has a strong influence on a system's stability. We show that, in general, linear dynamical systems defined on random graphs with a prescribed degree distribution of unbounded support are unstable if they are large enough, implying a tradeoff between stability and diversity. Remarkably, in contrast to the generic case, antagonistic systems that contain only interactions of the predator-prey type can be stable in the infinite size limit. This feature for antagonistic systems is accompanied by a peculiar oscillatory behavior of the dynamical response of the system after a perturbation, when the mean degree of the graph is small enough. Moreover, for antagonistic systems we also find that there exist a dynamical phase transition and critical mean degree above which the response becomes nonoscillatory.

Quantifying the impact of network structure on speed and accuracy in collective decision-making

Found in varied contexts from neurons to ants to fish, binary decision-making is one of the simplest forms of collective computation. In this process, information collected by individuals about an uncertain environment is accumulated to guide behavior at the aggregate scale. We study binary decision-making dynamics in networks responding to inputs with small signal-to-noise ratios, looking for quantitative measures of collectivity that control performance in this task. We find that decision accuracy is directly correlated with the speed of collective dynamics, which is in turn controlled by three factors: the leading eigenvalue of the network adjacency matrix, the corresponding eigenvector's participation ratio, and distance from the corresponding symmetry-breaking bifurcation. A novel approximation of the maximal attainable timescale near such a bifurcation allows us to predict how decision-making performance scales in large networks based solely on their spectral properties. Specifically, we explore the effects of localization caused by the hierarchical assortative structure of a "rich club" topology. This gives insight into the trade-offs involved in the higher-order structure found in living networks performing collective computations.

Localization and Universality of Eigenvectors in Directed Random Graphs

Although the spectral properties of random graphs have been a long-standing focus of network theory, the properties of right eigenvectors of directed graphs have so far eluded an exact analytic treatment. We present a general theory for the statistics of the right eigenvector components in directed random graphs with a prescribed degree distribution and with randomly weighted links. We obtain exact analytic expressions for the inverse participation ratio and show that right eigenvectors of directed random graphs with a small average degree are localized. Remarkably, if the fourth moment of the degree distribution is finite, then the critical mean degree of the localization transition is independent of the degree fluctuations, which is different from localization in undirected graphs that is governed by degree fluctuations. We also show that in the high connectivity limit the distribution of the right eigenvector components is solely determined by the degree distribution. For delocalized eigenvectors, we recover in this limit the universal results from standard random matrix theory that are independent of the degree distribution, while for localized eigenvectors the eigenvector distribution depends on the degree distribution.

Theory for the conditioned spectral density of noninvariant random matrices

We develop a theoretical approach to compute the conditioned spectral density of N×N noninvariant random matrices in the limit N→∞. This large deviation observable, defined as the eigenvalue distribution conditioned to have a fixed fraction k of eigenvalues smaller than x∈R, provides the spectrum of random matrix samples that deviate atypically from the average behavior. We apply our theory to sparse random matrices and unveil strikingly different and generic properties, namely, (i) their conditioned spectral density has compact support, (ii) it does not experience any abrupt transition for k around its typical value, and (iii) its eigenvalues do not accumulate at x. Moreover, our work points towards other types of transitions in the conditioned spectral density for values of k away from its typical value. These properties follow from the weak or absent eigenvalue repulsion in sparse ensembles and they are in sharp contrast to those displayed by classic or rotationally invariant random matrices. The exactness of our theoretical findings are confirmed through numerical diagonalization of finite random matrices.

Unifying model for random matrix theory in arbitrary space dimensions

A sparse random block matrix model suggested by the Hessian matrix used in the study of elastic vibrational modes of amorphous solids is presented and analyzed. By evaluating some moments, benchmarked against numerics, differences in the eigenvalue spectrum of this model in different limits of space dimension d, and for arbitrary values of the lattice coordination number Z, are shown and discussed. As a function of these two parameters (and their ratio Z/d), the most studied models in random matrix theory (Erdos-Renyi graphs, effective medium, and replicas) can be reproduced in the various limits of block dimensionality d. Remarkably, the Marchenko-Pastur spectral density (which is recovered by replica calculations for the Laplacian matrix) is reproduced exactly in the limit of infinite size of the blocks, or d→∞, which clarifies the physical meaning of space dimension in these models. We feel that the approximate results for d=3 provided by our method may have many potential applications in the future, from the vibrational spectrum of glasses and elastic networks to wave localization, disordered conductors, random resistor networks, and random walks.

Large-deviation theory for diluted Wishart random matrices

Wishart random matrices with a sparse or diluted structure are ubiquitous in the processing of large datasets, with applications in physics, biology, and economy. In this work, we develop a theory for the eigenvalue fluctuations of diluted Wishart random matrices based on the replica approach of disordered systems. We derive an analytical expression for the cumulant generating function of the number of eigenvalues I_{N}(x) smaller than x∈R^{+}, from which all cumulants of I_{N}(x) and the rate function Ψ_{x}(k) controlling its large-deviation probability Prob[I_{N}(x)=kN]≍e^{-NΨ_{x}(k)} follow. Explicit results for the mean value and the variance of I_{N}(x), its rate function, and its third cumulant are discussed and thoroughly compared to numerical diagonalization, showing very good agreement. The present work establishes the theoretical framework put forward in a recent letter [Phys. Rev. Lett. 117, 104101 (2016)PRLTAO0031-900710.1103/PhysRevLett.117.104101] as an exact and compelling approach to deal with eigenvalue fluctuations of sparse random matrices.

Pseudo-Hermitian anti-Hermitian ensemble of Gaussian matrices

It is shown that the ensemble of pseudo-Hermitian Gaussian matrices recently introduced gives rise in a certain limit to an ensemble of anti-Hermitian matrices whose eigenvalues have properties directly related to those of the chiral ensemble of random matrices.

Localization in random bipartite graphs: Numerical and empirical study

We investigate adjacency matrices of bipartite graphs with a power-law degree distribution. Motivation for this study is twofold: first, vibrational states in granular matter and jammed sphere packings; second, graphs encoding social interaction, especially electronic commerce. We establish the position of the mobility edge and show that it strongly depends on the power in the degree distribution and on the ratio of the sizes of the two parts of the bipartite graph. At the jamming threshold, where the two parts have the same size, localization vanishes. We found that the multifractal spectrum is nontrivial in the delocalized phase, but still near the mobility edge. We also study an empirical bipartite graph, namely, the Amazon reviewer-item network. We found that in this specific graph the mobility edge disappears, and we draw a conclusion from this fact regarding earlier empirical studies of the Amazon network.

Eigenvalue Outliers of Non-Hermitian Random Matrices with a Local Tree Structure

Spectra of sparse non-Hermitian random matrices determine the dynamics of complex processes on graphs. Eigenvalue outliers in the spectrum are of particular interest, since they determine the stationary state and the stability of dynamical processes. We present a general and exact theory for the eigenvalue outliers of random matrices with a local tree structure. For adjacency and Laplacian matrices of oriented random graphs, we derive analytical expressions for the eigenvalue outliers, the first moments of the distribution of eigenvector elements associated with an outlier, the support of the spectral density, and the spectral gap. We show that these spectral observables obey universal expressions, which hold for a broad class of oriented random matrices.

Large Deviation Function for the Number of Eigenvalues of Sparse Random Graphs Inside an Interval

We present a general method to obtain the exact rate function Ψ_{[a,b]}(k) controlling the large deviation probability Prob[I_{N}[a,b]=kN]≍e^{-NΨ_{[a,b]}(k)} that an N×N sparse random matrix has I_{N}[a,b]=kN eigenvalues inside the interval [a,b]. The method is applied to study the eigenvalue statistics in two distinct examples: (i) the shifted index number of eigenvalues for an ensemble of Erdös-Rényi graphs and (ii) the number of eigenvalues within a bounded region of the spectrum for the Anderson model on regular random graphs. A salient feature of the rate function in both cases is that, unlike rotationally invariant random matrices, it is asymmetric with respect to its minimum. The asymmetric character depends on the disorder in a way that is compatible with the distinct eigenvalue statistics corresponding to localized and delocalized eigenstates. The results also show that the level compressibility κ_{2}/κ_{1} for the Anderson model on a regular graph satisfies 0<κ_{2}/κ_{1}<1 in the bulk regime, in contrast with the behavior found in Gaussian random matrices. Our theoretical findings are thoroughly compared to numerical diagonalization in both cases, showing a reasonable good agreement.

Level Statistics and Localization Transitions of Lévy Matrices

This work provides a thorough study of Lévy, or heavy-tailed, random matrices (LMs). By analyzing the self-consistent equation on the probability distribution of the diagonal elements of the resolvent we establish the equation determining the localization transition and obtain the phase diagram. Using arguments based on supersymmetric field theory and Dyson Brownian motion we show that the eigenvalue statistics is the same one as of the Gaussian orthogonal ensemble in the whole delocalized phase and is Poisson-like in the localized phase. Our numerics confirm these findings, valid in the limit of infinitely large LMs, but also reveal that the characteristic scale governing finite size effects diverges much faster than a power law approaching the transition and is already very large far from it. This leads to a very wide crossover region in which the system looks as if it were in a mixed phase. Our results, together with the ones obtained previously, now provide a complete theory of Lévy matrices.

Index statistical properties of sparse random graphs

Using the replica method, we develop an analytical approach to compute the characteristic function for the probability P(N)(K,λ) that a large N×N adjacency matrix of sparse random graphs has K eigenvalues below a threshold λ. The method allows to determine, in principle, all moments of P(N)(K,λ), from which the typical sample-to-sample fluctuations can be fully characterized. For random graph models with localized eigenvectors, we show that the index variance scales linearly with N≫1 for |λ|>0, with a model-dependent prefactor that can be exactly calculated. Explicit results are discussed for Erdös-Rényi and regular random graphs, both exhibiting a prefactor with a nonmonotonic behavior as a function of λ. These results contrast with rotationally invariant random matrices, where the index variance scales only as lnN, with an universal prefactor that is independent of λ. Numerical diagonalization results confirm the exactness of our approach and, in addition, strongly support the Gaussian nature of the index fluctuations.

Limitations in the spectral method for graph partitioning: Detectability threshold and localization of eigenvectors

Investigating the performance of different methods is a fundamental problem in graph partitioning. In this paper, we estimate the so-called detectability threshold for the spectral method with both un-normalized and normalized Laplacians in sparse graphs. The detectability threshold is the critical point at which the result of the spectral method is completely uncorrelated to the planted partition. We also analyze whether the localization of eigenvectors affects the partitioning performance in the detectable region. We use the replica method, which is often used in the field of spin-glass theory, and focus on the case of bisection. We show that the gap between the estimated threshold for the spectral method and the threshold obtained from Bayesian inference is considerable in sparse graphs, even without eigenvector localization. This gap closes in a dense limit.

Finite-size corrections to the spectrum of regular random graphs: An analytical solution

We develop a thorough analytical study of the O(1/N) correction to the spectrum of regular random graphs with N→∞ nodes. The finite-size fluctuations of the resolvent are given in terms of a weighted series over the contributions coming from loops of all possible lengths, from which we obtain the isolated eigenvalue as well as an analytical expression for the O(1/N) correction to the continuous part of the spectrum. The comparison between this analytical formula and direct diagonalization results exhibits an excellent agreement, confirming the correctness of our expression.

Spectra of sparse non-hermitian random matrices: an analytical solution

We present the exact analytical expression for the spectrum of a sparse non-hermitian random matrix ensemble, generalizing two standard results in random-matrix theory: this analytical expression constitutes a non-hermitian version of the Kesten-McKay measure as well as a sparse realization of Girko's elliptic law. Our exact result opens new perspectives in the study of several physical problems modelled on sparse random graphs, which are locally treelike. In this context, we show analytically that the convergence rate of a transport process on a very sparse graph depends in a nonmonotonic way upon the degree of symmetry of the graph edges.

Spectra of sparse regular graphs with loops

We derive exact equations that determine the spectra of undirected and directed sparsely connected regular graphs containing loops of arbitrary lengths. The implications of our results for the structural and dynamical properties of network models are discussed by showing how loops influence the size of the spectral gap and the propensity for synchronization. Analytical formulas for the spectrum are obtained for specific lengths of the loops.