グラフ機械学習の紹介

グラフ機械学習（GraphML）は、項目が関係で結ばれた構造化データの分析を可能にし、グラフ、ノード、エッジ、サブグラフレベルでの予測を行うことができます。この分野は、医薬品探索や分子毒性予測から、ソーシャルネットワークのコミュニティ検出、旅程システムにおける交通推定まで、さまざまな応用にとって重要です。

基本的なグラフ概念

グラフは ノード（または頂点）と エッジ（またはリンク）で構成されます。データの性質に応じて、グラフは以下のような特性で分類されます：

均質 vs. 異質: 均質グラフは単一タイプのノードとエッジで構成されます。異質グラフは型付けされたノードやエッジを持ち（例：著者と論文の両方を含む引用ネットワーク）、表現にはトポロジー以外の追加情報が必要です。
有向 vs. 無向: 有向グラフ（例：フォロワーネットワーク）はエッジに特定の方向がありますが、無向グラフ（例：分子）は双方向の関係を持ちます。
表現: グラフは通常、エッジの集合として、または 隣接行列 として表されます。隣接行列は正方行列で、値が1である場合は二つのノード間に接続があることを示します。

重要なのは、グラフはシーケンス（テキスト/音声）やグリッド（画像）とは異なり、順序付けられたオブジェクトではないという点です。エッジリストや隣接行列の列をシャッフルしても基礎となるグラフは変わらず、これは 置換不変性 と呼ばれる性質です。

グラフ学習タスク

グラフ上の機械学習は、主に以下の4つの粒度レベルで適用されます：

グラフレベル: グラフ生成（例：医薬品探索）、グラフ進化予測（例：物理学）、およびグラフレベルの予測（例：分子毒性の予測）を含みます。
ノードレベル: ノード属性予測に焦点を当てます。例として、AlphaFold がノード属性を用いて分子中の原子の3次元座標を予測することがあります。
エッジレベル: エッジ属性予測（例：薬剤の副作用予測）や欠損エッジ予測（例：レコメンデーションシステム）を含みます。
サブグラフレベル: ソーシャルネットワークにおけるコミュニティ検出や、Googleマップのようなシステムでの到着時間推定のためのサブグラフ属性予測に焦点を当てます。

これらのタスクは、トランスダクティブ 設定（単一のグラフで訓練とテストを行う）または インダクティブ 設定（訓練、検証、テスト用に別々のグラフを使用）で実行されます。

グラフ表現の進化

ニューラル以前のアプローチ

ニューラルネットワークが登場する前は、グラフ表現は設計された特徴量に依存していました：

ノードレベルの特徴: 中心性（重要度）、次数（隣接ノード数）、クラスタ係数（隣接ノードの結びつき）です。
エッジレベルの特徴: ノード間の最短距離、共通隣接ノード、Katz指数（一定長さまでの歩行回数）です。
グラフレベルの特徴: 総グラフレット数や、"ノードのバッグ" アプローチによる類似度測定を行うカーネル手法です。

ウォークベースのアプローチ（例：Node2Vec）は、ランダムウォークを用いて類似度指標を定義し、skip-gramモデルで埋め込みを計算します。しかし、これらの手法は新しいノードの埋め込みを生成できず、細かな構造的類似性を捉えたり、追加のノード特徴を活用したりできません。

グラフニューラルネットワーク（GNN）

未見データに一般化するために、GNNは 置換不変（ノードの順序に関係なく出力が同じ）および 置換等価（ノードを置換すると表現も対応して置換される）になるよう設計されています。

GNNの層は メッセージパッシング と集約によって機能します。ノードの表現は、前層からの隣接ノードと自身の表現を集約することで更新されます。

代表的なGNNアーキテクチャには以下があります：

グラフ畳み込みネットワーク（GCN）: 隣接ノードの正規化された表現の平均を取ります。
グラフ注意ネットワーク（GAT）: 注意機構を用いて重要度に基づき隣接ノードに重み付けします。
GraphSAGE: 異なるホップで隣接ノードをサンプリングし、最大プーリングで情報を集約します。
グラフ同形性ネットワーク（GIN）: 隣接ノード表現の総和にMLPを適用します。

オーバースムージング問題

GNNに層を追加すると、各ノードの表現はより広い範囲から情報を集約します。層数がグラフの直径を超えると、ノード表現が同じ値に収束する オーバースムージング と呼ばれる現象が起こります。これを防ぐために、層の深さを制限したり、層の複雑さを高めたり、メッセージパッシング以外の層（例：MLP）を追加したり、スキップ接続を導入したりします。

グラフトランスフォーマー

トランスフォーマーは自然に置換不変であり、スケーラビリティが高いため、オーバースムージングや密なグラフへのスケーリングといったGNNの制限を克服するためにグラフへ適用されています。主な開発は以下です：

Graphormer: ノード特徴をクエリ/キー/バリューとして注意機構に使用し、中心性、空間、エッジエンコーディングを組み込みます。
TokenGT: グラフをノードとエッジの埋め込みのシーケンスとして表現し、識別子で拡張することで位置埋め込みが不要になります。
GraphGPS: メッセージパッシングネットワークと線形長距離トランスフォーマーを組み合わせたハイブリッドネットワークのフレームワークです。
スペクトル注意ネットワーク（SAN）: ノード特徴と、ラプラシアンの固有ベクトル/固有値から得られる学習位置エンコーディングを組み合わせます。

その他の注目すべき手法として、グラフからシーケンスへの学習用 Graph Encoder や GRPE（Graph Relative Positional Encoding）トランスフォーマーがあります。