論文の概要: Computationally-efficient Graph Modeling with Refined Graph Random Features

• arxiv url: http://arxiv.org/abs/2510.07716v1
• Date: Thu, 09 Oct 2025 02:53:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-10 17:54:14.824249
• Title: Computationally-efficient Graph Modeling with Refined Graph Random Features
• Title（参考訳）: 精製グラフランダム特徴量を用いた計算効率の良いグラフモデリング
• Authors: Krzysztof Choromanski, Avinava Dubey, Arijit Sehanobish, Isaac Reid,
• Abstract要約: 本稿では,グラフランダム特徴量(GRF)の新しいクラスを提案する。 GRFs++は、通常のGRFの長年の制限を解決している。 これにより、新しいウォークスティッチ技術により、長いグラフのランダムウォークのサンプリングへの依存を減らすことができる。
• 参考スコア（独自算出の注目度）: 13.71262071974362
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose refined GRFs (GRFs++), a new class of Graph Random Features (GRFs) for efficient and accurate computations involving kernels defined on the nodes of a graph. GRFs++ resolve some of the long-standing limitations of regular GRFs, including difficulty modeling relationships between more distant nodes. They reduce dependence on sampling long graph random walks via a novel walk-stitching technique, concatenating several shorter walks without breaking unbiasedness. By applying these techniques, GRFs++ inherit the approximation quality provided by longer walks but with greater efficiency, trading sequential, inefficient sampling of a long walk for parallel computation of short walks and matrix-matrix multiplication. Furthermore, GRFs++ extend the simplistic GRFs walk termination mechanism (Bernoulli schemes with fixed halting probabilities) to a broader class of strategies, applying general distributions on the walks' lengths. This improves the approximation accuracy of graph kernels, without incurring extra computational cost. We provide empirical evaluations to showcase all our claims and complement our results with theoretical analysis.
• Abstract（参考訳）: 我々は,グラフのノード上で定義されたカーネルを包含する高速かつ正確な計算を行うため,改良されたGRF (GRFs++) を提案する。 GRFs++は、より遠いノード間の関係をモデル化することの難しさを含む、通常のGRFの長年の制限のいくつかを解決している。 長いグラフのランダムウォークのサンプリングへの依存を減らし、新しいウォークスティッチ技術により、不偏を壊さずにいくつかの短いウォークを連結する。 これらの手法を適用することで、GRFs++はより長いウォークによって提供される近似品質を継承するが、より効率が高く、シーケンシャルに取引され、短いウォークと行列行列行列の乗算の並列計算のための長いウォークの非効率サンプリングを行う。 さらに、GRFs++は、単純なGRFのウォーク終了機構(固定停止確率を持つベルヌーリスキーム)をより広範な戦略に拡張し、ウォークの長さに一般的な分布を適用する。 これにより、余分な計算コストを発生させることなく、グラフカーネルの近似精度が向上する。 我々は、すべての主張を実証し、理論分析で結果を補完する実証的な評価を提供する。

関連論文リスト

• Efficient Graph Condensation via Gaussian Process [8.099774846541438]
  グラフ凝縮は、性能を維持しながら大きなグラフのサイズを減らす。 既存の手法はしばしば二段階最適化に依存しており、広範囲なGNNトレーニングとスケーラビリティの制限を必要とする。 本稿では,ガウス過程を用いたグラフ凝縮法(GCGP)を提案する。
  論文  参考訳（メタデータ） (2025-01-05T14:43:07Z)
• Sparse Training of Discrete Diffusion Models for Graph Generation [45.103518022696996]
  SparseDiffは、ほとんど全ての大きなグラフがスパースであるという観察に基づく、新しい拡散モデルである。 エッジのサブセットを選択することで、SparseDiffは、ノイズ発生過程とノイズ発生ネットワーク内のスパースグラフ表現を効果的に活用する。 本モデルでは,小規模・大規模両方のデータセットにおいて,複数のメトリクスにわたる最先端性能を示す。
  論文  参考訳（メタデータ） (2023-11-03T16:50:26Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Quasi-Monte Carlo Graph Random Features [38.762964164013226]
  グラフランダム特徴量(GRF)の精度向上のための新しいメカニズムを提案する。 提案手法は, アルゴリズムのランダムウォークの長さ間の負の相関を, アンチセティック終端を付与することによって引き起こす。 これらの準モンテカルロ GRF の性質に関する強い理論的保証を得る。
  論文  参考訳（メタデータ） (2023-05-21T14:12:02Z)
• Taming graph kernels with random features [17.482280753348288]
  グラフランダム特徴(GRF)のメカニズムについて紹介する。 GRFは、グラフのノード上で定義されたいくつかの重要なカーネルの非バイアスランダム化推定器を構築するのに使うことができる。
  論文  参考訳（メタデータ） (2023-04-29T03:04:49Z)
• Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks [52.566735716983956]
  本稿では,CGPと呼ばれるグラフの段階的プルーニングフレームワークを動的にGNNに提案する。 LTHに基づく手法とは異なり、提案手法では再学習を必要とせず、計算コストを大幅に削減する。 提案手法は,既存の手法の精度を一致させたり,あるいは超えたりしながら,トレーニングと推論の効率を大幅に向上させる。
  論文  参考訳（メタデータ） (2022-07-18T14:23:31Z)
• Fast Graph Attention Networks Using Effective Resistance Based Graph Sparsification [70.50751397870972]
  FastGATは、スペクトルスペーシフィケーションを用いて、注目に基づくGNNを軽量にし、入力グラフの最適プルーニングを生成する手法である。 我々は,ノード分類タスクのための大規模実世界のグラフデータセット上でFastGATを実験的に評価した。
  論文  参考訳（メタデータ） (2020-06-15T22:07:54Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)
• Gated Graph Recurrent Neural Networks [176.3960927323358]
  グラフ処理の一般的な学習フレームワークとしてグラフリカレントニューラルネットワーク(GRNN)を導入する。 勾配の消失問題に対処するため,時間,ノード,エッジゲートの3つの異なるゲーティング機構でGRNNを前進させた。 数値的な結果は、GRNNがGNNやRNNよりも優れており、グラフプロセスの時間構造とグラフ構造の両方を考慮することが重要であることを示している。
  論文  参考訳（メタデータ） (2020-02-03T22:35:14Z)

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

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