pith. sign in

arxiv: 2606.28188 · v1 · pith:CBC7BCBMnew · submitted 2026-06-26 · 💻 cs.DS

An Exponential Lower Bound for Spectral Density Estimation on Unweighted Graphs

Pan Peng , Yuyang Wang , Joy Qiping Yang , Yichun Yang This is my paper

Pith reviewed 2026-06-29 01:52 UTC · model grok-4.3

classification 💻 cs.DS
keywords spectral density estimationrandom walkslower boundsunweighted graphsnormalized adjacency matrixWasserstein distancequery complexityapproximation algorithms
0
0 comments X

The pith

No algorithm can approximate the normalized adjacency spectrum of unweighted graphs to ε using subexponentially many random walk transcripts.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves an exponential lower bound for ε-approximating the spectral density of the normalized adjacency matrix on unweighted graphs in the Wasserstein-1 distance. It shows that even with access to the full transcripts of 2^Ω(1/ε^{1/6}) random walks each of length 2^Ω(1/ε^{1/6}) started from uniformly random nodes, no algorithm succeeds with constant probability. This extends the prior lower bound known only for weighted graphs and resolves the open question for unweighted graphs. A reader would care because it demonstrates fundamental limits of the random walk transcript model for spectral estimation even on simple graphs.

Core claim

No algorithm can compute an ε-approximation to the spectrum of a normalized graph adjacency matrix with constant success probability, even when given the full transcripts of 2^Ω(1/ε^{1/6}) random walks, each of length 2^Ω(1/ε^{1/6}), started from uniformly random nodes, and this holds for unweighted graphs.

What carries the argument

The random-walk transcript oracle, which supplies complete sequences of node visits from walks initiated at uniformly random starting nodes and is used to establish hardness via a family of unweighted graphs.

Load-bearing premise

The algorithm can only access transcripts of random walks started from uniformly random nodes in the graph.

What would settle it

An algorithm that achieves an ε-approximation to the spectrum with constant success probability using o(2^{1/ε^{1/6}}) random walk transcripts of length o(2^{1/ε^{1/6}}) on every unweighted graph.

Figures

Figures reproduced from arXiv: 2606.28188 by Joy Qiping Yang, Pan Peng, Yichun Yang, Yuyang Wang.

Figure 1
Figure 1. Figure 1: Illustration of our constructions G1 and G2. 4 Large W1-distance between spectral densities of G1 and G2 In this section we prove the following theorem, showing that there is a polynomial large gap between ρAG1 and ρAG2 in terms of Wasserstein-1 distance with high probability. Theorem 4.1. Let G1 and G2 be as defined in Definition 3.1 with constant d ≥ 7 and n ≥ ℓ 7d 2 . Then it holds that W1(ρAG1 ,ρAG2 ) … view at source ↗
Figure 2
Figure 2. Figure 2: Testing W1(ρAG1 ,ρAG2 ) D Numerical experiments for measuring W1(ρAG1 ,ρAG2 ) Given parameters n, d, and ℓ, the eigenvalues of G1 and G2 can be computed exactly from our construction. In this section, we study the W1 distance between ρAG1 and ρAG2 by varying ℓ. Specifically, we fix n = 10,000 and d = 7, and let ℓ range from 10 to 300. Figures 2 (a) and (b) show the eigenvalues of G1 and G2 for ℓ = 10, whil… view at source ↗
read the original abstract

We study lower bounds for estimating the spectral density of the normalized adjacency matrix of a graph. Previously, Cohen-Steiner et al. [KDD 2018] proposed an algorithm for $\varepsilon$-approximate spectral density estimation in the Wasserstein-1 distance, using $2^{O(1/\varepsilon)}$ random walks initiated from uniformly random nodes in the graph. Later, Jin et al. [COLT 2023] established a nearly matching exponential lower bound for \emph{weighted} graphs, assuming the algorithm has access to samples from random walks started at random nodes. It was left open whether this lower bound could be extended to \emph{unweighted} graphs. In this paper, we answer this question in the affirmative by proving an exponential lower bound for unweighted graphs. Specifically, we show that no algorithm can compute an $\varepsilon$-approximation to the spectrum of a normalized graph adjacency matrix with constant success probability, even when given the full transcripts of $2^{\Omega(1/\varepsilon^{1/6})}$ random walks, each of length $2^{\Omega(1/\varepsilon^{1/6})}$, started from uniformly random nodes.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The paper proves an exponential lower bound for ε-approximating the spectral density of the normalized adjacency matrix of an unweighted graph to within Wasserstein-1 distance. It shows that no algorithm succeeds with constant probability even when given the full transcripts of 2^Ω(1/ε^{1/6}) random walks of length 2^Ω(1/ε^{1/6}) started from uniformly random nodes, thereby affirmatively resolving the open question left by Jin et al. for the unweighted case.

Significance. If the proof is correct, the result is significant: it demonstrates that the exponential sample complexity established by Jin et al. for weighted graphs carries over to unweighted graphs, which form the standard setting for many applications. Combined with the matching upper bound of Cohen-Steiner et al., this yields a nearly tight characterization of the query complexity in the uniform-start random-walk transcript model. The construction of suitable hard unweighted instances is the key technical contribution.

minor comments (1)
  1. [Abstract] The abstract cites Cohen-Steiner et al. [KDD 2018] and Jin et al. [COLT 2023] but does not include full bibliographic details; adding the complete references in the bibliography section would improve traceability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the paper and their recommendation to accept.

Circularity Check

0 steps flagged

No significant circularity; lower bound is a direct proof extension

full rationale

The paper constructs a new exponential lower bound for unweighted graphs in the random-walk transcript oracle model, directly answering an open question from Jin et al. The derivation is a mathematical proof establishing hardness for distinguishing spectra in W1 distance; it does not reduce any claimed result to a fitted parameter, self-definition, or load-bearing self-citation. The cited prior work (Jin et al.) has non-overlapping authors and is used only as the weighted-graph baseline being extended. No equations or steps in the provided abstract or description exhibit the enumerated circularity patterns. The result is scoped precisely to the stated oracle and remains falsifiable via the proof technique.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The lower bound rests on the standard random-walk transcript model from prior literature; no free parameters, new entities, or ad-hoc axioms are visible in the abstract.

axioms (1)
  • domain assumption Algorithms have access only to full transcripts of random walks started at uniformly random nodes.
    This is the query model inherited from Cohen-Steiner et al. and Jin et al. as referenced in the abstract.

pith-pipeline@v0.9.1-grok · 5743 in / 1164 out tokens · 24450 ms · 2026-06-29T01:52:11.847124+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

102 extracted references · 1 linked inside Pith

  1. [1]

    The Thirty Eighth Annual Conference on Learning Theory , pages=

    Sharper Bounds for Chebyshev Moment Matching, with Applications , author=. The Thirty Eighth Annual Conference on Learning Theory , pages=. 2025 , organization=

    2025

  2. [2]

    Foundations of Computational Mathematics , volume=

    Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time , author=. Foundations of Computational Mathematics , volume=. 2023 , publisher=

    2023

  3. [3]

    1998 , publisher=

    The symmetric eigenvalue problem , author=. 1998 , publisher=

    1998

  4. [4]

    Communications in Mathematical Physics , volume=

    Local Kesten--McKay law for random regular graphs , author=. Communications in Mathematical Physics , volume=. 2019 , publisher=

    2019

  5. [5]

    ECCC, TR19-102 , year=

    Testing isomorphism in the bounded-degree graph model , author=. ECCC, TR19-102 , year=

  6. [6]

    Inverse problems for symmetric doubly stochastic matrices whose Sule

    Gnacik, Micha. Inverse problems for symmetric doubly stochastic matrices whose Sule. Linear Algebra and its Applications , volume=. 2020 , publisher=

    2020

  7. [7]

    real-world

    Spectra of “real-world” graphs: Beyond the semicircle law , author=. Physical Review E , volume=. 2001 , publisher=

    2001

  8. [8]

    Wilkinson , journal =

    J.H. Wilkinson , journal =. Global convergene of tridiagonal QR algorithm with origin shifts , volume =

  9. [9]

    Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time , year=

    Banks, Jess and Garza-Vargas, Jorge and Kulkarni, Archit and Srivastava, Nikhil , booktitle=. Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time , year=

  10. [10]

    Faster Spectral Density Estimation and Sparsification in the Nuclear Norm , author=

  11. [11]

    and Srivastava, Nikhil , journal =

    Spielman, Daniel A. and Srivastava, Nikhil , journal =. Graph Sparsification by Effective Resistances , year =

  12. [12]

    Randomized Algorithms for Estimating the Trace of an Implicit Symmetric Positive Semi-Definite Matrix , year =

    Avron, Haim and Toledo, Sivan , journal =. Randomized Algorithms for Estimating the Trace of an Implicit Symmetric Positive Semi-Definite Matrix , year =

  13. [13]

    , journal =

    Hutchinson, Michael F. , journal =. A stochastic estimator of the trace of the influence matrix for

  14. [14]

    Meyer and Cameron Musco and Christopher Musco and David Woodruff , journal =

    Raphael A. Meyer and Cameron Musco and Christopher Musco and David Woodruff , journal =

  15. [15]

    Fast Attributed Graph Embedding via Density of States , year =

    Sawlani, Saurabh and Zhao, Lingxiao and Akoglu, Leman , booktitle =. Fast Attributed Graph Embedding via Density of States , year =

  16. [16]

    Computing Spectral Measures of Self-Adjoint Operators , year =

    Colbrook, Matthew and Horning, Andrew and Townsend, Alex , journal =. Computing Spectral Measures of Self-Adjoint Operators , year =

  17. [17]

    Estimating Sizes of Social Networks via Biased Sampling , year =

    Katzir, Liran and Liberty, Edo and Somekh, Oren , booktitle =. Estimating Sizes of Social Networks via Biased Sampling , year =

  18. [18]

    Ugur Guney and Yann Dauphin and Leon Bottou , journal =

    Levent Sagun and Utku Evci and V. Ugur Guney and Yann Dauphin and Leon Bottou , journal =. Empirical Analysis of the Hessian of Over-Parametrized Neural Networks , year =

  19. [19]

    The Full Spectrum of Deepnet Hessians at Scale: Dynamics with

    Vardan Papyan , journal =. The Full Spectrum of Deepnet Hessians at Scale: Dynamics with

  20. [20]

    An Investigation into Neural Net Optimization via Hessian Eigenvalue Density , year =

    Ghorbani, Behrooz and Krishnan, Shankar and Xiao, Ying , booktitle =. An Investigation into Neural Net Optimization via Hessian Eigenvalue Density , year =

  21. [21]

    Traditional and Heavy Tailed Self Regularization in Neural Network Models , year =

    Mahoney, Michael and Martin, Charles , booktitle =. Traditional and Heavy Tailed Self Regularization in Neural Network Models , year =

  22. [22]

    The emergence of spectral universality in deep networks , year =

    Jeffrey Pennington and Samuel Schoenholz and Surya Ganguli , booktitle =. The emergence of spectral universality in deep networks , year =

  23. [23]

    Calculating the density of states and optical-absorption spectra of large quantum systems by the plane-wave moments method , year =

    Wang, Lin-Wang , issue =. Calculating the density of states and optical-absorption spectra of large quantum systems by the plane-wave moments method , year =. Phys. Rev. B , publisher =

  24. [24]

    Silver, R.N. and R. Densities of States of Mega-Dimensional Hamiltonian Matrices , volume =. International Journal of Modern Physics C , number =

  25. [25]

    The Eigenvalues of Mega-dimensional Matrices

    Skilling, John. The Eigenvalues of Mega-dimensional Matrices. Maximum Entropy and Bayesian Methods: Cambridge, England, 1988. 1989

    1988

  26. [26]

    The Eigenvalues Slicing Library (

    Li, Ruipeng and Xi, Yuanzhe and Erlandson, Lucas and Saad, Yousef , journal =. The Eigenvalues Slicing Library (

  27. [27]

    Approximating Spectral Densities of Large Matrices , volume =

    Lin, Lin and Saad, Yousef and Yang, Chao , journal =. Approximating Spectral Densities of Large Matrices , volume =

  28. [28]

    Reviews of modern physics , volume=

    The kernel polynomial method , author=. Reviews of modern physics , volume=. 2006 , publisher=

    2006

  29. [29]

    Network density of states , year =

    Dong, Kun and Benson, Austin R and Bindel, David , booktitle =. Network density of states , year =

  30. [30]

    Approximating the Spectrum of a Graph , year =

    Cohen-Steiner, David and Kong, Weihao and Sohler, Christian and Valiant, Gregory , booktitle =. Approximating the Spectrum of a Graph , year =

  31. [31]

    Sublinear Time Spectral Density Estimation , year =

    Braverman, Vladimir and Krishnan, Aditya and Musco, Christopher , booktitle =. Sublinear Time Spectral Density Estimation , year =

  32. [32]

    CoRR , volume =

    Vladimir Braverman and Aditya Krishnan and Christopher Musco , title =. CoRR , volume =. 2021 , url =

    2021

  33. [33]

    Fast linear algebra is stable , volume =

    Demmel, James and Dumitriu, Ioana and Holtz, Olga , journal =. Fast linear algebra is stable , volume =

  34. [34]

    Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap , year =

    Kwok, Tsz Chiu and Lau, Lap Chi and Lee, Yin Tat and Oveis Gharan, Shayan and Trevisan, Luca , booktitle =. Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap , year =

  35. [35]

    18th International Workshop on Algorithms in Bioinformatics (WABI 2018) , year =

    Majewski, Szymon and Ciach, Michal Aleksander and Startek, Michal and Niemyska, Wanda and Miasojedow, Blazej and Gambin, Anna , title =. 18th International Workshop on Algorithms in Bioinformatics (WABI 2018) , year =

    2018

  36. [36]

    Spectral and Algebraic Graph Theory , year =

    Spielman, Daniel , chapter =. Spectral and Algebraic Graph Theory , year =

  37. [37]

    Spectrum estimation from samples , volume =

    Weihao Kong and Gregory Valiant , journal =. Spectrum estimation from samples , volume =

  38. [38]

    Wolfram Koepf , publisher =

  39. [39]

    L. V. Kantorovich , journal =. Mathematical Methods of Organizing and Planning Production , volume =

  40. [40]

    On a functional space and certain extremum problems , volume =

    Kantorovich, Leonid Vital'evich and Rubinshtein, Gennadii Shlemovich , booktitle =. On a functional space and certain extremum problems , volume =

  41. [41]

    2001 , issn =

    Maximal Energy Graphs , journal =. 2001 , issn =

    2001

  42. [42]

    1990 , publisher=

    Matrix Perturbation Theory , author=. 1990 , publisher=

    1990

  43. [43]

    , title = "

    Mirsky, L. , title = ". The Quarterly Journal of Mathematics , volume =. 1960 , month =

    1960

  44. [44]

    Moments, Random Walks, and Limits for Spectrum Approximation , author =

  45. [45]

    2011 , note =

    The energy of random graphs , journal =. 2011 , note =

    2011

  46. [46]

    Bandeira and Ramon van Handel , title =

    Afonso S. Bandeira and Ramon van Handel , title =. The Annals of Probability , number =

  47. [47]

    Electronic Communications in Probability , publisher =

    Alice Guionnet and Ofer Zeitouni , title =. Electronic Communications in Probability , publisher =

  48. [48]

    Journal of Mathematical Analysis and Applications , volume=

    The energy of graphs and matrices , author=. Journal of Mathematical Analysis and Applications , volume=. 2007 , publisher=

    2007

  49. [49]

    Almost-linear-time algorithms for markov chains and new spectral primitives for directed graphs , author=

  50. [50]

    , title =

    Eikmeier, Nicole and Gleich, David F. , title =. 2017 , booktitle =

    2017

  51. [51]

    Analysis of stochastic Lanczos quadrature for spectrum approximation , year =

    Tyler Chen and Thomas Trogdon and Shashanka Ubaru , booktitle =. Analysis of stochastic Lanczos quadrature for spectrum approximation , year =

  52. [52]

    Sublinear-time Algorithms , year =

    Czumaj, Artur and Sohler, Christian , booktitle =. Sublinear-time Algorithms , year =

  53. [53]

    2013 , journal=

    Probabilistic Spectral Sparsification In Sublinear Time , author=. 2013 , journal=. 1401.0085 , archivePrefix=

    Pith/arXiv arXiv 2013

  54. [54]

    2023 , booktitle=

    Linear-Sized Sparsifiers via Near-Linear Time Discrepancy Theory , author=. 2023 , booktitle=

    2023

  55. [55]

    SIAM Journal on Computing , volume=

    Constructing linear-sized spectral sparsification in almost-linear time , author=. SIAM Journal on Computing , volume=. 2018 , publisher=

    2018

  56. [56]

    SIAM Journal on Computing , volume=

    Spectral sparsification of graphs , author=. SIAM Journal on Computing , volume=. 2011 , publisher=

    2011

  57. [57]

    Communications of the ACM , volume=

    Spectral sparsification of graphs: theory and algorithms , author=. Communications of the ACM , volume=. 2013 , publisher=

    2013

  58. [58]

    SIAM Journal on computing , volume=

    Approximating the minimum spanning tree weight in sublinear time , author=. SIAM Journal on computing , volume=. 2005 , publisher=

    2005

  59. [59]

    , author=

    Sublinear-time approximation of Euclidean minimum spanning tree. , author=

  60. [60]

    A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size , author=

  61. [61]

    2017 , organization=

    Sublinear time estimation of degree distribution moments: The degeneracy connection , author=. 2017 , organization=

    2017

  62. [62]

    Information Processing Letters , volume=

    Estimating the number of connected components in sublinear time , author=. Information Processing Letters , volume=. 2014 , publisher=

    2014

  63. [63]

    On approximating the number of k-cliques in sublinear time , author=

  64. [64]

    arXiv preprint arXiv:2004.12002 , year=

    Finding planted cliques in sublinear time , author=. arXiv preprint arXiv:2004.12002 , year=

    arXiv 2004

  65. [65]

    Distributed Computing , pages=

    Sublinear-time distributed algorithms for detecting small cliques and even cycles , author=. Distributed Computing , pages=. 2022 , publisher=

    2022

  66. [66]

    , author=

    Sublinear time approximate clustering. , author=

  67. [67]

    Spectral clustering oracles in sublinear time , author=

  68. [68]

    Proceedings of the AAAI conference on artificial intelligence , volume=

    Approximate k-means++ in sublinear time , author=. Proceedings of the AAAI conference on artificial intelligence , volume=

  69. [69]

    Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Sublinear-Time Algorithms for Max Cut, Max E2Lin (q), and Unique Label Cover on Expanders , author=. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2023 , organization=

    2023

  70. [70]

    2021 , school=

    Sublinear Algorithms for Spectral Graph Clustering , author=. 2021 , school=

    2021

  71. [71]

    , title =

    Musco, Cameron and Netrapalli, Praneeth and Sidford, Aaron and Ubaru, Shashanka and Woodruff, David P. , title =

  72. [72]

    , title =

    Swartworth, William and Woodruff, David P. , title =. 2023 , booktitle =

    2023

  73. [73]

    Bhattacharjee, Rajarshi and Dexter, Gregory and Drineas, Petros and Musco, Cameron and Ray, Archan , title =

  74. [74]

    Faster matrix multiplication via asymmetric hashing , author=

  75. [75]

    and Srivastava, Nikhil , journal =

    Batson, Joshua and Spielman, Daniel A. and Srivastava, Nikhil , journal =. Twice-

  76. [76]

    Single Pass Spectral Sparsification in Dynamic Streams , volume =

    Michael Kapralov and Yin Tat Lee and Cameron Musco and Christopher Musco and Aaron Sidford , journal =. Single Pass Spectral Sparsification in Dynamic Streams , volume =

  77. [77]

    Approximating

    Bencz\'. Approximating

  78. [78]

    Testing the expansion of a graph , volume =

    Asaf Nachmias and Asaf Shapira , date-modified =. Testing the expansion of a graph , volume =. Information and Computation , number =

  79. [79]

    Testing Expansion in Bounded-Degree Graphs , year =

    Czumaj, Artur and Sohler, Christian , booktitle =. Testing Expansion in Bounded-Degree Graphs , year =

  80. [80]

    On Testing Expansion in Bounded-Degree Graphs , year =

    Goldreich, Oded and Ron, Dana , booktitle =. On Testing Expansion in Bounded-Degree Graphs , year =

Showing first 80 references.