論文の概要: All You Need is Resistance: On the Equivalence of Effective Resistance and Certain Optimal Transport Problems on Graphs
- arxiv url: http://arxiv.org/abs/2404.15261v1
- Date: Tue, 23 Apr 2024 17:50:52 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-24 12:53:16.018714
- Title: All You Need is Resistance: On the Equivalence of Effective Resistance and Certain Optimal Transport Problems on Graphs
- Title（参考訳）: 抵抗は必要なこと--グラフ上での有効抵抗と最適輸送問題の等価性について
- Authors: Sawyer Robertson, Zhengchao Wan, Alexander Cloninger,
- Abstract要約: 我々は、グラフ上の効果的な抵抗と最適輸送は、最大$p$を選択するまで、一つと同じものとして理解されるべきであると主張する。
最適停止時間とグラフ上のランダムウォーク,グラフソボレフ空間,ベナモ・ブレニエ型式に対する2ドルベックマン距離の明示的な接続を示す。
本稿では、ワッサーシュタイン距離が計算ボトルネックを引き起こす可能性のあるこれらの指標のさらなる利用法を提案する。
- 参考スコア（独自算出の注目度）: 48.84819106277247
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The fields of effective resistance and optimal transport on graphs are filled with rich connections to combinatorics, geometry, machine learning, and beyond. In this article we put forth a bold claim: that the two fields should be understood as one and the same, up to a choice of $p$. We make this claim precise by introducing the parameterized family of $p$-Beckmann distances for probability measures on graphs and relate them sharply to certain Wasserstein distances. Then, we break open a suite of results including explicit connections to optimal stopping times and random walks on graphs, graph Sobolev spaces, and a Benamou-Brenier type formula for $2$-Beckmann distance. We further explore empirical implications in the world of unsupervised learning for graph data and propose further study of the usage of these metrics where Wasserstein distance may produce computational bottlenecks.
- Abstract（参考訳）: グラフ上の効果的な抵抗と最適な輸送の分野は、組合せ論、幾何学、機械学習などへの豊富な接続で満たされている。
この記事では、大胆な主張を述べた: 2つの体は1つと同一であり、$p$を選択するまで理解されるべきである。
この主張は、グラフ上の確率測度に対して$p$-ベックマン距離のパラメータ化された族を導入し、それをワッサーシュタイン距離と鋭く関連付けることによって、正確にする。
次に、最適停止時間への明示的な接続、グラフ上のランダムウォーク、グラフソボレフ空間、ベナモ・ブレニエ型式を2ドルベックマン距離に分割する。
さらに、グラフデータに対する教師なし学習の世界における経験的意味を探求し、ワッサーシュタイン距離が計算ボトルネックを生み出す可能性のあるこれらの指標の利用について、さらなる研究を提案する。
関連論文リスト
- Inverse Entropic Optimal Transport Solves Semi-supervised Learning via Data Likelihood Maximization [65.8915778873691]
条件分布は機械学習の中心的な問題です
ペアデータとペアデータの両方を統合する新しい学習パラダイムを提案する。
我々のアプローチはまた、興味深いことに逆エントロピー最適輸送(OT)と結びついている。
論文 参考訳（メタデータ） (2024-10-03T16:12:59Z) - Exploiting Edge Features in Graphs with Fused Network Gromov-Wasserstein
Distance [18.522233517515975]
ノードとエッジが特徴を持つグラフを比較するために,Gromov-Wasserstein距離の拡張を導入する。
入力空間または出力空間でグラフが発生する学習タスクにおいて、新しい距離の有効性を実証的に示す。
論文 参考訳（メタデータ） (2023-09-28T17:05:03Z) - Inference via robust optimal transportation: theory and methods [7.690743442192021]
最適輸送理論と関連する$p$-Wasserstein距離は統計学や機械学習に広く応用されている。
彼らの人気にもかかわらず、これらのツールに基づく推論にはいくつかの問題がある。
論文 参考訳（メタデータ） (2023-01-16T07:56:22Z) - Unveiling the Sampling Density in Non-Uniform Geometric Graphs [69.93864101024639]
グラフを幾何学グラフとみなす: ノードは基礎となる計量空間からランダムにサンプリングされ、その距離が指定された近傍半径以下であれば任意のノードが接続される。
ソーシャルネットワークでは、コミュニティは密集したサンプル領域としてモデル化でき、ハブはより大きな近傍半径を持つノードとしてモデル化できる。
我々は,未知のサンプリング密度を自己監督的に推定する手法を開発した。
論文 参考訳（メタデータ） (2022-10-15T08:01:08Z) - Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
グラフに基づく相対的制約のない最小二乗重要度フィッティング(GRULSIF)
我々はこの考え方を、グラフベースの相対的非制約最小二乗重要度フィッティング(GRULSIF)と呼ばれる具体的な非パラメトリック手法で開発する。
我々は、ノード当たりの観測回数、グラフのサイズ、およびグラフ構造がタスク間の類似性をどの程度正確にエンコードしているかといった変数が果たす役割を強調する、協調的なアプローチの収束率を導出する。
論文 参考訳（メタデータ） (2022-05-28T15:37:03Z) - Hamilton-Jacobi equations on graphs with applications to semi-supervised
learning and data depth [1.52292571922932]
グラフ上のハミルトン・ヤコビ方程式の族を研究し、これを$p$-ekonal equation(英語版)と呼ぶ。
p=1$ の $p$-ekonal 方程式はグラフ上の証明可能な頑健な距離型関数であることを示す。
我々は,データ深度と半教師付き学習に対する$p$-ekonal方程式の適用を考察し,連続極限を用いて両者の整合性を証明した。
論文 参考訳（メタデータ） (2022-02-17T17:50:55Z) - Entropic Optimal Transport in Random Graphs [8.7314407902481]
グラフ解析において、古典的なタスクはノード間の(グループの)類似性の計算によって構成される。
潜在空間におけるノード群間の距離を連続的に推定することは可能であることを示す。
論文 参考訳（メタデータ） (2022-01-11T13:52:34Z) - A Thorough View of Exact Inference in Graphs from the Degree-4
Sum-of-Squares Hierarchy [37.34153902687548]
各エッジの1つの破損した観測からノードの未知の接地型バイナリラベリングを正確に回収する問題に取り組む。
この問題に対して、和の平方階層と呼ばれるリラクゼーションの階層を適用します。
我々は、緩和問題の双対の解がジョンソングラフとクネーサーグラフのエッジウェイトを見つけることに関連していることを示した。
論文 参考訳（メタデータ） (2021-02-16T08:36:19Z) - On Projection Robust Optimal Transport: Sample Complexity and Model
Misspecification [101.0377583883137]
射影ロバスト(PR)OTは、2つの測度の間のOTコストを最大化するために、射影可能な$k$次元部分空間を選択する。
私たちの最初の貢献は、PRワッサーシュタイン距離のいくつかの基本的な統計的性質を確立することである。
次に、部分空間を最適化するのではなく平均化することにより、PRW距離の代替として積分PRワッサーシュタイン距離(IPRW)を提案する。
論文 参考訳（メタデータ） (2020-06-22T14:35:33Z) - Wasserstein-based Graph Alignment [56.84964475441094]
我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。
提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
論文 参考訳（メタデータ） (2020-03-12T22:31:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。