Abstract Given a node-attributed graph, how can we efficiently represent it with few numerical features that expressively reflect its topology and attribute information? We propose A-DOGE, for attributed DOS-based graph embedding, based on density of states (DOS, a.k.a. spectral density) to tackle this problem. A-DOGE is designed to fulfill a long desiderata of desirable characteristics. Most notably, it capitalizes on efficient approximation algorithms for DOS, that we extend to blend in node labels and attributes for the first time, making it fast and scalable for large attributed graphs and graph databases. Being based on the entire eigenspectrum of a graph, A-DOGE can capture structural and attribute properties at multiple (“glocal”) scales. Moreover, it is unsupervised (i.e., agnostic to any specific objective) and lends itself to various interpretations, which makes it suitable for exploratory graph mining tasks. Finally, it processes each graph independent of others, making it amenable for streaming settings as well as parallelization. Through extensive experiments, we show the efficacy and efficiency of A-DOGE on exploratory graph analysis and graph classification tasks, where it significantly outperforms unsupervised baselines and achieves competitive performance with modern supervised GNNs, while achieving the best trade-off between accuracy and runtime.

We develop a framework for graph sparsification and sketching, based on a new tool, short cycle decomposition, which is a decomposition of an unweighted graph into an edge-disjoint collection of short cycles, plus a small number of extra edges. A simple observation shows 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. Both the existential and algorithmic variants of this decomposition enable us to make the following progress on several open problems in randomized graph algorithms: (1) We present an algorithm that runs in time $m^{1+o(1)}\varepsilon^{-1.5}$ and returns $(1\pm\varepsilon)$-approximations to effective resistances of all edges, improving over the previous best runtime of $\widetilde{{O}}(\min\{m\varepsilon^{-2}, n^{2} \varepsilon^{-1}\})$. This routine in turn gives an algorithm for approximating the determinant of a graph Laplacian up to a factor of $(1\pm \varepsilon)$ in $m^{1 + o(1)} + n^{\nicefrac{15}{8}+o(1)}\varepsilon^{-\nicefrac{7}{4}}$ time. (2) We show the existence of graphical spectral sketches with about $n\varepsilon^{-1}$ edges, and also give efficient algorithms to construct them. A graphical spectral sketch is a distribution over sparse graphs $H$ such that for a fixed vector ${\mathit{x}}$, we have ${{x}}^{\top} {L}_H {{x}} = (1\pm\varepsilon) {{x}}^{\top} {L}_G {{x}}$ and ${{x}}^{\top} {L}^{+}_H {{x}} = (1\pm\varepsilon) {{x}}^{\top} {L}^{+}_G {{x}}$ with high probability, where ${L}$ is the graph Laplacian and ${L}^{+}$ is its pseudoinverse. This implies the existence of resistance sparsifiers with about $n \varepsilon^{-1}$ edges that preserve the effective resistance between every pair of vertices up to $(1\pm\varepsilon)$. (3) 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 Eulerian directed graphs. The latter is critical to recent breakthroughs on faster algorithms for solving linear systems in directed Laplacians. The running time and output qualities of our spectral sketch and degree-preserving (directed) sparsification algorithms are limited by the efficiency of our routines for constructing short cycle decompositions. Improved algorithms for short cycle decompositions will lead to improvement in each of these algorithms.

Given a node-attributed graph, how can we efficiently represent it with few numerical features that expressively reflect its topology and attribute information? We propose A-DOGE, for Attributed DOS-based Graph Embedding, based on density of states (DOS, a.k.a. spectral density) to tackle this problem. A-DOGE is designed to fulfill a long desiderata of desirable characteristics. Most notably, it capitalizes on efficient approximation algorithms for DOS, that we extend to blend in node labels and attributes for the first time, making it fast and scalable for large attributed graphs and graph databases. Being based on the entire eigenspectrum of a graph, A-DOGE can capture structural and attribute properties at multiple (“glocal”) scales. Moreover, it is unsupervised (i.e. agnostic to any specific objective) and lends itself to various interpretations, which makes it is suitable for exploratory graph mining tasks. Finally, it processes each graph independent of others, making it amenable for streaming settings as well as parallelization. Through extensive experiments, we show the efficacy and efficiency of A-DOGE on exploratory graph analysis and graph classification tasks, where it significantly outperforms unsupervised baselines and achieves competitive performance with modern supervised GNNs, while achieving the best trade-off between accuracy and runtime.

Entity resolution (ER) refers to the problem of matching records in one or more relations that refer to the same real-world entity. While supervised machine learning (ML) approaches achieve the state-of-the-art results, they require a large amount of labeled examples that are expensive to obtain and often times infeasible. We investigate an important problem that vexes practitioners: is it possible to design an effective algorithm for ER that requires Zero labeled examples, yet can achieve performance comparable to supervised approaches? In this paper, we answer in the affirmative through our proposed approach dubbed ZeroER. Our approach is based on a simple observation --- the similarity vectors for matches should look different from that of unmatches. Operationalizing this insight requires a number of technical innovations. First, we propose a simple yet powerful generative model based on Gaussian Mixture Models for learning the match and unmatch distributions. Second, we propose an adaptive regularization technique customized for ER that ameliorates the issue of feature overfitting. Finally, we incorporate the transitivity property into the generative model in a novel way resulting in improved accuracy. On five benchmark ER datasets, we show that ZeroER greatly outperforms existing unsupervised approaches and achieves comparable performance to supervised approaches.

In this paper we study the problem of dynamically maintaining graph properties under batches of edge insertions and deletions in the massively parallel model of computation. In this setting, the graph is stored on a number of machines, each having space strongly sublinear with respect to the number of vertices, that is, nϵ for some constant 0 < ϵ < 1. Our goal is to handle batches of updates and queries where the data for each batch fits onto one machine in constant rounds of parallel computation, as well as to reduce the total communication between the machines. This objective corresponds to the gradual buildup of databases over time, while the goal of obtaining constant rounds of communication for problems in the static setting has been elusive for problems as simple as undirected graph connectivity. We give an algorithm for dynamic graph connectivity in this setting with constant communication rounds and communication cost almost linear in terms of the batch size. Our techniques combine a new graph contraction technique, an independent random sample extractor from correlated samples, as well as distributed data structures supporting parallel updates and queries in batches. We also illustrate the power of dynamic algorithms in the MPC model by showing that the batched version of the adaptive connectivity problem is P-complete in the centralized setting, but sub-linear sized batches can be handled in a constant number of rounds. Due to the wide applicability of our approaches, we believe it represents a practically-motivated workaround to the current difficulties in designing more efficient massively parallel static graph algorithms.

We give the first fully dynamic algorithm which maintains a (1−є)-approximate densest subgraph in worst-case time poly(logn, є−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 (1/4 − є) 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.

The problem of finding dense components of a graph is a major primitive in graph mining and data analysis. The densest subgraph problem (DSP) that asks to find a subgraph with maximum average degree forms a basic primitive in dense subgraph discovery with applications ranging from community detection to unsupervised discovery of biological network modules [16]. The DSP is exactly solvable in polynomial time using maximum flows [14, 17, 22]. Due to the high computational cost of maximum flows, Charikar’s greedy approximation algorithm is usually preferred in practice due to its linear time and linear space complexity [3, 8]. It constitutes a key algorithmic idea in scalable solutions for large-scale dynamic graphs [5, 7]. However, its output density can be a factor 2 off the optimal solution.

In this paper, we give a faster width-dependent algorithm for mixed packing-covering LPs. Mixed packing-covering LPs are fundamental to combinatorial optimization in computer science and operations research. Our algorithm finds a $1+\eps$ approximate solution in time $O(Nw/ \varepsilon)$, where $N$ is number of nonzero entries in the constraint matrix, and $w$ is the maximum number of nonzeros in any constraint. This algorithm is faster than Nesterov's smoothing algorithm which requires $O(N\sqrt{n}w/ \eps)$ time, where $n$ is the dimension of the problem. Our work utilizes the framework of area convexity introduced in [Sherman-FOCS'17] to obtain the best dependence on $\varepsilon$ while breaking the infamous $\ell_{\infty}$ barrier to eliminate the factor of $\sqrt{n}$. The current best width-independent algorithm for this problem runs in time $O(N/\eps^2)$ [Young-arXiv-14] and hence has worse running time dependence on $\varepsilon$. Many real life instances of mixed packing-covering problems exhibit small width and for such cases, our algorithm can report higher precision results when compared to width-independent algorithms. As a special case of our result, we report a $1+\varepsilon$ approximation algorithm for the densest subgraph problem which runs in time $O(md/ \varepsilon)$, where $m$ is the number of edges in the graph and $d$ is the maximum graph degree.

We present preconditioned stochastic gradient descent (SGD) algorithms for the $\ell_1$ minimization problem $\min_{\boldsymbol{\mathit{x}}}\|\boldsymbol{\mathit{A}} \boldsymbol{\mathit{x}} - \boldsymbol{\mathit{b}}\|_1$ in the overdetermined case, where there are far more constraints than variables. Specifically, we have $\boldsymbol{\mathit{A}} \in \mathbb{R}^{n \times d}$ for $n \gg d$. Commonly known as the Least Absolute Deviations problem, $\ell_1$ regression can be used to solve many important combinatorial problems, such as minimum cut and shortest path. SGD-based algorithms are appealing for their simplicity and practical efficiency. Our primary insight is that careful preprocessing can yield preconditioned matrices $\tilde{\boldsymbol{\mathit{A}}}$ with strong properties (besides good condition number and low-dimension) that allow for faster convergence of gradient descent. In particular, we precondition using Lewis weights to obtain an isotropic matrix with fewer rows and strong upper bounds on all row norms. We leverage these conditions to find a good initialization, which we use along with recent smoothing reductions and accelerated stochastic gradient descent algorithms to achieve $\epsilon$ relative error in $\widetilde{O}(nnz(\boldsymbol{\mathit{A}}) + d^{2.5} \epsilon^{-2})$ time with high probability, where $nnz(\boldsymbol{\mathit{A}})$ is the number of non-zeros in $\boldsymbol{\mathit{A}}$. This improves over the previous best result using gradient descent for $\ell_1$ regression. We also match the best known running times for interior point methods in several settings. Finally, we also show that if our original matrix $\boldsymbol{\mathit{A}}$ is approximately isotropic and the row norms are approximately equal, we can give an algorithm that avoids using fast matrix multiplication and obtains a running time of $\widetilde{O}(nnz(\boldsymbol{\mathit{A}}) + s d^{1.5}\epsilon^{-2} + d^2\epsilon^{-2})$, where $s$ is the maximum number of non-zeros in a row of $\boldsymbol{\mathit{A}}$. In this setting, we beat the best interior point methods for certain parameter regimes.

We develop a framework for graph sparsification based on a new tool, short cycle decomposition for graphs - a decomposition of a graph into a collection of short cycles, plus a small number of 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 m1+o(1)time algorithm for constructing a short cycle decomposition of the graph, with cycles of length no(1), and n1+o(1)extra edges. Both the existential and algorithmic variants of this decomposition enable us to make progress on several open problems in randomized graph algorithms. 1. We present an algorithm that runs in time m1+o(1)ε-1.5and returns (1 ± ε)-approximations to effective resistances of all edges, improving over the previous best of Õ(min{mε-2, n2ε-1}) This gives an algorithm to approximate the determinant of a graph Laplacian up to a factor of (1 ± ε) in roughly m + n15/8ε-7/4. 2. We show existence and efficient algorithms for constructing graphical spectral sketches - a distribution over sparse graphs H with about nε-1edges such that for a fixed vector x, we have xTLHx = (1 ± eps) xTLGx and xTL+Hx = (1 ± ε) xTL+Gx with high probability, where L is the graph Laplacian and L+ is its pseudoinverse. This implies resistance-sparsifiers with about nε edges that preserve the effective resistances between every pair of vertices up to (1 + eps). 3. By combining short cycle decomposition with importance sampling, 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 directed random walks and linear systems in directed Laplacian. The running time and output qualities of our spectral sketch and degree-preserving (directed) sparsification algorithms are limited by the efficiency of our routines for producing short cycle decompositions. Improved algorithms for short cycle decompositions will lead to improvements for each of these algorithms.

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 polylogarithmic 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 interleaved queries and updates to this randomized data structure may be of independent interest.

We give faster algorithms for producing sparse approximations of the transition matrices of k-step random walks on undirected and weighted graphs. These transition matrices also form graphs, and arise as intermediate objects in a variety of graph algorithms. Our improvements are based on a better understanding of processes that sample such walks, as well as tighter bounds on key weights underlying these sampling processes. On a graph with n vertices and m edges, our algorithm produces a graph with about nlog(n) edges that approximates the k-step random walk graph in about m + k^2 nlog^4(n) time. In order to obtain this runtime bound, we also revisit "density independent" algorithms for sparsifying graphs whose runtime overhead is expressed only in terms of the number of vertices.

For a graph G(V,E) and a vertex s in V, a weighting scheme (w : E -> N) is called a min-unique (resp. max-unique) weighting scheme, if for any vertex v of the graph G, there is a unique path of minimum (resp. maximum) weight from s to v. Instead, if the number of paths of minimum (resp. maximum) weight is bounded by n^c for some constant c, then the weighting scheme is called a min-poly (resp. max-poly) weighting scheme. In this paper, we propose an unambiguous non-deterministic log-space (UL) algorithm for the problem of testing reachability in layered directed acyclic graphs (DAGs) augmented with a min-poly weighting scheme. This improves the result due to Reinhardt and Allender [Reinhardt/Allender, SIAM J. Comp., 2000] where a UL algorithm was given for the case when the weighting scheme is min-unique. Our main technique is a triple inductive counting, which generalizes the techniques of [Immermann, Siam J. Comp.,1988; Szelepcsényi, Acta Inf.,1988] and [Reinhardt/Allender, SIAM J. Comp., 2000], combined with a hashing technique due to [Fredman et al.,J. ACM, 1984] (also used in [Garvin et al., Comp. Compl.,2014]). We combine this with a complementary unambiguous verification method, to give the desired UL algorithm. At the other end of the spectrum, we propose a UL algorithm for testing reachability in layered DAGs augmented with max-poly weighting schemes. To achieve this, we first reduce reachability in DAGs to the longest path problem for DAGs with a unique source, such that the reduction also preserves the max-poly property of the graph. Using our techniques, we generalize the double inductive counting method in [Limaye et al., CATS, 2009] where UL algorithms were given for the longest path problem on DAGs with a unique sink and augmented with a max-unique weighting scheme. An important consequence of our results is that, to show NL = UL, it suffices to design log-space computable min-poly (or max-poly) weighting schemes for DAGs.