Graph processing suffers from severe locality challenges due to considerable inefficient irregular memory accesses, which mainly originate from random accesses to neighbors of active vertices (a.k.a frontiers). Graph reordering, which assigns continuous IDs to vertices that are more likely to be accessed consecutively, can improve access locality effectively and has demonstrated significant speedups across various architectures and systems. Existing graph reordering methods primarily explore the overlapping intensity of in-neighbor vertices for the data access locality characterization. However, many graph algorithms often activate a fraction of the vertices across the graphs, which vary substantially over different inputs and processing iterations. Many of these vertices are neither connected nor have any shared neighbors, but they are actually processed at the same time and exhibit potential data access locality, which is generally overlooked in prior graph reordering methods. We notice that the data locality between concurrently activated vertices are usually attributed to the overlapped$k$-order in-neighbors. As the number of$k$-order in-neighbors grows explosively, it is unacceptably time-consuming to analyze the overlapping of$k$-order in-neighbors for graph reordering directly. In this case, we propose to replace the overlapping calculation of$k$-order in-neighbors with frontier distribution analysis of a few BFS samplings. Specifically, we profile the frontiers distributed across iterations of different BFS samplings first and build a feature vector based on the activated iteration order of each vertex in the BFS samplings. On top of the feature vectors, we propose FrontOrder, which has a customized distance metric to characterize the locality between different vertices and leverages$K$-means to cluster vertices with high locality to guide graph reordering. In addition, FrontOrder also takes the load balance into consideration by predicting the runtime computing intensity with the learned clusters of vertices. According to our experiments, FrontOrder delivers an average performance speedup of${2.33\times}$and${1.57\times}$on Ligra and GPOP, respectively, and consistently outperforms the state-of-the-art graph reordering methods on a set of representative graph algorithms and datasets with moderate preprocessing overhead.

Out-of-core graph processing systems are severely bottlenecked by I/O to the external storage because of the low compute-to-I/O ratio and the substantial amount of irregular data accesses. In order to alleviate the I/O bottleneck, prior works either focus on improving the bandwidth utilization by converting random I/O requests into sequential ones, or improving the data utilization by fetching only the required data to avoid the I/O redundancy. However, the former usually loads massive unused data, while the latter can induce frequent finegrained I/O requests, wasting the parallelism of the I/O channels and leading to under-utilization of the limited I/O bandwidth. Different from prior works, we systematically explore the use of computational storage devices (CSDs), which offer in-storage computing facilities with higher I/O bandwidth, to improve both the bandwidth utilization and data utilization for higher I/O efficiency. Specifically, we first introduce a graph-semanticaware data organization to enable the loading of only active graph partitions at the granularity of a physical page, reducing redundant I/O and enhancing data utilization. Additionally, we propose to coalesce parallel I/O requests of graph partitions distributed across different flash dies to maximize the parallelism of internal I/O channels, thereby fully utilizing the internal I/O bandwidth of CSDs. In addition, we capture the dynamic status of graph processing tasks across the iterations and partitions at runtime to dynamically offload I/O-intensive workloads into the instorage processors with restricted computing resources but higher I/O bandwidth to further improve the I/O efficiency. With the above techniques, we implement an out-of-core graph processing system prototype, namely TaijiGraph, on an open-channel CSD. According to our experiments on a set of representative graph datasets and algorithms, TaijiGraph achieves average speedups of$2.43 \times, 3.81 \times, 2.21 \times$and$7.89 \times$, respectively, when compared to state-of-the-art out-of-core graph processing systems including GridGraph, LUMOS, Blaze, and GraphSSD.

Due to hardware customization capabilities, FPGA-based graph processing accelerators achieve significantly higher energy efficiency than many general-purpose computing engines. However, designing these accelerators remains a substantial challenge for high-level users. To overcome the programming barrier, FPGA-based accelerator design frameworks on top of generic graph processing programming models have been developed to automate accelerator generation through pre-built templates. However, they often tightly couple graph processing algorithms, programming models and processing paradigms, and accelerator architectures, which severely limits the expression scope of the algorithms and may also restrict the performance when the generated accelerators fail to suit dynamic processing patterns of the graph processing algorithms.

Graph reordering is an effective technique for improving the access locality of graph processing. However, existing methods often overlook the data access locality among concurrently activated vertices (a.k.a. frontiers). These vertices, while lacking direct connections or shared neighbors, can exhibit significant locality attributed to their overlapped k-order in-neighbors. However, calculating such overlaps directly is computationally prohibitive. We propose to estimate the overlapped k-order in-neighbors through frontier distribution analysis based on a few BFS samples. Our proposed graph reordering method, FrontOrder, constructs feature vectors from the frontier distribution of BFS samples, and employs K-means clustering with a custom distance metric to group vertices with high locality. Additionally, the learned clusters can predict runtime computing intensity, enabling load balancing through vertex reordering. FrontOrder achieves average speedups of 2.65× on Ligra and 1.73× on GPOP, outperforming state-of-the-art methods.

Dynamic graphs can be utilized to model many real-world applications like social media analysis in which the connections and entities evolve continuously. Hence, the processing of dynamic graphs is gaining increasing popularity. However, prior dynamic graph processing systems mainly focus on the optimization of graph analytics but overlook graph updating which manages the evolving graph structure and presents a unified view to graph analytics. Since graph updating operates on evolving graphs and involves a large number of irregular memory accesses, it poses a substantial influence on the performance of dynamic graph processing systems. In this work, we observe that graph updating is mainly bottlenecked by a frequent indirect memory access pattern *(*(BAi+offset)). The pattern is inherent to the typical graph updating from the incoming edge stream to the base data store organized with either an adjacent list or a compressed sparse row. With this observation, we propose a novel Prefetcher for Dynamic Graph updating abbreviated as PDG. PDG is a lightweight pipelined instruction-based prefetcher specialized for graph updating and it is also compatible with the irregular memory access pattern BAi widely used in graph analytics. In addition, it leverages a monitor of the instruction queue to decide the appropriate timing of prefetching to make the best use of the cache. According to our experiments, PDG achieves 1.60×, 1.26× and 1.30× performance speedup compared to three representative prefetchers respectively with negligible hardware overhead in graph updating.

Higher-order proximity preserved network embedding has attracted increasing attention. In particular, due to the superior scalability, random-walk-based network embedding has also been well developed, which could efficiently explore higher-order neighborhoods via multi-hop random walks. However, despite the success of current random-walk-based methods, most of them are usually not expressive enough to preserve the personalized higher-order proximity and lack a straightforward objective to theoretically articulate what and how network proximity is preserved. In this paper, to address the above issues, we present a general scalable random-walk-based network embedding framework, in which random walk is explicitly incorporated into a sound objective designed theoretically to preserve arbitrary higher-order proximity. Further, we introduce the random walk with restart process into the framework to naturally and effectively achieve personalized-weighted preservation of proximities of different orders. We conduct extensive experiments on several real-world networks and demonstrate that our proposed method consistently and substantially outperforms the state-of-the-art network embedding methods.