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

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

グラフはコンピューティング オブジェクトとしてますます重要になってきており、グラフ構造はグループ関係を抽象化したものであり、豊富なオブジェクトと関係を記述することができます。グラフ コンピューティングの核心は、データをグラフ構造にモデル化する方法と、問題の解をグラフ構造上の計算問題に変換する方法です。問題に相関分析が含まれる場合、グラフ コンピューティングは多くの場合、自然に問題の解を導き出すことができます。グラフ構造に対する一連の操作と計算として表現されます。例えば、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. 概要

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

[参考資料]

「人工知能のグラフコンピューティング」清華大学人工知能研究所、北京知源人工知能研究所、清華工程学院知識知能共同研究センター、 2019- 2

https://www.php.cn/link/c9e5c2b59d98488fe1070e744041ea0e

https://www.php .cn /link/d40d35b3063c11244fbf38e9b55074be

https://www.php.cn/link/315f006f691ef2e689125614ea22cc61

https://www.php.cn/link/51d1cd3a02276948f566e6ea0a7d78cb

以上がグラフコンピューティングについて学び、考えるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。