MLエンジニアへの道 #31 - グラフ機械学習

MLDLGL

Last Edited: 12/19/2024

このブログ記事では、グラフ機械学習について紹介します。

ML

これまで、表形式データ、言語、画像に対する機械学習および深層学習手法についてのみ議論してきました。 しかし、化学構造、交通網、ソーシャルネットワークなど、現実世界の多くのデータは、ノード(または頂点) とそれらを接続するエッジ(または辺)で構成されたグラフとして本質的に表現されています。 (実際、言語や画像も、線形グラフや2次元グリッドグラフとして表現でき、これらは制約を持つ特殊なグラフの一種です。) したがって、グラフ上でさまざまなタスクを実行するための機械学習アルゴリズムの研究には大きな意義があります。 今回の記事では、グラフを学習する上で生じる難点や要件について議論します。

注: 本記事の内容は、Velickovic, P.（2021年）による動画 Theoretical Foundations of Graph Neural Networks を元にしたものです。ぜひチェックしてみてください。

順列不変性と順列同変性

グラフは興味深い研究対象ですが、扱う際にはいくつかの困難があります。 その1つは、頂点に順序が存在しないことです。この点を理解するために、 辺がなく、頂点が1, 2, 3, 4とラベル付けされたグラフを想像してみましょう。 ここで、頂点を1→2→3→4や2→4→1→3、4→3→1→2のように表現でき、 同じnn個の頂点セットを表現する順列がn!n!通りあることに気づきます。 これを便利に表現するために、頂点の順序を変換するだけの順列行列PPを使用できます。 順列行列の各行および列には、1が1つだけ含まれ、それ以外はすべて0です。

P(2,3,1,4)X=[0100001010000001][−x1−−x2−−x3−−x4−]=[−x2−−x3−−x1−−x4−] P_{(2,3,1,4)}X = \begin{bmatrix} 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1\\ \end{bmatrix} \begin{bmatrix} - x_1 -\\ - x_2 -\\ - x_3 -\\ - x_4 -\\ \end{bmatrix} = \begin{bmatrix} - x_2 -\\ - x_3 -\\ - x_1 -\\ - x_4 -\\ \end{bmatrix}

すべてのPPに対して、モデルは同じ出力を生成する必要があります。 これを実現する方法の1つは、順序に依存しないFFを使用すること、 つまり順列不変性(permutation invariance) を持つFFを使用することです。 これを以下のように表現できます：

F(PX)=F(X) F(PX) = F(X)

順列不変性を持つ関数の例として、合計（sum）、平均（average）、最大値（max）、 最小値（min）などの集約関数があります。これらは、頂点がどの順序で 与えられても同じ集約された出力を生成します。 しかし、グラフを集約せず、順序を保持したままで同じ出力を生成したい場合もあります。 そのような関数は順列同変性(permutation equivariance) を持つと言い、 以下のように表現できます：

F(PX)=PF(X) F(PX) = PF(X)

順列同変性を持つ関数は、各頂点に対して個別に操作される任意の関数です。 順序が仮定されていないグラフを処理するには、関数は順列不変性、順列同変性、 またはこれらを組み合わせた操作である必要があります。2つを組み合わせる場合、 順列同変操作を最初に行う必要があります。順列不変操作は集約関数であり、 順列を破壊するためです。これにより、以下のような式が得られます：

F(X)=ϕ(⨁i∈Vψ(xi)) F(X) = \phi ( \bigoplus_{i \in V}\psi(x_i) )

ψ\psi関数は各頂点に適用される任意の関数、⨁\bigoplusは集約子、 ϕ\phiは集約された出力に適用される別の任意の関数です。 上記の式は、パラメータ関数の選択やXX内の頂点の順序に関係なく、 同じ出力を生成することができます。

グラフの局所性

エッジのないグラフは単なる集合に過ぎません。集合における順列不変性と順列同変性を理解した今、エッジを導入してグラフについて議論を進めましょう。 エッジは隣接行列 AA で表現され、行と列が頂点を表します。（隣接行列について詳しくない場合は、C++プログラマへの道 #16 - グラフ をご覧になることをお勧めします。） これにより、AA の行と列の両方の順列、つまり PAPTPAP^T を考慮する必要があり、グラフの不変関数と同変関数を次のように更新しなければなりません。

F(PX,PAPT)=F(X,A)F(PX,PAPT)=PF(X,A) F(PX, PAP^T) = F(X, A) \\ F(PX, PAP^T) = PF(X, A)

順列不変な関数は引き続き、合計のような集約関数です。また、順列同変な関数も集合の場合と同じように、各頂点に個別に適用される任意の関数として設定できます。 しかし、エッジまたは1ホップ近傍を利用することで、より複雑な順列同変操作を実現できます。1ホップ近傍は、AA における頂点の順序に関係なく同じままであるためです。 より具体的には、近傍は接続エッジを持つ頂点として以下のように定義できます。

Ni={j:(i,j)∈ϵ∨(j,i)∈ϵ}XNi={xj:j∈Ni} N_i = \{j : (i, j) \in \epsilon \lor (j, i) \in \epsilon\} \\ X_{N_i} = \{x_j : j \in N_i \}

ローカル関数 gg が xix_i に対するすべての近傍 XNiX_{N_i} を受け取り、各行に適用される場合、この関数を用いて順列同変関数 FF を定義できます。

F(X,A)=[−g(x1,XN1)−−g(x2,XN2)−⋮−g(xv,XNv)−] F(X, A) = \begin{bmatrix} - g(x_1, X_{N_1}) -\\ - g(x_2, X_{N_2}) -\\ \vdots \\ - g(x_v, X_{N_v}) -\\ \end{bmatrix}

近傍は AA 内で異なる順序で整理される可能性があるため、FF が順列同変となるには、gg が順列不変である必要があります。 したがって、すべてのグラフモデルは、1ホップ近傍を使用し、各頂点に順列不変関数を適用することで順列を保持するグラフの潜在表現を学習する FF を学びます。 この表現は、後のいかなるタスクに利用することができます。

下流タスク

グラフに関連する主なタスクは、ノード分類、グラフ分類、エッジ予測の3つです。タスクに応じて、潜在表現は調整されます。

GNN Tasks

ノード分類は、分類するノードの潜在表現を抽出し、それを任意の関数に渡して処理します。これは、順列同変性によって頂点の順序が保持されるため可能になります。 エッジ予測も同様に、関連する頂点と必要に応じてエッジの潜在表現を抽出して予測を行います。 グラフ分類は順列不変な集約関数を用いて操作を行い、頂点の順序に関係なく同じ分類結果を得ることができます。

結論

本記事では、順序を仮定しないグラフを処理するために必要な、順列不変性と順列同変性という重要な概念について説明しました。 また、グラフモデルが学習する関数 FF についても紹介しました。この関数は、各頂点とその近傍に適用される順列不変操作を利用し、 順序を保持することで、いかなる下流タスクにも適用可能なグラフの潜在表現を生成できます。次回からの記事では、実際のいくつかのモデルと、 それらが学習する gg のパラメータについて取り上げます。

リソース

TOPに戻る↑