Sparse matrix multiplication (SpGEMM) is a fun-damental kernel used in many diverse application areas, both numerical and discrete. For example, many algebraic graph algorithms rely on SpGEMM in the tropical semiring to compute shortest paths in graphs. Recently, SpGEMM has received growing attention regarding implementations for specific (parallel) architectures. Yet, this concerns only the static problem, where both input matrices do not change. In many applications, however, matrices (or their corresponding graphs) change over time. Although recomputing from scratch is very expensive, we are not aware of any dynamic SpGEMM algorithms in the literature. In this paper, we thus propose a batch-dynamic algorithm for MPI-based parallel computing. Building on top of a distributed graph/matrix data structure that allows for fast updates, our dynamic SpGEMM reduces the communication volume signifi-cantly. It does so by exploiting that updates change far fewer matrix entries than there are non-zeros in the input operands. Our experiments with popular benchmark graphs show that our approach pays off. For batches of insertions or removals of matrix entries, our dynamic SpGEMM is substantially faster (sometimes by orders of magnitude) than the static algorithms in the state-of-the-art competitors CombBLAS, CTF and PETSc.

Analyzing large graphs in parallel has received considerable attention recently due to ever increasing data set sizes. Centrality measures indicate the importance of vertices (or edges) and belong to the most widely used analytic kernels. Harmonic centrality is a popular vertex centrality measure with many desirable properties. Since most of the applications of vertex centrality rely only on the ranking of vertices and not on their exact centrality scores, previous research has considered various algorithms that can quickly determine a ranking of the top-k vertices with highest harmonic centrality. Such algorithms are available for many types of real-world graphs, including dynamic graphs. Yet, no attempts have been made to efficiently parallelize these top-k algorithms (besides naive implementations based on a global lock). In this paper, we propose an MPI-distributed algorithm for (dynamic) top-k harmonic centrality. Our algorithm exploits an algebraic BFS technique and batching to parallelize the approximation of centrality scores of multiple vertices. Likewise, we use algebraic techniques to compute various bounds and heuristics that are necessary to obtain a fast top-k algorithm. Experiments demonstrate that our MPI-parallel algorithm outperforms existing implementations. Consequently, our new approach allows the computation of top-k harmonic centrality on graphs that are substantially larger.

General Sparse Matrix-Matrix Multiplication (SpGEMM) has attracted much attention from researchers in graph analyzing, scientific computing, and deep learning. Many optimization techniques have been developed for different applications and computing architectures over the past decades. The objective of this paper is to provide a structured and comprehensive overview of the researches on SpGEMM. Existing researches have been grouped into different categories based on target architectures and design choices. Covered topics include typical applications, compression formats, general formulations, key problems and techniques, architecture-oriented optimizations, and programming models. The rationales of different algorithms are analyzed and summarized. This survey sufficiently reveals the latest progress of SpGEMM research to 2021. Moreover, a thorough performance comparison of existing implementations is presented. Based on our findings, we highlight future research directions, which encourage better design and implementations in later studies.

Centrality measures characterize important nodes in networks. Efficiently computing such nodes has received a lot of attention. When considering the generalization of computing central groups of nodes, challenging optimization problems occur. In this work, we study two such problems, group-harmonic maximization and group-closeness maximization both from a theoretical and from an algorithm engineering perspective. On the theoretical side, we obtain the following results. For group-harmonic maximization, unless P = NP, there is no polynomial-time algorithm that achieves an approximation factor better than (directed) and (undirected), even for unweighted graphs. On the positive side, we show that a greedy algorithm achieves an approximation factor of (directed) and (undirected), where λ is the ratio of minimal and maximal edge weights. For group-closeness maximization, we obtain a strong separation between undirected and directed graphs (that holds even in the unweighted case). The undirected case is NP-hard to be approximated to within a factor better than and a constant approximation factor is achieved by a local-search algorithm. For the directed case, however, we show that, for any , the problem is NP-hard to be approximated within a factor of 4|V|−∊. From the algorithm engineering perspective, we provide efficient implementations of the above greedy and local search algorithms. In our extensive experimental study we show that, on instances small enough so that an optimum solution can be computed in reasonable time, the quality of both the greedy and the local search algorithms come very close to the optimum. On larger instances, our local search algorithms yield results with superior quality compared to existing greedy and local search solutions, at the cost of additional running time. We thus advocate local search for scenarios where solution quality is of highest concern.

Kernelization, i.e., the use of reduction rules to simplify a problem instance, is known to be highly successful for the VertexCover problem, both in theory and in practice. State-of-the-art solvers for VertexCover generally perform reductions, followed by a Branch-and-Bound algorithm on the kernelized instance. In fact, all top-3 solvers of the recent PACE 2019 challenge on VertexCover exploit this strategy. Branch-and-Reduce algorithms, i.e., extensions of Branch-and-Bound that perform reductions in each branch of the search tree, are known to solve some instances very well; however, they are not competitive with the best Branch-and-Bound solvers on kernelized instances. In this paper, we identify a critical bottleneck of Branch-and-Reduce algorithms, namely that on hard instances, many applications of reduction rules do not help to discard branches (even if the problem size is reduced considerably). Based on this observation, we design an algorithm that exploits a SAT solver to discard branches before significant amounts of ineffective reductions are applied. Our algorithm, which we term “SAT-and-Reduce”, generally runs a Branch-and-Reduce procedure. Before branching, we call into the SAT oracle that can either (i) find a vertex cover that improves upon the current best solution, (ii) discard the current branch to allow the algorithm to backtrack, (iii) yield an improved lower bound for the current branch, or (iv) force inclusion/exclusion of vertices into/from a minimal vertex cover. Branching continues when the SAT oracle hits a resource limit. Even during reductions, we maintain the state of the SAT oracle incrementally such that calls into the oracle have little overhead. Experiments on the PACE 2019 dataset demonstrate that (i) our strategy improves upon the best available solvers for VertexCover, and (ii) solves a strict superset of the instances that are solved by the best Branch-and-Reduce algorithm. We conjecture that our main observation about the effectiveness of Branch-and-Reduce extends beyond our VertexCover algorithm and can guide future implementations of Branch-and-Reduce in practice.

The emergence of massive graph data sets requires fast mining algorithms.Centrality measures to identify important vertices belong to the most popular analysis methods in graph mining.A measure that is gaining attention is forest closeness centrality; it is closely related to electrical measures using current flow but can also handle disconnected graphs.Recently, [Jin et al., ICDM'19] proposed an algorithm to approximate this measure probabilistically.Their algorithm processes small inputs quickly, but does not scale well beyond hundreds of thousands of vertices.In this paper, we first propose a different approximation algorithm; it is up to two orders of magnitude faster and more accurate in practice.Our method exploits the strong connection between uniform spanning trees and forest distances by adapting and extending recent approximation algorithms for related single-vertex problems.This results in a nearly-linear time algorithm with an absolute probabilistic error guarantee.In addition, we are the first to consider the problem of finding an optimal group of vertices w. r. t. forest closeness.We prove that this latter problem is NP-hard; to approximate it, we adapt a greedy algorithm by [Li et al., WWW'19], which is based on (partial) matrix inversion.Moreover, our experiments show that on disconnected graphs, group forest closeness outperforms existing centrality measures in the context of semi-supervised vertex classification.

The study of vertex centrality measures is a key aspect of network analysis. Naturally, such centrality measures have been generalized to groups of vertices; for popular measures it was shown that the problem of finding the most central group is -hard. As a result, approximation algorithms to maximize group centralities were introduced recently. Despite a nearly-linear running time, approximation algorithms for group betweenness and (to a lesser extent) group closeness are rather slow on large networks due to high constant overheads. That is why we introduce GED-Walk centrality, a new submodular group centrality measure inspired by Katz centrality. In contrast to closeness and betweenness, it considers walks of any length rather than shortest paths, with shorter walks having a higher contribution. We define algorithms that (i) efficiently approximate the GED-Walk score of a given group and (ii) efficiently approximate the (proved to be -hard) problem of finding a group with highest GED-Walk score. Experiments on several real-world datasets show that scores obtained by GED-Walk improve performance on common graph mining tasks such as collective classification and graph-level classification. An evaluation of empirical running times demonstrates that maximizing GED-Walk (in approximation) is two orders of magnitude faster compared to group betweenness approximation and for group sizes ≤ 100 one to two orders faster than group closeness approximation. For graphs with tens of millions of edges, approximate GED-Walk maximization typically needs less than one minute. Furthermore, our experiments suggest that the maximization algorithms scale linearly with the size of the input graph and the size of the group.

The ubiquity of massive graph data sets in numerous applications requires fast algorithms for extracting knowledge from these data. We are motivated here by three electrical measures for the analysis of large small-world graphs $G = (V, E)$ -- i.e., graphs with diameter in $O(\log |V|)$, which are abundant in complex network analysis. From a computational point of view, the three measures have in common that their crucial component is the diagonal of the graph Laplacian's pseudoinverse, $L^\dagger$. Computing diag$(L^\dagger)$ exactly by pseudoinversion, however, is as expensive as dense matrix multiplication -- and the standard tools in practice even require cubic time. Moreover, the pseudoinverse requires quadratic space -- hardly feasible for large graphs. Resorting to approximation by, e.g., using the Johnson-Lindenstrauss transform, requires the solution of $O(\log |V| / ε^2)$ Laplacian linear systems to guarantee a relative error, which is still very expensive for large inputs. In this paper, we present a novel approximation algorithm that requires the solution of only one Laplacian linear system. The remaining parts are purely combinatorial -- mainly sampling uniform spanning trees, which we relate to diag$(L^\dagger)$ via effective resistances. For small-world networks, our algorithm obtains a $\pm ε$-approximation with high probability, in a time that is nearly-linear in $|E|$ and quadratic in $1 / ε$. Another positive aspect of our algorithm is its parallel nature due to independent sampling. We thus provide two parallel implementations of our algorithm: one using OpenMP, one MPI + OpenMP. In our experiments against the state of the art, our algorithm (i) yields more accurate results, (ii) is much faster and more memory-efficient, and (iii) obtains good parallel speedups, in particular in the distributed setting.

Betweenness centrality is one of the most popular vertex centrality measures in network analysis. Hence, many (sequential and parallel) algorithms to compute or approximate betweenness have been devised. Recent algorithmic advances have made it possible to approximate betweenness very efficiently on shared-memory architectures. Yet, the best shared-memory algorithms can still take hours of running time for large graphs, especially for graphs with a high diameter or when a small relative error is required.In this work, we present an MPI-based generalization of the state-of-the-art shared-memory algorithm for betweenness approximation. This algorithm is based on adaptive sampling; our parallelization strategy can be applied in the same manner to adaptive sampling algorithms for other problems. In experiments on a 16-node cluster, our MPI-based implementation is by a factor of 16.1x faster than the state-of-the-art shared-memory implementation when considering our parallelization focus - the adaptive sampling phase - only. For the complete algorithm, we obtain an average (geom. mean) speedup factor of 7.4x over the state of the art. For some previously very challenging inputs, this speedup is much higher. As a result, our algorithm is the first to approximate betweenness centrality on graphs with several billion edges in less than ten minutes with high accuracy.

Partitioning graphs into blocks of roughly equal size such that few edges run between blocks is a frequently needed operation when processing graphs on a parallel computer. When a topology of a distributed system is known, an important task is then to map the blocks of the partition onto the processors such that the overall communication cost is reduced. We present novel multilevel algorithms that integrate graph partitioning and process mapping. Important ingredients of our algorithm include fast label propagation, more localized local search, initial partitioning, as well as a compressed data structure to compute processor distances without storing a distance matrix. Moreover, our algorithms are able to exploit a given hierarchical structure of the distributed system under consideration. Experiments indicate that our algorithms speed up the overall mapping process and, due to the integrated multilevel approach, also find much better solutions in practice. For example, one configuration of our algorithm yields similar solution quality as the previous state-of-the-art in terms of mapping quality for large numbers of partitions while being a factor 9.3 faster. Compared to the currently fastest iterated multilevel mapping algorithm Scotch, we obtain 16% better solutions while investing slightly more running time.

In network analysis and graph mining, closeness centrality is a popular measure to infer the importance of a vertex. Computing closeness efficiently for individual vertices received considerable attention. The NP-hard problem of group closeness maximization, in turn, is more challenging: the objective is to find a vertex group that is central as a whole and state-of the-art heuristics for it do not scale to very big graphs yet.In this paper, we present new local search heuristics for group closeness maximization. By using randomized approximation techniques and dynamic data structures, our algorithms are often able to perform locally optimal decisions efficiently. The final result is a group with high (but not optimal) closeness centrality. We compare our algorithms to the current state-of-the-art greedy heuristic both on weighted and on unweighted real-world graphs. For graphs with hundreds of millions of edges, our local search algorithms take only around ten minutes, while greedy requires more than ten hours. Overall, our new algorithms are between one and two orders of magnitude faster, depending on the desired group size and solution quality. For example, on weighted graphs and k =10, our algorithms yield solutions of 12.4% higher quality, while also being 793. 6× faster. For unweighted graphs and k =10, we achieve solutions within 99.4% of the state-of-the-art quality while being 127. 8× faster.

Network science methodology is increasingly applied to a large variety of real-world phenomena. Thus, network data sets with millions or billions of edges are more and more common. To process and analyze such graphs, we need appropriate graph processing systems and fast algorithms. Many analysis algorithms have been pioneered, however, on small networks when speed was not the highest concern. Developing an analysis toolkit for large-scale networks thus often requires faster variants, both from an algorithmic and an implementation perspective.In this paper we focus on computational aspects of vertex centrality measures. Such measures indicate the importance of a vertex based on the position of the vertex in the network. We describe several common measures as well as algorithms for computing them. The description has two foci: (i) our recent contributions to the field and (ii) possible future work, particularly regarding lower-level implementation.

Network analysis defines a number of centrality measures to identify the most central nodes in a network. Fast computation of those measures is a major challenge in algorithmic network analysis. Aside from closeness and betweenness, Katz centrality is one of the established centrality measures. In this paper, we consider the problem of computing rankings for Katz centrality. In particular, we propose upper and lower bounds on the Katz score of a given node. While previous approaches relied on numerical approximation or heuristics to compute Katz centrality rankings, we construct an algorithm that iteratively improves those upper and lower bounds until a correct Katz ranking is obtained. We extend our algorithm to dynamic graphs while maintaining its correctness guarantees. Experiments demonstrate that our static graph algorithm outperforms both numerical approaches and heuristics with speedups between 1.5 x and 3.5 x, depending on the desired quality guarantees. Our dynamic graph algorithm improves upon the static algorithm for update batches of less than 10000 edges. We provide efficient parallel CPU and GPU implementations of our algorithms that enable near real-time Katz centrality computation for graphs with hundreds of millions of nodes in fractions of seconds.