Breadth-first search (BFS) is a fundamental building block of various high-performance computing applications beyond graph analysis and also known as a benchmark problem in the Graph 500 list. The increasing volume of global data demands efficient distributed BFS, which, however, is hindered by the high communication costs of exchanging vertex data between compute nodes. To address this challenge, this paper introduces four techniques: (i) forest pruning, which reduces the number of vertices by eliminating those unnecessary for the search; (ii) group reordering and (iii) multilevel bitmap compression, which decrease the memory footprint of graph data, thereby enabling fewer nodes to manage larger graphs; and (iv) adaptive parameter tuning, which quickly optimizes the hyperparameters of the BFS algorithm. In the evaluation using 152,064 nodes of the supercomputer Fugaku, our implementation achieved 198 tera-traversed edges per second, doubling the performance reported in the latest Graph500-related study on Fugaku.

Subgraph matching, which finds subgraphs isomorphic to a query, is crucial for information retrieval from data represented as a graph. To avoid redundant explorations in the data, existing methods restrict the search space by extracting candidate vertices and edges that may constitute isomorphic subgraphs. However, expensive computation is still required because candidate vertices induce many non-isomorphic subgraphs. In this paper, we propose GuP, a subgraph matching algorithm with pruning based on guards. A guard represents a pattern of intermediate search states that never lead to isomorphic subgraphs. By attaching a guard to each candidate vertex and edge, GuP adaptively filters out unnecessary candidates depending on the search state at each step. The experimental results show that GuP effectively reduces the search space and can answer difficult queries that state-of-the-art methods cannot answer within a practical time frame.

One-class SVM is a popular method for one-class classification but it needs high computation cost. This paper proposes Quix as an efficient training algorithm for one-class SVM. It prunes unnecessary data points before applying the SVM solver by computing upper and lower bounds of a parameter that determines the hyper-plane. Since we can efficiently check optimality of the hyper-plane by using the bounds, it guarantees the identical classification results to the original approach. Experiments show that it is up to 6800 times faster than existing approaches without degrading optimality.

Random forest is an ensemble approach based on decision trees. It computes the best split in each node in terms of impurity reduction. However, the impurity computations incur high computation cost in its training process. This paper proposes F-forest, an efficient variant of random forest. It incrementally estimates upper bounds for scores that correspond to impurity reductions to find the best split. Since we can safely skip unnecessary computations, it can guarantee the same training result as the original approach. Experiments show that our approach is faster than state-of-the-art approaches.

Support Vector Machine (SVM) is one of the most popular classification algorithms. SVM separates data points into two classes by using the hyper-plane that is maximally distant from the two classes. Since SVM is theoretically based on statistical learning theory and the principle of structural risk minimization, it offers highly accurate classification. However, its training process is computationally expensive. This paper proposes Sahara as an efficient training algorithm for SVM. It identifies data points that have no influence on SVM classification by computing the upper and lower bounds of a parameter that determines the hyper-plane. Our approach can efficiently compute the bounds by using Singular Value Decomposition (SVD) and a sparse data matrix. Theoretically, our approach guarantees to yield the optimal hyper-plane of SVM for any given set of data points. Experiments show that Sahara is significantly faster than previous approaches.

Ahead-of-time data layout optimization by vertex reordering is a widely used technique to improve memory access locality in graph analysis. While reordered graphs yield better analysis performance, the existing reordering algorithms use significant amounts of computation time to provide efficient vertex ordering, hence, they fail to reduce end-to-end processing time. This paper presents a first algorithm for just-in-time parallel reordering, named Rabbit Order. It reduces end-to-end runtime by achieving high locality and fast reordering at the same time through two approaches. The first approach is hierarchical community-based ordering, which exploits the locality derived from hierarchical community structures in real-world graphs. Our ordering fully leverages low-latency cache levels by mapping hierarchical communities into hierarchical caches. The second approach is parallel incremental aggregation, which improves the runtime efficiency of reordering by decreasing the number of vertices to be processed. In addition, this approach utilizes lightweight atomic operations for concurrency control to avoid locking overheads and achieve high scalability. Our experiments show that Rabbit Order significantly outperforms state-of-the-art reordering algorithms.

The lasso-based L 1 -graph is used in many applications since it can effectively model a set of data points as a graph. The lasso is a popular regression approach and the L 1 -graph represents data points as nodes by using the regression result. More specifically, by solving the L 1 -optimization problem of the lasso, the sparse regression coefficients are used to obtain the weights of the edges in the graph. Conventional graph structures such as k -NN graph use two steps, adjacency searching and weight selection, for constructing the graph whereas the lasso-based L 1 -graph derives the adjacency structure as well as the edge weights simultaneously by using a coordinate descent. However, the construction cost of the lasso-based L 1 -graph is impractical for large data sets since the coordinate descent iteratively updates the weights of all edges until convergence. Our proposal, Castnet, can efficiently construct the lasso-based L 1 -graph. In order to avoid updating the weights of all edges, we prune edges that cannot have nonzero weights before entering the iterations. In addition, we update edge weights only if they are nonzero in the iterations. Experiments show that Castnet is significantly faster than existing approaches.