Motivo: fast motif counting via succinct color coding and adaptive sampling

Summary: Motivo scales color-coding motif counting to billion-edge graphs via succinct structures and biased coloring. Fractional-set-cover adaptive sampling breaks the additive-approximation barrier, providing multiplicative estimates for rare and frequent motifs on commodity hardware. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 12042
Venue: VLDB
Year: 2019
Pagerank: 7.8349117e-05
Overall Rank: 3,028 | 79.23%
DOI: 10.14778/3342263.3342640

Incoming Non-self Citations Over Time

Authors

1. Marco Bressan (Sapienza University)
2. Stefano Leucci (Max Planck Institute)
3. Alessandro Panconesi (Sapienza University)

BibTeX Citation

@article{bressan_vldb19,
        title = {{Motivo: fast motif counting via succinct color coding and adaptive sampling}},
        author = {Bressan, Marco and Leucci, Stefano and Panconesi, Alessandro},
        journal = {PVLDB},
        series = {{VLDB} '19},
        volume = {12},
        number = {11},
        pages = {1651--1663},
        doi = {10.14778/3342263.3342640},
        url = {https://doi.org/10.14778/3342263.3342640},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,731	Neural Subgraph Counting with Wasserstein Estimator	2022	SIGMOD	8.1959181e-05
3,283	A Learned Sketch for Subgraph Counting	2021	SIGMOD	7.56675e-05
4,143	Efficient Biclique Counting in Large Bipartite Graphs	2023	SIGMOD	6.8760066e-05
5,208	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB	6.3165129e-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
5,942	Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach	2024	VLDB	6.0334209e-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,546	TIMEST: Temporal Information Motif Estimator Using Sampling Trees	2026	VLDB	5.093636e-05
10,877	Efficient and Adaptive Estimation of Local Triadic Coefficients	2025	VLDB	5.093636e-05
10,885	Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach	2025	VLDB	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
1,958	A General Framework for Estimating Graphlet Statistics via Random Walk	2017	VLDB	9.4093057e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,072	Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds	2025	VLDB
2	4,581	Mining Graph Patterns Efficiently via Randomized Summaries	2009	VLDB
3	5,797	Effective and Efficient Dynamic Graph Coloring	2018	VLDB
4	10,598	Scalable Approximate Biclique Counting over Large Bipartite Graphs	2026	VLDB
5	5,603	Output Space Sampling for Graph Patterns	2009	VLDB
6	10,546	TIMEST: Temporal Information Motif Estimator Using Sampling Trees	2026	VLDB
7	11,346	MOSER: Scalable Network Motif Discovery using Serial Test	2024	VLDB
8	8,019	Efficient Maximal Motif-Clique Enumeration over Large Heterogeneous Information Networks	2024	VLDB
9	5,598	Hypergraph Motifs: Concepts, Algorithms, and Discoveries	2020	VLDB
10	11,690	On Analyzing Graphs with Motif-Paths	2021	VLDB