Finding a minimum spanning tree (MST) for $n$ points in an arbitrary metric space is a fundamental primitive for hierarchical clustering and many other ML tasks, but this takes $\Omega(n^2)$ time to even approximate. We introduce a framework for metric MSTs that first (1) finds a forest of trees using practical heuristics, and then (2) finds a small weight set of edges to connect disjoint components in the forest into a spanning tree. We prove that optimally solving step (2) still takes $\Omega(n^2)$ time, but we provide a subquadratic 2.62-approximation algorithm. In the spirit of learning-augmented algorithms, we then show that if the heuristic forest found in step (1) overlaps with an optimal MST, we can approximate the original MST problem in subquadratic time, where the approximation factor depends on a measure of overlap. In practice, we find nearly optimal spanning trees for a wide range of metrics, while being orders of magnitude faster than exact algorithms.

Given an edge-weighted graph and a set of known seed vertices of interest, a network scientist often desires to understand the graph relationships to explain connections between the seed vertices. If the size of the seed set is 2, shortest path calculations are an attractive computational kernel to explore the connections between the two vertices. When the seed set is 3 or larger (say up to 1,000s) Steiner minimal tree – min-weight acyclic connected subgraph (of the input graph) that contains all the seed vertices – is an attractive generalization of shortest weighted paths. In general, computing a Steiner minimal tree is NP-hard, but decades ago several polynomial-time algorithms were designed and proven to yield Steiner trees whose total weight is bounded within 2 times the minimal Steiner tree. Despite its rich theoretical literature, works related to parallel Steiner minimal tree computation and their scalable implementations are rather scarce. In this paper, we present a parallel 2-approximation Steiner minimal tree algorithm (with theoretical guarantees) and its MPI-based distributed implementation. In place of distance computation between all pairs of seed vertices, an expensive phase in many approximation algorithms, the solution we employ, exploits Voronoi cell computation. Also, this approach has higher parallel efficiency than others that involve minimum spanning tree computation on the entire graph. Furthermore, our distributed design exploits asynchronous processing and a message prioritization scheme to accelerate convergence of distance computation, employs techniques to avoid inefficient distributed spanning tree computation on the entire graph, and harnesses a combination of vertex and edge centric processing to offer fast time-to-solution. We demonstrate scalability and performance of our solution using real-world graphs with up to 128 billion edges and 512 compute nodes (8K processes), show the ability to find Steiner trees with up to 10K seed vertices in under one minute, and present in-depth analyses that highlight the benefits of our design choices. Using four real-world graphs and three seed sets for each, we compare our solution with the state-of-the-art exact Steiner minimal tree solver, SCIP-Jack, and two sequential algorithms with the same approximation bound as our algorithm. Our distributed solution comfortably outperforms these related works on graphs with 10s million edges and offers decent strong scaling – up to 90% efficient. We empirically show that, on average, the total distance (sum of edge weights) of the Steiner tree identified by our solution is 1.0527 times greater than the Steiner minimal tree (i.e., the optimal solution) – well within the theoretical bound of less than equal to 2.

Various digital data sets that encode user-item relationships contain a multilevel overlapping cluster structure. The user-item relation can be encoded in a weighted bipartite graph and uncovering these overlapping coclusters of users and items at multiple levels in the bipartite graph can play an important role in analyzing user-item data in many applications. For example, for effective online marketing, such as placing online ads or deploying smart online marketing strategies, identifying co-occurring clusters of users and items can lead to accurately targeted advertisements and better marketing outcomes. In this paper, we propose fast algorithms inspired by algebraic multigrid methods for finding multilevel overlapping cocluster structures of feature matrices that encode user-item relations. Starting from the weighted bipartite graph structure of the feature matrix, the algorithms use agglomeration procedures to recursively coarsen the bipartite graphs that represent the relations between the coclusters on increasingly coarser levels. New fast coarsening routines are described that circumvent the bottleneck of all-to-all similarity computations by exploiting measures of direct connection strength between row and column variables in the feature matrix. Providing accurate coclusters at multiple levels in a manner that can scale to large data sets is a challenging task. In this paper, we propose heuristic algorithms that approximately and recursively minimize normalized cuts to obtain coclusters in the aggregated bipartite graphs on multiple levels of resolution. Whereas the main novelty and focus of the paper lies in algorithmic aspects of reducing computational complexity to obtain scalable methods specifically for large rectangular user-item matrices, the algorithmic variants also define several new models for determining multilevel coclusters that we justify intuitively by relating them to principles that underlie collaborative filtering methods for user-item relationships. Experimental results show that the proposed algorithms successfully uncover the multilevel overlapping cluster structure for artificial and real data sets. Summary of Contribution: This paper develops new and efficient computational methods for finding the multilevel overlapping cocluster structure of feature matrices that encode user-item relationships. We base our approach on the use of pairwise similarity measures between features, seeking clusters of points that are similar to each other and dissimilar from the points outside the cluster. We approximately solve the problem of finding optimal overlapping coclusters on multiple levels by employing a framework that is based on efficient multilevel methods that have been used previously to solve sparse linear systems and to cluster graphs. Our main contribution is that we extend these methods in efficient manners to find coclusters in the bipartite graphs that encode common and important user-item relationships or social network relations. The novel methods that we propose are inherently scalable to large problem sizes and are naturally able to uncover overlapping coclusters at multiple levels, whereas existing methods generally only find coclusters at the fine level. We illustrate the algorithm and its performance on some standard test problems from the literature and on a proof-of-concept real-world data set that relates LinkedIn users to their skills and expertise.

Dynamic graphs are natural abstractions for modeling correlations in brain activity. These correlation graphs are constructed from time-series signals corresponding to neuronal activity in different regions of the brain over suitably selected time windows, by linking correlated regions via edges. An important problem in the context of these dynamic correlation graphs is the discovery of sets of regions of the brain, whose activity level is temporally coherent. These manifest as temporally persistent sub-graphs that are strongly connected, referred to as coherent subgraphs. In this paper, we present a model and method for identifying coherent subgraphs in dynamic correlation graphs. We show that densely connected components in correlation graphs can be effectively modeled as low-rank sub-matrices derived from the time series signals. Specifically, we derive theoretical results showing that quasi cliques in a correlation graph can be inferred from rows of the left singular matrix of its time-series, and can be tracked in time to identify coherent subgraphs. We apply our proposed method to real-world time-series data from functional MRIs. We show that signals corresponding to nodes in coherent subgraphs can accurately predict whether the subject was actively performing a cognitive task, or was at rest. Furthermore, we also show that the same set of nodes can predict task outcomes/ conditions (such as win v/s loss in a gambling task). To the best of our knowledge, our work is the first in theoretically modeling and analyzing dynamic brain networks using spectral decomposition of the windowed time-series.

Understanding the higher-order interactions within network data is a key objective of network science. Surveys of metadata triangles (or patterned 3-cycles in metadata-enriched graphs) are often of interest in this pursuit. In this work, we develop TriPoll, a prototype distributed HPC system capable of surveying triangles in massive graphs containing metadata on their edges and vertices. We contrast our approach with much of the prior effort on triangle analysis, which often focuses on simple triangle counting, usually in simple graphs with no metadata. We assess the scalability of TriPoll when surveying triangles involving metadata on real and synthetic graphs with up to hundreds of billions of edges. We utilize communication-reducing optimizations to demonstrate a triangle counting task on a 224 billion edge web graph in approximately half of the time of competing approaches, while additionally supporting metadata-aware capabilities.

There are multiple situations where supporting approximation in graph pattern matching tasks is highly desirable: (i) the data acquisition process can be noisy; (ii) a user may only have an imprecise idea of the search query; and (iii) approximation can be used for high volume vertex labeling when extracting machine learning features from graph data. We present a new algorithmic pipeline for approximate matching that combines edit-distance based matching with systematic graph pruning. We formalize the problem as identifying all exact matches for up to k edit-distance subgraphs of a user-supplied template. We design a solution which exploits unique optimization opportunities within the design space, not explored previously. Our solution is (i) highly scalable, (ii) supports arbitrary patterns and edit-distance, (iii) offers 100% precision and 100% recall guarantees, and (vi) supports a set of popular data analysis scenarios. We demonstrate its advantages through an implementation that offers good strong and weak scaling on massive real-world (257 billion edges) and synthetic (1.1 trillion edges) labeled graphs, respectively, and when operating on a massive cluster (256 nodes/9,216 cores), orders of magnitude larger than previously used for similar problems. Empirical comparison with the state-of-the-art highlights the advantages of our solution when handling massive graphs and complex patterns.

The eccentricity of a vertex is defined as the length of the longest shortest path to any other vertex. While eccentricity is an important measure of vertex centrality, directly computing exact eccentricity for all vertices on large-scale graphs is prohibitively costly. Takes and Kosters proposed an iterative algorithm that uses multiple runs of single-source shortest path (SSSP) to compute lower and upper bounds on eccentricity at every vertex. Their technique converges to exact eccentricity by performing SSSP from only a small percentage of vertices, when sources are efficiently selected. However, their source selection strategies do not always yield rapid convergence. We propose a pincer movement source selection algorithm that efficiently selects source vertices based on analysis of the lower and upper bounds produced by SSSP. We also leverage k-BFS, which runs breadth-first search (BFS) from multiple sources concurrently on HavoqGT, a high-performance vertex-centric message-passing graph processing framework, to achieve an additional significant performance improvement on distributed-memory systems. We demonstrate that our novel source vertex selection strategy has better performance on various real-world graph datasets compared with the previous strategy. In addition, we compute exact eccentricity for graphs with more than 1000X more edges (112B undirected edges) than graphs in the previous literature.

Subgraph pattern matching is fundamental to graph analytics and has wide applications. Unfortunately, high computational complexity limits the robustness guarantees of existing algorithms: they do not scale for modern large graph datasets and/or they have limitations in terms of accuracy or in terms of the intricacy of the patterns supported. We present algorithms, theory, and empirical evidence that iteratively eliminating vertices that do not meet local constraints dramatically reduces the search space for pattern matching in real-world graphs, and demonstrate a scalable implementation of our algorithms. We additionally identify the characteristics of patterns for which every non-eliminated vertex participates in a match. These techniques are an essential step to enable scalable, practical solutions for robust pattern matching in large-scale labeled graphs.We demonstrate the advantages of the proposed approach through strong and weak scaling experiments on massive-scale real-world (up to 257 billion edges) and synthetic (up to 2.2 trillion edges) graphs and at scales (256 compute nodes with 6,144 processors) orders of magnitude larger than those used in the past for similar problems.