Hyperedge Estimation using Polylogarithmic Subset Queries

Anup Bhattacharya; Arijit Bishnu; Arijit Ghosh; Gopinath Mishra

REVIEW 3 major objections 5 minor 18 references

Hyperedge Estimation using Polylogarithmic Subset Queries

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

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

Pith's one-line read For every fixed d, the number of hyperedges in a d-uniform hypergraph can be estimated within a (1±epsilon) factor using only polylogarithmically many GPIS queries, with no dependence on hyperedge intersection multiplicity.

desk verdict The reported log-exponent flaw in Lemma 4.1 doesn't survive contact with the equation; the c_t bound already puts log^{d-1} inside the square root, so delta comes out with log^{d/2}. The paper's central claim looks sound and deserves real review. read the letter →

arxiv 1908.04196 v4 pith:EYYMCNRE submitted 2019-08-12 cs.DS

Anup Bhattacharya , Arijit Bishnu , Arijit Ghosh , Gopinath Mishra This is my paper · ORCID

classification cs.DS MSC 05C6568Q2568W20

keywords hypergraphestimationGPISoraclesubsetqueriesrandomizedalgorithmssparsificationquerycomplexityd-uniformhypergraphspolylogarithmic

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

The paper tries to establish that, for any fixed uniformity d, the number of hyperedges in a d-uniform hypergraph can be approximated to within a (1±epsilon) factor using only O_d($log^{{5d+5}}$ n / $epsilon^{4}$) yes/no queries to a Generalized d-partite Independent Set (GPIS) oracle, with high probability. This would extend edge and triangle estimation to hypergraphs while removing the earlier need to bound how many hyperedges can share an edge. It would mean that even with complicated intersection patterns, a randomized coloring can sparsify the hypergraph into manageable pieces while approximately preserving the total count. The proof's engine is a sparsification lemma asserting concentration of the number of properly colored ordered hyperedges around its mean.

What carries the argument

The load-bearing object is the sparsification lemma (Lemma 4.1). It colors the vertices of a d-uniform hypergraph with k colors and uses an independent hash bit h_d(c_1,...,c_d) for each d-tuple of colors, defining a properly colored ordered hyperedge as one whose vertex colors form a tuple with hash value 1. The count R_d of properly colored ordered hyperedges has expectation mo($A_1^{{[a_1]}}$,...,$A_s^{{[a_s]}}$)/k, and the lemma claims a concentration bound of order $\sqrt$(m log^d n) with high probability. This is what lets the algorithm replace a dense d-partite subhypergraph by roughly k independent sparse pieces, each of whose counts can be handled exactly or coarsely; the d-fold recursion in the proof of the lemma is what removes the earlier dependence on the maximum number of hyperedges sharing an edge.

What would settle it

Recompute the averaged-bounded-differences step in the proof of Lemma 4.1. Since c_t = $2^{{2d-1}}$ $theta^{{d-1}}$ $\sqrt$(d! |F_o(t)| $log^{{d-1}}$ n), the sum over t of $c_t^{2}$ is of order m_0(A) $log^{{2d-1}}$ n, not m_0(A) log^d n. Setting delta = $\sqrt$(sum_t $c_t^{2}$) therefore gives a deviation of order $\sqrt$(m_0(A)) $log^{{d-1/2}}$ n, while the printed lemma's bound is $\sqrt$(m_0(A)) $log^{{d/2}}$ n. Checking this calculation either confirms the printed bound or shows that the sparsification guarantee, and hence the theorem's query count, needs a larger log exponent.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.2: for any epsilon in (0,1), Hyperedge-Estimation can be solved using O_d($log^{{5d+5}}$ n / $epsilon^{4}$) GPIS queries with high probability, where the hidden constant depends only on d. The underlying discovery is a sparsification routine for arbitrary d-uniform hypergraphs. Vertices are colored uniformly at random with k colors, and a hash function h_d on d-tuples of colors independently decides which color combinations count as proper; the number R_d of properly colored ordered hyperedges has expectation m/k. The paper argues that R_d concentrates near m/k, so scaling by k gives a good estimate, and the argument recurses on d by fixing one vertex at a time. Around this sparsification step, the algorithm alternates exact counting for sparse subhypergraphs, coarse estimation via sampled verification, and importance sampling to keep the number of subhypergraphs bounded, yielding the polylogarithmic query bound.

Load-bearing premise

The entire query bound rests on the sparsification lemma's concentration inequality, which states that the number of properly colored hyperedges stays within roughly $\sqrt$(m log^d n) of its expectation; if the true deviation is larger, the thresholds and final query count do not follow.

Editorial extensions

If this is right

For any fixed d, hyperedge counts become accessible with only polylogarithmically many GPIS queries, independent of the number of hyperedges or their intersection multiplicities.
The result generalizes edge and triangle estimation to d-uniform hypergraphs, providing a single query framework for all d.
The sparsification routine itself is a reusable tool for turning dense uniform hypergraphs into sparse pieces while preserving approximate counts.
The algorithm's query complexity is O_d(log^{5d+5} n / epsilon^4), so for constant d it remains polylogarithmic in n and polynomial in 1/epsilon.

Reading between the lines

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

The same color-tuple hashing idea may apply to counting copies of fixed small subhypergraphs, not only all d-uniform hyperedges, by choosing the hash domain to match the pattern being counted.
One could try to derandomize the coloring with small sample spaces, which would turn the high-probability query algorithm into a deterministic one.
Identifying the exact dependence on d would clarify whether the polylogarithmic exponent is close to optimal for this oracle model.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Colleague,

Short version: the central objection in the report is, as far as I can tell, wrong. The claimed log-exponent gap in Lemma 4.1 comes from pulling log^{d-1} out of the square root. The proof's c_t is c_t = const * sqrt(d! |F_o(t)| log^{d-1} n), so after squaring you get |F_o(t)| log^{d-1} n, and after summing over t with sum |F_o(t)| = d mo, delta becomes const * sqrt(mo log^d n) = const sqrt(mo) log^{d/2} n, which is exactly the lemma's bound. The stress-test note squares as if the log were outside the sqrt; it's an algebra slip, not a gap in the paper.

That matters because the rest of the architecture hangs on Lemma 4.1, and the lemma looks fine. The sparsification idea is genuinely the new thing: a d-dimensional hash with P=1/k per tuple, used to induct on d, which removes the Delta-dependence from the earlier triangle work. The extension to d-uniform hypergraphs and the polylog query bound are real. The acknowledgment of the concurrent Dell et al. result is honest.

There are minor blemishes. Lemma 6.2's proof has a direction slip: it writes P(E1) ≤ exp(-1) where it means P(E1^c) ≤ exp(-1); the conclusion still holds because it later uses (1 - e^{-1})^d. A few displayed equations have small notation typos. None of these affect the main theorem.

So my recommendation: send it to a serious referee. The result is significant enough, the central lemma survives the attack in the stress test, and the writing, while dense, is at a standard where a careful referee can check the steps. The report's REJECT should not be acted on as-is.

Referee Report

3 major / 5 minor

Summary. The paper proposes a randomized algorithm for estimating the number of hyperedges m(H) in a d-uniform hypergraph on n vertices using queries to a Generalized d-partite Independent Set (GPIS) oracle. The main theorem claims an (1±ε)-approximation with O_d(log^{5d+5} n / ε^4) queries with high probability. The algorithm maintains a data structure of weighted d-partite subhypergraphs; it repeatedly (i) exactly counts subhypergraphs with at most τ ordered hyperedges using a trie-based decision tree, (ii) sparsifies larger subhypergraphs by random vertex coloring together with a random hash on color tuples, and (iii) when too many subhypergraphs accumulate, uses a coarse estimator followed by an importance-sampling step to reduce their number. The central technical ingredient is Lemma 4.1, which asserts that the number of properly colored ordered hyperedges R_d satisfies |R_d − m_o/k| ≤ 2^{2d} θ^d sqrt(d! m_o log^d n) with probability at least 1 − d!/n^{4θ−2d}. The proof of this lemma is by induction on d using the method of averaged bounded differences. The paper also proves that the GPIS1 and GPIS2 oracle variants can be simulated by polylogarithmically many GPIS queries.

Significance. If correct, the main result would be the first polylogarithmic-query algorithm for d-uniform hyperedge estimation without the parameter Δ that appeared in the triangle-estimation work of Bhattacharya et al., and it would generalize the edge-estimation result of Beame et al. The paper is clearly written and the supporting lemmas (exact estimation, coarse estimation, importance sampling) are presented in detail. The comparison with the concurrent work of Dell et al. is transparent and helpful. However, the central sparsification lemma has a substantive proof gap: the calculation of the concentration parameter δ gives a deviation of order sqrt(m_o) log^{d−1/2} n rather than sqrt(m_o) log^{d/2} n, and the application of the averaged-bounded-differences inequality is not justified because the required bounds are not established on the conditional space. These issues are load-bearing for the threshold setting and for the final query bound. As a result, the main theorem is not established in the present manuscript.

major comments (3)

[Section 4.2, proof of Lemma 4.1] The computation of δ is incorrect. With c_t = 2^{2d−1} θ^{d−1} sqrt(d! F_o(t) log^{d−1} n) and ∑_t F_o(t) = d m_o(A), one obtains ∑_t c_t^2 = 2^{4d−2} θ^{2d−2} d! d m_o(A) log^{2d−2} n. Therefore δ = 2 sqrt(θ log n · ∑_t c_t^2) = 2^{2d} θ^{d−1/2} sqrt(d! d m_o(A)) log^{d−1/2} n, not the paper's 2^{2d} θ^{d−1/2} sqrt(d! m_o(A) log^d n). For d ≥ 2, the correct δ exceeds the bound asserted in Lemma 4.1 by a factor θ^{−1/2} sqrt(d) log^{(d−1)/2} n, and the additive m_o(A)P(B) term in the next display cannot close this gap. Since the threshold τ in Section 7 and Equation (3) in Section 8 are derived from the claimed log^{d/2} bound, Theorem 1.2 is not supported as written.
[Section 4.2 and Lemma A.2] The application of the averaged bounded differences inequality is not justified. Lemma A.2 requires, for the event B, a bound on the conditional expectations given B^c, namely |E[f | X_1,...,X_{i−1}, X_i=a_i, B^c] − E[f | ..., X_i=a'_i, B^c]| ≤ c_i. The proof, however, bounds the unconditional differences E_t R_d via Claim 4.4. Conditioning on B^c — the event that all these differences are small — changes the distribution of the remaining colors and can alter the conditional differences. No argument is given that the c_t bounds hold on the conditional space B^c, so the concentration step in the proof of Lemma 4.1 is not established.
[Section 8, Observation 8.4 and proof of Lemma 8.2] Observation 8.4 is stated only for the case that the data structure contains exactly one tuple after iteration i, but its proof immediately treats the case of r > N tuples (Step 4), and Lemma 8.2 applies the observation to all iterations, during which D generally contains many tuples. As stated, the observation does not support the chain of (1±λ)-approximations used in the proof of Lemma 8.2; the statement and proof need to be generalized to arbitrary tuple sets.

minor comments (5)

[Algorithm 1, line 5] The condition 'while there is a leaf node mo(B_1^{[b_1]},...,B_t^{[b_t]}) = 0 in the tree with label 1' should read 'with label 1'; the equality to 0 is inconsistent with the surrounding text and with the prose description of the algorithm.
[Lemma 6.2, proof] The displayed inequalities for P(E1) and P(E_i | ...) bound the probabilities of the complementary events; as printed they have the wrong sign. The final line P(∩ E_i) ≥ (1−e^{−1})^d reveals the intended meaning, but the inequalities need to be corrected.
[Section 4.2] The inequality 'P(B) ≤ 2d!/n^{4θ−4d+1}' appears to be a typo for 2d!/n^{4θ−2d+1}, which is the value used in the next display and follows from the union bound over t.
[Section 7, Step 4] The sentence 'Since the algorithm of Lemma 3.4 does not require any queries, the number of GPIS2 queries in this step in each iteration is O_d(log^{d+1} n) per tuple' is confusing: the O_d(log^{d+1} n) bound comes from the coarse-estimation step, not from Lemma 3.4 itself.
[Lemma 6.2, definitions of events] In the definition of the events E_i, the line 'Aj((Q_{j−1},U_{j−1}),q_j)∩B_{j,q}≠∅, where 2≤i≤d−1' uses j in place of i and should be rephrased for clarity.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the derivation is self-contained; the skeptical log-exponent concern is a correctness issue, not a self-referential one.

full rationale

I find no circularity in the paper's derivation chain. The main result, Theorem 1.2, is obtained by combining the exact-estimation lemma, the sparsification lemma, the coarse-estimation lemma, and the importance-sampling lemma. Lemma 3.2 / Lemma 4.1, the load-bearing concentration result, is proved directly by induction on d, using only the externally cited averaged bounded differences lemma (Lemma A.2), Hoeffding's inequality, and the paper's own color/hash construction. No parameter is fitted to the quantity being estimated, and no estimate is used as an input to its own proof. The self-citations to the authors' earlier triangle-estimation papers are used as background, as a statement of previous query complexity bounds, and as a comparison point; they are not used to justify the new d-uniform sparsification bound. The proof of Lemma 4.1 explicitly invokes its own induction hypothesis, not a prior published theorem, so the chain is internal. The skeptical observation about the log exponent in the deviation bound is a possible mathematical flaw in the proof as printed, but it is a correctness risk, not circularity: even if the printed bound does not follow from the displayed calculation, the attempted reduction is from independent concentration analysis, not from a restatement of the target result. Likewise, the threshold tau and the final query count are derived by substituting the lemmas' bounds, which is a normal chain of reasoning rather than a renaming of the answer. Accordingly, the appropriate circularity score is 0.

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

The paper introduces no new physical or mathematical entities; the GPIS oracle was defined in prior work. The free parameters are algorithmic thresholds and analysis constants, not fitted values. The axioms are the query model, standard concentration tools, and the constant-d assumption. No circularity or data-dependent fitting is present.

free parameters (3)

theta = 2d (set in Section 8)
A constant greater than d used in the sparsification lemma's probability bound. It is chosen to make concentration bounds work and affects the exponents in p_d; it is not fitted to data.
kappa_d = unspecified constant, fixed later
Constant in the tuple-count threshold N = kappa_d log^{4d} n / epsilon^2. It is introduced to force sparsification every other iteration and is not estimated from data.
tau = k 2^{4d} theta^{2d} 16^{d} 2^{d} d! log^{d+2} n / epsilon^2, k=4
Threshold for exact counting; set so that the sparsification error is at most epsilon/(4d log n) per tuple. An algorithmic parameter, not a fitted constant.

assumptions (5)

domain assumption d is a fixed constant; all O_d(.) hide functions of d.
Theorem 1.2 and the polylog bound hold only for constant d; the algorithms' query counts grow with d and the brute-force case uses n^d queries.
domain assumption GPIS, GPIS1, and GPIS2 oracles answer exactly per Definitions 1.1, B.5, and B.6, and GPIS1/GPIS2 can be simulated by polylog GPIS queries.
The entire query model rests on these definitions; the simulation proofs in Appendix C use random partitioning and repetition.
standard math Standard concentration inequalities (Hoeffding, Chernoff, averaged bounded differences) apply as stated.
Used in the sparsification proof (Section 4) and the coarse estimation proof (Section 6).
standard math The hash function h_d: [k]^d to {0,1} has independent bits with P[1]=1/k, and the induced h_{d-1} in the induction step is independent.
Required for the induction in Claim 4.4(a) and for E[R_d] = mo/k.
ad hoc to paper The exact estimation tree (Section 5) is a valid trie: every hyperedge corresponds to exactly one root-to-leaf path, so the number of internal nodes is O(mo log n).
Used to bound the number of GPIS1 queries in Lemma 5.1. Standard trie argument, but not proved in detail in the paper.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Hyperedge Estimation using Polylogarithmic Subset Queries." pith.science (2026). https://pith.science/paper/EYYMCNRE

@misc{pith2026190804196,
  author       = {Pith},
  title        = {Pith review of: Hyperedge Estimation using Polylogarithmic Subset Queries},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EYYMCNRE}},
  note         = {Machine review of arXiv:1908.04196}
}

abstract

In this work, we estimate the number of hyperedges in a hypergraph ${\cal H}(U({\cal H}), {\cal F}({\cal H}))$, where $U({\cal H})$ denotes the set of vertices and ${\cal F}({\cal H}))$ denotes the set of hyperedges. We assume a query oracle access to the hypergraph ${\cal H}$. Estimating the number of edges, triangles or small subgraphs in a graph is a well studied problem. Beame \etal~and Bhattacharya \etal~gave algorithms to estimate the number of edges and triangles in a graph using queries to the {\sc Bipartite Independent Set} ({\sc BIS}) and the {\sc Tripartite Independent Set} ({\sc TIS}) oracles, respectively. We generalize the earlier works by estimating the number of hyperedges using a query oracle, known as the {\bf Generalized $d$-partite independent set oracle ({\sc GPIS})}, that takes $d$ (non-empty) pairwise disjoint subsets of vertices $A_1,\ldots,A_d \subseteq U({\cal H})$ as input, and answers whether there exists a hyperedge in ${\cal H}$ having (exactly) one vertex in each $A_i, i \in \{1,2,\ldots,d\}$. We give a randomized algorithm for the hyperedge estimation problem using the {\sc GPIS} query oracle to output $\widehat{m}$ for $m({\cal H})$ satisfying $(1-\epsilon) \cdot m({\cal H}) \leq \widehat{m} \leq (1+\epsilon) \cdot m({\cal H})$. The number of queries made by our algorithm, assuming $d$ to be a constant, is polylogarithmic in the number of vertices of the hypergraph.

Figures

Figures reproduced from arXiv: 1908.04196 by the authors.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 17 canonical work pages

[1]

On Triangle Estimation using Tripartite Independent Set Queries

Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra. Triangle estimation using polylogarithmic queries. CoRR , abs/1808.00691, 2018

work page Pith review arXiv 2018
[2]

Triangle estimation using polylogarithmic queries

Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra. Triangle estimation using polylogarithmic queries. In ISAAC , 2019

work page 2019
[3]

Bishnu, A

A. Bishnu, A. Ghosh, S. Kolay, G. Mishra, and S. Saurabh. Parameterized query complexity of hitting set using stability of sunflowers. In ISAAC , 2018

work page 2018
[4]

Almost optimal query algorithm for hitting set using a subset query

A. Bishnu, A. Ghosh, S. Kolay, G. Mishra, and S. Saurabh. Parameterized Query Complexity of Hitting Set using Stability of Sunflowers . CoRR , abs/1807.06272, 2018

work page Pith review arXiv 2018
[5]

Beame, S

P. Beame, S. Har - Peled, S. N. Ramamoorthy, C. Rashtchian, and M. Sinha. Edge Estimation with Independent Set Oracles . In ITCS , 2018

work page 2018
[6]

Nearly optimal edge estimation with independent set queries

Xi Chen, Amit Levi, and Erik Waingarten. Nearly optimal edge estimation with independent set queries. CoRR , abs/1907.04381, 2019

work page Pith review arXiv 1907
[7]

Dell and J

H. Dell and J. Lapinskas. Fine-grained reductions from approximate counting to decision. In STOC , 2018

work page 2018
[8]

Approximately counting and sampling small witnesses using a colourful decision oracle

Holger Dell, John Lapinskas, and Kitty Meeks. Approximately counting and sampling small witnesses using a colourful decision oracle. CoRR , abs/1907.04826, 2019

work page Pith review arXiv 1907

Show all 18 references

[9]

Dubhashi and A

D.P. Dubhashi and A. Panconesi. Concentration of Measure for the Analysis of Randomized Algoritms . In Cambridge , 2009

2009
[10]

T. Eden, A. Levi, D. Ron, and C. Seshadhri. Approximately Counting Triangles in Sublinear Time . SIAM J. Comput. , 46(5), 2017

2017
[11]

T. Eden, D. Ron, and C. Seshadhri. On approximating the number of k -cliques in sublinear time. In STOC , 2018

2018
[12]

U. Feige. On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph . SIAM J. Comput. , 2006

2006
[13]

Introduction to Property Testing

Oded Goldreich. Introduction to Property Testing . Cambridge University Press, 2017

2017
[14]

Goldreich and D

O. Goldreich and D. Ron. Approximating Average Parameters of Graphs . Random Struct. Algorithms , 2008

2008
[15]

Lectures on discrete geometry , volume 212 of Graduate texts in mathematics

Ji v r ' i Matou v s ek. Lectures on discrete geometry , volume 212 of Graduate texts in mathematics . Springer, 2002

2002
[16]

Ron and G

D. Ron and G. Tsur. The power of an example: Hidden set size approximation using group queries and conditional sampling. TOCT , 2016

2016
[17]

L. J. Stockmeyer. The complexity of approximate counting. In STOC , 1983

1983
[18]

L. J. Stockmeyer. On approximation algorithms for \# p. SIAM J. Comput. , 1985

1985

Pith tools

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

[1] [1]

On Triangle Estimation using Tripartite Independent Set Queries

Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra. Triangle estimation using polylogarithmic queries. CoRR , abs/1808.00691, 2018

work page Pith review arXiv 2018

[2] [2]

Triangle estimation using polylogarithmic queries

Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra. Triangle estimation using polylogarithmic queries. In ISAAC , 2019

work page 2019

[3] [3]

Bishnu, A

A. Bishnu, A. Ghosh, S. Kolay, G. Mishra, and S. Saurabh. Parameterized query complexity of hitting set using stability of sunflowers. In ISAAC , 2018

work page 2018

[4] [4]

Almost optimal query algorithm for hitting set using a subset query

A. Bishnu, A. Ghosh, S. Kolay, G. Mishra, and S. Saurabh. Parameterized Query Complexity of Hitting Set using Stability of Sunflowers . CoRR , abs/1807.06272, 2018

work page Pith review arXiv 2018

[5] [5]

Beame, S

P. Beame, S. Har - Peled, S. N. Ramamoorthy, C. Rashtchian, and M. Sinha. Edge Estimation with Independent Set Oracles . In ITCS , 2018

work page 2018

[6] [6]

Nearly optimal edge estimation with independent set queries

Xi Chen, Amit Levi, and Erik Waingarten. Nearly optimal edge estimation with independent set queries. CoRR , abs/1907.04381, 2019

work page Pith review arXiv 1907

[7] [7]

Dell and J

H. Dell and J. Lapinskas. Fine-grained reductions from approximate counting to decision. In STOC , 2018

work page 2018

[8] [8]

Approximately counting and sampling small witnesses using a colourful decision oracle

Holger Dell, John Lapinskas, and Kitty Meeks. Approximately counting and sampling small witnesses using a colourful decision oracle. CoRR , abs/1907.04826, 2019

work page Pith review arXiv 1907