【グラフ深層学習】第2章 グラフ理論の基礎

はじめに

本章で用いる記法

• $\mathcal{G}$: グラフ
• $\mathcal{V}$: ノードの集合
• $\mathcal{E}$: エッジの集合
• $v_i$: 個々のノード
• $e_i$: 個々のエッジ
• $\mathbf{A}$: 隣接行列
• $\mathbf{A}_{i,j}$: 隣接行列の要素（ノード $v_i$ と $v_j$ の接続状況）
• $d(v_i)$: ノード $v_i$ の次数
• $\mathcal{N}(v_i)$: ノード $v_i$ の近傍
• $c_d(v_i)$: ノード $v_i$ の次数中心性
• $c_e(v_i)$: ノード $v_i$ の固有ベクトル中心性
• $\mathbf{L}$: ラプラシアン行列
• $\mathbf{D}$: 対角次数行列
• $\mathbf{f}$: グラフ上の信号・特徴ベクトル（各ノードに関連付けられたデータや属性を表すベクトル）
• $\hat{\mathbf{f}}[l]$: グラフフーリエ変換後の信号
• $\mathbf{u}_l$: ラプラシアン行列の固有ベクトル
• $\lambda_l$: 固有値（$l$ は固有値を指定する添え字）

グラフの表現

グラフは、多くの実世界の現象やシステムを表現するために使用されます。本節では、グラフの基本的な定義と表現について説明します。

定義 ：グラフ

グラフは通常、ノードの集合とエッジの集合から構成されます。グラフは $\mathcal{G} = \left\{\mathcal{V},\mathcal{E}\right\}$ と表記されることが多いです。ここで、

• $\mathcal{V}=\left\{v_1,\dots,v_N\right\}$ はノード（頂点）の集合で、$N$ はグラフのノード数を表します。
• $\mathcal{E}=\left\{e_1,\dots,e_M\right\}$ はエッジ（辺）の集合で、$M$ はグラフのエッジ数を表します。

グラフ内のノードは、グラフにおける個々の要素を表し、エッジはこれらのノード間の関係や接続を表します。例えば、ソーシャルグラフでは人々をノードと見なし、友人関係をエッジとして表します。また、化合物グラフでは、原子をノードとし、化学結合をエッジとして表します。

定義: 隣接行列

グラフは、隣接行列を使って数学的に表現することもできます。グラフ $\mathcal{G} = \left\{\mathcal{V},\mathcal{E}\right\}$ の隣接行列は $\mathbf{A}\in \left\{0,1\right\}^{N\times N}$ で表され、ノード間の接続状況を表します。隣接行列の各要素 $\mathbf{A}_{i,j}$ は、ノード $v_i$ とノード $v_j$ が隣接している場合は1、隣接していない場合は0となります。

無向グラフでは、隣接行列は対称行列となり、 $\mathbf{A}_{i,j} = \mathbf{A}_{j,i}$ が成り立ちます。これは、無向グラフにおいてはエッジの向きが区別されないためです。

例として、ノード数5、エッジ数6のグラフを考えます。このグラフの隣接行列は以下のように表されます。

$$\tag{1}
\mathbf{A} =
\begin{pmatrix}
0 & 1 & 0 & 1 & 1\\
1 & 0 & 1 & 0 & 0\\
0 & 1 & 0 & 0 & 1\\
1 & 0 & 0 & 0 & 1\\
1 & 0 & 1 & 1 & 0
\end{pmatrix}
$$

このように、グラフはノードとエッジの集合、あるいは隣接行列として表現され、それぞれの要素がグラフ内の関係や接続を具体的に示しています。

グラフの性質と様々な指標

グラフは多様な構造と特性を持っており、これらを理解するためには様々な指標が用いられます。ここでは、グラフの基本的な性質と指標を説明します。

次数

グラフ $\mathcal{G}$ におけるノード $v$ の次数は、そのノードが隣接する他のノードの数を指します。数学的には、ノード $v_i$ の次数 $d(v_i)$ は隣接行列 $\mathbf{A}$ を用いて次のように定義されます：
$$
d(v_i) = \sum^{N}_{j=1}\mathbf{A}_{i,j}
$$

例えば、(1)式で表現されるグラフにおいて、ノード $v_5$ は、他の3つのノード $(v_1,v_3,v_4)$ と隣接しており、その次数は3となります。

近傍

グラフ $\mathcal{G} = \left\{\mathcal{V},\mathcal{E}\right\}$ のノード $v_i$ の近傍 $\mathcal{N}(v_i)$ は、$v_i$ と隣接している全ノードの集合を表しています。$\mathcal{N}(v_i)$ に含まれるノードの数は、ノード $v_i$ の次数に等しいのが特徴です（ $d(v_i) = |\mathcal{N}(v_i)|$ ）。

中心性

グラフにおけるノードの中心性は、ノードの重要度を示す指標です。この指標は、グラフの構造に基づいてノードの影響力や関係性の強さを測定します。

次数中心性

次数中心性は、多くのノードに接続しているノードが重要であると考える指標です。これはノード $v_i$ の次数に基づいており、以下のように定義されます：

$$
c_d(v_i) = d(v_i) = \sum^{N}_{j=1}\mathbf{A}_{i,j}.
$$

固有ベクトル中心性

次数中心性ではすべての近傍を平等に扱いますが、固有ベクトル中心性は隣接ノード自体の重要度も考慮する方法です。固有ベクトル中心性は、ノード $v_i$ の中心性スコアをその隣接ノードの中心性スコアを基に計算します。式は以下の通り：

$$
\mathbf{c}_e = \dfrac{1}{\lambda}\mathbf{A}\cdot\mathbf{c}_e
$$

ここで $\mathbf{c}_e$ はグラフ内の全ノードの中心性スコアを成分に持つベクトルで、$\mathbf{A}$ の固有ベクトルに相当します：
$$
\lambda \cdot \mathbf{c}_e = \mathbf{A}\cdot\mathbf{c}_e
$$

スペクトルグラフ理論

スペクトルグラフ理論は、グラフの性質をラプラシアン行列の固有値や固有ベクトルを通じて分析する理論です。この理論は、グラフ構造とその性質を深く理解するのに役立ちます。

ラプラシアン行列

ラプラシアン行列は、グラフの隣接行列と次数行列を用いて定義されます。ラプラシアン行列 $\mathbf{L}$ は次のように定義されます：

$$
\mathbf{L} = \mathbf{D} - \mathbf{A},
$$

ここで $\mathbf{D}$ は対角次数行列、$\mathbf{A}$ は隣接行列です。

例えば、(1)式に基づくと、ラプラシアン行列以下のように計算されます：

$$
\mathbf{L} = \mathbf{D} - \mathbf{A} =
\begin{pmatrix}
3 & 0 & 0 & 0 & 0\\
0 & 2 & 0 & 0 & 0\\
0 & 0 & 2 & 0 & 0\\
0 & 0 & 0 & 2 & 0\\
0 & 0 & 0 & 0 & 3
\end{pmatrix}
-\begin{pmatrix}
0 & 1 & 0 & 1 & 1\\
1 & 0 & 1 & 0 & 0\\
0 & 1 & 0 & 0 & 1\\
1 & 0 & 0 & 0 & 1\\
1 & 0 & 1 & 1 & 0
\end{pmatrix}=
\begin{pmatrix}
3 & -1 & 0 & -1 & -1\\
-1 & 2 & -1 & 0 & 0\\
0 & -1 & 2 & 0 & -1\\
-1 & 0 & 0 & 2 & -1\\
-1 & 0 & -1 & -1 & 3
\end{pmatrix}
$$

ラプラシアン行列の性質

ラプラシアン行列は対称行列であり、隣接するノード間の値の差を基にした数値を生成します。具体的には、ベクトル $\mathbf{f}$ と $\mathbf{L}$ の積は次のように計算されます：

$$
\mathbf{h} = \mathbf{L}\mathbf{f} = \mathbf{D}\mathbf{f} - \mathbf{A}\mathbf{f}.
$$

※ $\mathbf{f}$はグラフ上の信号または特徴ベクトルを表しており、グラフの各ノードに関連付けられたデータや属性を表すベクトルです。具体的には、グラフの各ノードが持つ値や特性（例えば、ユーザーの年齢、分子の化学的性質など）を数値化したものです。これにより、グラフ上のノード間の関係やダイナミクスを数学的に分析・処理することができます。

ラプラシアン行列の固有値と固有ベクトル

ラプラシアン行列の固有値には次の特徴があります。まず、これらの値は非負ですべて0以上です。そして、少なくとも1つの固有値は常に0です。
この固有値0は、グラフ内のすべてのノードに同じ値（例：$\mathbf{u}_1 = \tfrac{1}{\sqrt{N}}(1,\dots,1)$ ）が割り当てられた場合に対応します。

グラフ信号処理

グラフ信号処理は、グラフにおけるノードの特徴や属性を分析するための方法論です。これには、グラフの構造情報とデータ（ノードの属性）の両方を組み合わせたアプローチが含まれます。

グラフ信号の滑らかさ

各ノードにグラフ信号が与えられている状況を考えましょう。
「グラフ信号の滑らかさ」とは、グラフ上で隣接するノード間での信号値の変化の度合いを指します。グラフ信号が滑らかだということは、隣接するノード間で信号値があまり変わらないことを意味します。つまり、グラフ上を移動するにつれて、信号値が徐々にしか変わらない状態です。

この「滑らかさ」を数学的に評価するために、ラプラシアン行列の二次形式、すなわち $\mathbf{f}^T\mathbf{L}\mathbf{f}$ を用います。この計算式における $\mathbf{f}$ はグラフ上の信号（ノードごとの値）を表し、$\mathbf{L}$ はグラフのラプラシアン行列です。この式の値が小さいほど、グラフ上の信号はより滑らかであると判断されます。これは、隣接するノード間で信号値の変化が少ないことを意味し、グラフ全体として信号が一様に分布していることを示しています。逆に、この値が大きい場合は、グラフ上の信号が急激に変化していることを意味し、信号の「荒さ」を示しています。

グラフフーリエ変換

グラフフーリエ変換は、グラフ信号を「空間領域からスペクトル領域（周波数領域）に変換する」方法です。グラフ $\mathcal{G}$ 上の信号 $\mathbf{f}$ のグラフフーリエ変換は、ラプラシアン行列の固有ベクトルを基にして計算されます。この変換は、信号を固有ベクトル（グラフフーリエ基底）に分解し、対応するグラフフーリエ係数を求めます。

$$
\hat{\mathbf{f}}[l] = \langle\mathbf{f},\mathbf{u}_l \rangle = \sum^{N}_{i=1}\mathbf{f}[i]\mathbf{u}_l[i].
$$

ここで $\mathbf{u}_l$ はラプラシアン行列の $l$ 番目の固有ベクトルであり、対応する固有値 $\lambda_l$ はその周波数を表します。

$\hat{\mathbf{f}}[l]$ に変換することで、グラフ上の信号が周波数領域にマッピングされます。これにより、グラフ信号の構造や動態をより深く理解することができるようになります。具体的には、次のような利点があります：

• 周波数成分の識別: 元の信号 $\mathbf{f}[i]$ から変換された $\hat{\mathbf{f}}[l]$ は、グラフ信号の異なる周波数成分を表しています。これにより、グラフ上の信号がどのような周波数の成分から構成されているかを明らかにすることができます。

• 信号の特徴把握: 低周波成分（小さい固有値に対応）は信号の滑らかな部分を、高周波成分（大きな固有値に対応）は信号の急激な変化や局所的な特徴を示します。これにより、グラフ信号の全体的な特性や、特定のノードやエリアにおける特異性を理解するのに役立ちます。

• 信号処理のための基盤: この変換は、ノイズ除去、信号平滑化、特徴抽出など、さまざまな信号処理タスクに応用することができます。周波数領域での操作により、元の空間領域では難しかった処理が可能になり、グラフデータに対する洞察を深めることができます。

総じて、$\mathbf{f}[i]$ から $\hat{\mathbf{f}}[l]$ への変換は、グラフ信号をより詳細に分析し、様々な応用に利用するための強力な手段となっています。

逆グラフフーリエ変換

逆グラフフーリエ変換は、スペクトル領域で表されたグラフ信号を空間領域に戻す変換です。この変換は以下の式で表されます：

$$
\mathbf{f}[i] = \sum^{N}_{l=1}\hat{\mathbf{f}}[l]\mathbf{u}_l[i].
$$

複雑グラフ(Complex Graph)

複雑グラフは、実世界の多様なデータを表現するために使われる、さまざまな種類のグラフ構造です。以下は、本節で紹介されている複雑グラフの種類とその特徴です。

ヘテログラフ(Heterogeneous graph)

ヘテログラフは、複数種類のノードとエッジを持つグラフです。ノードとエッジには異なる"タイプ"が関連付けられ、それぞれのタイプに応じた関係をモデル化します。学術ネットワークのように、著者、論文、学会など複数のノードタイプと、それらをつなぐ様々なエッジタイプが存在します。

二部グラフ(Bipartite graph)

二部グラフは、ノード集合を互いに素な2つの部分集合に分割し、エッジは異なる集合のノード間をつなぐものです。例えば、ECサイトにおいてユーザとアイテムの間のクリック履歴をモデル化する際に用いられます。

多次元グラフ(Multidimensional graph)

多次元グラフは、一組のノード間に複数の関係が存在するグラフです。例としてYouTubeでは、ユーザ間のチャンネル登録、共有、コメントなど複数の関係タイプが存在します。これらの関係は、異なる次元の隣接行列で表現されます。

符号付きグラフ(Signed graph)

符号付きグラフは、正と負のエッジを含むグラフです。SNSでは、友だち関係（正のエッジ）とブロックや友達リストからの削除（負のエッジ）など、異なる種類のエッジが存在します。

ハイパーグラフ(Hypergraph)

ハイパーグラフは、2つ以上のノード間の関係を表すハイパーエッジを持つグラフです。例えば、論文ネットワークでは、1人の著者が複数の論文を発表することがあり、これらの論文はハイパーエッジで結ばれます。

ダイナミックグラフ(Dynamic graph)

ダイナミックグラフは、時間とともに変化するグラフです。新しいノードやエッジが継続的に出現し、グラフの構造が変化します。FacebookのようなSNSでは、新しい友だち関係の形成や新規ユーザの参加により、グラフが動的に変化します。

以上，こうした複雑グラフは、実世界の複雑なデータを表現するために不可欠であり、異なる特性や関係を捉えるため非常に重要となっています。

グラフを使った分析タスク

「グラフ分析タスク」とは、グラフ理論と統計学、機械学習の手法を組み合わせて、グラフ構造データから有用な情報を抽出し、解釈する一連のプロセスを指しています。
グラフ分析タスクは、大きく「ノードに焦点を当てたタスク」と「グラフに焦点を当てたタスク」の2つに分類されます：

ノードに焦点を当てたタスク

ノードに焦点を当てたタスクでは、グラフ内の個々のノードがデータサンプルとして扱われます。主なタスクは以下の通り：

• ノード分類: ノードには様々な情報が関連付けられており、これらはラベルとして扱われます。ノード分類タスクの目的は、ラベルのないノードにラベルを予測・付与することです。例えば、SNSでのユーザの興味・嗜好の予測などが該当します。

• リンク予測: リンク予測は、観測されたグラフにおいて欠落しているエッジ（リンク）を推測するタスクです。これにより、SNSでの友達推薦や知識グラフの補完、犯罪情報分析などが可能になります。

グラフに焦点を当てたタスク

グラフに焦点を当てたタスクでは、各サンプルがグラフとして表現されます。主なタスクは以下の通りです。

• グラフ分類: グラフ分類は、ラベルのないグラフにラベルを予測することを目的としています。化学分子のグラフなどが、このタイプの分類問題の例です。ここでは、化学分子全体にラベル（例えば、溶解度や毒性）が与えられ、新しい化学分子の性質を予測するために使用されます。

これらのタスクは、グラフの特性を利用して、ノードやグラフ全体の特性や関係性を理解し、予測するために用いられます。また、これらのタスクは単純グラフに限らず、2.6節で紹介された複雑グラフにも拡張可能です。

より詳細を知りたい方へ

以上、「グラフ深層学習」の第2章についてまとめました。
もし気に入っていただければ，ぜひ書籍版をご購入くださると嬉しいです．
本書の概要ページは以下になります．