論文の概要: 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の評価において我々の方法がもたらす重要な改善を実証する。
関連論文リスト
- 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) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳(メタデータ) (2020-12-21T17:29:58Z) - SLEIPNIR: Deterministic and Provably Accurate Feature Expansion for
Gaussian Process Regression with Derivatives [86.01677297601624]
本稿では,2次フーリエ特徴に基づく導関数によるGP回帰のスケーリング手法を提案する。
我々は、近似されたカーネルと近似された後部の両方に適用される決定論的、非漸近的、指数関数的に高速な崩壊誤差境界を証明した。
論文 参考訳(メタデータ) (2020-03-05T14:33:20Z) - Learning Implicit Generative Models with Theoretical Guarantees [12.761710596142109]
我々はtextbfimplicit textbfmodeling (UnifiGem) のためのtextbfunified textbfframework を提案する。
UnifiGemは、最適輸送、数値ODE、密度比(密度差)推定、ディープニューラルネットワークのアプローチを統合する。
合成データセットと実ベンチマークデータセットの両方の実験結果は、我々の理論的な結果をサポートし、UnifiGemの有効性を実証する。
論文 参考訳(メタデータ) (2020-02-07T15:55:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。