グラフニューラルネットワーク(GNN)って何？
深層学習が大人気だった数年前、私の周りの世の中は畳み込みニューラルネットワーク(CNN)や、回帰型ニューラルネットワーク(RNN)が溢れていたような気がする。画像処理にはCNN、時系列データにはRNNやLSTM、生成系には敵対的生成ネットワーク(GAN)という、その頃の人間が聞けば懐かしいと感じる概念の最盛期に、ひっそりと？グラフ構造を対象としたグラフニューラルネットワーク(GNN)というものが存在していたのはご存知だろうか。GNNを利用すると、読み込んだグラフの特性や各ノードの特性、さらには、各ノード間の関係性まで上手く捉えることができるようになるのだ。
GNNでできることの代表例：
- ノード表現の学習: グラフ内の個々のノードの埋め込み（ベクトル表現）を学習し、ノードの役割や特徴、近隣ノードとの関係性を捉えることができる。これらの表現は、ノード分類やリンク予測などのタスクに利用可能。
- グラフ表現の学習: グラフ全体の埋め込みを学習し、グラフの全体的な構造や特徴を捉えることができる。これは、グラフ分類などのタスクに用いられる。
- ノード分類: 学習されたノード表現を用いて、グラフ内のノードが属するカテゴリを予測することができる。
- リンク予測: グラフ内の2つのノード間にエッジが存在するかどうかを予測することができる。
- グラフ分類: 学習されたグラフ全体の表現を用いて、グラフが属するカテゴリを予測することができる。
本シリーズ記事ではこの中でもノード表現の学習に焦点を当てて、GNNを見ていこうと思う。
GNNでできることの応用例：
上の基本的なGNNのできることではピンとこないなー、というそこのあなたのために、具体的な応用例も列挙してみた。正直この辺はグラフ理論をはじめとしたより専門的な知識を要するため私もあまり詳しくない。もっと詳しく知りたい人のために、関連のありそうな論文等へのリンクを参考文献として貼ってあるが、私もすべてを読んだわけではないことを一応、ここに明記しておく。なお、様々な文献を漁っていくとMessage Passing Neural Network(MPNN)という言葉が見つかるが、これはこの記事で対象としているGNNとほぼ同義であると考えてよい。
-
アルゴリズム的推論: グラフ上で定義されたアルゴリズム的な問題を解くためにGNNを活用することもできる。動的計画法や最短経路探索といったアルゴリズムとGNNの関連性が研究されていた気がする。これはNeural Algorithmic Reasoningと呼ばれる分野らしい。
参考文献 Neural algorithmic reasoning -
分子特性の予測と設計: 化学分野では、分子をグラフとして表現し、GNNを用いて分子の量子特性を予測したり、特定の性質を持つ新しい分子を設計したりすることができる。
参考文献 Neural Message Passing for Quantum Chemistry -
動的システムのモデリング: 時間とともに情報や構造が変化するグラフを扱うことができ、ソーシャルネットワークのインタラクション予測や交通予測などにも応用可能。
参考文献は確かこれだった気がする Spatio-Temporal Latent Graph Structure Learning for Traffic Forecasting -
グラフ生成: 特定の性質を持つ新しいグラフ構造を生成するDeep Graph Generative ModelsのベースとしてGNNが用いられることもある。
参考文献 Learning Deep Generative Models of Graphs -
強化学習におけるポリシー学習: グラフ構造で表現された環境において、エージェントが最適なポリシーを学習するためにGNNを利用することもできる。
参考文献 Deep reinforcement learning with relational inductive biases -
自然言語処理における埋め込み表現の学習:自然言語はよく時系列データであると考えられがちだが、文法構造の依存関係等を考慮するとグラフ構造（というよりは木構造）であるともいえる。この依存関係を利用してよりよい埋め込み表現を得ようとする試みもある。
参考文献は確かこれだった気がする Graph Neural Networks for Adapting Off-the-shelf General Domain Language Models to Low-Resource Specialised Domains
そもそもグラフって何？
離散数学を学んだことのない人(学んでいても忘れた人)にグラフって何？と聞くと以下のようなものが返ってくるかもしれない。
折れ線グラフ
関数グラフ
どれもグラフであることに間違いはない。しかし、今回我々が注目するのはグラフ理論やネットワーク理論という領域において主役となるグラフである。これは以下のような形をしている。
図はWikipediaのグラフ理論ページより
グラフはノード(図の中の丸)とエッジ(丸と丸をつなぐ線)の集合からできている。上の図であればノードは全部で6個、エッジは全部で7個ある。グラフを理解するうえで必要なのは、極論、これだけである。
グラフは何がうれしいの？
「こんな丸と線の集合体に何の意味があるんだ！」と思った人もいるかもしれない。「グラフ理論？なんにでも理論ってつければいいと思いやがって！」と理論アレルギーの人の怒号も聞こえてきそうである。ただ、この単純な丸と線の集合は意外に使いやすい。それは、これが世の中のいろいろなものを抽象的に表した表現だからである。
人間関係としてのグラフ
図はWikipediaのグラフ理論ページより
先ほどのこの図を見てみよう。この味気ないグラフが実は六人の人間の数奇な人間関係をあらわしているとしたらどうだろうか？丸を人間とし、線を友人関係としたとき、様々なものが見えてくる。
6番の人は友人が一人だけであるところを見ると、どうやらあまり人づきあいが得意ではないのかもしれない。逆に1番、2番、5番は互いが互いに友人関係にあるところを見るに、仲良し三人組といったところであろう。
さらに、「友達の友達は俺の友達」というオープンなマインドでこのグラフを見たとき、6番の人間が交友関係を広めるには友人関係の多い5番や2番と友達になるのがよさそうだと分かる。
また、仮に、1番、2番、4番が全員バスケ部だとすると、そのすべてとつながっている5番もバスケ部である可能性が見えてくる。
地図としてのグラフ
図はWikipediaのグラフ理論ページより
今度はこの図を地図として見てみよう。各丸が町を表し、線が道をあらわしていると想像しよう。町にしては、お互いをつなぐ道が一本しかないのは寂しいものだなーと思った方は、規模を縮小して、村でも、家でも、自分に合った想像をしてみてもいいかもしれない。このとらえ方により、また多くの情報を知ることができる。
まず、5番や2番、4番は比較的栄えた町であることがうかがえる。「全ての道はローマに通ず」なんて言葉があるが、多くの道が集まる場所は重要拠点である可能性が高い。そうした意味で3本と多めの道を持つこの町たちは栄えているのであろう。逆に、6番などは4番からしか道がなく、交通の便から考えてもあまり栄えていないかもしれない。
また、あなたが旅人だとして、すべての町を訪れなければならないとしよう。あなたはすべての町を訪れることはできるだろうか？そして、もしあなたがとても飽き性の旅人で、一度通った道を絶対に二度と訪れないという頑固なポリシーの持ち主だったとしたら、それでも旅は可能だろうか？
グラフを見るに、すべての町がなんらかの道でほかの町につながっているので、どの町から出発してもすべての町を回ることはできそうだ。一方、頑固なポリシーを持つ旅人の願いは叶いそうにない。これは、頑固なポリシーがこのグラフを一筆書きでなぞれるか？という問題と同義であり、それが不可能なことがグラフ理論で証明されているためである(詳しくは下記の豆知識を参照されたし)。
グラフのまとめ
このように、味気なかった丸と線だけのグラフが実は実世界の概念の抽象的な表現であることに気づくと、グラフを少し身近に感じられるかもしれない。上では、人間関係や地図といった単純な例を持ち出したが、グラフはさらに複雑な実世界の概念である、SNSのつながりや、分子構造、回路図といったものまで表現することができる。
豆知識：オイラーグラフの定理
あるグラフが一筆書きで戻ってこれるかどうかは、そのグラフの各ノードにくっついているエッジの数が偶数である必要がある。
上のグラフでは3番と1番以外のノードにくっついているエッジの数が奇数だったので、一筆書きで戻ってくることはできず、結果として頑固なポリシーの旅人の旅は出発する前から失敗が約束されていた。
まとめ
さて、いろいろ情報を詰め込んでしまったが、この記事で知ってほしかったことは二つしかない。
- グラフっていろんなものを表現するのに便利だなー
- そのグラフに対していろいろできるGNNって面白そー
これだけである。
次の記事はいつ書けるのか？、それは神のみぞ知る領域の話だが、時間があればまたコツコツ書いていきたい。
次の記事では、GNNの仕組みに触れ、できればCNNやTransformerがGNNの特別なケースであることを示せれば幸いであると感じている。
Discussion