コンパクトな準同型サブグラフ

arXiv:2602.07530v1 発表 タイプ：new 摘要：準同型予測は厳密な、分布に依存しない不確実性保証を提供しますが、経路計画、計画、順列推奨などの構造化されたドメインでは、しばしば不適切に大きな予測セットを出力します。私たちは「準同型圧縮」を導入しました。このフレームワークは、統計的な妥当性を保ちつつ構造的な複雑性を低減するコンパクトなサブグラフの構成方法を提供します。私たちは圧縮を、指定された確率質量の分数をキャッチする最小サブグラフを選択することとして形式化し、サブグラフが大量のエッジを持つ領域では、超グラフの最も高密度 k サブグラフの重み付けバージョンに戻しました。私たちは、定数倍の被覆率和サイズのトレードオフを実現する効率的な近似アルゴリズムを設計しました。至关重要的是，我々は、この緩和がパラメトリックな最小切断への接続から導かれた単調性を満たすことを証明しました。これは、準同型保証に必要な入れ子構造を保証します。結果は、一方では単調性を介して効率的な準同型予測と組み合わせグラフ圧縮を結び付け、統計的な妥当性と圧縮（サイズ）の両方に対して厳密な保証を提供し、他方では、古典的な最も高密度 k サブグラフの難易度設定とは異なるアルゴリズム的領域を強調しました。これは、この問題は効率的に近似可能であることを意味します。最後に、私たちは乗客計画とナビゲーションのためのシミュレーションを通じて our アルゴリズム的アプローチを検証し、自然な基準と比較しました。

arXiv:2602.07530v1 Announce Type: new 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.