# Compact Conformal Subgraphs

arXiv: https://arxiv.org/abs/2602.07530 · HTML: https://mlsanity.com/paper/2602.07530/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 32 references that are in the map.
- First posted on arXiv 7 Feb 2026.

## Builds on (most cited first, 15 of 15)

- [A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification](https://mlsanity.com/paper/2107.07511/) (2021)
- [Distribution-Free Predictive Inference For Regression](https://mlsanity.com/paper/1604.04173/) (2016)
- [Conformalized Quantile Regression](https://mlsanity.com/paper/1905.03222/) (2019)
- [Least Ambiguous Set-Valued Classifiers with Bounded Error Levels](https://mlsanity.com/paper/1609.00451/) (2016)
- [Learn then Test: Calibrating Predictive Algorithms to Achieve Risk Control](https://mlsanity.com/paper/2110.01052/) (2021)
- [Large language model validity via enhanced conformal prediction methods](https://mlsanity.com/paper/2406.09714/) (2024)
- [CD-split and HPD-split: efficient conformal regions in high dimensions](https://mlsanity.com/paper/2007.12778/) (2020)
- [Flexible distribution-free conditional predictive bands using density estimators](https://mlsanity.com/paper/1910.05575/) (2019)
- [Length Optimization in Conformal Prediction](https://mlsanity.com/paper/2406.18814/) (2024)
- [Conformal Off-policy Prediction](https://mlsanity.com/paper/2206.06711/) (2022)
- [Conformal Predictive Safety Filter for RL Controllers in Dynamic Environments](https://mlsanity.com/paper/2306.02551/) (2023)
- [The Densest k-Subhypergraph Problem](https://mlsanity.com/paper/1605.04284/) (2016)
- [Volume Optimality in Conformal Prediction with Structured Prediction Sets](https://mlsanity.com/paper/2502.16658/) (2025)
- [Computing High-dimensional Confidence Sets for Arbitrary Distributions](https://mlsanity.com/paper/2504.02723/) (2025)
- [Learning Confidence Ellipsoids and Applications to Robust Subspace Recovery](https://mlsanity.com/paper/2512.16875/) (2025)

## Abstract (arXiv)

Conformal prediction provides rigorous, distribution-free uncertainty guarantees, but often yields prohibitively large prediction sets in structured domains such as routing, planning, or sequential recommendation. We introduce "graph-based conformal compression", a framework for constructing compact subgraphs that preserve statistical validity while reducing structural complexity. We formulate compression as selecting a smallest subgraph capturing a prescribed fraction of the probability mass, and reduce to a weighted version of densest k-subgraphs in hypergraphs, in the regime where the subgraph has a large fraction of edges. We design efficient approximation algorithms that achieve constant factor coverage and size trade-offs. Crucially, we prove that our relaxation satisfies a monotonicity property, derived from a connection to parametric minimum cuts, which guarantees the nestedness required for valid conformal guarantees. Our results on the one hand bridge efficient conformal prediction with combinatorial graph compression via monotonicity, to provide rigorous guarantees on both statistical validity, and compression or size. On the other hand, they also highlight an algorithmic regime, distinct from classical densest-k-subgraph hardness settings, where the problem can be approximated efficiently. We finally validate our algorithmic approach via simulations for trip planning and navigation, and compare to natural baselines.