Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Faster Spectral Density Estimation and Sparsification in the Nuclear Norm
We consider the problem of estimating the spectral density of the normalized adjacency matrix of an $$n$$-node undirected graph. We provide a randomized algorithm that, with $$O(n\epsilon^{-2})$$ queries to a degree and neighbor oracle and in $$O(n\epsilon^{-3})$$ time, estimates the spectrum up to $$\epsilon$$ accuracy in the Wasserstein-1 metric. This improves on previous state-of-the-art methods, including an $$O(n\epsilon^{-7})$$ time algorithm from [Braverman et al., STOC 2022] and, for sufficiently small $$\epsilon$$, a $$2^{O(\epsilon^{-1})}$$ time method from [Cohen-Steiner et al., KDD 2018]. To achieve this result, we introduce a new notion of graph sparsification, which we call \emph{nuclear sparsification}. We provide an $$O(n\epsilon^{-2})$$-query and $$O(n\epsilon^{-2})$$-time algorithm for computing $$O(n\epsilon^{-2})$$-sparse nuclear sparsifiers. We show that this bound is optimal in both its sparsity and query complexity, and we separate our results from the related notion of additive spectral sparsification. Of independent interest, we show that our sparsification method also yields the first \emph{deterministic} algorithm for spectral density estimation that scales linearly with $$n$$ (sublinear in the representation size of the graph).  more » « less
Award ID(s):
2045590
PAR ID:
10576237
Author(s) / Creator(s):
; ; ; ;
Publisher / Repository:
Proceedings of Machine Learning Research
Date Published:
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ; (, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020)
    null (Ed.)
    We present a general framework of designing efficient dynamic approximate algorithms for optimization on undirected graphs. In particular, we develop a technique that, given any problem that admits a certain notion of vertex sparsifiers, gives data structures that maintain approximate solutions in sub-linear update and query time. We illustrate the applicability of our paradigm to the following problems. (1) A fully-dynamic algorithm that approximates all-pair maximum-flows/minimum-cuts up to a nearly logarithmic factor in $$\tilde{O}(n^{2/3})$$ amortized time against an oblivious adversary, and $$\tilde{O}(m^{3/4})$$ time against an adaptive adversary. (2) An incremental data structure that maintains $O(1)$-approximate shortest path in $$n^{o(1)}$$ time per operation, as well as fully dynamic approximate all-pair shortest path and transshipment in $$\tilde{O}(n^{2/3+o(1)})$$ amortized time per operation. (3) A fully-dynamic algorithm that approximates all-pair effective resistance up to an $$(1+\eps)$$ factor in $$\tilde{O}(n^{2/3+o(1)} \epsilon^{-O(1)})$$ amortized update time per operation. The key tool behind result (1) is the dynamic maintenance of an algorithmic construction due to Madry [FOCS' 10], which partitions a graph into a collection of simpler graph structures (known as j-trees) and approximately captures the cut-flow and metric structure of the graph. The $O(1)$-approximation guarantee of (2) is by adapting the distance oracles by [Thorup-Zwick JACM `05]. Result (3) is obtained by invoking the random-walk based spectral vertex sparsifier by [Durfee et al. STOC `19] in a hierarchical manner, while carefully keeping track of the recourse among levels in the hierarchy. 
    more » « less
  2. ; ; ; (, Proceedings of Thirty Sixth Conference on Learning Theory)
    We study lower bounds for the problem of approximating a one dimensional distribution given (noisy) measurements of its moments. We show that there are distributions on $[-1,1]$ that cannot be approximated to accuracy $$\epsilon$$ in Wasserstein-1 distance even if we know \emph{all} of their moments to multiplicative accuracy $$(1\pm2^{-\Omega(1/\epsilon)})$$; this result matches an upper bound of Kong and Valiant [Annals of Statistics, 2017]. To obtain our result, we provide a hard instance involving distributions induced by the eigenvalue spectra of carefully constructed graph adjacency matrices. Efficiently approximating such spectra in Wasserstein-1 distance is a well-studied algorithmic problem, and a recent result of Cohen-Steiner et al. [KDD 2018] gives a method based on accurately approximating spectral moments using $$2^{O(1/\epsilon)}$$ random walks initiated at uniformly random nodes in the graph.As a strengthening of our main result, we show that improving the dependence on $$1/\epsilon$$ in this result would require a new algorithmic approach. Specifically, no algorithm can compute an $$\epsilon$$-accurate approximation to the spectrum of a normalized graph adjacency matrix with constant probability, even when given the transcript of $$2^{\Omega(1/\epsilon)}$$ random walks of length $$2^{\Omega(1/\epsilon)}$$ started at random nodes. 
    more » « less
  3. ; ; ; ; ; ; ; (, Proceedings of the 2021 {ACM-SIAM} Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021)
    null (Ed.)
    Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether $$(1+\epsilon)$$-approximate cut-preserving vertex sparsifiers with size close to the number of terminals exist. As a step towards this goal, we initiate the study of a thresholded version of the problem: for a given parameter $$c$$, find a smaller graph, which we call \emph{connectivity-$$c$$ mimicking network}, which preserves connectivity among $$k$$ terminals exactly up to the value of $$c$$. We show that connectivity-$$c$$ mimicking networks of size $O(kc^4)$ exist and can be found in time $$m(c\log n)^{O(c)}$$. We also give a separate algorithm that constructs such graphs of size $$k \cdot O(c)^{2c}$$ in time $$mc^{O(c)}\log^{O(1)}n$$. These results lead to the first offline data structures for answering fully dynamic $$c$$-edge-connectivity queries for $$c \ge 4$$ in polylogarithmic time per query as well as more efficient algorithms for survivable network design on bounded treewidth graphs. 
    more » « less
  4. ; (, International Conference on Machine Learning)
    We study the densest subgraph problem and give algorithms via multiplicative weights update and area convexity that converge in $$O\left(\frac{\log m}{\epsilon^{2}}\right)$$ and $$O\left(\frac{\log m}{\epsilon}\right)$$ iterations, respectively, both with nearly-linear time per iteration. Compared with the work by Bahmani et al. (2014), our MWU algorithm uses a very different and much simpler procedure for recovering the dense subgraph from the fractional solution and does not employ a binary search. Compared with the work by Boob et al. (2019), our algorithm via area convexity improves the iteration complexity by a factor $$\Delta$$ — the maximum degree in the graph, and matches the fastest theoretical runtime currently known via flows (Chekuri et al., 2022) in total time. Next, we study the dense subgraph decomposition problem and give the first practical iterative algorithm with linear convergence rate $$O\left(mn\log\frac{1}{\epsilon}\right)$$ via accelerated random coordinate descent. This significantly improves over $$O\left(\frac{m\sqrt{mn\Delta}}{\epsilon}\right)$$ time of the FISTA-based algorithm by Harb et al. (2022). In the high precision regime $$\epsilon\ll\frac{1}{n}$$ where we can even recover the exact solution, our algorithm has a total runtime of $$O\left(mn\log n\right)$$, matching the state of the art exact algorithm via parametric flows (Gallo et al., 1989). Empirically, we show that this algorithm is very practical and scales to very large graphs, and its performance is competitive with widely used methods that have significantly weaker theoretical guarantees. 
    more » « less
  5. ; (, Journal of computational geometry)
    We present the first near-linear-time algorithm that computes a (1+ε)-approximation of the diameter of a weighted unit-disk graph of n vertices. Our algorithm requires O(n log^2 n) time for any constant ε>0, so we considerably improve upon the near-O(n^{3/2})-time algorithm of Gao and Zhang (2005). Using similar ideas we develop (1+ε)-approximate \emph{distance oracles} of O(1) query time with a likewise improvement in the preprocessing time, specifically from near O(n^{3/2}) to O(n log^3 n). We also obtain similar new results for a number of related problems in the weighted unit-disk graph metric such as the radius and the bichromatic closest pair. As a further application we employ our distance oracle, along with additional ideas, to solve the (1+ε)-approximate \emph{all-pairs bounded-leg shortest paths\/} (apBLSP) problem for a set of n planar points. Our data structure requires O(n^2 log n) space, O(loglog n) query time, and nearly O(n^{2.579}) preprocessing time for any constant ε>0, and is the first that breaks the near-cubic preprocessing time bound given by Roditty and Segal (2011). 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Text Encoded Conversion
  • XML
  • Save / Share this Record
  • Send to Email