論文の概要: A Residual-Shell-Based Lower Bound for Ollivier-Ricci Curvature

• arxiv url: http://arxiv.org/abs/2604.12211v1
• Date: Tue, 14 Apr 2026 02:40:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-15 19:11:32.20062
• Title: A Residual-Shell-Based Lower Bound for Ollivier-Ricci Curvature
• Title（参考訳）: Ollivier-Ricci曲率に対する残留シェル型下界
• Authors: Xiang Gu, Huichun Zhang, Jian Sun,
• Abstract要約: Ollivier-Ricci曲率(Ollivier-Ricci curvature、ORC)は、リッチな幾何学的情報を取得するワッサーシュタイン距離によって定義される。 従来の研究では、1ホップランダムウォークに基づくORCのプロキシとして計算効率のよい下界を導入していた。 我々は、計算コストをはるかに低く保ちながら、既存の下限よりもORCのかなり狭い下限を確立する。
• 参考スコア（独自算出の注目度）: 43.85263006081191
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Ollivier-Ricci curvature (ORC), defined via the Wasserstein distance that captures rich geometric information, has received growing attention in both theory and applications. However, the high computational cost of Wasserstein distance evaluation has significantly limited the broader practical use of ORC. To alleviate this issue, previous work introduced a computationally efficient lower bound as a proxy for ORC based on 1-hop random walks, but this approach empirically exhibits large gaps from the exact ORC. In this paper, we establish a substantially tighter lower bound for ORC than the existing lower bound, while retaining much lower computational cost than exact ORC computation, with practical speedups of tens of times. Moreover, our bound is not restricted to 1-hop random walks, but also applies to k-hop random walks (k > 1). Experiments on several fundamental graph structures demonstrate the effectiveness of our bound in terms of both approximation accuracy and computational efficiency.
• Abstract（参考訳）: オリビエ・リッチ曲率(Ollivier-Ricci curvature,ORC)は、ワッサーシュタイン距離で定義され、リッチな幾何学的情報を捉え、理論と応用の両方で注目されている。 しかし、ワッサーシュタイン距離評価の計算コストが高いことは、ORCのより広範な実用的利用を著しく制限している。 この問題を緩和するため、従来の研究は1ホップランダムウォークに基づくORCのプロキシとして計算効率の低い境界を導入したが、この手法は正確なORCとの大きなギャップを経験的に示している。 本稿では,ORCの計算コストを計算コストよりはるかに低く抑えつつ,実際の処理速度を数十倍に抑えながら,ORCの既存の下界よりも大幅に低い境界を確立する。 さらに、1-ホップランダムウォークに限らず、k-ホップランダムウォークにも適用できる(k > 1)。 いくつかの基本グラフ構造に関する実験は、近似精度と計算効率の両方の観点から、我々の境界の有効性を実証している。

関連論文リスト

• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  ROC曲線の下の領域(AUC)は、クラス不均衡と決定制約の両方を持つ実世界のシナリオにおける重要な評価指標である。 PAUC最適化の近似ギャップを埋めるために,2つの簡単なインスタンス単位のミニマックス修正を提案する。 得られたアルゴリズムは、サンプルサイズと典型的な一方方向と双方向のPAUCに対して$O(-2/3)$の収束率の線形パーイテレーション計算複雑性を享受する。
  論文  参考訳（メタデータ） (2025-12-01T02:52:33Z)
• Quantization-based Bounds on the Wasserstein Metric [0.7550566004119158]
  ワッサーシュタイン計量は、多くの機械学習アプリケーションにおいてますます重要になっている。 その魅力にも拘わらず、計算にはコストがかかりすぎることが多い。 より厳密な上界や下界としても機能するワッサーシュタイン計量の効率的な近似計算の課題を考察する。
  論文  参考訳（メタデータ） (2025-06-01T12:06:31Z)
• Accelerated Evaluation of Ollivier-Ricci Curvature Lower Bounds: Bridging Theory and Computation [0.0]
  曲線は強力な記述不変量として機能し、その有効性は理論上も実際上もグラフ理論内で検証される。 我々は、Ollivierによって提唱された一般化リッチ曲率の定義を使用し、LinとYauは後にOllivier-Ricci曲率(ORC)として知られるグラフ理論に適応した。 ORCはワッサーシュタイン距離を用いて曲率を測り、幾何学的概念と確率論と最適輸送を統合する。
  論文  参考訳（メタデータ） (2024-05-22T02:44:46Z)
• A Bound on the Maximal Marginal Degrees of Freedom [0.0]
  本稿では,カーネルリッジ回帰に対する低階近似とサロゲートについて述べる。 我々は,最も一般的な低ランク手法であるNystr"om法(英語版)の計算コストが,サンプルサイズにおいてほぼ線形であることを実証した。 この結果は、関連する積分作用素の範囲の要素による基本核関数の近似の徹底的な理論的解析に基づいている。
  論文  参考訳（メタデータ） (2024-02-20T10:25:44Z)
• Efficient Computation of Counterfactual Bounds [44.4263314637532]
  我々は,構造因果モデルのサブクラスにおけるクレダルネットのアルゴリズムを用いて,正確な反ファクト境界を計算する。 近似の精度を信頼性のある間隔で評価する。
  論文  参考訳（メタデータ） (2023-07-17T07:59:47Z)
• Statistical, Robustness, and Computational Guarantees for Sliced Wasserstein Distances [18.9717974398864]
  スライスされたワッサーシュタイン距離は古典的なワッサーシュタイン距離の性質を保ちながら、高次元での計算と推定によりスケーラブルである。 このスケーラビリティを, (i) 経験的収束率, (ii) データの汚染に対する堅牢性, (iii) 効率的な計算方法という3つの重要な側面から定量化する。
  論文  参考訳（メタデータ） (2022-10-17T15:04:51Z)
• Nystr\"om Kernel Mean Embeddings [92.10208929236826]
  Nystr"om法に基づく効率的な近似手法を提案する。 サブサンプルサイズの条件は標準の$n-1/2$レートを得るのに十分である。 本稿では,この結果の最大誤差と二次規則の近似への応用について論じる。
  論文  参考訳（メタデータ） (2022-01-31T08:26:06Z)
• One-Bit Compressed Sensing via One-Shot Hard Thresholding [7.594050968868919]
  1ビット圧縮センシングの問題は、いくつかのバイナリ測定からスパース信号を推定することである。 広範に使われている非制約の幅の概念から遠ざかる、斬新で簡潔な分析法を提案する。
  論文  参考訳（メタデータ） (2020-07-07T17:28:03Z)
• Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
  主成分分析(PCA)は、機械学習と統計学において広く使われている次元削減手法である。 スパース主成分分析(Sparse principal Component Analysis)と呼ばれる,スパース主成分負荷を求める様々な手法が提案されている。 本研究では,SPCA問題に対するしきい値の精度,時間,近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-23T04:25:36Z)
• Projection Robust Wasserstein Distance and Riemannian Optimization [107.93250306339694]
  プロジェクション・ソリッドスタイン(PRW)は、ワッサーシュタイン・プロジェクション(WPP)のロバストな変種であることを示す。 本稿では,PRW距離の計算への第一歩として,その理論と実データに関する実験の関連について述べる。
  論文  参考訳（メタデータ） (2020-06-12T20:40:22Z)

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

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