Compact Conformal Subgraphs

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 calibration. Our results therefore not only highlight an algorithmic regime, distinct from classical densest-k-subgraph hardness settings, where the problem can be approximated efficiently, but also bridge conformal prediction with combinatorial graph compression via monotonicity. We finally validate our algorithmic approach via simulations for trip planning and navigation, and compare to natural baselines.

Modern AI systems often need to make predictions about complex, structured decisions—like planning routes, recommending sequences of actions, or navigating through a map. It’s important not just to make a single prediction, but to also quantify uncertainty: what other possibilities are plausible? Conformal prediction is a popular method that provides strong, mathematically guaranteed uncertainty estimates without making assumptions about the data. However, when applied to structured problems, it often produces very large sets of possible answers, which can be impractical to use. In this work, we propose a new method to make these uncertainty sets much smaller and more useful. Instead of listing many individual possibilities, we represent them as a compact graph—a structured summary that still captures the most likely outcomes. Our approach carefully selects a small subgraph that preserves most of the probability mass while reducing complexity. We develop efficient algorithms for finding such compact representations and show that they maintain the same statistical guarantees as conformal prediction. A key insight is that our method has a “nestedness” property, which ensures it works correctly with conformal calibration. This property arises from a connection to classical graph optimization techniques. Overall, our work bridges ideas from uncertainty quantification and graph algorithms, enabling more practical and interpretable uncertainty estimates for complex decision-making tasks. We demonstrate its effectiveness on simulated problems such as trip planning and navigation, where it produces smaller and more informative prediction sets compared to standard approaches.