Quasi-stable Coloring for Graph Compression: Approximating Max-Flow, Linear Programs, and Centrality
Summary: Introduce quasi-stable coloring, an approximate variant of color refinement that trades strict symmetry for compression to produce compact, lossy graph summaries enabling approximate LP, max-flow, and betweenness-centrality on reduced graphs. Prove computing a maximal quasi-stable coloring is NP-hard, present a simple heuristic algorithm, and empirically demonstrate strong compression/approximation on real graphs versus prior techniques. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Moe Kayali
- 2. Dan Suciu
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 9,876 | Color: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation | 2025 | VLDB | 4.2615675e-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,188 | word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data | 2020 | PODS | 0.00013431099 |
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 10,312 | Scalable Approximate Biclique Counting over Large Bipartite Graphs | 2026 | VLDB | 4.1905499e-05 |
| 387 | Graph Summarization with Bounded Error | 2008 | SIGMOD | 0.00024682268 |
| 9,614 | Auto-Approximation of Graph Computing | 2014 | VLDB | 4.3136057e-05 |
| 4,207 | Querying Big Graphs within Bounded Resources | 2014 | SIGMOD | 6.3519481e-05 |
| 9,876 | Color: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation | 2025 | VLDB | 4.2615675e-05 |
| 7,714 | Minimum Strongly Connected Subgraph Collection in Dynamic Graphs | 2024 | VLDB | 4.6651585e-05 |
| 1,572 | Query Preserving Graph Compression | 2012 | SIGMOD | 0.00011296109 |
| 9,246 | Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs | 2024 | VLDB | 4.3648789e-05 |
| 8,907 | Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms | 2023 | PODS | 4.4229886e-05 |
| 5,764 | Effective and Efficient Dynamic Graph Coloring | 2018 | VLDB | 5.3358197e-05 |