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,877 | Color: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation | 2025 | VLDB | 4.2656547e-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,190 | word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data | 2020 | PODS | 0.00013438056 |
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 10,300 | Scalable Approximate Biclique Counting over Large Bipartite Graphs | 2026 | VLDB | 4.1945683e-05 |
| 388 | Graph Summarization with Bounded Error | 2008 | SIGMOD | 0.00024662272 |
| 9,614 | Auto-Approximation of Graph Computing | 2014 | VLDB | 4.3177432e-05 |
| 4,211 | Querying Big Graphs within Bounded Resources | 2014 | SIGMOD | 6.3563454e-05 |
| 9,877 | Color: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation | 2025 | VLDB | 4.2656547e-05 |
| 7,716 | Minimum Strongly Connected Subgraph Collection in Dynamic Graphs | 2024 | VLDB | 4.6696364e-05 |
| 1,579 | Query Preserving Graph Compression | 2012 | SIGMOD | 0.00011283792 |
| 9,239 | Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs | 2024 | VLDB | 4.3690661e-05 |
| 8,905 | Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms | 2023 | PODS | 4.427232e-05 |
| 5,751 | Effective and Efficient Dynamic Graph Coloring | 2018 | VLDB | 5.3409543e-05 |