グラフラプラシアンの定義と性質を分かりやすく解説

近年深層学習で、GNN(Graph Neural Netork)やGCN(Graph Convolutional Netowork)がノード分類、グラフ識別などのグラフを用いたタスクで非常に高い精度を上げています。

しかし、このGNNの理論的な背景や著名な論文を読んでいると、グラフラプラシアン(Graph Laplacian)という用語が登場し、面食らってしまった人も多いのではないでしょうか。

グラフラプラシアン自体は通常理解するのにかなり難易度が高いと思われますが、一方でGNNやGCNを理解するのに、必要なグラフラプラシアンに関する知識はそこまで多くはありません

今回は、このグラフラプラシアンについて、出来るわけわかりやすく噛み砕いて解説していきます。

グラフラプラシアンの定義

グラフラプラシアンは、1つのグラフについて定義できる行列となっています。今、このような無向グラフがあるとします。この時、隣接行列$A$と次数行列$D$は、次のようになります。

A = \begin{pmatrix}
0 & 1 & 0 & 0 & 1 & 1 & 0 \\
1 & 0 & 1 & 0 & 1 & 0 & 0 \\
0 & 1 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 1 & 0 & 0 \\
1 & 1 & 0 & 1 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 1 & 1 & 1 & 0 \\
\end{pmatrix},  ~~~
D =  \begin{pmatrix}
3 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 3 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 2 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 3 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 4 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 2 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 3 \\
\end{pmatrix}

隣接行列は、各ノードがどのノードと接続されているかを示しており、次数行列$D$は、各ノードが何個のノードと接続されているかを示している行列です。

ここで、この無向グラフに対する、グラフラプラシアン$\mathcal{L}$は次のように表現されます。

\begin{equation}
\mathcal{L} = D -A
\end{equation}

グラフラプラシアンの性質

グラフラプラシアンの性質は下記のような性質があります。