論文の概要: Universal Graph Random Features

• arxiv url: http://arxiv.org/abs/2310.04859v2
• Date: Tue, 10 Oct 2023 08:03:47 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-12 14:55:44.021893
• Title: Universal Graph Random Features
• Title（参考訳）: ユニバーサルグラフランダム特徴
• Authors: Isaac Reid, Krzysztof Choromanski, Eli Berger, Adrian Weller
• Abstract要約: 重み付き隣接行列の任意の関数の偏りのない推定のためのランダムウォークに基づく新しいアルゴリズムを提案する。 提案アルゴリズムは, ノード数に関して, グラフカーネル評価の厳密な3次スケーリングを克服し, 準四次時間的複雑性を享受する。
• 参考スコア（独自算出の注目度）: 46.70803658513939
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose a novel random walk-based algorithm for unbiased estimation of arbitrary functions of a weighted adjacency matrix, coined universal graph random features (u-GRFs). This includes many of the most popular examples of kernels defined on the nodes of a graph. Our algorithm enjoys subquadratic time complexity with respect to the number of nodes, overcoming the notoriously prohibitive cubic scaling of exact graph kernel evaluation. It can also be trivially distributed across machines, permitting learning on much larger networks. At the heart of the algorithm is a modulation function which upweights or downweights the contribution from different random walks depending on their lengths. We show that by parameterising it with a neural network we can obtain u-GRFs that give higher-quality kernel estimates or perform efficient, scalable kernel learning. We provide robust theoretical analysis and support our findings with experiments including pointwise estimation of fixed graph kernels, solving non-homogeneous graph ordinary differential equations, node clustering and kernel regression on triangular meshes.
• Abstract（参考訳）: 重み付き隣接行列の任意の関数を偏りなく推定するための新しいランダムウォークベースアルゴリズム,unbiased universal graph random features (u-grfs)を提案する。 これはグラフのノード上で定義された最も一般的なカーネルの例を含む。 このアルゴリズムはノード数に関してサブクアドラティックな時間複雑性を享受し、厳密なグラフカーネル評価の厳密な立方体スケーリングを克服する。 マシン間では自明に分散することも可能で、より大きなネットワークで学習することができる。 アルゴリズムの中心にある変調関数は、その長さに応じて異なるランダムウォークからの貢献をアップウェイトまたはダウンウェイトする。 ニューラルネットワークでパラメータ化することで、高品質なカーネル推定や、効率的でスケーラブルなカーネル学習を実現するu-GRFが得られることを示す。 我々は,固定グラフカーネルのポイントワイズ推定,非均質グラフ常微分方程式の解法,ノードクラスタリング,三角メッシュ上のカーネル回帰などの実験を行い,ロバストな理論解析を行い,その実験を支援する。

関連論文リスト

• Optimal Time Complexity Algorithms for Computing General Random Walk Graph Kernels on Sparse Graphs [14.049529046098607]
  スパースグラフに対する一般ランダムウォークカーネル(RWK)の非バイアス近似のための最初の線形時間複雑性ランダム化アルゴリズムを提案する。 提案手法は,大規模グラフ上での効率的な計算において,最大$mathbf27timesの高速化を実現する。
  論文  参考訳（メタデータ） (2024-10-14T10:48:46Z)
• Heating Up Quasi-Monte Carlo Graph Random Features: A Diffusion Kernel Perspective [0.0]
  我々は最近導入された準グラフランダムな特徴のクラス(q-GRF)の上に構築する。 拡散核は2正規化ラプラシアンと最もよく似ている。 我々は、以前に確立されたアンチテーゼの終了手順の恩恵を受けるグラフタイプを探索する。
  論文  参考訳（メタデータ） (2024-10-10T21:51:31Z)
• Analysis and Approximate Inference of Large Random Kronecker Graphs [4.417282202068703]
  大規模なランダムクロネッカーグラフの隣接性は分解可能であることを示す。 本稿では,鍵グラフパラメータを推論するデノワーズ・アンド・ソルブの手法を提案する。
  論文  参考訳（メタデータ） (2023-06-14T13:09:38Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Taming graph kernels with random features [17.482280753348288]
  グラフランダム特徴(GRF)のメカニズムについて紹介する。 GRFは、グラフのノード上で定義されたいくつかの重要なカーネルの非バイアスランダム化推定器を構築するのに使うことができる。
  論文  参考訳（メタデータ） (2023-04-29T03:04:49Z)
• Graph Neural Network Bandits [89.31889875864599]
  グラフ構造データ上で定義された報酬関数を用いた帯域最適化問題を考察する。 この設定の主な課題は、大きなドメインへのスケーリングと、多くのノードを持つグラフへのスケーリングである。 グラフニューラルネットワーク(GNN)を用いて報酬関数を推定できることを示す。
  論文  参考訳（メタデータ） (2022-07-13T18:12:36Z)
• Random Features for the Neural Tangent Kernel [57.132634274795066]
  完全接続型ReLUネットワークのニューラルタンジェントカーネル(NTK)の効率的な特徴マップ構築を提案する。 得られた特徴の次元は、理論と実践の両方で比較誤差境界を達成するために、他のベースライン特徴マップ構造よりもはるかに小さいことを示しています。
  論文  参考訳（メタデータ） (2021-04-03T09:08:12Z)
• Multipole Graph Neural Operator for Parametric Partial Differential Equations [57.90284928158383]
  物理系をシミュレーションするためのディープラーニングベースの手法を使用する際の大きな課題の1つは、物理ベースのデータの定式化である。 線形複雑度のみを用いて、あらゆる範囲の相互作用をキャプチャする、新しいマルチレベルグラフニューラルネットワークフレームワークを提案する。 実験により, 離散化不変解演算子をPDEに学習し, 線形時間で評価できることを確認した。
  論文  参考訳（メタデータ） (2020-06-16T21:56:22Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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