Hypergraph-based locality-enhancing methods for graph operations in Big Data applications

Abstract

The need for speeding up data analytics increases inevitably due to the need for extracting valuable information from social media, data generated by smart devices with sensors, patterns of people’s communications over the web, items viewed and bought by global-scale customers, cloud applications, etc., all of which take part in the “Big Data.” Such kind of interaction data is very well represented as sparse graphs to enable the graph analytics, which requires efficient underlying kernels. The breadth-first search (BFS)-based traversal is a commonly used kernel in graph algorithms such as the betweenness centrality algorithm for centrality analysis. In this work, we focus on parallel BFS operations and propose hypergraph-based combinatorial models that aim at reducing cache misses and hence exploiting data locality during the parallel BFS operations. Our models are based on finding new vertex visit orders so that locality in accessing the data associated with vertices is exploited. Experiments on graphs arising in a wide range of applications show that our proposed models achieve on average 9% performance improvement in the CPU-based Ligra data analytics framework.

Keywords

Big Data graph analytics graph traversal betweenness centrality breadth-first search data locality hypergraph

1. Introduction

Centrality analysis is widely used for modeling various entities (such as virus infection spread, package delivery, and telecommunications) (Borgatti, 2005), identifying influencers in legitimate or criminal organizations (Morselli and Roy, 2008), spreading reach in a social network (Wu et al., 2012), root cause analysis (Milroy et al., 2019), intelligent transportation systems (Puzis et al., 2013), bibliometric analysis (Aliyev et al., 2019), and for extracting valuable information from various kinds of data such as hyperlink network (Nam et al., 2014), friendship network (Catanese et al., 2012), online sales data (Ding et al., 2018), and user interaction graphs (Ediger et al., 2010). Efficiently analyzing such data using graph theoretical algorithms constitutes an important class of problems in “Big Data” research. Many research efforts are made towards consolidating “Big Data” applications with the underlying high performance computing (HPC) platforms. For this purpose, plenty of graph analytics frameworks such as GraphMat (Sundaram et al., 2015), Ligra (Shun and Blelloch, 2013), and Gunrock (Wang et al., 2016) with novel data structures and parallelism strategies are proposed to become closer to the limits of the underlying hardware.

One of the principal optimizations in HPC is reducing data movement via exploiting data locality on multicore CPUs (Borkar and Chien, 2011; Unat et al., 2017; Akbudak and Aykanat, 2017; Zhang et al., 2018). In this work, we propose hypergraph-based models for finding a vertex visit order that enhances the data locality via decreasing cache misses during kernel graph operations. We focus on betweenness centrality (BC), which uses the breadth-first search (BFS)-based traversal algorithm as the kernel operation. Our proposed methods can also be applied to many other graph theoretical algorithms, which inherit the computation pattern of accessing neighbors of vertices during the execution of the algorithm. We validate the proposed methods on a wide range of graph data from various applications using the state-of-the-art graph processing framework Ligra (Shun and Blelloch 2013) for multicore CPUs.

The rest of the paper is organized as follows: Section 2 presents the related work on graph analytics frameworks and methods for exploiting data locality. Section 3 summarizes the novel contributions of this work. The background information about the BFS and BC algorithms are given in Section 4. Implementations of these two algorithms in Ligra and the data locality characteristics of the kernel operations in them are presented in Section 5. The proposed reordering methods are presented in Section 6. Section 7 presents an experimental analysis of the proposed and existing reordering methods. The paper is concluded and the future work is mentioned in Section 8.

2. Related work

2.1. Graph analytics on various architectures

There are several tools for graph processing on GPUs such as MapGraph, CuShua, and Gunrock. MapGraph (Fu et al., 2014) is a programming framework that provides a vertex-centric abstraction for graph algorithms. CuSha (Khorasani et al., 2014) is a vertex-centric framework based on novel data structures (G-Shards and concatenated windows) instead of the compressed sparse row (CSR) format commonly used for sparse matrices. Gunrock (Wang et al., 2016, 2017) provides frontier-centric framework for expressing graph algorithms. The frontiers in Gunrock can be either vertices or edges.

Galois, GraphChi, Grace, Ligra, GraphMat, and GraphIt are among the frameworks which target only shared-memory CPU architectures. Galois (Kulkarni et al., 2007, 2009; Nguyen et al., 2013a) is a C++ framework that provides a domain-specific language (DSL) for easily implementing graph operations in parallel. GraphChi (Kyrola et al., 2012) is an out-of-core framework based on parallel sliding windows method to process large graphs. Grace (Prabhakaran et al., 2012) combines several optimizations depending on the graph structure. One of the proposed optimizations in Grace to exploit data locality is a simple graph partitioning algorithm based on grouping adjacent vertices greedily to find a vertex reordering. Ligra (Shun and Blelloch, 2013) adopts the hybrid BFS approach proposed in Beamer et al. (2012) and provides BC, graph radii estimation, connected components (CC), PageRank, and single-source shortest paths (SSSP) algorithms. In the GraphMat (Sundaram et al., 2015) framework, graph algorithms are represented as sparse matrix operations such as sparse matrix-vector multiplication (SpMV). GraphIt (Zhang et al., 2018) is another framework providing a DSL for high performance graph operations.

For the distributed-memory systems, there are plenty of tools such as, Neo4j (2007), Combinatorial BLAS (Buluç and Gilbert, 2011), Apache Giraph (2012), GraphX (Xin et al., 2013), Parallel Boost Graph Library (PBGL) (Gregor and Lumsdaine, 2005), Pegasus (Kang et al., 2009, 2011) Pregel (Malewicz et al., 2010), Knowledge Discovery Toolbox (Lugowski et al., 2012), distributed GraphLab (Low et al., 2012), PowerGraph (Gonzalez et al. 2012), PowerGraph’s optimized version PowerLyra (Chen et al., 2015), and GraphPad (Anderson et al., 2016). Neo4j, Giraph, GraphX, and Pegasus use the MapReduce framework. GraphPad and Combinatorial BLAS use the Scalable Universal Matrix Multiplication Algorithm (SUMMA) (Van De Geijn and Watts, 1997) for the distributed sparse matrix-matrix multiplication (SpGEMM) operation. For the PowerGraph framework, methods for efficient processing of graphs with highly skewed power-law degree distributions are proposed in Li et al. (2018). In Buluc and Madduri (2013), hypergraph partitioning is used to minimize the total communication volume during distributed-memory BFS operations.

Except Grace (Prabhakaran et al., 2012), the above-mentioned works do not consider the structure of the underlying graph for exploiting data locality. In this work, we propose reordering methods that aim at finding a better vertex visit order for exploiting data locality during graph operations.

2.2. Data locality

Beamer et al. (2015b) compare performances of PageRank, BC, SSSP, and CC algorithms provided by Galois, Ligra, and GAP Benchmark Suit (Beamer et al., 2015a) in terms of various metrics such as utilized memory bandwidth, cache misses, and branch misprediction rates. It is mainly concluded that graph algorithms do not fully utilize the memory bandwidth of the system so decreasing memory access will improve the applications’ performance. Another conclusion in Beamer et al. (2015b) is the importance of exploiting intra-socket locality to decrease NUMA effects.

Gorder (2016) proposed in Wei et al. (2016) aims at exploiting data locality in CPU caches. The effectiveness of Gorder is tested on kernels such as depth-first search (DFS), BFS, CC, SSSP, PageRank, and graph diameter. Gorder is also commonly used (e.g., Lakhotia et al., 2017; Balaji and Lucia, 2018; Faldu et al., 2019; Lee et al., 2019; Wang et al., 2019; Faldu et al., 2020) to exploit locality. Arai et al. (2016) propose a parallel hierarchical bottom-up vertex matching algorithm named Rabbit (2016) to exploit locality through reordering tightly connected vertices in a graph nearby. Lakhotia et al. (2017) propose an ordering method similar to Gorder with a sorted list data structure instead of the max heap in the Gorder algorithm. Lakhotia et al. (2020) propose a method that assigns the vertices according to their indices into fixed-size bins and performs bin-wise updates instead of single-vertex updates during graph operations to decrease data movement. Barik et al. (2020) investigate the performance relation between locality-enhancing reordering methods and metrics defined on the graphs.

For PageRank computations, Beamer et al. (2017) propose to store blocks of contributions (propagations) to vertex weights in separate bins in the first phase and to accumulate these contributions in bins for updating vertex weights in the second phase. Since the output vertex weights are accessed in a blocked manner in the accumulation phase, spatial locality is exploited. Zhang et al. (2017) propose a block-based PageRank algorithm and reordering high out-degree vertices consecutively so that hot vertices reside in higher cache levels in order to exploit data locality. Balaji and Lucia, 2018 study graph reordering methods and compares them in terms of amortization of methods’ overheads.

Faldu et al. (2019) use Ligra to show effectiveness of their proposed reordering algorithm Degree-Based Grouping (DBG) (DBG, 2019). In DBG, there are a fixed number of bins for degree ranges. Vertices are assigned to these bins according to their degrees. Hence, each bin contains vertices with close degrees. The structure of the graph is not considered. Lee et al. (2019) propose Neighborhood Ordering (Norder) for disk-based systems. Norder starts from the node with the highest in-degree and reorders vertices according to a BFS traversal with a limited distance from the currently active node. Faldu et al. (2020) propose a cache management framework that protects frequently used high-degree vertices thrashed from the cache to provide temporal locality in accessing such vertices.

The methods proposed in this work use hypergraph models, which encapsulate the relation among multiple vertices, whereas the above-mentioned works consider either only degrees without the graph topology or only relations between vertex pairs. The superiority of modeling power of hypergraphs over graphs (Catalyurek and Aykanat, 1999) leads to better performance modeling of graph-based applications on today’s highly parallel CPUs with deep cache hierarchies.

3. Contributions

This work is the first step toward showing the applicability of hypergraphs to model irregular graph-based operations (e.g., BFS) for exploiting data locality in the deep cache hierarchy of a multicore CPU system. We first present the data locality characteristics of kernel graph operations. Then we propose two hypergraph-based models that enhance the data locality. As an empirical contribution, a wide set of graphs arising in various applications is tested on the Ligra framework to validate the effectiveness of the proposed hypergraph models and the reordering methods. These contributions are not limited to the BFS algorithm and the Ligra framework. Any other graph algorithms and graph analytics frameworks that have irregular accesses due to the graph structure will benefit from the proposed reordering methods depending on their locality characteristics.

4. Background

4.1. Breadth-first search (BFS)

Let G = (V, E) denote a directed unweighted graph, where V is the set of vertices and E is the set of directed edges. The text-book implementation of BFS is presented in Algorithm 1. The BFS algorithm starts traversing a given graph G from a given source vertex s ∈ V and explores direct neighbors of this vertex (lines 8–11). The set of active vertices that currently explore other vertices is called frontier, which is denoted as F. After all vertices in the current frontier are processed, the vertices in the next frontier, F_next, become active and start exploring. The BFS algorithm computes and returns a tree rooted at s (line 13).

The BFS-based graph traversal is an important kernel operation (Mattson et al., 2013; Murphy et al., 2010) in Big Data analytics. Several graph analytics algorithms such as finding shortest paths (Cherkassky et al., 1996), k-hop reachability (Cheng et al., 2012), and BC (Brandes, 2001; Bader and Madduri, 2006; Madduri et al., 2009) iteratively use this kernel operation. According to the requirements of the top-level application, one or more arrays associated with vertices can be irregularly accessed at lines 9 and 10 of Algorithm 1 depending on the graph structure. This type of accesses might cause performance bottleneck due to lack of data locality.

4.2. Betweenness centrality (BC)

The BC algorithm (Freeman, 1977) is used to find vertices bridging one part of a graph to another. In other words, BC finds the number of shortest paths passing over a vertex. The centrality rankings of vertices relate to the power of controlling the communication in the network represented by the graph.

5. Data locality in graph computations

We select Ligra (Shun and Blelloch, 2013; Ligra, 2014) as a sample framework in this work since it is widely accepted as a state-of-the-art tool in many graph analytics works (Balaji and Lucia, 2018; Nguyen et al., 2013b; Wang et al., 2016, 2017, 2019; Zhang et al., 2017, 2018). In this section, we focus on the kernel operations in parallel BFS and BC implementations in Ligra and their performance characteristics in terms of data locality. The discussions in this section about data locality are also valid for other frameworks (Galois, Boost Graph Library, etc.) based on traversing vertices/edges according to neighborhood information.

Ligra provides both pull- and push-based schemes as also discussed in Besta et al. (2017). In the push-based scheme, out-neighbors of vertices are directly updated using writes, whereas in the pull-based scheme, in-neighbors are read. Another optimization technique in Ligra is that the framework selects the best edge mapping strategy (either sparse or dense) according to the active frontier. In Ligra, push-based scheme is used for sparse edge mapping and pull-based scheme is used for dense edge mapping. It is reported in Shun and Blelloch (2013) that the push-based scheme for dense edge mapping is more efficient for only PageRank and Bellman-Ford algorithms so the push-based scheme for dense edge mapping is omitted in the following discussions and analysis.

Algorithm 2 presents the mapping procedures provided by the Ligra framework for implementing efficient parallel graph algorithms. VertexMap (U, f) applies a given function f to all vertices in set U. EdgeMap (G, U, f, c) applies a given function f to all vertices satisfying the condition c and neighbor to vertices in set U. If U is small enough, push (write)-based edge-map procedure (i.e., EdgeMapSparse) is called for efficiency, otherwise pull (read)-based procedure (i.e., EdgeMapDense) is called. Aⁱⁿ(v) at line 5 of EdgeMapDense denotes the in-neighbors of vertex v. That is Aⁱⁿ(v) = {r: < r, v > ∈ E}, where $< r, v >$ denotes a directed edge from vertex r to v. A^out(v) at line 4 of EdgeMapSparse denotes the out-neighbors of vertex v. That is A^out(v) = {r: < v, r > ∈ E}. Consequently, A(v) = Aⁱⁿ(v) ∪ A^out(v).

Both spatial and temporal localities are feasible at line 3 of VertexMap in Algorithm 2. Both types of localities can be exploited if vertices in V, which are commonly processed together, have consecutive or close indices.

Only spatial locality is feasible and inherently exploited in checking condition at line 4 of EdgeMapDense in Algorithm 2 since all vertices are accessed consecutively. Both spatial and temporal localities are feasible at lines 7 and 9 since vertices are irregularly accessed. Spatial locality can be exploited if in-neighbors (r’s) of the currently processed vertex (v) have consecutive or close indices. Temporal locality can be exploited if in-neighbors of the consecutively processed vertices are common. Both spatial and temporal localities are feasible at lines 5 and 6 of EdgeMapSparse in Algorithm 2 since vertices are irregularly accessed. Both types of localities can be exploited if the above-mentioned conditions are satisfied for the out-neighbors (v’s).

The above-mentioned locality characteristics of the mapping functions rely on accessing arrays directly associated with vertices, that is, each associated array has the same index as the vertices have. Ligra uses the BC algorithm proposed by Brandes (2001). For the sake of completeness, we present the BFS and BC implementations in Ligra as Algorithms 3 and 4, respectively. Algorithm 4 presents the betweenness centrality computation from a single root vertex s. This algorithm is repeated for randomly selected vertices to compute approximate centrality rankings of all vertices. As seen in Algorithms 3 and 4, VertexMap and EdgeMap rely on accessing parent, visited, numPaths, and dependencies arrays associated with vertices. Visited and dependencies arrays respectively store bits and floating-point numbers; parent and numPaths arrays store integers. The sizes of elements in each array have a significant impact on the performance. Visit function used by VertexMap in Algorithm 4 accesses only a bit array. Hence, the overall kernel time is expected to be small and locality enhancements might not be significant.

SetParent and IfParentNotSet functions used by EdgeMap in Algorithm 3 access parent array. UpdatePaths and UpdateDependencies functions used by EdgeMap in Algorithm 4 access numPaths and dependencies arrays. The element update operations (read and write) in SetParent, UpdatePaths, and UpdateDependencies have more impact on the performance with respect to only read operation. Especially the latter two functions are expected to take most of the execution time since they perform more operations and data accesses than the condition checking functions perform. They are also expected to benefit from the locality enhancements in updating the above-mentioned arrays.

6. Hypergraph-based reordering methods

We propose hypergraph models to encapsulate the temporal locality characteristic of EdgeMap kernel operation presented in Section 5 employed by analytics algorithms running on a given directed graph G = (V, E). Figure 1 displays a sample EdgeMap operation with an active frontier having three vertices colored in gray and their unvisited out-neighbors colored in white.

Let Hⁱⁿ = (X, N) be a hypergraph (Berge, 1984), where X is the set of vertices and N is the set of nets connecting vertices in X. In the proposed hypergraph model Hⁱⁿ, there exists a vertex x_i ∈ X for each vertex v_i ∈ V. During the execution of EdgeMap, each vertex in v ∈ V causes update of array elements associated with the vertices u ∈ A^out(v). A net n_u represents such updates and hence n_u ∈ N is connected to pins (n_u) = {x_j ∈ X: v_j ∈ Aⁱⁿ(u), u ∈ V} ∪ {x_u} in the proposed hypergraph model Hⁱⁿ. Note here that, u ∈ A^out(v) ⇔ v ∈ Aⁱⁿ(u). A net in Hⁱⁿ represents the multiway relation between a vertex and its in-neighbors in G. Nets and vertices in Hⁱⁿ are assigned unit weights. Figure 2 displays the hypergraph model Hⁱⁿ for the EdgeMap operation presented in Figure 1.

We also propose a dual hypergraph model H^out which has a vertex x_i ∈ X for each vertex v_i ∈ V and a net n_u ∈ N connected to pins (n_u) = {x_j ∈ X: v_j ∈ A^out(u), u ∈ V} ∪ {x_u}. A net in H^out represents the multiway relation between a vertex and its out-neighbors in G. Nets and vertices in H^out are assigned unit weights. Figure 3 displays the hypergraph model H^out for the EdgeMap operation presented in Figure 1.

Temporal and spatial localities can be achieved by clustering vertices in X that share common nets in N and reordering these vertices closely. The clustering of vertices in Hⁱⁿ aims at increasing temporal reuse of elements of arrays associated with the vertices within each frontier. If vertices connected by common nets are partitioned into smaller groups, spatial locality will be exploited by H^out. As a different point of view, in Hⁱⁿ, vertices that have common children are clustered so that locality in accessing these children is exploited. In H^out, vertices that have common parents are clustered so that locality in accessing these vertices is exploited.

A K-way partition $Π (X) = {X_{1}, \dots, X_{K}}$ on vertices of the proposed hypergraph models Hⁱⁿ and H^out is directly decoded as a K-way partition $Π (V) = {V_{1}, \dots, V_{K}}$ on vertices of G. Π(V) is decoded as a partial reordering of elements of parent, visited, numPaths, and dependencies arrays mentioned in Section 5 as follows: The array elements corresponding to the vertices in $V_{k + 1}$ are reordered after the elements corresponding to the vertices in $V_{k}$ . Figure 4 shows the decoding of the two-way partitioning of Hⁱⁿ and H^out given in Figures 2 and 3 as a partial reordering.

Π(X) is also decoded as a partition $Π (N) = {N_{1}, \dots, N_{K}, N_{c u t}}$ on the nets of the proposed hypergraph models Hⁱⁿ and H^out. Here, each net $n \in N_{c u t}$ connects at least two vertices that are in separate parts. Such nets in $N_{c u t}$ are said to be cut and the remaining uncut nets are said to be internal. The set of parts that contain vertices connected to a cut net n is denoted as parts(n).

A brief insight on how the proposed models achieve locality can be given as follows: A net n_u in Hⁱⁿ decodes the access to vertex v_u by its in-neighbors. Given a partition of Hⁱⁿ, an internal net n_u connected to the vertices in pins (n_u) corresponds to possible reuse of v_u ∈ V while accessed by its in-neighbor vertices in {v_j: x_j ∈ pins (n_u)\x_u}. A cut net n_u connected to the vertices in pins (n_u) corresponds to at most |parts (n_u)| cache misses while accessing v_u ∈ V by its in-neighbor vertices in {v_j: x_j ∈ pins (n_u)\x_u}. For example, in Figure 2, the internal net n₄ represents the accesses to vertex v₄ ∈ G by vertices v₁ and v₃ in the current frontier. Since x₁ and x₃ are in the same part, v₁ and v₃ have a higher possibility of being stored and hence processed closely as seen in Figure 4. As a result, an extra cache miss while accessing v₄ will be avoided and the array elements corresponding to v₄ will be reused. The cut net n₇ represents the accesses to v₇ by vertices v₂ and v₃. Since x₂ and x₃ are in separate parts, accessing v₇ twice will probably cause one extra cache miss while accessed by v₂ and v₃.

A net n_u in H^out decodes the access to out-neighbors of v_u when v_u starts exploring. Given a partition of H^out, an internal net n_u connected to the vertices in pins (n_u) corresponds to possible reuse of cache lines containing out-neighbor vertices in {v_j: x_j ∈ pins (n_u)\x_u}. A cut net n_u connected to the vertices in pins (n_u) corresponds to at most |parts (n_u)| cache misses while accessing out-neighbor vertices in {v_j: x_j ∈ pins (n_u)\x_u}. For example, in Figure 3, the internal net n₁ represents the accesses to vertices v₄, v₈ ∈ G in the current frontier. Since x₄ and x₈ are in the same part, v₄ and v₈ have higher possibility of being stored in the same cache line and reused as seen in Figure 4. As a result, an extra cache miss while processing v₁ will be avoided. The cut net n₂ represents the accesses to vertices v₅, v₆, v₇, and v₉. Since x₇ is in a separate part, at least one extra cache miss will occur while accessing v₇ and the cache line containing v₅, v₆, and v₉ is expected to be reused.

The K value impacts the quality of clustering in terms of data locality. Temporal locality can be achieved by using relatively smaller K values. However, increasing the chance of spatial locality may require large enough K values so that the vertices in a part are clustered within a cache line. This fact can also be observed in Figure 4. Partitions on the vertices of the two hypergraph models Hⁱⁿ and H^out may be the same and achieve the common goal of exploiting both types of data locality.

7. Experiments

7.1. Data set

The effectiveness of the proposed reordering methods is empirically verified on 17 graphs arising in various applications. The adjacency matrix representations of these graphs are obtained from the University of Florida Sparse Matrix Collection (Davis and Hu, 2011). Table 1 shows the properties of graphs, which are sorted alphabetically by their names. Brief information about each graph is given in the “Kind” column. The amount of pattern symmetricity of the adjacency matrix representation of each graph is given in the “Sym” column.

Table 1.

The properties of graphs and K values used in partitioning.


					Statistics on vertex degrees
Graph	Kind	Sym (%)	\|V\|	\|E\|	Avg	Maxⁱⁿ	Stdⁱⁿ	CVⁱⁿ	Max^out	Std^out	CV^out	K
amazon0302	Co-purchasing network	54	262,111	1,234,877	4.7	420	5.7	1.2	5	0.0	0.0	602
amazon0505	Co-purchasing network	55	410,236	3,356,824	8.2	2760	15.3	1.9	10	3.0	0.4	1639
amazon0601	Co-purchasing network	56	403,394	3,387,388	8.4	2751	15.2	1.8	10	2.6	0.3	1653
analytics	Data analytics problem	100	303,813	1,752,374	5.8	25,665	131.4	22.8	25,665	131.4	22.8	551
coAuthorsCiteseer	Citation network	100	227,320	1,628,268	7.2	1372	10.6	1.5	1372	10.6	1.5	397
coAuthorsDBLP	Citation network	100	299,067	1,955,352	6.5	336	9.7	1.5	336	9.7	1.5	477
coPapersCiteseer	Citation network	100	434,102	32,073,440	73.9	1188	101.3	1.4	1188	101.3	1.4	2000
email-EuAll	email network	26	265,214	418,956	1.6	7631	36.5	23.1	929	9.9	6.3	205
germany_osm	Road network	100	11,548,845	24,738,362	2.1	13	0.0	0.0	13	0.0	0.0	2000
great-britain_osm	Road network	100	7,733,822	16,313,034	2.1	8	0.0	0.0	8	0.0	0.0	2000
HTC_336_9129	Power network	100	226,340	657,082	2.9	7393	31.9	11.0	7393	31.9	11.0	270
smallworld	Random network	100	100,000	999,996	10.0	17	1.0	0.1	17	1.0	0.1	244
sx-askubuntu	User-question interaction	33	159,316	544,621	3.4	1953	16.3	4.8	4965	43.4	12.7	291
vsp_c-60_data_cti_cs4	Random network	100	85,830	482,160	5.6	2207	10.2	1.8	2207	10.2	1.8	117
web-Stanford	Hyperlink graph	28	281,903	2,312,497	8.2	38,606	166.3	20.3	255	11.3	1.4	1129
wiki-Talk	User-user interaction	14	2,394,385	5,021,410	2.1	3311	12.2	5.8	100,022	99.9	47.6	2000
wiki-talk-temporal	User-user interaction	22	1,140,149	3,130,742	2.7	3315	16.8	6.1	141,883	168.6	61.4	1616

In Table 1, “Avg,” “Max,” “Std,” and “CV” columns, respectively, show the average, the maximum, the standard deviation, and the coefficient of variation of number of edges per vertex. “Max”, “Std,” and “CV” columns with “ⁱⁿ” superscript denote the statistics for incoming edges, whereas columns with “^out” superscript denote the statistics for outgoing edges. Max and Std values give insight when one graph is considered, whereas CV can be used for comparison of different graphs since CV is defined as the ratio of Std to Avg. The higher Std and CV values indicate higher amount of irregularity in the structure of the graphs (e.g., wiki-Talk), whereas the lower Max, Std, and CV values indicate a regular structure (e.g., amazon0302).

The last column of Table 1 shows the number of parts K used in partitioning for the proposed methods. The number of parts for each graph is calculated with respect to the L1 cache size of the system and the number of edges of the graph. K is set to 2000 as its maximum value to limit the partitioning time for large graphs.

7.2. System setup for experiments

Experiments are performed on a system with dual Intel Xeon E5-2680 v4 CPUs clocked at 2.4 GHz. Each CPU has 14 cores sharing 35 MB 20-way set associative L3 cache. Each core has 32 KB 8-way set associative L1 data and 256 KB 8-way set associative L2 cache. The system runs Ubuntu 16.04. All codes are compiled with GCC 5.4 using -O3 and -march=native flags for optimizing their performances.

7.3. Preprocessing framework

The multilevel hypergraph partitioner PaToH (Catalyurek and Aykanat, 1999) is used for partitioning the proposed hypergraph models Hⁱⁿ and H^out of each graph in the experimental data set. For each proposed method, PaToH is run three times with different seeds because it uses randomized algorithms. Among these three partitionings, the best-performing instance is selected for reporting. The proposed methods mainly aim at clustering vertices with similar connectivity and they do not depend on the part weights. Hence, the final imbalance ratio parameter of PaToH is set to 10%, which corresponds to a rather loose constraint on the weights of vertex parts.

The multilevel hypergraph partitioning framework in PaToH has coarsening, initial partitioning, and refinement phases. For the coarsening phase, Heavy Connectivity Clustering (PATOH_CRS_HCC) is used. This method tries to assign a vertex to the cluster with the maximum number of shared nets among the vertex and the cluster. PaToH is used with the set of parameters suggested for shorter partitioning times and acceptable partitioning quality. The connectivity-1 metric is used since the cost of extra cache misses is related to the number of parts that a net connects as described in Section 6.

7.4. Graph analytics framework

Ligra (Shun and Blelloch, 2013) is selected for graph analytics. OpenMP is used for enabling parallelism inside Ligra. The number of source vertices is set to 10% of the vertices in each graph, and the same set of randomly selected source vertices is used for all experiments involving a specific graph. The reported times are averaged over five runs of a centrality computation after a warm-up run. Arithmetic average is used throughout the paper. The number of threads employed by Ligra is set to the total number of hyperthreads, which is equal to twice number of physical cores on the system since shorter times are observed when hyperthreading is used.

7.5. Baseline methods

Gorder (2016), DBG (2019), the Reverse Cuthill-McKee (RCM) algorithm proposed by Cuthill and McKee (1969), nested dissection ordering (METIS ND) and graph partitioning (METIS GP) developed by Karypis and Kumar (1998), and the Rabbit (2016) ordering are used as the baseline methods for reordering the original graphs. RCM and METIS are commonly used for enhancing locality in graph applications (Wei et al. 2016; Barik et al. 2020). Gorder is used with the default value of 5 for the window size. DBG integrated into the Ligra framework is used with the default parameters. RCM in the Boost Library v1.58 is used for an efficient C++ implementation. The number of parts is set to 32 for METIS GP, and default parameters are used for METIS as suggested in Barik et al. (2020).

7.6. Performance analysis of kernel operations

We first present breakdown of overall time for the BC operation on the original graphs without reordering in Table 2. For the first and second phases of the BC algorithm given in Algorithm 4, the VertexMap, EdgeMapDense, and EdgeMapSparse columns contain times in terms of percentages of the overall BC times for each graph.

Table 2.

For original ordering, BC time breakdown into kernel operations (i.e., VertexMap, EdgeMapDense, and EdgeMapSparse) in terms of percentages of the overall time. Significant amount of time is spent in EdgeMap so performance improvement in EdgeMap operations is expected to have a higher impact on the overall run time.

	The first phase			The second phase
	VertexMap	EdgeMap		VertexMap	EdgeMap
Graph	(%)	Dense (%)	Sparse (%)	(%)	Dense (%)	Sparse (%)
amazon0302	5	29	15	7	29	11
amazon0505	4	28	12	7	34	8
amazon0601	4	32	11	6	34	8
analytics	2	34	10	2	38	5
coAuthorsCiteseer	5	29	13	6	31	10
coAuthorsDBLP	4	34	9	5	36	6
coPapersCiteseer	2	37	9	3	38	6
email-EuAll	3	30	8	4	35	7
germany_osm	7	0	48	10	0	30
great-britain_osm	9	0	45	11	0	32
HTC_336_9129	3	40	5	4	39	3
smallworld	4	33	10	5	33	6
sx-askubuntu	4	31	10	5	34	7
vsp_c-60_data_cti_cs4	5	33	11	5	33	7
web-Stanford	7	14	25	10	16	24
wiki-Talk	2	33	3	5	41	3
wiki-talk-temporal	2	32	5	4	41	4

Average	4	28	15	6	30	10

In Table 2, any EdgeMapDense operation is not performed for the road networks since the maximum vertex degrees for germany_osm and great-britain_osm are very small (i.e., 13 and 8, respectively) as seen in Table 1. The EdgeMapDense operations in both phases take 58% of overall run time on average, where 25% of the overall time is spent for the sparse version. Conforming to the discussion in Section 5, VertexMap function takes considerably smaller time, that is, 10% on the overall average, with respect to the two edge mapping functions. Hence, the performance improvement in the EdgeMap operations is expected to have the highest impact on the overall run time.

7.7. Performance impact of reordering methods

Table 3 displays the performance comparison of the existing methods and the proposed hypergraph-based methods. All values are normalized with respect to the BC time for the original (unordered) graph. The best results are shown in boldface. The overall average results are presented in the last row of the table. The best performance for either Hⁱⁿ or H^out is reported for each graph since the effectiveness of PaToH highly depends on the connectivity pattern of vertices in terms of in and out edges of the graph and each centrality computation generally employs both pull- and push-based schemes. Nevertheless, it is experimentally observed that these hypergraph models display relatively close performance in general. Also, finding the reasons behind the superior performance of one model over the other for each graph necessitates detailed analysis of all kernel operations using cache simulators and hence it is out of the scope of this work.

Table 3.

The performance effect of reordering methods in terms of run time of the centrality algorithm in Ligra. Run times are normalized w.r.t. the original (unordered) case. A lower value means shorter run time. The best results are shown in boldface. As seen in the table, on the overall average, the proposed methods respectively achieve 9% and 4% shorter centrality computation times w.r.t. the unordered case and the best existing method METIS GP.

	Existing methods						Proposed methods
Graph	Gorder	DBG	RCM	METIS ND	METIS GP	Rabbit	Proposed methods
amazon0302	1.19	1.09	1.14	1.06	1.00	1.07	0.97
amazon0505	0.93	0.88	1.02	0.97	0.96	0.94	0.86
amazon0601	0.97	0.96	0.96	0.97	0.89	0.86	0.88
analytics	0.99	1.00	0.93	1.03	0.83	0.97	0.88
coAuthorsCiteseer	0.95	0.93	0.93	0.91	0.93	0.86	0.92
coAuthorsDBLP	0.94	0.94	1.00	0.93	0.94	0.84	0.88
coPapersCiteseer	0.67	0.93	1.05	0.94	0.97	1.09	0.65
email-EuAll	0.98	1.03	0.99	1.07	0.98	0.94	0.95
germany_osm	1.33	1.08	1.36	0.98	0.95	0.95	0.94
great-britain_osm	1.22	1.03	1.25	1.02	0.99	0.99	0.98
HTC_336_9129	1.05	1.07	1.06	1.10	1.04	1.11	0.98
smallworld	0.98	1.10	1.00	0.98	0.94	0.97	0.92
sx-askubuntu	1.06	1.05	1.03	0.95	0.96	0.99	0.96
vsp_c-60_data_cti_cs4	0.94	0.93	0.91	0.95	0.95	0.99	0.91
web-Stanford	1.00	1.02	1.00	0.95	0.93	0.93	0.93
wiki-Talk	1.06	1.03	0.98	1.06	0.94	0.94	0.94
wiki-talk-temporal	1.00	0.99	0.98	1.00	0.90	0.89	0.96

Average	1.02	1.00	1.03	0.99	0.95	0.96	0.91

The comparison of the first two columns of Table 3 confirms the superiority of DBG over Gorder. DBG, RCM, and METIS ND are considerably less performant than METIS GP, Rabbit, and the proposed methods. Regarding the overall average performance, the inferior performance of RCM and METIS ND can be attributed to the very loose relation between their optimization objectives and exploiting locality. RCM tries to minimize the bandwidth of the adjacency matrix, and METIS ND tries to find vertex separators between two parts of a graph. METIS GP and Rabbit achieve comparable performance. Rabbit has more best-performing instances, whereas METIS GP is slightly better than Rabbit in the overall average. When the hypergraph-based methods are compared against Rabbit and METIS GP, the proposed methods perform considerably better in the overall average and have significantly more best-performing instances. The proposed methods achieve up to 35% performance improvement with respect to the original order and 9% improvement on the overall average. Rabbit and METIS GP utilize vertex matching based on only two-way edge connectivity for finding clusters and coarsen the input graph. The proposed hypergraph-based methods are capable of modeling multi-way locality relations between vertices and hence perform better than the graph-based methods. These results confirm the importance of exploiting locality in accessing data structures during the execution of irregular graph applications.

Table 3 verifies the validity of the proposed methods for graphs with symmetricity values varying from 14% to 100%. For example, the proposed methods achieve 12% improvement for the analytics graph, which is an undirected graph. The proposed methods achieve 12% improvement for amazon0601, which has the highest symmetricity value of 56%, and 6% improvement for wiki-Talk, which has the lowest symmetricity value of 14%.

Table 3 also shows the success of the proposed methods on both regular and highly irregular graphs. The proposed methods achieve 6% improvement for germany_osm, which is a very regular graph with a CV value of zero. In case of irregular graphs, the proposed methods achieve 4% improvement for wiki-talk-temporal, which has the highest CV value of 61.4 and 6% improvement for wiki-Talk, which has the second-highest CV value of 47.6.

7.8. Reordering overhead

Table 4 presents the preprocessing overheads of the existing and proposed methods for all graphs in the data set and overall averages. Each preprocessing time is normalized with respect to the run time of a single centrality computation LigraBC(G, s) in Algorithm 4 on the respective graph. As seen in Table 4, DBG has the lowest preprocessing overhead since it requires only one pass over the set of vertices and edges. As expected, Gorder performs significantly slower than DBG because reordering is performed according to the similarities of vertices in terms of edge connectivity in the graph. RCM yields significantly high overhead for some graphs. This may be attributed to the overhead of finding the peripheral vertex. The overhead of the Rabbit ordering is lower w.r.t. METIS and the proposed methods since it is parallelized and contains only vertex matching step without initial partitioning and refinement. The proposed hypergraph-based methods are slower than METIS GP and Rabbit. However, this overhead can be hidden since the centrality computations are repeatedly performed on the same graph structure. Also, there are many efforts towards efficient hypergraph clustering algorithms (Kumar et al., 2020; Zhou et al., 2006), and these efficient clustering methods can be directly used in the proposed methods.

Table 4.

The reordering overhead of the existing and proposed methods. For each graph, the preprocessing time of each method is divided by the time of a single centrality computation LigraBC(G, s) in Algorithm 4.

	Existing methods						Proposed methods
Graph	Gorder	DBG	RCM	METIS ND	METIS GP	Rabbit	Proposed methods
amazon0302	16.64	0.13	13.21	192.93	29.82	7.05	293.22
amazon0505	47.71	0.14	41.80	17.71	67.53	7.66	858.12
amazon0601	58.34	0.08	24.21	16.53	67.16	10.47	883.24
analytics	51.99	0.28	11,251.15	255.31	126.95	15.72	712.62
coAuthorsCiteseer	49.90	0.15	16.72	191.23	44.21	9.71	496.61
coAuthorsDBLP	63.27	0.24	20.07	15.68	82.11	10.89	826.62
coPapersCiteseer	248.17	0.04	32.50	177.56	67.41	11.05	2106.94
email-EuAll	25.79	0.37	4929.42	837.87	78.22	14.09	296.91
germany_osm	5.44	0.03	11.64	102.17	11.72	2.28	148.48
great-britain_osm	4.09	0.02	7.16	59.31	6.91	1.53	75.39
HTC_336_9129	11.11	0.26	1931.31	135.95	16.38	7.48	160.05
smallworld	51.25	0.61	36.52	367.13	123.19	16.79	744.92
sx-askubuntu	44.33	0.43	797.28	279.22	412.38	18.94	504.60
vsp_c-60_data_cti_cs4	26.55	0.49	14.47	184.15	27.73	7.52	279.86
web-Stanford	17.30	0.05	104.31	170.16	31.96	5.67	441.87
wiki-Talk	126.18	0.13	1833.34	8618.72	403.50	12.19	1668.91
wiki-talk-temporal	114.71	0.17	24,970.91	4300.87	671.41	13.00	4755.23

Average	56.63	0.21	2708.00	936.62	133.45	10.12	897.27

7.9. Performance impact in end-to-end graph analytics application

Table 5 displays end-to-end application speedups, including the reordering times of the existing methods and the proposed hypergraph-based methods for all graphs in the data set. The BC times for the original (unordered) graphs are used to obtain the speedup values. The best speedup values are shown in boldface. The overall average speedups are presented in the last row of the table. As seen in the table, the proposed methods are considerably faster than both METIS GP and Rabbit on the overall average. METIS GP, Rabbit, and the proposed methods achieve the best performance in 2, 5, and 8 instances, respectively. The proposed methods also achieve up to 1.48x speedup w.r.t. the original order without causing any performance degradation for any graph and 1.10x speedup on the overall average.

Table 5.

The performance effect of reordering methods in terms of net speedup of the centrality algorithm in Ligra. The reordering times of the methods are included. The BC times for the original (unordered) graphs are used to obtain the speedup values. A larger value means a larger speedup so the larger the better. The best results are shown in boldface. As seen in the table, on the overall average, the proposed methods achieve 1.10x speedup for the application time including the reordering overhead w.r.t. the unordered case.

	Existing methods						Proposed methods
Graph	Gorder	DBG	RCM	METIS ND	METIS GP	Rabbit	Proposed methods
amazon0302	0.84	0.91	0.91	0.94	1.00	0.94	1.04
amazon0505	1.07	1.13	0.98	1.03	1.04	1.06	1.15
amazon0601	1.02	1.04	1.05	1.03	1.12	1.17	1.13
analytics	1.00	1.00	0.80	0.96	1.20	1.03	1.13
coAuthorsCiteseer	1.05	1.07	1.10	1.09	1.07	1.16	1.07
coAuthorsDBLP	1.06	1.07	1.02	1.07	1.06	1.19	1.13
coPapersCiteseer	1.49	1.08	0.96	1.06	1.03	0.92	1.48
email-EuAll	1.02	0.97	0.88	0.90	1.02	1.06	1.08
germany_osm	0.75	0.93	0.73	1.02	1.05	1.05	1.07
great-britain_osm	0.82	0.97	0.80	0.98	1.01	1.01	1.03
HTC_336_9129	0.96	0.93	0.90	0.91	0.96	0.90	1.05
smallworld	1.01	0.91	1.02	0.98	1.05	1.03	1.04
sx-askubuntu	0.94	0.95	0.95	1.03	1.02	1.01	1.02
vsp_c-60_data_cti_cs4	1.06	1.08	1.10	1.03	1.05	1.01	1.11
web-Stanford	1.00	0.98	1.00	1.05	1.07	1.08	1.06
wiki-Talk	0.94	0.97	1.02	0.91	1.06	1.06	1.07
wiki-talk-temporal	1.00	1.01	0.85	0.97	1.10	1.12	1.02

Average	1.00	1.00	0.94	1.00	1.05	1.05	1.10

7.10. Another graph analytics algorithm: PageRank

This section presents experiments performed with another graph analytics algorithm, PageRank, to show that the validity of the proposed methods is not confined to centrality computations. Table 6 displays the performance comparison of the existing methods and the proposed hypergraph-based methods for the PageRank algorithm in Ligra. All values are normalized w.r.t. the PageRank time for the original (unordered) graph. The best results are shown in boldface. The overall average results are presented in the last row of the table. As seen in the table, the proposed methods are slightly faster than METIS GP and Rabbit on the overall average. Moreover, the proposed methods have more best-performing instances than METIS GP and Rabbit have.

Table 6.

The performance effect of reordering methods in terms of run time of the PageRank algorithm in Ligra. Run times are normalized w.r.t. the original (unordered) case. A lower value means shorter run time. The best results are shown in boldface. As seen in the table, the proposed methods achieve the best performance for 10 out of 17 graphs, and 2% faster than the best baseline method METIS GP on the overall average.

	Existing methods						Proposed methods
Graph	Gorder	DBG	RCM	METIS ND	METIS GP	Rabbit	Proposed methods
amazon0302	1.11	1.04	1.10	0.96	0.88	1.01	0.80
amazon0505	1.08	1.02	1.16	0.94	0.92	0.84	0.84
amazon0601	1.10	1.02	1.22	0.93	0.86	0.83	0.81
analytics	0.77	0.61	0.62	0.86	0.55	0.57	0.57
coAuthorsCiteseer	1.00	1.03	1.06	0.91	0.96	0.90	0.91
coAuthorsDBLP	0.92	0.93	0.98	0.84	0.91	0.79	0.82
coPapersCiteseer	1.16	0.99	1.25	0.98	0.99	1.03	0.97
email-EuAll	0.82	0.79	0.89	1.23	0.76	0.70	0.67
germany_osm	1.17	1.05	1.34	0.91	0.91	0.87	0.90
great-britain_osm	1.18	1.09	1.29	0.95	0.94	0.91	0.93
HTC_336_9129	1.00	0.94	0.99	1.21	0.84	0.95	0.84
smallworld	1.03	1.02	1.05	1.04	0.96	0.98	0.96
sx-askubuntu	1.04	1.08	1.03	1.03	0.93	0.97	0.93
vsp_c-60_data_cti_cs4	0.95	0.91	0.95	0.90	0.87	0.90	0.87
web-Stanford	1.07	0.96	1.04	1.10	0.77	0.81	0.74
wiki-Talk	1.03	1.00	1.09	1.02	1.00	1.03	1.00
wiki-talk-temporal	1.01	0.99	1.07	1.02	0.98	1.01	1.00

Average	1.03	0.97	1.07	0.99	0.88	0.89	0.86

The performance gap between the proposed and the existing methods is less for the PageRank algorithm w.r.t. the BC algorithm when averages in Tables 3 and 6 are compared. This may be attributed to the fact that the BC algorithm randomly accesses four arrays associated with the vertices, as explained in Section 5. In contrast, the PageRank algorithm accesses only one array, which stores the scores. In conclusion, the superiority of the proposed methods is expected to be more significant as the total size of the storage associated with each vertex increases.

8. Conclusion and future work

We present the data locality characteristic of a common graph kernel operation, that is, breadth-first search (BFS) algorithm. Then, we propose hypergraph-based reordering methods for exploiting data locality in graph-based data analytics on CPUs with deep cache hierarchies. The proposed methods aim at clustering vertices that are accessed together so that the data elements associated with vertices that are accessed closely in time by the graph analytics framework remain in higher levels of the system’s memory hierarchy. The experiments on a system with Intel CPUs empirically verify the validity of the proposed methods on graphs arising in a wide range of applications.

An immediate follow-up work is exploiting locality during processing of large graphs requiring hundreds of giga bytes of memory within a node. Processing such large graphs necessitate novel parallel partitioning and clustering methods to hierarchically divide the graph into chunks to have better locality both within a chunk and among chunks close in the hierarchy. Such parallel methods will also significantly decrease the preprocessing overhead.

The achieved improvements on a single node also open up the path to distributed-memory frameworks. One future research direction is using a novel method to decrease inter-node communication and using the proposed methods to exploit data locality within a node. Graph analytics on GPUs is also important since there are many GPU-based frameworks. Hence, a future extension of this work will be exploiting data locality via decreasing the random accesses to vertices in order to efficiently utilize the resources of GPUs.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

ORCID iD

Kadir Akbudak

Author biography

Kadir Akbudak received a BS degree from Hacettepe University and MS and PhD degrees from Bilkent University, all in computer science. He received a TUBITAK scholarship during his graduate studies and awards of computing resources on Europe's large-scale Tier-0 parallel systems. He was a postdoctoral researcher in the Department of Computer Science at Bilkent University, Turkey. He actively took place in four European Commission-funded PRACE projects. Dr. Akbudak led the development of the Hierarchical Computations on Manycore Architectures (HiCMA) software toolkit as a postdoctoral researcher in the Extreme Computing Research Center at KAUST, Saudi Arabia. Then, he contributed to the Software for Linear Algebra Targeting Exascale (SLATE) project, funded by the US Department of Energy (DOE), as a research scientist in the Innovative Computing Laboratory at the University of Tennessee, Knoxville, TN, USA. Dr. Akbudak's research interests include machine learning, big data analytics, combinatorial scientific computing, performance optimizations for multicore architectures and hardware accelerators.

References

Akbudak

Aykanat

(2017) Exploiting locality in sparse matrix-matrix multiplication on many-core architectures. IEEE Transactions on Parallel and Distributed Systems 28(8): 2258–2271.

Aliyev

Urkmez

Wagner

(2019) A comprehensive look at luxury brand marketing research from 2000 to 2016: a bibliometric study and content analysis. Management Review Quarterly 69(3): 233–264.

Anderson

Sundaram

Satish

, et al. (2016) GraphPad: optimized graph primitives for parallel and distributed platforms. In: 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 313–322.

Apache Giraph (2012) Available at: http://giraph.apache.org/(Accessed 16 June 2020).

Arai

Shiokawa

Yamamuro

, et al. (2016) Rabbit order: just-in-time parallel reordering for fast graph analysis. In: 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 22–31.

Bader

Madduri

(2006) Parallel algorithms for evaluating centrality indices in real-world networks. In: 2006 International Conference on Parallel Processing (ICPP’06). 539–550.

Balaji

Lucia

(2018) When is graph reordering an optimization? studying the effect of lightweight graph reordering across applications and input graphs. In: 2018 IEEE International Symposium on Workload Characterization (IISWC). 203–214.

Barik

Minutoli

Halappanavar

, et al. (2020) Vertex reordering for real-world graphs and applications: an empirical evaluation. In: 2020 IEEE International Symposium on Workload Characterization (IISWC). IEEE, 240–251.

Beamer

Asanovic

Patterson

(2012) Direction-optimizing breadth-first search. In: SC’12: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis. IEEE, 1–10.

10.

Beamer

Asanovic

Patterson

(2015a) The GAP Benchmark Suite.

11.

Beamer

Asanovic

Patterson

(2015b) Locality exists in graph processing: workload characterization on an ivy bridge server. In: 2015 IEEE International Symposium on Workload Characterization. 56–65.

12.

Beamer

Asanović

Patterson

(2017) Reducing pagerank communication via propagation blocking. In: 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 820–831.

13.

Berge

(1984) Hypergraphs: Combinatorics of Finite Sets, Volume 45. Elsevier.

14.

Besta

Podstawski

Groner

, et al. (2017) To push or to pull: on reducing communication and synchronization in graph computations. In: Proceedings of the 26th International Symposium on High-Performance Parallel and Distributed Computing, HPDC’17. New York, NY, USA: ACM. ISBN 9781450346993, 93–104.

15.

Borgatti

(2005) Centrality and network flow. Social Networks 27(1): 55–71.

16.

Borkar

Chien

(2011) The future of microprocessors. Communications of the ACM 54(5): 67–77.

17.

Brandes

(2001) A faster algorithm for betweenness centrality. Journal of Mathematical Sociology 25(2): 163–177.

18.

Buluç

Gilbert

(2011) The Combinatorial BLAS: design, implementation, and applications. The International Journal of High Performance Computing Applications 25(4): 496–509.

19.

Buluc

Madduri

(2013) Graph partitioning for scalable distributed graph computations. Graph Partitioning and Graph Clustering 588: 83.

20.

Catalyurek

Aykanat

(1999) Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication. IEEE Transactions on Parallel and Distributed Systems 10(7): 673–693.

21.

Catanese

De Meo

Ferrara

, et al. (2012) Extraction and analysis of Facebook friendship relations. In: Computational Social Networks. Springer, 291–324.

22.

Chen

Shi

Chen

, et al. (2015) Powerlyra: differentiated graph computation and partitioning on skewed graphs. In: Proceedings of the Tenth European Conference on Computer Systems, EuroSys’15. New York, NY, USA: ACM. ISBN 9781450332385.

23.

Cheng

Shang

Cheng

, et al. (2012) K-reach: who is in your small world. Proceedings of the VLDB Endowment 5(11).

24.

Cherkassky

Goldberg

Radzik

(1996) Shortest paths algorithms: theory and experimental evaluation. Mathematical Programming 73(2): 129–174.

25.

Cuthill

McKee

(1969) Reducing the bandwidth of sparse symmetric matrices. In: Proceedings of the 1969 24th National Conference. 157–172.

26.

Davis

(2011) The university of Florida sparse matrix collection. ACM Transactions on Mathematical Software 38(1).

27.

DBG (2019) Available at: http://github.com/faldupriyank/dbg (Accessed 16 June 2020).

28.

Ding

Hosoya

Kamioka

(2018) Co-purchase analysis by hierarchical network structure. PACIS 149.

29.

Ediger

Jiang

Riedy

, et al. (2010) Massive social network analysis: mining twitter for social good. In: 2010 39th International Conference on Parallel Processing. 583–593.

30.

Faldu

Diamond

Grot

(2019) A closer look at lightweight graph reordering. IISWC 1–13. DOI: 10.1109/IISWC47752.2019.9041948

31.

Faldu

Diamond

Grot

(2020) Domain-specialized cache management for graph analytics. In: 2020 IEEE International Symposium on High Performance Computer Architecture (HPCA). 234–248.

32.

Freeman

(1977) A set of measures of centrality based on betweenness. Sociometry 40(1): 35–41.

33.

Personick

Thompson

(2014) Mapgraph: a high level api for fast development of high performance graph analytics on gpus. In: Proceedings of Workshop on GRAph Data Management Experiences and Systems, GRADES’14. New York, NY, USA: ACM, 1–6. ISBN 9781450329828.

34.

Gonzalez

Low

, et al. (2012) Powergraph: distributed graph-parallel computation on natural graphs. In: Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation, OSDI’12. USA: USENIX Association, 17–30. ISBN 9781931971966.

35.

Gorder (2016) Available at: http://github.com/datourat/Gorder (Accessed 16 June 2020).

36.

Gregor

Lumsdaine

(2005) The parallel bgl: a generic library for distributed graph computations. Parallel Object-Oriented Scientific Computing (POOSC) 2: 1–18.

37.

Kang

Tsourakakis

Faloutsos

(2009) Pegasus: a peta-scale graph mining system implementation and observations. In: 2009 Ninth IEEE International Conference on Data Mining. IEEE, 229–238.

38.

Kang

Tsourakakis

Faloutsos

(2011) Pegasus: mining peta-scale graphs. Knowledge and Information Systems 27(2): 303–325.

39.

Karypis

Kumar

(1998) A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing 20(1): 359–392.

40.

Khorasani

Vora

Gupta

, et al. (2014) Cusha: vertex-centric graph processing on gpus. In: Proceedings of the 23rd International Symposium on High-Performance Parallel and Distributed Computing, HPDC’14. New York, USA: ACM. ISBN 9781450327497, 239–252.

41.

Kulkarni

Pingali

Walter

, et al. (2007) Optimistic parallelism requires abstractions. In: Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI’07. New York, USA: ACM, 211–222. ISBN 9781595936332.

42.

Kulkarni

Burtscher

Casçaval

, et al. (2009) Lonestar: a suite of parallel irregular programs. In: ISPASS ’09: IEEE International Symposium on Performance Analysis of Systems and Software.

43.

Kumar

Vaidyanathan

Ananthapadmanabhan

, et al. (2020) Hypergraph clustering by iteratively reweighted modularity maximization. Applied Network Science 5(1): 1–22.

44.

Kyrola

Blelloch

Guestrin

(2012) Graphchi: large-scale graph computation on just a PC. In: Presented as Part of the 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI 12). Hollywood, CA: USENIX, 31–46. ISBN 978-1-931971-96-6.

45.

Lakhotia

Singapura

Kannan

, et al. (2017) Recall: reordered cache aware locality based graph processing. In: 2017 IEEE 24th International Conference on High Performance Computing (HiPC). 273–282.

46.

Lakhotia

Kannan

Pati

, et al. (2020) Gpop: a scalable cache- and memory-efficient framework for graph processing over parts. ACM Trans Parallel Comput 7(1).

47.

Lee

Kim

Lim

, et al. (2019) Pre-select static caching and neighborhood ordering for bfs-like algorithms on disk-based graph engines. In: 2019 USENIX Annual Technical Conference (USENIX ATC 19). Renton, WA: USENIX Association, 459–474. ISBN 978-1-939133-03-8.

48.

Ren

, et al. (2018) Concurrent hybrid breadth-first-search on distributed powergraph for skewed graphs. In: 2018 IEEE 24th International Conference on Parallel and Distributed Systems (ICPADS), 160–169. IEEE.

49.

Ligra (2014) Available at: http://github.com/jshun/ligra/(Accessed 16 June 2020).

50.

Low

Bickson

Gonzalez

, et al. (2012) Distributed GraphLab: a framework for machine learning and data mining in the cloud. Proc. VLDB Endow 5(8): 716–727.

51.

Lugowski

Alber

Buluç

, et al. (2012) A flexible open-source toolbox for scalable complex graph analysis. In: Proceedings of the Twelfth SIAM International Conference on Data Mining (SDM12). 930–941.

52.

Madduri

Ediger

Jiang

, et al. (2009) A faster parallel algorithm and efficient multithreaded implementations for evaluating betweenness centrality on massive datasets. In: 2009 IEEE International Symposium on Parallel Distributed Processing. 1–8.

53.

Malewicz

Austern

Bik

, et al. (2010) Pregel: a system for large-scale graph processing. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data. 135–146.

54.

Mattson

Bader

Berry

, et al. (2013) Standards for graph algorithm primitives. In: 2013 IEEE High Performance Extreme Computing Conference (HPEC). 1–2.

55.

Milroy

Baker

Hammerling

, et al. (2019) Making root cause analysis feasible for large code bases: a solution approach for a climate model. In: Proceedings of the 28th International Symposium on High-Performance Parallel and Distributed Computing. 73–84.

56.

Morselli

Roy

(2008) Brokerage qualifications in ringing operations. Criminology 46(1): 71–98.

57.

Murphy

Wheeler

Barrett

, et al. (2010) Introducing the graph 500. Cray Users Group (CUG) 19: 45–74.

58.

Nam

Barnett

Kim

(2014) Corporate hyperlink network relationships in global corporate social responsibility system. Quality and Quantity 48(3): 1225–1242.

59.

Neo4j (2007) Available at: http://neo4j.com/(Accessed 16 June 2020).

60.

Nguyen

Lenharth

Pingali

(2013a) A lightweight infrastructure for graph analytics. In: Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, SOSP’13. New York, NY, USA: ACM, 456–471. ISBN 9781450323888.

61.

Nguyen

Lenharth

Pingali

(2013b) A lightweight infrastructure for graph analytics. In: Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles. 456–471.

62.

Prabhakaran

Weng

, et al. (2012) Managing large graphs on multi-cores with graph awareness. In: Presented as Part of the 2012 USENIX Annual Technical Conference (USENIX ATC 12). 41–52.

63.

Puzis

Altshuler

Elovici

, et al. (2013) Augmented betweenness centrality for environmentally aware traffic monitoring in transportation networks. Journal of Intelligent Transportation Systems 17(1): 91–105.

64.

Rabbit (2016) Available at: https://github.com/araij/rabbit_order (Accessed 07 January 2023).

65.

Shun

Blelloch

(2013) Ligra: a lightweight graph processing framework for shared memory. In: Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP’13. New York, NY, USA: ACM, 135–146. ISBN 9781450319225.

66.

Sundaram

Satish

Patwary

MMA

, et al. (2015) Graphmat: high performance graph analytics made productive. Proceedings of the VLDB Endowment 8(11).

67.

Unat

Dubey

Hoefler

, et al. (2017) Trends in data locality abstractions for hpc systems. IEEE Transactions on Parallel and Distributed Systems 28(10): 3007–3020.

68.

Van De Geijn

Watts

(1997) Summa: scalable universal matrix multiplication algorithm. Concurrency: Practice and Experience 9(4): 255–274.

69.

Wang

Davidson

Pan

, et al. (2016) Gunrock: a high-performance graph processing library on the gpu. In: Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP’16. New York, NY, USA: ACM. ISBN 9781450340922.

70.

Wang

Pan

Davidson

, et al. (2017) Gunrock: gpu graph analytics. ACM Trans. Parallel Comput 4(1).

71.

Wang

Zhou

(2019) Parallelizing approximate single-source personalized pagerank queries on shared memory. The VLDB Journal 28(6): 923–940.

72.

Wei

, et al. (2016) Speedup graph processing by graph ordering. In: Proceedings of the International Conference on Management of Data, SIGMOD’16. New York, NY, USA: ACM, 1813–1828.

73.

Gong

Rand

, et al. (2012) Making recommendations in a microblog to improve the impact of a focal user. In: Proceedings of the Sixth ACM Conference on Recommender Systems. 265–268.

74.

Xin

Gonzalez

Franklin

, et al. (2013) Graphx: a resilient distributed graph system on spark. In: First International Workshop on Graph Data Management Experiences and Systems, GRADES’13. New York, NY, USA: ACM. ISBN 9781450321884.

75.

Zhang

Kiriansky

Mendis

, et al. (2017) Making caches work for graph analytics. In: 2017 IEEE International Conference on Big Data (Big Data). 293–302.

76.

Zhang

Yang

Baghdadi

, et al. (2018) Graphit: a high-performance graph DSL. Proceedings of the ACM on Programming Languages 2(OOPSLA): 1–30.

77.

Zhou

Huang

Schölkopf

(2006) Learning with hypergraphs: clustering, classification, and embedding. Advances in Neural Information Processing Systems 19: 1601–1608.