グラフデータを機械学習で扱いやすくするための革新(2/3)

１．グラフデータを機械学習で扱いやすくするための革新(2/3)まとめ

・従来のほとんどの手法は各ノードに対して単一のembeddingが学習されなければならないと仮定している
・現実のネットワークは複数の重複するコミュニティと複数の役割が同時に存在している
・自我ネットワーク分析に基づいた直近の革新を用いて重複問題を解決するSplitter embeddingを開発

２．Splitter embeddingとは？

以下、ai.googleblog.comより「Innovations in Graph Representation Learning」の意訳です。元記事は2019年6月25日、Alessandro EpastoさんとBryan Perozziさんによる投稿です。

複数の社会的繋がりを捕捉可能な特徴表現を学習する
標準的なグラフembedding手法が、ほとんど全てのケースで仮定している事は、各ノードに対して単一のembeddingが学習されなければならないということです。従って、embeddingとは、グラフ内の各ノードを特徴付ける単一の役割または位置を識別しようとする試みと言えます。

しかし、最新の研究では、実際のネットワーク内のノードは複数の重複するコミュニティに属し、複数の役割を果たしていることがわかってきています。あなた自身も「あなたの家族」と「あなたの職場」の両方で役割と繋がりを持っている事からもわかると思います。

この観察は、以下のような研究上の疑問を引き起こします。重複するコミュニティへの参加を表現可能な、各ノードを複数のベクトルにembeddingする手法を開発することは可能ですか？

私たちのWWW’19の論文では、「Splitter」を開発しました。これは、グラフ内のノードに複数のembeddingを持たせて、複数のコミュニティへの参加をより適切にエンコードできるようにする教師なしのembedding手法です。

私達の方法は、自我ネットワーク(ego-network)分析に基づいた直近の革新、重複クラスタリングに基づいており、特にペルソナ(表面的な人格)グラフの概念を使用しています。

この手法はグラフGにおいて、新しいグラフP(ペルソナグラフと呼ばれます)を作成します。ここで、Gの各ノードはペルソナノードと呼ばれる一連の複製によっても表現されます。

ノードの各ペルソナは、それが属するローカルコミュニティ内のノードのインスタンスを表現しています。

グラフ内の各ノードUについて、ノードの自我ネットワークを分析して、そのノードが属するローカルコミュニティを見つけ出します。

例えば、以下の図では、ノードUは2つのコミュニティに属しています。クラスタ１(友人AとBとと共に、Uの家族とします)、クラスタ２(CとDと共に、Uの同僚とします)。

ノードUの自我ネットワーク

次に、この情報を使用して、ノードUをその2つのペルソナU1(家族ペルソナ)とU2(仕事ペルソナ)に「分割」します。これは2つのコミュニティを解きほぐし、それらがもはや重ならないようにします。

2つペルソナでUノードを分離する自我分割法。

このテクニックは、グラフembedding手法における最先端の結果を改善するために使用されています。様々なグラフでリンク予測誤差、(つまり、将来どのノード間にリンクが形成されるかを予測する際の誤差)を最大90％削減します。

この誤差率改善の主な理由は、ソーシャルネットワークや他の現実世界のグラフに見られる極度に重複したコミュニティを明確化にする能力です。

「共著者グラフ」の詳細な分析でこの結果をさらに検証します。このグラフでは著者らは重複する研究コミュニティ、例えば、機械学習とデータマイニングなどに属しています。

左上：コミュニティが極度に重なりあっている典型的なグラフ。
右上：node2vecを使用して左側のグラフのembeddingを作り出す従来手法。
左下：上のグラフのペルソナグラフ。
右下：ペルソナグラフのSplitter embedding。
ペルソナグラフが、重複しているコミュニティを元のグラフと比較して明確に区別出来ていることに注目してください。そして、Splitterは、よく分離された元のグラフを出力します。