こんにちは． Sansan DSOC 研究開発部の黒木裕鷹です． 2回目の緊急事態が宣言され，昇降デスクを買ったりモニターや服を買い足したりしていました． お財布は寂しいですが，在宅戦闘力が高まりなんだか良い気分です．
さて，この連載では，自分の勉強・復習も兼ねて，ネットワークデータにまつわる統計解析を気の向くままに紹介しています． 前回の記事では，DeepWalkやnode2vecをはじめとするnode embeddingの手法を浅く広く紹介しました． 今回は，ネットワークデータに対する深層学習 (Graph Neural Network; GNN) を俯瞰していきます． 数式は可能な限り使わず，直感的に全体像を把握する助けとなれば良いなと思っています．
それではやっていきます．
はじめに
Graph Neural Network (GNN) は，グラフデータにニューラルネットワークを適用することを目的とした手法の集まりです． 前回記事でも触れましたが，グラフは規則的な格子でないため，従来の深層学習をグラフデータに一般化することは容易ではありませんでした． GNNの研究は21世紀はじめにまで遡ることができ，Scarselli et al. (2005, 2008) はノード単位のタスクとグラフ単位のタスクのそれぞれに焦点を当てた最初のGNNを提案しています． その後，深層学習の技術がCVやNLPなど多くの分野で活躍すると，GNNの研究も盛んになってきた流れがあります．
ノード単位のタスクとグラフ単位のタスク
GNNは，大きくノード単位のタスクとグラフ単位の2つに分類することができます． ノード単位のタスクでは，ノード単位で良い特徴を学習し，それぞれのノードに対して分類したり回帰したりすることを目標としています． 一方でグラフ単位のタスクでは，グラフ全体の代表的な特徴を学習し，1つのグラフを分類・回帰することを目的としており，ノードごとに良い特徴を得ることはあくまでも中間的なステップとなります． グラフ単位のタスクの例としては，高分子化合物の分類などがあるでしょう． 両タスクのイメージを下図に示しました．
ノード単位のタスクでは，特徴量とグラフ構造を学習し，元のグラフと同じ形の予測値をアウトプットすれば良く， 一方グラフ単位のタスクでは，ノード特徴とグラフ構造を集約し，1つの値をアウトプットしなくてはなりません． つまり，GNN には，次の2つの処理が要求されていることが分かります．
- 各ノードの特徴とグラフ構造を加味し，元のグラフ構造と新たな特徴を出力する処理
- 複数のノードを集約し，より粗いグラフ構造と特徴を出力する処理
それぞれグラフフィルタ，グラフプーリングと呼ばれることがあり，この連載でもこれを採用することにします． 一般的に，ノード単位のタスクはグラフフィルタと活性化層の積み重ねで行われますが，グラフ単位のタスクではプーリング層を組み合わせ，適宜グラフを粗くする必要があります．
グラフフィルタ
グラフフィルタは，各ノードの特徴とグラフ構造をもとに特徴量を洗練していく操作で，インプットとアウトプットのグラフ構造は同じなのでした． そのイメージを下図に示します．
グラフフィルタの設計には様々な工夫がありますが，有名なものは大きく2つのカテゴリに分けることができます． それは，spatial-based グラフフィルタ と spectral-based グラフィフィルタです． spatial-based なフィルタは，ノードとノードの接続を明示的に利用し，グラフ構造のまま特徴抽出を行っていきます． 一方，spectral-basedなスペクトルグラフ理論に基づき，まるで波形データのようにスペクトル領域でのフィルタリングを行います． この記事ではまずspectral-based フィルタを先に紹介し，spatial-based の観点からはどのように解釈できるかを説明します． また，その後に様々な spatial-basedなグラフフィルタについて紹介します．
spectral-based グラフフィルタ
現在，spectral-based グラフフィルタでデファクトとなっているのは Kipf and Welling (2016) で提案されている GCN フィルタです． ここでは最終的に GCN フィルタを直感的に理解することを目標に，まずは GCN フィルタができるまでの流れを追っていきたいとおもいます．
GCN フィルタができるまで
spectral-based なフィルタは，グラフ信号のスペクトル領域で処理を行います． まずは，最も基本的な Graph Spectral Filtering (GFS) を紹介しましょう． GSFのアイデアは，まるで音声のフィルタリングのように，グラフ信号の周波数を変調し，周波数成分の一部を保持し，他の成分を除去させることです． グラフフーリエ変換 (GFT; Graph Fourier Transform) によりフーリエ係数を求め，ある部分を除去したり減少させ，逆変換で元に戻すことをします． 音声で雑音を取り除く処理のように，なめらかな信号のみ取り出したい場合は高周波成分を取り除き，ローパスフィルタを設計します．
ここでいう「なめらかな成分」とは，「隣り合うノード間で特徴が似通っている」というイメージです． しかし，GNNのグラフフィルタとして周波数成分の選択を用いる場合，どの周波数がより重要なのかがわかりません． そこで，その係数もパラメータとすることで，従来のニューラルネットワークと同様に end-to-end で学習することができます．
このアイデアは良さそうに見えますが，いくつかの課題があります．
時系列のフーリエ変換が系列の長さと同じになるように，GFTでもノードの数と同じになってしまいます．
つまり，学習するパラメータの数はネットワークの大きさと同じになり，現実のネットワークでは学習が困難になります．
また，同様の理由で行列の内積が現実的ではありません．
そこで，Defferrard et al. (2016) は，完全にノンパラメトリックだった係数を少し制約し，多項式の表現で近似するように設定しました．
これによってパラメータ数は多項式の次数 + 1になります．
ノードの数とは関係なくなりました．
実は多項式の次数 が空間上でも大きな影響をもっており，
-hop の近傍のみを考慮することに相当しています．
つまり，このフィルタは
次の近傍を考慮する spatial-based フィルタとしても解釈することができます．
Atwood and Towsley (2016) では，PolyFilterと同様の動作をするグラフフィルタが，周辺ノードの信号の線形結合で設計されています．
これで大分良くなったように見えますが，多項式近似の利用にも問題点があります． それは，多項式の基底が互いに直交していないことです． つまり，係数は互いに依存関係にあり，学習の途中で受ける摂動に非常に不安定になります． この問題を解決するために，Defferrard et al. (2016) は直交基底の集合をもつ Chebyshev 多項式近似をフィルタに利用することを提案しています．
GCN フィルタ
Kipf and Welling (2016) で提案された GCN フィルタは，Chebyshev 多項式近似によるフィルタをより簡略化し，多項式の係数を としたものです．
つまり，スペクトル領域ではなくネットワークで考えると，各ノードの最近傍のみを考慮するということです．
フィルタ層と活性化層を重ねていくことを考えると，「
程度で十分で，次元の大きい多項式では表現力が高すぎた」ということかもしれません．
spatial-based グラフフィルタ
続いて，グラフの接続を明示的に利用する spatial-based なグラフフィルタを紹介します． こちらも様々なものが提案されてきていますが，特に利用されているものが GraphSAGE フィルタ，GAT フィルタの2つです． この2つを直感的に理解することを目標にします
最初の GNN フィルタ
初めての GNN フィルタは，おそらく Scarselli et al. (2005, 2008) によって提案されたのだと思います． Scarselli et al. (2008) は，あるノードに隣り合う最近傍ノードの特徴量を集約し，あるノードの特徴を更新するものです． 前述した GCN フィルタのようなイメージですね． この操作を何度も繰り返すことにより，近傍だけでなくより広い範囲のグラフ構造と特徴を反映することができます． 一方で欠点もあり，何度も繰り返すことで，全てのノードの特徴が似通ってきてしまいます．
GraphSAGE フィルタ
Hamilton et al. (2017) で提案された GraphSAGE フィルタもまた，隣接したノードの特徴を集約することを行います． ただし，隣接したノード全てを用いるのではなく，ランダムに選択します． また，集約の関数も単純な平均だけでなく，mean aggregator, LSTM aggregator, pooling operator の3つが提案されています．
mean aggregator は，ランダムに選択された隣接ノードの特徴をシンプルに平均するものです． 次に LSTM aggregator ですが，選択された隣接ノードを並べて系列として扱い，LSTM の処理を適用するものです． ここで，どのようにノードを並べるかが問題となりますが，（特殊な場合を除き）自然な順序はないため，ランダムに並べることが採用されます． 最後に pooling operator ですが，これは選択されたノードの特徴を max pooling するような処理です． 何か強い特徴が周りに影響していると考えられる場合には良さそうですね．
GAT フィルタ
Velckovic et al. (2017) によって提案された GAT フィルタは，self-attention (Vaswani et al., 2017) のアイデアをグラフフィルタに反映したものです． GAT フィルタも，他の spatial-based フィルタと同様に近傍ノードの集約を行うのですが，attention メカニズムによって近傍ノードの重要度を考慮します． 近傍ノードすべてに対して重要さのスコアを生成し，その重みに従って加重平均を行います． 活性化関数には，多くの attention と同様 Leaky ReLU が用いられることが多いようです． また，attention 自体ここ数年のトレンドになっているので，勉強がてらまた詳しく記事にしたいと思っています．
グラフプーリング
グラフフィルタは，グラフ構造を変更することなく，ノードの特徴を洗練・集約させていくのでした． ノード単位のタスクではグラフフィルタで事足りますが，グラフに焦点を当てたタスクでは，グラフ全体を表す特徴が望まれます． このような表現を得るためにに，ノードの特徴を要約し，より粗いグラフを出力するグラフプーリングを行う必要があります。 そのイメージを下図に示しました．
最も単純なグラフプーリングは，入力されたグラフ全体から1つの値を出力するようなプーリングです． たとえば，特徴ごとに全ノードの最大値を取るような max-pooling や（加重）平均値を取る average-pooling などがあります． attention を適用することで，各ノードの重みも学習することもできます (Li et al., 2015)． これらのプーリングはグラフ構造を全く考慮しないため，グラフ単位のタスクの最終層付近で用いられることが多いです．
一方で，グラフ構造を考慮できるように，元のグラフを段階的に粗くしてグラフ情報をまとめる階層型のグラフプーリングも提案されてきました． 階層型のプーリングは大きく分けて，複数のノードをクラスターにまとめることで粗くするものと，代表的なノードをいくつか選択することで粗くするものがあります． ノードの選択に基づくプーリングが入力されたグラフのノードを保持する一方で，クラスタリングに基づくプーリングは新たなノードを作り出すことが大きな違いです．
ノードのクラスタリングに基づくプーリング
diffpool
Ying et al. (2018) で提案された diffpool では，入力の各ノードが，出力のどのクラスタに所属するかを表した の割り当て行列（
）を学習し，この行列に従った新たなグラフ構造と特徴量を出力します．
EigenPooling
Ma et al. (2019) によって提案された EigenPooling では，スペクトラルクラスタリングを用いてクラスタを作成し，同一クラスタのノードをまとめています． スペクトラルクラスタリングはグラフデータの代表的なクラスタリング手法で，非常に重要なアルゴリズムであるため，この連載でもいずれ取り上げたいです．
出力される新たな粗いグラフでは，クラスタ間のエッジのみが考慮され，クラスタに付随する特徴量には，スペクトル領域での最初のいくつかの係数が採用されます． 理由としては，クラスターごとに様々な数のノードを持つため一定に揃えなければならないこと，同一クラスターのノードは似た傾向があると考えられるため，はじめの数個（より滑らかな成分）の係数が重要と考えられること，などがあるようです．
ノードの選択に基づくプーリング
gPoolとその拡張
ノードの選択に基づくプーリングで最も有名なものは，おそらく gPool (Gao and Ji, 2019) です．
gPool では，各ノードに対し重要度スコアを考え，これを学習します（詳細には，特徴量から重要度への写像を学習します）．
そして，重要度スコアの順にノード選択し，その誘導部分グラフを次の層への入力とします．
誘導部分グラフについては連載第1回でも触れましたが，選択されたノードと．そのノード間のエッジにより構成される部分グラフです．
重要度スコアはノードの選択だけでなく，各ノードの特徴量の強調にも使用されます．
具体的には，シグモイド関数によってに丸められた重要度スコアを，各ノードの特徴量にかけ，次の層へのインプットとします．
gPool を提案した Gao and Ji (2019) では，アンプーリングである gUnpool も提案されており，これらを組み合わせたグラフ U-Nets の性能が評価されています． 時間があればじっくりと理解したり実装したりしてみたいですね．
さて，gPool では単に重要度を算出しているため，グラフ構造を無視したプーリングとなっています． しかし，前段でグラフフィルタリングを使用することで，周辺ノードの特徴も集約されているはずです． これを明示的に組み込んだプーリングが，Lee et al. (2019) で提案された SAGPool です． GCN フィルタによる出力の次元を1にすることで，重要度スコアとしています．
おわりに
今回は，ネットワークデータに対する深層学習 GNN を幅広く眺めてみました． 個々の操作について詳細に説明することはありませんでしたが，GNN の全体観を把握する助けや導入となれれば幸いです． より詳細に知りたい方は，紹介した文献をご参照ください． また，Zhou et al. (2018a) や Wu et al. (2020) など，GNN のサーベイ論文もいくつか出ているため，そちらを参照するのも良いでしょう．
ネットワークのモデルを俯瞰するシリーズは今回でいったん終え，次回からはまた狭いトピックに絞った記事を書いていきたいと思います． 予定では，古典的なランダムグラフの理論を取り上げていきたいとおもっています（完全に個人の趣味です）．
では，またよろしくお願いします． 緊急事態下ではありますが健やかにお過ごしください．
参考文献
- Atwood, J., & Towsley, D. (2016). Diffusion-convolutional neural networks. Proceedings of the 30th International Conference on Neural Information Processing Systems, 1993–2001.
- Defferrard, M., Bresson, X., & Vandergheynst, P. (2016). Convolutional neural networks on graphs with fast localized spectral filtering. Proceedings of the 30th International Conference on Neural Information Processing Systems, 3844–3852.
- Gao, H., & Ji, S. (2019). Graph u-nets. Proceedings of the 36th International Conference on Machine Learning, 2083-2092.
- Hamilton, W. L., Ying, R., & Leskovec, J. (2017). Proceedings of the 31st International Conference on Neural Information Processing Systems, 1025–1035.
- Kipf, T. N., & Welling, M. (2016). Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907.
- Lee, J., Lee, I., & Kang, J. (2019). Self-attention graph pooling. Proceedings of the 36th International Conference on Machine Learning, 3734–3743.
- Li, Y., Tarlow, D., Brockschmidt, M., & Zemel, R. (2015). Gated graph sequence neural networks. arXiv preprint arXiv:1511.05493.
- Ma, Y., Wang, S., Aggarwal, C. C., & Tang, J. (2019, July). Graph convolutional networks with eigenpooling. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 723–731.
- Scarselli, F., Yong, S. L., Gori, M., Hagenbuchner, M., Tsoi, A. C., & Maggini, M. (2005). Graph neural networks for ranking web pages. The 2005 IEEE/WIC/ACM International Conference on Web Intelligence (WI'05), 666–672.
- Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., & Monfardini, G. (2008). The graph neural network model. IEEE Transactions on Neural Networks, 20(1), 61–80.
- Vaswani, Ashish, Shazeer, Noam, Parmar, Niki, Uszkoreit, Jakob, Jones, Llion, Gomez,Aidan N, Kaiser, Łukasz, and Polosukhin, Illia. (2017). Attention is all you need. Proceedings of the 31st International Conference on Neural Information Processing Systems, 6000–6010.
- Veličković, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., & Bengio, Y. (2017). Graph attention networks. arXiv preprint arXiv:1710.10903.
- Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., & Philip, S. Y. (2020). A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 4–24.
- Ying, R., You, J., Morris, C., Ren, X., Hamilton, W. L., & Leskovec, J. (2018). Hierarchical graph representation learning with differentiable pooling. Proceedings of the 32nd International Conference on Neural Information Processing Systems, 4805–4815.
- Zhou, J., Cui, G., Zhang, Z., Yang, C., Liu, Z., Wang, L., & Sun, M. (2018). Graph neural networks: A review of methods and applications. arXiv preprint arXiv:1812.08434.
