論文の概要: Large-Scale Network Embedding in Apache Spark
- arxiv url: http://arxiv.org/abs/2106.10620v1
- Date: Sun, 20 Jun 2021 04:42:24 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-23 12:38:01.286374
- Title: Large-Scale Network Embedding in Apache Spark
- Title(参考訳): Apache Sparkに組み込む大規模ネットワーク
- Authors: Wenqing Lin
- Abstract要約: 本稿では,Apache Sparkを用いた大規模グラフへのネットワーク埋め込みのための効率的かつ効率的な分散アルゴリズムを提案する。
提案手法は数時間で数十億のエッジを持つグラフを処理でき、最先端のアプローチよりも少なくとも4倍高速であることを示す。
- 参考スコア(独自算出の注目度): 1.3769786711365102
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: Network embedding has been widely used in social recommendation and network
analysis, such as recommendation systems and anomaly detection with graphs.
However, most of previous approaches cannot handle large graphs efficiently,
due to that (i) computation on graphs is often costly and (ii) the size of
graph or the intermediate results of vectors could be prohibitively large,
rendering it difficult to be processed on a single machine. In this paper, we
propose an efficient and effective distributed algorithm for network embedding
on large graphs using Apache Spark, which recursively partitions a graph into
several small-sized subgraphs to capture the internal and external structural
information of nodes, and then computes the network embedding for each subgraph
in parallel. Finally, by aggregating the outputs on all subgraphs, we obtain
the embeddings of nodes in a linear cost. After that, we demonstrate in various
experiments that our proposed approach is able to handle graphs with billions
of edges within a few hours and is at least 4 times faster than the
state-of-the-art approaches. Besides, it achieves up to $4.25\%$ and $4.27\%$
improvements on link prediction and node classification tasks respectively. In
the end, we deploy the proposed algorithms in two online games of Tencent with
the applications of friend recommendation and item recommendation, which
improve the competitors by up to $91.11\%$ in running time and up to $12.80\%$
in the corresponding evaluation metrics.
- Abstract(参考訳): ネットワーク埋め込みは、リコメンデーションシステムやグラフによる異常検出など、ソーシャルレコメンデーションやネットワーク分析に広く利用されている。
しかし、グラフ上の計算はコストがかかることが多く、(ii)グラフのサイズやベクトルの中間結果が禁止的に大きくなり、単一のマシンで処理することが難しくなるため、従来のアプローチでは大きなグラフを効率的に処理することはできない。
本稿では,Apache Sparkを用いてグラフを複数の小さなサブグラフに再帰的に分割してノードの内部および外部構造情報をキャプチャし,各サブグラフに対するネットワーク埋め込みを並列に計算する,大規模グラフへのネットワーク埋め込みのための効率的かつ効率的な分散アルゴリズムを提案する。
最後に、すべての部分グラフの出力を集約することにより、線形コストでノードの埋め込みを得る。
その後、さまざまな実験において、提案手法が数十億のエッジを持つグラフを数時間で処理でき、最先端のアプローチよりも少なくとも4倍高速であることを示す。
さらに、リンク予測とノード分類タスクで最大4.25 %$と4.27 %$の改善が達成されている。
最終的に、提案されたアルゴリズムをTencentの2つのオンラインゲームに、友人の推薦とアイテムレコメンデーションの応用で展開し、実行時に最大911.11\%、対応する評価指標で最大12.80\%の競争力を向上させる。
関連論文リスト
- T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
T-GAEはグラフオートエンコーダフレームワークで、GNNの転送性と安定性を活用して、再トレーニングなしに効率的なネットワークアライメントを実現する。
実験の結果、T-GAEは最先端の最適化手法と最高のGNN手法を最大38.7%、50.8%で上回っていることがわかった。
論文 参考訳(メタデータ) (2023-10-05T02:58:29Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳(メタデータ) (2023-06-14T09:21:15Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳(メタデータ) (2022-10-14T01:42:05Z) - Optimal Propagation for Graph Neural Networks [51.08426265813481]
最適グラフ構造を学習するための二段階最適化手法を提案する。
また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
論文 参考訳(メタデータ) (2022-05-06T03:37:00Z) - Neighbor2Seq: Deep Learning on Massive Graphs by Transforming Neighbors
to Sequences [55.329402218608365]
本研究では,各ノードの階層的近傍をシーケンスに変換するためにNeighbor2Seqを提案する。
1100万以上のノードと160億のエッジを持つ大規模グラフ上で,本手法の評価を行った。
その結果,提案手法は大規模グラフに対してスケーラブルであり,大規模グラフと中規模グラフにまたがる優れた性能を実現する。
論文 参考訳(メタデータ) (2022-02-07T16:38:36Z) - RaWaNet: Enriching Graph Neural Network Input via Random Walks on Graphs [0.0]
グラフニューラルネットワーク(GNN)の人気が高まっており、グラフで表されるデータに対して非常に有望な結果を示している。
本稿では,3つの選択された長さに基づいて,グラフのランダムなウォークデータ処理を提案する。すなわち,グラフ上の局所的および大域的ダイナミクスを捉えるために,長さ1,2の(正規)ウォークと長さ0,1$の分節ウォークを提案する。
本手法は, 処理ノードの特徴をネットワークに渡すことによって, 様々な分子データセット上で検証し, 分類および回帰処理を行う。
論文 参考訳(メタデータ) (2021-09-15T20:04:01Z) - Evaluating Node Embeddings of Complex Networks [0.0]
agood embeddedはグラフトポロジー、ノード間関係、およびグラフに関する他の関連情報をキャプチャする。
主な課題は、埋め込みがグラフの特性をうまく記述することを保証する必要があることである。
実世界のネットワーク上でも人工的に生成されたものでも、選択したグラフ埋め込みアルゴリズムを用いて一連の実験を行う。
論文 参考訳(メタデータ) (2021-02-16T16:55:29Z) - 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) - SIGN: Scalable Inception Graph Neural Networks [4.5158585619109495]
本稿では,グラフサンプリングの必要性を助長する,効率的でスケーラブルなグラフ深層学習アーキテクチャを提案する。
私たちのアーキテクチャでは、異なるローカルグラフ演算子を使用して、そのタスクに最も適しています。
我々は,1億1000万のノードと15億のエッジを持つ,最大の公開グラフデータセットであるogbn-papers100Mについて,最先端の結果を得た。
論文 参考訳(メタデータ) (2020-04-23T14:46:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。