グラフニューラルネットワーク（GNN）は、グラフ構造を持つデータを直接扱える深層学習手法です。GNNを理解するためには、まずグラフというデータ構造そのものを理解する必要があります。この記事では、グラフの定義・種類・数学的な表現方法を解説します。本記事はWilliam L. Hamiltonの "Graph Representation Learning"（以下、GRL本）の第1章1.1節をもとにしています。

グラフの定義｜ノードとエッジで表現されるデータ構造

グラフの数学的定義

グラフ $\mathcal{G}$ は、ノード（節点）の集合 $\mathcal{V}$ とエッジ（辺）の集合 $\mathcal{E}$ の組として定義されます。

$$\mathcal{G} = (\mathcal{V},\, \mathcal{E})$$

ノード数を $|\mathcal{V}| = n$、エッジ数を $|\mathcal{E}| = m$ と表記します。ノード $u \in \mathcal{V}$ からノード $v \in \mathcal{V}$ へのエッジは $(u, v) \in \mathcal{E}$ と表現します。

以下の図は、$|\mathcal{V}| = 7$、$|\mathcal{E}| = 10$のグラフを可視化したものです。

グラフの構造を表現するには隣接行列 $A \in ＼mathcal{R}^{|\mathcal{V}|\times|\mathcal{V}|}$ を使います。グラフ内の各ノードを隣接行列$A$の行と列に対応させます。あるノード$u$と$v$の間にエッジ$(u, v)$が存在することは、$A[u, v] = 1$と表し、エッジが無ければ0とします。

単純グラフ

単純グラフは以下の条件を満たすグラフです。

• 任意のノード対の間にエッジは高々1本
• 自己ループ（ノードからそれ自身へのエッジ）なし
• すべてのエッジが無向（$(u, v) \in \mathcal{E} \iff (v, u) \in \mathcal{E}$）

ノードとエッジが表すもの

グラフは「エンティティ（対象）」と「その間の関係」を表現する汎用的なデータ構造です。対象によってノードとエッジの意味が変わります。以下には領域が異なる対象を4つ挙げていますが、すべてグラフの枠組みでモデル化することができます。

対象	ノード	エッジ
分子構造	原子	化学結合
SNS	ユーザー	フォロー関係
タンパク質相互作用	タンパク質	生物学的相互作用
計算メッシュ	格子点	格子辺

計算流体力学（CFD）の文脈では、非構造格子はグラフそのものです。各格子点がノード、隣接する格子点を結ぶ辺がエッジに対応します。GNNを使うと、この格子構造を直接入力として扱えるため、PINNが苦手とする複雑形状への対応が期待できます。

グラフの種類｜有向・重み付き・多関係グラフの違い

無向グラフと有向グラフ

グラフでは、エッジに向きの情報を持たせるかどうかも決めることができます。向きを持たせないグラフを無向グラフ、持たせるグラフを有向グラフといいます。

無向グラフでは $(u, v) \in \mathcal{E} \iff (v, u) \in \mathcal{E}$ が成り立ち、隣接行列は対称行列になります。有向グラフでは $u \to v$ と $v \to u$ は異なるエッジであり、隣接行列は一般に非対称になります。

流体領域では、配管網や水道網、河川のモデル化に有向グラフを使い、流れを予測する研究例があります。

重み付きグラフ

重み付きグラフでは、エッジの重みが $\{0, 1\}$ ではなく任意の実数値をとります。隣接行列の成分 $A_{uv}$ は重み $w_{uv} \in \mathbb{R}$ を格納します。

たとえば、タンパク質相互作用グラフでは、エッジの重みが2つのタンパク質間の相互作用の強さを表します。CFDの格子では、隣接格子点間の距離や接続面積を重みとして持たせることができます。

多関係グラフ（Multi-relational Graph）

向きの有無、重みの有無とは別に、エッジに種類（関係タイプ）$\tau \in \mathcal{R}$ を持たせることもできます。多関係グラフと言い、ノード$u$と$v$の間にタイプ$\tau$のエッジがあるとき、このエッジは $(u, \tau, v) \in \mathcal{E}$ と表記されます。

各関係タイプ $\tau$ に対して1つの隣接行列 $\mathbf{A}_\tau$ を定義できます。グラフ全体は隣接テンソル

$$\mathcal{A} \in \mathbb{R}^{|\mathcal{V}| \times |\mathcal{R}| \times |\mathcal{V}|}$$

にまとめられます。$\mathcal{R}$ は関係タイプの集合です。

化学分子では、単結合・二重結合・三重結合という異なる関係タイプを持つ多関係グラフとして表現できます。薬物間相互作用グラフでは、2つの薬を同時に服用したときに生じる副作用の種類が関係タイプに対応します。

多関係グラフには、代表的な2つのグラフがあります。異種グラフと多重グラフです。

異種グラフ（Heterogeneous Graph）

ノードが種類（タイプ）を持つグラフを異種グラフといいます。次式のように、ノードは互いに素な集合に分割することができます。

$$\mathcal{V} = \mathcal{V}_1 \cup \mathcal{V}_2 \cup \cdots \cup \mathcal{V}_k, \quad \mathcal{V}_i \cap \mathcal{V}_j = \emptyset \; (i \neq j)$$

異種グラフの例として、学術論文ネットワークを紹介します。

• ノードの種類: 著者、論文、キーワード
• エッジの種類: 執筆（著者→論文）、含む（論文→キーワード）、引用（論文→論文）

このグラフでは、エッジ「執筆」はノード「著者」からノード「論文」にしか割り当てられません。同様に、エッジ「含む」と「引用」も割り当てられるノードの組み合わせが決まっています。このように、異種グラフのエッジは、ノードの種類の組み合わせによって割り当てられる種類が決まっています。このルールは次の数式で表現することができます。

$(u, \tau_i, v) \in \mathcal{E} \Rightarrow u \in \mathcal{V}_j,\, v \in \mathcal{V}_k$

さらに、異種グラフの特殊ケースとして、多部グラフ（multipartite graph）があります。異種グラフではエッジを割り当てられるノードの組み合わせルールは決まっていましたが、学術論文グラフのエッジ「引用」をノード「論文」からノード「論文」のエッジに割り当てられたように、同じ種類のノード同士を結ぶことができました。一方、多部グラフでは、エッジは必ず異なるタイプのノード間を結びます

$(u, \tau_i, v) \in \mathcal{E} \Rightarrow u \in \mathcal{V}_j,\, v \in \mathcal{V}_k \wedge j \neq k$

多部グラフの例として、医療グラフを紹介します。

• ノードの種類: 薬、タンパク質、疾患
• エッジの種類: 治療（薬→疾患）、含む（論文→キーワード）、引用（論文→論文）

エッジは有向で、「治療」と「関与」が考えられます。いずれのエッジも、異なる種類のノード間にしか割り当てることができません。

多重グラフ（Multiplex Graph）

すべてのノードが複数の「レイヤー（層）」に存在するグラフを多重グラフといいます。層ごとに固有の関係を表し、層内のノード同士を結ぶエッジと層をまたいでノードを結ぶエッジがあります。具体例として、交通ネットワークを紹介します。

• ノード：都市（東京・大阪・福岡など）
• レイヤー1：飛行機でつながる路線
• レイヤー2：新幹線でつながる路線
• レイヤー間のエッジ：同じ都市内での乗り換え（飛行機 ↔ 新幹線）

多重グラフは自己ループあり、ノード間エッジの本数を複数でもよいことにすれば単一レイヤーのグラフで同じ構造を表現することもできます。しかし、レイヤー分けすることで、レイヤーごとに異なる学習ルールを適用できる、ヒトにとっての可読性が上がるなどのメリットが現れるため、多重グラフにも用いるメリットがあると言えます。

特徴情報

グラフに対し、属性情報または特徴情報（Feature Information）を定義することがあります。例えば、ソーシャルネットワークを表すグラフにおいて、ノード「アカウント」に特徴「プロフィール写真」を関連づけさせるなどです。

よくあるケースとして、先の例のようにノードに特徴情報を付与することがあります。特徴情報は、隣接行列$A$で定義したノードの順番と同じになるように、行列 $\mathcal{X} \in \mathcal{R}^{|V|\times m}$として定義します。$m$は特徴の数で、$\mathcal{X}$の要素は実数です。

異種グラフでは複数のノードの種類がありますが、その種類によって特徴の数は異なり得ます。

エッジやグラフに特徴情報を定義することもあります。例えば、配管ネットワークをグラフで表現するとき、エッジに配管長さや径を定義し、グラフに重力や運転圧力を定義する、などが考えられます。

まとめ

• グラフとはノード集合とエッジ集合の組である
• 単純グラフ（ノード間エッジは1本、自己ループなし、無向）
• エッジには向きや重みを定義することもできる
• 多関係グラフ（エッジに種類を持たせたグラフ）
• 異種グラフ（ノードの組み合わせごとにエッジの種類が決まってるグラフ）
• 多重グラフ（交通ネットワークのような、複数レイヤー構造のグラフ）
• ノード、エッジ、グラフに特徴情報を付与することも可能

次の記事では、グラフがどのように機械学習と関係するかについてまとめます。

さらに深く学ぶための書籍

本記事のテーマをより深く学びたい方には、以下の書籍をおすすめします。

• Graph Representation Learning（William L. Hamilton、Morgan & Claypool Publishers）：本記事のベースとなった教科書です。グラフの基礎からグラフニューラルネットワークの最新手法まで体系的に解説しており、著者のウェブサイトから無料で入手できます。