Quasi-stable Coloring for Graph Compression
Summary: Introduces quasi-stable coloring, the first approximate color-refinement scheme, trading graph compression for representation accuracy beyond strict symmetries. Establishes approximation benefits for LP, max-flow, and betweenness centrality; maximal coloring is NP-hard, addressed heuristically. (summarized by gpt-5.6-luna on Jul 24 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Moe Kayali (University of Washington)
- 2. Dan Suciu (University of Washington)
BibTeX Citation
@article{kayali_vldb23,
title = {{Quasi-stable Coloring for Graph Compression}},
author = {Kayali, Moe and Suciu, Dan},
journal = {PVLDB},
series = {{VLDB} '23},
volume = {16},
number = {4},
pages = {803--815},
doi = {10.14778/3574245.3574264},
url = {https://doi.org/10.14778/3574245.3574264},
year = {2023}
}Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
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,411 | word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data | 2020 | PODS | 0.00010852334 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 10,598 | Scalable Approximate Biclique Counting over Large Bipartite Graphs | 2026 | VLDB |
| 2 | 548 | Graph Summarization with Bounded Error | 2008 | SIGMOD |
| 3 | 9,749 | Auto-Approximation of Graph Computing | 2014 | VLDB |
| 4 | 4,474 | Querying Big Graphs within Bounded Resources | 2014 | SIGMOD |
| 5 | 10,027 | Color: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation | 2025 | VLDB |
| 6 | 7,578 | Minimum Strongly Connected Subgraph Collection in Dynamic Graphs | 2024 | VLDB |
| 7 | 1,336 | Query Preserving Graph Compression | 2012 | SIGMOD |
| 8 | 9,387 | Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs | 2024 | VLDB |
| 9 | 9,060 | Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms | 2023 | PODS |
| 10 | 5,797 | Effective and Efficient Dynamic Graph Coloring | 2018 | VLDB |