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

「グラフニューラルネットワーク(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-SCHOLAR」では現在、このようなビジョンに共感してくれるエンジニアや研究者のライターを募集しています。

論文紹介から、コラム、動向紹介まで様々なジャンルでの募集です。
署名記事で書いて頂き、自分の会社やブログへのリンクを貼って頂くのもOK。
自社のブランディングや知名度アップに使って頂いても構いません。

自分ならもっと良いコンテンツが書けるのに。。という想いを一度でも感じたことがある人であれば、まずはAI-SCHOLARライターの扉を叩いて下さい。

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

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

株式会社wevnal(以下「当社」といいます。)は、AI-SCHOLAR(以下「本サイト」といいます。)をご利用になる方(以下「ユーザー」といいます。)の個人情報保護の重要性について認識し、個人情報の保護に関する法律(以下「個人情報保護法」といいます。)を遵守すると共に、以下のプライバシーポリシー(以下「本プライバシーポリシー」といいます。)に従い、適切に取り扱うものとします。

1. 個人情報の定義

本プライバシーポリシーにおいて、個人情報とは、生存する個人に関する情報であって、当該情報に含まれる氏名、生年月日その他の記述等により特定の個人を識別することができるもの(他の情報と容易に照合することができ、それにより特定の個人を識別することができることとなるものを含みます。)を意味するものとします。

2. 個人情報の利用目的

当社は、ユーザーの個人情報を、以下の目的で利用いたします。
(1)本サイトのサービス提供のため
(2)本サイトの利用に伴うご案内のため
(3)本サイトのサービスに関するご意見、お問い合せ等への対応のため
(4)メールマガジン・DM・各種お知らせ等の配信・送付のため
(5)ユーザーの承諾・申込みに基づく、本サイト掲載企業等への個人情報の提供のため
(4)当社の商品、サービス等のご案内のため
(5)当社のサービスに関する当社の規約、ポリシー等に違反する行為への対応のため
(6)当社のサービスの改善、新サービスの開発、マーケティング等のため

3. 個人情報の第三者への提供

当社は、ユーザーの同意を得て、以下の提供先に、以下の提供情報内容を以下の手段又は方法で提供することがあります。
(1)提供先について
登録ユーザーが本サイトにおいて資料の請求、閲覧もしくはダウンロードする場合、その資料の提供元である本サイト掲載企業(当該提供元企業から委託を受けた者を含みます。なお、所属企業ではなく、企業に所属する個人が提供元である場合もあります。)に、以下の情報が提供されます。
(2)提供情報内容
ユーザーから取得した情報
(3)提供の手段又は方法
電磁的な方法による送信

また、次に掲げる場合は、関係法令に反しない範囲で、ユーザーの同意なく個人情報を第三者に提供することがあります。
(1) 法令により許容されている場合
(2) ユーザーが第三者に不利益を及ぼすと判断した場合
(3) 公衆衛生の向上または児童の健全な育成の推進のために特に必要がある場合であって、ユーザー本人の承諾を得ることが困難である場合
(4) 国の機関若しくは地方公共団体またはその委託を受けた者が法令の定める事務を遂行することに対して協力する必要がある場合で、ユーザー本人の同意を得ることによりその事務の遂行に支障を及ぼすおそれがある場合
(5) 裁判所、検察庁、警察またはこれらに準じた権限を有する機関から、個人情報についての開示を求められた場合
(6) 合併その他の事由による事業の承継に伴って個人情報が提供される場合であって、承継前の利用目的の範囲内で利用する場合

4. 個人情報取扱業務の外部委託

当社は、個人情報取扱業務の一部または全部を外部委託することがあります。なお、委託先における個人情報の取扱いについては当社が責任を負います。

5. 統計データの利用

当社は、個人を特定できないよう加工した統計データを作成することがあります。当社は、統計データを何ら制限なく利用することができるものとします。

6. 個人情報の開示・訂正・利用停止等

原則として、ユーザーご本人に限り、個人情報の開示、訂正、追加または削除、利用停止、ならびに第三者への提供の停止(以下「個人情報の開示等」といいます)を求めることができるものとします。ただし、以下の場合は個人情報の変更等に応じないことがあります。
(1) ユーザー本人または第三者の生命、身体、財産その他の権利・利益を害するおそれがある場合
(2) 当社のサービスの適正な実施に著しい支障を及ぼすおそれがある場合
(3) 他の法令に違反することとなる場合
また、当該個人情報の変更等に多額の費用を要する場合、その他の、個人情報の開示等を行うことが困難な場合であって、ユーザーの権利・利益を保護するため必要なこれに代わるべき措置をとるときは、個人情報の変更等に応じないことがあります。

7.  Cookie(クッキー)その他の技術の利用

当社サービスは、Cookie及びこれに類する技術を利用することがあります。これらの技術は、当社による当社サービスの利用状況等の把握に役立ち、サービス向上に資するものです。Cookieを無効化されたいユーザーは、ウェブブラウザの設定を変更することによりCookieを無効化することができます。但し、Cookieを無効化すると、当社サービスの一部の機能をご利用いただけなくなる場合があります。

8. お問い合わせ

開示等のお申出、ご意見、ご質問、苦情のお申出その他個人情報の取扱いに関するお問い合わせは、以下の個人情報管理責任者までお願い致します。

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

9. プライバシーポリシーの変更

当社は、法令等の定めがある場合を除き、必要に応じて、本プライバシーポリシーを変更することができるものとします。

10. プライバシーマークに関して

当社は、プライバシーマークの認証を取得しています。
認証番号:21004560(01)

制定年月日   2011年4月1日
最終改訂年月日 2019年10月1日

この記事をシェアする