Compact Conformal Subgraphs

View PDF HTML (experimental)

Abstract: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.

Subjects:

Machine Learning (cs.LG); Data Structures and Algorithms (cs.DS)

Cite as: arXiv:2602.07530 [cs.LG]

(or arXiv:2602.07530v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2602.07530

arXiv-issued DOI via DataCite

Submission history

From: Kamesh Munagala [view email] [v1] Sat, 7 Feb 2026 12:55:54 UTC (839 KB) [v2] Fri, 27 Mar 2026 21:19:08 UTC (580 KB)