論文の概要: Hamilton-Jacobi equations on graphs with applications to semi-supervised
learning and data depth
- arxiv url: http://arxiv.org/abs/2202.08789v1
- Date: Thu, 17 Feb 2022 17:50:55 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-18 16:34:52.624462
- Title: Hamilton-Jacobi equations on graphs with applications to semi-supervised
learning and data depth
- Title（参考訳）: グラフ上のハミルトン・ヤコビ方程式と半教師付き学習とデータ深度への応用
- Authors: Jeff Calder, Mahmood Ettehad
- Abstract要約: グラフ上のハミルトン・ヤコビ方程式の族を研究し、これを$p$-ekonal equation(英語版)と呼ぶ。
p=1$ の $p$-ekonal 方程式はグラフ上の証明可能な頑健な距離型関数であることを示す。
我々は,データ深度と半教師付き学習に対する$p$-ekonal方程式の適用を考察し,連続極限を用いて両者の整合性を証明した。
- 参考スコア（独自算出の注目度）: 1.52292571922932
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Shortest path graph distances are widely used in data science and machine
learning, since they can approximate the underlying geodesic distance on the
data manifold. However, the shortest path distance is highly sensitive to the
addition of corrupted edges in the graph, either through noise or an
adversarial perturbation. In this paper we study a family of Hamilton-Jacobi
equations on graphs that we call the $p$-eikonal equation. We show that the
$p$-eikonal equation with $p=1$ is a provably robust distance-type function on
a graph, and the $p\to \infty$ limit recovers shortest path distances. While
the $p$-eikonal equation does not correspond to a shortest-path graph distance,
we nonetheless show that the continuum limit of the $p$-eikonal equation on a
random geometric graph recovers a geodesic density weighted distance in the
continuum. We consider applications of the $p$-eikonal equation to data depth
and semi-supervised learning, and use the continuum limit to prove asymptotic
consistency results for both applications. Finally, we show the results of
experiments with data depth and semi-supervised learning on real image
datasets, including MNIST, FashionMNIST and CIFAR-10, which show that the
$p$-eikonal equation offers significantly better results compared to shortest
path distances.
- Abstract（参考訳）: 最も短いパスグラフ距離は、データ多様体上の測地線距離を近似できるため、データサイエンスや機械学習で広く使われている。
しかし、最短経路距離は、ノイズまたは逆方向の摂動によって、グラフ内の破損したエッジの追加に非常に敏感である。
本稿では, グラフ上のハミルトン・ヤコビ方程式の族を, $p$-eikonal equation と呼ぶ。
p=1$の$p$-ekonal方程式はグラフ上の証明可能な堅牢な距離型関数であり、$p\to \infty$制限は最短経路距離を回復する。
p$-eikonal方程式は最短経路グラフ距離とは一致しないが、ランダムな幾何学グラフ上の$p$-eikonal方程式の連続限界は連続体における測地密度重み付き距離を回復することを示している。
我々は,データ深度と半教師付き学習に対する$p$-ekonal方程式の適用を検討し,連続極限を用いて両アプリケーションに漸近的整合性を示す。
最後に,MNIST,FashionMNIST,CIFAR-10などの実画像データセットに対して,データ深度と半教師付き学習による実験結果を示す。
関連論文リスト
- Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の等方的ガウスデータの下で勾配降下学習の問題を考察する。
SGDアルゴリズムで最適化された2層ニューラルネットワークは、サンプル付き任意のリンク関数の$f_*$を学習し、実行時の複雑さは$n asymp T asymp C(q) cdot dであることを示す。
論文 参考訳（メタデータ） (2024-06-03T17:56:58Z) - Continuum limit of $p$-biharmonic equations on graphs [3.79830302036482]
ランダムな幾何グラフが考慮され、データポイントの数が無限大になるとき、解の挙動を調査する。
連続極限は、均一なノイマン境界条件を持つ適切な重み付き$p$-ビハーモニック方程式であることを示す。
論文 参考訳（メタデータ） (2024-04-30T16:29:44Z) - All You Need is Resistance: On the Equivalence of Effective Resistance and Certain Optimal Transport Problems on Graphs [48.84819106277247]
我々は、グラフ上の効果的な抵抗と最適輸送は、最大$p$を選択するまで、一つと同じものとして理解されるべきであると主張する。
最適停止時間とグラフ上のランダムウォーク,グラフソボレフ空間,ベナモ・ブレニエ型式に対する2ドルベックマン距離の明示的な接続を示す。
本稿では、ワッサーシュタイン距離が計算ボトルネックを引き起こす可能性のあるこれらの指標のさらなる利用法を提案する。
論文 参考訳（メタデータ） (2024-04-23T17:50:52Z) - Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
グラフ埋め込みの信頼性は、連続空間の幾何がグラフ構造とどの程度一致しているかに依存する。
我々は、この問題を解決することができる、ソフト多様体と呼ばれる新しい多様体のクラスを導入する。
グラフ埋め込みにソフト多様体を用いることで、複雑なデータセット上のデータ解析における任意のタスクを追求するための連続空間を提供できる。
論文 参考訳（メタデータ） (2023-11-29T12:48:33Z) - Graph Mover's Distance: An Efficiently Computable Distance Measure for
Geometric Graphs [0.0]
幾何グラフ距離(GGD)は、2つの幾何学グラフ間の類似性の有意義な尺度として最近研究されている。
本稿では,地球移動機の距離の例として定式化されたグラフ・モーバー距離(GMD)を提案する。
論文 参考訳（メタデータ） (2023-06-03T15:06:12Z) - Tight and fast generalization error bound of graph embedding in metric
space [54.279425319381374]
非ユークリッド計量空間へのグラフ埋め込みは、既存の有界よりもはるかに少ない訓練データを持つユークリッド空間におけるグラフ埋め込みよりも優れていることを示す。
我々の新しい上限は、既存の上限よりもかなり強く速く、最大で$R$と$O(frac1S)$に指数関数できる。
論文 参考訳（メタデータ） (2023-05-13T17:29:18Z) - Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect
Alignment [51.74913666829224]
強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。
本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。
実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
論文 参考訳（メタデータ） (2022-08-18T09:19:01Z) - Condensing Graphs via One-Step Gradient Matching [50.07587238142548]
ネットワーク重みを訓練せずに1ステップのみの勾配マッチングを行う1ステップ勾配マッチング方式を提案する。
我々の理論的分析は、この戦略が実際のグラフの分類損失を減少させる合成グラフを生成することができることを示している。
特に、元のパフォーマンスの最大98%を近似しながら、データセットサイズを90%削減することが可能です。
論文 参考訳（メタデータ） (2022-06-15T18:20:01Z) - Multiscale Graph Comparison via the Embedded Laplacian Distance [6.09170287691728]
非常に異なるサイズのグラフを比較するために,埋め込みラプラシアン距離 (ELD) を提案する。
我々のアプローチはまず、図形構造を尊重する共通の低次元ラプラシア埋め込み空間にグラフを投影する。
距離は自然スライスされたワッサーシュタインアプローチによって効率的に計算できる。
論文 参考訳（メタデータ） (2022-01-28T12:13:08Z) - Continuum Limit of Lipschitz Learning on Graphs [0.0]
我々は$Gamma$-convergenceを使ってLipschitz学習の連続的限界を証明する。
最小化の収束を意味する関数のコンパクト性を示す。
論文 参考訳（メタデータ） (2020-12-07T15:10:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。