テンセントの高性能グラフコンピューティングフレームワークPlatoとそのアルゴリズムの応用

[[318509]]

プラトンについて

テンセントの高性能グラフコンピューティングフレームワークPlato

グラフは、ビッグデータを表現および分析するための効果的な方法として、ソーシャル ネットワーク、推奨システム、ネットワーク セキュリティ、テキスト検索、バイオメディカルなどの分野で重要なデータ分析およびマイニング ツールになっています。たとえば、ユーザーの検索エクスペリエンスを向上させるために影響力に基づいて Web ページを定期的にランク付けしたり、大規模なソーシャル ネットワーク構造を分析してユーザーにサービスを正確に推奨したり、サブグラフ マッチングなどの方法を通じてタンパク質間の相互作用を理解してより効果的な臨床医薬品を開発したりします。

Plato は、Tencent のグラフ コンピューティング TGraph が Tencent の内部グラフ コンピューティング リソースを統合して作成した、業界をリードする超大規模グラフ コンピューティング プラットフォームです。 Plato は数十億のノードを持つ超大規模グラフ コンピューティングをターゲットにしており、アルゴリズムの計算時間を数日から数分に短縮し、パフォーマンスを数十倍向上させて業界トップ レベルに到達し、数百のサーバーを必要とすることが多いリソースのボトルネックを解消します。計算を完了するために必要なサーバーはわずか 10 台です。 Plato は、WeChat を含む Tencent 内の多くの中核事業を強化し、ビジネス価値を大きく創造します。

図1: プラトン建築

Plato オープンソース アドレス: https://github.com/tencent/plato

Plato 高性能グラフ コンピューティング フレームワークの主な貢献は次のとおりです。

1. Platoは、テンセントの超大規模ソーシャルネットワークグラフデータに対する各種計算を効率的にサポートし、その性能は学界と産業界のトップレベルに達しており、Spark GraphXよりも1〜2桁高くなっています。日常的に計算される多くのアルゴリズムを数時間、さらには数分で完了することを可能にし、テンセントのグラフコンピューティングが分レベルの時代に完全に突入したことも意味します。
2. Plato のメモリ消費量は Spark GraphX より 1 ～ 2 桁少ないため、Tencent データ レベルでの超大規模グラフ計算を完了するには小規模または中規模のクラスター (約 10 台のサーバー) のみが必要となり、数百台のサーバーを必要とするリソースのボトルネックが解消され、コンピューティング コストも大幅に節約されます。
3. PlatoはテンセントのグラフコンピューティングTGraphに属し、超大規模ソーシャルネットワークグラフデータから生まれましたが、他の種類のグラフデータにも完璧に適応できます。同時に、高性能、スケーラブル、プラグイン可能な産業グレードのグラフコンピューティングフレームワークとして、Platoは業界の超大規模グラフコンピューティングフレームワークの技術進歩を促進してきました。

プラトンアルゴリズムの応用

Plato は現在、ノード中心性インジケーター、接続グラフ、コミュニティ検出、グラフ表現学習など、さまざまなグラフ アルゴリズムをサポートしています。この記事では、Plato に基づくコミュニティ検出アルゴリズムの紹介に焦点を当てます。

ソーシャル ネットワークには、多くの場合、クラスタリング効果があります。似たような背景や同じ趣味を持つ人々が集まり、サークル (コミュニティ) を形成する傾向があります。特定のソーシャル ネットワークから現実のサークルを復元する方法は、ソーシャル レコメンデーション、ソーシャル マーケティングなどの分野で非常に幅広く応用されています。

コミュニティ発見アルゴリズムの紹介

複雑ネットワークにおけるクラスタリング効果

複雑ネットワーク研究では、グラフを使用してネットワークを表します。ネットワークの参加者はノード (頂点) に抽象化され、参加者間の相互作用または接続はノード間のエッジ (エッジ) に抽象化されます。これらのノードの集合 V = {v1,v2,··· ,vn} とエッジの集合 E = {vivj | vi,vj ∈ V } は、グラフ G(V,E) を構成します。

図 2 に示すように、ネットワークには内部接続が密で外部接続が疎なノードのクラスターが 4 つあります。これはクラスタリング効果を直感的に反映したものです。これらのクラスターは通常、コミュニティと呼ばれます。コミュニティ検出アルゴリズムの目的は、ノードを異なるコミュニティに正確に分割することです。このネットワークでは、古典的なコミュニティ発見アルゴリズムを使用します。計算結果は図 3 に示されており、コミュニティの所属はノードの色でマークされています。

図2: ソーシャルネットワーク

図3: コミュニティ発見計算結果

モジュール性指数

モジュール性指数はコミュニティの分割の質をよりよく特徴付けることができる[1]。

同じネットワークでも、異なるコミュニティ区分は通常、異なるモジュール性に対応します。図 4 と 5 を例にとると、異なるコミュニティが異なる色で区別されている場合、図 4 の単純区分のモジュール性は 0 で、図 5 の非単純区分のモジュール性は 5/14 です。明らかに、後者の区分の方が合理的です。これは、モジュールの大きさがコミュニティ分割の品質をある程度反映できることを示しています。値が大きいほど、分割の品質が高くなります。

エッジの媒介性に基づく分割アルゴリズム

コミュニティ分割の品質を測る基準であるモジュール性を見つけました。次のステップは、モジュール性を最大化するコミュニティ分割を見つけることです。モジュラリティ最大化問題はNP困難問題であることが証明されている[5]。したがって、許容できる時間内にコミュニティ分割を得るために、貪欲な戦略を使用して次善の解決策を探すことがよくありますが、これはデータ クラスタリングの考え方とまったく同じです。

次に紹介するクラスタリング アルゴリズムは、分割アルゴリズムと凝集アルゴリズムに分けられます。まず、接続されたエッジを削除することでクラスタリングの目的を達成する分割アルゴリズムを紹介します。まず、ネットワーク全体をコミュニティと見なし、次に中間度が最も大きいエッジを連続的に削除して複数のコミュニティに分割し、次にモジュール性インジケータを使用して分割の深さを制御します。分割アルゴリズムは、ネットワーク全体のエッジ間の計算を伴うため、計算量が大きすぎて、エンジニアリングに実装することが困難です。次に、エンジニアリングに実装しやすいアルゴリズムを紹介します。

モジュール性ゲインに基づく凝集アルゴリズム

大規模ネットワークには適用できず、小規模コミュニティを識別できないという分割アルゴリズムの欠点を解決するために、階層的なコミュニティ構造を検出できる凝集アルゴリズム[2]（高速展開アルゴリズム）が提案されています。まず、各ノードをコミュニティと見なし、次にモジュール性ゲインを最大化する隣接コミュニティをより大きなコミュニティに吸収し、モジュール性ゲインがゼロに達するとアルゴリズムを停止します。

アルゴリズムは最終的に複数のコミュニティ区分を出力する可能性があります。各凝集度はコミュニティ区分のレベルに対応します。レベルが低いほどコミュニティのサイズが小さくなり、小規模コミュニティの検出漏れを回避できます。

ラベル伝播アルゴリズム

ラベル伝播アルゴリズム[3]（略してLPA）は目的関数によって導かれるものではない。一般的なプロセスは、ノードが属するコミュニティの名前がノードラベルとして使用され、ラベルが何らかの方法でネットワークに伝播されるというものである。ラベル伝播が安定すると、各ノードは所属するコミュニティを識別するラベルを持ち、コミュニティの分割が完了します。

しかし、LPA には無視できない弱点もあります。それは、計算結果のランダム性が高いことです。LPA を 2 回実行した場合のコミュニティ分割の結果は、一貫性がないことがよくあります。 LPA が隣接ラベルを使用してノード ラベルを更新する場合、各隣接と各ラベルの重要性は等しくなります。伝播プロセスにおける LPA のランダム性と組み合わせると、ランダム伝播によって発生したエラーが複数回伝播され、継続的に拡散および増幅される可能性があります。

そこで、HANPアルゴリズム[4]が提案された。近傍ラベルを収集する際に、各近傍ノードの重要度と複数回の伝播後の各ラベルの減衰を総合的に考慮し、エラー発生確率を低減し、エラー増幅を抑制する。

Platoの高性能実装に基づくコミュニティ発見アルゴリズム

業界実装ソリューション

近年のグラフコンピューティングの発展により、多くの優れたグラフコンピューティング フレームワークが登場しました。

C/C++で書かれたGraphLabとPowerGraphシステムは、メッセージパッシングに基づくプログラミングインターフェースとグラフアルゴリズムの高性能な分散実装のセットを提供しますが、システム実装レベルでのCOST（単一スレッドよりも優れた構成）[6]は比較的高くなります。

Spark GraphXシステムは、Sparkのビッグデータエコシステムを組み合わせ、GraphLabやPowerGraphに比べてプログラミングインターフェースの使いやすさを向上させ、計算上のフォールトトレランスの問題をうまく処理します。ただし、Java/Scala言語自体のオーバーヘッドのため、理想的なパフォーマンスを実現することはできません。

Gemini[7]システムは、低コストでスケーラブルな分散グラフコンピューティング設計ソリューションを提供します。

図6: さまざまな計算モードでのLPAアルゴリズム実行の概略図

コミュニティ識別アルゴリズムにはさまざまな計算モードがあります。LPAやHANPなどのアルゴリズムの場合、既存の計算モードには大きなパフォーマンス上の問題があります。図6では、Geminiシステムを例に詳しく説明しています。

高密度モードでは、ノード D は隣接ノードからラベルを取得し、それらを 1 つのメッセージ (それぞれ A と B のラベル値を表す 2 つの要素 (La,1) と (Lb,1) を含む) にマージしようとします。固定長のメッセージに結合することはできないため、メッセージ D と E の合計長は 5 になります。

スパースモードでは、A は自身のラベルを A のミラーノードに送信するため、3 つのノード ABC によって送信されるメッセージの合計長は 3 となり、密なモードと比較して通信量が大幅に削減されます。ただし、スパース モードでは、3 つのノード ABC が 2 つのノード DE にプッシュでメッセージを渡すため、書き込みの競合を避けるためにロックが必要になります。同時に、D と E はラベルを保存するために長さ 5 の可変長バッファを維持する必要があります。

上記の例から、送信されたメッセージを固定長メッセージに結合することはできず、メモリを大量に消費し、限られたリソース内で計算を効率的に完了できないことがわかります。

Platoの高性能実装

PlatoはCyclops[8]の論文の手法を借用して簡略化し、MPIの高性能通信プリミティブを使用して実装した。図 6 に示すように、ノード ABC は最初に状態 (ラベル値) をサーバー 1 に同期します。このプロセスでは、3 単位の通信が生成されますが、これは Dense モードでの通信よりも少なくなります。その後、ノード D と E は Pull メソッドを使用して周囲のすべてのノードのラベルにアクセスし、独自のラベル値を決定します。

上記の方法により、計算処理におけるメモリ消費量と通信オーバーヘッドを大幅に削減でき、メッセージを固定長データ型に結合できない LPA や HANP などのグラフアルゴリズム計算を限られたリソース内で迅速に完了できます。

プラトンアルゴリズムの例

上で述べた FastUnfolding、LPA、HANP などのコミュニティ発見アルゴリズムは、GitHub でオープンソース化されています。興味のある読者は、次のアドレスからアルゴリズムの紹介とソース コードを入手できます。

オープンソースアドレス: https://github.com/Tencent/plato

アルゴリズムの紹介: https://github.com/Tencent/plato/wiki

コード例: https://github.com/Tencent/plato/tree/master/example

要約する

テンセントの高性能分散グラフコンピューティングフレームワークPlatoは、Fast Unfolding、LPA、HANPなど、最も一般的に使用されているコミュニティ発見アルゴリズムの高性能実装を統合しています。超大規模ネットワークでのコミュニティ発見を数分で完了することができ、業界のグラフコンピューティングの技術進歩に貢献したいと考えています。

参考文献

MEJ Newman、M. Girvan。ネットワークにおけるコミュニティ構造の発見と評価[J]。Physical Review E、2004、69(2):026113。

VD Blondel、JL Guillaume、R. Lambiotter、他「大規模ネットワークにおけるコミュニティ階層の高速展開 [J]」。Journal of Statistical Machanics: Theory and Experiment、2008、10: 10008。

UN Raghavan、R. Albert、S. Kumara。大規模ネットワークにおけるコミュニティ構造を検出するためのほぼ線形時間アルゴリズム [J/OL]。Eprint arXiv、2007、0709:2938。[2012-6-18]。http://www.arXiv.org。

Ian XY Leung、Pan Hui、Pietro Li`o、他「大規模ネットワークにおけるリアルタイムコミュニティ検出に向けて [J/OL]」。Eprint arXiv、2009、0808:2633。[2019-12-18]。http://www.arXiv.org。

S. Fortunato. グラフにおけるコミュニティ検出 [J/OL]. Eprint arXiv. 2009,0906:0612. [2012-12-24]. http://www.arXiv.org.

McSherry, Frank、Michael Isard、および Derek G. Murray。「スケーラビリティ! しかし、{コスト} はいくらですか?」第 15 回オペレーティング システムのホット トピックに関するワークショップ (HotOS {XV})。2015 年。

Zhu, Xiaowei、他「Gemini: 計算中心の分散グラフ処理システム」第 12 回 {USENIX} オペレーティング システムの設計と実装に関するシンポジウム ({OSDI} 16)。2016 年。

Chen, Rong 他「分散不変ビューによる計算と通信の効率化グラフ処理」高性能並列分散コンピューティングに関する第 23 回国際シンポジウムの議事録。ACM、2014 年。