論文の概要: Accelerated Evaluation of Ollivier-Ricci Curvature Lower Bounds: Bridging Theory and Computation
- arxiv url: http://arxiv.org/abs/2405.13302v1
- Date: Wed, 22 May 2024 02:44:46 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-25 01:34:09.722396
- Title: Accelerated Evaluation of Ollivier-Ricci Curvature Lower Bounds: Bridging Theory and Computation
- Title(参考訳): Ollivier-Ricci曲線下界の加速評価:ブリッジ理論と計算
- Authors: Wonwoo Kang, Heehyun Park,
- Abstract要約: 曲線は強力な記述不変量として機能し、その有効性は理論上も実際上もグラフ理論内で検証される。
我々は、Ollivierによって提唱された一般化リッチ曲率の定義を使用し、LinとYauは後にOllivier-Ricci曲率(ORC)として知られるグラフ理論に適応した。
ORCはワッサーシュタイン距離を用いて曲率を測り、幾何学的概念と確率論と最適輸送を統合する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Curvature serves as a potent and descriptive invariant, with its efficacy validated both theoretically and practically within graph theory. We employ a definition of generalized Ricci curvature proposed by Ollivier, which Lin and Yau later adapted to graph theory, known as Ollivier-Ricci curvature (ORC). ORC measures curvature using the Wasserstein distance, thereby integrating geometric concepts with probability theory and optimal transport. Jost and Liu previously discussed the lower bound of ORC by showing the upper bound of the Wasserstein distance. We extend the applicability of these bounds to discrete spaces with metrics on integers, specifically hypergraphs. Compared to prior work on ORC in hypergraphs by Coupette, Dalleiger, and Rieck, which faced computational challenges, our method introduces a simplified approach with linear computational complexity, making it particularly suitable for analyzing large-scale networks. Through extensive simulations and application to synthetic and real-world datasets, we demonstrate the significant improvements our method offers in evaluating ORC.
- Abstract(参考訳): 曲線は強力な記述不変量として機能し、その有効性は理論上も実際上もグラフ理論内で検証される。
我々は、Ollivierによって提唱された一般化リッチ曲率の定義を用い、LinとYauは後にOllivier-Ricci曲率(ORC)として知られるグラフ理論に適応した。
ORCはワッサーシュタイン距離を用いて曲率を測り、幾何学的概念と確率論と最適輸送を統合する。
ジョストとリューは以前、ワッサーシュタイン距離の上界を示すことによってORCの下界について議論した。
我々はこれらの境界の適用性を、整数、特にハイパーグラフ上のメトリクスを持つ離散空間に拡張する。
計算問題に直面したCoupette, Dalleiger, RieckによるハイパーグラフにおけるORCに関する以前の研究と比較すると, 線形計算の複雑化を伴う単純化されたアプローチを導入し, 大規模ネットワークの解析に特に適している。
人工および実世界のデータセットへの広範なシミュレーションと応用を通じて、ORCの評価において我々の方法がもたらす重要な改善を実証する。
関連論文リスト
- Kernel Approximation of Fisher-Rao Gradient Flows [52.154685604660465]
本稿では,フィッシャー・ラオ型およびワッサーシュタイン型勾配流の勾配構造,流れ方程式,および核近似に関する厳密な研究を行う。
具体的には、フィッシャー・ラオ幾何学とその様々なカーネルに基づく近似に注目し、原理的な理論的枠組みを開発する。
論文 参考訳(メタデータ) (2024-10-27T22:52:08Z) - Finite-dimensional approximations of push-forwards on locally analytic functionals [5.787117733071417]
我々のアプローチは、解析写像そのものを直接扱うのではなく、局所解析関数の空間上のプッシュフォワードを考えることである。
有限離散データからプッシュフォワードの適切な有限次元近似を可能にする手法を確立する。
論文 参考訳(メタデータ) (2024-04-16T17:53:59Z) - Revealing Decurve Flows for Generalized Graph Propagation [108.80758541147418]
本研究は,有向グラフと重み付きグラフを用いて,m文を一般化した伝播を定義することによって,従来のメッセージパッシング(中心からグラフ学習)の限界に対処する。
この分野ではじめて、データセットにおける学習された伝播パターンの予備的な探索を含む。
論文 参考訳(メタデータ) (2024-02-13T14:13:17Z) - Curvature-Independent Last-Iterate Convergence for Games on Riemannian
Manifolds [77.4346324549323]
本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。
我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
論文 参考訳(メタデータ) (2023-06-29T01:20:44Z) - A Framework for Analyzing Cross-correlators using Price's Theorem and
Piecewise-Linear Decomposition [5.094549132183797]
本稿では,片方向線形関数の混合を用いて構築したクロスコレレータを解析できる汎用的な数学的枠組みを提案する。
最も有望なクロスコレレータのいくつかは、Huberの損失関数、マージンプロパゲーション(MP)関数、log-sum-exp(LSE)関数に基づいている。
論文 参考訳(メタデータ) (2023-04-18T19:03:27Z) - Ollivier-Ricci Curvature for Hypergraphs: A Unified Framework [15.447966950703952]
我々はOllivier-Ricci曲率をハイパーグラフに一般化するフレキシブルなフレームワークORCHIDを開発した。
ORCHID曲線は拡張性があり,様々なハイパーグラフ処理を行うのに有用であることを示す。
論文 参考訳(メタデータ) (2022-10-21T15:40:49Z) - Optimizing Information-theoretical Generalization Bounds via Anisotropic
Noise in SGLD [73.55632827932101]
SGLDにおけるノイズ構造を操作することにより,情報理論の一般化を最適化する。
低経験的リスクを保証するために制約を課すことで、最適なノイズ共分散が期待される勾配共分散の平方根であることを証明する。
論文 参考訳(メタデータ) (2021-10-26T15:02:27Z) - Projected Statistical Methods for Distributional Data on the Real Line
with the Wasserstein Metric [0.0]
本研究では,実線上の確率分布のデータセットに関する統計解析を行うための,新規な予測手法を提案する。
特に主成分分析(PCA)と回帰に重点を置いています。
モデルのいくつかの理論的性質が研究され、一貫性が証明される。
論文 参考訳(メタデータ) (2021-01-22T10:24:49Z) - Efficient Semi-Implicit Variational Inference [65.07058307271329]
効率的でスケーラブルな半単純外挿 (SIVI) を提案する。
本手法はSIVIの証拠を低勾配値の厳密な推測にマッピングする。
論文 参考訳(メタデータ) (2021-01-15T11:39:09Z) - SLEIPNIR: Deterministic and Provably Accurate Feature Expansion for
Gaussian Process Regression with Derivatives [86.01677297601624]
本稿では,2次フーリエ特徴に基づく導関数によるGP回帰のスケーリング手法を提案する。
我々は、近似されたカーネルと近似された後部の両方に適用される決定論的、非漸近的、指数関数的に高速な崩壊誤差境界を証明した。
論文 参考訳(メタデータ) (2020-03-05T14:33:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。