Graph neural networks (GNNs) have achieved breakthroughs in various real-world downstream tasks due to their powerful expressiveness. As the scale of real-world graphs has been continuously growing, a storage-based approach to GNN training has been studied, which leverages external storage (e.g., NVMe SSDs) to handle such web-scale graphs on a single machine. Although such storage-based GNN training methods have shown promising potential in large-scale GNN training, we observed that they suffer from a severe bottleneck in data preparation since they overlook a critical challenge: how to handle a large number of small storage I/Os. To address the challenge, in this paper, we propose a novel storage-based GNN training framework, named AGNES, that employs a method of block-wise storage I/O processing to fully utilize the I/O bandwidth of high-performance storage devices. Moreover, to further enhance the efficiency of each storage I/O, AGNES employs a simple yet effective strategy, hyperbatch-based processing based on the characteristics of real-world graphs. Comprehensive experiments on five real-world graphs reveal that AGNES consistently outperforms four state-of-the-art methods, up to 4.1× faster than the best competitor.

With the increasing size of real-world networks, efficient analysis of large-scale graphs has become an important research area. To this end, we can consider Processing-in-Memory (PIM), which integrates processing units and main memory into a single chip, as a promising solution. Many studies have focused on enabling highly efficient processing of memory-intensive tasks by using PIM's high internal bandwidth. To the best of our knowledge, however, there have been no studies related to the scenarios where the entire graph does not fit in main memory and data movement across storage, memory, and cache should be considered. Motivated by this, we propose RealGraph PIM, a new PIM-based graph engine, that processes large-scale real-world graphs efficiently on top of the original RealGraph, a state-of-the-art CPU-based graph engine. RealGraph PIM employs (1) asynchronous I/O to reduce wasting time in an idle state and (2) column-wise partitioning to reduce CPU workloads, thereby issuing I/O requests more frequently. Experimental results on real-world datasets show that RealGraph PIM outperforms dramatically state-of-the-art graph engines including a naive version of RealGraphPIM.

Sparse generalized matrix-matrix multiplication (SpGEMM) is a fundamental operation for real-world network analysis. With the increasing size of real-world networks, the single-machine-based SpGEMM approach cannot perform SpGEMM on large-scale networks, exceeding the size of main memory (i.e., not scalable). Although the distributed-system-based approach could handle large-scale SpGEMM based on multiple machines, it suffers from severe inter-machine communication overhead to aggregate results of multiple machines (i.e., not efficient). To address this dilemma, in this paper, we propose a novel storage-based SpGEMM approach (SAGE) that stores given networks in storage (e.g., SSD) and loads only the necessary parts of the networks into main memory when they are required for processing via a 3-layer architecture. Furthermore, we point out three challenges that could degrade the overall performance of SAGE and propose three effective strategies to address them: (1) block-based workload allocation for balancing workloads across threads, (2) in-memory partial aggregation for reducing the amount of unnecessarily generated storage-memory I/Os, and (3) distribution-aware memory allocation for preventing unexpected buffer overflows in main memory. Via extensive evaluation, we verify the superiority of SAGE over existing SpGEMM methods in terms of scalability and efficiency.

Sparse general matrix-matrix multiplication (SpGEMM) is a major kernel in various emerging applications, such as database management systems, deep learning, graph analysis, and recommendation systems. Since SpGEMM requires extensive computation, many SpGEMM techniques have been implemented based on graphics processing units (GPUs) to exploit massive data parallelism completely. However, traditional SpGEMM techniques usually do not fully utilize the GPU because most non-zero elements of the target sparse matrices exist in a few hub nodes, and non-hub nodes barely have non-zero elements. The data-related characteristics (power law) result in a significant degradation in performance because of the load imbalance between the GPU cores and the low utilization of each core. Many attempts have been made through recent implementations to solve this problem using smart pre-/post-processing. However, the net performance hardly improves and sometimes even deteriorates owing to the large overheads. Additionally, non-hub nodes are inherently not suitable for GPU computing, even after optimization. Furthermore, the performance is no longer dominated by kernel execution, but by data transfers such as device-to-host (D2H) data transfers and file I/Os, owing to the rapid growth in the computing power of GPUs and input data size.Therefore, this work proposes a Dynamic Block Distributor (DBD), a novel full-system-level SpGEMM orchestration framework for heterogeneous systems, improving the overall performance by enabling an efficient CPU-GPU collaboration and further minimizing the overhead in data transfer between all the system elements. This framework first divides the target matrix into smaller blocks and then offloads the computation of each block to an appropriate computing unit between a GPU and CPU based on its workload type and the status of resource utilization at runtime. It also minimizes the overhead in data transfer with simple but suitable techniques, such as Row Collecting, I/O Overlapping, and I/O Binding. Our experiments showed that this framework increased the execution latency of SpGEMM, which included both the kernel execution and D2H transfers, by 3.24x on average, and the overall execution time by 2.07x on average, compared to that of the baseline cuSPARSE library.

A graph, consisting of vertices and edges, has been widely adopted for network analysis. Recently, with the increasing size of real-world networks, many graph engines have been studied to efficiently process large-scale real-world graphs. RealGraph, one of the state-of-the-art single-machine-based graph engines, efficiently processes storage-to-memory I/Os by considering unique characteristics of real-world graphs. Via an in-depth analysis of RealGraph, however, we found that there is still a chance for more performance improvement in the computation part of RealGraph despite its great I/O processing ability. Motivated by this, in this paper, we propose RealGraphGPU, a GPU-based single-machine graph engine. We design the core components required for GPU-based graph processing and incorporate them into the architecture of RealGraph. Further, we propose two optimizations that successfully address the technical issues that could cause the performance degradation in the GPU-based graph engine: buffer pre-checking and edge-based workload allocation strategies. Through extensive evaluation with 6 real-world datasets, we demonstrate that (1) RealGraphGPU improves RealGraph by up to 546%, (2) RealGraphGPU outperforms existing state-of-the-art graph engines dramatically, and (3) the optimizations are all effective in large-scale graph processing.

Graph engines have been used in many applications to handle big graphs efficiently. The majority of the research to improve their performance has focused primarily on the design of efficient graph processing. This paper claims,however,the focus should be given also to graph storage design. This is because good storage design can improve both CPU performance and I/O performance of graph engines. In this paper,we propose an efficient data layout for single-machine based graph engines. We identify the common node access pattern of the graph algorithms running on single-machine based graph engines. Based on this finding,we propose the breadth-first (BF) data layout which places the nodes processed together in the same or adjacent storage space so that they can be accessed together as much as possible. The experimental results show that the BF data layout improves both CPU and I/O performances significantly in all single-machine based graph engines.

In this demo, we present RealGraph Web , a web-based platform that provides various kinds of graph analysis services. RealGraph Web is based on RealGraph, a graph engine that addresses the problem of performance degradation in processing real-world big graphs, achieving great performance improvement up to 44 times over existing state-of-the-art graph engines. RealGraph Web runs on a single machine with a web-based interface, thereby allowing users to easily and conveniently enjoy graph analysis services and perform various graph algorithms anywhere on the web . In this demo, we present how a user can analyze a graph on RealGraph Web in three steps and get the analysis result quickly via a graphical user interface.

As the size of real-world graphs has drastically increased in recent years, a wide variety of graph engines have been developed to deal with such big graphs efficiently. However, the majority of graph engines have been designed without considering the power-law degree distribution of real-world graphs seriously. Two problems have been observed when existing graph engines process real-world graphs: inefficient scanning of the sparse indicator and the delay in iteration progress due to uneven workload distribution. In this paper, we propose RealGraph, a single-machine based graph engine equipped with the hierarchical indicator and the block-based workload allocation. Experimental results on real-world datasets show that RealGraph significantly outperforms existing graph engines in terms of both speed and scalability.

Graphs are very widely used to represent datasets in various real-world applications. Many algorithms dealing with graphs represent them in the form of sparse matrices and process them through sparse matrix operations. Recently, as the size of a graph increases rapidly, a single-machine-based graph engine has emerged as a general framework for effectively performing large-scale sparse matrix operations. Sparse matrices multiplication (SpGEMM) is a core building block for developing a variety of graph algorithms such as all source shortest paths, betweenness centrality, breadth first search from multiple sources, subgraph indexing, and graph construction. This paper addresses how to perform two sparse matrices multiplication (SpGEMM) efficiently on a single-machine-based graph engine. To effectively perform the large-scale SpGEMM, we have two issues: (1) selecting an appropriate type of matrix products (i.e., inner products, outer products, and row-row products), and (2) allocating memory space to matrices according to different types of matrix products. We first formulate the cost models for the three matrix product types by reflecting their characteristics. We observed the commonality in the processes of the matrix multiplication and the join in a relational database. Based on this observation, we propose memory allocation schemes for three matrix products by borrowing the idea of memory allocation employed in join. Finally, we show the effectiveness of our approach via extensive experiments with real-life datasets.

The size of graphs has dramatically increased. Graph engines for a single machine have been emerged to process these graphs efficiently. However, existing engines have overlooked a data locality which is an imperative factor to improve the performance of these engines in the previous literature. In this paper, we show the importance of data locality with graph algorithms by running on graph engines based on a single machine.