グラフニューラルネットワーク（GNN）は、グラフ構造データを操作するために設計された人工ニューラルネットワークの一種であり、入力はノード（頂点）とエッジ（接続）から構成され、これらは正規の順序付けを欠く場合がある。固定サイズで順序付けられた入力を想定する標準的なニューラルネットワークとは異なり、GNNは様々なサイズとトポロジーのグラフを扱うように構築されており、分子化学、ソーシャルネットワーク分析、組合せ最適化などの領域に適している。GNNの核心的な革新は、ペアワイズメッセージパッシングの使用にあり、各ノードは隣接ノードからの情報を集約することで反復的に表現を更新し、ネットワークが局所的な構造パターンと依存関係を捕捉できるようにする。
GNNは通常、置換同変（permutation equivariant）になるように設計されており、入力グラフ内のノードを並べ替えると、ネットワークが生成するノード表現も対応して並べ替えられることを意味する。分子全体の特性を予測するなどのグラフレベルの予測タスクでは、GNNは置換不変の読み出し関数を採用し、ノード表現を単一の固定サイズの出力に集約して、結果がノード順序に影響されないことを保証する。この特性は、グラフに自然なノード順序がなく、ネットワークの出力がグラフの表現方法に関係なく一貫している必要があるため、不可欠である。
歴史的発展
GNNの概念は、構造化データのためのニューラルネットワークに関する初期の研究から生まれ、基礎的なアイデアは1990年代に遡る。有向非巡回グラフに適用された再帰型ニューラルネットワークなどの初期のアプローチは、グラフ状構造を処理するための基盤を築いた。しかし、メッセージパッシングと置換同変に基づくGNNの現代的な定式化は、深層学習の台頭とともに2010年代に顕著になった。MIT CSAILやスタンフォードAIラボなどの機関の研究者は、任意のグラフを処理できるアーキテクチャの開発に貢献し、GNNが機械学習内の明確なサブフィールドとして確立されるに至った。
2010年代後半までに、GNNは深層学習における標準的なツールとなり、その表現力とスケーラビリティを向上させるために多数の変種が提案された。2022年のポジションペーパー「Weisfeiler and Leman Go Neural」および類似の研究は、GNNとグラフ同型性テストの関係を形式化し、その理論的限界を明確にし、より強力なアーキテクチャの研究を促進した。
アーキテクチャ
一般的なGNNのアーキテクチャは、グラフ構造入力を処理するために連携して機能するいくつかの基本層を実装する。これらの層には、置換同変層、局所プーリング層、および大域プーリング層が含まれ、それぞれがグラフ表現の変換において異なる目的を果たす。
置換同変層はGNNの核心であり、グラフノード間のペアワイズメッセージパッシングを介して実装される。メッセージパッシング層では、各ノードが直接の隣接ノードから受信したメッセージを集約することで表現を更新する。このプロセスは、層ごとにGNNの受容野を1ホップずつ増加させ、ネットワークが徐々に大きな近傍からの情報を組み込むことを可能にする。メッセージパッシング操作は、ノード特徴、隣接特徴、およびエッジ特徴を入力として受け取り、更新されたノード表現を生成する関数として形式的に表現できる。
局所プーリング層は、ダウンサンプリングを介してグラフを粗くし、重要な構造情報を保持しながらノード数を削減する。これは畳み込みニューラルネットワーク（CNN）のプーリング層に類似しており、GNNの受容野を増加させるのに役立つ。一般的な例には、k近傍プーリング、トップkプーリング、および自己注意プーリングがあり、それぞれ異なる基準に基づいて保持するノードのサブセットを選択する。
大域プーリング層は、読み出し層とも呼ばれ、グラフ全体の固定サイズ表現を提供する。これらの層は置換不変でなければならず、グラフのノードとエッジの任意の置換が最終出力を変更しないことを意味する。要素ごとの和、平均、および最大操作は、大域プーリングの典型的な選択肢であり、ノード表現を単一のベクトルに集約して、グラフレベルの予測に使用できるようにする。
メッセージパッシング層
メッセージパッシング層はGNNの定義的な構成要素であり、メッセージパッシングニューラルネットワーク（MPNN）として知られるプロセスを通じて置換同変変換を実装する。ノード集合Vとエッジ集合Eを持つグラフG = (V, E)が与えられたとき、V内の各ノードuは関連する特徴x_uを持ち、E内の各エッジ(u, v)は特徴e_uvを持つ。ノードuの近傍N_uは、E内のエッジ(u, v)が存在するすべてのノードvで構成される。
MPNN層は、メッセージパッシング関数を使用して各ノードuの表現を更新する。層は各隣接ノードvからuへのメッセージを計算し、メッセージはソースノード特徴、ターゲットノード特徴、およびエッジ特徴の関数である。これらのメッセージは、和、平均、または最大などの置換不変操作を使用して集約され、その後、通常はニューラルネットワークである微分可能な更新関数を通じてノード自身の特徴と組み合わされる。このプロセスは複数の層で繰り返すことができ、情報がグラフ全体に伝播することを可能にする。
メッセージパッシング関数の設計は、GNNアーキテクチャによって異なる。単純な線形変換を使用するものもあれば、より複雑な注意メカニズムやゲート付きリカレントユニットを採用するものもある。集約操作の選択も、ネットワークの表現力と異なるタイプの構造情報を捕捉する能力に影響を与える。
表現力と限界
標準的なメッセージパッシングGNNは、最大でもWeisfeiler-Lehmanグラフ同型性テストと同じ表現力を持ち、これは2つのグラフが同型であるかどうかを決定する古典的なアルゴリズムである。これは、非同型グラフに対して同一の表現を生成する可能性があるため、標準的なGNNでは区別できない異なるグラフ構造が存在することを意味する。この限界は、メッセージパッシングの局所的な性質に起因し、直接の隣接ノードからの情報を集約することに依存しており、大域的な構造パターンを捕捉できない場合がある。
これらの限界を克服するために、研究者は、ペアワイズエッジを超えた高次相互作用をエンコードできる単体複体やハイパーグラフなどの高次元幾何学で動作する、より強力なGNNを提案している。2022年の時点で、将来のアーキテクチャがメッセージパッシングのプリミティブを完全に克服するかどうかは未解決の研究課題であり、グラフトランスフォーマーや同変ニューラルネットワークなどの代替パラダイムを探求する進行中の研究がある。
応用
GNNは、グラフ構造データを処理する能力を活用して、幅広い領域で応用されている。分子生物学と化学では、分子は原子をノード、化学結合をエッジとするグラフとして表現され、既知の化学的特性が特徴として含まれることが多い。グラフレベルのタスクには、大腸菌を除去するなどの特定の医療用途に対する分子の有効性の予測、または溶解度や毒性などの物理的・化学的特性の推定が含まれる。これにより、GNNは薬物設計や材料科学において貴重なツールとなっている。
自然言語処理では、GNNは構文依存木や意味役割グラフに適用でき、文内の単語間の関係を捕捉する。また、ソーシャルネットワーク分析では、ユーザー間の相互作用をモデル化し、コミュニティを検出し、リンクを予測するために使用される。ノードが論文を表し、エッジが引用を表す引用ネットワークも一般的な応用であり、論文分類や推薦などのタスクを可能にする。
GNNは物理学にも関連しており、粒子相互作用のモデル化や動的システムのシミュレーションに使用でき、NP困難な組合せ最適化問題では、グラフ彩色や巡回セールスマン問題などのタスクのヒューリスティックを学習できる。GNNの多様性は、学術研究と産業応用の両方での採用につながっている。
他のニューラルネットワークアーキテクチャとの関係
幾何学的深層学習のより広い文脈では、特定の既存のニューラルネットワークアーキテクチャは、適切に定義されたグラフ上で動作するGNNとして解釈できる。コンピュータビジョンで一般的に使用される畳み込みニューラルネットワーク（CNN）層は、ノードがピクセルであり、エッジが隣接するピクセルのみを接続するグラフに適用されるGNNと見なすことができる。この視点は、CNNとGNNの間の局所接続性と特徴集約の共有原則を強調する。
同様に、自然言語処理や大規模言語モデルで広く使用されるトランスフォーマー層は、ノードがテキストのパッセージ内の単語またはトークンである完全グラフに適用されるGNNと見なすことができる。この解釈では、トランスフォーマーの注意メカニズムはメッセージパッシングの一種として機能し、各トークンが他のすべてのトークンからの情報を集約する。この接続は、これらのアーキテクチャを統合し、GNNからの洞察を適用してトランスフォーマーベースのモデルを改善する研究を促進している。
ソフトウェアライブラリとツール
GNNの実装と展開を容易にするために、いくつかのオープンソースライブラリが開発されている。PyTorch Geometricは、PyTorchフレームワーク上に構築され、グラフデータ処理とメッセージパッシング層のための包括的なツールセットを提供する。TensorFlow GNNは、TensorFlowエコシステム内で同様の機能を提供する。Deep Graph Library（DGL）は、PyTorch、TensorFlow、Apache MXNetを含む複数のバックエンドをサポートするフレームワーク非依存のライブラリである。Google JAXのユーザーには、jraphがグラフニューラルネットワークのための軽量ライブラリを提供する。Juliaプログラミング言語では、GraphNeuralNetworks.jlとGeometricFlux.jlが、Flux機械学習フレームワーク上に構築されたGNN実装を提供する。
これらのライブラリは、研究者や実務者にとっての参入障壁を低くし、様々なGNNアーキテクチャの迅速なプロトタイピングと実験を可能にした。標準的なメッセージパッシング層、プーリング操作、およびグラフデータセットの読み込みと処理のためのユーティリティの実装が含まれており、GNNを幅広いユーザーにアクセス可能にしている。
将来の方向性
GNNに関する研究は進化し続けており、表現力の向上、大規模グラフへのスケーラビリティ、ノイズや不完全なデータへの堅牢性などの分野が活発に調査されている。注意メカニズムとグラフ構造を組み合わせたグラフトランスフォーマーの開発は、長距離依存関係を捕捉するための有望な方向性を表している。さらに、ノードとエッジが時間とともに変化する動的グラフや、複数のタイプのノードとエッジを持つ異種グラフへのGNNの適用への関心が高まっている。
2020年代初頭の時点で、GNNは機械学習ツールキットの標準的な構成要素となっており、学術機関と産業研究ラボからの継続的な貢献がある。その能力と限界の理論的理解は深まり続けており、ますます複雑なグラフベースの問題に取り組むことができる次世代アーキテクチャの設計を導いている。