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

「グラフニューラルネットワーク(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にお任せか


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

当メディアは、最新AI技術情報をビジネスマンにも理解できるように「AIをどこよりも分かりやすく!どこよりも身近に!」をコンセプトとした、AI論文翻訳メディアです。

AI関連技術は今、急激な勢いで進化しています。毎日、さまざまな論文が発表され、「最新の手法」が数週間で変わるぐらいその変化は激しいものです。

一方で、AIのビジネス活用の現場には、情報の非対称性が存在します。ビジネスサイドのAI技術に対する理解不足が大きいため、「AIでなんとかなるだろう」という異常な期待値の高さが生まれており、このため、AI事業を目的化してしまい真の課題解決に結びついていません。

新しい技術とそれがもたらす社会の変化を俯瞰的な視点でとらえることは、ビジネスマンのひとつの役割のはずです. しかしことAIに関して言うと、難解なイメージだけが先行してしまし、実態がつかめないと感じる方が多いのではないでしょうか?

このサイトがすこしでもその心理的な障壁を下げ、AIへの理解を深める役割を担えれば幸いです。サイトを眺めながら、この辺が研究トレンドとして熱いんだなとインスピレーションをかきたてるようなサイトになれたらいいなと思っています。

上記のようなメディアを目指して、共に走ってくれるライターを我々は募集しております。
応募対象者は、強い好奇心とAIに関する知見を世の中に広め、AIがより活用される社会を作りたいとビジョンに共感していただいた方すべて受け付けます。

AI-SCHOLARライターに採用されると3つの特典が付きます。
1. ライター同士のコミュニティを運営しており、最新の論文の動向について知ることができます。
2. AI-SCHOLARのライターにのみご紹介されるAI関連の求人案件が多数ございます。
3.講談社が運営するブルーバックスに転載される可能性があり、ライターとしての認知度が向上します。

お名前
必須
ふりがな
必須
生年月日

必須
性別 必須
電話番号 必須
出身校 必須
メールアドレス 必須
ライターとしての意気込み 任意
個人情報のお取扱いについて

ご入力いただいた個人情報は、下記の目的で利用いたします。
・お問合せやご質問に対応するため
・当社が取り扱うサービスのご案内のため

ご入力いただいた情報をシステム上で保管・管理するため、当社の選定基準を満たした事業者に委託する場合がございます。これ以外の場合において、皆様の個人情報をご本人の同意なく第三者に提供することはございません。
ご入力いただいた個人情報に関して、利用目的の通知、個人情報の開示、訂正、追加、削除、利用停止、消去、第三者提供の停止を求めることができます。これらの請求をおこないたい場合は、下記の窓口までご連絡ください。
当社に提供される個人情報の内容は、ご本人様の任意によるものです。 ただし、必要な項目をいただけない場合、適切な対応ができない場合があります。
当社のサービスは、Cookie及びこれに類する技術を利用することがあります。これらの技術は、当社による当社のサービスの利用状況等の把握に役立ち、サービス向上に資するものです。Cookieを無効化されたいユーザーは、ウェブブラウザの設定を変更することによりCookieを無効化することができます。ただし、Cookieを無効化すると、当社のサービスの一部の機能をご利用いただけなくなる場合があります。

【個人情報お問い合わせ窓口】
株式会社wevnal
担当:個人情報保護管理者 CTO 木曽隆
住所:東京都渋谷区渋谷1-11-8 渋谷パークプラザ5F
電話:03-5766-8877