A General Framework for Estimating Graphlet Statistics via Random Walk

Summary: General framework to estimate graphlet statistics of any size from large graphs via consecutive random-walk samples. Unbiased estimator with Chernoff-Hoeffding sample-size bound and two optimization techniques reduce required samples; experiments show up to an order of magnitude gains in accuracy and time over prior methods. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11712
Venue: VLDB
Year: 2017
Pagerank: 9.4093057e-05
Overall Rank: 1,958 | 86.57%
DOI: 10.14778/3021924.3021940

Incoming Non-self Citations Over Time

Authors

1. Xiaowei Chen (Chinese University of Hong Kong)
2. Yongkun Li (University of Science and Technology Beijing)
3. Pinghui Wang (Xi'an Jiaotong University)
4. John C.S. Lui (Chinese University of Hong Kong)

BibTeX Citation

@article{chen_vldb17,
        title = {{A General Framework for Estimating Graphlet Statistics via Random Walk}},
        author = {Chen, Xiaowei and Li, Yongkun and Wang, Pinghui and Lui, John C.S.},
        journal = {PVLDB},
        series = {{VLDB} '17},
        volume = {10},
        number = {3},
        pages = {253--264},
        doi = {10.14778/3021924.3021940},
        url = {https://doi.org/10.14778/3021924.3021940},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,028	Motivo: fast motif counting via succinct color coding and adaptive sampling	2019	VLDB	7.8349117e-05
5,506	Accurate and Fast Approximate Graph Pattern Mining at Scale	2025	VLDB	6.1925892e-05
5,598	Hypergraph Motifs: Concepts, Algorithms, and Discoveries	2020	VLDB	6.1546212e-05
6,866	Towards Plug-and-Play Visual Graph Query Interfaces: Data-driven Selection of Canned Patterns for Large Networks	2021	VLDB	5.7507099e-05
8,019	Efficient Maximal Motif-Clique Enumeration over Large Heterogeneous Information Networks	2024	VLDB	5.5062157e-05
8,251	Fast Local Subgraph Counting	2024	VLDB	5.4574671e-05
10,192	An Efficient Streaming Algorithm for Approximating Graphlet Distributions	2026	SIGMOD	5.093636e-05
10,575	AGIS: Fast Approximate Graph Pattern Mining with Structure-Informed Sampling	2026	VLDB	5.093636e-05
11,165	gSWORD: GPU-accelerated Sampling for Subgraph Counting	2024	SIGMOD	5.093636e-05
11,690	On Analyzing Graphs with Motif-Paths	2021	VLDB	5.093636e-05
11,757	Factorized Graph Representations for Semi-Supervised Learning from Sparse Data	2020	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
4,497	Leveraging History for Faster Sampling of Online Social Networks	2015	VLDB	6.6618536e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,228	FlowWalker: A Memory-efficient and High-performance GPU-based Dynamic Graph Random Walk Framework	2024	VLDB
2	7,201	An I/O-Efficient Disk-based Graph System for Scalable Second-Order Random Walk of Large Graphs	2022	VLDB
3	1,396	Estimating PageRank on Graph Streams	2008	PODS
4	10,192	An Efficient Streaming Algorithm for Approximating Graphlet Distributions	2026	SIGMOD
5	13,359	A Sampling-based Framework for Hypothesis Testing on Large Attributed Graphs	2024	VLDB
6	4,572	On the Embeddability of Random Walk Distances	2013	VLDB
7	5,687	Walk, Not Wait: Faster Sampling Over Online Social Networks	2015	VLDB
8	8,054	Approximating Aggregate Queries about Web Pages via Random Walks	2000	VLDB
9	6,423	Memory-Aware Framework for Efficient Second-Order Random Walk on Large Graphs	2020	SIGMOD
10	4,497	Leveraging History for Faster Sampling of Online Social Networks	2015	VLDB