UC Riverside

Analyses on large graphs are an increasingly important computational workload as graph analytics is employed in many domains. Therefore, a great deal of research in this area has focused on building frameworks that exploit the parallelism available on various hardware platforms ranging from a single GPU or a multicore server to a cluster of servers and/or GPUs. This thesis combines parallelism with a complimentary approach that comprehensively reduces redundancy for scaling performance. Redundancy can be found and removed not only from the computation and propagation of values, but also from graph traversal and graph data transfer across memory hierarchy. This thesis applies redundancy reduction to the two main graph analytics scenarios, involving static (fixed) graphs and evolving (changing) graphs, and obtained substantial performance improvements.To remove redundancy from the evaluation of a query over a static graph, we combine the use of a small proxy graph and the large original graph in a two-phase query evaluation. The first phase evaluates the query on the proxy graph incurring low overheads and producing mostly precise results. The second phase uses these mostly precise results to bootstrap query evaluation on the larger original graph producing fully precise results. The effectiveness of this approach depends upon the quality of the proxy graph. We have developed a new form of proxy graph named the Core Graph (CG) that is not only small, it also produces highly precise results [EuroSys 2024]. A CG is a subgraph of the larger input graph that contains all vertices but on average contains only 10.7% of edges and yet produces precise results for 94.5 - 99.9% vertices in the graph for different kinds of queries. The finding of such an effective CG is based on our key new insight, namely, a small subset of non-zero centrality edges are responsible for determining the converged results of nearly all the vertices across different queries. Across six kinds of graph queries and four input graphs, CGs improved the performance of the GPU-based Subway system by up to 4.48x.The challenge of evaluating a query further intensifies when it is to be evaluated over a sequence of snapshots of an evolving graph, where changes occur through the addition and deletion of edges. To remove redundancy from evaluation of a query over an evolving graph (i.e., evaluation of a query on multiple snapshots of a changing graph), we propose Common Graph [ASPLOS 2023]. We first observe that edge deletion operations are significantly more expensive than edge addition operations for many graph queries. Common Graph converts all deletions to additions by finding a common graph that exists across all snapshots. After computing the query on this graph, to reach any snapshot, we simply need to add the missing edges and incrementally update the query results. Common Graph also allows sharing of common additions among snapshots that require them, and breaks the sequential dependency inherent in the traditional streaming approach where snapshots are processed in sequence, enabling additional opportunities for parallelism. Common Graph achieves 1.38x - 8.17x improvement in performance over KickStarter based on streaming across multiple benchmarks.In a recent study we identified another opportunity for redundancy reduction. It shows that due to the gradually changing nature of evolving graphs, when a vertex-specific query is evaluated over a sequence of 25 to 100 snapshots, for over 50% to 90% of vertices the query results remain unchanged across all snapshots. Therefore, the Unchanged Vertex Values (UVVs) can be computed once and then minimal analysis can be performed for each snapshot to obtain the results for the rest of the vertices for each snapshot. We have developed a novel intersection-union analysis that very accurately computes lower and upper bounds of vertex values across all snapshots. When the lower and upper bounds for a vertex are found to be equal, we can safely conclude that the value found for the vertex remains the same across all snapshots. Therefore, the rest of our query evaluation is limited to computing values across snapshots for vertices whose bounds do not match. Our experiments with several benchmarks and graphs show that we need to carry out per snapshot incremental analysis for under 42% vertices on a graph with under 32% of edges. Our approach delivers speedups of 2.01× – 12.23× when compared to the state-of-the-art RisGraph implementation of the KickStarter-based incremental algorithm for 64 snapshots.