{"id":"482967c5-0844-4339-a6ac-a621656d61e6","arxiv_id":"2509.00674","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"New algorithms HTCount and HTCount-P estimate hyper-triangle counts under memory limits, but their unbiasedness proof relies on a uniform-sampling lemma that fails when hyperedge sizes vary.","lead":"Streaming triangle counting over hypergraphs got two new memory-adaptive estimators, HTCount and HTCount-P, plus a proposed hybrid triangle class. But the paper's proof that these estimators are unbiased rests on a sampling lemma that is not correct, so the central theoretical guarantee does not hold as stated.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.2 is false under variable hyperedge sizes; a 5-edge stream with M=5 yields expected hybrid estimate 2.5 instead of true 1, so the unbiasedness theorems fail.","rationale":"The reader's weakest assumption, Lemma 4.2, is indeed the load-bearing point, and the reader's counterexample already falsifies that lemma. My own 5-edge example goes further: it shows the algorithm is actually biased under the pseudocode as written, not merely that the proof is incomplete. The correction factors θ and γ are inverse sampling probabilities only if Lemma 4.2 holds; with variable hyperedge sizes, the marginal inclusion probabilities are unequal and the final sample size is random, so the inverse-correction argument collapses. The update-after-eviction behavior in Algorithm 1 makes the bias concrete and easy to test. The taxonomy contribution and the experimental study may still have empirical value as heuristics, but the paper's theoretical contribution—unbiased estimation with bounded variance—is not supported. No formal verification or released code is provided to offset this. Therefore the REJECT verdict should stand unchanged.","tokens_in":29351,"tokens_out":18544,"duration_ms":225520,"concrete_test":"Simulate Algorithm 1 exactly as written on the 5-edge stream (M=5) for 10^6 independent runs, reporting the average hybrid triangle estimate. The average should be approximately 2.5, not the true value 1. As a second check, brute-force enumerate all random choices (rejection, deletion, evictions) and compute the expectation analytically; this will confirm the 2.5 value. If the authors intend UpdateTriangles to run only when the new edge survives the while loop, the pseudocode must be changed and the theorems reproved under that semantics.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 4.2 claims every hyperedge has marginal inclusion probability |G_s|/m, and Theorem 4.3 relies on it to justify the correction factors θ and γ. The proof only multiplies survival probabilities through the eviction loop and never accounts for the rejection branch or for the fact that the sample size |G_s| itself becomes random when variable-size hyperedges trigger multiple evictions. The claim is false: for M=2 and a stream with edge sizes 1,1,2, the large edge has inclusion probability 1/3 while the two size-1 edges each have probability 1/2, not the common |G_s|/m. The failure is not merely a proof gap. Algorithm 1 as written calls UpdateTriangles even when the newly arrived edge was evicted in the while loop (lines 18-21), so it counts pairs whose two hyperedges are not simultaneously in the final sample. Concrete stream: M=5, e1={a,b}, e2={c}, e3={d}, e4={e}, e5={a,b,x}. True hybrid count is 1. At t=5, with probability 4/5 the new edge is accepted; if a size-1 edge is evicted (prob 3/4), the while loop sometimes keeps e1 but evicts e5, and the code still records the e1-e5 hybrid triangle. The expected estimate is (4/5)(3/4)[(1/4)(10/3)+(1/2)(2/3)(10)] = 2.5, strictly greater than 1. Thus the central advertised unbiasedness guarantee is contradicted by the published algorithm.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":29762,"tokens_out":6883,"duration_ms":83140,"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":[{"comment":"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.","section":"§4.2.1, Lemma 4.2"},{"comment":"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.","section":"Algorithm 1, lines 14–21 and 6–9"},{"comment":"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.","section":"§4.2.2, proof of Theorem 4.4"}],"minor_comments":[{"comment":"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.","section":"Definition 3.1 and Figure 3"},{"comment":"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.","section":"Algorithm 1, line 5"},{"comment":"The theorem statement contains a stray 'E' before 'where' and is otherwise poorly typeset, making the claim hard to parse.","section":"Theorem 5.3"},{"comment":"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.","section":"Equation (1)"},{"comment":"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.","section":"Section 7.2, Exp-1"}],"recommendation":"reject","confidential_remarks":"The rejection is driven by a concrete counterexample to Lemma 4.2, not by disagreement with the paper's goals or by stylistic preferences. Correcting the issue would require either a new derivation of exact inclusion probabilities for the variable-size eviction process or a redesign of the sampler, which is beyond a routine revision. The taxonomy and case studies could potentially be published separately as an analytical/empirical contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper's new classification of hyper-vertex triangles into inner, hybrid, and outer is genuinely useful, and the case studies show hybrid triangles are common in real co-authorship data. The memory-adaptive reservoir and the partition-based variant are reasonable engineering ideas, and the experiments on eight datasets are careful and clearly presented. That is the good part.\n\nThe bad part is the theory. Lemma 4.2, which claims every hyperedge has marginal inclusion probability |G_s|/m at all times, is simply false when hyperedge sizes vary. The proof only tracks survival through the eviction loop and never accounts for the rejection branch or for the fact that |G_s| itself becomes a random variable when a large edge causes multiple evictions in one step. A 3-edge stream with M=2 and sizes 1,1,2 gives inclusion probabilities 1/2, 1/2, 1/3, while |G_s|/m is 4/9. The stress-test counterexample with M=5 is also correct: Algorithm 1 calls UpdateTriangles even when the incoming edge was evicted in the while loop, so it counts triangles whose two hyperedges are not simultaneously in the final sample. That produces an expected estimate of 2.5 for a true hybrid count of 1. This is not a gap in one lemma; it kills Theorems 4.3, 4.4, 5.3, 5.4, 6.1, and 6.2, because the correction factors θ and γ are exactly the inverses of these wrongly computed probabilities.\n\nSo the central advertised contribution, unbiased estimation with bounded variance, does not hold as stated. The experiments may still show that the method works well in practice, but the paper's own framing is as a provable streaming algorithm, and that framing is wrong. The variance bounds are also not justified once the inclusion probabilities are wrong.\n\nWho is this for? Readers interested in hypergraph motif taxonomies might get value from the definitions and the empirical case studies. But anyone looking for a correct streaming triangle-counting estimator should not rely on this paper's theorems.\n\nMy recommendation: send it to peer review, because the taxonomy and experiments are substantive enough that an editor would not desk-reject it. But it needs major revision. The authors should either fix the sampling analysis, which seems hard given the variable-size eviction, or honestly reposition the method as a heuristic and remove the unbiasedness claims. As it stands, the load-bearing proofs are false.","headline":"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.","tokens_in":30199,"tokens_out":5371,"would_cite":false,"duration_ms":60093,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["hypergraph streams","triangle counting","reservoir sampling","memory-aware sampling","hyper-vertex triangles","hyper-edge triangles","unbiased estimation","streaming algorithms"],"falsifier":"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.","tokens_in":29284,"feed_emoji":"🔺","tokens_out":9567,"duration_ms":109207,"temperature":0.7,"pith_summary":"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.","feed_headline":"Adaptive sampler keeps hypergraph triangle counts unbiased","feed_subtitle":"One-pass sampler adapts to variable edge sizes, covering inner, hybrid, and outer hypergraph triangles under memory limits.","key_machinery":"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","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the prior reservoir-based hypergraph triangle counter whose fixed sample size and missing hybrid-triangle distinction motivate the new memory-adaptive algorithms.","marker":"[83]"},{"why":"Supplies the four-class CCC/TCC/TTC/TTT taxonomy of hyper-edge triangles that the paper adopts and counts.","marker":"[78]"},{"why":"Adaptive-size reservoir sampling that the paper contrasts with; its inability to guarantee strict unbiasedness motivates the partition variant.","marker":"[2]"},{"why":"Classical reservoir sampling theory that underlies the uniform-inclusion probability lemma on which the correction factors depend.","marker":"[65]"},{"why":"Reservoir-based streaming triangle counting framework whose correction-factor argument is adapted to hypergraph streams.","marker":"[60]"}],"fun_headline_variants":["Memory-sized reservoir counts all hypergraph triangles","Single-pass triangle counting for hypergraphs with adaptive memory","Complete triangle classification meets adaptive stream sampling","Unbiased triangle counts for hypergraphs under tight memory","One-pass counter for inner, hybrid, and outer hypergraph triangles"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Memory-sized reservoir counts all hypergraph triangles","Single-pass triangle counting for hypergraphs with adaptive memory","Complete triangle classification meets adaptive stream sampling","Unbiased triangle counts for hypergraphs under tight memory","One-pass counter for inner, hybrid, and outer hypergraph triangles"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000692,"raw_usage":{"total_tokens":2977,"prompt_tokens":759,"completion_tokens":2218,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":503,"completion_tokens_details":{"reasoning_tokens":2144}},"tokens_in":503,"tokens_out":2218,"duration_ms":20957,"temperature":1.0,"reasoning_tokens":2144,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T13:21:28.186255+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the prior reservoir-based hypergraph triangle counter whose fixed sample size and missing hybrid-triangle distinction motivate the new memory-adaptive algorithms."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the four-class CCC/TCC/TTC/TTT taxonomy of hyper-edge triangles that the paper adopts and counts."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Classical reservoir sampling theory that underlies the uniform-inclusion probability lemma on which the correction factors depend."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Reservoir-based streaming triangle counting framework whose correction-factor argument is adapted to hypergraph streams."}],"review_version":1}