グラフ機械学習の概要
グラフ機械学習の概要
このブログ投稿では、グラフ機械学習の基礎をカバーします。
まず、グラフの定義、使用目的、および最良の表現方法について学びます。次に、人々がグラフ上で学習する方法について簡単に説明し、ニューラルメソッド(グラフの特徴を同時に探索する)から一般的にグラフニューラルネットワークと呼ばれるものまでをカバーします。最後に、グラフのためのトランスフォーマーの世界を垣間見ます。
グラフ
グラフとは何ですか?
基本的に、グラフは関係でリンクされたアイテムの記述です。
グラフの例には、ソーシャルネットワーク(Twitter、Mastodon、論文と著者をリンクする引用ネットワークなど)、分子、知識グラフ(UML図、百科事典、ページ間のハイパーリンクを持つウェブサイトなど)、文を構文木として表現したもの、3Dメッシュなどがあります。したがって、グラフはどこにでも存在すると言っても過言ではありません。
グラフのアイテム(またはネットワーク)をノード(または頂点)と呼び、それらの接続をエッジ(またはリンク)と呼びます。たとえば、ソーシャルネットワークでは、ノードはユーザーであり、エッジはその接続です。分子では、ノードは原子であり、エッジは分子結合です。
- ノードまたはエッジに型が付いたグラフは異種と呼ばれます(例:論文または著者のいずれかとなるアイテムを持つ引用ネットワークには型付きノードがあり、関係に型が付いたXMLダイアグラムには型付きエッジがあります)。これは単にトポロジだけで表現することはできず、追加の情報が必要です。この投稿では同種のグラフに焦点を当てています。
- グラフはまた、有向(フォローネットワークのように、AがBをフォローしていることがBがAをフォローしていることを意味しない)または無向(分子のように、原子間の関係が両方の方向に進む)になります。エッジは異なるノードを接続することも、ノード自体に接続することもできますが、すべてのノードが接続される必要はありません。
データを使用する場合、最初に最適な特性(同種/異種、有向/無向など)を考慮する必要があります。
グラフはどのように使用されますか?
グラフで行う可能性のあるタスクの一覧を見てみましょう。
グラフレベルでは、主なタスクは次のとおりです:
- グラフ生成:新しい可能性のある分子を生成するために薬剤探索で使用されます
- グラフの進化(与えられたグラフが時間とともにどのように進化するかを予測する):物理学でシステムの進化を予測するために使用されます
- グラフレベルの予測(グラフからのカテゴリ化または回帰タスク):分子の毒性を予測するなど
ノードレベルでは、通常はノードの特性予測が行われます。たとえば、Alphafoldは、分子の全体的なグラフからノードの特性予測を使用して原子の3D座標を予測し、分子が3D空間でどのように折りたたまれるかを予測します。これは難しい生化学の問題です。
エッジレベルでは、エッジの特性予測または欠損エッジの予測が行われます。エッジの特性予測は、薬物の副作用予測に使用され、一対の薬物に対して副作用を予測します。欠損エッジの予測は、推薦システムで使用され、グラフ内の2つのノードが関連しているかどうかを予測します。
サブグラフレベルでは、コミュニティの検出やサブグラフの特性予測などが行われます。ソーシャルネットワークでは、コミュニティの検出を使用して人々がどのように接続されているかを判断します。サブグラフの特性予測は、旅程システム(Googleマップなど)で推定到着時間を予測するために使用されます。
これらのタスクに取り組む方法は2つあります。
特定のグラフの進化を予測する場合、すべて(トレーニング、検証、テスト)を同じ単一のグラフ上で行う転移学習の設定で作業します。この場合、単一のグラフからトレーニング/評価/テストデータセットを作成することは容易ではありませんので注意してください。ただし、異なるグラフ(別々のトレーニング/評価/テストデータセット)を使用して作業することもあります。これは帰納的な設定と呼ばれます。
グラフはどのように表現されますか?
グラフを処理および操作するための一般的な方法は次のいずれかです:
- すべてのエッジの集合として表現する(すべてのノードの集合と補完される場合もあります)
- または、すべてのノード間の隣接行列として表現する。隣接行列は、直接接続されているノードを示す正方行列(ノード数*ノード数の大きさ)であり、(n_i)と(n_j)が接続されている場合に(A_{ij} = 1)となり、そうでなければ0となります。注意:ほとんどのグラフは密に接続されていないため、疎な隣接行列を持ち、計算がより困難になる可能性があります。
しかし、これらの表現は見慣れているように思えますが、騙されないでください!
グラフは、通常のMLで使用されるオブジェクトとは非常に異なります。なぜなら、グラフのトポロジーは単なる「シーケンス」(テキストや音声など)や「順序付きグリッド」(例えば画像やビデオ)よりも複雑だからです。リストや行列で表現することができるかもしれませんが、その表現は順序付けられたオブジェクトとは考えられません!
しかし、これはどういう意味でしょうか?文をシャッフルして単語の順序を変えると、新しい文が作成されます。画像の列を並び替えると、新しい画像が作成されます。
しかし、グラフの場合は異なります。エッジリストや隣接行列の列をシャッフルしても、それはまだ同じグラフです。(詳細は後で形式的に説明します。順列不変性を探してください。)
MLを通じたグラフの表現
グラフを機械学習で扱うための通常のプロセスは、まず興味のあるアイテム(ノード、エッジ、またはフルグラフ)の意味のある表現を生成し、その後、これらを使用してターゲットタスクの予測モデルをトレーニングすることです。私たちは(他のモダリティと同様に)オブジェクトの数学的表現を制約することで、類似したオブジェクトが数学的に近いことを望んでいます。しかし、グラフMLではこの類似性を厳密に定義することは難しいです。例えば、ラベルが同じか、隣接するノードが同じかで、2つのノードはどちらがより類似しているのでしょうか?
注意:以下のセクションでは、ノードの表現の生成に焦点を当てます。ノードレベルの表現があれば、エッジやグラフレベルの情報を取得することも可能です。エッジレベルの情報では、ノードペアの表現を連結したり、ドット積を行ったりすることができます。グラフレベルの情報では、すべてのノードレベルの表現のテンソルをグローバルプーリング(平均、合計など)することができます。ただし、これによりグラフ全体の情報が滑らかになり、情報が失われます。再帰的な階層的プーリングはより意味があるかもしれません。または、グラフのすべての他のノードに接続された仮想ノードを追加し、その表現を全体のグラフ表現として使用することもできます。
ニューラル以前のアプローチ
エンジニアリングされた特徴の単純な使用
ニューラルネットワーク以前、グラフとその興味のあるアイテムは、タスクに応じた特徴の組み合わせとして表現することができました。現在でもこれらの特徴はデータ拡張や半教師あり学習で使用されますが、より複雑な特徴生成手法も存在します。タスクに応じて、これらをネットワークにどのように提供するかを見つけることは非常に重要です。
ノードレベルの特徴は、重要性(このノードがグラフにとってどれだけ重要か)や構造ベース(ノード周りのグラフの形状はどうですか?)についての情報を提供できます。これらは組み合わせることもできます。
ノードの中心性は、グラフ内でのノードの重要性を測定します。これは、各ノードの隣接ノードの中心性を収束するまで再帰的に合計するか、ノード間の最短距離によって計算することができます。ノードの次数は、直接の隣接ノードの数です。ノードのクラスタリング係数は、ノードの隣接ノードがどれだけつながっているかを測定します。 グラフレット次数ベクトルは、特定のノードをルートとする異なるグラフレットの数を数えます。グラフレットは、与えられた数の接続ノードで作成できるすべてのミニグラフです(3つの接続ノードで、2つのエッジを持つ直線または3つのエッジを持つ三角形など)。
エッジレベルの特徴は、ノードの接続性に関する詳細な情報を補完します。これには、2つのノード間の最短距離、共通の隣接ノード、およびKatz指数(2つのノード間の特定の長さまでの可能なウォークの数)が含まれます。Katz指数は、隣接行列から直接計算することができます。
グラフレベルの特徴には、グラフの類似性と特異性に関する高レベルの情報が含まれます。合計グラフレットカウントは、サブグラフの形状に関する情報を提供します。 カーネルメソッドは、グラフ間の類似性を異なる「ノードのバッグ」メソッドを通じて測定します(単語のバッグと似ています)。
ウォークベースのアプローチ
ウォークベースのアプローチでは、ランダムウォーク上でノードiからノードjを訪れる確率を使用して類似性メトリクスを定義します。これらのアプローチは、ローカル情報とグローバル情報の両方を組み合わせます。たとえば、Node2Vecは、グラフのノード間でランダムウォークをシミュレートし、それらのウォークをスキップグラムで処理します。これは、文の中の単語を処理するのと同様です。これらのアプローチは、PageRankメソッドの計算を高速化するためにも使用することができます。PageRankメソッドは、各ノードに重要度スコアを割り当てます(他のノードとの接続性に基づき、たとえばランダムウォークによる訪問頻度などで評価されます)。
ただし、これらの方法には制約があります:新しいノードの埋め込みを取得することができない、ノード間の構造的な類似性を細かく捉えることができない、追加の特徴を使用することができないという制約があります。
グラフニューラルネットワーク
ニューラルネットワークは未知のデータに一般化することができます。先ほど述べた表現の制約を考えると、グラフに適した良いニューラルネットワークはどのようなものでしょうか?
それは以下のような特徴を持つべきです:
- 順列不変であること:
- 方程式:f ( P ( G ) ) = f ( G ) f(P(G))=f(G) f ( P ( G ) ) = f ( G ) (fはネットワーク、Pは順列関数、Gはグラフ)
- 説明:グラフとその順列の表現は、ネットワークを通過した後も同じであるべきです
- 順列共変であること:
- 方程式:P ( f ( G ) ) = f ( P ( G ) ) P(f(G))=f(P(G)) P ( f ( G ) ) = f ( P ( G ) ) (fはネットワーク、Pは順列関数、Gはグラフ)
- 説明:ネットワークに渡す前にノードを順列することは、それらの表現を順列することと等価であるべきです
典型的なニューラルネットワーク、例えばRNNやCNNは順列不変ではありません。そのため、新たなアーキテクチャであるグラフニューラルネットワークが導入されました(最初は状態ベースのマシンとして)。
GNNは連続した層で構成されています。GNNの層は、前の層の隣接ノードと自身の表現の組み合わせ(集約)をノードの表現として表します(メッセージパッシング)。通常、非線形性を追加するために活性化関数も使用されます。
他のモデルとの比較:CNNは、固定された隣接サイズ(スライディングウィンドウを介して)と順序(順列共変ではありません)を持つGNNと見なすことができます。位置エンベディングのないTransformerは、完全に接続された入力グラフ上のGNNと見なすことができます。
集約とメッセージパッシング
隣接ノードからメッセージを集約する方法は多くあります。例えば、合計、平均などです。このアイデアに基づくいくつかの注目すべき研究は以下のとおりです:
- Graph Convolutional Networksは、ノードの正規化された表現の隣接ノードの平均値を集約します(ほとんどのGNNは実際にはGCNです)。
- Graph Attention Networksは、重要度に基づいて異なる隣接ノードに重みを付けることを学習します(トランスフォーマーのようなものです)。
- GraphSAGEは、最大プーリングを使用して複数のステップで異なるホップの隣接ノードをサンプリングし、その情報を集約します。
- Graph Isomorphism Networksは、隣接ノードのノード表現の和にMLPを適用して表現を集約します。
集約の選択:一部の集約手法(特に平均/最大プーリング)は、似たようなノードの異なる近隣の微妙な違いを細かく区別する表現を作成する際に失敗することがあります(例:平均プーリングを介して表される4つのノードからなる近隣は、1, 1, -1, -1と表され、平均値は0になり、-1, 0, 1と表される3つのノードからなる近隣とは異なりません)。
GNNの形状と過剰平滑化の問題
各新しい層ごとに、ノードの表現にはますます多くのノードが含まれます。
ノードは、最初の層を通じてはその直接の隣接ノードの集約です。2番目の層を通じても、それはまだ直接の隣接ノードの集約ですが、この場合は彼らの表現には彼ら自身の隣接ノード(1番目の層から)も含まれます。n層後、すべてのノードの表現は距離nの全ての隣接ノードの集約、すなわち、グラフ全体(グラフの直径がn未満の場合)の集約となります。
ネットワークに層が多すぎると、各ノードが全体のグラフの集約となり(ノードの表現がすべてのノードに対して同じものに収束する)、これを過剰平滑化の問題と呼びます
これは以下の方法で解決できます:
- GNNのスケーリングを行い、ネットワーク全体を各ノードが近似しないようにするために、層の数を小さくする(グラフの直径と形状を最初に分析することで行う)
- 層の複雑さを増す
- メッセージを処理するための非メッセージパッシング層を追加する(例:単純なMLP)
- スキップ接続を追加する
過剰平滑化の問題は、グラフMLの重要な研究分野であり、これによってGNNが他のモダリティでトランスフォーマーのようにスケーリングできなくなる可能性があります。
グラフトランスフォーマー
位置エンコーディングレイヤーを持たないトランスフォーマーは順列不変であり、トランスフォーマーはスケーリングがうまくいくことが知られているため、最近では、トランスフォーマーをグラフに適応させることに関心が向けられています(サーベイ)。ほとんどの手法は、グラフの最良の表現方法、位置情報の最良の表現方法、およびこれらの新しいデータに合わせて注意を変更するための最良の方法を探索することに焦点を当てています。
以下は、最新の研究結果またはStanfordのOpen Graph Benchmarkとして利用可能なベンチマークの中でも最も困難なもののいずれかで、最先端の結果または近い結果を示したいくつかの興味深い手法です:
- グラフ・トランスフォーマーによるグラフからシーケンスへの学習(Cai and Lam, 2020)では、ノードを埋め込みと位置埋め込みの連結として表現し、ノード間の最短パスをノード関係として表現し、関係を増強した自己注意に組み合わせるグラフエンコーダを導入しています。
- スペクトル注意を使用したグラフトランスフォーマーの再考(Kreuzer et al, 2021)では、スペクトル注意ネットワーク(SANs)を導入しています。これにより、ノードの特徴とラプラシアン固有ベクトル/値から計算された学習可能な位置エンコーディングを組み合わせて、注意のキーとクエリとして使用し、注意値はエッジの特徴です。
- グラフトランスフォーマーのための相対位置エンコーディング(Park et al, 2021)では、グラフ相対位置エンコーディングトランスフォーマーを導入しています。グラフレベルの位置エンコーディングとノード情報、エッジレベルの位置エンコーディングとノード情報を組み合わせ、注意機構で組み合わせます。
- グラフ畳み込みの代替としてのグローバル自己注意(Hussain et al, 2021)では、エッジ増強トランスフォーマーを導入しています。このアーキテクチャは、ノードとエッジを別々に埋め込み、変更された注意でそれらを集約します。
- トランスフォーマーは本当にグラフ表現に対して悪いパフォーマンスをするのか(Ying et al, 2021)では、MicrosoftのGraphormerを紹介しています。これは、ノードの特徴を注意のクエリ/キー/値として使用し、中心性、空間性、エッジエンコーディングの組み合わせとともにその表現を合計します。
最も最近のアプローチは、純粋なトランスフォーマーは強力なグラフ学習者である(Kim et al, 2022)で、TokenGTを導入しています。この手法では、入力グラフをノードとエッジの埋め込みのシーケンス(直交ノード識別子と訓練可能なタイプ識別子で拡張)として表現し、位置埋め込みを持たずにこのシーケンスをトランスフォーマーに入力します。非常にシンプルでありながら、賢い方法です!
少し異なるアプローチとして、一般的で強力なスケーラブルなグラフトランスフォーマーのためのレシピ(Rampášek et al, 2022)では、モデルではなくGraphGPSと呼ばれるフレームワークを紹介しています。このフレームワークは、メッセージパッシングネットワークと線形(長距離)トランスフォーマーを組み合わせてハイブリッドネットワークを簡単に作成することができます。このフレームワークには、ノード、グラフ、エッジレベルの位置エンコーディング、特徴拡張、ランダムウォークなどを計算するためのいくつかのツールも含まれています。
グラフに対するトランスフォーマーの使用はまだ非常に初期の段階ですが、GNNのいくつかの制限(より大きな/より密なグラフへのスケーリング、過度な平滑化なしでモデルサイズの拡大など)を緩和する可能性があるため、有望です。
さらに掘り下げたい場合は、次のいくつかのコースを参照してください:
- アカデミック形式
- Stanfordのグラフを用いた機械学習
- McGillのグラフ表現学習
- ビデオ形式
- 幾何学的深層学習コース
- 書籍
- グラフ表現学習、Hamilton
- サーベイ
- グラフニューラルネットワークの学習ガイド
- 研究方向
- 2023年のGraphMLに関するまとめは、2023年のGraphMLの興味深い方向をまとめたものです。
グラフで作業するための便利なライブラリとしては、PyGeometricやDeep Graph Library(グラフML用)およびNetworkX(一般的なグラフ操作)があります。
品質のベンチマークが必要な場合は、次のリソースをチェックしてみてください:
- Open Graph Benchmark(OGB):さまざまなタスクとデータスケールの参照グラフベンチマークデータセット。
- GNNのベンチマーク:グラフMLネットワークとその表現能力をベンチマークするためのライブラリとデータセット。関連する論文では、統計的な観点からどのデータセットが関連性があり、どのグラフの特性を評価できるか、どのデータセットはもはやベンチマークとして使用すべきではないかについて研究しています。
- Long Range Graph Benchmark:最新の(2022年11月)の長距離グラフ情報を調査するベンチマーク。
- Graph Representation Learningのベンチマークのタクソノミー:2022年のLearning on Graphs会議で発表された論文で、既存のベンチマークデータセットを分析・整理しています。
他のデータセットについては、以下を参照してください:
- Paper with code Graph tasks Leaderboards:公開データセットとベンチマークのリーダーボード – 注意:このリーダーボードのすべてのベンチマークがまだ関連しているわけではありません
- TUデータセット:公開データセットのコンパイル、現在はカテゴリと特徴によって整理されています。これらのデータセットのほとんどはPyGで読み込むこともでき、いくつかはDatasetsに移植されています
- SNAPデータセット:Stanford大規模ネットワークデータセットコレクション:
- MoleculeNetデータセット
- 関係データセットリポジトリ
外部画像の帰属
サムネイルの絵文字はOpenmoji(CC-BY-SA 4.0)から提供されています。グラフレットの図は、Biological network comparison using graphlet degree distribution (Pržulj, 2007)から取得されています。
We will continue to update VoAGI; if you have any questions or suggestions, please contact us!
Was this article helpful?
93 out of 132 found this helpful
Related articles