論文の概要: Taming graph kernels with random features

• arxiv url: http://arxiv.org/abs/2305.00156v1
• Date: Sat, 29 Apr 2023 03:04:49 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-02 16:50:28.297834
• Title: Taming graph kernels with random features
• Title（参考訳）: ランダムな特徴を持つグラフカーネルの改ざん
• Authors: Krzysztof Choromanski
• Abstract要約: グラフランダム特徴(GRF)のメカニズムについて紹介する。 GRFは、グラフのノード上で定義されたいくつかの重要なカーネルの非バイアスランダム化推定器を構築するのに使うことができる。
• 参考スコア（独自算出の注目度）: 17.482280753348288
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce in this paper the mechanism of graph random features (GRFs). GRFs can be used to construct unbiased randomized estimators of several important kernels defined on graphs' nodes, in particular the regularized Laplacian kernel. As regular RFs for non-graph kernels, they provide means to scale up kernel methods defined on graphs to larger networks. Importantly, they give substantial computational gains also for smaller graphs, while applied in downstream applications. Consequently, GRFs address the notoriously difficult problem of cubic (in the number of the nodes of the graph) time complexity of graph kernels algorithms. We provide a detailed theoretical analysis of GRFs and an extensive empirical evaluation: from speed tests, through Frobenius relative error analysis to kmeans graph-clustering with graph kernels. We show that the computation of GRFs admits an embarrassingly simple distributed algorithm that can be applied if the graph under consideration needs to be split across several machines. We also introduce a (still unbiased) quasi Monte Carlo variant of GRFs, q-GRFs, relying on the so-called reinforced random walks, that might be used to optimize the variance of GRFs. As a byproduct, we obtain a novel approach to solve certain classes of linear equations with positive and symmetric matrices.
• Abstract（参考訳）: 本稿では,グラフランダム特徴(GRF)のメカニズムを紹介する。 GRFはグラフのノード上で定義されたいくつかの重要なカーネル、特に正規化されたラプラシアカーネルの非バイアスランダム化推定器を構築するのに使うことができる。 非グラフカーネルの通常のRFとして、グラフ上で定義されたカーネルメソッドをより大きなネットワークにスケールアップする手段を提供する。 重要なのは、下流のアプリケーションに適用しながら、より小さなグラフに対してもかなりの計算量が得られることだ。 その結果、GRFはグラフカーネルアルゴリズムの3乗(グラフのノード数)時間複雑性の非常に難しい問題に対処する。 速度テストからフロベニウス相対誤差解析から、グラフカーネルを用いたkmeansグラフクラスタリングまで、幅広い経験的評価を行った。 GRFの計算は、考慮中のグラフを複数のマシンに分割する必要がある場合に適用可能な、恥ずかしいほど単純な分散アルゴリズムを許容していることを示す。 我々はまた、GRFの分散を最適化するために用いられる、いわゆる強化ランダムウォークに依存する(まだバイアスのない)準モンテカルロ変種 q-GRF も導入する。 副産物として、正および対称行列を持つ線型方程式のある種のクラスを解く新しいアプローチを得る。

関連論文リスト

• Heating Up Quasi-Monte Carlo Graph Random Features: A Diffusion Kernel Perspective [0.0]
  我々は最近導入された準グラフランダムな特徴のクラス(q-GRF)の上に構築する。 拡散核は2正規化ラプラシアンと最もよく似ている。 我々は、以前に確立されたアンチテーゼの終了手順の恩恵を受けるグラフタイプを探索する。
  論文  参考訳（メタデータ） (2024-10-10T21:51:31Z)
• General Graph Random Features [42.75616308187867]
  重み付き隣接行列の任意の関数の偏りのない推定のためのランダムウォークに基づく新しいアルゴリズムを提案する。 提案アルゴリズムは, ノード数に関して, グラフカーネル評価の厳密な3次スケーリングを克服し, 準四次時間的複雑性を享受する。
  論文  参考訳（メタデータ） (2023-10-07T15:47:31Z)
• Analysis and Approximate Inference of Large Random Kronecker Graphs [4.417282202068703]
  大規模なランダムクロネッカーグラフの隣接性は分解可能であることを示す。 本稿では,鍵グラフパラメータを推論するデノワーズ・アンド・ソルブの手法を提案する。
  論文  参考訳（メタデータ） (2023-06-14T13:09:38Z)
• Graph Fourier MMD for Signals on Graphs [67.68356461123219]
  本稿では,グラフ上の分布と信号の間の新しい距離を提案する。 GFMMDは、グラフ上で滑らかであり、期待差を最大化する最適な目撃関数によって定義される。 グラフベンチマークのデータセットと単一セルRNAシークエンシングデータ解析について紹介する。
  論文  参考訳（メタデータ） (2023-06-05T00:01:17Z)
• Quasi-Monte Carlo Graph Random Features [38.762964164013226]
  グラフランダム特徴量(GRF)の精度向上のための新しいメカニズムを提案する。 提案手法は, アルゴリズムのランダムウォークの長さ間の負の相関を, アンチセティック終端を付与することによって引き起こす。 これらの準モンテカルロ GRF の性質に関する強い理論的保証を得る。
  論文  参考訳（メタデータ） (2023-05-21T14:12:02Z)
• Graph Neural Network Bandits [89.31889875864599]
  グラフ構造データ上で定義された報酬関数を用いた帯域最適化問題を考察する。 この設定の主な課題は、大きなドメインへのスケーリングと、多くのノードを持つグラフへのスケーリングである。 グラフニューラルネットワーク(GNN)を用いて報酬関数を推定できることを示す。
  論文  参考訳（メタデータ） (2022-07-13T18:12:36Z)
• Graph Based Gaussian Processes on Restricted Domains [13.416168979487118]
  非パラメトリック回帰では、入力はユークリッド空間の制限された部分集合に落ちるのが一般的である。 入力領域の幾何学を尊重する共分散を学習するグラフラプラシアン型GP(GL-GP)の新たなクラスを提案する。 本稿では,GL-GP手法の理論的サポートを提供し,各種アプリケーションの性能向上を示す。
  論文  参考訳（メタデータ） (2020-10-14T17:01:29Z)
• Dirichlet Graph Variational Autoencoder [65.94744123832338]
  本稿では,グラフクラスタメンバシップを潜在因子とするDGVAE(Dirichlet Graph Variational Autoencoder)を提案する。 バランスグラフカットにおける低パス特性により、入力グラフをクラスタメンバシップにエンコードする、Heattsと呼ばれるGNNの新しい変種を提案する。
  論文  参考訳（メタデータ） (2020-10-09T07:35:26Z)
• Embedding Graph Auto-Encoder for Graph Clustering [90.8576971748142]
  グラフ自動エンコーダ(GAE)モデルは、半教師付きグラフ畳み込みネットワーク(GCN)に基づく 我々は、グラフクラスタリングのための特定のGAEベースのモデルを設計し、その理論、すなわち、埋め込みグラフオートエンコーダ(EGAE)と整合する。 EGAEは1つのエンコーダと2つのデコーダで構成される。
  論文  参考訳（メタデータ） (2020-02-20T09:53:28Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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