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

Deepwalk: Online learning of social representations

Graph Representationに移ります。

この「Deepwalk」というものがあって、Embeddingの話、グラフのノードの分散表現を得たいという話をしたいと思います。このDeepwalkは、けっこう有名かなと思います。

グラフ上でランダムウォークします。すると、系列が得られると思いますが、その得られた系列、Skip-gramってわかりますかね？　n-gramはわかると思いますが、Skip-gramは「I have a pen」みたいなものがあったとして、ちゃんと学習されたSkip-gramがあったら、「I」がきたときに隣接する単語「a」は違うよね、「have」ですよね、みたいな。そうやって、関係性の近いワードの確率が出ます。それがSkip-gramです。

その得られた系列をSkip-gramに入力してノードの分散表現を得ます、ということをDeepwalkはやっています。

この図はグラフがあって、そのグラフが分散表記になったというやつなんですけど。なんかイケてる感じしませんか？　グラフの近さを表現できてる感があると思います。

Line: Large-scale Information Network Embedding

続いて「LINE」という手法があって、直接リンクを持っていないノードでも近しい特徴を持っているのであればそれは似ているノードだから、それも考慮してEmbeddingしましょう、みたいな感じです。

これは図を見てもらうのが一番早いですね。図を見てもらうとノード5と6があると思いますが、まずノード5と6はつながっていません、ですが、ノード5と6がつながっているノードはだいたい一緒です。なので、「second-order proximity」と言っているのですが、「グローバルに見ると5と6は似てますよね」みたいなことを言っています。だからそれを考慮してEmbeddingしましょう、というやつです。一応エッジサンプリングを工夫したりとかもありますが、こういう手法があります。

node2vec: Scalable Feature Learning for Networks

次に「node2vec」というやつが出て、これはだいたい1年刻みでやっています。

なのでこのnode2vecは、DeepWalkで系列取得するのがランダムウォークだったんですが、ランダムウォークではなくもうちょっとグラフらしくノード探索しましょう、というのを提案してますね。

「グラフらしく」とは何かというと、幅優先と深さ優先のバランス取りましょう、という話です。今までやっていたのは、幅優先、近隣の関係見ましょうという感じで、同じノードばかり見てしまうんですよね。ですが、深さ優先するとより遠くのノードから近傍を構成できます。

ただし、遠くに行くので分散がデカくなるという問題はありますが、その間のバランスを取ってサンプリング戦略決めましょう、ということで、サンプリング戦略を持っているDeepwalkです。

GraphGAN: Graph Representation Learning with Generative Adversarial Nets

あとは、GraphGANというものがあります。

これは何かと言うと、シンプルに言うと生成されたノードをグラフに混ぜ込んでいく生成モデルと、それに対してグラフ全体の妥当性を判断する識別モデルがあったら、グラフでGANできるやん、ということをやってます。

だからこれは生成されたノードをグラフに混ぜ込むということがわかっていれば、パッと理解できるかなと思います。一応policy gradientを取るんですが、これがけっこう曲者です。loss計算が曲者で、そこでけっこうがんばってるイメージですね。そこをがんばって、Graph Softmaxを導入していて、これが地味に貢献していて、計算効率がすごい上がりますよ、という。異なる文脈で発展してきたグラフ生成モデルという識別モデルがここで融合します。

Weisfeiler-Lehman Graph Kernels

次はずっと話したかったWL testです。

これは「グラフの同型性の判断をやるやつですよ」と言ったんですが、これは1回やってみるといいなって思っています。1回、何か小さなグラフでWL testやってみると、一発でわかります。

一発でわかるんですが、一応説明します。全部のノードについて、自分と近傍ノードのラベルを集めてきます。そして集めたラベルをソートして、そのラベル集合にまったく新しいラベルを振ります。これを繰り返すと毎回新しいラベルが作られていくのですが、その新しく作られるラベル集合がどこかで一致しだしたら同型。一致してなかったら非同型ですよ、というやつです。これはやればわかります。同型性判定ではおそらく一番引用されてるんじゃないかと思います。

このWL subtree kernelというものは、subtree kernelを使うと特徴量化もできるのですが、これは同じ人が論文を書いています。同じ人が書いているので、だいたい書き方も一緒です。よかったら読んでください。

Embedding Logical Queries on Knowledge Graph

続いて、Applicationsを見ます。

これはグラフの低次元埋め込みを学習して、グラフでの論理演算を帰化操作に変換するということをしていて、まず何かグラフあるとします。それを埋め込みます。グラフでやりたかった操作があったとして、そのグラフでやりたかった操作は埋め込み空間では、幾何操作ですよね。

グラフでやりたかった論理演算は、埋め込み空間で何か対応する幾何操作があります。その幾何操作でやると、線形時間で探索できていいですよ、みたいなことをいっています。

1個1個説明します。まず、Knowledge Graphを対象にしてるんですが、現実世界にあるKnowledge Graphって、絶対に何か欠けてると思っていいと思います。それはなぜかというと、僕らはすべての知識を持っているわけではなく、ちょっとずつKnowledge Graphに新しい知識を足しながら、その中で推論をやっていきます。なので、常に不完全なグラフの上で僕らは推論してると思うんです。

その不完全なグラフがあって、今はわからないですが、新しいノードが実はつながってて、本当は今回のクエリの答えはそれなんだって場合、あり得るじゃないですか。

そのときに、ちゃんと今はないノードを指してほしい、というのがモチベーションとしてあります。まずグラフ上でのクエリ自体をグラフにして、その始点を今回はconjunctive queryなので論理積の演算なんですが、そのスタートのところを低次元で埋め込む。そして、グラフ上では論理積の操作なんですが、このグラフ上での論理積の操作は埋め込み空間ではprojectionになってると。このprojectionはベクトルのintersectionでできる、というのが今回の論文でわかりました。

そして、projectionしたら、今は存在しないノードかもしれませんが、そのprojectionによって、この新しいノードが求めるものですよ、ということがわかる。シンプルに言うとそういう感じです。

今までもこういうことはありましたが、これを幾何操作でやっているところが偉くて。なぜかというと、まず考えてほしいのですが、Knowledge Graphがあって「不完全なKnowledge Graphですよ」と言われたときに、全てのノードを取ってきて、そのノードが新しいノードとつながっている可能性を全部考慮しなければいけません。結局、ノードの数だけ尤度計算が発生するんですよね。ノード全部に対して、新しいノードとのつながりがあり得るから。

なんですが、これをProjectionにすると考えなくていいんですよね。ただ移動するだけなので、わかりますかね（笑）……考えなくていいんですよね、すべての点に対する尤度計算しなくていいので。だから線形時間と言っていて、この論文はそういうちょっとおもしろいことを提案しています。

この論文は他にも言うことはありますが、グラフを経由したEmbeddingをやることで、論理演算可能な性質がEmbedding先の空間に残るというのがおもしろいです。

Interactrion Networks for Learning about Objects, Relations and Physics

最後に、見て一発でわかる系のやつで終わります。物理法則を物体とその関係性に分解することで推測できるようにしました、という物理シミュレーションですね。

シンプルに物体と物体間の関係をグラフにして、その効果量の計算モデルと、あとは外力ですね。その相互作用を考慮した状態推定を行うモデルを2個作ってやっています。という感じなんですけど。なんかキレイにできてるな、って思ったので紹介しました。

汎用性が高くて一般的な物理法則に適用できるんですが、まだまだトイプログラムぐらいしかできないくらい、計算量がめちゃくちゃ大きいんですね。

とりあえずこれで論文は終わりです。あとは今回読んでいて「おもしろい論文書くな」と思った研究者を紹介します。

とくに僕が好きなのは、このMax Wellingさんですね。この人はVariational AutoEncoderの人なので、知ってる人も多いと思います。あとはThomasさんはたぶんこの研究室の博士だと思いますが、GCNでけっこう実績を残している人です。僕が一番好きなのは、このWilliam Hamilton先生です。すごく独特の切り口で、毎回グラフのいろいろな問題を扱ってらっしゃいます。