Efficient and Complete Triangle Counting in Hypergraph Streams

Full abstract

Read the full abstract

Triangle counting in hypergraph streams, including both hyper-vertex and hyper-edge triangles, is a fundamental problem in hypergraph analytics, with broad applications. However, existing methods face two key limitations: ( i ) an incomplete classification of hyper-vertex triangle structures, typically considering only inner or outer triangles; and ( ii ) inflexible sampling schemes that predefine the number of sampled hyperedges, which is impractical under strict memory constraints due to highly variable hyperedge sizes. To address these challenges, we first introduce a complete classification of hyper-vertex triangles, including inner, hybrid, and outer triangles. Based on this, we propose two complementary categories of streaming algorithms. For element-wise eviction, we develop HTCount, an algorithm that dynamically adjusts the sample size based on the available memory M , and HTCount-P, a partition-based variant that further improves memory utilization by partitioning unused memory into independent sample subsets. For batch eviction, we propose HTCount-B, which adopts a lazy maintenance strategy controlled by a decay parameter β , reducing per-update computational cost by operating with a smaller average sample set and naturally capturing temporal locality in triangle formation. We provide theoretical analysis of the unbiasedness and variance bounds of the proposed algorithms. Case studies demonstrate the expressiveness of our triangle structures in revealing meaningful interaction patterns. Extensive experiments on real-world hypergraphs show that our algorithms achieve highly accurate triangle count estimates under strict memory constraints, with relative errors 1–2 orders of magnitude lower than existing methods; HTCount-B further attains higher throughput with appropriate β settings, and practical guidelines are provided for different datasets.