グラフニューラルネットで、「つながり」からコミュニティが見えてくる

「グラフニューラルネットワーク(GNN)」をご存知でしょうか。その名の通りグラフ構造を持つデータに有効なディープラーニング手法で、2年ほど前から盛んに扱われるようになった比較的新しいAI分野です。今回はこちらの論文を基に、GNNの改良版とそれが得意とする実践的なコミュニティ検出手法を紹介します。

本日取り上げる論文

目次
(1) グラフニューラルネット(GNN)
(2) LGNN
1.GNNの限界
2.線グラフ、マルチスケール化
3.結果
(3)まとめ

(1) グラフニューラルネットワーク(GNN)

「グラフニューラルネットワーク(GNN)/グラフ畳み込みネットワーク(GCN)」とは、グラフ構造を扱うニューラルネットワークです。

GNNは、画像認識の分野で用いられる「畳み込みニューラルネットワーク(CNN)」を基に開発されたもので、SNSでのつながり情報や辞書のような階層的な情報、さらには薬品の構造式など、様々なグラフ情報を扱うことができます。

以下の動画はGNNの役割を視覚的に表現したものです。

これは、34人の友好関係からそれぞれのメンバーが所属するグループを推定するというもので、グラフの頂点が各メンバー、辺が友好関係、色がグループを表しています。

GNNはグラフ構造と各グループの代表者1人ずつを教えられると、グラフの構造だけから残りの人が所属するグループを綺麗に推定することができてしまいます。

上の例はとてもシンプルなものでしたが、このようにGNNはグラフの構造から有益な情報を抽出することに優れており、グラフ構造を持つ複雑なデータに対していかにGNNを適用するかという研究が現在盛んに行われており、社会実装も進み始めています。

(2) LGNN

1. GNNの限界

GNNはまだ比較的新しい分野ということもあり、扱えないグラフや性能を発揮できないグラフがありました。

まずひとつが有向グラフです。一方通行の道路のように、頂点から頂点へ一方的な関係を持つような辺を持つグラフを「有向グラフ」といいます(逆に方向を持たない辺だけで構成されるグラフを「無向グラフ」といいます)。例えばSNSのつながり関係でも「AさんはBさんをフォローしているけどBさんはAさんをフォローしていない」というような状態が有向な関係と言えます。

そして次に上げられるのが大きいグラフです。これは冒頭でGNNはCNNを模したものだと紹介しましたがそれが原因とも言えます。CNNは、例えば人の顔を認識する際は「ここが目でここが鼻で…」というように部分部分の特徴を掴んで行くことを基本的な戦略としていますが、GNNも同じように局所局所の特徴を掴むことが得意です。具体的には、「この人の周りにはたくさん人が集まっていて人気者に違いない!」や、「この人は人気者と人気者の間にいるぞ、重要な人物に違いない!」などといったことを抽出していると考えられています。しかし既存のGNNでは、「3人のつながりを辿っても繋がらない人同士の関係性は考慮できない」というように考慮できる関係性の範囲に限界があったため、本当は大事だったかもしれない大きなスケールでの情報を抽出できませんでした。

これらの課題を解決したのが今回紹介する論文の主な貢献となっています。

(2) 線グラフ、マルチスケール化

さてここからが論文の提案です。今回の論文はかなり数学力を必要とする内容でしたが、ぜひイメージを掴んでいただければと思います。

まず有向グラフへの対応です。これには主に線グラフという考え方を導入することで、無向グラフ, 有向グラフに関係なく一般的に高い性能を発揮しうるモデルにしています。

https://en.wikipedia.org/wiki/Line_graph

(図の一番左が通常のグラフ、一番右が線グラフ)

線グラフは、グラフの頂点ではなく辺に情報が詰まっているというコンセプトのもと開発されたものです。通常のグラフと線グラフを組み合わせて使うことで、「頂点の情報」と「頂点から頂点への情報の流れ」という2種類の情報を扱えるようにしています。

次がマルチスケール化です。

少し唐突ですが『六次の隔たり』という言葉をご存知でしょうか。これは「何事にも6回関係する物事をたどれば繋がっている」というもので、「友達の友達の友達の…」と6人の友達をたどれば世界中の任意の人物との関係を主張できる、というような事象を指しており、実際にいくつかの仮説を置けば理論的に正しいことが知られています。

これと同じようなスケールの捉え方を基に、論文ではある頂点から指数関数的なスケールで考慮する頂点の範囲を順に広げて行くことで全体のグラフ構造を少ない計算ステップで見渡せるような工夫がされています。

論文では、その他いくつかの細かい工夫を施したGNNをLGNN(Line Graph Neural Networks)と呼んでいます。

(3) 結果

論文内で示されたいくつかの実験のうち、ライターが一番直感的だと感じた「YouTubeデータセット」を使ったものを紹介します。(この実験自体は無向グラフを扱うものとなっています)

YouTubeには動画を見ながらグループチャットを楽しめる機能があるそうなのですが、「ユーザー」を頂点、「(一つ以上の)同じグループに属しているか否か」というつながり情報を辺、「各ユーザーが属しているすべてのグループ」を各頂点が持つ情報として、グラフの構造だけからユーザーが属しているグループを推論する、という問題設定になっています。

論文の提案手法「LGNN」が、既存のディープラーニングを使わない手法「AGMFit」にかなり有意な差を付けていることがわかります。

この実験は、直感的には「つながり」情報だけからコミュニティを浮き上がらせることに成功しており、これを使って「人物のつながり状態の評価」、「コミュニティの規模の数値化」などを客観的に行うことができると考えられます。

(3) まとめ

このようにGNNは拡張することでいろいろな問題に適用することができ、他のAI分野と同様、様々なタスクにおいて既存のヒューリスティックな手法を凌駕していくことは間違いないでしょう。

一口に「グラフ」と言ってもグラフで表現できるものは多種多様であり、今回取り上げたものに限らず、少し変わったものをグラフで表現してみることで新しいGNNの使い方が切り拓かれるかもしれません。


AIメディアライターを大募集中!

ライターとして早速働きたいライター希望で、まずは相談したいライターではなく、メディアディレクターをやりたいその他