Distributed Maximal Independent Set Computation in Hundred Billion-Edge Graphs

cuMIS: A Unified Scalable Framework for Computing Maximal Independent Sets on Trillion-Edge Graphs

This paper addresses the problem of computing a maximal independent set (MIS), defined as a set of vertices where no two vertices are connected by an edge and no additional vertex can be added without violating the independence property. While several GPU-accelerated algorithms exist to find the MIS efficiently, the problem remains challenging for graphs exceeding the memory of a single GPU. In this paper, we present cuMIS, a unified scalable framework for computing MIS on single-GPU, multi-GPU, and distributed multi-node configurations. cuMIS employs a data-driven approach that processes only an active set of undecided vertices for reduced memory access and a degree-aware workload distribution that mitigates imbalance and thread divergence. Our results show that cuMIS outperforms ECL-MIS and MG-MIS—the state-of-the-art single-GPU and multi-GPU baselines—achieving speedups of up to 6.5 × and 156 × , respectively, while maintaining comparable or superior solution quality. Finally, we demonstrate that cuMIS scales effectively to process trillion-edge graphs in distributed multi-node environments where existing approaches fail to operate.

HP-MC: Quickly Computing Maximum Clique Sizes of Large Sparse Graphs

Scalable Graph Coreset Selection via Greedy Sampling

This work proposes a simple and effective column-selective graph sampling algorithm based on a minimum inner product greedy selection rule, well-suited for large-scale graphs where the full Laplacian cannot be stored in memory.

A Survey of Large-Scale Out-of-Core Graph Processing

Through analyzing and mining the relationships among different objects, graph processing is playing an increasingly important role in various application domains, such as social network analysis, product recommendation, and traffic planning. Unfortunately, real-world graphs often exhibit enormous sizes (i.e., trillions of vertices and edges) and complex structures, which makes large-scale in-memory graph processing extremely challenging, if not impractical, and necessitates out-of-core approaches. Therefore, numerous out-of-core graph processing systems have been developed in recent years to efficiently store and process these large graphs. By exploiting the low-cost HDD-/SSD-based external storage and designing disk-friendly graph data placement and execution models, these systems can achieve relatively good performance with low hardware costs, making them a cost-effective solution for large-scale graph analytics. In this paper, we conduct a survey on the designs and implementations of out-of-core graph processing systems. Specifically, we review the key techniques in different dimensions of optimization for out-of-core graph processing systems, including graph preprocessing, graph algorithm execution, utilization of emerging storage devices, and miscellaneous optimizations. For each dimension, we analyze the technical challenges and provide critical insights. Furthermore, we explore and discuss the opportunities for the future research of out-of-core graph processing systems. This survey will help researchers better understand and gain useful insights into the large and complex design space of out-of-core graph processing.

Listing Minimal Cores in Large Real-World Graphs

Cohesive subgraph mining is a fundamental task in graph data analytics. We re-visit the problem of listing all minimal $k$-cores, where a $k$-core is a subgraph in which every vertex has degree at least $k$, and minimality requires that no proper subset remains a $k$-core. Existing methods are computationally prohibitive due to explosive branching and costly branch state update, leading to the trivial worst-case bound $O^{*}\left(2^{n}\right)$ for the basic branch-and-bound baseline wh, where $O^{*}$ suppresses polynomial factors and $n$ is the number of vertices. In this paper, we present an improved method IMinC based on three key ideas: (i) a principled branching state with lineartime update; (ii) a pivot strategy that guides branching toward promising vertices; and (iii) a divide-and-conquer framework that initializes each subproblem to enable our pivot strategy throughout and reduce recursion depth. We further introduce three reduction rules that aggressively prune infeasible branches. Together, these components yield the worst-case time complexity of $O^{*}\left(\alpha_{\ell}^{n}\right)$, where $\alpha_{\ell}$ is a positive number strictly smaller than 2. We also extend IMinC to list minimal $k$-cores under a size bound, addressing practical needs such as size-bounded community search. Extensive experiments on 12 real-world graphs demonstrate that IMinC outperforms the baselines by up to 2 order of magnitude, delivering substantial gains in efficiency.

Fully Dynamic Rooted Spanning Tree on GPU

Spanning trees are fundamental structures in graph theory, essential for various applications such as network maintenance, routing adjustments, and many more. The dynamic nature of real-world networks requires efficient updates to these structures as the underlying graph evolves. Maintaining rooted spanning trees dynamically is particularly crucial for algorithms addressing 2-connected components and minimum-weighted spanning trees. In this paper, we address the challenge of maintaining a rooted spanning forest when a batch of edges are inserted or deleted. We present four novel fully dynamic parallel algorithms to update the spanning forest without reconstructing it from scratch. To the best of our knowledge, parallel algorithms for this problem remain largely unexplored. Our experiments on a diverse collection of real-world graphs using a GPU environment demonstrate a throughput of 2 million insertions and 1.4 million deletions per second, significantly outperforming state-of-the-art parallel static algorithms.