論文の概要: Scalable Optimal Transport in High Dimensions for Graph Distances,
Embedding Alignment, and More
- arxiv url: http://arxiv.org/abs/2107.06876v1
- Date: Wed, 14 Jul 2021 17:40:08 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-15 15:11:07.894298
- Title: Scalable Optimal Transport in High Dimensions for Graph Distances,
Embedding Alignment, and More
- Title（参考訳）: グラフ距離、埋め込みアライメントなどのための高次元のスケーラブルな最適輸送
- Authors: Johannes Klicpera, Marten Lienen, Stephan G\"unnemann
- Abstract要約: 最適輸送のためのコスト行列の2つの効率的な対数線形時間近似を提案する。
これらの近似は、複雑な高次元空間に対してもよく機能するエントロピー規則化OTに対する一般的な対数線形時間アルゴリズムを可能にする。
グラフ距離回帰のために,グラフニューラルネットワーク(GNN)と拡張シンクホーンを組み合わせたグラフトランスポートネットワーク(GTN)を提案する。
- 参考スコア（独自算出の注目度）: 7.484063729015126
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The current best practice for computing optimal transport (OT) is via entropy
regularization and Sinkhorn iterations. This algorithm runs in quadratic time
as it requires the full pairwise cost matrix, which is prohibitively expensive
for large sets of objects. In this work we propose two effective log-linear
time approximations of the cost matrix: First, a sparse approximation based on
locality-sensitive hashing (LSH) and, second, a Nystr\"om approximation with
LSH-based sparse corrections, which we call locally corrected Nystr\"om (LCN).
These approximations enable general log-linear time algorithms for
entropy-regularized OT that perform well even for the complex, high-dimensional
spaces common in deep learning. We analyse these approximations theoretically
and evaluate them experimentally both directly and end-to-end as a component
for real-world applications. Using our approximations for unsupervised word
embedding alignment enables us to speed up a state-of-the-art method by a
factor of 3 while also improving the accuracy by 3.1 percentage points without
any additional model changes. For graph distance regression we propose the
graph transport network (GTN), which combines graph neural networks (GNNs) with
enhanced Sinkhorn. GTN outcompetes previous models by 48% and still scales
log-linearly in the number of nodes.
- Abstract（参考訳）: 現在の最適輸送(OT)計算のベストプラクティスはエントロピー正規化とシンクホーン反復によるものである。
このアルゴリズムは、一対のコスト行列を必要とするため、2次時間で実行される。
本稿では,コスト行列の2つの有効対数線形時間近似を提案する。1つは局所性感受性ハッシュ(lsh)に基づくスパース近似,もう1つは,局所補正されたnystr\"om(lcn)と呼ばれるlshに基づくスパース補正を用いたnystr\"om近似である。
これらの近似は、深層学習で一般的な複雑な高次元空間でもうまく機能するエントロピー正規化otに対する一般的な対数線形時間アルゴリズムを可能にする。
これらの近似を理論的に解析し、実世界のアプリケーションのためのコンポーネントとして直接およびエンドツーエンドの両方で実験的に評価する。
教師なし単語埋め込みアライメントの近似を用いて3倍の精度で最先端の手法を高速化すると同時に,追加のモデル変更なしに3.1ポイントの精度を向上する。
グラフ距離回帰のために,グラフニューラルネットワーク(GNN)と拡張シンクホーンを組み合わせたグラフトランスポートネットワーク(GTN)を提案する。
GTNは以前のモデルを48%上回り、それでもノード数でログリニアにスケールする。
関連論文リスト
- Sparse Decomposition of Graph Neural Networks [20.768412002413843]
本稿では,集約中に含まれるノード数を削減する手法を提案する。
線形変換された特徴の重み付け和を用いてノード表現の近似を学習し、スパース分解によりこれを実現できる。
提案手法は推論高速化のために設計された他のベースラインよりも優れていることを示す。
論文 参考訳（メタデータ） (2024-10-25T17:52:16Z) - CiliaGraph: Enabling Expression-enhanced Hyper-Dimensional Computation in Ultra-Lightweight and One-Shot Graph Classification on Edge [1.8726646412385333]
CiliaGraphはグラフ分類のための拡張表現型だが超軽量なHDCモデルである。
CiliaGraphはメモリ使用量を削減し、トレーニング速度を平均292倍に高速化する。
論文 参考訳（メタデータ） (2024-05-29T12:22:59Z) - Exact Gauss-Newton Optimization for Training Deep Neural Networks [0.0]
一般化されたガウスニュートン(GN)ヘッセン近似と低ランク線形代数を組み合わせた2階最適化アルゴリズムEGNを提案する。
線形探索,適応正則化,運動量などの改良をEGNにシームレスに追加して,アルゴリズムをさらに高速化する方法について述べる。
論文 参考訳（メタデータ） (2024-05-23T10:21:05Z) - Efficient Heterogeneous Graph Learning via Random Projection [58.4138636866903]
不均一グラフニューラルネットワーク(HGNN)は、異種グラフを深層学習するための強力なツールである。
最近のプリ計算ベースのHGNNは、一時間メッセージパッシングを使用して不均一グラフを正規形テンソルに変換する。
我々はRandom Projection Heterogeneous Graph Neural Network (RpHGNN) というハイブリッド計算前HGNNを提案する。
論文 参考訳（メタデータ） (2023-10-23T01:25:44Z) - Neural Gradient Learning and Optimization for Oriented Point Normal
Estimation [53.611206368815125]
本研究では,3次元点雲から勾配ベクトルを一貫した向きで学習し,正規推定を行うためのディープラーニング手法を提案する。
局所平面幾何に基づいて角距離場を学習し、粗勾配ベクトルを洗練する。
本手法は,局所特徴記述の精度と能力の一般化を図りながら,グローバル勾配近似を効率的に行う。
論文 参考訳（メタデータ） (2023-09-17T08:35:11Z) - Geometry-Informed Neural Operator for Large-Scale 3D PDEs [76.06115572844882]
大規模偏微分方程式の解演算子を学習するために,幾何インフォームド・ニューラル演算子(GINO)を提案する。
我々はGINOを訓練し、わずか500点のデータポイントで車両表面の圧力を予測することに成功した。
論文 参考訳（メタデータ） (2023-09-01T16:59:21Z) - Optimality of Message-Passing Architectures for Sparse Graphs [13.96547777184641]
スパース設定における特徴デコレーショングラフ上のノード分類問題、すなわちノードの期待次数がノード数で$O(1)$である場合について検討する。
局所ベイズ最適性(英語版)と呼ばれるノード分類タスクに対するベイズ最適性(英語版)の概念を導入する。
最適なメッセージパッシングアーキテクチャは,低グラフ信号のレギュレーションにおける標準と高グラフ信号のレギュレーションにおける典型とを補間することを示す。
論文 参考訳（メタデータ） (2023-05-17T17:31:20Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via
GDPA Linearization [59.87663954467815]
アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。
本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。
実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
論文 参考訳（メタデータ） (2021-09-10T07:01:15Z) - Improving predictions of Bayesian neural nets via local linearization [79.21517734364093]
ガウス・ニュートン近似は基礎となるベイズニューラルネットワーク(BNN)の局所線形化として理解されるべきである。
この線形化モデルを後部推論に使用するので、元のモデルではなく、この修正モデルを使用することも予測すべきである。
この修正された予測を"GLM predictive"と呼び、Laplace近似の共通不適合問題を効果的に解決することを示す。
論文 参考訳（メタデータ） (2020-08-19T12:35:55Z) - A Study of Performance of Optimal Transport [16.847501106437534]
本稿では,ネットワークの単純化と拡張パスに基づくアルゴリズムが,数値行列スケーリング法より一貫して優れていることを示す。
古典的なKuhn-Munkresアルゴリズムを改良した新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-05-03T20:37:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。