Aug 2026· ACM Computing Surveys· 0 citations· 149 references
TL;DR
This survey will help researchers better understand and gain useful insights into the large and complex design space of out-of-core graph processing, including graph preprocessing, graph algorithm execution, utilization of emerging storage devices, and miscellaneous optimizations.
Abstract
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.
Traditional graph processing systems are built on monolithic servers, which couple a fixed ratio of compute and memory resources but often result in resource under-utilization in data centers. Although the disaggregated memory (DM) architecture has emerged to address this inefficiency, we identify that existing graph processing systems on DM remain highly impractical. They rely on unscalable architectures that fail to scale beyond a single memory node and a single compute node, and they require compute-side caches that are orders of magnitude larger than conventional practice in DM. To this end, this paper presents DMG, the first practical graph processing system on DM, which demonstrates superior system scalability and cache efficiency while delivering high performance. To improve efficiency of graph retrieval on DM, DMG proposes a DM-friendly graph store with retrieval optimizations. To mitigate costly update propagation, DMG presents an adaptive update coordinator that coordinates compute and memory nodes to perform update propagation with low overhead. To enable fast and effective load balancing, DMG employs a two-stage workload manager that includes a coarse-grained initial partitioning and a fine-grained runtime re-scheduling. Experimental results substantiate that compared with the state-of-the-art DM-based graph processing system, DMG can elastically scale up both compute and memory resources, delivering up to 4.9X better performance and accommodating graphs with ever-increasing sizes; meanwhile, it effectively tames the compute-side cache demands by up to 18.9X, positioning itself as a DM-ready solution in practice.
Yizou Chen, Tsun-Yu Yang, Zhisheng Hu et al.· 0 citations
Uncertain graphs are commonly used to model the uncertain relationships between entities that arise from experimental or measurement errors. In recent years, the analysis of uncertain graphs has attracted significant research attention, with the computation of (k,η)-cores emerging as a fundamental problem. However, existing studies on (k,η)-cores often neglect edge directions, resulting in weak correlations among vertices in the resulting subgraph. To address this limitation, we propose a direction-aware (k,l,η)-core model. Specifically, a (k,l,η)-core is defined as a maximal connected subgraph in which every vertex has a probability of at least η of having in-degree ≥k and out-degree ≥l. We first present an online algorithm based on a peeling strategy to compute (k,l,η)-cores. To improve query performance, we develop two indexing mechanisms, DUCS-E and DUCS, that accelerate query processing. DUCS-E stores probability information for all possible (k,l,η)-cores, enabling it to completely avoid redundant computations during query processing, but at the cost of large storage space. To mitigate this issue, we propose the lightweight DUCS index, which stores directional probability information separately, reducing storage overhead while still pruning many irrelevant vertices; however, it requires additional verification. To balance efficiency and storage, we further design a hybrid index that combines the strengths of both approaches. Finally, experimental evaluations on real-world datasets demonstrate the effectiveness of the proposed (k,l,η)-core model as well as the efficiency and scalability of our methods.
Experimental results demonstrate that TWJtr-D significantly reduces computation time and outperforms state-of-the-art methods which process in a similar pattern, highlighting the efficiency of TWJtr-D for triangle detection in large-scale networks.
Sarah Balbouzi, Lougmiri Zekri, Kheira Mechach· ITEGAM- Journal of Engineeri...· 0 citations
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.
Yukai Sun, Kaiqiang Yu, Shengxin Liu et al.· IEEE International Conferenc...· 0 citations
The findings indicate that the Eppstein-Wang algorithm provides a practical and scalable solution for average distance estimation, with higher reliability on unipartite graphs compared to bipartite graphs.
Connected Components (CC) is a foundational primitive in graph analytics, yet scaling it to billion-edge graphs on GPUs remains challenging as real-world graphs exceed GPU capacity. A naïve solution to oversubscribe GPU memory is UVM. However, UVM triggers excessive page faults under the irregular access patterns, while out-of-GPU-memory frameworks either introduce significant preprocessing overhead or suffer from random-access I/O bottlenecks. We present ExCC, an external-memory CC algorithm that keeps the full graph in host-pinned RAM and streams edge batches to the GPU through a three-phase pipeline of union-find merging. ExCC achieves predictable sequential I/O behavior across all phases, demonstrating average speedups of 1.98x over UVM, 4.03x over Subway, and 2.81x over EMOGI on billion-scale graphs.
Prajjwal Nijhara, D. Banerjee· IEEE International Symposium...· 0 citations