論文の概要: Realtime Index-Free Single Source SimRank Processing on Web-Scale Graphs
- arxiv url: http://arxiv.org/abs/2002.08082v1
- Date: Wed, 19 Feb 2020 09:38:40 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-30 14:29:20.114347
- Title: Realtime Index-Free Single Source SimRank Processing on Web-Scale Graphs
- Title（参考訳）: webスケールグラフ上でのリアルタイムインデックスフリーなシングルソースシムランク処理
- Authors: Jieming Shi, Tianyuan Jin, Renchi Yang, Xiaokui Xiao, Yin Yang
- Abstract要約: 単一ソースのSimRank計算への既存のアプローチは、長いクエリ応答時間か高価なプリ計算のいずれかを発生させる。
プリ計算なしで単一のソースSimRankクエリに応答する新しいアルゴリズムSimPushを提案する。
SimPushは、最も高速なインデックスベースのソリューションよりも、クエリ処理速度が大幅に向上する。
- 参考スコア（独自算出の注目度）: 25.644425340357184
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Given a graph G and a node u in G, a single source SimRank query evaluates
the similarity between u and every node v in G. Existing approaches to single
source SimRank computation incur either long query response time, or expensive
pre-computation, which needs to be performed again whenever the graph G
changes. Consequently, to our knowledge none of them is ideal for scenarios in
which (i) query processing must be done in realtime, and (ii) the underlying
graph G is massive, with frequent updates.
Motivated by this, we propose SimPush, a novel algorithm that answers single
source SimRank queries without any pre-computation, and at the same time
achieves significantly higher query processing speed than even the fastest
known index-based solutions. Further, SimPush provides rigorous result quality
guarantees, and its high performance does not rely on any strong assumption of
the underlying graph. Specifically, compared to existing methods, SimPush
employs a radically different algorithmic design that focuses on (i)
identifying a small number of nodes relevant to the query, and subsequently
(ii) computing statistics and performing residue push from these nodes only.
We prove the correctness of SimPush, analyze its time complexity, and compare
its asymptotic performance with that of existing methods. Meanwhile, we
evaluate the practical performance of SimPush through extensive experiments on
8 real datasets. The results demonstrate that SimPush consistently outperforms
all existing solutions, often by over an order of magnitude. In particular, on
a commodity machine, SimPush answers a single source SimRank query on a web
graph containing over 133 million nodes and 5.4 billion edges in under 62
milliseconds, with 0.00035 empirical error, while the fastest index-based
competitor needs 1.18 seconds.
- Abstract（参考訳）: グラフ G と G のノード u が与えられた場合、単一のソース SimRank クエリは、G のノード v と u との類似性を評価する。
したがって、私たちの知る限りでは、これらのどれもシナリオに理想的ではありません。
(i)クエリ処理はリアルタイムに行う必要があり、
(ii) グラフ G は巨大であり、頻繁に更新される。
そこで我々は,SimPushを提案する。SimPushは,事前計算なしで単一ソースのSimRankクエリに応答する新しいアルゴリズムであり,同時に,最も高速なインデックスベースソリューションよりもはるかに高いクエリ処理速度を実現する。
さらに、SimPushは厳密な結果の品質保証を提供し、そのハイパフォーマンスは基礎となるグラフの強い仮定に依存しない。
具体的には、既存の方法と比較して、SimPushはアルゴリズム設計に重点を置いている。
(i)クエリに関連する少数のノードを識別した後
(II)計算統計とこれらのノードからの残余プッシュのみを実行すること。
我々はSimPushの正確性を証明し、その時間的複雑さを分析し、その漸近的性能を既存の手法と比較する。
一方,SimPushの実践的性能は,8つの実データセットに対する広範な実験により評価する。
結果は、SimPushが既存のソリューション全てを一貫して上回り、しばしば桁違いに上回っていることを示している。
特にコモディティマシンでは、simpushは1億3300万のノードと540億のエッジを含むwebグラフ上の1つのソースのsimrankクエリに62ミリ秒未満で回答する。
関連論文リスト
- CausalTime: Realistically Generated Time-series for Benchmarking of
Causal Discovery [14.092834149864514]
本研究では,実データに非常によく似た時系列を生成するためのCausalTimeパイプラインを紹介する。
パイプラインは、特定のシナリオにおける実際の観察から始まり、一致するベンチマークデータセットを生成する。
実験では, 定性的, 定量的な実験を行い, 既存のTSCDアルゴリズムのベンチマークを行った。
論文 参考訳（メタデータ） (2023-10-03T02:29:19Z) - SimMatchV2: Semi-Supervised Learning with Graph Consistency [53.31681712576555]
半教師付き学習アルゴリズムSimMatchV2を導入する。
グラフの観点からラベル付きデータとラベルなしデータの間の様々な一貫性の規則化を定式化する。
SimMatchV2は、複数の半教師付き学習ベンチマークで検証されている。
論文 参考訳（メタデータ） (2023-08-13T05:56:36Z) - Seq-HGNN: Learning Sequential Node Representation on Heterogeneous Graph [57.2953563124339]
本稿では,シーケンシャルノード表現,すなわちSeq-HGNNを用いた新しい異種グラフニューラルネットワークを提案する。
Heterogeneous Graph Benchmark (HGB) と Open Graph Benchmark (OGB) の4つの広く使われているデータセットについて広範な実験を行った。
論文 参考訳（メタデータ） (2023-05-18T07:27:18Z) - Graph Signal Sampling for Inductive One-Bit Matrix Completion: a
Closed-form Solution [112.3443939502313]
グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。
キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。
オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
論文 参考訳（メタデータ） (2023-02-08T08:17:43Z) - SCARA: Scalable Graph Neural Networks with Feature-Oriented Optimization [23.609017952951454]
グラフ計算のための特徴指向最適化を備えたスケーラブルグラフニューラルネットワーク(GNN)であるSCARAを提案する。
SCARAはノードの特徴からグラフの埋め込みを効率的に計算し、機能の結果を選択して再利用することでオーバーヘッドを減らします。
利用可能な最大10億のGNNデータセットであるPapers100M(1110万ノード、1.6Bエッジ)を100秒でプリ計算するのが効率的である。
論文 参考訳（メタデータ） (2022-07-19T10:32:11Z) - Optimal Propagation for Graph Neural Networks [51.08426265813481]
最適グラフ構造を学習するための二段階最適化手法を提案する。
また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
論文 参考訳（メタデータ） (2022-05-06T03:37:00Z) - Topology-Guided Sampling for Fast and Accurate Community Detection [1.0609815608017064]
本稿では,ブロック分割の高速化を目的としたトポロジー誘導サンプリング手法を提案する。
また、高速化を犠牲にして、我々のアプローチの有効性を向上させるための学位ベースのしきい値設定手法も導入する。
以上の結果から,本手法はサンプリングなしでブロック分割を最大15倍高速化する可能性が示唆された。
論文 参考訳（メタデータ） (2021-08-15T03:20:10Z) - Scaling Graph Neural Networks with Approximate PageRank [64.92311737049054]
GNNにおける情報拡散の効率的な近似を利用したPPRGoモデルを提案する。
高速であることに加えて、PPRGoは本質的にスケーラブルであり、業界設定で見られるような大規模なデータセットに対して、自明に並列化することができる。
このグラフのすべてのノードに対するPPRGoのトレーニングとラベルの予測には1台のマシンで2分未満で、同じグラフ上の他のベースラインをはるかに上回ります。
論文 参考訳（メタデータ） (2020-07-03T09:30:07Z) - CoSimGNN: Towards Large-scale Graph Similarity Computation [5.17905821006887]
グラフニューラルネットワーク(GNN)はこのタスクにデータ駆動型ソリューションを提供する。
既存のGNNベースの手法は、それぞれ2つのグラフを埋め込んだり、グラフ全体のクロスグラフインタラクションをデプロイしたりするが、まだ競合する結果が得られない。
このフレームワークは,まず適応的なプーリング操作で大きなグラフを埋め込んで粗くし,最後に類似点を求めるために粗いグラフにきめ細かな相互作用を展開させる。
論文 参考訳（メタデータ） (2020-05-14T16:33:13Z) - Gumbel-softmax-based Optimization: A Simple General Framework for
Optimization Problems on Graphs [5.486093983007419]
本稿では,ディープラーニングフレームワークによって強化された高度な自動微分技術に基づく,シンプルで高速で汎用的なアルゴリズムフレームワークを提案する。
高品質なソリューションは、従来のアプローチに比べてはるかに少ない時間で得られる。
論文 参考訳（メタデータ） (2020-04-14T14:11:00Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。