Research map / Graph learning / Graph algorithms and clustering
Individual Fairness in Graph Decomposition
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows classic KPR low-diameter decomposition can never separate some close pairs in planar graphs, and gives randomized planar LDD variants trading off individual fairness (lower bounds on separation probability) against connectivity and compression.
Problem
Randomized low-diameter decomposition of planar graphs should separate pairs of nodes with probability comparable to their distance (individual fairness), but the classic KPR procedure gives only an upper bound on separation and can fail to separate some pairs at all.
Approach
Modify KPR with random vertex weights (for edges), two cut sequences per phase, random diameter parameters, or embedding-plus-random-projection, obtaining two-sided separation bounds Theta(rho) with trade-offs in connectivity (CON) and compression (COMP); also tie ideal Theta(rho) fairness to the open l1-embedding distortion question for planar graphs.
Key results
- Theorem shows KPR never separates some pair at distance d for R > 2d, so its lower bound g(rho) is zero.
- Random vertex-weight KPR gives every edge separation probability in [1/(2R), 3/R] while keeping connectivity and O(n/R) expected components.
- On NC, MD, PA precinct graphs with R=5, the random-weight variant's edge separation probabilities are more uniform than KPR's; the number of clusters stays below n/R empirically.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add random vertex weights to KPR | KPR on planar graph edges · Planar graphs (edges) | separation probability lower bound: 0 -> \frac{1}{2R} | Helped |
| add random vertex weights to KPR | KPR on planar graph edges · Planar graphs (edges) | separation probability upper bound: 3 · ρ_uv -> \frac{3}{R} | Mixed |
| use two cut sequences per phase, including a randomized offset | KPR on planar graphs · Planar graphs (all pairs) | separation probability lower bound: 0 -> \Omega(\epsilon^2 \cdot \rho^{2+\epsilon}) | Helped |
| sample the KPR radius from a distribution instead of fixing it at R | KPR on planar graphs · Planar graphs (all pairs) | separation probability lower bound: 0 -> \Omega(\epsilon \cdot \rho^{1+\epsilon}) | Helped |
| project a Euclidean embedding onto a random line and partition by random shifts | Planar graph LDD · Planar graphs (all pairs) | separation probability lower bound: 0 -> \Omega\left(\frac{\rho}{\sqrt{\log R}}\right) | Helped |
| use KPR without random vertex weights | KPR on planar graphs · Planar graphs (all pairs) | individual fairness lower bound: \frac{1}{2R} -> 0 | Hurt |
| choose BFS roots uniformly at random instead of adversarially | KPR on planar graphs · Planar graphs (all pairs) | separation probability lower bound | No clear effect |
| run the random-diameter KPR procedure with α=0 | KPR with random diameter · Planar graphs (all pairs) | separation probability lower bound: \left(\frac{\rho_{uv}}{43}\right) -> | Helped |
| violate connectivity and compression using Euclidean embedding and random projection | Planar graph LDD · Planar graphs (all pairs) | separation probability lower bound: \Omega\left(\frac{\rho}{\sqrt{\log R}}\right) | Helped |
| use KPR with random vertex weights instead of KPR | Precinct graph decompositions · North Carolina, Maryland, Pennsylvania (edges) | edge separation probability fairness | Helped |
| use KPR with random vertex weights instead of KPR with uniformly random roots | Precinct graph decompositions · North Carolina, Maryland, Pennsylvania (edges) | edge separation probability fairness | Helped |
| use KPR with random vertex weights | Precinct graph decompositions with R=5 · North Carolina, Maryland, Pennsylvania | number of clusters: n/R -> empirically smaller than n/R | Helped |
Surprising findings
- Classic KPR can fail individual fairness entirely: some pairs at any distance d are never separated, even edges.
- Randomizing BFS roots does not help KPR's individual fairness beyond a 1/poly(n) lower bound.
Limitations
- Full Theta(rho) individual fairness for general distances would resolve a major open conjecture on l1 embedding of planar graphs, so the best bounds are weaker.
- Some variants violate connectivity or compression (COMP), trading off desiderata.
- Experiments only cover edges (d=1) on three US state precinct graphs.
Experimental setup
Datasets: MGGG precinct graphs (North Carolina, Maryland, Pennsylvania)
Metrics: edge separation probability number of clusters maximum cluster diameter
Baselines: KPR
Builds on: KPR decomposition Chang-Eilers-type cop decompositions
Closest papers by meaning
- A Little Charity Guarantees Fair Connected Graph Partitioning (AAAI 2022 · similarity 0.87)
- Fair Short Paths in Vertex-Colored Graphs (AAAI 2023 · similarity 0.87)
- Proportional Fairness in Clustering: A Social Choice Perspective (NeurIPS 2024 · similarity 0.87)
- The Price of Connectivity in Fair Division (AAAI 2021 · similarity 0.86)
- Proportionally Fair Matching via Randomized Rounding (AAAI 2025 · similarity 0.86)
- Balanced and Fair Partitioning of Friends (AAAI 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.