論文の概要: Tight and fast generalization error bound of graph embedding in metric
space
- arxiv url: http://arxiv.org/abs/2305.07971v1
- Date: Sat, 13 May 2023 17:29:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-16 18:31:31.457780
- Title: Tight and fast generalization error bound of graph embedding in metric
space
- Title（参考訳）: 距離空間におけるグラフ埋め込みの厳密かつ高速な一般化誤差境界
- Authors: Atsushi Suzuki, Atsushi Nitanda, Taiji Suzuki, Jing Wang, Feng Tian,
and Kenji Yamanishi
- Abstract要約: 非ユークリッド計量空間へのグラフ埋め込みは、既存の有界よりもはるかに少ない訓練データを持つユークリッド空間におけるグラフ埋め込みよりも優れていることを示す。
我々の新しい上限は、既存の上限よりもかなり強く速く、最大で$R$と$O(frac1S)$に指数関数できる。
- 参考スコア（独自算出の注目度）: 54.279425319381374
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent studies have experimentally shown that we can achieve in non-Euclidean
metric space effective and efficient graph embedding, which aims to obtain the
vertices' representations reflecting the graph's structure in the metric space.
Specifically, graph embedding in hyperbolic space has experimentally succeeded
in embedding graphs with hierarchical-tree structure, e.g., data in natural
languages, social networks, and knowledge bases. However, recent theoretical
analyses have shown a much higher upper bound on non-Euclidean graph
embedding's generalization error than Euclidean one's, where a high
generalization error indicates that the incompleteness and noise in the data
can significantly damage learning performance. It implies that the existing
bound cannot guarantee the success of graph embedding in non-Euclidean metric
space in a practical training data size, which can prevent non-Euclidean graph
embedding's application in real problems. This paper provides a novel upper
bound of graph embedding's generalization error by evaluating the local
Rademacher complexity of the model as a function set of the distances of
representation couples. Our bound clarifies that the performance of graph
embedding in non-Euclidean metric space, including hyperbolic space, is better
than the existing upper bounds suggest. Specifically, our new upper bound is
polynomial in the metric space's geometric radius $R$ and can be
$O(\frac{1}{S})$ at the fastest, where $S$ is the training data size. Our bound
is significantly tighter and faster than the existing one, which can be
exponential to $R$ and $O(\frac{1}{\sqrt{S}})$ at the fastest. Specific
calculations on example cases show that graph embedding in non-Euclidean metric
space can outperform that in Euclidean space with much smaller training data
than the existing bound has suggested.
- Abstract（参考訳）: 近年の研究では、計量空間におけるグラフの構造を反映した頂点表現を得ることを目的として、非ユークリッド計量空間において有効かつ効率的なグラフ埋め込みが達成できることが実験的に示されている。
具体的には、双曲空間へのグラフ埋め込みは、例えば自然言語、ソーシャルネットワーク、知識ベースなどの階層構造を持つグラフの埋め込みに実験的に成功している。
しかし、近年の理論解析により、非ユークリッドグラフ埋め込みの一般化誤差はユークリッドグラフよりもかなり高い値を示しており、高い一般化誤差はデータの不完全性とノイズが学習性能に重大な影響を与えることを示している。
これは、既存の境界が非ユークリッド距離空間におけるグラフ埋め込みの成功を実際の訓練データサイズで保証できないことを意味しており、非ユークリッドグラフ埋め込みの実際の問題への応用を防ぐことができる。
本稿では、表現対の距離の関数集合としてモデルの局所ラデマッハ複雑性を評価することにより、グラフ埋め込みの一般化誤差の新たな上限を与える。
我々の境界は、双曲空間を含む非ユークリッド距離空間におけるグラフ埋め込みのパフォーマンスが、既存の上界よりも優れていることを明確化する。
具体的には、我々の新しい上界は距離空間の幾何半径$R$の多項式であり、最大で$O(\frac{1}{S})$で、$S$はトレーニングデータサイズである。
我々のバウンダリは、既存のバウンダリよりもかなり強く、高速で$R$と$O(\frac{1}{\sqrt{S}})$に指数関数化できる。
例における特定の計算により、非ユークリッド計量空間へのグラフ埋め込みは、既存の有界よりもはるかに少ない訓練データを持つユークリッド空間におけるグラフ埋め込みよりも優れていることが示される。
関連論文リスト
- Shedding Light on Problems with Hyperbolic Graph Learning [2.3743504594834635]
グラフ機械学習文学における近年の論文は、双曲表現学習に多くのアプローチを導入している。
現在、双曲グラフ表現学習の分野を注意深く見ていく。
多くの論文では,アルゴリズム構築時にベースラインの厳密な提示に失敗し,ミスリード指標を用いてグラフデータセットの幾何を定量化している。
論文 参考訳（メタデータ） (2024-11-11T03:12:41Z) - Weighted Embeddings for Low-Dimensional Graph Representation [0.13499500088995461]
グラフを重み付き空間に埋め込むことを提案し、これは双曲幾何学と密接に関連しているが数学的には単純である。
重み付き埋め込みは、より少ない次元を使いながら、異質グラフに対する最先端のユークリッド埋め込みを著しく上回ることを示す。
論文 参考訳（メタデータ） (2024-10-08T13:41:03Z) - Normed Spaces for Graph Embedding [8.949780057954404]
ノルム空間は、低次元の歪みに驚くほど低い理論的境界を持つ有限距離空間を埋め込むことができることを示す。
我々の研究は、幾何グラフ表現学習のためのノルム空間の可能性を強調し、新しい研究課題を提起し、有限距離空間埋め込みの分野における実験数学に有用なツールを提供する。
論文 参考訳（メタデータ） (2023-12-03T20:21:08Z) - Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
グラフ埋め込みの信頼性は、連続空間の幾何がグラフ構造とどの程度一致しているかに依存する。
我々は、この問題を解決することができる、ソフト多様体と呼ばれる新しい多様体のクラスを導入する。
グラフ埋め込みにソフト多様体を用いることで、複雑なデータセット上のデータ解析における任意のタスクを追求するための連続空間を提供できる。
論文 参考訳（メタデータ） (2023-11-29T12:48:33Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳（メタデータ） (2023-06-14T09:21:15Z) - Geometry Contrastive Learning on Heterogeneous Graphs [50.58523799455101]
本稿では,幾何学コントラスト学習(Geometry Contrastive Learning, GCL)と呼ばれる,新しい自己指導型学習手法を提案する。
GCLはユークリッドと双曲的な視点からヘテロジニアスグラフを同時に見ることができ、リッチな意味論と複雑な構造をモデル化する能力の強い融合を目指している。
4つのベンチマークデータセットの大規模な実験は、提案手法が強いベースラインよりも優れていることを示している。
論文 参考訳（メタデータ） (2022-06-25T03:54:53Z) - Provably Accurate and Scalable Linear Classifiers in Hyperbolic Spaces [39.71927912296049]
スケーラブルで単純な双曲型線形分類器を学習するための統一的なフレームワークを提案する。
我々のアプローチの要点は、ポアンカーの球体モデルに焦点を合わせ、接空間形式を用いて分類問題を定式化することである。
Poincarの2階と戦略的パーセプトロンの優れた性能は、提案フレームワークが双曲空間における一般的な機械学習問題にまで拡張可能であることを示している。
論文 参考訳（メタデータ） (2022-03-07T21:36:21Z) - Geometric Graph Representation Learning via Maximizing Rate Reduction [73.6044873825311]
学習ノード表現は、コミュニティ検出やノード分類などのグラフ解析において、さまざまな下流タスクの恩恵を受ける。
教師なしの方法でノード表現を学習するための幾何学グラフ表現学習(G2R)を提案する。
G2R は異なるグループ内のノードを異なる部分空間にマッピングし、各部分空間はコンパクトで異なる部分空間が分散される。
論文 参考訳（メタデータ） (2022-02-13T07:46:24Z) - ACE-HGNN: Adaptive Curvature Exploration Hyperbolic Graph Neural Network [72.16255675586089]
本稿では、入力グラフと下流タスクに基づいて最適な曲率を適応的に学習する適応曲率探索ハイパーボリックグラフニューラルネットワークACE-HGNNを提案する。
複数の実世界のグラフデータセットの実験は、競争性能と優れた一般化能力を備えたモデル品質において、顕著で一貫したパフォーマンス改善を示す。
論文 参考訳（メタデータ） (2021-10-15T07:18:57Z) - Highly Scalable and Provably Accurate Classification in Poincare Balls [40.82908295137667]
我々は、スケーラブルで単純な双曲型線形分類器を証明可能な性能保証で学習するための統一的なフレームワークを構築した。
提案手法は,新しい双曲型および二階型パーセプトロンアルゴリズムと,双曲型サポートベクトルマシン分類器の効率的かつ高精度な凸最適化設定を含む。
数百万の点からなる合成データセットと、シングルセルRNA-seq式測定、CIFAR10、Fashion-MNIST、mini-ImageNetのような複雑な実世界のデータセットの性能評価を行う。
論文 参考訳（メタデータ） (2021-09-08T16:59:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。