グラフ構造にまつわるサーベイ結果まとめ　GNNからApplicationsまで Part1

グラフにまつわるサーベイまとめ

Kenshi Uchihashi氏：僕はグラフについてサーベイしていまして、幅広くやっているのですが、特にGraph Neural NetworksやGraph Embedding、Link Prediction、Graph Classification、Graph Completion、CV、NLPなど、応用タスクをサーベイしました。だいたい120本くらい読んで、30本の重要論文と70本の関連論文にまとめたのですが、今回は発表用の縮小版です。

まずは自己紹介させてください。

僕は内橋堅志と申しまして、xpaper.challengeの運営をしています。フリーランスの機械学習エンジニアとリサーチャーで、いろいろなお仕事やらせてもらっています。Twitterは「uchi_k」という名前でやってるので、よかったら見てみてください。

今回サーベイをどうやってやったかですが、まずは関連するキーワードや重要な研究者を洗い出してGoogle Scholarに突っ込んで、論文見ていって。そして論文のリストを作って、重要そうな論文を探していきます。

重要論文の選定なんですが、2018年より以前だと、引用数でだいたい評価が定まってるんですよね。なので、主にそれを使って評価しました。2019年だとまだまだ引用数がついていないので、がんばって内容で評価する。あとは有名研究者が書いていたらちょっと優先して読む、みたいな感じで消化していってます。あとは有識者に「この論文どうですか」「最近なんかいいのありましたか」みたいなことを聞いてます。

今はだいたい120～130本ぐらい読んでいる感じなんですが、カンファレンスの割合としてはNeurIPSが多いですね。あとはICLRが多いです。ICML、AAAIと続いていくのですが、やはり理論系のトップ会議に集中します。だいたいここまで挙げた会議で半分くらいかな、という感じです。これからグラフの論文で、例えばグラフニューラルネットワークスが多いんですがそういったものを書くとしたら、このあたりを狙って出すのかな、という感じです。

あとは情報検索系の会議です。KDDやWWW、WISDOM、SIGIRもけっこうあります。Graph Embeddingとか、リコメンデーション系のタスクは、こっちのほうが多いかなと。あとはarxivですね、2019年の論文はだいたいarxivでした。論文は最も貢献が大きいと思った分野に割り振りながら説明します。

今回は前提とする知識が正直結構あります。一番はニューラルネットワークの基礎知識ですね。MLPだとかconvolution、pooling、CNN、RNN、LSTM、その他といったところです。あとはグラフの基礎用語です。だいたいは大丈夫だと思いますが、グラフラプラシアンとかはちょっとむずかしいというかアレなんですが、その辺を前提にしています。

そして、とくに断りがなければループや多重エッジがないグラフを扱ってます。数式は追わないで、論文内で重要な数式があれば紹介しますし、図を見た方が早い場合はそれでやっちゃう、という感じでやらせてください。

今日は30分で説明するのですが、結構な量を紹介したいと思うので、細かいところは紹介できません。

では、まとめたものです。

一応、重要論文30本、関連論文70本にまとめようということでやっています。ただ、今見ていただいている資料では40ぐらいに減らしています。それでも終わるかわかりませんが、発表では基本、基礎的な内容に絞ってやっていきたいと思います。

ちょっと範囲が広いので説明不十分なところがあるかと思いますが、後日アップする資料で補完してもらえたらなと思います。よろしくお願いします。

The Graph Neural Network Model

まずはグラフニューラルネットワークです。『The Graph Neural Network Model』という論文があって、これは2009年に出た論文です。

グラフニューラルネットワークの一番最初みたいな感じですね。一応2005年ぐらいに出た論文もあるんですが、おそらくこちらのほうが引用されているし、ちゃんとした定式化されているという印象です。

本当にシンプルで、ノードがメッセージを伝播していく仕組みでGNNを導出する、という感じですね。これを見てもらうと図がありますが、隣接ノードを見ています。まず、自分のノードが持っているラベルと、隣接してるエッジ。エッジというのはこのノードを結ぶ線のことです。エッジのラベルと隣接しているノードの状態、あとは隣接ノードのラベルの4つを伝播していく、という仕組みです。

最近傍ノードの情報も再帰的にaggregateし、1回1回集めていきます。だから1-hopなんですよね。隣のノードの情報しか取れないので。ですが、例えば5回やると、毎回集めてるのは最近傍ですが、その最近傍のノードはさらにその最近傍のノードの情報を取ってくるので、k回やるとk-hopの情報が取れます。一応、あらかじめ決められたタイムステップで学習が終わるモデルです。

問題点があって、まずこのやり方は、1回1回繰り返す毎にめちゃめちゃ薄まっていきます。そして、遠くのノードの情報は取りにくいです。最初にできたやつなんでこんなものですね。グラフ構造もそのままニューラルネットに落とし込めるようになりました、というのが一番の貢献なのかなと思います。

Spectral Networks and Locally Connected Networks on Graphs

続いてそこから一気に5年経ちます。

タイトル見てもらうと「Spectral」と「Locally Connected」がありますね。この論文では2つの提案をしてるのですが、この論文でやっているのは、グラフにおける局所性と解像度を定義して、グラフに拡張する方法をSpatial、空間的な方法と、Spectral、周波数空間でやるという2種類を提案しました。

これは著者見てもらうとYann LeCun先生が書いています。Yann LeCun先生はCNNを作った人ということで、今回紹介してみました。

2つあると言ったんですが、まずはSpatialなほうで説明していきます。「局所性と解像度を定義し」と言ったので、まずは隣接行列を使って局所性を定義します。これがすごく簡単で、正確に言うと重み付き隣接行列ですね。隣接行列って、ノードの数が例えばn個だとn×nの行列で、つながってるところに1が入ってる、みたいな感じです。重み付きだと、そのつながりにちょっと重みがかかっています。

この重み付き隣接行列に対して、デルタでしきい値を適当に設定して、それより値が大きいところがつながってるとして、強くつながってるところだけを取ってくる、という操作で局所性を表現しています。

もう1個が、マルチスケールクラスタリングです。これが解像度を表現しようとしているのですが、クラスタに含まれている全ノードの特徴量を入力にして、代表値として1つの特徴量を出力するというものです。

入力ノードの集合がまずあったとして、それがクラスタリングされて、4つの点が凝縮されて代表点が取れています。これが、例えば6個のクラスタに順番に分けていくと。そうやっていくと、CNNで言う解像度みたいに見えます。そういうことをやってますと。

ここで軽く触れておきたいのが、CNNの特徴はこの局所性と解像度という、入力のサイズによらないフィルターですよね。poolingやサブサンプリングするというのもありますが。

あとは重み共有があります。重み共有に関して、おそらくグラフで重み共有するのは難しいと思います。その理由はいろいろありますが、グラフって構造が場所によって全く違うので、共有した重みを定義しづらいんですね。なので、完全にCNNに持ってくるのはハナから諦めている、とイメージしてもらえるといいかなと思います。

時間がないのでポンポンいきます。この「F k,i,j」という添字がありますが、これは隣接関係があるところだけを残すフィルターです。このフィルターってノード数がnとしたら、n×nなんですよ。n×nのフィルターなんですが、一応めっちゃスパースです。今回は局所性を定義しているので、それに従ってめっちゃスパースではあるんですが、n×nなんですよね。なので、大きいフィルタをボーンとかけている、というのが下の式です。

次に、Spectralな手法について説明します。

先ほどのやつはわかりやすかったと思いますが、これは簡単に言うと、フーリエ変換したところで要素積をとって逆フーリエ変換しましょう、という話です。

ですが、「グラフでフーリエ変換って何なの？」となるので、できるだけがんばって説明します。まず、フーリエ変換というのは、波形を周波数成分に分解する。そして周波数成分がいっぱいでてきて、それに対して係数が付いていて、その足し合わせになりますよ、というものだと思います。

これを踏まえて、グラフフーリエ変換とは何かということです。グラフ上で定義された信号があります。これはノードの特徴量と思ってください。それに対して信号の急峻さを定義して、その急峻さごとに成分分解するんですけど……。

これは説明をパッとするの難しいのですが、今は納得してください。急峻さごとに成分分解するのがグラフフーリエ変換です。

では、これはどうやってやるかというと、グラフラプラシアンの固有値計算をしたら、急峻さ成分への分解が可能です。これも納得してもらうしかないんですけど。

ここまでできるとしたら、convolutionはFourier domainで要素積になりますよ、という定理があります。なので、じゃあ要素積でconvolutionできるじゃん、ということなんですね。

そうしたら、要素積に対して逆フーリエ変換を取ると、Spectralな空間でconvolutionをして返ってきます。なので、フーリエ基底に対応したグラフラプラシアンの固有ベクトルがあって、その結合係数を変化させて、グラフ上の特徴量変換をやって元の空間に返ってくればいい、というのがこの式ですね。

固有値計算ってめっちゃ計算量がヤバいんです。固有ベクトルの積も計算コストがデカい。なのでやりたくないんですが、こういう大きい計算が最初に定義された論文ですね。

Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

その固有値計算とか、そこを回避したいってモチベがあるので、そこに取り組んだのがその2年後に出たこちらの論文です。これは一言で言うと、チェビシェフ多項式近似で固有値分解を回避しよう。計算量を下げて、実用的な範囲で計算量をとどめましょう、みたいなことです。

一言で言うと「チェビシェフ多項式近似しました」って感じですね。

それで、多項式近似したほうが精度上がったというのがおもしろいところだと思っています。結局「なんで近似したほうが精度上がるの？」という話なんですが、これは「そもそもちょっと過学習してたんじゃない？」みたいな疑惑がありました。この次の論文でも、この「多項式近似したら精度上がった」という部分とちょっと関係してきます。

あとはチェビシェフ多項式の次数、今回はkなんですが、これって固有値をk個取るのに対応しているので、フィルターサイズと対応してます。これ、後で使うのでちょっと覚えておいてください。

Semi-Supervised Classification with Graph Convolutional Networks

この次を見ると、今まで紹介した論文一旦忘れてもいいぐらい、これ大事なのかなと思います。

「Semi-Supervised Classification」って言ってますけど、Graph Convolutional Networksのデファクトみたいな感じです。

書いてる人も業界のメインみたいな人です。引用もめちゃめちゃされている論文です。一言で言うと、隣接ノードの畳み込みオンリーでSpectralGCNの近似ができます。

隣接ノードの畳み込みの話をSpatialのところでやって、SpectralGCNの近似になるという話なので、簡単に言うと、SpatialなやつとSpectralなやつが、今ここで融合したと思ってください。

先ほどチェビシェフ多項式近似をやりましたが、k=1の場合、最近傍のみ参照するということです。そのk=1の場合でやります。

確かに、モデルの表現能力はめっちゃ下がります。k=1だと線形になるんですが、そこはDNNの深さでがんばりましょう。今まで勾配消失に対応するテクニックみたいな概念はあまりなかったんですが、ここでrenormalization trickがいくつか導入されています。これはちょっと紹介できませんが、見てみてください。ここで標準的なGraph Convolutional Networksが定義されたかな、というところですね。

今回は「Semi-Supervised」と言っているんですが、ラベルが付いてるデータがちょろっとあって、それに対してsoftmax cross entropyで学習します、という論文です。今までのSpatialなやつとSpectralなやつとが合流した感じで、注目されていました。

あとはこれもチェビシェフ多項式近似でk=1にしていますが、今まで過学習をたくさんしていたのか、過学習の抑制効果で近似したほうが精度が良くなっているんだと思います。あとは多項式近似にしたほうが精度も上がります。これはチェビシェフでも言いましたが、僕は過学習の抑制ができたからだと思っています。

Gated Graph Sequence Neural Networks

続いて、『Gated Graph Sequence Neural Networks』です。

一番最初に出たGraph Neural Networksは、x(t+1)をx(t)の状態から更新していくもので、あれは実質RNNなんですが、その状態更新をLSTMやGRUでやりましょう、ということですね。

一応、勾配計算のアルゴリズムが変わったのと、シーケンシャルな出力を学習できるようになったので、応用幅はすごく増えたと思っています。この論文の中ではけっこういろんなタスクをやっていますが、コードの信頼性評価というタスクがあり、これがおもしろいなと思ったので、興味あったら見てみてください。前の論文は2009年で、これは2016年ということで、よりスマートな時代に沿った定式ではないかと思います。

How Powerful are Graph Neural Networks?

次の『How Powerful are Graph Neural Networks?』という論文は、めちゃくちゃおもしろいです。これがICLRの2019のオーラルだったと思いますが、この論文が今後すごく大事になると思っています。GNNsを再定式化して、この「WL test」はあまり聞き慣れないと思いますが、これは簡単に言うとグラフが2個あって、それが同じグラフであるかをチェックする方法です。このWL testをかけると同じかどうかわかるというものです。

結局グラフの表現能力は、グラフが同じ形かどうかをチェックできるかどうかで見ればいいよね、みたいな。このWL testと同等の性能がそもそも得られているかを調べて、必要な制約は何か、というのをやっています。

まず定式化です。基本はAGGREGATEしてCOMBINEしてるよね、みたいな、この2つに分けています。Graph-focused Task、ノードの情報を見るのではなく、結局そのノードの情報を最後にまとめて、グラフ全体で例えばGraph Classificationとか、そういうタスクをする場合はREADOUTで全ノード情報を集約して、みたいなのは一応ありますが基本はNode-focused TaskだったらAGGREGATEしてからCOMBINEしています。

「結局、今まではAGGREGATEとCOMBINEに何を選ぶかでしたよね」ということを言っています。GCNに関しては「ぽく」書けばこうですね、みたいなことをこの論文では言っています。

そう書けるのはわかりました。じゃあそれぞれの表現能力の高さを分析したいんですけど、理想的には異なるグラフを完全に識別できるかどうかで、グラフの表現能力の高さがわかります。ですが、もし完全に識別できるとしたら、同型性識別問題はNPなんですけど、それを解決したことになってしまいます。

この論文の中でいろいろ説明されてるんですが、今回は割愛します。ただ結論を言います。AGGREGATEとCOMBINEで記述できるGNNsは、グラフ部分構造の識別能力はWL subtree kernelと等価です。

等価なんですが、そもそもWL testって、特徴ベクトルとして出てくるのって離散値なんですよ。で、subtree間の類似性とかそういうものは見れないんですが、GNNsではできます。

なので、結局GNNsってWL testに類似しているというのがあるんですが、それを学習ベースで連続空間に拡張しています。なので、結局表現能力の高さではなく、embeddingやグラフ構造間のdependencyができるようになってるところがいいよね、というように結論付けてます。

結局今までのやつは、表現能力という点で見るとWL testと一緒ぐらいです。では「WL test保証がある一番ミニマムなやつって何？」ということで、それを導出しているのがGIN「Graph Isomorphism Network」です。これがミニマムですよ、ということで、シンプルなものを提案しています。

シンプルなんですが、もうこれでいいんですよ。これで「理論上、同程度の性能が出ます」と言ってるところが、クールなところかなと思います。