We present a parallel algorithm for the (1 — ɛ) -approximate maximum flow problem in capacitated, undirected graphs with n vertices and m edges, achieving O(ɛ-3 polylog n) depth and O(mɛ-3 polylog n) work in the PRAM model. Although near-linear time sequential algorithms for this problem have been known for almost a decade, no parallel algorithms that simultaneously achieved polylogarithmic depth and near-linear work were known.

We consider the following basic, and very broad, statistical problem: Given a known high-dimensional distribution D over ℝn and a collection of data points in ℝn, distinguish between the two possibilities that (i) the data was drawn from D, versus (ii) the data was drawn from D|S, i.e. from D subject to truncation by an unknown truncation set S ⊆ ℝn. We study this problem in the setting where D is a high-dimensional i.i.d. product distribution and S is an unknown degree-d polynomial threshold function (one of the most well-studied types of Boolean-valued function over ℝn). Our main results are an efficient algorithm when D is a hypercontractive distribution, and a matching lower bound: 1. For any constant d, we give a polynomial-time algorithm which successfully distinguishes D from D|S using O(nd/2) samples (subject to mild technical conditions on D and S); 2. Even for the simplest case of D being the uniform distribution over {±1}n, we show that for any constant d, any distinguishing algorithm for degree-d polynomial threshold functions must use Ω(nd/2) samples.

We present a new approach for finding matchings in dense graphs by building on Szemerédi’s celebrated Regularity Lemma. This allows us to obtain non-trivial albeit slight improvements over longstanding bounds for matchings in streaming and dynamic graphs. In particular, we establish the following results for n-vertex graphs:

A seminal work of [Ahn-Guha-McGregor, PODS’12] showed that one can compute a cut sparsifier of an unweighted undirected graph by taking a near-linear number of linear measurements on the graph. Subsequent works also studied computing other graph sparsifiers using linear sketching, and obtained near-linear upper bounds for spectral sparsifiers [Kapralov-Lee-Musco-Musco-Sidford, FOCS’14] and first non-trivial upper bounds for spanners [Filtser-Kapralov-Nouri, SODA’21]. All these linear sketching algorithms, however, only work on unweighted graphs, and are extended to weighted graphs by weight grouping, a non-linear operation not implementable in, for instance, general turnstile streams.In this paper, we initiate the study of weighted graph sparsification by linear sketching by investigating a natural class of linear sketches that we call incidence sketches, in which each measurement is a linear combination of the weights of edges incident on a single vertex. This class captures all aforementioned linear sketches for unweighted sparsification. It also covers linear sketches implementable in the simultaneous communication model, where edges are distributed across n machines. Our results are:1)Weighted cut sparsification: We give an algorithm that computes a $(1+\epsilon)$-cut sparsifier using $\tilde{O}(n\epsilon^{-3})$ linear measurements, which is nearly optimal. This also implies a turnstile streaming algorithm with $\tilde{O}(n\epsilon^{-3})$ space. Our algorithm is achieved by building a so-called “weighted edge sampler” for each vertex.2)Weighted spectral sparsification: We give an algorithm that computes a $(1+\epsilon)$-spectral sparsifier using $\tilde{O}(n^{6/5}\epsilon^{-4})$ linear measurements. This also implies a turnstile streaming algorithm with $\tilde{O}(n^{6/5}\epsilon^{-4})$ space. Key to our algorithm is a novel analysis of how the effective resistances change under vertex sampling. Complementing our algorithm, we then prove a superlinear lower bound of $\Omega(n^{21/20-o(1)})$ measurements for computing some O(1)-spectral sparsifier using incidence sketches.3)Weighted spanner computation: We first show that any $o(n^{2})$ linear measurements can only recover a spanner of stretch that in general depends linearly on $\frac{w_{\max}}{w_{\min}}$. We thus focus on graphs with $\frac{w_{\max}}{w_{\min}}=O(1)$ and study the stretch’s dependence on n. On such graphs, the algorithm in [FiltserKapralov-Nouri, SODA’21] can obtain a spanner of stretch $\tilde{O}\left(n^{\frac{2}{3}\left(1-\alpha\right)}\right)$ using $\tilde{O}(n^{1+\alpha})$ measurements for any $\alpha\in [0,1]$. We prove that, for incidence sketches, this tradeoff is optimal up to an $n^{o(1)}$ factor for all $\alpha\lt 1/10$.We prove both our lower bounds by analyzing the “effective resistances” in certain matrix-weighted graphs, where we develop a number of new tools for reasoning about such graphs – most notably (i) a matrix-weighted analog of the widely used expander decomposition of ordinary graphs, and (ii) a proof that a random vertex-induced subgraph of a matrix-weighted expander is also an expander. We believe these tools are of independent interest.

Hierarchical clustering over graphs is a fundamental task in data mining and machine learning with applications in many domains including phylogenetics, social network analysis, and information retrieval. Specifically, we consider the recently popularized objective function for hierarchical clustering due to Dasgupta~\cite{Dasgupta16}, namely, minimum cost hierarchical partitioning. Previous algorithms for (approximately) minimizing this objective function require linear time/space complexity. In many applications the underlying graph can be massive in size making it computationally challenging to process the graph even using a linear time/space algorithm. As a result, there is a strong interest in designing algorithms that can perform global computation using only sublinear resources (space, time, and communication). The focus of this work is to study hierarchical clustering for massive graphs under three well-studied models of sublinear computation which focus on space, time, and communication, respectively, as the primary resources to optimize: (1) (dynamic) streaming model where edges are presented as a stream, (2) query model where the graph is queried using neighbor and degree queries, (3) massively parallel computation (MPC) model where the edges of the graph are partitioned over several machines connected via a communication channel.We design sublinear algorithms for hierarchical clustering in all three models above. At the heart of our algorithmic results is a view of the objective in terms of cuts in the graph, which allows us to use a relaxed notion of cut sparsifiers to do hierarchical clustering while introducing only a small distortion in the objective function. Our main algorithmic contributions are then to show how cut sparsifiers of the desired form can be efficiently constructed in the query model and the MPC model. We complement our algorithmic results by establishing nearly matching lower bounds that rule out the possibility of designing algorithms with better performance guarantees in each of these models.

We study the problem of minimizing a convex function given by a zeroth order oracle that is possibly corrupted by {\em outlier noise}. Specifically, we assume the function values at some points of the domain are corrupted arbitrarily by an adversary, with the only restriction being that the total volume of corrupted points is bounded. The goal then is to find a point close to the function's minimizer using access to the corrupted oracle.We first prove a lower bound result showing that, somewhat surprisingly, one cannot hope to approximate the minimizer {\em nearly as well} as one might expect, even if one is allowed {\em an unbounded number} of queries to the oracle. Complementing this negative result, we then develop an efficient algorithm that outputs a point close to the minimizer of the convex function, where the specific distance matches {\em exactly}, up to constant factors, the distance bound shown in our lower bound result.

Graph clustering is a basic technique in machine learning, and has widespread applications in different domains. While spectral techniques have been successfully applied for clustering undirected graphs, the performance of spectral clustering algorithms for directed graphs (digraphs) is not in general satisfactory: these algorithms usually require symmetrising the matrix representing a digraph, and typical objective functions for undirected graph clustering do not capture cluster-structures in which the information given by the direction of the edges is crucial. To overcome these downsides, we propose a spectral clustering algorithm based on a complex-valued matrix representation of digraphs. We analyse its theoretical performance on a Stochastic Block Model for digraphs in which the cluster-structure is given not only by variations in edge densities, but also by the direction of the edges. The significance of our work is highlighted on a data set pertaining to internal migration in the United States: while previous spectral clustering algorithms for digraphs can only reveal that people are more likely to move between counties that are geographically close, our approach is able to cluster together counties with a similar socio-economical profile even when they are geographically distant, and illustrates how people tend to move from rural to more urbanised areas.

We give the first polynomial-time approximation scheme (PTAS) for the stochastic load balancing problem when the job sizes follow Poisson distributions. This improves upon the 2-approximation algorithm due to Goel and Indyk (FOCS'99). Moreover, our approximation scheme is an efficient PTAS that has a running time double exponential in $1/ε$ but nearly-linear in $n$, where $n$ is the number of jobs and $ε$ is the target error. Previously, a PTAS (not efficient) was only known for jobs that obey exponential distributions (Goel and Indyk, FOCS'99). Our algorithm relies on several probabilistic ingredients including some (seemingly) new results on scaling and the so-called "focusing effect" of maximum of Poisson random variables which might be of independent interest.

We study the problem of maximizing the number of spanning trees in a connected graph with n vertices and m edges, by adding at most k edges from a given set of q candidate edges, a problem that has applications in many domains. We give both algorithmic and hardness results for this problem: 1) We give a greedy algorithm that obtains an approximation ratio of (1 - 1/e - ∈) in the exponent of the number of spanning trees for any ∈ > 0 in time Õ(m∈-1+ (n + q)∈-3), where Õ(·) hides poly log(n) factors. Our running time is optimal with respect to the input size, up to logarithmic factors, and improves on the O(n3) running time of the previous proposed greedy algorithm with an approximation ratio (1 - 1/e) in the exponent. Notably, the independence of our running time of k is novel, compared to conventional top-k selections on graphs that usually run in Ω(mk) time. 2) We show the exponential inapproximability of this problem by proving that there exists a constant c > 0 such that it is NP-hard to approximate the optimum number of spanning trees in the exponent within (1 - c).

The problem of selecting a group of vertices under certain constraints that maximize their joint centrality arises in many practical scenarios. In this paper, we extend the notion of current flow closeness centrality (CFCC) to a set of vertices in a graph, and investigate the problem of selecting a subset S to maximizes its CFCC C(S), with the cardinality constraint |S| = k. We show the NP-hardness of the problem, but propose two greedy algorithms to minimize the reciprocal of C(S). We prove the approximation ratios by showing the monotonicity and supermodularity. A proposed deterministic greedy algorithm has an approximation factor and cubic running time. To compare with, a proposed randomized algorithm gives -approximation in nearly-linear time, for any ? > 0. Extensive experiments on model and real networks demonstrate the effectiveness and efficiency of the proposed algorithms, with the randomized algorithm being applied to massive networks with more than a million vertices.

The hierarchical graphs and Sierpiński graphs are constructed iteratively, which have the same number of vertices and edges at any iteration, but exhibit quite different structural properties: the hierarchical graphs are nonfractal and small-world, while the Sierpiński graphs are fractal and "large-world." Both graphs have found broad applications. In this paper, we study consensus problems in hierarchical graphs and Sierpiński graphs, focusing on three important quantities of consensus problems, that is, convergence speed, delay robustness, and coherence for first-order (and second-order) dynamics, which are, respectively, determined by algebraic connectivity, maximum eigenvalue, and sum of reciprocal (and square of reciprocal) of each nonzero eigenvalue of Laplacian matrix. For both graphs, based on the explicit recursive relation of eigenvalues at two successive iterations, we evaluate the second smallest eigenvalue, as well as the largest eigenvalue, and obtain the closed-form solutions to the sum of reciprocals (and square of reciprocals) of all nonzero eigenvalues. We also compare our obtained results for consensus problems on both graphs and show that they differ in all quantities concerned, which is due to the marked difference of their topological structures.

We introduce a new approach to spectral sparsification that approximates the quadratic form of the pseudoinverse of a graph Laplacian restricted to a subspace. We show that sparsifiers with a near-linear number of edges in the dimension of the subspace exist. Our setting generalizes that of Schur complement sparsifiers. Our approach produces sparsifiers by sampling a uniformly random spanning tree of the input graph and using that tree to guide an edge elimination procedure that contracts, deletes, and reweights edges. In the context of Schur complement sparsifiers, our approach has two benefits over prior work. First, it produces a sparsifier in almost-linear time with no runtime dependence on the desired error. We directly exploit this to compute approximate effective resistances for a small set of vertex pairs in faster time than prior work (Durfee-Kyng-Peebles-Rao-Sachdeva '17). Secondly, it yields sparsifiers that are reweighted minors of the input graph. As a result, we give a near-optimal answer to a variant of the Steiner point removal problem. A key ingredient of our algorithm is a subroutine of independent interest: a near-linear time algorithm that, given a chosen set of vertices, builds a data structure from which we can query a multiplicative approximation to the decrease in the effective resistance between two vertices after identifying all vertices in the chosen set to a single vertex with inverse polynomial additional additive error in near-constant time.

The Kirchhoff index, defined as the sum of effective resistances over pairs all of nodes, is of primary significance in diverse contexts of complex networks. In this paper, we propose to use the rate at which the Kirchhoff index changes with respect to the change of resistance of an edge as a measure of importance for this edge in weighted networks. For an arbitrary edge, we explicitly determine the change of the Kirchhoff index and express it in terms of the biharmonic distance between its end nodes, and thus call this centrality as biharmonic distance related centrality (BDRC). We show that BDRC has a better discriminating power than those commonly used metrics, such as edge betweenness and spanning edge centrality. We give an efficient algorithm that provides an approximation of biharmonic distance for all edges in nearly linear time of the number of edges, with a high probability. Experiment results validate the efficiency and accuracy of the presented algorithm.

Estimating the relative importance of vertices and edges is a fundamental issue in the analysis of complex networks, and has found vast applications in various aspects, such as social networks, power grids, and biological networks. Most previous work focuses on metrics of vertex importance and methods for identifying powerful vertices, while related work for edges is much lesser, especially for weighted networks, due to the computational challenge. In this paper, we propose to use the well-known Kirchhoff index as the measure of edge centrality in weighted networks, called θ-Kirchhoff edge centrality. The Kirchhoff index of a network is defined as the sum of effective resistances over all vertex pairs. The centrality of an edge e is reflected in the increase of Kirchhoff index of the network when the edge e is partially deactivated, characterized by a parameter θ. We define two equivalent measures for θ-Kirchhoff edge centrality. Both are global metrics and have a better discriminating power than commonly used measures, based on local or partial structural information of networks, e.g. edge betweenness and spanning edge centrality. Despite the strong advantages of Kirchhoff index as a centrality measure and its wide applications, computing the exact value of Kirchhoff edge centrality for each edge in a graph is computationally demanding. To solve this problem, for each of the θ-Kirchhoff edge centrality metrics, we present an efficient algorithm to compute its ∊-approximation for all the m edges in nearly linear time in m. The proposed θ-Kirchhoff edge centrality is the first global metric of edge importance that can be provably approximated in nearly-linear time. Moreover, according to the θ-Kirchhoff edge centrality, we present a θ-Kirchhoff vertex centrality measure, as well as a fast algorithm that can compute e-approximate Kirchhoff vertex centrality for all the n vertices in nearly linear time in m.

Various graph products and operations have been widely used to construct complex networks with common properties of real-life systems. However, current works mainly focus on designing models of binary networks, in spite of the fact that many real networks can be better mimicked by heterogeneous weighted networks. In this paper, we develop a corona product of two weighted graphs, based on which and an observed updating mechanism of edge weight in real networks, we propose a minimal generative model for inhomogeneous weighted networks. We derive analytically relevant properties of the weighted network model, including strength, weight and degree distributions, clustering coefficient, degree correlations and diameter. These properties are in good agreement with those observed in diverse real-world weighted networks. We then determine all the eigenvalues and their corresponding multiplicities of the transition probability matrix for random walks on the weighted networks. Finally, we apply the obtained spectra to derive explicit expressions for mean hitting time of random walks and weighted counting of spanning trees on the weighted networks. Our model is an exactly solvable one, allowing us to analytically treat its structural and dynamical properties, which is thus a good test-bed and an ideal substrate network for studying different dynamical processes, in order to explore the impacts of heterogeneous weight distribution on these processes.