Graph Embeddings - The Summary
グラフは現実世界の様々なアプリケーションで使われています。ソーシャルネットワークは相互にフォローし合う人々で構成された巨大なグラフであり、生物学者はタンパク質の相互作用をグラフとして扱いますし、コミュニケーションネットワークもグラフそのものです。テキストマイニングにおける単語の共起ネットワークもグラフとして扱います。グラフ上での機械学習への関心も高まってきています。ソーシャルメディアでは友達予測をしようとする一方、生物学者はタンパク質を機能レベルでの予測を試みています。グラフ上での数学的・統計的操作は難しく、グラフへの機械学習手法の直接的な適用は困難です。この状況で、埋め込みは合理的な解決策となります。
グラフ埋め込みとは何か？
グラフ埋め込みとは、プロパティグラフをベクトル空間に落とし込むことです。埋め込みは、グラフのトポロジー、ノード間の関係性、その他グラフ・部分グラフ・ノードに関するあらゆる情報を保持する必要があります。多くの情報が埋め込まれるほど、後のタスクでいい結果が得られやすくなります。埋め込みの手法は、大きく以下の2つに分けられます。
ノード埋め込み：
各ノードをベクトル表現にエンコードすることができます。ノードレベルでの可視化や予測を行う際に使用されます。
例) ２次元空間でノードを可視化する / ノードの類似性から、新たな関係性を予測する
グラフ埋め込み
各グラフ全体を一つのベクトル空間で表現します。グラフレベルで予測をしたり、グラフ全体の比較や可視化をしたりする際に使用されます。
例）化学構造の比較
後ほど、ノード埋め込みの手法（DeepWalk、node2vec、SDNE）とグラフ埋め込みの手法（graph2vec）を紹介します。
グラフ埋め込みを使う理由は？
グラフは情報を多く含み、それが理解しやすいデータ構造をしています。ですが、グラフ埋め込みが必要になるいくつかの理由があります。
グラフ上での機械学習手法は限られている
グラフはノードとエッジで構成されています。ベクトル空間では数学・統計・機械学習の手法はいくつもありますが、このようなネットワークの関係性で使用できる手法は限られています。
埋め込みは圧縮表現である
グラフでのノード間のつながりを表現できる手法として、隣接行列があります。グラフでのノード数がV個であれば、|V|×|V|次元の行列になります。行列での各行各列がノードを表します。行列で0でない値は、各ノードがつながりを持つことを表します。巨大グラフの特徴空間として隣接行列を使うことは、限りなく不可能に近いです。100万ノードを持つグラフがあるとすれば、100万×100万次元の隣接行列が必要になります。ノードの特徴を小さい次元で扱える点において、埋め込み表現は隣接行列よりも有用だと言えます。
ベクトルの操作はそれに類するグラフの操作よりもシンプルかつ速い
チャレンジ
埋め込みによって満たすべき条件がいくつか存在します。ここでは、埋め込み手法によって満たすべき3つの条件をご紹介します。
・埋め込みがグラフのプロパティを十分に表現している必要がある
グラフのトポロジー、ノード間のつながり、隣接するノードを表現している必要があります。予測・可視化のパフォーマンスは、埋め込みの質にか
かっています。
・グラフの大きさによって埋め込みの速度が遅くなってはならない
たいていの場合、グラフは大規模です。何百万もの人々によって構成されるソーシャルグラフを想像してみてください。
・計算量の増加
多くの次元を埋め込むと（元のグラフに関する）多くの情報を保持できますが、埋め込みに時間がかかり、空間計算量も増加します。ユーザは、要件に応じてトレードオフを図る必要があります。通説では、ほとんどのタスクにおいて128～256次元が効率的であると報告されています。
Word2vecでは、埋め込みの長さを300次元にしています。
（前提知識として）Word2vec
グラフ埋め込みの前に、Word2vecとskip-gramについてご紹介します。これらの手法は、グラフ埋め込みの基礎となる手法です。
Word2vecは、単語をベクトル空間に落とし込む手法です。似ている単語は似ている埋め込みを持つ必要があります。Word2vecはskip-gramを使います。skip-gramとは、隠れ層を1つ持つニューラルネットワークです。skip-gramは、隣接する単語を予測するために学習します。この学習は、学習フェーズでしか使用されないため、フェイクタスクと呼ばれます。skip-gramは、単語を入力とし、隣接する単語を高い確率で予測することができるように最適化されます。以下では、入力単語（緑で色が付いている）と予測される単語の例を示しています。2つの似ている単語は、隣接する単語も似ていると想定されるため、似た埋め込みが得られます。
以下の図で、skip-gramは入力層・1つの隠れ層・出力層を持っています。入力層では、one-hotベクトルで表された単語を入力します。one-hotベクトルは、出現する単語の辞書と同じ長さを持ち、1つ以外は全て0で表されるベクトルです。1は、辞書中でベクトル化された単語が出現するところに表示されます。隠れ層は活性化関数を持たず、出力は（埋め込まれた）単語そのものになります。出力層にはソフトマックス関数がかけられ、隣接する単語を確率的に予測します。skip-gramに関する詳細は、以下の記事が参考になります。
以下では、4つのグラフ埋め込みのアプローチをご紹介します。そのうち3つはノードを埋め込み、1つはグラフ全体を単一ベクトルとして表現します。（ノード埋め込みの）3つの手法においては、Word2vecの埋め込み手法から着想されています。
ノード埋め込みのアプローチ
ここからは、グラフでのノードを埋め込む手法を3つご紹介します。これら3つを選んだ理由は、実用的かついい結果を残しているためです。3つの手法についての紹介に入る前に、ノード埋め込みは3つのグループに分けられることをお伝えします。要素分解のアプローチ・ランダムウォークのアプローチ・深いアプローチの3つです。
DeepWalk
DeepWalkは、埋め込み表現を作り出すためにランダムウォークを使用します。ランダムウォークでは、あるノードを始点とし、隣接するノードへと一定数の移動を行います。
この手法は、大きく3つのプロセスから構成されています。
サンプリング：
ランダムウォークにより、グラフがサンプリングされます。各ノードから32～64回のランダムウォークを行うと効率的であることが報告されています。「良い」ランダムウォークは、40ステップであることも報告されています。
skip-gramモデルの学習：
ランダムウォークは、Word2vecのアプローチにおける文と同じものです。skip-gramでは、ランダムウォークにによって取得したノードをone-hotベクトルの入力として受け付け、隣接するノードを確率的に最大化するように学習します。一般的には、隣接する20個のノード（10個の左側のノードと10個の右側のノード）を予測するように学習します。
埋め込みの計算：
埋め込みは、ネットワークの隠れ層の出力です。DeepWalkでは、グラフ内の各ノードの埋め込みを計算します。
DeepWalkはランダムウォークを「ランダムに」実行します。つまり、埋め込みはあるノードが隣接しているノードの情報をうまく保存できません。この問題を解決したのが、Node2vecです。
Node2vec
Node2vecは、DeepWalkのランダムウォークに微修正を加えたものです。パラメータとしてPとQを持ちます。Pがランダムウォークにおいて辿ったノードに戻る確率を決めるのに対し、Qはまだ辿っていないノードに渡る確率を決めます。Pはノード周辺のごく小さい部分を発見する確率を調整する一方、Qはノード周辺の大域的な部分を発見する確率を調整します。コミュニティと複雑な依存関係を推論します。
埋め込みの他のステップについては、DeepWalkと同じです。
Structural Deep Network Embeddings(SDNE)
ランダムウォークを行わないので、上記2つ（DeepWalk、Node2vec）のアプローチとは全く異なります。ここでSDNEに言及する理由は、あらゆるタスクにおいて、パフォーマンスが非常に安定しているためです。この手法は、埋め込みがローカルな構造(First Order Proximity)とグローバルな構造(Second Order Proximity)を保つように設計されています。ローカルな構造(First Order Proximity)は、エッジによって結ばれたノード同士の近接性であり、ローカルなネットワークの構造を特徴づけています。エッジで結ばれていたら、そのノード同士は似ている、とされています。ある論文が別の論文を引用していたら、両者は同一のトピックについての論文であるのがその一例です。グローバルな構造(Second Order Proximity）は、隣接するノードに着目した近接性です。グローバルな構造に着目した概念であり、2つのノードが共通のノードを多く持っていたら、両ノードは似ている、と言えます。
以下の資料を参考にしてください。
https://www.slideshare.net/KoheiSaito9/what-is-graph-embedding-what-is-sdne
グラフ埋め込みのアプローチ
（この記事で紹介する）最後のアプローチでは、グラフ全体を埋め込みます。グラフをベクトルとして表現し、計算を行います。ここでは、グラフ埋め込みのアプローチで最も良い結果を出しているgraph2vecをご紹介します。
Graph2vec
Graph2vecは、skip-gramを使うDoc2vecのアプローチに着想を得ています。ドキュメントIDを入力層で受け取り、ドキュメントからランダムに単語を推測する確率を最大化するように学習します。
Graph2vecは以下の3つのプロセスから構成されています。
グラフから全ての部分グラフを抽出し、ラベル付けする
部分グラフは、特定のノードの周辺に現れるノードの集まりを指します。部分グラフのノードは、指定したエッジの本数よりも離れていません。
skip-gramモデルの学習
グラフはドキュメントに似ています。ドキュメントは単語の集合でありますが、グラフも部分グラフの集合であるからです。この段階で、skip-gramモデルが学習されます。入力グラフ内に存在する部分グラフを予測する確率を最大化するように学習されます。入力層でのグラフは、one-hotベクトルで表されます。
埋め込みの計算
入力にはグラフIDがone-hotベクトルとして渡されます。埋め込みは、隠れ層の結果で表現されます。
このタスクは部分グラフを予測しているので、似た部分グラフや似た構造を持つグラフ同士は、似た埋め込みを得ることになります。
その他の埋め込みのアプローチ
本記事では、よく使われる文献に基づくアプローチをご紹介してきました。このトピック（グラフ埋め込み）はとても人気があるため、他にもあらゆるアプローチが提唱されています。他のアプローチも一部ご紹介します。
ノード埋め込みのその他の手法
LLE, Laplacian Eigenmaps, Graph Factorization, GraRep, HOPE, DNGR, GCN, LINE
グラフ埋め込みのその他の手法
Patchy-san, sub2vec (embed subgraphs), WL kernel andDeep WL kernels
追記予定
今後は、わかりやすさのために、本記事に図を追記していきたいと思います。