HashOrder: Accelerating Graph Processing Through Hashing-based Reordering

I am largely positive for the paper but surprised that the authors do not provide responses to the reviews. As such, I will not fight against rejecting the paper.

We apologize for not posting the responses earlier. We had an unusually large number of reviewers and we had been working on a large set of additional experiments to address the reviewers' concerns. We will be posting the responses shortly.

We thank the reviewer for recognizing the strengths of the paper in terms of the novelty of the idea and effectiveness of the method. We respond to the reviewer’s comments as follows.

1. Discussion on how hashing is used to handle graph problems in the related work.

Some notable related works include [1, 2, 3]. Specifically, [1] develops a highly efficient graph community detection method based on MinHash, [2] derives meaningful features from MinHash and HyperLogLog for learning link prediction models on graphs, [3] develops a scalable set-based graph summarization algorithm based on LSH. We will add the discussion to the final paper.

2. Any ideas on how HashOrder can benefit from multiple hash signatures?

Our final hash function is indeed composed of the concatenation of multiple hash functions. By increasing the number of hash functions, we can ensure that the hash function can distinguish whether a pair of nodes lie inside a cluster or in different clusters. The exact characterization of this property and required number of hash functions to obtain theoretical guarantees is provided in Theorem 1. Empirically, we found l=2 improves the ordering quality over l=1 (0.27% and 0.19% higher relative speedup), where l is the number of hash signatures. l=4 negatively impacts the ordering quality (7.89% and 1.46% lower relative speedup than 2 hashes), likely due to diminishing probability of collision for pairs inside a cluster.

References

[1] Chamberlain, Benjamin Paul, et al. "Real-time community detection in full social networks on a laptop." PloS one 13.1 (2018): e0188702.

[2] Chamberlain, Benjamin Paul, et al. "Graph neural networks for link prediction with subgraph sketching." arXiv preprint arXiv:2209.15486 (2022).

[3] Yong, Quinton, et al. "Efficient graph summarization using weighted lsh at billion-scale." Proceedings of the 2021 International Conference on Management of Data. 2021.

We thank the reviewer for recognizing the strengths of the paper in terms of the presentation, the theoretical support, and the empirical effectiveness of our proposed method. We address the reviewer’s concerns and questions below, and we are happy to add these discussions to the final paper. If the reviewer's concerns are sufficiently answered, we urge the reviewer to reconsider the score. If not, we would be happy to answer further clarifications.

1. Difference between existing methods and our proposed method.

Sorry for the confusion--there is no existing hash-based graph sorting algorithm. Our proposed method is a first of its kind probabilistic approach to the reordering problem, which is completely different from the existing methods. The existing methods can be categorized as follows 1) greedy optimization-based methods, such as GOrder 2) graph traversal-based methods, such as RCM 3) degree sorting-based methods, such as SortIn, SortOut, HubCluster, HubSort, and DBG. In contrast to these methods, HashOrder optimizes the fitness of all nodes simultaneously (unlike greedy and graph traversal-based methods) by leveraging randomized hashing and takes the higher order neighborhood into account (unlike degree sorting-based methods).

2. Can you briefly describe what kind of graph reordering algorithms are used in the existing methods based on the proposed method?

We apologize for not understanding this question. Could you please further elaborate on the question?

3. Experiments using datasets other than small-world and scale-free graphs.

Most real-world graphs exhibit small-world and power-law properties. Hence we study random graphs generated from Erdős-Rényi (ER) and Barabási-Albert (BA) models. ER is a well-studied scale-free random network model, while a BA network exhibits preferential attachment. We compare the runtime of one iteration of PageRank averaged over 5 runs on random graphs with different configurations, with n as the number of nodes and m as the number of edges. HashOrder achieves higher speedups than GOrder across different random graphs.

We thank the reviewer for recognizing the strengths of the paper in terms of the effectiveness of the proposed method. We address the reviewer's concerns and questions below. If the reviewer's concerns are sufficiently answered, we urge the reviewer to reconsider their score. If not, we would be happy to answer further clarifications.

1. LSH has been used in similar problems for graph reordering.

To the best of our knowledge, our proposed method is the first probabilistic approach to the reordering problem, which is completely different from existing methods. The existing methods can be categorized as follows 1) greedy optimization-based methods, such as GOrder 2) graph traversal-based methods, such as RCM 3) degree sorting-based methods, such as SortIn, SortOut, HubCluster, HubSort, and DBG. In contrast to these methods, HashOrder optimizes the fitness of all nodes simultaneously (unlike greedy and graph traversal-based methods) by leveraging randomized hashing and takes the higher order neighborhood into account (unlike degree sorting-based methods). LSH has been used for problems such as sparse-dense matrix multiplication, task scheduling, and load balancing, which are distinct problems from graph reordering and require dedicated solutions.

2. Can HashOrder run on GPU?

Yes, HashOrder can run on GPU since it conforms to the SIMD paradigm. The building blocks of the HashOrder algorithm are message passing with minimum aggregation and sorting, which are parallelizable operations on the GPU.

We perform experiments for two data loading mechanisms (1) when data loading happens on CPUs and (2) when data loading happens via UVA mechanism on GPUs (see figure 4). In both cases, even if the data per node is larger than cache-size, the colocation of data for two nodes which are accessed together inside a page helps. We explain this below,

1. On GPU via UVA : In this case there will be a page miss when GPU accesses a node data from a page not previously accessed.
2. On CPU : In this case there will be a TLB miss when CPU accesses a node data from a page which is not present in the TLB.

We thank the reviewer for recognizing the strengths of the paper in terms of the interestingness of the idea, the presentation of the paper, and the comprehensive evaluations of the proposed method. We respond to the reviewer’s concerns as follows.

1. Does not seem to have significant improvement compared to GOrder.

Our proposed method outperforms or is competitive with GOrder wrt downstream application runtime, while having significantly lower computational overhead. As shown in Figure 2, HashOrder surpasses GOrder in terms of ordering quality on average across all tasks, while being 592x (on average) more efficient in reordering.

2. Reporting median speedup/limited median speedup?

We see significant average speedups across tasks in downstream applications. We updated the paper to report the average speedup across datasets in the abstract. HashOrder speeds up PageRank by 1.44x and GNN data loaders by 1.93x on average.

3. Show end-to-end speedup for GNN training.

We present additional experimental results on end-to-end GNN training time. We train a 3-layer GCN on ogbn-papers100M using the MultiLayerFullNeighborSampler with different reordering algorithms, and measure the data loading and training time per batch. HashOrder outperforms RCM and achieves up to 36.55% speedup on end-to-end GNN training. We will add the results to the final paper.

4. Measure cache hits in the experiments.

We have already included cache hit rates in Table 3 and 4 in the appendix.

5. Will reordering lead to other side effects?

We do not expect any negative side effects from reordering. Reordering improves the locality of the data layout so it accelerates training and inference. Accuracy is not affected as the graph remains the same with better memory layout.

6. Blanks in Figure 4.

Blanks in Figure 4 means the experiments are not feasible for those settings due to the inherent limitations of the GNN library. GraphSAINT sampler fails on ogbn-papers100M since torch.multinomial does not support a number of categories beyond 2^24. Full neighbor sampling using UVA fails on ogbn-products and ogbn-papers100M due to GPU memory limitations. We will improve the figure to clarify this.

7. Why l=2?

Empirically, we found l=2 marginally improves the ordering quality over l=1 (0.27% and 0.19% higher relative speedup). l=4 negatively impacts the ordering quality (7.89% and 1.46% lower relative speedup than 2 hashes), likely due to diminishing probability of collision.

5. End-to-end evaluation that encompasses both reordering and graph analysis.

In real-world industry applications, graph analysis can be prohibitively expensive and [3] shows that even reordering with high overhead can benefit the end-to-end application run time. Even in our experiments with simple graph analysis, we found that HashOrder can consistently speedup the end-to-end run time of PageRank, which we present the results in the following table.

References

[2] V. Balaji and B. Lucia, "When is Graph Reordering an Optimization? Studying the Effect of Lightweight Graph Reordering Across Applications and Input Graphs," 2018 IEEE International Symposium on Workload Characterization (IISWC), Raleigh, NC, USA, 2018, pp. 203-214, doi: 10.1109/IISWC.2018.8573478.

[3] Wei, Hao, et al. "Speedup graph processing by graph ordering." Proceedings of the 2016 International Conference on Management of Data. 2016.

We thank the reviewer for recognizing the strengths of the paper in terms of the empirical effectiveness and the theoretical support of the proposed method. We address the reviewer's concerns and questions below. If the reviewer's concerns are sufficiently answered, we urge the reviewer to reconsider their score. If not, we would be happy to answer further clarifications.

1. Evaluations on GNN training and inference time.

We present additional experimental results on end-to-end GNN training time. We train a 3-layer GCN on ogbn-papers100M using the MultiLayerFullNeighborSampler with different reordering algorithms in DGL framework, and measure the data loading and training time per batch. HashOrder outperforms RCM and achieves up to 36.55% speedup on end-to-end GNN training.

2. Comparison with Rabbit Order.

We compare HashOrder with Rabbit Order on the efficiency of solving the SSSP (single-source shortest path) problem. For Rabbit Order, we use the official implementation from GitHub. The table below shows the relative speedup of different algorithms. HashOrder achieves greater speedups than Rabbit Order and GOrder. Rabbit Order generally performs worse than GOrder, which is consistent with the findings in [1].

3. The definition of fitness is extended from the GO algorithm.

The definition of fitness in GO has drawbacks. It considers a sliding window and evaluates pairs of nodes inside the sliding window, and thus includes pairs which might lie in different cache lines/pages. However, in reality, evaluating pairs of nodes exclusively within a cache line/page better reflects the hardware. We fix this issue in our fitness definition. Additionally, we also generalize the inner product (neighbourhood intersection) used by GO to measure pairwise fitness. We find that our formulation allows for other metrics such as Jaccard similarity which can lead to efficient algorithms such as HashOrder.

4. The size of epsilon in the proposal.

We have reformulated the theorems for ease of reading introducing the definition of $(S,\alpha, \beta)$ clusterable graphs and theorem 1 for such graphs. The value of $\epsilon$ (reworded as $\beta$ in new formulation) is a property of the graph and not the hash function. It affects the quality of ordering, as mentioned in theorem 1, for all similarities and their corresponding hash families $(S, \mathcal{H})$ including Jaccard similarity and Minhash family of hash functions.

References

[1] M. Koohi Esfahani, P. Kilpatrick and H. Vandierendonck, "Locality Analysis of Graph Reordering Algorithms," 2021 IEEE International Symposium on Workload Characterization (IISWC), Storrs, CT, USA, 2021, pp. 101-112, doi: 10.1109/IISWC53511.2021.00020.

We thank the reviewer for recognizing the strengths of the paper in terms of the novelty of the idea and the effectiveness of the proposed method. We address the reviewer's concerns and questions below. The reviewer asked for two sets of additional experiments. Given the time constraints and the other experiments we had been working on, we have not been able to run them, but we will add them to the final version of the paper. If the reviewer's concerns are sufficiently answered, we urge the reviewer to reconsider their score. If not, we would be happy to answer further clarifications.

1. Structure of the theoretical results.

Sorry for the confusion. For Jaccard similarity which we use in HashOrder, the hash family assumed in Lemma 1 always exists since for any given $\alpha$ and $R$ such that $R > \alpha$, MinHash is a $(R, \alpha, R, \alpha)$-sensitive family. We have improved the presentation of the definitions and theorems (marked in blue) in the paper, but the theoretical result remains unchanged.

2. Discussion on "Finding exact and approximate block structures for ILU preconditioning."

The paper by Saad, Yousef explores reordering sparse matrices to form block structures for accelerating block ILU factorization. Although it focuses on sparse matrix reordering, to the best of our understanding, its objective is to achieve compression of the original matrix and reducing the number of fill-ins, which is different from the graph reordering objective of reducing the number cache misses. The two reordering problems are distinct from each other and require dedicated solutions. We will add the discussion and the experiments to the final paper.

3. The experimental results are based only on the authors' implementation.

In fact, we do use official implementations as much as possible. Our implementation extends the C implementation used in [2], which contains the official implementation of methods such as DBG, HubSort, HubCluster, SortIn and SortOut. As we have pointed out in the paper, we use the Ligra framework for running graph processing workloads and DGL for GNN workloads. We use the official implementation of RCM from the scipy package for the GNN experiments. Also, our experimental findings on reordering time and speedup of different methods are consistent with previous works.

4. The workloads largely seem to be based on repeated SpMV and SpMM.

While many workloads are related to SpMV/SpMM kernels, the range of graph analysis tasks are wide and many are difficult if not impossible to be reduced to SpMV or SpMM. For example, graph-based near-neighbor-search systems can be accelerated through reordering [1], but their searching process cannot be easily reduced to SpMV or SpMM. Moreover, many GNN data samplers cannot be efficiently implemented through SpMV or SpMM. In our paper, we evaluate a wide range of representative graph workloads, which are consistent with previous works [2]. Having said that, we are still happy to perform additional experiments and report them in the final paper.

References

[1] Coleman, Benjamin, et al. "Graph Reordering for Cache-Efficient Near Neighbor Search." Advances in Neural Information Processing Systems 35 (2022): 38488-38500.

[2] P. Faldu, J. Diamond and B. Grot, "A Closer Look at Lightweight Graph Reordering," 2019 IEEE International Symposium on Workload Characterization (IISWC), Orlando, FL, USA, 2019, pp. 1-13, doi: 10.1109/IISWC47752.2019.9041948.