論文の概要: Uniform Convergence Rates for Lipschitz Learning on Graphs

• arxiv url: http://arxiv.org/abs/2111.12370v1
• Date: Wed, 24 Nov 2021 09:44:14 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-25 16:08:45.891753
• Title: Uniform Convergence Rates for Lipschitz Learning on Graphs
• Title（参考訳）: グラフ上のリプシッツ学習のための一様収束率
• Authors: Leon Bungert, Jeff Calder, Tim Roith
• Abstract要約: リプシッツ学習(英: Lipschitz learning)は、グラフに基づく半教師付き学習法である。 グラフ無限大ラプラス方程式の解に対する一様収束率を証明する。
• 参考スコア（独自算出の注目度）: 1.9014535120129339
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Lipschitz learning is a graph-based semi-supervised learning method where one extends labels from a labeled to an unlabeled data set by solving the infinity Laplace equation on a weighted graph. In this work we prove uniform convergence rates for solutions of the graph infinity Laplace equation as the number of vertices grows to infinity. Their continuum limits are absolutely minimizing Lipschitz extensions with respect to the geodesic metric of the domain where the graph vertices are sampled from. We work under very general assumptions on the graph weights, the set of labeled vertices, and the continuum domain. Our main contribution is that we obtain quantitative convergence rates even for very sparsely connected graphs, as they typically appear in applications like semi-supervised learning. In particular, our framework allows for graph bandwidths down to the connectivity radius. For proving this we first show a quantitative convergence statement for graph distance functions to geodesic distance functions in the continuum. Using the "comparison with distance functions" principle, we can pass these convergence statements to infinity harmonic functions and absolutely minimizing Lipschitz extensions.
• Abstract（参考訳）: リプシッツ学習(英: lipschitz learning)は、重み付きグラフ上の無限ラプラス方程式を解いてラベル付きデータからラベルなしデータにラベルを拡張したグラフベースの半教師付き学習手法である。 本研究では、グラフ無限大ラプラス方程式の解に対する一様収束率を、頂点数が無限大に成長するにつれて証明する。 彼らの連続極限は、グラフ頂点がサンプリングされる領域の測地線計量に関して、絶対的にリプシッツ拡大を最小化している。 グラフ重み、ラベル付き頂点の集合、連続体領域に関する非常に一般的な仮定の下で作業する。 私たちの主な貢献は、半教師付き学習のようなアプリケーションでよく見られるように、非常に疎結合なグラフでも定量的収束率を得ることです。 特に、我々のフレームワークは、接続半径までグラフ帯域幅を可能にする。 これを証明するために、まず、連続体の測地距離関数に対するグラフ距離関数の定量的収束文を示す。 距離関数との比較」の原理を用いて、これらの収束ステートメントを無限大調和函数に渡し、リプシッツ拡大を絶対最小化することができる。

関連論文リスト

• Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
  グラフ埋め込みの信頼性は、連続空間の幾何がグラフ構造とどの程度一致しているかに依存する。 我々は、この問題を解決することができる、ソフト多様体と呼ばれる新しい多様体のクラスを導入する。 グラフ埋め込みにソフト多様体を用いることで、複雑なデータセット上のデータ解析における任意のタスクを追求するための連続空間を提供できる。
  論文  参考訳（メタデータ） (2023-11-29T12:48:33Z)
• Generalized Graphon Process: Convergence of Graph Frequencies in Stretched Cut Distance [30.279435887366578]
  スパースグラフ列は、従来のカット距離の定義の下で自明なグラフオンに収束する。 我々は、スパースグラフ列の収束を記述するために、一般化グラフと拡張カット距離の概念を利用する。 その結果,スパースグラフ間の移動学習の可能性が示唆された。
  論文  参考訳（メタデータ） (2023-09-11T06:34:46Z)
• Path convergence of Markov chains on large graphs [3.693375843298262]
  グラフのサイズが無限大になるにつれて、プロセスのランダムな軌跡は測度値グラフの空間上の決定論的曲線に収束することを示す。 このアプローチの新たな特徴は、ある制限状態におけるメトロポリス連鎖に対して正確な指数収束速度を提供することである。
  論文  参考訳（メタデータ） (2023-08-18T00:13:59Z)
• Limits, approximation and size transferability for GNNs on sparse graphs via graphops [44.02161831977037]
  我々は,GNNを構成する集約演算など,グラフから導出される演算子の極限を取るという観点から考える。 我々の結果は、密でスパースなグラフ、およびグラフ極限の様々な概念に当てはまる。
  論文  参考訳（メタデータ） (2023-06-07T15:04:58Z)
• Tight and fast generalization error bound of graph embedding in metric space [54.279425319381374]
  非ユークリッド計量空間へのグラフ埋め込みは、既存の有界よりもはるかに少ない訓練データを持つユークリッド空間におけるグラフ埋め込みよりも優れていることを示す。 我々の新しい上限は、既存の上限よりもかなり強く速く、最大で$R$と$O(frac1S)$に指数関数できる。
  論文  参考訳（メタデータ） (2023-05-13T17:29:18Z)
• Graphon Pooling for Reducing Dimensionality of Signals and Convolutional Operators on Graphs [131.53471236405628]
  グラフ空間における[0, 1]2の分割上のグラフとグラフ信号の誘導的グラフ表現を利用する3つの方法を提案する。 これらの低次元表現がグラフとグラフ信号の収束列を構成することを証明している。 我々は,層間次元減少比が大きい場合,グラノンプーリングは文献で提案した他の手法よりも有意に優れていることを観察した。
  論文  参考訳（メタデータ） (2022-12-15T22:11:34Z)
• Gradient flows on graphons: existence, convergence, continuity equations [27.562307342062354]
  確率測度上のワッサーシュタイン勾配流は、様々な最適化問題に多くの応用を見出した。 辺重みの適当な関数のユークリッド勾配流は、グラノン空間上の曲線によって与えられる新しい連続極限に収束することを示す。
  論文  参考訳（メタデータ） (2021-11-18T00:36:28Z)
• Continuum Limit of Lipschitz Learning on Graphs [0.0]
  我々は$Gamma$-convergenceを使ってLipschitz学習の連続的限界を証明する。 最小化の収束を意味する関数のコンパクト性を示す。
  論文  参考訳（メタデータ） (2020-12-07T15:10:35Z)
• Hamiltonian systems, Toda lattices, Solitons, Lax Pairs on weighted Z-graded graphs [62.997667081978825]
  グラフ上の解に対して一次元の解を持ち上げることができる条件を特定する。 位相的に興味深いグラフの簡単な例であっても、対応する非自明なラックス対と関連するユニタリ変換は、Z階数グラフ上のラックス対に持ち上げないことを示す。
  論文  参考訳（メタデータ） (2020-08-11T17:58:13Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。 その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-19T13:09:44Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。 提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
  論文  参考訳（メタデータ） (2020-03-12T22:31:59Z)

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

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