Triangle listing and counting is a highly-studied problem in computer science and is a key building block in various graph analysis techniques such as clustering coefficients [1], k-truss [2], and triangle centrality [3]. The MIT/Amazon/IEEE Graph Challenge [4], [5] includes triangle counting as a fundamental method in graph analytics. There are at most n 3 = Θ n 3 triangles in a graph G = (V, E) with n = |V | vertices and m = |E| edges. The focus of this paper is on sequential triangle counting algorithms for sparse graphs that are stored in compressed, sparse row (CSR) format, rather than adjacency matrix format. The naïve approach using triply-nest loops to check if each triple (u, v, w) forms a triangle takes O n 3 time and is inefficient for sparse graphs. It is well-known that listing all triangles in G is Ω m 3 2 time [6], [7]. The main contributions of this paper are:
• A new triangle algorithm that combines the techniques of cover-edges, forward, and hashing and runs in O (m • a(G)), where a(G) is the arboricity of the graph; • An experimental study of an implementation of this novel triangle counting algorithm on real and synthetic graphs; and • Freely-available, open-source software for more than 20 triangle counting algorithms and variants in the C programming language.
There are faster algorithms for triangle counting, such as the work of Alon, Yuster, and Zwick [8] that require an adjacency matrix for the input graph representation and use fast matrix multiplication. As this is infeasible for large, sparse graph, their and other fast multiply methods are outside the scope of this paper.
Latapy [7] provides a survey on triangle counting algorithms for very large, sparse graphs. One of the earliest algorithms, tree-listing, published in 1978 by Itai and Rodeh [6] first finds a rooted spanning tree of the graph. After iterating through the non-tree edges and using criteria to identify triangles, the tree edges are removed and the algorithm repeats until there are no edges remaining. This approach takes O m The most common triangle counting algorithms in the literature include vertex-iterator [6], [7] and edge-iterator [6], [7] approaches that run in O (m • d max ) time [6], [9], [10], where d max is the maximum degree of a vertex in the graph. In vertex-iterator, the adjacency list N (v) of each vertex v ∈ V is doubly-enumerated to find all 2-paths (u, v, w) where u, w ∈ N (v). Then, the graph is searched for the existence of the closing edge (u, w) by checking if w ∈ N (u) (or if u ∈ N (w)). Arifuzzaman et al. [11] study modifications of the vertex-iterator algorithm based on various methods for vertex ordering.
In edge-iterator, each edge (u, v) in the graph is examined, and the intersection of N (u) and N (v) is computed to find triangles. A common optimization is to use a direction-oriented approach that only considers edges (u, v) where u < v. The variants of edge-iterator are often based on the algorithm used to perform the intersection. When the two adjacency lists are sorted, then MergePath and BinarySearch can be used. MergePath performs a linear scan through both lists counting the common elements. Makkar, Bader and Green [12] give an efficient MergePath algorithm for GPU. Mailthody et al. [13] use an optimized two-pointer intersection (MergePath) for set intersection. BinarySearch, as the name implies, uses a binary search to determine if each element of the smaller list is found in the larger list. Hash is another method for performing the intersection of two sets and it does not require the adjacency lists to be sorted. A typical implementation of Hash initializes a Boolean array of size m to all false. Then, positions in Hash corresponding to the vertex values in N (u) are set to true. Then N (v) is scanned, looking up in Θ(1) time whether or not there is a match for each vertex. Chiba and Nishizeki published one of the earliest edge iterator with hashing algorithms for triangle finding in 1985 [14]. The running time is O (a(G)m), where a(G) is defined as the arboricity of G, which is upper-bounded a(G) ≤ ⌈(2m + n) 1 2 /2⌉ [14]. In 2018, Davis rediscovered this method, which he calls tri_simple in his comparison with SuiteSparse GraphBLAS [15]. According to Davis [15]: this algorithm "is already a non-trivial method. It requires expert knowledge of how Gustavson's method can be implemented efficiently, including a reduction of the result to a single scalar." Mowlaei [16] gave a variant of the edgeiterator algorithm that uses vectorized sorted set intersection and reorders the vertices using the reverse Cuthill-McKee heuristic.
In 2005, Schank and Wagner [9], [10] designed a fast triangle counting algorithm called forward (see Algorithm 1) that is a refinement of the edge-iterator approach. Instead of intersections of the full adjacency lists, the forward algorithm uses a dynamic data structure A(v) to store a subset of the neighborhood N (v) for v ∈ V . Initially each set A() is empty, and after computing the intersection of the sets A(u) and A(v) for each edge (u, v) (with u < v), u is added to A(v). This significantly reduces the size of the intersections needed to find triangles. The running time is O (m • d max ). However, if one reorders the vertices in decreasing order of their degrees as a Θ(n log n) time pre-processing step, the forward algorithm's running time reduces to O m 3 2 . Donato et al. [17] implement the forward algorithm for sharedmemory. Ortmann and Brandes [18] survey triangle counting algorithms, create a unifying framework for parsimonious implementations, and conclude that nearly every triangle listing variant is in O (m • a(G)).
Algorithm 1 Forward Triangle Counting [9], [10]
The forward-hashed algorithm [9], [10] (also called compact-forward [7]) is a variant of the forward algorithm that uses the hashing described above for the intersections of the A() sets, see Algorithm 2. Shun and Tangwongsan [19] parallelize the forward and forward-hashed algorithms for multicore systems. Low et al. [20] derive a linear-algebra method for triangle counting that does not use matrix multiplication. Their algorithm results in the forward-hashed algorithm.
Recently, we presented Algorithm 3 [21] as a new method for finding triangles. This approach finds a subset of cover edges from E such that every triangle contains at least one cover edge.
This algorithm uses breadth-first search (BFS) to find a reduced cover-edge set consisting of edges (u, v) where the Algorithm 2 Forward-Hashed Triangle Counting [9], [10]
∀w ∈ A(u) 7:
Hash[w] ← true 8:
∀w ∈ A(v) 9:
if Hash[w] then 10:
T ← T + 1 11:
∀w ∈ A(u) 12:
Hash[w] ← false 13:
Algorithm 3 Cover-Edge Triangle Counting [21] Input:
levels of vertices u and v are the same, i.e., L(u) ≡ L(v).
From the result in [21], each triangle must contain at least one of these horizontal edges. Then each edge in the cover set is examined, and Hash is used to find the vertices w in the intersection of N (u) and N (v
if Hash[w] then 16:
In this paper, we present our new triangle counting algorithm (Alg. 4), called fast triangle counting. This new triangle counting algorithm is similar with cover-edge triangle counting in Alg. 3 and uses BFS to assign a level to each vertex in lines 1 and 2. Next in lines 3 to 7, the edges E of the graph are partitioned into two sets E0 -the horizontal edges where both endpoints are on the same level -and E1 -the remaining tree and non-tree edges that span a level. Thus, we now have two graphs, G0 = (V, E0) and G1 = (V, E1), where E = E0∪E1 and E0 ∩ E1 = ∅. Triangles that are fully in G0 are counted with one method and triangles not fully in G0 are counted with another method. For G0, the graph with horizontal edges, we count the triangles efficiently using the forward-hashed method (line 8). For triangles not fully in G0, the algorithm uses the following approach to count these triangles. Using G1, the graph that contains the edges that span levels, we use a hashed intersection approach in lines 9 to 18. As per the coveredge triangle counting, we need to find the intersections of the adjacency lists from the endpoints of horizontal edges. Thus, we use G0 to select the edges, and perform the hash-based intersections from the adjacency lists in graph G1. The proof of correctness for cover-edge triangle counting is given in [21]. Alg. 4 is a hybrid version of this algorithm, that partitions the edge set, and uses two different to count these two types of triangles. The proof of correctness is still valid with these new refinements to the algorithm. The running time of Alg. 4 is the maximum of the running time of forward-hashing and Alg. 3. Alg. 4 uses hashing for the set intersections. For vertices u and v the cost is min(d(u), d(v)) since the algorithm can check if the neighbors of the lower-degree endpoint are in the hash set of the higher-degree endpoint. Over all (u, v) edges in E, these intersections take O (m • a(G)) expected time. Hence, Alg. 4 takes O (m • a(G)) expected time.
Similar with the forward-hashed method, by pre-processing the graph by re-ordering the vertices in decreasing order of degree in Θ(n log n) time often leads to a faster triangle counting algorithm in practice.
We implemented more than 20 triangle counting algorithms and variants in C and use the Intel Development Cloud for benchmarking our results on a GNU/Linux node. The compiler is Intel(R) oneAPI DPC++/C++ Compiler 2023.1.0 (2023.1.0.20230320) and '-O2' is used as a compiler optimization flag. For benchmarking we compare the performance using two recently-launched Intel Xeon processors (Sapphire Rapids launched Q1'23) with two types of memory (DDR5 and HBM). The first node is a dedicated 2.00 GHz 56-core (112 thread) Intel(R) Xeon(R) Platinum 8480+ processor (formerly known as Sapphire Rapids) with 105M cache and 1024GB of DDR5 RAM. The second node is a dedicated 1.90 GHz 56-core (112 thread) Intel(R) Xeon(R) CPU Max 9480 processor (formerly known as Sapphire Rapids HBM) with 112.5M cache and 256GB of high-memory bandwidth (HBM) memory.
Following the best practices of experimental algorithmics [22], we conduct the benchmarking as follows. Each algorithm is written in C and has a single argument -a pointer to the graph in a compressed sparse row (CSR) format. The input is treated as read-only. If the implementation needs auxiliary arrays, pre-processing steps, or additional data structures, it is charged the full cost. Each implementation must manage memory and not contain any memory leaks -hence, any dynamically allocated memory must be freed prior to returning the result. The output from each implementation is an integer with the number of triangles found. Each algorithm is run ten times, and the mean running time is reported. To reduce variance for random graphs, the same graph instance is used for all of the experiments. The source code is sequential C code without any explicit parallelization. The same coding style and effort was used for each implementation.
Experimental results are presented in [15]) LA : Linear Algebra (CMU [20]) CE : Cover Edge (Bader, [21]) CED : Cover Edge with degree-ordering (Bader, [21]) Bader : this paper BaderD: this paper with degree-ordering While all of the algorithms tested have the same asymptotic worst-case complexity, the running times range by orders of magnitude between the approaches. In nearly every case where edge direction-orientation is used, the performance is typically improved by a constant factor up to two. The vertex-iterator and Itah-Rodeh algorithms are the slowest across the real and synthetic datasets. The timings between the Intel Xeon Platinum 8480+ and Intel Xeon Max 9480 are consistent, with the 8480+ a few percent faster than the 9480 processor. This is likely due to the fact that we are using single-threaded code on one core, and that the 8480+ is clocked at a slightly higher rate (2.00GHz vs 1.90GHz).
In general, the forward algorithms and its variants tend to perform the fastest, followed by the edge-iterator, and then the vertex-iterator methods. The new fast triangle counting algorithm is competitive with the forward approaches, and may be useful when the results of a BFS are already available from the analyst's workflow, which is often the case.
The performance of the road network graphs (roadNet-CA, roadNet-PA, roadNet-TX) are outliers from the other graphs. Road networks, unlike social networks, often have only low degree vertices (for instance, many degree four vertices), and large diameters. The percentage of horizontal edges (k) of these road networks is under 15% and we see less benefit of the new approach due to this low value of k. In addition, the sorting of vertices by degree for the road network significantly harms the performance compared with the default ordering of the input. This may be due to the fact that there are few unique degree values, and sorting decimates the locality in the graph data structure.
The linear algebra approach [20] does not typically perform as well on the real and synthetic social networks. For example, on a large RMAT graph of scale 18, the linear algebra algorithm method takes seconds, whereas the new algorithm runs in under a second. However, the linear algebra approach performs well on the road networks.
In this paper we design and implement a novel, fast triangle counting algorithm, that uses new techniques to improve the performance. It is the first algorithm in decades to shine new light on triangle counting, and use a wholly new method of cover-edges to reduce the work of set intersections, rather than other approaches that are variants of the well-known vertexiterator and edge-iterator methods. We provide extensive performance results in a parsimonious framework for benchmarking serial triangle counting algorithms for sparse graphs in a uniform manner. The results use one of Intel's latest processor families, the Intel Sapphire Rapids (Platinum 8480+) and Sapphire Rapids HBM (CPU Max 9480) launched in the 1st quarter of 2023. The new triangle counting algorithm can benefit when the results of a BFS are available, which is often the case in network science. Additionally, this work will inspire much interest within the Graph Challenge community to implement versions of the presented algorithms for large-shared memory, distributed memory, GPU, or multi-GPU frameworks.
The fast triangle counting algorithm (Alg. 4) can be readily parallelized using a parallel BFS, partitioning the edge set in parallel, and using a parallel triangle counting algorithm on graph G0, and parallelizing the set intersections for graph G1. In future work, we will implement this parallel algorithm and compare its performance with other parallel approaches.