論文の概要: Fast Graph Neural Tangent Kernel via Kronecker Sketching
- arxiv url: http://arxiv.org/abs/2112.02446v1
- Date: Sat, 4 Dec 2021 23:23:20 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-07 17:04:28.768820
- Title: Fast Graph Neural Tangent Kernel via Kronecker Sketching
- Title(参考訳): Kronecker Sketchingによる高速グラフニューラルタンジェントカーネル
- Authors: Shunhua Jiang, Yunze Man, Zhao Song, Zheng Yu, Danyang Zhuo
- Abstract要約: 近年,グラフデータを学習するための新しい手法がGNTK (Graph Neural Tangent Kernel) である。
GNTKは、グラフデータに対するNeural Tangent Kernel(NTK)の応用である。
本稿では,カーネル行列を$o(n2N3)$実行時間で構築する最初のアルゴリズムを提供する。
- 参考スコア(独自算出の注目度): 21.262462612395016
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Many deep learning tasks have to deal with graphs (e.g., protein structures,
social networks, source code abstract syntax trees). Due to the importance of
these tasks, people turned to Graph Neural Networks (GNNs) as the de facto
method for learning on graphs. GNNs have become widely applied due to their
convincing performance. Unfortunately, one major barrier to using GNNs is that
GNNs require substantial time and resources to train. Recently, a new method
for learning on graph data is Graph Neural Tangent Kernel (GNTK) [Du, Hou,
Salakhutdinov, Poczos, Wang and Xu 19]. GNTK is an application of Neural
Tangent Kernel (NTK) [Jacot, Gabriel and Hongler 18] (a kernel method) on graph
data, and solving NTK regression is equivalent to using gradient descent to
train an infinite-wide neural network. The key benefit of using GNTK is that,
similar to any kernel method, GNTK's parameters can be solved directly in a
single step. This can avoid time-consuming gradient descent. Meanwhile,
sketching has become increasingly used in speeding up various optimization
problems, including solving kernel regression. Given a kernel matrix of $n$
graphs, using sketching in solving kernel regression can reduce the running
time to $o(n^3)$. But unfortunately such methods usually require extensive
knowledge about the kernel matrix beforehand, while in the case of GNTK we find
that the construction of the kernel matrix is already $O(n^2N^4)$, assuming
each graph has $N$ nodes. The kernel matrix construction time can be a major
performance bottleneck when the size of graphs $N$ increases. A natural
question to ask is thus whether we can speed up the kernel matrix construction
to improve GNTK regression's end-to-end running time. This paper provides the
first algorithm to construct the kernel matrix in $o(n^2N^3)$ running time.
- Abstract(参考訳): 多くのディープラーニングタスクは、グラフ(例えば、タンパク質構造、ソーシャルネットワーク、ソースコード抽象構文木)を扱う必要がある。
これらのタスクの重要性から、人々はグラフ学習の事実上の方法としてグラフニューラルネットワーク(GNN)に目を向けた。
GNNは説得力のある性能のために広く採用されている。
残念なことに、GNNを使用する上で大きな障壁のひとつは、トレーニングにかなりの時間とリソースを必要とすることだ。
近年,グラフデータを用いた新しい学習法としてgraph neural tangent kernel (gntk) [du, hou, salakhutdinov, poczos, wang, xu 19] が提案されている。
GNTKはグラフデータに対するNural Tangent Kernel (NTK) [Jacot, Gabriel and Hongler 18] (カーネル法)の応用であり、NTK回帰の解法は勾配勾配を用いて無限大のニューラルネットワークを訓練するのと等価である。
GNTKを使用する主な利点は、任意のカーネルメソッドと同様に、GNTKのパラメータを1ステップで直接解決できることである。
これにより、時間を要する勾配降下を回避できる。
一方、スケッチはカーネルレグレッションの解決を含む様々な最適化問題のスピードアップにますます使われてきた。
n$グラフのカーネル行列が与えられると、カーネルレグレッションを解くのにスケッチを使うと、実行時間は$o(n^3)$になる。
しかし残念なことに、そのような手法は通常、事前にカーネル行列に関する広範な知識を必要とするが、GNTKの場合、各グラフが$N$ノードを持つと仮定すると、カーネル行列の構成は既に$O(n^2N^4)$である。
カーネル行列の構成時間は、グラフのサイズが$N$増加すると大きなパフォーマンスボトルネックとなる。
自然な質問は、gntkレグレッションのエンドツーエンド実行時間を改善するためにカーネルマトリックス構築をスピードアップできるかどうかである。
本稿では,カーネル行列を$o(n^2N^3)$実行時間で構築するアルゴリズムを提案する。
関連論文リスト
- Is Solving Graph Neural Tangent Kernel Equivalent to Training Graph
Neural Network? [9.599018775881275]
理論的深層学習の傾向は、なぜニューラルタンジェントカーネル(NTK) [jgh18]を介してディープラーニングが機能するのかを理解することである。
GNTKは,多層ニューラルネットワークのトレーニングに勾配勾配を用いたカーネル手法である。
GNTKは各種バイオインフォマティクスデータセットのGNNと同様の精度が得られることを示す。
論文 参考訳(メタデータ) (2023-09-14T06:24:33Z) - Graph Neural Tangent Kernel: Convergence on Large Graphs [7.624781434274796]
グラフニューラルネットワーク(GNN)は、グラフ機械学習タスクにおいて顕著なパフォーマンスを達成する。
グラフニューラルカーネル(GNTK)とグラフトンを用いた大規模グラフGNNのトレーニングダイナミクスについて検討する。
論文 参考訳(メタデータ) (2023-01-25T19:52:58Z) - Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
グラフニューラルネットワーク(GNN)は、ネットワーク化されたデータの意味のあるパターンを活用するために、グラフ畳み込みに依存している。
我々は,成長するグラフ列の極限オブジェクトであるグラフオンを利用して,非常に大きなグラフ上のGNNを学習することを提案する。
論文 参考訳(メタデータ) (2022-10-27T16:00:45Z) - Graph Neural Network Bandits [89.31889875864599]
グラフ構造データ上で定義された報酬関数を用いた帯域最適化問題を考察する。
この設定の主な課題は、大きなドメインへのスケーリングと、多くのノードを持つグラフへのスケーリングである。
グラフニューラルネットワーク(GNN)を用いて報酬関数を推定できることを示す。
論文 参考訳(メタデータ) (2022-07-13T18:12:36Z) - Neural Networks can Learn Representations with Gradient Descent [68.95262816363288]
特定の状況下では、勾配降下によって訓練されたニューラルネットワークは、カーネルメソッドのように振る舞う。
実際には、ニューラルネットワークが関連するカーネルを強く上回ることが知られている。
論文 参考訳(メタデータ) (2022-06-30T09:24:02Z) - Fast Finite Width Neural Tangent Kernel [47.57136433797996]
ニューラルネットワークのJacobianは、ディープラーニングの研究の中心的な対象として登場した。
有限幅NTKは計算に費用がかかることで有名である。
有限幅NTKの計算およびメモリ要求の指数を変化させる2つの新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-06-17T12:18:22Z) - Adaptive Kernel Graph Neural Network [21.863238974404474]
グラフニューラルネットワーク(GNN)は,グラフ構造化データの表現学習において大きな成功を収めている。
本稿では,AKGNN(Adaptive Kernel Graph Neural Network)という新しいフレームワークを提案する。
AKGNNは、最初の試みで最適なグラフカーネルに統一的に適応することを学ぶ。
評価されたベンチマークデータセットで実験を行い、提案したAKGNNの優れた性能を示す有望な結果を得た。
論文 参考訳(メタデータ) (2021-12-08T20:23:58Z) - Fast Sketching of Polynomial Kernels of Polynomial Degree [61.83993156683605]
他のカーネルはしばしばテイラー級数展開を通じてカーネルによって近似されるので、カーネルは特に重要である。
スケッチの最近の技術は、カーネルの$q$という難解な程度に実行時間に依存することを減らしている。
我々は、この実行時間を大幅に改善する新しいスケッチを、先頭の注文項で$q$への依存を取り除くことで提供します。
論文 参考訳(メタデータ) (2021-08-21T02:14:55Z) - Scaling Neural Tangent Kernels via Sketching and Random Features [53.57615759435126]
最近の研究報告では、NTKレグレッションは、小規模データセットでトレーニングされた有限範囲のニューラルネットワークより優れている。
我々は、アークコサインカーネルの拡張をスケッチして、NTKの近距離入力スパーシティ時間近似アルゴリズムを設計する。
CNTKの特徴をトレーニングした線形回帰器が,CIFAR-10データセット上での正確なCNTKの精度と150倍の高速化を実現していることを示す。
論文 参考訳(メタデータ) (2021-06-15T04:44:52Z) - GraphNorm: A Principled Approach to Accelerating Graph Neural Network
Training [101.3819906739515]
グラフニューラルネットワーク(GNN)における正規化の有効性について検討する。
BatchNormやLayerNormと比較して、インスタンスNormの方が高速に収束できる。
GraphNormはGNNの一般化も改善し、グラフ分類ベンチマークのパフォーマンス向上を実現している。
論文 参考訳(メタデータ) (2020-09-07T17:55:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。