論文の概要: Compact Conformal Subgraphs

• arxiv url: http://arxiv.org/abs/2602.07530v1
• Date: Sat, 07 Feb 2026 12:55:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-10 20:26:24.671295
• Title: Compact Conformal Subgraphs
• Title（参考訳）: コンパクトコンフォーマルな部分グラフ
• Authors: Sreenivas Gollapudi, Kostas Kollias, Kamesh Munagala, Aravindan Vijayaraghavan,
• Abstract要約: グラフベース共形圧縮(graph-based conformal compression)は、コンパクトな部分グラフを構築するためのフレームワークである。 定数係数カバレッジとサイズトレードオフを実現する効率的な近似アルゴリズムを設計する。
• 参考スコア（独自算出の注目度）: 19.72191566715581
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.
• Abstract（参考訳）: 整合予測は厳密で分布のない不確実性を保証するが、しばしばルーティング、計画、シーケンシャルレコメンデーションといった構造化ドメインにおいて、非常に大きな予測セットをもたらす。 構造的複雑性を低減しつつ統計的妥当性を保ちながらコンパクトな部分グラフを構築するためのフレームワークである「グラフベース共形圧縮」を紹介する。 我々は, 圧縮を, 確率質量の所定の割合を捉えた最小の部分グラフの選択として定式化し, ハイパーグラフにおける最も高密度な$k$-部分グラフの重み付け版に還元する。 定数係数カバレッジとサイズトレードオフを実現する効率的な近似アルゴリズムを設計する。 重要なことは、我々の緩和がパラメトリックな最小カットへの接続から導かれる単調性特性を満たすことを証明し、これは有効な共形保証に必要となるネスト性を保証する。 本研究の結果は, 単調性による組合せグラフ圧縮による共形予測を効果的に行い, 統計的妥当性, 圧縮, サイズともに厳密な保証を提供する。 一方、アルゴリズムは古典的な高密度なk$サブグラフの硬度設定と異なり、この問題を効率的に近似できるアルゴリズム体系も強調している。 最終的に、旅行計画とナビゲーションのシミュレーションによるアルゴリズムアプローチを検証するとともに、自然なベースラインと比較する。

関連論文リスト

• Epistemic Uncertainty in Conformal Scores: A Unified Approach [2.449909275410288]
  等角予測法は、分布のない保証を持つ予測帯域を生成するが、不確実性を明示的に捉えることはできない。 モデルに依存しないアプローチである $texttEPICSCORE$ を導入する。 $texttEPICSCORE$は、限られたデータを持つ領域の予測間隔を適応的に拡張し、データが豊富であるコンパクト間隔を維持します。
  論文  参考訳（メタデータ） (2025-02-10T19:42:54Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Uncertainty-aware Efficient Subgraph Isomorphism using Graph Topology [10.922787879808576]
  部分グラフ同型 (subgraph isomorphism) あるいは部分グラフマッチング (subgraph matching) は一般にNP完全問題とみなされる。 本稿では,ノードラベルのない不正確な場合において,サブグラフとフルグラフのノード対応を同定する手法を提案する。
  論文  参考訳（メタデータ） (2022-09-15T02:45:05Z)
• Distributed Sketching for Randomized Optimization: Exact Characterization, Concentration and Lower Bounds [54.51566432934556]
  我々はヘシアンの形成が困難である問題に対する分散最適化法を検討する。 ランダム化されたスケッチを利用して、問題の次元を減らし、プライバシを保ち、非同期分散システムにおけるストラグラーレジリエンスを改善します。
  論文  参考訳（メタデータ） (2022-03-18T05:49:13Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。 提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
  論文  参考訳（メタデータ） (2022-01-05T13:37:27Z)
• Partition and Code: learning how to compress graphs [50.29024357495154]
  まず、分割アルゴリズムがグラフを基本構造に分解し、これらを確率分布を学習する小さな辞書の要素にマッピングし、エントロピーエンコーダが表現をビットに変換する。 提案アルゴリズムは,非パラメトリックおよびパラメトリックグラフ圧縮器の異なるファミリーに対して,多種多様な実世界のネットワーク上で定量的に評価し,大幅な性能向上を実現している。
  論文  参考訳（メタデータ） (2021-07-05T11:41:16Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• On Compression Principle and Bayesian Optimization for Neural Networks [0.0]
  本稿では,全てのデータとモデル定義の合計圧縮メッセージ長を最小化しつつ,デオードビリティを保証しながら,最適な予測モデルを提案する圧縮原理を提案する。 圧縮原理によって要求される最適ネットワーク次元を求めることができる連続的な次元削減にドロップアウトが利用できることを示す。
  論文  参考訳（メタデータ） (2020-06-23T03:23:47Z)
• An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits [34.06611065493047]
  本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。 サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。 また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-21T00:56:33Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。