グラフコンピューティングについて学び、考える-AI-php.cn

優れたソフトウェアは、プログラム分析やエラー検出によって発見されるのではなく、適切な人材によって構築されます。

グラフはコンピューティングオブジェクトとしてますます重要になってきており、グラフ構造はグループ関係を抽象化したものであり、豊富なオブジェクトと関係を記述することができます。グラフコンピューティングの核心は、データをグラフ構造にモデル化する方法と、問題の解をグラフ構造上の計算問題に変換する方法です。問題に相関分析が含まれる場合、グラフコンピューティングは多くの場合、自然に問題の解を導き出すことができます。グラフ構造に対する一連の操作と計算として表現されます。例えば、Web ページのリンクのグラフ構造に基づく PageRank アルゴリズムは、検索エンジンのランキングの参考となる Web ページの重みを取得するために使用され、グラフ構造のユーザー行動データは、正確な重みを取得するために使用されます。グループの好みの分析とパーソナライズされた製品の推奨結果。

1. グラフコンピューティングとは何ですか?

グラフコンピューティングは、人間世界の物事と物事間の関係を研究し、それらを記述、描写、分析、計算する技術です。ここでのグラフは「グラフ」であり、数学のグラフ理論に由来するグラフ「画像」ではありません。

グラフは最も柔軟な接続方法であり、エンティティを制限なく接続できます。グラフコンピューティングは単なるテクノロジーではなく、世界を理解する方法です。グラフデータは、接続の方向や属性の記述など、物事間の接続を適切に記述することができます。データ構造の観点から見ると、グラフは物事間の関係をネイティブに表現したものです。ある程度、リレーショナルデータベースはテーブルデータベースと呼ばれる必要があり、グラフデータベースはリレーショナルデータベースと呼ばれる必要があります。広義のグラフコンピューティングとは、グラフデータベースを含むグラフデータに基づく様々な処理を指します。

グラフコンピューティングテクノロジは、従来のコンピューティングモードにおける関連クエリの低効率と高コストの問題を解決します。問題領域内の関係を完全に描写し、豊富で効率的かつ機敏なデータ分析機能を備えています。その特徴は次のとおりです。

グラフ抽象化に基づくデータモデル
グラフデータモデルの並列抽象化
グラフモデルシステムの最適化

グラフの場合コンピューティング、パフォーマンスコスト、フォールトトレランスメカニズム、およびスケーラビリティはすべて非常に重要です。

2. 歴史的発展の観点からグラフコンピューティングを考察する

グラフコンピューティングは 1960 年代のツリー構造データベースにまで遡ることができ、属性グラフ指向のモデルとテクノロジは 1960 年代に登場しました。 1970年代～1980年代 LDM（論理データモデル）など2007 年までに、最初の商用グラフデータベース Neo4j が確立され、グラフコンピューティングが発展段階に入ったことを示しました。

グラフコンピューティング研究の本当の始まりは、Google がビッグデータの並列処理のためのコンピューティングモデルである MapReduce を開発した 2004 年でした。このモデルの発表は、ビッグデータの並列処理に大きな革命的な影響をもたらしました。その後、2006 年に、Apache Hadoop チームは Hadoop 分散ファイルシステム (HDFS) と新しい Hadoop MapReduce フレームワークを導入しました。 2009 年、カリフォルニア大学バークレー校の AMP 研究室は Spark システムを開発しました。

2010 年以降、大規模分散アーキテクチャ、マルチモーダルサポート、グラフクエリ言語設計などのグラフコンピューティングの研究方向が徐々に注目を集めています。 Google は、BSP コンピューティングモデルに従って、グラフアルゴリズムの特性に合わせて設計された分散グラフコンピューティングシステムである Pregel を提案し、その後 CMU Select Laboratory GraphLab プロジェクトチームが GAS コンピューティングモデルを提案しました。。 pregel と GraphLab はどちらも複雑な機械学習計算用の処理フレームワークであり、反復計算に使用されますが、その実装方法は異なります。Pregel はラージブロックメッセージパッシングメカニズムに基づいており、GraphLab はメモリ共有メカニズムに基づいています。その後の他のグラフコンピューティングシステムの設計に大きな影響を与えます。

Google は 2012 年 5 月に、情報を接続する新しい方法であるナレッジグラフの概念を提案しました。その基本単位は「エンティティ - 関係 - エンティティ」の 3 つ組であり、エンティティは関係を通じて接続され、相互に接続されて形成されます。ネットワーク化された知識構造。ナレッジグラフの確立の中核はコンピュータの知識推論メカニズムであり、グラフコンピューティングはそれに対する重要な基礎的な技術サポートを提供します。

2015 年、データ量の急速な増加に伴い、アプリケーション市場が徐々に開放され、グラフコンピューティングシステムの拡張性と効率性に対する需要が高まり続けました。中国におけるグラフコンピューティング分野の学術および産業研究は、清華大学の Gemini など、独自のグラフコンピューティングシステムとプラットフォームを徐々に開発し始めています。

近年、人工知能技術の発展に伴い、グラフニューラルネットワークも業界でその才能を発揮しています。

3. フレームワークモデルからグラフコンピューティングを考察する

グラフコンピューティングフレームワークは、基本的に BSP (Bulk Synchronous Parallell) コンピューティングモデルに従います。 BSP モードのバルク同期メカニズムのユニークな機能は、スーパーステップ概念の導入にあります。計算プロセスは一連のグローバルスーパーステップで構成され、各スーパーステップには並列計算 (ローカル計算)、グローバル通信 (非ローカルデータ通信)、フェンス同期 (通信動作の終了待ち) の 3 つのステージが含まれます。

BSP モードには次の特徴があります:

計算を 1 つずつスーパーステップに分割し、デッドロックを効果的に回避します;

プロセッサとルーターを分離し、コンピューティングタスクの分離を強調します。ルータはポイントツーポイントのメッセージ配信のみを完了し、アセンブリ、複製、ブロードキャストなどの機能は提供しませんが、特定の相互接続ネットワークトポロジを隠すだけでなく、通信プロトコルを簡素化します。

同期モードを採用して、ハードウェアにグローバル同期と制御可能な粗粒レベルを実装し、密結合された同期並列アルゴリズムを実行します。

グラフコンピューティングについて学び、考える

いくつかの代表的なグラフコンピューティングフレームワークは次のとおりです。

Neo4j-APOC: グラフデータベースに基づいて、いくつかの基本的なグラフアルゴリズムをサポートします。配布バージョンはオープンソースではありません。
Pregel: Google が 2009 年に提案したグラフコンピューティングモデルの創始者であり、その後の多くの作品がそのアイデアの影響を受けてきました。オープンソースではありません。
Giraph: Pregel のアイデアに基づいた Facebook のオープンソース実装。
ジェミニ: 清華大学は、Pregel のアイデアに基づいて多くの改善を実施し、優れたパフォーマンスを実現しました。無料のデモのみが提供されており、商用バージョンはオープンソースではありません。
KnightKing: ウォーカー歩行アルゴリズム用に特別に設計されたグラフコンピューティングフレームワークですが、汎用ではありません。
GraphX: Spark に基づいて Apache Foundation によって実装されたグラフコンピューティングフレームワークで、コミュニティ活動が活発です。
GraphLab (PowerGraph): オープンソースではなく商用ソフトウェアです。 Appleに買収されました。
Plato: Gemini と KnightKing のアイデアに基づいた Tencent の C オープンソース実装で、高性能、スケーラブル、接続が簡単なグラフコンピューティングフレームワークです。

4. アルゴリズムの観点からグラフ計算を見てみる

グラフアルゴリズムとは、無向グラフや有向グラフなど、特定の頂点と辺を使用して答えを見つける単純な方法を指します。およびネットワーク一般的に使用される多くのグラフアルゴリズムを使用できます。グラフデータの場合、トラバーサルアルゴリズム (深さ/幅を優先) が他のアルゴリズムの基礎となります。一般的なグラフアルゴリズムには、PageRank、最短パス、接続されたブランチ、最大独立セット、最小スパニングツリー、およびベイジアン信念伝播が含まれます。グラフの最小スパニングツリーは、生涯の最低コストまたは最小コストを表すことが多く、プリムのアルゴリズムとクラスカルのアルゴリズムがよく使用されます。コミュニティ発見、最短パス、トポロジカルソート、クリティカルパスにも対応するアルゴリズムがあります。

グラフアルゴリズムには、検索、照合、分類、評価などの多様なデータ解析技術が含まれますが、アルゴリズムの構造次元から、走査中心のアルゴリズムと計算中心のアルゴリズムの2つに大別されます。トラバーサル中心のアルゴリズムでは、特定の頂点から特定の方法でグラフをトラバースする必要があり、大量のランダムアクセスが発生します。計算中心のアルゴリズムは、反復サイクルで多数の演算を必要とし、データの局所性が比較的良好です。

グラフコンピューティングについて学び、考える

#5. コンピュータアーキテクチャの観点からグラフコンピューティングを考察する

グラフコンピューティングは一般にデータ駆動型の計算であり、コンピューティングの構造を正確に表現することはできません。は実行前に予測されるため、フォームに明確なパターンがなく、効率的かつ高品質に分割することが困難です。既存のキャッシュメカニズムでは、多くの場合、局所性を高めてデータアクセスを高速化することしかできず、大量のデータにアクセスすると、プロセッサが I/O 待ちの状態になることがよくあります。

グラフコンピューティングの負荷は複雑であり、最も代表的なグラフコンピューティングの負荷は 1 つもありません。頂点を接続するエッジは、無数の可能な接続のほんの一部にすぎず、非常に不規則です。グラフコンピューティングのプロセスでは、読み取りと書き込みの時空間的な局所性を把握することが難しく、帯域幅の占有率を予測することが困難です。

ほとんどのアルゴリズムは、メモリ帯域幅の 50% 未満しか占有しない可能性があります。メモリ帯域幅の使用を制限するものは何ですか?プロセッサは命令を取得する必要があり、命令ウィンドウの間にはスペースがあり、レジスタオペランドはオペランドが使用可能になるまで待機する必要があり、関連する依存関係は解放されません。命令ヒット率が高いため、メモリレベルでの並列処理が低下する可能性があり、プラットフォームのメモリ帯域幅を最大限に活用することが困難になります。キャッシュデータの使用率が低いということは、アプリケーションが空間的局所性の恩恵を受けることが難しく、データのプリフェッチ戦略が効果的でないことを意味します。データのプリフェッチは一般にパフォーマンスの向上に役立ちますが、無駄なプリフェッチ操作が大量に生成されることもあります。メモリ帯域幅またはキャッシュ容量が限られているアプリケーションの場合、データのプリフェッチによってリソースがある程度無駄になる可能性があります。マルチスレッドコンピューティングの場合、より高いレイテンシでリモートメモリアクセスをトリガーすると、マルチスレッドの利点が相殺されます。

グラフコンピューティングにはどのようなプロセッサコアが必要ですか?一般に、多数の小さな計算コアと多数のスレッドを備えたアーキテクチャが使用され、従来のマルチコアプロセッサが苦手とする大規模なグラフ計算の処理に適しています。複数のグラフの同時計算には、共有割り当てと排他的割り当ての 2 つの戦略があります。共有割り当て戦略は、m 個のリクエストのそれぞれが n 個の論理コアを使用して並列処理され、OS が論理コア上の異なるリクエストの切り替えを管理することを意味します。排他的割り当て戦略とは、論理コアがタスク間で切り替える必要がないように、各リクエストに n/m 個の論理コアを割り当てることを指します。排他的割り当て戦略は、グラフの同時計算に適しており、通常、排他的により、同じ同時リクエストの全体的な実行時間を短縮できます。リオーダキャッシュの競合が少ないことが、同時グラフコンピューティングシナリオで共有戦略よりも排他戦略の方が優れている理由である可能性があります。

グラフ計算により発生する消費電力に関しては、負荷変動によりシステム電力が変動し、山谷の時差が発生します。同時タスクが増加すると、ピーク対トラフの比率が変化し、消費電力が増加します。一般に、CPU 消費電力の点では、計算中心のアルゴリズムは命令ごとに平均して大量のエネルギーを消費しますが、トラバーサル中心のアルゴリズムは逆の効果があり、メモリ消費電力の点では、計算中心のアルゴリズムの方がメモリ消費量が少なくなります。平均エネルギー消費量は小さく、トラバーサル中心のアルゴリズムではその逆が当てはまります。

グラフコンピューティングベースのアプリケーションのほとんどはメモリに制限がありますが、コアコンポーネントの制限によってメモリ使用率が不十分になることもあります。十分なアクティブなスレッドにより同時アクセスが作成され、使用率が向上する可能性があります。より多くのスレッドが必要ですが、スレッド間の不均衡により、効率的に使用されない可能性があります。マルチコアプロセッサの高帯域幅メモリ使用量を最適化するには、よりスケーラブルな並列戦略を提供する必要があります。消費電力とエネルギー消費の動作は、命令の観点と頂点計算の観点では異なるため、正確な電力管理方法が必要であり、大幅な調整は効果的ではない可能性があります。

6. システムからグラフ計算を表示

大規模グラフコンピューティングシステムの使用シナリオとコンピューティングプラットフォームアーキテクチャの違いに基づいて、それらは単一マシンのメモリグラフに分類できます。コンピューティングシステムおよび単一マシン外部メモリグラフコンピューティングシステムコンピューティングシステム、分散メモリグラフコンピューティングシステム、および分散外部メモリグラフコンピューティングシステム。

グラフコンピューティングについて学び、考える

#単一マシンメモリグラフ処理システムは、単一マシン環境で実行され、すべてのグラフデータをメモリにバッファリングするグラフ処理システムです。スタンドアロン外部メモリグラフ処理システムは、グラフ処理システムがスタンドアロン環境で実行され、グラフデータの計算を通じてメモリおよびディスクと継続的に対話する効率的なグラフアルゴリズムです。分散メモリシステムは、分散クラスタ環境で動作するグラフ処理システムであり、すべてのグラフデータはメモリにロードされます。分散型外部メモリグラフコンピューティングシステムは、単一マシンのアウトオブコアシステムをクラスタに拡張し、数兆のオーダーのエッジを持つグラフを処理できます。

7. AI からグラフコンピューティングを見つめる

AI とグラフコンピューティングの融合によって生成されるグラフニューラルネットワーク (GNN) は、現在急速に発展しつつある重要な分野です。さまざまなエンティティ間の関係データをニューラルネットワークと組み合わせるにはどうすればよいでしょうか?グラフニューラルネットワークは表現学習を使用しており、グラフの構造を通じて、各ノードまたはエッジはまずベクトルで表され、次にニューラルネットワークを使用してさらに処理されます。これにより、ニューラルネットワークの使用範囲が拡大し、エンティティ間の関係が AI 処理に導入されます。

グラフニューラルネットワークは、ノードの代表的な特徴やグラフレベルの代表的な特徴など、グラフの特徴の学習プロセスとみなすことができます。一般に、グラフのプロパティとグラフの構造を入力として受け取ります。そして更新されたノードのセットを出力します。一般に、このプロセスはグラフフィルタリング操作とも呼ばれます。グラフのフィルタリングはノードの機能を更新しますが、グラフの構造は変更しません。グラフニューラルネットワークの開発はさまざまな理論的動機から開発されています。たとえば、GNN が非ユークリッド距離の畳み込み一般化とみなされる場合、グラフ信号に基づいて開発されますが、現在、ほとんどの GNN はニューラルメッセージパッシング手法に基づいています。グラフィカルモデルにおける確率論的推論との類似を通じて提案された通過アルゴリズム。

スペクトル手法であれ、空間ベースのアイデアであれ、グラフニューラルネットワークは最終的にメッセージパッシングに基づくフレームワークに統合できます。 GNN メッセージパッシングフレームワークの基本的な考え方は、反復ごとに各ノードが近隣ノードの情報を集約するというものです。反復回数が増加するにつれて、各ノードにはグラフ上のより広範囲の情報が含まれます。たとえば、k 回の反復の後、中央ノードはその k ホップの隣接ノードに関する情報を取得できます。重要なアイデアは、グラフ構造と既知の特徴情報に基づいてノード表現を生成することです。 GNN は、グラフ上の構造とノードの特徴情報を使用して深い埋め込み表現を生成しますが、従来のグラフ埋め込み手法は、グラフの構造情報のみを使用して、テーブルルックアップを通じてレイヤーの埋め込みを生成します。

7.1 GNN VS MLP/CNN/RNN

グラフデータ内のノードの隣接ノードには 2 つの特性があります。1 つは不定の数であり、もう 1 つは順序が不確実であるためです。 MLP/CNN/RNN は、このような非ユークリッドデータを直接処理することはできず、GNN でのみモデル化できます。実際、GNN はより一般的なモデルとみなすことができます。たとえば、RNN は線形グラフ上の GNN と同等であり、Transformer は完全なグラフ上の GNN と同等です。

7.2 GNN VS グラフ埋め込み

GNN よりも前に多くのグラフ埋め込み手法が登場し、検索サービスのベクトル呼び出しフェーズで広く使用されています。 Word2vec による、オリジナルの Item2Vec から、均一性と構造のバランスの改善に基づく Node2Vec、グラフの不均一性の改善に基づく MetaPath2Vec、および行動データの希薄性を軽減するための属性データの導入に至るまで、これらのメソッドはすべてを備えています。スキップグラムパラダイムに従います。

これらの方法と比較すると、GNN はターゲットタスクと組み合わせてエンドツーエンドでトレーニングできますが、グラフエンベディングは事前トレーニングに近く、学習するエンベディングは必ずしもターゲットタスクに関連しているわけではありません。特にサンプルサイズにおいて、大規模なビジネスシナリオでは、エンドツーエンドトレーニングで取得したエンベディングは、事前トレーニングで取得したエンベディングよりも効果的です。

GNN の階層ネットワーク構造は、GCN Attentinotallow=GAT などの他の深層学習テクノロジと簡単に組み合わせることができます。 GNN は帰納的タスクに適用できます。つまり、グラフの構造が変更され、いくつかの新しいノードが追加された場合、グラフ埋め込みメソッドの場合はモデルを再トレーニングする必要があり、GNN は GraphSage Node と同様のメソッドを使用できます。すでにトレーニングされたモデルを使用したワイズサンプリングは、新しいノードを直接推論し、メッセージパッシングプロセスでさまざまな機能を使用できます。

7.3 GNN VS 特徴連結、協調フィルタリング、近接損失

特徴連結とは、特徴を結合し、特徴交差を通じて一次属性関連情報を学習することを意味します。協調フィルタリングは、ユーザーの履歴行動を通じて一次行動相関情報を学習することもできます。近接損失とは、隣接するノードをより類似させるために損失関数に規則的な項を追加することを意味しますが、一方ではそれは暗黙的な方法であり、他方では高次の類似関係を確実に学習したい場合は、以下を追加する必要があります。さらに複雑 K 次の正規項は、GCN が提案されたときの出発点の 1 つでもあります。これら3つの手法に比べ、GNNは複数の層を重ねることで高次の相関情報を明示的に学習することができます。

グラフニューラルネットワークの設計では、順列不変性または順列等変性という重要な条件を満たす必要があります。つまり、設計された関数はノードの順序や入力の順序に影響されません。グラフデータを処理する場合、変換ドメインの出力は同じ順序になります。

8. 概要

グラフは最も柔軟な接続方法であり、エンティティを制限なく接続できます。グラフコンピューティングは、大量のデータの中からグラフデータを効率的に計算・保存・管理する方法を研究する分野で、資本市場のリスク管理、ライフサイエンス研究、医療提供、モニタリングなど幅広いビジネスシーンに応用できます。交通事故への対応、インテリジェントなインフラ管理など大規模データを効率的に処理するグラフコンピューティングは、ソーシャルネットワーク分析、セマンティックウェブ分析、生体情報ネットワーク分析、自然言語処理などの新たな応用分野の発展を促進します。