Cover Edge-Based Novel Triangle Counting

David A. Bader, Fuhuan Li, Zhihui Du, Palina Pauliuchenka, Oliver Alvarado Rodriguez, Anant Gupta, Sai Vastav Minnal, Valmik Nahata, Anya Ganeshan, Ahmet Gündoğdu, Jason LewAlgorithms 2025 · DOI

TL;DR

This paper introduces a novel "cover-edge set" concept for triangle counting in graphs, significantly reducing computational overhead by focusing on a smaller, essential subset of edges. They developed efficient sequential and parallel algorithms based on this concept, demonstrating substantial speedups and providing a comprehensive open-source framework for evaluating triangle counting methods.

What Problem Does This Paper Address?

Triangle counting is a fundamental problem in graph analysis with applications ranging from community detection to network centrality. Existing methods, while effective, can be computationally expensive, especially for large and sparse graphs. Naive approaches are O(n³), and even optimized methods often involve redundant checks or extensive computations. The paper aims to address this by developing a more efficient triangle counting approach that minimizes unnecessary edge examinations.

Methods

The core innovation is the "cover-edge set," defined as a subset of graph edges that contains at least one edge from every triangle. This set is constructed efficiently using a Breadth-First Search (BFS) to classify edges into tree-edges, strut-edges, and horizontal-edges. The paper proves that the set of all horizontal edges forms a valid cover-edge set. Based on this, they propose the Cover-Edge Triangle Counting (CETC) algorithm.

Key algorithmic contributions include:

  • CETC-Seq: A sequential algorithm that leverages the cover-edge set derived from BFS to count triangles, ensuring each triangle is counted exactly once.
  • CETC-Seq-FE, CETC-Seq-S, CETC-Seq-SD, CETC-Seq-SR: Variants of CETC-Seq that incorporate further optimizations like dynamic algorithm selection based on graph characteristics, graph partitioning, degree ordering, and recursion.
  • CETC-SM: A shared-memory parallel version of CETC designed for multi-core processors.

The authors also developed an open-source evaluation framework integrating 22 sequential and 11 parallel triangle counting algorithms for comprehensive benchmarking.

Datasets

The authors evaluated their algorithms on a diverse set of 24 graphs, including:

  • Real-world datasets: Sourced from the Stanford Network Analysis Project (SNAP), such as roadNet-CA, roadNet-PA, roadNet-TX, soc-Epinions1, wiki-Vote, loc-Brightkite, loc-Gowalla, and karate.
  • Synthetic graphs: Generated using large Graph500 RMAT graphs with varying parameters.

Key Insights and Ideas

  • The "Cover-Edge Set" is a powerful abstraction: By identifying a minimal set of edges that "cover" all triangles, the problem can be significantly simplified, reducing redundant computations.
  • BFS is surprisingly effective for edge classification: The simple act of performing a BFS and classifying edges based on levels provides a crucial structure (horizontal edges) for building the cover-edge set.
  • Graph topology matters immensely: The performance of different algorithms, especially optimizations like degree ordering and the effectiveness of the cover-edge approach, is highly dependent on graph characteristics like density, diameter, and degree distribution.
  • Hybrid approaches can be highly effective: Combining different algorithmic strategies (e.g., partitioning the graph and using specialized methods for each partition, as in CETC-Seq-S) can yield superior results.
  • Parallelization overhead is a critical factor for small graphs: For very small graphs, the benefits of parallelization can be negated by the overhead of thread management and communication.

Key Results

  • Significant Speedups: The novel CETC-Seq variants achieved speedups of up to 24x compared to baseline algorithms.
  • Parallel Performance: Parallel versions, particularly those using binary search (EBP, EBDP) and hash-based methods (EHDP), showed excellent scalability, achieving speedups of up to 233x on large graphs with 224 threads.
  • DO Optimization: Direction-Oriented (DO) optimization consistently provided speedups of at least two-fold, with the WD algorithm showing an average speedup of 3.637x.
  • Hash-Based Optimization: Hash methods offered significant speedups, with EH achieving an average of 5.4x and FH achieving 3.0x.
  • Forward Algorithm Variants: FH and FHD demonstrated exceptional efficiency, achieving speedups as high as 29.1x.
  • CETC-SM Scalability: CETC-SM showed a speedup of 3.9x with 32 threads, indicating good parallel performance.

Limitations and Future Work

Limitations: * BFS Overhead: For certain graph structures (e.g., long-diameter graphs with few neighbors), the BFS preprocessing step in CETC-Seq can become a bottleneck, consuming a significant portion of the total execution time (up to 60%). * Road Network Performance: Road networks, characterized by low-degree vertices and large diameters, showed limited gains from some optimizations, suggesting that a small covering ratio doesn't always guarantee higher performance. * Parallel Overhead on Small Graphs: For very small graphs, parallel algorithms can be slower than sequential ones due to overhead.

Future Work: * Extend CETC to distributed memory systems and heterogeneous architectures (GPU, multi-GPU). * Incorporate hybrid task parallelism and asynchronous data exchange for improved performance at scale. * Integrate CETC into dynamic graph processing frameworks for efficient triangle maintenance under edge insertions/deletions. * Apply the cover-edge principle to broader subgraph counting and pattern discovery problems. * Further explore structural optimizations beyond traditional iterator-based paradigms.

Summary updated

Abstract

Counting and listing triangles in graphs is a fundamental task in network analysis, supporting applications such as community detection, clustering coefficient computation, k-truss decomposition, and triangle centrality. We introduce the cover-edge set, a novel concept that eliminates unnecessary edges during triangle enumeration, thereby improving efficiency. This compact cover-edge set is rapidly constructed using a breadth-first search (BFS) strategy. Using this concept, we develop both sequential and parallel triangle-counting algorithms and conduct comprehensive comparisons with state-of-the-art methods. We also design a benchmarking framework to evaluate our sequential and parallel algorithms in a systematic and reproducible manner. Extensive experiments on the latest Intel Xeon 8480+ processor reveal clear performance differences among algorithms, demonstrate the benefits of various optimization strategies, and show how graph characteristics, such as diameter and degree distribution, affect algorithm performance. Our source code is available on GitHub.
BibTeX
@inproceedings{bader2025cover,
  author = {David A. Bader and Fuhuan Li and Zhihui Du and Palina Pauliuchenka and Oliver Alvarado Rodriguez and Anant Gupta and Sai Vastav Minnal and Valmik Nahata and Anya Ganeshan and Ahmet Gündoğdu and Jason Lew},
  title = {{Cover Edge-Based Novel Triangle Counting}},
  booktitle = {Algorithms},
  year = {2025},
  doi = {10.3390/a18110685},
}
Figure