論文の概要: Optimal Time Complexity Algorithms for Computing General Random Walk Graph Kernels on Sparse Graphs

• arxiv url: http://arxiv.org/abs/2410.10368v1
• Date: Tue, 15 Oct 2024 14:12:43 GMT
• ステータス: 処理完了
• システム内更新日: 2024-10-29 22:04:40.542580
• Title: Optimal Time Complexity Algorithms for Computing General Random Walk Graph Kernels on Sparse Graphs
• Title（参考訳）: スパースグラフ上の一般ランダムウォークグラフカーネルの最適時間複雑度アルゴリズム
• Authors: Krzysztof Choromanski, Isaac Reid, Arijit Sehanobish, Avinava Dubey,
• Abstract要約: スパースグラフに対する一般ランダムウォークカーネル(RWK)の非バイアス近似のための最初の線形時間複雑性ランダム化アルゴリズムを提案する。 提案手法は,大規模グラフ上での効率的な計算において,最大$mathbf27timesの高速化を実現する。
• 参考スコア（独自算出の注目度）: 14.049529046098607
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present the first linear time complexity randomized algorithms for unbiased approximation of the celebrated family of general random walk kernels (RWKs) for sparse graphs. This includes both labelled and unlabelled instances. The previous fastest methods for general RWKs were of cubic time complexity and not applicable to labelled graphs. Our method samples dependent random walks to compute novel graph embeddings in $\mathbb{R}^d$ whose dot product is equal to the true RWK in expectation. It does so without instantiating the direct product graph in memory, meaning we can scale to massive datasets that cannot be stored on a single machine. We derive exponential concentration bounds to prove that our estimator is sharp, and show that the ability to approximate general RWKs (rather than just special cases) unlocks efficient implicit graph kernel learning. Our method is up to $\mathbf{27\times}$ faster than its counterparts for efficient computation on large graphs and scales to graphs $\mathbf{128 \times}$ bigger than largest examples amenable to brute-force computation.
• Abstract（参考訳）: スパースグラフに対する一般ランダムウォークカーネル(RWK)の無バイアス近似のための最初の線形時間複雑性ランダム化アルゴリズムを提案する。 これにはラベル付きインスタンスと非ラベル付きインスタンスの両方が含まれる。 これまでのRWKの最も高速な手法は3次時間複雑性であり、ラベル付きグラフには適用できない。 提案手法はランダムウォークを用いて$\mathbb{R}^d$ の新たなグラフ埋め込みを計算し,ドット積は期待値の真の RWK に等しい。 つまり、単一のマシンに格納できない巨大なデータセットにスケールできるのです。 指数集中束を導出し、我々の推定器がシャープであることを証明し、一般RWKを(単なる特殊な場合ではなく)近似できる能力が効率的な暗黙グラフカーネル学習を解き放つことを示す。 我々の手法は、大きなグラフ上の効率的な計算とグラフへのスケールのために、最大$\mathbf{27\times}$がそれよりも高速である。

関連論文リスト

• A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
  このようなグラフに特化された効率的な(epsilon,$delta$)-DPアルゴリズムを提供する。 我々のアルゴリズムは、ほぼバランスの取れたクラスタに対して$k$のグラフを扱う。
  論文  参考訳（メタデータ） (2024-03-21T11:57:16Z)
• Fast and Simple Spectral Clustering in Theory and Practice [7.070726553564701]
  スペクトルクラスタリング(Spectral clustering)は、グラフの$G$で$k$のクラスタを見つけるために設計された、人気があり効果的なアルゴリズムである。 電力法により計算された$O(log(k))$の頂点埋め込みに基づく単純なスペクトルクラスタリングアルゴリズムを提案する。 合成および実世界の複数のデータセット上で新しいアルゴリズムを評価し,クラスタリングの精度をほぼ同一にしながら,他のクラスタリングアルゴリズムよりもはるかに高速であることを確認した。
  論文  参考訳（メタデータ） (2023-10-17T02:31:57Z)
• General Graph Random Features [42.75616308187867]
  重み付き隣接行列の任意の関数の偏りのない推定のためのランダムウォークに基づく新しいアルゴリズムを提案する。 提案アルゴリズムは, ノード数に関して, グラフカーネル評価の厳密な3次スケーリングを克服し, 準四次時間的複雑性を享受する。
  論文  参考訳（メタデータ） (2023-10-07T15:47:31Z)
• AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution [79.44066256794187]
  我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。 アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。 理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
  論文  参考訳（メタデータ） (2021-11-12T07:08:13Z)
• Fast Graph Kernel with Optical Random Features [17.403133838762447]
  グラフレットカーネルは、同型テストを含むため、高い計算コストに悩まされる。 本稿では,グラフレットフレームワーク内のカーネルランダムな特徴を活用し,平均的なカーネルメトリックと理論的なリンクを確立することを提案する。
  論文  参考訳（メタデータ） (2020-10-16T09:43:47Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
  カーネル法は、非パラメトリック学習に対するエレガントで原則化されたアプローチを提供するが、今のところ大規模な問題ではほとんど利用できない。 最近の進歩は、最適化、数値線形代数、ランダム射影など、多くのアルゴリズム的アイデアの利点を示している。 ここでは、これらの取り組みをさらに進めて、GPUハードウェアを最大限に活用する解決器を開発し、テストする。
  論文  参考訳（メタデータ） (2020-06-18T08:16:25Z)
• Fast Graph Attention Networks Using Effective Resistance Based Graph Sparsification [70.50751397870972]
  FastGATは、スペクトルスペーシフィケーションを用いて、注目に基づくGNNを軽量にし、入力グラフの最適プルーニングを生成する手法である。 我々は,ノード分類タスクのための大規模実世界のグラフデータセット上でFastGATを実験的に評価した。
  論文  参考訳（メタデータ） (2020-06-15T22:07:54Z)
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case [6.810856082577402]
  量子回路は、グラフの局所性を尊重するユニタリ作用素の p 個の応用を持つ。 我々は、d と n を大きく保った dn/2 エッジを持つランダムグラフにおいて、大きな独立集合を見つけることに集中する。
  論文  参考訳（メタデータ） (2020-04-20T00:48:02Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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