Pith. sign in

REVIEW 3 major objections 5 minor 86 references

Triangle Counting in Hypergraph Streams: A Complete and Practical Approach

T0 review · 3 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A memory-adaptive reservoir pass produces unbiased estimates of all three hyper-vertex triangle types and the four hyper-edge triangle classes in a hypergraph stream.

desk verdict The taxonomy is worth something, but the paper's core unbiasedness claim is false: Lemma 4.2 does not hold, and the algorithm also counts evicted edges, so the advertised guarantees fail. read the letter →

arxiv 2509.00674 v1 pith:FYNFSEDZ submitted 2025-08-31 cs.DS cs.GR

Lingkai Meng , Long Yuan , Xuemin Lin , Wenjie Zhang , Ying Zhang This is my paper · ORCID
classification cs.DScs.GR
keywords hypergraphstreamstrianglecountingreservoirsamplingmemory-awarehyper-vertextriangleshyper-edgeunbiasedestimationstreamingalgorithms
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Triangle counting in hypergraph streams has been held back by two gaps: the standard view of hyper-vertex triangles ignores the hybrid pattern, and sampling schemes fix the number of sampled hyperedges in advance, which is unsafe when hyperedge sizes vary enormously. This paper closes both gaps. It defines a complete split of hyper-vertex triangles into inner, hybrid, and outer, and gives two streaming algorithms—HTCount and its partition-based variant HTCount-P—that maintain a reservoir whose size is measured in vertices, so the memory budget M is respected directly. The algorithms claim unbiased estimates of all hyper-vertex and hyper-edge triangle counts, with variance bounds, and experiments on real hypergraphs report relative errors one to two orders of magnitude below the previous method. If these claims hold, practitioners can track fine-grained triangle patterns online without knowing hyperedge sizes in advance.

What carries the argument

The load-bearing object is the reservoir G_s, whose size is measured in stored vertices rather than number of hyperedges, together with the correction factors θ = m(m−1)/(|G_s|(|G_s|−1)) for hybrid triangles and γ = m(m−1)(m−2)/(|G_s|(|G_s|−1)(|G_s|−2)) for outer and hyper-edge triangles. These factors are the inverses of the claimed probability that the relevant pair or triple of hyperedges is simultaneously present in the sample, so multiplying observed local intersections by them converts a sampled count into an unbiased estimate of the global count. HTCount-P's added mechanism is a partition of the unused memory into independent reservoirs, each with its own m[i] and |G_s[i]|, which lets

What would settle it

Simulate HTCount many times on a short stream with variable hyperedge sizes and a small vertex budget, and tally how often each hyperedge survives. The uniformity lemma predicts every hyperedge appears with frequency |G_s|/m; a persistent gap between empirical inclusion and that ratio would falsify the unbiasedness proof.

Watch

Extended reading notes

Core claim

The central claim is that a hypergraph triangle count can be estimated on a single pass under a fixed vertex budget by treating the reservoir as memory-sized rather than edge-count-sized. For every arriving hyperedge, HTCount does exact inner-triangle accounting from C(|e|,3), then reservoir-samples the edge with probability |G_s|/m; if insertion exceeds M, uniformly random evictions continue until memory fits. Counts of hybrid and outer triangles found in the current sample are reweighted by the inverse sampling probabilities θ and γ, which the paper proves makes their expectations equal the true counts (Theorems 4.3 and 4.4). HTCount-P partitions spare memory into independent reservoirs, r

Load-bearing premise

Unbiasedness stands on the claim that at every time step the reservoir is a uniformly random subset of all hyperedges seen so far, so each hyperedge's inclusion probability is exactly the sample count divided by the stream length; if that ratio is wrong, the correction factors systematically misstate the counts.

Editorial extensions

If this is right

  • Practitioners can set a single memory budget in bytes or vertices; the algorithms adapt the sample size automatically, avoiding both overflow and the severe under-utilization of fixed-λ sampling when edge sizes vary by orders of magnitude.
  • Hybrid triangles become a first-class, trackable quantity in streams; the case studies show their rise precedes outer-triangle growth in co-authorship networks, offering an earlier signal of interdisciplinary convergence.
  • Because updates happen on every accepted hyperedge rather than after sampling ends, the algorithms support real-time triangle-count estimates, not just final aggregates.
  • The four hyper-edge triangle classes (CCC/TCC/TTC/TTT) inherit the same unbiasedness and bounded-variance guarantees with no change to the sampling core.
  • Under the same memory, HTCount-P samples more distinct hyperedges by splitting unused space, which the experiments connect to lower relative error, especially on skewed datasets like Congress-bills.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The correction-factor scheme is really a general recipe: any streaming sampler that can compute exact joint inclusion probabilities for the k hyperedges of a motif can be turned into an unbiased motif counter, so the design should transfer to four-vertex cliques or path motifs.
  • The hybrid-triangle signal observed in DBLP and MAG-Geology suggests a lightweight, online proxy for detecting cross-team collaboration onset; a testable extension is to compare hybrid-triangle growth rates against bibliometric measures of interdisciplinarity.
  • The partition threshold τ is currently a hand-tuned parameter; an adaptive rule that estimates the hyperedge-size distribution on the fly and sets τ accordingly could remove the last user input while preserving the variance gains.
  • Because the inner-triangle estimate is exact and the variance bounds depend on the ratio m/|G_s| per subset, the algorithms' accuracy should degrade gracefully with stream length; a natural stress test is to feed arbitrarily long streams with a fixed M and observe whether relative error stays bounded as predicted.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies triangle counting in hypergraph streams. It proposes a taxonomy of hyper-vertex triangles (inner, hybrid, outer), and two streaming algorithms: HTCount (Algorithm 1), a reservoir-based sampler that adapts sample size to a vertex-based memory budget M, and HTCount-P (Algorithm 2), a partition-based variant. The paper claims unbiased estimation of hyper-vertex and hyper-edge triangle counts (Theorems 4.3, 5.3, 6.1, 6.2), bounded variance (Theorems 4.4, 5.4), and superior empirical accuracy over HyperSV on eight real datasets. The correctness of all estimators rests on Lemma 4.2, which asserts that every hyperedge has equal marginal inclusion probability |G_s|/m at all times.

Significance. If the correctness results held, the paper would make a useful practical contribution: it gives a complete classification of hyper-vertex triangles, a memory-adaptive sampling scheme that avoids pre-specifying a sample size, and an extensive experimental evaluation on eight real hypergraphs, with reported relative errors 1–2 orders of magnitude below HyperSV. The case studies in Section 7.1 show that hybrid triangles capture interpretable collaboration patterns. However, the central theoretical guarantee—unbiasedness of HTCount and HTCount-P—rests on a false uniform-sampling lemma, and a concrete counterexample shows the published algorithm is biased. The taxonomy and case-study portions appear valuable independently, but the algorithmic claims as stated are not supported.

major comments (3)
  1. [§4.2.1, Lemma 4.2] The lemma is false under variable hyperedge sizes. The proof multiplies survival probabilities through the eviction loop but never conditions on the rejection branch or on the fact that |G_s| changes within the same step and is itself random. Counterexample: M=2, stream e1={v1}, e2={v2}, e3={v1,v2}. At t=3, e3 is sampled with probability (2/3)·(1/2)=1/3, while e1 and e2 each remain with probability 1/2; the final |G_s| is 2 w.p. 1/3 and 1 w.p. 2/3, so no value |G_s|/3 equals these probabilities. Since the correction factors θ and γ in Algorithm 1 (lines 8, 27–35) are defined as inverses of the probabilities claimed by the lemma, Theorem 4.3's unbiasedness proof collapses; Lemma 5.1 and Theorems 5.3, 5.4, 6.1, 6.2 inherit the error.
  2. [Algorithm 1, lines 14–21 and 6–9] SampleHyperedge returns true unconditionally after the while loop, even if the newly arrived edge e was evicted during that loop. UpdateTriangles is then invoked with e not in G_s, so hybrid/outer counts are updated for pairs and triples that are not simultaneously present in the final sample. Example: M=5, stream {a,b}, {c}, {d}, {e}, {a,b,x}. If the last edge is accepted but then evicted while a singleton edge is removed, the pair ({a,b},{a,b,x}) is still counted even though {a,b,x} is not in G_s. This is an additional source of estimator bias, independent of the faulty Lemma 4.2.
  3. [§4.2.2, proof of Theorem 4.4] The variance argument is internally incomplete even if Lemma 4.2 were correct. It introduces p=Pr(T_i≤T_M) without defining T_i or T_M, asserts E[X_i^2]=p+θ(1−p), and then replaces the joint term E[X_i X_j] with θ while summing it as 2c(c−1)θ. The displayed bound (2c²−c)θ−c² does not follow from these ingredients; the term involving p disappears without justification. The same pattern is used in Theorem 5.4. Thus the variance bounds are not established.
minor comments (5)
  1. [Definition 3.1 and Figure 3] The definition of a hybrid triangle includes configurations that are also inner triangles (e.g., {v3,v4,v5} in e5 is both inner and hybrid). The paper does not clarify whether the three triangle-type counts are intended to be disjoint and how overlaps are attributed in the estimators.
  2. [Algorithm 1, line 5] There appears to be a line-numbering/formatting glitch in the pseudocode: the inner-triangle update at line 5 is followed by a stray semicolon on line 6.
  3. [Theorem 5.3] The theorem statement contains a stray 'E' before 'where' and is otherwise poorly typeset, making the claim hard to parse.
  4. [Equation (1)] The notation P_c1 is introduced but not used in the subsequent text, and the case labels (i),(ii),(iii) collide with the triangle-index variables i and j. Clarify the cases and their relationship to the eventual bound.
  5. [Section 7.2, Exp-1] Relative error is reported as an average over 100 runs, but no standard deviation or variance is given. Given the failure of the variance proofs, reporting run-to-run dispersion would be informative.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the unbiasedness proof is a self-contained inverse-probability-weighting argument conditional on Lemma 4.2, with no fitted prediction or load-bearing self-citation.

full rationale

The paper's central derivation (Theorem 4.3) is a Horvitz-Thompson-style argument: Lemma 4.2 asserts that every hyperedge has marginal inclusion probability |G_s|/m, and the correction factors theta and gamma are the inverses of the two-edge and three-edge inclusion probabilities. This is not fitting the target triangle counts, renaming a known result, or defining a quantity in terms of the quantity being predicted. The sampling probabilities are properties of the reservoir procedure itself, not fitted parameters, and the proof does not import its conclusion through a self-citation. Inner triangles are counted exactly by the combinatorial formula, so unbiasedness there is definitionally exact but not circular in the problematic sense. HTCount-P's Lemma 5.1 reuses Lemma 4.2 subset-by-subset and applies the same inverse-probability correction; the structure is again self-contained given the lemma. Section 6's hyper-edge triangle extension uses the same gamma factor and adds no new fitted input. The paper cites prior work by overlapping authors (Yin et al. for the hyper-edge triangle taxonomy; Meng et al. for butterfly counting), but these citations are background, taxonomy, or evaluation-metric references; they do not serve as the load-bearing justification for the unbiasedness theorems, and no uniqueness theorem is invoked to forbid alternatives. One important caveat is a correctness concern rather than a circularity concern: the provided proof of Lemma 4.2 omits the rejection branch and the effect of variable-size evictions on the marginal inclusion probability. If that lemma is false, the algorithms are biased, but that would be a mathematical error in the proof, not a circular derivation. Under the circularity rubric, the paper's prediction chain does not reduce to its own inputs.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

The central claim rests on the standard reservoir-sampling theorem, but the paper applies it where the reservoir size is not constant. The only hand-tuned parameters are tau and N, which affect practical performance but not the theoretical unbiasedness argument. No new entities are postulated.

free parameters (2)
  • memory utilization threshold tau = 0.6-0.99 per dataset and sample size
    HTCount-P creates a new subset when utilization drops below tau; the paper tunes tau per dataset and memory size, with lower values for Congress-bills due to skew.
  • max number of subsets N = 10
    Set by hand as a balance between adaptivity and overhead; no principled derivation.
assumptions (3)
  • standard math Classical reservoir sampling gives each of the first m items equal inclusion probability k/m when the reservoir size k is constant.
    Invoked in Lemma 4.2's proof; the present algorithm generalizes to variable reservoir size, where the classical statement no longer applies.
  • domain assumption Insert-only hypergraph stream, no deletions, hyperedges arrive online.
    Problem statement Section 3 and Algorithm 1 process each hyperedge exactly once with no deletion; the estimator and proofs assume this.
  • domain assumption Memory M is measured in number of stored 32-bit vertices.
    Used to define M_s as sum of |e| and to compare with M; stated in Section 4.1.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Triangle Counting in Hypergraph Streams: A Complete and Practical Approach." pith.science (2026). https://pith.science/paper/FYNFSEDZ

@misc{pith2026250900674,
  author       = {Pith},
  title        = {Pith review of: Triangle Counting in Hypergraph Streams: A Complete and Practical Approach},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FYNFSEDZ}},
  note         = {Machine review of arXiv:2509.00674}
}
read the original 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 develop HTCount, a reservoir-based algorithm that dynamically adjusts the sample size based on the available memory M. To further improve memory utilization and reduce estimation error, we develop HTCount-P, a partition-based variant that adaptively partitions unused memory into independent sample subsets. 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 both our algorithms achieve highly accurate triangle count estimates under strict memory constraints, with relative errors that are 1 to 2 orders of magnitude lower than those of existing methods and consistently high throughput.

Figures

Figures reproduced from arXiv: 2509.00674 by the authors.

Figure 1
Figure 1. A Hypergraph Example networks [14, 42, 76], collaborative shopping networks [18, 71], and co-authorship networks [22, 78] [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Case Studies of the Co-authorship Network [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Hyper-vertex Triangles are tailored to static, traditional graphs and do not extend to the richer structure of hypergraphs. For hypergraphs, Yin et al. [78] introduced a taxonomy of hyper-edge triangle patterns and a two-step framework based on hyperwedges for efficient and accurate triangle counting. Triangle Counting over Streaming Graphs. TRIÈST [60] introduces a family of reservoir￾sampling algorithms for estima… view at source ↗
Figures from the paper (12 more)
Figure 4
Figure 4. Figure 4: Hyper-edge Triangles 𝑁𝑣𝑖 = {𝑣𝑗 ∈ 𝑉 | 𝐸𝑣𝑗 ∩ 𝐸𝑣𝑖 ≠ ∅} to represent all neighbors of 𝑣𝑖 . We define a subgraph 𝐻 ′ = (𝑉 ′ , 𝐸′ ) of a hypergraph 𝐻 = (𝑉 , 𝐸) as a hypergraph where 𝑉 ′ ⊆ 𝑉 and there exists an injective mapping 𝜙 : 𝐸 ′ → 𝐸 such that for each 𝑒 ′ ∈ 𝐸 ′ , we h…
Figure 5
Figure 5. Figure 5: An Example of Our Algorithms (𝑀 = 32, 𝜏 = 0.7) removed uniformly at random until the constraint is satisfied (lines 18-20). If the insertion is successful, it proceeds to update other triangle count estimates by examining intersections between the new hyperedge and the…
Figure 6
Figure 6. Figure 6: Triangle Counts from Real-world Datasets [PITH_FULL_IMAGE:figures/full_fig_p018_6.png]
Figure 7
Figure 7. Figure 7: The Number of Triangles over Time 2 10 2 11 2 12 2 13 2 14 2 15 2 16 2 17 2 18 2 19 2 20 10 2 10 1 10 0 Relative Error (a) MAG (M) 2 10 2 11 2 12 2 13 2 14 2 15 2 16 2 17 2 18 2 19 2 20 10 2 10 1 10 0 Relative Error (b) Walmart (M) 2 10 2 11 2 12 2 13 2 14 2 15 2 16 2 …
Figure 8
Figure 8. Figure 8: Relative Error of Hyper-vertex Triangle Counting under Different Sample Sizes [PITH_FULL_IMAGE:figures/full_fig_p019_8.png]
Figure 9
Figure 9. Figure 9: Relative Error of Hyper-edge Triangle Counting under Different Sample Sizes [PITH_FULL_IMAGE:figures/full_fig_p019_9.png]
Figure 6
Figure 6. Figure 6: By analyzing the distribution of triangles, we observe similar trends in DBLP and MAG-Geology: only inner and hybrid triangles exist, with TTT dominating hyper-edge classes. This indicates frequent cross-group collaboration and most collaborations occur between sub-tea…
Figure 10
Figure 10. Figure 10: Comparison of Memory Utilization (a) Congress-bills (b) DBLP [PITH_FULL_IMAGE:figures/full_fig_p021_10.png]
Figure 11
Figure 11. Figure 11: Memory Utilization and Relative Error over Time ( [PITH_FULL_IMAGE:figures/full_fig_p021_11.png]
Figure 12
Figure 12. Figure 12: Throughput over All Datasets 7.2 Performance Evaluations Exp-1: Accuracy. We assess the accuracy of hyper-vertex and hyper-edge triangle estimates across various algorithms and sample sizes ranging from 2 10 to 2 20. The “sample size” refers to the total number of ver…
Figure 13
Figure 13. Figure 13: The Estimated Number of Triangles over Time [PITH_FULL_IMAGE:figures/full_fig_p022_13.png]
Figure 14
Figure 14. Figure 14: Impact of Memory Utilization Threshold 𝜏 2 18 , 2 19, and 2 20. For the Congress-bills dataset, due to its highly skewed hyperedge size distribution, we use lower thresholds: 𝜏 = 0.6 for 2 10—2 12 , 𝜏 = 0.8 for 2 13—2 15, and 𝜏 = 0.9 for 2 16 and above. Each experimen…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

86 extracted references · 79 canonical work pages

  1. [1]

    Nesreen K Ahmed, Nick Duffield, Jennifer Neville, and Ramana Kompella. 2014. Graph sample and hold: A framework for big-graph analytics. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. 1446–1455

    2014

  2. [2]

    Mohammed Al-Kateb, Byung Suk Lee, and X Sean Wang. 2007. Adaptive-size reservoir sampling over data streams. In 19th International Conference on Scientific and Statistical Database Management (SSDBM 2007) . IEEE, 22–22

    2007

  3. [3]

    Dan Alistarh, Jennifer Iglesias, and Milan Vojnovic. 2015. Streaming min-max hypergraph partitioning. Advances in Neural Information Processing Systems 28 (2015)

    2015

  4. [4]

    Ilya Amburg, Nate Veldt, and Austin Benson. 2020. Clustering in graphs and hypergraphs with categorical edge labels. In Proceedings of the web conference 2020 . 706–717

    2020

  5. [5]

    Albert Atserias, Martin Grohe, and Dániel Marx. 2013. Size bounds and query plans for relational joins. SIAM J. Comput. 42, 4 (2013), 1737–1767. Proc. ACM Manag. Data, Vol. 0, No. 0, Article xxx. Publication date: 2025. Triangle Counting in Hypergraph Streams: A Complete and Practical Approach xxx:25

    2013

  6. [6]

    Austin R Benson, Rediet Abebe, Michael T Schaub, Ali Jadbabaie, and Jon Kleinberg. 2018. Simplicial closure and higher-order link prediction. Proceedings of the National Academy of Sciences 115, 48 (2018), E11221–E11230

    2018

  7. [7]

    Mauro Bisson and Massimiliano Fatica. 2017. High Performance Exact Triangle Counting on GPUs. IEEE Trans. Parallel Distributed Syst. 28, 12 (2017), 3501–3510

    work page 2017

  8. [8]

    Lu Chen, Yunjun Gao, Yuanliang Zhang, Christian S Jensen, and Bolong Zheng. 2019. Efficient and incremental clustering algorithms on star-schema heterogeneous graphs. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 256–267

    work page 2019

Show all 86 references
  1. [9]

    Lu Chen, Yunjun Gao, Yuanliang Zhang, Sibo Wang, and Baihua Zheng. 2018. Scalable hypergraph-based image retrieval and tagging system. In 2018 IEEE 34th International Conference on Data Engineering (ICDE) . IEEE, 257–268

    2018

  2. [10]

    Zi Chen, Bo Feng, Long Yuan, Xuemin Lin, and Liping Wang. 2023. Fully Dynamic Contraction Hierarchies with Label Restrictions on Road Networks. Data Sci. Eng. 8, 3 (2023), 263–278

    2023

  3. [11]

    Philip S Chodrow, Nate Veldt, and Austin R Benson. 2021. Generative hypergraph clustering: From blockmodels to modularity. Science Advances 7, 28 (2021), eabh1303

    2021

  4. [12]

    Mathijs De Vaan, David Stark, and Balazs Vedres. 2015. Game changer: The topology of creativity. Amer. J. Sociology 120, 4 (2015), 1144–1194

    2015

  5. [13]

    Seshadhri

    Talya Eden, Amit Levi, Dana Ron, and C. Seshadhri. 2015. Approximately Counting Triangles in Sublinear Time. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS . 614–633

    2015

  6. [14]

    Song Feng, Emily Heath, Brett Jefferson, Cliff Joslyn, Henry Kvinge, Hugh D Mitchell, Brenda Praggastis, Amie J Eisfeld, Amy C Sims, Larissa B Thackray, et al. 2021. Hypergraph models of biological networks to identify genes critical to pathogenic viral response. BMC bioinform...

    2021

  7. [15]

    Yunjun Gao, Ziquan Fang, Jiachen Xu, Shenghao Gong, Chunhui Shen, and Lu Chen. 2023. An efficient and distributed framework for real-time trajectory stream clustering. IEEE Transactions on Knowledge and Data Engineering 36, 5 (2023), 1857–1873

    2023

  8. [16]

    Yunjun Gao, Xiaoye Miao, Gang Chen, Baihua Zheng, Deng Cai, and Huiyong Cui. 2017. On efficiently finding reverse k-nearest neighbors over uncertain graphs. The VLDB journal 26, 4 (2017), 467–492

    2017

  9. [17]

    Xiangyang Gou and Lei Zou. 2021. Sliding window-based approximate triangle counting over streaming graphs with duplicate edges. In Proceedings of the 2021 International Conference on Management of Data . 645–657

    2021

  10. [18]

    Yan Han, Edward W Huang, Wenqing Zheng, Nikhil Rao, Zhangyang Wang, and Karthik Subbian. 2023. Search behavior prediction: A hypergraph perspective. In Proceedings of the sixteenth acm international conference on web search and data mining . 697–705

    2023

  11. [19]

    Kongzhang Hao, Long Yuan, Zhengyi Yang, Wenjie Zhang, and Xuemin Lin. 2023. Efficient and scalable distributed graph structural clustering at billion scale. In International Conference on Database Systems for Advanced Applications . Springer, 234–251

    2023

  12. [20]

    Howie Huang

    Yang Hu, Hang Liu, and H. Howie Huang. 2018. TriCore: parallel triangle counting on GPUs. In Proceedings of SC. IEEE / ACM, 14:1–14:12

    2018

  13. [21]

    Jianqiang Huang, Haojie Wang, Xiang Fei, Xiaoying Wang, and Wenguang Chen. 2022. $TC-Stream$TC-Stream: Large-Scale Graph Triangle Counting on a Single Machine Using GPUs. IEEE Trans. Parallel Distributed Syst. 33, 11 (2022), 3067–3078

    2022

  14. [22]

    Masaaki Inoue, Thong Pham, and Hidetoshi Shimodaira. 2022. A hypergraph approach for estimating growth mechanisms of complex networks. IEEE Access 10 (2022), 35012–35025

    2022

  15. [23]

    Madhav Jha, Comandur Seshadhri, and Ali Pinar. 2013. A space efficient streaming algorithm for triangle counting using the birthday paradox. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. 589–597

    2013

  16. [24]

    Jiaqi Jin, Ziquan Fang, Lu Chen, and Yunjun Gao. 2025. PostMan: A Productive System for Spatio-temporal Data Management and Analysis. Data Science and Engineering (2025), 1–24

    2025

  17. [25]

    Jonas L Juul, Austin R Benson, and Jon Kleinberg. 2024. Hypergraph patterns and collaboration structure. Frontiers in Physics 11 (2024), 1301994

    2024

  18. [26]

    John Kallaugher, Michael Kapralov, and Eric Price. 2018. The sketching complexity of graph and hypergraph counting. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) . IEEE, 556–567

    2018

  19. [27]

    John Kallaugher and Eric Price. 2017. A hybrid sampling scheme for triangle counting. In Proceedings of the Twenty- Eighth Annual ACM-SIAM Symposium on Discrete Algorithms . SIAM, 1778–1797

    2017

  20. [28]

    Jihoon Ko, Yunbum Kook, and Kijung Shin. 2022. Growth patterns and models of real-world hypergraphs. Knowledge and Information Systems 64, 11 (2022), 2883–2920

    2022

  21. [29]

    Kuldeep Kurte, Neena Imam, SM Shamimul Hasan, and Ramakrishnan Kannan. 2021. Phoenix: A scalable streaming hypergraph analysis framework. In Advances in data science and information engineering: proceedings from ICDATA 2020 and IKE 2020 . Springer, 3–25. Proc. ACM Manag. Data,...

    2021

  22. [30]

    Matthieu Latapy. 2008. Main-memory triangle computations for very large (sparse (power-law)) graphs.Theor. Comput. Sci. 407, 1-3 (2008), 458–473

    2008

  23. [31]

    Dongjin Lee, Kijung Shin, and Christos Faloutsos. 2020. Temporal locality-aware sampling for accurate triangle counting in real graph streams. VLDB J. 29, 6 (2020), 1501–1525

    2020

  24. [32]

    Geon Lee, Fanchen Bu, Tina Eliassi-Rad, and Kijung Shin. 2025. A survey on hypergraph mining: Patterns, tools, and generators. Comput. Surveys 57, 8 (2025), 1–36

    2025

  25. [33]

    Geon Lee, Jihoon Ko, and Kijung Shin. 2020. Hypergraph motifs: concepts, algorithms, and discoveries. Proc. VLDB Endow. 13, 12 (July 2020), 2256–2269

    2020

  26. [34]

    Geon Lee and Kijung Shin. 2023. Temporal hypergraph motifs. Knowledge and Information Systems 65, 4 (2023), 1549–1586

    2023

  27. [35]

    Geon Lee, Jaemin Yoo, and Kijung Shin. 2022. Mining of real-world hypergraphs: Patterns, tools, and generators. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management . 5144–5147

    2022

  28. [36]

    Dong Li, Zhiming Xu, Sheng Li, and Xin Sun. 2013. Link prediction in social networks based on hypergraph. In Proceedings of the 22nd international conference on world wide web . 41–42

    2013

  29. [37]

    Yongsub Lim and U Kang. 2015. Mascot: Memory-efficient and accurate sampling for counting local triangles in graph streams. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining . 685–694

    2015

  30. [38]

    Qing Liu, Xuankun Liao, Xin Huang, Jianliang Xu, and Yunjun Gao. 2023. Distributed (𝛼,𝛽)-core decomposition over bipartite graphs. In 2023 IEEE 39th International Conference on Data Engineering (ICDE) . IEEE, 909–921

    2023

  31. [39]

    Qing Liu, Minjun Zhao, Xin Huang, Jianliang Xu, and Yunjun Gao. 2020. Truss-based community search over large directed graphs. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data . 2183–2197

    2020

  32. [40]

    Qing Liu, Yifan Zhu, Minjun Zhao, Xin Huang, Jianliang Xu, and Yunjun Gao. 2020. VAC: vertex-centric attributed community search. In 2020 IEEE 36th International Conference on Data Engineering (ICDE) . IEEE, 937–948

    2020

  33. [41]

    Quintino Francesco Lotito, Federico Musciotto, Alberto Montresor, and Federico Battiston. 2022. Higher-order motif analysis in hypergraphs. Communications Physics 5, 1 (2022), 79

    2022

  34. [42]

    Jose Lugo-Martinez, Daniel Zeiberg, Thomas Gaudelet, Noël Malod-Dognin, Natasa Przulj, and Predrag Radivojac

  35. [43]

    Qi Luo, Wenjie Zhang, Zhengyi Yang, Dong Wen, Xiaoyang Wang, Dongxiao Yu, and Xuemin Lin. 2024. Hierarchical structure construction on hypergraphs. In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management. 1597–1606

    2024

  36. [44]

    Qi Luo, Wenjie Zhang, Zhengyi Yang, Dongxiao Yu, Xuemin Lin, and Liping Wang. 2025. Efficient indexing and searching of constrained core in hypergraphs. The VLDB Journal 34, 3 (2025), 34

    2025

  37. [45]

    Lingkai Meng, Yu Shao, Long Yuan, Longbin Lai, Peng Cheng, Xue Li, Wenyuan Yu, Wenjie Zhang, Xuemin Lin, and Jingren Zhou. 2024. A survey of distributed graph algorithms on massive graphs. Comput. Surveys 57, 2 (2024), 1–39

    2024

  38. [46]

    Lingkai Meng, Yu Shao, Long Yuan, Longbin Lai, Peng Cheng, Xue Li, Wenyuan Yu, Wenjie Zhang, Xuemin Lin, and Jingren Zhou. 2025. Revisiting Graph Analytics Benchmark. Proceedings of the ACM on Management of Data 3, 3 (2025), 1–28

    2025

  39. [47]

    Lingkai Meng, Long Yuan, Zi Chen, Xuemin Lin, and Shiyu Yang. 2022. Index-based structural clustering on directed graphs. In 2022 IEEE 38th International Conference on Data Engineering (ICDE) . IEEE, 2831–2844

    2022

  40. [48]

    Lingkai Meng, Long Yuan, Xuemin Lin, Chengjie Li, Kai Wang, and Wenjie Zhang. 2024. Counting Butterflies over Streaming Bipartite Graphs with Duplicate Edges. arXiv preprint arXiv:2412.11488 (2024)

    2024 arXiv

  41. [49]

    Li, Lingda Li, Adolfy Hoisie, Caiwen Ding, Dong Li, and Hang Liu

    Santosh Pandey, Zhibin Wang, Sheng Zhong, Chen Tian, Bolong Zheng, Xiaoye S. Li, Lingda Li, Adolfy Hoisie, Caiwen Ding, Dong Li, and Hang Liu. 2021. Trust: Triangle Counting Reloaded on GPUs. IEEE Trans. Parallel Distributed Syst. 32, 11 (2021), 2646–2660

    2021

  42. [50]

    David A Papa and Igor L Markov. 2007. Hypergraph Partitioning and Clustering.Handbook of Approximation Algorithms and Metaheuristics 20073547 (2007), 61–1

    2007

  43. [52]

    Serafeim Papadias, Zoi Kaoudi, Varun Pandey, Jorge-Arnulfo Quiané-Ruiz, and Volker Markl. 2024. Counting butterflies in fully dynamic bipartite graph streams. In 2024 IEEE 40th International Conference on Data Engineering (ICDE) . IEEE, 2917–2930

    2024

  44. [53]

    Pulak Purkait, Tat-Jun Chin, Alireza Sadri, and David Suter. 2016. Clustering with hypergraphs: the case for large hyperedges. IEEE transactions on pattern analysis and machine intelligence 39, 9 (2016), 1697–1711

    2016

  45. [54]

    Kaushik Ravichandran, Akshara Subramaniasivam, P. S. Aishwarya, and N. S. Kumar. 2023. Chapter Eight - Fast exact triangle counting in large graphs using SIMD acceleration. Adv. Comput. 128 (2023), 233–250. Proc. ACM Manag. Data, Vol. 0, No. 0, Article xxx. Publication date: 2...

    2023

  46. [55]

    Henrik Reinstädtler, SM Ferdous, Alex Pothen, Bora Uçar, and Christian Schulz. 2025. Semi-streaming algorithms for hypergraph matching. arXiv preprint arXiv:2502.13636 (2025)

    2025 arXiv

  47. [56]

    Thomas Schank and Dorothea Wagner. 2005. Finding, counting and listing all triangles in large graphs, an experimental study. In International workshop on experimental and efficient algorithms . Springer, 606–609

    2005

  48. [57]

    Tamer Özsu

    Aida Sheshbolouki and M. Tamer Özsu. 2022. sGrapp: Butterfly Approximation in Streaming Graphs. ACM Trans. Knowl. Discov. Data 16, 4 (2022), 76:1–76:43

    2022

  49. [58]

    Kijung Shin, Sejoon Oh, Jisu Kim, Bryan Hooi, and Christos Faloutsos. 2020. Fast, accurate and provable triangle counting in fully dynamic graph streams. ACM Transactions on Knowledge Discovery from Data (TKDD) 14, 2 (2020), 1–39

    2020

  50. [59]

    Arnab Sinha, Zhihong Shen, Yang Song, Hao Ma, Darrin Eide, Bo-June Hsu, and Kuansan Wang. 2015. An overview of microsoft academic service (mas) and applications. In Proceedings of the 24th international conference on world wide web. 243–246

    2015

  51. [60]

    Lorenzo De Stefani, Alessandro Epasto, Matteo Riondato, and Eli Upfal. 2017. Triest: Counting local and global triangles in fully dynamic streams with fixed memory size. ACM Transactions on Knowledge Discovery from Data (TKDD) 11, 4 (2017), 1–50

    2017

  52. [61]

    Fatih Taşyaran, Berkay Demireller, Kamer Kaya, and Bora Uçar. 2021. Streaming hypergraph partitioning algorithms on limited memory environments. arXiv preprint arXiv:2103.05394 (2021)

    2021 arXiv

  53. [62]

    Charalampos E Tsourakakis, U Kang, Gary L Miller, and Christos Faloutsos. 2009. Doulion: counting triangles in massive graphs with a coin. 837–846 pages

    2009

  54. [63]

    Ata Turk and Duru T¨"urkoglu. 2019. Revisiting Wedge Sampling for Triangle Counting. In Proceedings of WWW . ACM, 1875–1885

    2019

  55. [64]

    Balazs Vedres and David Stark. 2010. Structural folds: Generative disruption in overlapping groups. American journal of sociology 115, 4 (2010), 1150–1190

    2010

  56. [65]

    Jeffrey S Vitter. 1985. Random sampling with a reservoir. ACM Transactions on Mathematical Software (TOMS) 11, 1 (1985), 37–57

    1985

  57. [66]

    Pinghui Wang, Yiyan Qi, Yu Sun, Xiangliang Zhang, Jing Tao, and Xiaohong Guan. 2017. Approximately counting triangles in large graph streams including edge duplicates with a fixed memory usage. Proceedings of the VLDB Endowment 11, 2 (2017), 162–175

    2017

  58. [67]

    Xinzhou Wang, Yinjia Chen, Zhiwei Zhang, PengPeng Qiao, and Guoren Wang. 2022. Efficient truss computation for large hypergraphs. In International Conference on Web Information Systems Engineering . Springer, 290–305

    2022

  59. [68]

    Xufei Wang, Lei Tang, Huiji Gao, and Huan Liu. 2010. Discovering overlapping groups in social media. In 2010 IEEE international conference on data mining . IEEE, 569–578

    2010

  60. [69]

    Xueyan Wang, Jianlei Yang, Yinglin Zhao, Yingjie Qi, Meichen Liu, Xingzhou Cheng, Xiaotao Jia, Xiaoming Chen, Gang Qu, and Weisheng Zhao. 2020. TCIM: Triangle Counting Acceleration With Processing-In-MRAM Architecture. In 57th ACM/IEEE Design Automation Conference, DAC 2020 . ...

    2020

  61. [70]

    Bin Wu, Ke Yi, and Zhenguo Li. 2016. Counting Triangles in Large Graphs by Random Sampling. IEEE Trans. Knowl. Data Eng. 28, 8 (2016), 2013–2026

    2016

  62. [71]

    Hanrui Wu, Yuguang Yan, and Michael Kwok-Po Ng. 2022. Hypergraph collaborative network on vertices and hyperedges. IEEE Transactions on Pattern Analysis and Machine Intelligence 45, 3 (2022), 3245–3258

    2022

  63. [72]

    Xiaowei Xu, Nurcan Yuruk, Zhidan Feng, and Thomas AJ Schweiger. 2007. Scan: a structural clustering algorithm for networks. In Proceedings of SIGKDD. 824–833

    2007

  64. [73]

    Wei Xuan, Yan Liang, Huawei Cao, Ning Lin, Xiaochun Ye, and Dongrui Fan. 2024. DTC: Real-Time and Accurate Distributed Triangle Counting in Fully Dynamic Graph Streams. In 2024 43rd International Symposium on Reliable Distributed Systems (SRDS). IEEE, 198–209

    2024

  65. [74]

    Xu Yang, Chao Song, Jiqing Gu, Ke Li, and Hongwei Li. 2023. A distributed streaming framework for edge-cloud triangle counting in graph streams. Knowl. Based Syst. 278 (2023), 110878

    2023

  66. [75]

    Xu Yang, Chao Song, Mengdi Yu, Jiqing Gu, and Ming Liu. 2022. Distributed Triangle Approximately Counting Algorithms in Simple Graph Stream. ACM Trans. Knowl. Discov. Data 16, 4 (2022), 79:1–79:43

    2022

  67. [76]

    Zhengyi Yang, Wenjie Zhang, Xuemin Lin, Ying Zhang, and Shunyang Li. 2023. Hgmatch: A match-by-hyperedge approach for subgraph matching on hypergraphs. In 2023 IEEE 39th International Conference on Data Engineering (ICDE). IEEE, 2063–2076

    2023

  68. [77]

    Umit V. Çataly¨

    Abdurrahman Yasar, Sivasankaran Rajamanickam, Jonathan W. Berry, and¨"Umit V. Çataly¨"urek. 2022. A Block-Based Triangle Counting Algorithm on Heterogeneous Environments. IEEE Trans. Parallel Distributed Syst. 33, 2 (2022), 444–458

    2022

  69. [78]

    Haozhe Yin, Kai Wang, Wenjie Zhang, Ying Zhang, Ruijia Wu, and Xuemin Lin. 2024. Efficient Computation of Hyper-Triangles on Hypergraphs. Proceedings of the VLDB Endowment 18, 3 (2024), 729–742. Proc. ACM Manag. Data, Vol. 0, No. 0, Article xxx. Publication date: 2025. xxx:28 ...

    2024

  70. [79]

    Michael Yu, Lu Qin, Ying Zhang, Wenjie Zhang, and Xuemin Lin. 2020. Aot: Pushing the efficiency boundary of main-memory triangle listing. In International Conference on Database Systems for Advanced Applications . Springer, 516–533

    2020

  71. [80]

    Long Yuan, Xiaotong Sun, Zi Chen, Peng Cheng, Longbin Lai, and Xuemin Lin. 2025. HINSCAN: Efficient Structural Graph Clustering over Heterogeneous Information Networks. In 2025 IEEE 41st International Conference on Data Engineering (ICDE). IEEE Computer Society, 278–291

    2025

  72. [81]

    Long Yuan, Zeyu Zhou, Zi Chen, Xuemin Lin, Xiang Zhao, and Fan Zhang. 2025. GPUSCAN++: Efficient Structural Graph Clustering on GPUs. IEEE Transactions on Parallel and Distributed Systems (2025)

    2025

  73. [82]

    Yuanyuan Zeng, Kenli Li, Xu Zhou, Wensheng Luo, and Yunjun Gao. 2021. An efficient index-based approach to distributed set reachability on small-world graphs. IEEE Transactions on Parallel and Distributed Systems 33, 10 (2021), 2358–2371

    2021

  74. [83]

    Lingling Zhang, Zhiwei Zhang, Guoren Wang, Ye Yuan, and Kangfei Zhao. 2023. Efficiently Counting Triangles for Hypergraph Streams by Reservoir-Based Sampling. IEEE Transactions on Knowledge and Data Engineering 35, 11 (2023), 11328–11341

    2023

  75. [84]

    Tianming Zhang, Yunjun Gao, Jie Zhao, Lu Chen, Lu Jin, Zhengyi Yang, Bin Cao, and Jing Fan. 2024. Efficient exact and approximate betweenness centrality computation for temporal graphs. In Proceedings of the ACM Web Conference

    2024

  76. [85]

    Wenqian Zhang, Zhengyi Yang, Dong Wen, Wentao Li, Wenjie Zhang, and Xuemin Lin. 2025. Accelerating core decomposition in billion-scale hypergraphs. Proceedings of the ACM on Management of Data 3, 1 (2025), 1–27

    2025

  77. [86]

    Jianming Zhu, Junlei Zhu, Smita Ghosh, Weili Wu, and Jing Yuan. 2018. Social influence maximization in hypergraph in social networks. IEEE Transactions on Network Science and Engineering 6, 4 (2018), 801–811. Received April 2025; revised July 2025; accepted August 2025 Proc. A...

    2018

  78. [2021]

    Bioinformatics 37, 7 (2021), 1000–1007

    Classification in biological networks with hypergraphlet kernels. Bioinformatics 37, 7 (2021), 1000–1007

    2021

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.