Play like a Vertex: A Stackelberg Game Approach for Streaming Graph Partitioning

Summary: Streaming vertex-cut partitioning for massive graphs via S5P, a skewness-aware method that splits edges into head/tail sets, clusters them, then solves a Stackelberg game to exploit degree skew. Yields better balance/communication than prior skew-oblivious streaming partitioners, up to 51% quality gain and 81% lower communication cost. (summarized by gpt-5.4-mini on May 24 2026)

Paper ID: 6988
Venue: SIGMOD
Year: 2024
Pagerank: 5.8381749e-05
Overall Rank: 6,566 | 54.96%
DOI: 10.1145/3654965

Incoming Non-self Citations Over Time

Authors

1. Zezhong Ding (Data Darkness Lab; MIRACLE Center; Suzhou Institute for Advanced Research, University of Science and Technology of China; University of Science and Technology Beijing)
2. Yongan Xiang (University of Science and Technology Beijing)
3. Shangyou Wang (University of Science and Technology Beijing)
4. Xike Xie (Data Darkness Lab; MIRACLE Center; Suzhou Institute for Advanced Research, University of Science and Technology of China; University of Science and Technology Beijing)
5. S. Kevin Zhou (MIRACLE Center; Suzhou Institute for Advanced Research, University of Science and Technology of China; University of Science and Technology Beijing)

BibTeX Citation

@inproceedings{ding_sigmod24,
        title = {{Play like a Vertex: A Stackelberg Game Approach for Streaming Graph Partitioning}},
        author = {Ding, Zezhong and Xiang, Yongan and Wang, Shangyou and Xie, Xike and Zhou, S. Kevin},
        series = {{SIGMOD} '24},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3654965},
        url = {https://dl.acm.org/doi/10.1145/3654965},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,440	DiskGNN: Bridging I/O Efficiency and Model Accuracy for Out-of-Core GNN Training	2025	SIGMOD	5.8782861e-05
9,879	Capsule*: An Out-of-Core Training Mechanism for Colossal GNNs	2025	SIGMOD	5.2040783e-05
10,330	SWIFT: Enabling Large-Scale Temporal Graph Learning on a Single Machine	2026	SIGMOD	5.093636e-05
11,108	Efficient Graph Embedding Generation and Update for Large-Scale Temporal Graph	2025	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
3	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0012250108
20	Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud	2012	VLDB	0.00056944564
223	AliGraph: A Comprehensive Graph Neural Network Platform	2019	VLDB	0.00024182473
937	Blogel: A Block-Centric Framework for Distributed Computation on Real-World Graphs	2014	VLDB	0.00013091546
2,148	Graph Stream Summarization: From Big Bang to Big Crunch	2016	SIGMOD	9.0825156e-05
3,752	Distributed Edge Partitioning for Trillion-edge Graphs	2019	VLDB	7.15217e-05
3,962	Real-Time Multi-Criteria Social Graph Partitioning: A Game Theoretic Approach	2015	SIGMOD	6.9865803e-05
5,610	Hybrid Edge Partitioner: Partitioning Large Power-Law Graphs under Memory Constraints	2021	SIGMOD	6.1508076e-05
6,457	TrillionG: A Trillion-scale Synthetic Graph Generator using a Recursive Vector Model	2017	SIGMOD	5.8741671e-05
8,647	Auxo: A Scalable and Efficient Graph Stream Summarization Structure	2023	VLDB	5.3921304e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,752	Distributed Edge Partitioning for Trillion-edge Graphs	2019	VLDB
2	11,238	FSM: A Fine-grained Splitting and Merging Framework for Dual-balanced Graph Partition	2024	VLDB
3	487	From "Think Like a Vertex" to "Think Like a Graph"	2014	VLDB
4	9,218	GraphTwist: Fast Iterative Graph Computation with Two-tier Optimizations	2015	VLDB
5	7,362	A Study of Partitioning Policies for Graph Analytics on Large-scale Distributed Platforms	2019	VLDB
6	1,865	An Experimental Comparison of Partitioning Strategies in Distributed Graph Processing	2017	VLDB
7	3,225	A Scalable Distributed Graph Partitioner	2015	VLDB
8	3,362	Experimental Analysis of Streaming Algorithms for Graph Partitioning	2019	SIGMOD
9	5,610	Hybrid Edge Partitioner: Partitioning Large Power-Law Graphs under Memory Constraints	2021	SIGMOD
10	2,221	Streaming Graph Partitioning: An Experimental Study	2018	VLDB