論文の概要: Accelerated Evolving Set Processes for Local PageRank Computation

• arxiv url: http://arxiv.org/abs/2510.08010v1
• Date: Thu, 09 Oct 2025 09:47:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-10 17:54:14.994183
• Title: Accelerated Evolving Set Processes for Local PageRank Computation
• Title（参考訳）: ローカルPageRank計算のためのアクセラレーション・エクリプティング・セット・プロセス
• Authors: Binbin Huang, Luo Luo, Yanghua Xiao, Deqing Yang, Baojian Zhou,
• Abstract要約: この研究は、パーソナライズされたPageRank計算を高速化するために、ネストした進化したセットプロセスに基づく新しいフレームワークを提案する。 このような局所化手法の時間複雑性は、PPRベクトルの$epsilon$-approximationを得るために$mintildemathcalO(R2/epsilon2), tildemathcalO(m)$によって上界となることを示す。
• 参考スコア（独自算出の注目度）: 75.54334100808022
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This work proposes a novel framework based on nested evolving set processes to accelerate Personalized PageRank (PPR) computation. At each stage of the process, we employ a localized inexact proximal point iteration to solve a simplified linear system. We show that the time complexity of such localized methods is upper bounded by $\min\{\tilde{\mathcal{O}}(R^2/\epsilon^2), \tilde{\mathcal{O}}(m)\}$ to obtain an $\epsilon$-approximation of the PPR vector, where $m$ denotes the number of edges in the graph and $R$ is a constant defined via nested evolving set processes. Furthermore, the algorithms induced by our framework require solving only $\tilde{\mathcal{O}}(1/\sqrt{\alpha})$ such linear systems, where $\alpha$ is the damping factor. When $1/\epsilon^2\ll m$, this implies the existence of an algorithm that computes an $\ epsilon $-approximation of the PPR vector with an overall time complexity of $\tilde{\mathcal{O}}\left(R^2 / (\sqrt{\alpha}\epsilon^2)\right)$, independent of the underlying graph size. Our result resolves an open conjecture from existing literature. Experimental results on real-world graphs validate the efficiency of our methods, demonstrating significant convergence in the early stages.
• Abstract（参考訳）: 本研究は,Personalized PageRank(PPR)計算を高速化するために,ネストした進化過程に基づく新しいフレームワークを提案する。 プロセスの各段階では、単純化された線形系を解くために、局所化された不正確な近位点反復を用いる。 そのようなローカライズドメソッドの時間複雑性は、PPRベクトルの$\epsilon$-approximationを得るために$\min\{\tilde{\mathcal{O}}(R^2/\epsilon^2), \tilde{\mathcal{O}}(m)\}$により上界であることが示される。 さらに、我々のフレームワークによって誘導されるアルゴリズムは、$\tilde{\mathcal{O}}(1/\sqrt{\alpha})$そのような線形系のみを解く必要がある。 1/\epsilon^2\ll m$ のとき、これは、基礎となるグラフサイズとは独立に、$\tilde{\mathcal{O}}\left(R^2 / (\sqrt{\alpha}\epsilon^2)\right)$の全体的な時間複雑性を持つ PPR ベクトルの$\ epsilon $-approximation を計算するアルゴリズムの存在を意味する。 私たちの結果は、既存の文献からのオープンな予想を解決します。 実世界のグラフ実験により,本手法の有効性が検証され,初期の段階において顕著な収束が示された。

関連論文リスト

• Iterative Methods via Locally Evolving Set Process [43.405427507066065]
  Approximate Personalized PageRank (APPR)はGauss-Seidelのローカル版である。 我々はAPPRが新しいランタイム境界である$tildeO(overlineoperatornamevol(S_t)/overlinegamma_t leq 1/epsilon$を認めたことを示す。 計算結果は,本フレームワークの効率を確認し,実世界のグラフ上で対応する標準解法よりも100倍の高速化を示す。
  論文  参考訳（メタデータ） (2024-10-19T07:28:11Z)
• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  複素勾配問題に対する2つの分散化ZO推定器を提案する。 我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
  論文  参考訳（メタデータ） (2024-10-03T15:04:01Z)
• Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method [10.742859956268655]
  本稿では,レバレッジスコア勾配から固有モデルパラメータを復元することを目的とする。 具体的には、レバレッジスコア勾配の逆転を$g(x)$として精査する。
  論文  参考訳（メタデータ） (2024-08-21T01:39:42Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity [15.18055488087588]
  上記の凸定式化を$widetildeO(sum_i=1n d_i log (1 /epsilon))$グラデーション計算で$epsilon$-accuracyに最小化するアルゴリズムを与える。 我々の主な技術的貢献は、カットプレーン法とインテリアポイント法を組み合わせた新しい組み合わせにより、各イテレーションで$f_i$項を選択する適応的な手順である。
  論文  参考訳（メタデータ） (2022-08-07T20:53:42Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。 複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。 少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
  論文  参考訳（メタデータ） (2021-06-14T07:36:25Z)

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

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