画像データに対するGraph Neural Network（GNN）入門

# はじめに
最近、グラフニューラルネットワーク（Graph Neural Network; GNN）を用いた気象予測の論文が話題を呼んでいました。

>Learning skillful medium-range global weather forecasting | Science
>https://www.science.org/doi/10.1126/science.adi2336
>Google DeepMindの気象予測AI「GraphCast」、1分で前例ない精度の10日間予報を出力
>https://www.techno-edge.net/article/2023/11/15/2259.html
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/76983/8aec1c7a-1f3b-10b3-9ca5-b07ecff8acd9.png)
　Learning skillful medium-range global weather forecasting (Lam et al. 2023)



こちらの研究では空間スケールの異なる様々な気象現象をグラフ表現で上手く捉えることにより、少ないパラメータで効率的な学習を実現、1分間という非常に短い時間で、物理ベースや従来の機械学習ベースの気象予測モデルを上回る精度を実現しています。

これまでの気象・気候領域への機械学習の適用は、Convolutional Neural Network (CNN)やTransformerが主流だったですが、今後はGNNの採用も主要な選択肢の一つになるのではと考えています。

そこで、本記事ではGNNの基礎についてまとめてみようと思います。

# 本記事の焦点

GNNの歴史は意外にも古く、論文としては2015年にグラフ構造にニューラルネットワークが適用される研究が発表され（Gori et al. 2015）て以降、様々な研究成果が発表されています (Wu et al. 2019)。

一方で、実務（ビジネス）でGNNを適用している場面は自分の周りではあまり見かけず、その要因として、グラフ構造のデータセットを直接的に取り扱っているドメインが限定的であり、これがGNNの活用の妨げになっているのではと考えています。

しかし、グラフ構造は実は様々なデータのより一般的（抽象的）な表現であり、使い方の工夫によってはブレークスルーのヒントになるのではないかと考えています。実際に、近年、画像データ、テキストデータに対するGNNを適用する手法が登場してきています。

そこで、本記事では前半では、グラフ構造やGNNについて簡単にまとめ、後半では非構造化データの代表である画像データに対してGNNを適用するために方法を述べたいと思います。更に余力があれば、別記事でPythonを用いて画像データにGNNを実装する方法も紹介します。

# グラフとは
- 簡単にいうと、つながり方に着目して抽象化された「点とそれらを結ぶ線」
- ノード（V; Vertex）とエッジ（E; Edge）で表現される
- グラフで表現できる代表例としては、SNSや交通ネットワーク、分子構造などがある
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/76983/0950ae92-8669-7ba9-2d31-9503eac4efd4.png)

- また、グラフには様々な種類があり
    - エッジに方向の情報がある有向グラフ⇔無向グラフ
    - エッジが複数の線である多重グラフ⇔単純グラフ
- その他にも完全グラフ・非完全グラフ、循環・非循環グラフ等の様々なグラフ種類の分類がある

# グラフの特徴・主要タスク
- グラフは画像やテキストといった様々な事象を抽象的に表現できる（一般表現）
- グラフは数学と相性が良い（行列で表現できる）　*補足①参照
- 一方で、グラフ構造はノードの順番や位置を固定しないので、どの様に上手くモデリングするかが難しい
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/76983/7a0c9506-9182-7ac6-db50-85173b9837b1.png)

- グラフで取り扱うタスクは以下の様に分類できる
    - 教師あり
        - グラフレベル：グラフそのものを分類・回帰する
        - ノードレベル：ノードを分類・回帰する
        - エッジレベル（リンクレベル）：エッジを分類・回帰する
    - 教師なし
        - グラフの潜在表現の学習（エンコードディング）
- SNSの例（ノードが個人、エッジが関係性）で各タスクを説明すると、
    - グラフレベル：友達グループの判定
    - ノードレベル：個人の属性推定
    - エッジレベル：交友関係の推定（知り合いレコメンド）

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/76983/dfa7c5fa-5965-fd94-1ffa-1b0a607200c8.png)



# Graph Neural Network（GNN）とは
- グラフ構造のデータを取り扱うニューラルネットワーク
- 基本的な考え方は通常のニュートラルネットワークと同様であり、
グラフデータを特徴量抽出してベクトル表現（node embeding）し、様々な後続タスクを解く
    - グラフ構造をそのまま出力（左図）
    - 1次元の特徴量ベクトルに圧縮して、分類・回帰（中央）
    - グラフと他データを高次元空間で結合して、グラフで復元（右図）

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/76983/945a356d-987b-29f9-0fab-48933234e483.png)


- しかし、グラフ構造をそのままニューラルネットワークに入力すると問題が発生する
    - 固定サイズの入力：通常のニューラルネットワークは、同じ大きさのデータを扱うが、グラフは大きさや形が異なる（例. SNSでも人によって友人ネットワークのサイズが異なる）
    - ノードの特徴量抽出：各ノードやエッジでは、近傍ノードが間接的に影響しあっている構造であり、これらの特徴を上手く抽出することは従来のニューラルネットワークでは構造的に難しい
- そこで、隣接ノードの特徴量を畳み込みにより取り入れて、新たな特徴量を生成する手法として、Graph Convolutional Neural network（GCN）が提案された (Schlichtkrull et al. 2017)
- GCNは現在、最も基本的なGNNとして利用されている
- GCNの数学的な表現は補足②を参照

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/76983/b0fd3b9a-75fc-2205-4d78-5260400913a9.png)


# 画像に対するGNNの適用

ここから画像データに対するGNNの適用を説明する（具体的にはVision GNN (Han et al. 2022)を紹介）

本研究では、画像をグラフとして扱い、GNNで画像認識することで、Vision Transformer等の最新モデルを超えるパフォーマンスを実現した

## 従来手法との比較

近年の深層学習を用いた画像処理は、画像をパッチに分解して扱う

- CNN（Convolutional Neural Network）：画像パッチに対して移動窓（sliding window）をシフトさせていくことで局所的な特徴量を抽出
- Transformer：パッチ分割した画像を連続的な配列とみなして、注意機構を適用して関係性を特徴量として抽出

しかし、世の中の多くの画像は正方形であることは少なく、その中の存在する不規則で複雑なオブジェクトを認識するにはグリッドやシーケンシャル構造として特徴量を捉えることには限界がある
そこで、グラフ構造を取り入れることで、四角形でない様々な画像を取り扱えたり、画像内のオブジェクトのパーツごとの関係性（つながり）をノードとエッジで表現することができる
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/76983/73f5194b-c120-2970-0610-b062801731e0.png)


## モデル
VisionGNNでは、画像をいくつかのパッチに分割し、それらをノードと見なす
パッチ（ノード）に対してk-近傍でエッジを作ることでグラフを構成する

グラフ構造化した画像データに対して、以下の処理を繰り返し行う
- Graph processing：グラフ情報の集約と更新を行うグラフ畳み込みモジュール
- Feature transform：ノードの特徴変換を行う2つの線形層からなる全結合モジュール
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/76983/8ae79e30-f0b3-2237-98f6-353025d8f7e4.png)


## モデルの可視化（どの様に学習を行っているののか）
下図はノード（星）に対して、学習により獲得した近傍ノードとエッジを示している
- 左図は入力画像に対して、中心の図は浅い層のグラフ、右図は深い層のグラフを表している
    - 浅い層では、色やテクスチャ（質感）などの局所的な特徴の関係性を捉えている
（例. 青線では、近傍の背景である植物との関係を強く捉えている）
    - 深い層では、より画像の意味やオブジェクト理解を踏まえた特長の関係性を捉えている
（例. 青線では、魚と人を中心オブジェクトとみなした際の背景全般との関係性を強く捉えている）
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/76983/1c2e1481-8067-c892-741f-397a215771d6.png)

## 結論
- 提案手法は画像認識と物体検出タスクにおいて、代表的なCNN、Transfomer、MLPと比較して優れた性能を示すことが確認された
- 画像に対して直接的にGNNを適用した本研究はこの先に様々な発展可能性がある

# 最後に
本記事では、GNNの基本からその特長・可能性を紹介しつつ、近年の研究で頻繁に利用されるGraph Convolutional Neural network（GCN）に触れ、最後に画像に対して直接的にGNNを適用した研究を紹介しました。
こちらの記事でGNNの大きな可能性と概念的な理解に繋がればと思います。
次記事ではPythonによるGNNの実装を通じて、より具体的・詳細な理解に繋げたいと思います。

# 補足①）グラフの数学的表現
グラフは行列で表現できる
- 隣接表列 A (Adjacency Matrix)：ノードの接続状況
- 次数行列 D（Degree matrix）：ノードの接続数（対角行列）
- 重み行列 W（Weight matrix）：エッジの重み
- 特徴量行列 X：ノードの特徴量
- ラプラシアン行列 L：L = D - A
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/76983/527f6c67-9036-73ea-9408-0cb8fc670484.png)

# 補足）GCNの数学的表現
GCNの数式：
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/76983/1dc59f93-1f85-43e0-115d-cc34b87c6abf.png)
- $H$は中間層の特徴量行列（$l$はネットワーク層を表し、$l_0$は入力の特徴量X）
- $σ$は活性化関数（例. ReLU）
- $A$は隣接行列、$D$は次数行列
ここで隣接行列は次数行列で正則化されている. なぜなら正則化しないと次数の多いエッジの特徴量ほど、繰り返し計算しているうちに、より多くの情報がネットワーク全体に反映されてしまうため.
- Wはレイヤーごとの重み行列（学習で獲得するパラメータ）
- 見通しを良くするために、図で②と③を$X$とすると、$H_{l+1} = σ（X_{l} \cdot W_{l}）$であり、直前のネットワークの出力と重みの行列積を活性化関数に通して次層に渡している一般的なニューラルネットワークの構造と捉えることができる

# 参考文献
- A comprehensive survey on Graph Neural Networks (Wu et al. 2019)
- Graph Neural Networks: A Review of Methods and Applications (Zhou et al. 2018)
- GraphCast: Learning skillful medium-range global weather forecasting (Lam et al. 2023)
- Vision GNN: An image is worth graph of nodes (Han et al. 2022)
- SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS (Kipf and Welling, 2017)