Search

We propose a simple and computationally efficient method for dense subgraph discovery, which is a classic problem both in theory and in practice. It is well known that dense subgraphs can have strong correlation with structures of interest in real-world networks across various domains ranging from social networks to biological systems [Gionis and Tsourakakis `15]. For the densest subgraph problem, Charikar's greedy algorithm [Asashiro `00, Charikar `00] is very simple, and can typically find result of quality much better than the provable factor 2-approximation, which makes it very popular in practice. However, it is also known to give suboptimal output in many real-world examples. On the other hand, finding the exact optimal solution requires the computation of maximum flow. Despite the existence of highly optimized maximum flow solvers, such computation still incurs prohibitive computational costs for the massive graphs arising in modern data science applications. We devise an iterative algorithm which naturally generalizes the greedy algorithm of Charikar. Our algorithm draws insights from the iterative approaches from convex optimization, and also exploits the dual interpretation of the densest subgraph problem. We have empirical evidence that our algorithm is much more robust against the structural heterogeneities in real-world datasets, and converges to the optimal subgraph density even when the simple greedy algorithm fails. On the other hand, in instances where Charikar's algorithm performs well, our algorithm is able to quickly verify its optimality. Furthermore, we demonstrate that our method is significantly faster than the maximum flow based exact optimal algorithm. We conduct experiments on datasets from broad domains, and our algorithm achieves $\sim$145$\times$ speedup on average to find subgraphs whose density is at least 90\% of the optimal value., Comment: fixed incorrect email ID in V2

We give the first fully dynamic algorithm which maintains a $(1-\epsilon)$-approximate densest subgraph in worst-case time $\text{poly}(\log n, \epsilon^{-1})$ per update. Dense subgraph discovery is an important primitive for many real-world applications such as community detection, link spam detection, distance query indexing, and computational biology. We approach the densest subgraph problem by framing its dual as a graph orientation problem, which we solve using an augmenting path-like adjustment technique. Our result improves upon the previous best approximation factor of $\left(\frac{1}{4} - \epsilon\right)$ for fully dynamic densest subgraph [Bhattacharya et. al., STOC `15]. We also extend our techniques to solving the problem on vertex-weighted graphs with similar runtimes. Additionally, we reduce the $(1-\epsilon)$-approximate densest subgraph problem on directed graphs to $O(\log n/\epsilon)$ instances of $(1-\epsilon)$-approximate densest subgraph on vertex-weighted graphs. This reduction, together with our algorithm for vertex-weighted graphs, gives the first fully-dynamic algorithm for directed densest subgraph in worst-case time $\text{poly}(\log n, \epsilon^{-1})$ per update. Moreover, combined with a near-linear time algorithm for densest subgraph [Bahmani et. al., WAW `14], this gives the first near-linear time algorithm for directed densest subgraph., Comment: Updated version. Accepted at STOC '20

We develop a framework for graph sparsification and sketching, based on a new tool, short cycle decomposition -- a decomposition of an unweighted graph into an edge-disjoint collection of short cycles, plus few extra edges. A simple observation gives that every graph G on n vertices with m edges can be decomposed in $O(mn)$ time into cycles of length at most $2\log n$, and at most $2n$ extra edges. We give an $m^{1+o(1)}$ time algorithm for constructing a short cycle decomposition, with cycles of length $n^{o(1)}$, and $n^{1+o(1)}$ extra edges. These decompositions enable us to make progress on several open questions: * We give an algorithm to find $(1\pm\epsilon)$-approximations to effective resistances of all edges in time $m^{1+o(1)}\epsilon^{-1.5}$, improving over the previous best of $\tilde{O}(\min\{m\epsilon^{-2},n^2 \epsilon^{-1}\})$. This gives an algorithm to approximate the determinant of a Laplacian up to $(1\pm\epsilon)$ in $m^{1 + o(1)} + n^{15/8+o(1)}\epsilon^{-7/4}$ time. * We show existence and efficient algorithms for constructing graphical spectral sketches -- a distribution over sparse graphs H such that for a fixed vector $x$, we have w.h.p. $x'L_Hx=(1\pm\epsilon)x'L_Gx$ and $x'L_H^+x=(1\pm\epsilon)x'L_G^+x$. This implies the existence of resistance-sparsifiers with about $n\epsilon^{-1}$ edges that preserve the effective resistances between every pair of vertices up to $(1\pm\epsilon).$ * By combining short cycle decompositions with known tools in graph sparsification, we show the existence of nearly-linear sized degree-preserving spectral sparsifiers, as well as significantly sparser approximations of directed graphs. The latter is critical to recent breakthroughs on faster algorithms for solving linear systems in directed Laplacians. Improved algorithms for constructing short cycle decompositions will lead to improvements for each of the above results., Comment: 80 pages

Motivated by the study of matrix elimination orderings in combinatorial scientific computing, we utilize graph sketching and local sampling to give a data structure that provides access to approximate fill degrees of a matrix undergoing elimination in $O(\text{polylog}(n))$ time per elimination and query. We then study the problem of using this data structure in the minimum degree algorithm, which is a widely-used heuristic for producing elimination orderings for sparse matrices by repeatedly eliminating the vertex with (approximate) minimum fill degree. This leads to a nearly-linear time algorithm for generating approximate greedy minimum degree orderings. Despite extensive studies of algorithms for elimination orderings in combinatorial scientific computing, our result is the first rigorous incorporation of randomized tools in this setting, as well as the first nearly-linear time algorithm for producing elimination orderings with provable approximation guarantees. While our sketching data structure readily works in the oblivious adversary model, by repeatedly querying and greedily updating itself, it enters the adaptive adversarial model where the underlying sketches become prone to failure due to dependency issues with their internal randomness. We show how to use an additional sampling procedure to circumvent this problem and to create an independent access sequence. Our technique for decorrelating the interleaved queries and updates to this randomized data structure may be of independent interest., Comment: 58 pages, 3 figures. This is a substantially revised version of arXiv:1711.08446 with an emphasis on the underlying theoretical problems

We study faster algorithms for producing the minimum degree ordering used to speed up Gaussian elimination. This ordering is based on viewing the non-zero elements of a symmetric positive definite matrix as edges of an undirected graph, and aims at reducing the additional non-zeros (fill) in the matrix by repeatedly removing the vertex of minimum degree. It is one of the most widely used primitives for pre-processing sparse matrices in scientific computing. Our result is in part motivated by the observation that sub-quadratic time algorithms for finding min-degree orderings are unlikely, assuming the strong exponential time hypothesis (SETH). This provides justification for the lack of provably efficient algorithms for generating such orderings, and leads us to study speedups via degree-restricted algorithms as well as approximations. Our two main results are: (1) an algorithm that produces a min-degree ordering whose maximum degree is bounded by $\Delta$ in $O(m \Delta \log^3{n})$ time, and (2) an algorithm that finds an $(1 + \epsilon)$-approximate marginal min-degree ordering in $O(m \log^{5}n \epsilon^{-2})$ time. Both of our algorithms rely on a host of randomization tools related to the $\ell_0$-estimator by [Cohen `97]. A key technical issue for the final nearly-linear time algorithm are the dependencies of the vertex removed on the randomness in the data structures. To address this, we provide a method for generating a pseudo-deterministic access sequence, which then allows the incorporation of data structures that only work under the oblivious adversary model., Comment: 57 pages