Pith. sign in

REVIEW 1 major objections 5 minor 76 references

Efficient and Adaptive Estimation of Local Triadic Coefficients

T0 review · 1 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read A single sampled edge can update every bucket's estimate of local clustering and closure, with simultaneous error guarantees.

desk verdict A genuinely new estimator family and a first algorithm for average local closure, but the main sample-complexity guarantee is not fully proved as written and a variance formula is misprinted; both are fixable. read the letter →

arxiv 2507.07536 v1 pith:MALYLKLF submitted 2025-07-10 cs.DS cs.SI

Ilie Sarpe , Aristides Gionis This is my paper · ORCID
classification cs.DScs.SI MSC 68R1005C8068W2060C05
keywords localclusteringcoefficientclosuretriadiccoefficientsgraphsamplingtrianglecountingpseudo-dimensionadaptiveestimationempiricalBernsteinbounds
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

This paper introduces Triad, an adaptive edge-sampling algorithm for estimating the average local clustering coefficient and the average local closure coefficient over each set in a partition of a graph's nodes. Since exact computation requires listing all triangles, the paper replaces it with a class of unbiased estimators that distribute the triangles incident to a sampled edge among the buckets in a tunable way. The paper proves a pseudo-dimension-based sample-size bound and uses empirical-Bernstein confidence intervals to stop adaptively, yielding data-dependent error bars per bucket. Its main guarantee is that with probability at least $1-\eta$ the estimates satisfy $|f_j - \Psi_j| \le \hat{\varepsilon}_j \le \varepsilon_j$ for every bucket $j$ simultaneously. The same machinery covers local closure coefficients, for which the paper provides the first dedicated estimation algorithm, and experiments on billion-edge graphs show accurate estimates from roughly one per mille of the edges.

What carries the argument

The load-bearing object is the $q$-weighted triangle-diffusion estimator. Given a uniformly sampled edge $e=\{u,v\}$ and the set $\Delta_e$ of triangles containing it, the estimator assigns weight $q|\Delta_e|/(p|\mathcal{W}^*_u|)$ to $u$, the same to $v$, and $(1-2q)/(p|\mathcal{W}^*_w|)$ to each common neighbor $w$, where $|\mathcal{W}^*_v|$ is the number of wedges centered or headed at $v$ and $p=1/m$ is the edge sampling probability; the bucket estimate $f_j(e)$ is the average of these weights over nodes in bucket $V_j$. This asymmetric assignment is what gives unbiasedness and a tunable variance. The proof of the sample bound uses pseudo-dimension: the family $\{f_j\}_{j=1}^k$ has pseudo-dimension at most $\lfloor \log_2 \hat{\chi}\rfloor+1$, and this feeds into a uniform-convergence bound that fixes the maximum sample count. The adaptive stopping rule is an empirical-Bernstein inequality, with a betting-based plugin version for the implemented variant, that bounds $|f_j-\Psi_j|$ using the empirical variance of the collected samples and produces the per-bucket error certificates.

What would settle it

On a small graph where exact bucket averages are known by enumerating all triangles, pick $\varepsilon_j$ and $\eta$, run Triad many times, and record the fraction of runs in which any bucket violates $|f_j-\Psi_j| \le \hat{\varepsilon}_j \le \varepsilon_j$. If that empirical failure rate exceeds $\eta$, the pseudo-dimension sample bound used to set $s_{\max}$ does not hold in the stated form.

Watch

Extended reading notes

Core claim

The central claim is that the adaptive algorithm Triad solves the estimation problem with simultaneous per-bucket guarantees for either triadic coefficient. For any partition $\mathbf{V}$ of the node set, Triad returns estimates $f_j$ and error bounds $\hat{\varepsilon}_j$ such that $|f_j - \Psi_j| \le \hat{\varepsilon}_j \le \varepsilon_j$ for all $j \in [k]$ with probability at least $1-\eta$. The engine is a novel estimator class: a uniformly sampled edge $e$ with $|\Delta_e|$ incident triangles is turned into a per-bucket estimate by giving a $q$-fraction of the triangle weight to each endpoint and a $(1-2q)$-fraction to each common neighbor, normalized by bucket size and wedge counts; the parameter $q\in[0,1/2]$ is then chosen to minimize the maximum empirical variance. The sample size is controlled by a pseudo-dimension bound $\zeta \le \lfloor \log_2 \hat{\chi}\rfloor + 1$, where $\hat{\chi}$ counts how many buckets a single edge can influence through its lower-degree endpoint, and adaptive stopping uses empirical-Bernstein inequalities to convert observed variance into per-bucket confidence intervals. The result applies to both average local clustering and average local closure coefficients.

Load-bearing premise

The guarantee depends on an imported uniform-convergence bound, quoted without proof, that a sample size of $(b-a)^2\varepsilon^{-2}(\zeta+\log(1/\eta))$ is enough to keep every bucket estimate within $\varepsilon$; if the true constant in that bound is larger than the paper assumes, the computed maximum sample size would be too small for the promised $1-\eta$ probability.

Editorial extensions

If this is right

  • Both average local clustering and average local closure coefficients can be estimated for arbitrary node partitions without listing all triangles.
  • The pseudo-dimension bound $\zeta \le \lfloor \log_2 \hat{\chi}\rfloor + 1$ can be logarithmically smaller than a generic $\log n$ bound; on a star graph it is $1$, so the worst-case sample count drops accordingly.
  • A single sampled edge updates every bucket simultaneously, so the method avoids the $\Theta(k\varepsilon^{-2}\log(k/\eta))$ wedge-sample count of previous per-bucket estimators.
  • The adaptive empirical-Bernstein bounds give confidence intervals that tighten with the data; in the reported experiments, errors of order $10^{-2}$ to $10^{-3}$ are achieved within seconds to a few minutes on large graphs.
  • The fixed-sample variant Triad-f can be used when a strict sublinear budget is required, with accurate estimates observed at about one per mille of the edges.

Reading between the lines

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

  • Beyond the paper, the same $q$-weighted distribution rule could be adapted to estimate other local subgraph statistics, such as typed or weighted triangle counts, by changing the weight split and the normalization.
  • The dependency of the sample bound on $\hat{\chi}$ suggests a partition-dependent trade-off: coarsening buckets reduces $\hat{\chi}$ and hence the sample complexity, a trade-off the paper does not explore.
  • Since the algorithm only needs per-edge contributions and running variances, it should extend to streaming or distributed settings; the paper names this as future work, so the extension is an inference rather than a claim.
  • The DBLP case study implies a downstream use: average triadic coefficients over metadata-defined communities could serve as structural features for graph learning models, a connection the paper leaves implicit.
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

1 major / 5 minor

Summary. The paper introduces the problem of estimating the average local clustering and local closure coefficients over each set in a given partition of the graph's vertex set. The proposed algorithm, Triad, samples edges uniformly at random, uses a family of unbiased estimators parametrized by an interpolation weight q, computes an upper bound on the pseudo-dimension of the estimator family, and stops adaptively using empirical Bernstein bounds. The main theoretical claim is a simultaneous guarantee: with probability at least 1−η, the output (f_j, bε_j) satisfies |f_j − Ψ_j| ≤ bε_j ≤ ε_j for every bucket j simultaneously. The paper also provides an extensive experimental evaluation on large graphs and a case study on DBLP collaboration patterns.

Significance. If the main guarantee is established, the paper is a strong contribution: it is, to the authors' knowledge, the first algorithm for estimating average local closure coefficients; the estimator family is flexible and provably unbiased for every q; the pseudo-dimension bound depending on bχ rather than k can be much smaller than naive bounds; and the adaptive empirical-Bernstein stopping rule is practically effective, as demonstrated by experiments with public code. The unbiasedness lemmas (3.2–3.4) are correct, and the empirical-Bernstein step is well-founded. However, the central sample-complexity theorem (Theorem 3.6) is quoted without proof and with missing constants, and its application in the proof of Theorem 3.12 contains a logarithmic mismatch; as a result, the advertised 1−η guarantee is not established as written. The remaining issues are local and fixable, so the paper merits revision rather than rejection.

major comments (1)
  1. [Section 3.3.1 (Theorem 3.6) and Algorithm 1 line 7] The sample-complexity theorem that underlies the stopping rule is stated without proof and with coefficient 1 on (b−a)^2 ε^{−2} (ζ + log(1/η)); standard pseudo-dimension uniform-convergence results include a universal constant C ≥ 1, and the paper neither proves a C=1 bound for this specific function family nor cites a theorem with exact constants. In addition, the proof of Theorem 3.12 in Appendix A applies Theorem 3.6 with failure probability η/2, which requires log(2/η) in the sample size, but Algorithm 1 line 7 uses log(1/η). With the printed s_max, the theorem only gives P[F1] ≤ η, so the union bound yields total failure probability at most 1.5η instead of η. This is a load-bearing gap in the central simultaneous-guarantee claim; it should be fixed by either proving Theorem 3.6 with explicit constants for the estimator family or conservatively setting s_max with an explicit constant and log(2/η).
minor comments (5)
  1. [Algorithm 1] The pseudocode uses the batch sizes s_i (line 9) and initializes s0 (line 7) without defining either quantity; the text later mentions a geometric schedule s_i = θ s_{i−1}, but this should appear in the algorithm for reproducibility.
  2. [Appendix C.3, Algorithm 2 (FindThreshold)] The loop overwrites T with β^2 D_β rather than accumulating the sum Σ_{j≤β} j^2 D_j, so the pseudocode does not implement the threshold described in the text; to match the text the update should be T ← T + β^2 D_β.
  3. [Appendix A, proof of Lemma 3.5] The justification 'for the events I ... it holds I ⊆ I′' is incorrect for a single-edge sampling scheme (the events X_{e1}=1 and X_{e2}=1 are mutually exclusive for e1≠e2); the inequality E[X_{e1}X_{e2}] ≤ p is nevertheless true, so the proof's conclusion is unaffected but the explanation should be corrected.
  4. [Section 3.3.1 and Corollary 3.9] There is a numbering inconsistency: the statement is Proposition 3.8, but Corollary 3.9 refers to 'Theorem 3.8' and the proof in Appendix A is titled 'Proof of Theorem 3.8'; the numbering and references should be harmonized.
  5. [Section 3.3.3, Lemma 3.14] The proof gives a Hoeffding bound for each fixed q, but the lemma asserts a uniform statement over all q∈[0,1/2]; since the variance estimate is quadratic in q, a uniform bound is needed (e.g., via a Lipschitz argument or a union bound over the vertex of the parabola), and this should be supplied to justify the claim that Fixq computes a near-optimal q.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Triad's estimators are proved unbiased by direct calculation, the adaptive bounds come from external concentration inequalities, and no prediction is forced by a fitted constant or by self-citation.

full rationale

I walked the derivation chain from the estimators (Lemmas 3.2--3.3) through the sample-complexity argument (Theorem 3.6, Proposition 3.8), the adaptive stopping rule (Theorem 3.11 and Theorem 3.12), and the experimental comparison in Section 4.3. The unbiasedness of the per-edge estimators is shown by explicit expectation computations over the random edge draw, with the identity sum_e a_q(v,e) = |Delta_v| proven in Appendix A; the quantity being estimated (Psi_j) is not used to define the estimator. The pseudo-dimension bound in Proposition 3.8 is proved from the shattering definition rather than assumed, and it is combined with a standard (quoted, external) uniform-convergence bound rather than with a result that already contains Triad's target accuracy. The adaptive empirical-Bernstein bounds are imported as external concentration inequalities ([34, 36] and [52, 62]) and are applied to the same samples, which is a data-dependent confidence interval, not a fitted parameter renamed as a prediction; the stopping time is controlled by a union bound over iterations in the proof of Theorem 3.12. No step reduces an output equation to an input equation by construction, and no load-bearing premise is justified only by the authors' own prior work. The main weakness is a correctness gap, not circularity: Algorithm 1 sets s_max = R^2/epsilon^2 (zeta + log(1/eta)) while the proof of Theorem 3.12 bounds P[F1] <= eta/2 by invoking Theorem 3.6, which for failure probability eta/2 would require log(2/eta); moreover Theorem 3.6 is quoted without proving its multiplicative constant. These issues affect whether the stated 1-eta guarantee is established as written, but they are not cases where the derivation is equivalent to its own inputs. The experimental choice in Section 4.3 of feeding Triad's reported b_epsilon values into the baseline is a fairness/evaluation procedure, not a circular prediction. Accordingly, the circularity score is 0.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

The central correctness of Triad rests on standard concentration inequalities and a pseudo-dimension convergence theorem; no new physical or graph entity is postulated. The estimators are unbiased for every q, so the adaptive parameter q is an efficiency lever rather than a fitted target value.

free parameters (4)
  • q (estimator interpolation weight) = 0.03 +/- 0.02 on fb-CMU and 0.3 +/- 0.06 on PT in the reported experiments; otherwise chosen adaptively in [0, 1/2]
    Interpolation weight in the estimator family. The Fixq subroutine chooses q by minimizing estimated variance of the bucket estimates; any value in [0, 1/2] preserves unbiasedness, so this affects efficiency only.
  • C (small-degree filtering threshold) = 30, 100, 150, or 500, depending on dataset
    Threshold in Section 3.4.3 up to which triangles are computed exactly. It is set per dataset in Appendix F.1.2 and affects runtime and variance but not unbiasedness of the estimates.
  • c (sample size for q optimization) = 500
    Number of sampled edges used by Fixq to estimate variance coefficients A_j, B_j, C_j, listed in Appendix E.
  • theta (geometric sample schedule ratio) = 1.4
    Controls how quickly the sample bag grows between adaptive-loop iterations; taken from prior work on adaptive sampling.
assumptions (4)
  • standard math Pseudo-dimension uniform-convergence theorem for function classes with bounded range
    Invoked to set s_max in Theorem 3.6; the statement is used as a black box from the cited pseudo-dimension literature without a proof in this paper.
  • standard math Empirical Bernstein and betting concentration inequalities
    Used to construct adaptive confidence intervals and stopping conditions, cited to Theorems 3.11 and 3.16.
  • domain assumption In-memory adjacency access allows enumerating N_e and |Delta_e| in O(d_max) time per sampled edge
    The algorithm and its complexity analysis in Section 3.5 assume the graph can be randomly queried in this way; streaming variants are left to future work.
  • domain assumption After filtering, all remaining nodes have original degree at least C (at least 10 in Appendix E), so |W*_v| > 0 and the UpperBounds routine avoids division by zero
    Section 3.4.3 and Appendix E rely on the threshold C to keep the filtered graph well-behaved for the range bounds R_j.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Efficient and Adaptive Estimation of Local Triadic Coefficients." pith.science (2026). https://pith.science/paper/MALYLKLF

@misc{pith2026250707536,
  author       = {Pith},
  title        = {Pith review of: Efficient and Adaptive Estimation of Local Triadic Coefficients},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MALYLKLF}},
  note         = {Machine review of arXiv:2507.07536}
}
read the original abstract

Characterizing graph properties is fundamental to the analysis and to our understanding of real-world networked systems. The local clustering coefficient, and the more recently introduced, local closure coefficient, capture powerful properties that are essential in a large number of applications, ranging from graph embeddings to graph partitioning. Such coefficients capture the local density of the neighborhood of each node, considering incident triadic structures and paths of length two. For this reason, we refer to these coefficients collectively as local triadic coefficients. In this work, we consider the novel problem of computing efficiently the average of local triadic coefficients, over a given partition of the nodes of the input graph into a set of disjoint buckets. The average local triadic coefficients of the nodes in each bucket provide a better insight into the interplay of graph structure and the properties of the nodes associated to each bucket. Unfortunately, exact computation, which requires listing all triangles in a graph, is infeasible for large networks. Hence, we focus on obtaining highly-accurate probabilistic estimates. We develop Triad, an adaptive algorithm based on sampling, which can be used to estimate the average local triadic coefficients for a partition of the nodes into buckets. Triad is based on a new class of unbiased estimators, and non-trivial bounds on its sample complexity, enabling the efficient computation of highly accurate estimates. Finally, we show how Triad can be efficiently used in practice on large networks, and we present a case study showing that average local triadic coefficients can capture high-order patterns over collaboration networks.

Figures

Figures reproduced from arXiv: 2507.07536 by the authors.

Figure 1
Figure 1. 1A: the local clustering coefficient of a node [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. 2A: Discussion in Section 2. For node𝑢 it holds 𝛼𝑢 = 1 and 𝜙𝑢 = O (1/𝑛). For node𝑤 it holds 𝛼𝑤 = O (1/𝑛 2 ) and 𝜙𝑤 = 1. Thus, the local clustering and local closure coefficients can differ significantly. 2B: Discussion in Section 3. Consider a sampled edge 𝑒 ∈ 𝐸. For each node 𝑤 ∈ 𝑉 in the graph, our estimate for |Δ𝑤 | is |Δ𝑤 | = 𝑞|Δ𝑒 |/𝑝, if 𝑤 ∈ {𝑢, 𝑣 }, and |Δ𝑤 | = (1 − 2𝑞)|Δ𝑒 |/𝑝, if 𝑤 = 𝑧𝑖 ∈ N𝑒 . if 𝑣 ∈ w and 𝑣 … view at source ↗
Figure 3
Figure 3. Value Ψ𝑖 and its maximum error (|𝑓𝑖 − Ψ𝑖 |) over five runs. We also report, the supremum error 𝜚ˆ = sup𝑖∈ [𝑘 ] |𝑓𝑖 − Ψ𝑖 | and the average runtime over five independent runs across all buckets, for varying sample size (𝑠 ∈ {1, 2, 5}‰ of the total edges 𝑚). Note that all the above partition schemes place nodes with sim￾ilar degree in the same bucket. This is often the case in practical applications, where nodes with s… view at source ↗
Figures from the paper (10 more)
Figure 4
Figure 4. Figure 4: Comparison of Triad and the baselines WedgeSampler. For each dataset we show, (top plot): the average supremum error over all buckets over the various runs. (bottom): average runtime to perform an execution. Small-degree processing Fixq UpperBounds Adaptive step VV V P…
Figure 5
Figure 5. Figure 5: Fine grained runtime analysis. We show the average [PITH_FULL_IMAGE:figures/full_fig_p010_5.png]
Figure 6
Figure 6. Figure 6: Supremum error over ten runs over different parti [PITH_FULL_IMAGE:figures/full_fig_p010_6.png]
Figure 7
Figure 7. Figure 7: Average local clustering and local closure coefficient [PITH_FULL_IMAGE:figures/full_fig_p011_7.png]
Figure 8
Figure 8. Figure 8: Induced subgraphs by communities. (Left): compu [PITH_FULL_IMAGE:figures/full_fig_p011_8.png]
Figure 9
Figure 9. Figure 9: Value Ψ𝑖 and its maximum error (|𝑓𝑖 − Ψ𝑖 |) over five runs. We also report, the supremum error 𝜚ˆ = sup𝑖∈ [𝑘 ] |𝑓𝑖 − Ψ𝑖 | and the average runtime over five independent runs across all buckets, for varying sample size (𝑠 ∈ {1, 2, 5}‰ of the total edges 𝑚). WedgeSampler-…
Figure 10
Figure 10. Figure 10: Comparison of Triad and the base￾lines WedgeSampler. For each dataset we show, (top plot): the average supremum error over all buckets over the various runs. (bottom): average runtime to perform an execution. – Data management: VLDB, PVLDB, SIGMOD, PODS, ICDE, PODC, S…
Figure 11
Figure 11. Figure 11: Value Ψ𝑖 and its maximum error (|𝑓𝑖 − Ψ𝑖 |) over five runs. We also report, the supremum error 𝜚ˆ = sup𝑖∈ [𝑘 ] |𝑓𝑖 − Ψ𝑖 | and the average runtime over five independent runs across all buckets, for varying sample size (𝑠 ∈ {1, 2, 5}‰ of the total edges 𝑚). F.2 Extendin…
Figure 12
Figure 12. Figure 12: Induced subgraphs by the various research communities over time. We select sufficiently small-sized subgraphs for ease of visualization [PITH_FULL_IMAGE:figures/full_fig_p022_12.png]
Figure 13
Figure 13. Figure 13: Binned degree distribution of the various research categories over the DBLP graph. Y-axis is in log-scale for ease of visualization [PITH_FULL_IMAGE:figures/full_fig_p023_13.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

76 extracted references · 41 canonical work pages

  1. [1]

    Ahmed, Nick Duffield, Theodore L

    Nesreen K. Ahmed, Nick Duffield, Theodore L. Willke, and Ryan A. Rossi. 2017. On sampling from massive graph streams. Proceedings of the VLDB Endowment 10, 11 (Aug. 2017), 1430–1441. https://doi.org/10.14778/3137628.3137651

    arXiv 2017

  2. [2]

    Ahmed, Theodore L

    Nesreen K. Ahmed, Theodore L. Willke, and Ryan A. Rossi. 2016. Estimation of local subgraph counts. In 2016 IEEE International Conference on Big Data (Big Data). IEEE. https://doi.org/10.1109/bigdata.2016.7840651

    work page arXiv 2016

  3. [3]

    Mohammad Al Hasan and Vachik S. Dave. 2017. Triangle counting in large networks: a review. WIREs Data Mining and Knowledge Discovery 8, 2 (Oct. 2017). https://doi.org/10.1002/widm.1226

    work page doi:10.1002/widm.1226 2017

  4. [4]

    David A. Bader. 2023. Fast Triangle Counting. In 2023 IEEE High Performance Extreme Computing Conference (HPEC) . IEEE, 1–6. https://doi.org/10.1109/ hpec58863.2023.10363539

    arXiv 2023

  5. [5]

    Cover Edge-Based Novel Triangle Counting

    David A. Bader, Fuhuan Li, Zhihui Du, Palina Pauliuchenka, Oliver Alvarado Rodriguez, Anant Gupta, Sai Sri Vastav Minnal, Valmik Nahata, Anya Ganeshan, Ahmet Gundogdu, and Jason Lew. 2024. Cover Edge-Based Novel Triangle Counting. https://doi.org/10.48550/ARXIV.2403.02997

    work page Pith review arXiv doi:10.48550/arxiv.2403.02997 2024

  6. [6]

    Thomas Baignères, Pascal Junod, and Serge Vaudenay. 2004. How Far Can We Go Beyond Linear Cryptanalysis? Springer Berlin Heidelberg, 432–450. https: //doi.org/10.1007/978-3-540-30539-2_31

    work page doi:10.1007/978-3-540-30539-2_31 2004

  7. [7]

    Luca Becchetti, Paolo Boldi, Carlos Castillo, and Aristides Gionis. 2010. Efficient algorithms for large-scale local triangle counting.ACM Transactions on Knowledge Discovery from Data 4, 3 (oct 2010), 1–28. https://doi.org/10.1145/1839490.1839494

    work page arXiv 2010

  8. [8]

    Bhowmick and Boon Siew Seah

    Sourav S. Bhowmick and Boon Siew Seah. 2016. Clustering and Summarizing Protein-Protein Interaction Networks: A Survey. IEEE Transactions on Knowledge and Data Engineering 28, 3 (March 2016), 638–658. https://doi.org/10.1109/tkde. 2015.2492559

    arXiv 2016

Show all 76 references
  1. [9]

    Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. 2019. Spectral Clustering with Graph Neural Networks for Graph Pooling. https://doi.org/10. 48550/ARXIV.1907.00481

    2019 doi arXiv

  2. [10]

    Michele Borassi and Emanuele Natale. 2019. KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation. ACM Journal of Experimental Algorithmics 24 (Feb. 2019), 1–35. https://doi.org/10.1145/3284359

    2019 doi

  3. [11]

    Marco Bressan, Stefano Leucci, and Alessandro Panconesi. 2019. Motivo: fast motif counting via succinct color coding and adaptive sampling. Proceedings of the VLDB Endowment 12, 11 (July 2019), 1651–1663. https://doi.org/10.14778/ 3342263.3342640

    2019

  4. [12]

    Buriol, Gereon Frahling, Stefano Leonardi, and Christian Sohler

    Luciana S. Buriol, Gereon Frahling, Stefano Leonardi, and Christian Sohler. [n.d.]. Estimating Clustering Indexes in Data Streams . Springer Berlin Heidelberg, 618–

  5. [13]

    Norishige Chiba and Takao Nishizeki. 1985. Arboricity and Subgraph Listing Algorithms. SIAM J. Comput. 14, 1 (feb 1985), 210–223. https://doi.org/10.1137/ 0214017

    1985

  6. [14]

    Marek Ciglan, Alex Averbuch, and Ladialav Hluchy. 2012. Benchmarking Traver- sal Operations over Graph Databases. In 2012 IEEE 28th International Conference on Data Engineering Workshops. IEEE, 186–189. https://doi.org/10.1109/icdew. 2012.47

    2012 doi

  7. [15]

    de Lima, Murilo V

    Alane M. de Lima, Murilo V. G. da Silva, and André L. Vignatti. 2022. Estimating the Clustering Coefficient Using Sample Complexity Analysis . Springer Interna- tional Publishing, 328–341. https://doi.org/10.1007/978-3-031-20624-5_20

    2022 doi

  8. [16]

    Seshadhri

    Talya Eden, Amit Levi, Dana Ron, and C. Seshadhri. 2017. Approximately Count- ing Triangles in Sublinear Time. SIAM J. Comput. 46, 5 (Jan. 2017), 1603–1646. https://doi.org/10.1137/15m1054389

    2017 doi

  9. [17]

    Roohollah Etemadi and Jianguo Lu. 2017. Bias correction in clustering coefficient estimation. In 2017 IEEE International Conference on Big Data (Big Data) . IEEE, 606–615. https://doi.org/10.1109/bigdata.2017.8257976

    2017

  10. [18]

    Yixiang Fang, Xin Huang, Lu Qin, Ying Zhang, Wenjie Zhang, Reynold Cheng, and Xuemin Lin. 2019. A survey of community search over big graphs.The VLDB Journal 29, 1 (July 2019), 353–392. https://doi.org/10.1007/s00778-019-00556-x

    2019 doi

  11. [19]

    Hardiman and Liran Katzir

    Stephen J. Hardiman and Liran Katzir. 2013. Estimating clustering coefficients and size of social networks via random walk. In Proceedings of the 22nd international conference on World Wide Web (WWW ’13) . ACM, 539–550. https://doi.org/10. 1145/2488388.2488436

    2013

  12. [20]

    Seshadhri, and Ali Pinar

    Madhav Jha, C. Seshadhri, and Ali Pinar. 2015. Path Sampling. In Proceedings of the 24th International Conference on World Wide Web . International World Wide Web Conferences Steering Committee. https://doi.org/10.1145/2736277.2741101

    2015

  13. [21]

    Bin Jiang, Sijian Zhao, and Junjun Yin. 2008. Self-organized natural roads for predicting traffic flow: a sensitivity study. Journal of Statistical Mechanics: Theory and Experiment 2008, 07 (July 2008), P07008. https://doi.org/10.1088/1742-5468/ 2008/07/p07008

    2008 doi

  14. [22]

    Lee, and Hui Hong

    Ruoming Jin, Victor E. Lee, and Hui Hong. 2011. Axiomatic ranking of network role similarity. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD ’11) . ACM, 922–930. https: //doi.org/10.1145/2020408.2020561

    2011

  15. [23]

    Marcus Kaiser. 2008. Mean clustering coefficients: the role of isolated nodes and leafs on clustering measures for small-world networks. New Journal of Physics 10, 8 (Aug. 2008), 083042. https://doi.org/10.1088/1367-2630/10/8/083042

    2008 doi

  16. [24]

    George Karypis and Vipin Kumar. 1998. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs. SIAM Journal on Scientific Computing 20, 1 (Jan. 1998), 359–392. https://doi.org/10.1137/s1064827595287997

    1998 doi

  17. [25]

    Kolda, Ali Pinar, Todd Plantenga, C

    Tamara G. Kolda, Ali Pinar, Todd Plantenga, C. Seshadhri, and Christine Task

  18. [26]

    Kolountzakis, Gary L

    Mihail N. Kolountzakis, Gary L. Miller, Richard Peng, and Charalampos E. Tsourakakis. 2012. Efficient Triangle Counting in Large Graphs via Degree- Based Vertex Partitioning. Internet Mathematics 8, 1-2 (mar 2012), 161–185. https://doi.org/10.1080/15427951.2012.625260

    2012

  19. [27]

    Konstantin Kutzkov and Rasmus Pagh. 2013. On the streaming complexity of computing local clustering coefficients. In Proceedings of the sixth ACM inter- national conference on Web search and data mining (WSDM 2013) , Vol. 5. ACM, 677–686. https://doi.org/10.1145/2433396.2433480

    2013

  20. [28]

    Silvio Lattanzi and Stefano Leonardi. 2016. Efficient computation of the Weighted Clustering Coefficient. Internet Mathematics 12, 6 (June 2016), 381–401. https: //doi.org/10.1080/15427951.2016.1198281

    2016

  21. [29]

    Jure Leskovec, Ajit Singh, and Jon Kleinberg. 2006. Patterns of Influence in a Recommendation Network. Springer Berlin Heidelberg, 380–389. https://doi.org/ 10.1007/11731139_44

    2006 doi

  22. [30]

    Jure Leskovec and Rok Sosič. 2016. SNAP: A General-Purpose Network Anal- ysis and Graph-Mining Library. ACM Transactions on Intelligent Systems and Technology 8, 1 (July 2016), 1–20. https://doi.org/10.1145/2898361

    2016 doi

  23. [31]

    Qiyan Li and Jeffrey Xu Yu. 2024. Fast Local Subgraph Counting. Proceedings of the VLDB Endowment 17, 8 (April 2024), 1967–1980. https://doi.org/10.14778/ 3659437.3659451

    2024

  24. [32]

    Rong-Hua Li, Lu Qin, Jeffrey Xu Yu, and Rui Mao. 2015. Influential community search in large networks. Proceedings of the VLDB Endowment 8, 5 (Jan. 2015), 509–520. https://doi.org/10.14778/2735479.2735484

    2015

  25. [33]

    Yusheng Li, Yilun Shang, and Yiting Yang. 2017. Clustering coefficients of large networks. Information Sciences 382–383 (March 2017), 350–358. https://doi.org/ 10.1016/j.ins.2016.12.027

    2017 doi

  26. [34]

    Andreas Maurer and Massimiliano Pontil. 2009. Empirical Bernstein Bounds and Sample Variance Penalization. (July 2009). https://doi.org/10.48550/ARXIV.0907. 3740 arXiv:0907.3740 [stat.ML]

    2009 doi arXiv

  27. [35]

    Michael Mitzenmacher. 2017. Probability and computing (second edition ed.). Cambridge University Press, Cambridge. Hier auch später erschienene, unverän- derte Nachdrucke

    2017

  28. [36]

    Volodymyr Mnih, Csaba Szepesvári, and Jean-Yves Audibert. 2008. Empirical Bernstein stopping. In Proceedings of the 25th international conference on Machine learning - ICML ’08 (ICML ’08) . ACM Press, 672–679. https://doi.org/10.1145/ 1390156.1390241

    2008

  29. [37]

    Mark Newman. 2018. Networks. Oxford University Press. https://doi.org/10. 1093/oso/9780198805090.001.0001

    2018

  30. [38]

    Xiaohui Pan, Guiqiong Xu, Bing Wang, and Tao Zhang. 2019. A Novel Community Detection Algorithm Based on Local Similarity of Clustering Coefficient in Social Networks. IEEE Access 7 (2019), 121586–121598. https://doi.org/10.1109/access. 2019.2937580

    2019

  31. [39]

    Seshadhri

    Noujan Pashanasangi and C. Seshadhri. 2020. Efficiently Counting Vertex Orbits of All 5-vertex Subgraphs, by EVOKE. In Proceedings of the 13th International Conference on Web Search and Data Mining (WSDM ’20) . ACM. https://doi.org/ 10.1145/3336191.3371773

    2020

  32. [40]

    Leonardo Pellegrina. 2023. Efficient Centrality Maximization with Rademacher Averages. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining . ACM. https://doi.org/10.1145/3580305.3599325

    2023

  33. [41]

    Leonardo Pellegrina and Fabio Vandin. 2023. SILVAN: Estimating Betweenness Centralities with Progressive Sampling and Non-uniform Rademacher Bounds. ACM Transactions on Knowledge Discovery from Data 18, 3 (Dec. 2023), 1–55. https://doi.org/10.1145/3628601

    2023 doi

  34. [42]

    Mahmudur Rahman, Mansurul Alam Bhuiyan, and Mohammad Al Hasan. 2014. Graft: An Efficient Graphlet Counting Method for Large Graph Analysis. IEEE Transactions on Knowledge and Data Engineering 26, 10 (Oct. 2014), 2466–2478. https://doi.org/10.1109/tkde.2013.2297929

    2014

  35. [43]

    Matteo Riondato and Eli Upfal. 2018. ABRA: Approximating Betweenness Centrality in Static and Dynamic Graphs with Rademacher Averages. ACM Transactions on Knowledge Discovery from Data 12, 5 (July 2018), 1–38. https: //doi.org/10.1145/3208351

    2018 doi

  36. [44]

    Matteo Riondato and Fabio Vandin. 2018. MiSoSouP: Mining Interesting Sub- groups with Sampling and Pseudodimension. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD ’18). ACM. https://doi.org/10.1145/3219819.3219989

    2018

  37. [45]

    Ryan Rossi and Nesreen Ahmed. 2015. The Network Data Repository with Interactive Graph Analytics and Visualization.Proceedings of the AAAI Conference on Artificial Intelligence 29, 1 (March 2015). https://doi.org/10.1609/aaai.v29i1. 9277

    2015 doi

  38. [46]

    Rossi, Nesreen K

    Ryan A. Rossi, Nesreen K. Ahmed, Aldo Carranza, David Arbour, Anup Rao, Sungchul Kim, and Eunyee Koh. 2019. Heterogeneous Network Motifs. (Jan. 2019). https://doi.org/10.48550/ARXIV.1901.10026 arXiv:1901.10026 [cs.SI]

    2019 doi arXiv

  39. [47]

    Rossi, Anup Rao, Tung Mai, and Nesreen K

    Ryan A. Rossi, Anup Rao, Tung Mai, and Nesreen K. Ahmed. 2020. Fast and Accurate Estimation of Typed Graphlets. In Companion Proceedings of the Web Conference 2020. ACM. https://doi.org/10.1145/3366424.3382683

    2020

  40. [48]

    Thomas Schank and Dorothea Wagner. 2005. Approximating Clustering Coeffi- cient and Transitivity. Journal of Graph Algorithms and Applications 9, 2 (2005), 265–275. https://doi.org/10.7155/jgaa.00108

    2005 doi

  41. [49]

    Seshadhri, Ali Pinar, and Tamara G

    C. Seshadhri, Ali Pinar, and Tamara G. Kolda. 2014. Wedge sampling for com- puting clustering coefficients and triangle counts on large graphs. Statistical Analysis and Data Mining: The ASA Data Science Journal 7, 4 (may 2014), 294–307. https://doi.org/10.1002/sam.11224

    2014 doi

  42. [50]

    Comandur Seshadhri and Srikanta Tirthapura. 2019. Scalable Subgraph Counting: The Methods Behind The Madness. In Companion Proceedings of The 2019 World Wide Web Conference (WWW ’19) . ACM, 1317–1318. https://doi.org/10.1145/ 3308560.3320092

    2019

  43. [51]

    Shai Shalev-Shwartz. 2014. Understanding machine learning. Cambrige University Press, Cambridge. Hier auch später erschienene, unveränderte Nachdrucke

    2014

  44. [52]

    Shubhanshu Shekhar and Aaditya Ramdas. 2023. On the near-optimality of betting confidence sets for bounded means. https://doi.org/10.48550/ARXIV. 2310.01547

    2023 doi arXiv

  45. [53]

    Chuan Shi, Yitong Li, Jiawei Zhang, Yizhou Sun, and Philip S. Yu. 2017. A survey of heterogeneous information network analysis. IEEE Transactions on Knowledge and Data Engineering 29, 1 (Jan. 2017), 17–37. https://doi.org/10.1109/tkde.2016. 2598561

    2017 doi

  46. [54]

    Kijung Shin. 2017. WRS: Waiting Room Sampling for Accurate Triangle Counting in Real Graph Streams. In 2017 IEEE International Conference on Data Mining (ICDM). IEEE, 1087–1092. https://doi.org/10.1109/icdm.2017.143

    2017 doi

  47. [55]

    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 14, 2 (Feb. 2020), 1–39. https://doi.org/10.1145/3375392

    2020 doi

  48. [56]

    Lorenzo De Stefani, Alessandro Epasto, Matteo Riondato, and Eli Upfal. 2017. TRIÈST: Counting Local and Global Triangles in Fully Dynamic Streams with Fixed Memory Size. ACM Transactions on Knowledge Discovery from Data 11, 4 (June 2017), 1–50. https://doi.org/10.1145/3059194

    2017 doi

  49. [57]

    Yizhou Sun and Jiawei Han. 2013. Mining heterogeneous information networks: a structural analysis approach. ACM SIGKDD explorations newsletter 14, 2 (2013), 20–28

    2013

  50. [58]

    Tsourakakis, U

    Charalampos E. Tsourakakis, U. Kang, Gary L. Miller, and Christos Faloutsos

  51. [59]

    Johan Ugander, Brian Karrer, Lars Backstrom, and Cameron Marlow. 2011. The Anatomy of the Facebook Social Graph. https://doi.org/10.48550/ARXIV.1111. 4503

    2011 doi

  52. [60]

    Lui, Don Towsley, Jing Tao, and Xiaohong Guan

    Pinghui Wang, Junzhou Zhao, Xiangliang Zhang, Zhenguo Li, Jiefeng Cheng, John C.S. Lui, Don Towsley, Jing Tao, and Xiaohong Guan. 2018. MOSS-5: A Fast Method of Approximating Counts of 5-Node Graphlets in Large Graphs. IEEE Transactions on Knowledge and Data Engineering 30, 1 ...

    2018

  53. [61]

    Watts and Steven H

    Duncan J. Watts and Steven H. Strogatz. 1998. Collective dynamics of ‘small- world’ networks. Nature 393, 6684 (jun 1998), 440–442. https://doi.org/10.1038/ 30918

    1998

  54. [62]

    Ian Waudby-Smith and Aaditya Ramdas. 2023. Estimating means of bounded random variables by betting. Journal of the Royal Statistical Society Series B: Statistical Methodology 86, 1 (Feb. 2023), 1–27. https://doi.org/10.1093/jrsssb/ qkad009

    2023 doi

  55. [63]

    Zhihao Wu, Youfang Lin, Jing Wang, and Steve Gregory. 2016. Link predic- tion with node clustering coefficient. Physica A: Statistical Mechanics and its Applications 452 (June 2016), 1–8. https://doi.org/10.1016/j.physa.2016.01.038

    2016 doi

  56. [64]

    Junming Xu. 2001. Topological Structure and Analysis of Interconnection Networks . Springer US. https://doi.org/10.1007/978-1-4757-3387-7

    2001 doi

  57. [65]

    Benson, and Jure Leskovec

    Hao Yin, Austin R. Benson, and Jure Leskovec. 2018. Higher-order clustering in networks. Physical Review E 97, 5 (May 2018), 052306. https://doi.org/10.1103/ physreve.97.052306

    2018

  58. [66]

    Benson, and Jure Leskovec

    Hao Yin, Austin R. Benson, and Jure Leskovec. 2019. The Local Closure Coefficient: A New Perspective On Network Clustering. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining (WSDM ’19) . ACM. https://doi.org/10.1145/3289600.3290991

    2019

  59. [67]

    Benson, Jure Leskovec, and David F

    Hao Yin, Austin R. Benson, Jure Leskovec, and David F. Gleich. 2017. Local Higher- Order Graph Clustering. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’17) . ACM. https: //doi.org/10.1145/3097983.3098069

    2017

  60. [68]

    M. Yuan. 2024. Central limit theorem for the average closure coefficient. Acta Mathematica Hungarica 172, 2 (March 2024), 543–569. https://doi.org/10.1007/ s10474-024-01416-z

    2024

  61. [69]

    Chi Zhang, Wenkai Xiang, Xingzhi Guo, Baojian Zhou, and Deqing Yang

  62. [70]

    2017.Efficient Local Clustering Coefficient Estimation in Massive Graphs

    Hao Zhang, Yuanyuan Zhu, Lu Qin, Hong Cheng, and Jeffrey Xu Yu. 2017.Efficient Local Clustering Coefficient Estimation in Massive Graphs . Springer International Publishing, 371–386. https://doi.org/10.1007/978-3-319-55699-4_23

    2017 doi

  63. [71]

    𝑋𝑒1 = 1”, and 𝐼′ “𝑋𝑒2 = 1

    Kangfei Zhao, Jeffrey Xu Yu, Hao Zhang, Qiyan Li, and Yu Rong. 2021. A Learned Sketch for Subgraph Counting. In Proceedings of the 2021 International Conference on Management of Data (SIGMOD/PODS ’21) . ACM. https://doi.org/10.1145/ 3448016.3457289 A MISSING PROOFS Proof of Le...

    2021

  64. [76]

    w = closed

    By a similar argument to the proof of Theorem 3.8 consider an element of the form 𝑒 =(𝑢,𝑥) in the shattered set 𝑄 such that |𝑄| = 𝜁 , then the two nodes forming the edge 𝑒 ={𝑢,𝑣} do not contribute to the functions𝑓𝑗(𝑒) for the partitions they belong to, that is 2𝜁−1≤ b𝜒′, taki...

    2009

  65. [632]

    https://doi.org/10.1007/978-3-540-75520-3_55

    doi

  66. [2009]

    In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining

    DOULION. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining . ACM. https://doi.org/10.1145/1557019. 1557111

    doi

  67. [2014]

    SIAM Journal on Scientific Computing 36, 5 (jan 2014), S48–S77

    Counting Triangles in Massive Graphs with MapReduce. SIAM Journal on Scientific Computing 36, 5 (jan 2014), S48–S77. https://doi.org/10.1137/13090729x

    2014 doi

  68. [2023]

    In 2023 IEEE International Conference on Data Mining Workshops (ICDMW)

    SubAnom: Efficient Subgraph Anomaly Detection Framework over Dy- namic Graphs. In 2023 IEEE International Conference on Data Mining Workshops (ICDMW). IEEE, 1178–1185. https://doi.org/10.1109/icdmw60847.2023.00154

    2023

Pith tools

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