グラフ埋め込みの概要: ノード、エッジ、グラフの埋め込み方法と Python の実装

グラフベースの機械学習は、近年大きく進歩しました。グラフベースの手法は、リンク予測、コミュニティ発見、ノード分類など、データ サイエンスにおける多くの一般的な問題に応用できます。問題を解決するには、問題を整理する方法と所有するデータに応じてさまざまな方法があります。この記事では、グラフベースの埋め込みアルゴリズムの概要を説明します。最後に、Python ライブラリ (node2vec など) を使用してグラフ上にさまざまな埋め込みを生成する方法も紹介します。

#グラフベースの機械学習

人工知能には、レコメンデーション システム、時系列、自然言語に至るまで、さまざまな分野があります。処理、コンピュータビジョン、グラフ機械学習などグラフベースの機械学習に関する一般的な問題を解決するには、いくつかの方法があります。コミュニティ発見、リンク予測、ノード分類などが含まれます。

グラフ上の機械学習の主な問題は、機械学習モデルがグラフの構造を簡単に利用できるようにグラフの構造を表現 (またはエンコード) する方法を見つけることです [1]。通常、機械学習でこの問題を解決するには、モデルに関連付けられた構造化された表形式のデータを通じて、ある種の表現を学習する必要があります。これまでは、統計測定またはカーネル関数を通じて行われていました。近年の傾向は、グラフをエンコードして機械学習モデルをトレーニングするための埋め込みベクトルを生成する傾向にあります。

機械学習モデルの目標は、データセット内のパターンを大規模に学習して認識できるように機械をトレーニングすることです。グラフは他の形式のデータ (テキスト、オーディオ、画像など) にはない異なる複雑な構造を提供するため、グラフを操作する場合、これはさらに顕著になります。グラフベースの機械学習は、繰り返し発生する根本的なパターンを検出して説明できます [2]。

私たちは、ソーシャル ネットワーク上のユーザーに関連する人口統計情報を決定することに興味があるかもしれません。人口統計データには、年齢、性別、人種などが含まれます。 Facebook や Twitter などの企業のソーシャル メディア ネットワークは、数百万から数十億のユーザーと数兆の面に及びます。このネットワークには、人間やアルゴリズムでは簡単に検出できないユーザーの人口統計に関連するパターンがいくつか存在することは間違いありませんが、モデルはそれらを学習できるはずです。同様に、ユーザーのペアに友達になるよう勧めたい場合もありますが、まだ友達ではありません。これは、グラフベースの機械学習のもう 1 つのアプリケーションであるリンク予測の材料となります。

グラフの埋め込みとは何ですか?

特徴エンジニアリングとは、入力データを処理して、元のデータ セットのコンパクトで意味のある表現を提供する一連の特徴を形成する一般的な方法を指します。特徴エンジニアリング フェーズの結果は、機械学習モデルへの入力として機能します。これは、表形式の構造化データ セットを操作する場合には必要なプロセスですが、グラフ データを操作する場合は、すべてのグラフ データに関連付けられた適切な表現を生成する方法を見つける必要があるため、実行するのは困難なアプローチです。

グラフから構造情報を表す特徴を生成するには、さまざまな方法があります。最も一般的で簡単な方法は、グラフから統計を抽出することです。これには、認識分布、ページランク、中心性メトリクス、jaccard スコアなどが含まれます。次に、必要な属性がカーネル関数を介してモデルに組み込まれますが、カーネル関数の問題は、結果の生成に伴う時間の複雑さが高いことです。

最近の研究傾向は、意味のあるグラフ表現を見つけてグラフの埋め込み表現を生成することに移行しています。これらの埋め込みは、ネットワークの元の構造を保存するグラフ表現を学習します。これは、離散グラフを連続領域に変換するために設計されたマッピング関数と考えることができます。関数を学習したら、それをグラフに適用し、結果のマッピングを機械学習アルゴリズムの特徴セットとして使用できます。

グラフ埋め込みのタイプ

グラフの分析は 3 つの粒度レベルに分解できます。ノードレベル、エッジレベル、グラフレベル（グラフ全体）。各レベルは、埋め込みベクトルを生成する異なるプロセスで構成されており、選択されるプロセスは問題と処理されるデータに依存する必要があります。以下に示す粒度レベルの埋め込みには、それぞれを視覚的に区別するための図が付いています。

ノードの埋め込み

ノード レベルでは、グラフ内の各ノードに関連付けられた埋め込みベクトルが生成されます。この埋め込みベクトルは、グラフの表現と構造に対応できます。基本的に、互いに近いノードには、互いに近いベクトルも必要です。これは、Node2Vec などの一般的なノード埋め込みモデルの基本原則の 1 つです。

エッジ埋め込み

エッジ層では、グラフ内の各エッジに関連する埋め込みベクトルが生成されます。リンク予測問題は、エッジ埋め込みを使用する一般的なアプリケーションです。リンク予測とは、エッジがノードのペアを接続しているかどうかの可能性を予測することを指します。これらの埋め込みは、グラフによって提供されるエッジ プロパティを学習できます。たとえば、ソーシャル ネットワーク グラフでは、年齢層や性別などに基づいてノードをエッジで接続できるマルチエッジ グラフを作成できます。これらのエッジのプロパティは、エッジの相関ベクトルを表すことで学習できます。

グラフの埋め込み

グラフレベルの埋め込みは一般的ではなく、各グラフを表す埋め込みベクトルの生成で構成されます。たとえば、複数のサブグラフを含む大きなグラフでは、対応する各サブグラフにグラフ構造を表す埋め込みベクトルがあります。分類問題は、グラフの埋め込みが役立つ一般的なアプリケーションです。この種の問題には、グラフを特定のカテゴリに分類することが含まれます。

Python の実装

Python コードを使用して、必要な次のライブラリを実装します

Pythnotallow=3.9
 networkx>=2.5
 pandas>=1.2.4
 numpy>=1.20.1
 node2vec>=0.4.4
 karateclub>=1.3.3
 matplotlib>=3.3.4

そうでない場合node2vec パッケージがインストールされている場合は、そのドキュメントを参照してください。 karateclub パッケージをインストールします。これも

ノードの埋め込み

import random
 import networkx as nx
 import matplotlib.pyplot as plt
 
 from node2vec import Node2Vec
 from node2vec.edges import HadamardEmbedder
 from karateclub import Graph2Vec
 
 plt.style.use("seaborn")
 
 # generate barbell network
 G = nx.barbell_graph(
m1 = 13,
m2 = 7
 )
 
 # node embeddings
 def run_n2v(G, dimensions=64, walk_length=80, num_walks=10, p=1, q=1, window=10):
"""
Given a graph G, this method will run the Node2Vec algorithm trained with the
appropriate parameters passed in.
 
Args:
G (Graph) : The network you want to run node2vec on
 
Returns:
This method will return a model
 
Example:
G = np.barbell_graph(m1=5, m2=3)
mdl = run_n2v(G)
"""
 
mdl = Node2Vec(
G,
dimensions=dimensions,
walk_length=walk_length,
num_walks=num_walks,
p=p,
q=q
)
mdl = mdl.fit(window=window)
return mdl
 
 mdl = run_n2v(G)
 
 # visualize node embeddings
 x_coord = [mdl.wv.get_vector(str(x))[0] for x in G.nodes()]
 y_coord = [mdl.wv.get_vector(str(x))[1] for x in G.nodes()]
 
 plt.clf()
 plt.scatter(x_coord, y_coord)
 plt.xlabel("Dimension 1")
 plt.ylabel("Dimension 2")
 plt.title("2 Dimensional Representation of Node2Vec Algorithm on Barbell Network")
 plt.show()

上の図は、によって生成された視覚的なノードの埋め込みです。バーベル グラフには、node2vec、ディープ ウォーク、ランダム ウォークなど、ノードの埋め込みを計算するための多くの方法があります。ここではnode2vecが使用されます。

エッジ埋め込み

edges_embs = HadamardEmbedder(
keyed_vectors=mdl.wv
 )
 
 # visualize embeddings
 coordinates = [
edges_embs[(str(x[0]), str(x[1]))] for x in G.edges()
 ]
 
 plt.clf()
 plt.scatter(coordinates[0], coordinates[1])
 plt.xlabel("Dimension 1")
 plt.ylabel("Dimension 2")
 plt.title("2 Dimensional Representation of Edge Embeddings on Barbell Network")
 plt.show()

バーベル グラフによるエッジ埋め込みの視覚化を表示します。Hammard Embedder のソース コードはここにあります。 (https://github.com/eliorc/node2vec/blob/master/node2vec/edges.py#L91)。

グラフ埋め込み

n_graphs = 10
 Graphs = [
nx.fast_gnp_random_graph(
n = random.randint(5,15),
p = random.uniform(0,1)
) for x in range(n_graphs)
 ]
 
 g_mdl = Graph2Vec(dimensions=2)
 g_mdl.fit(Graphs)
 g_emb = g_mdl.get_embedding()
 
 x_coord = [vec[0] for vec in g_emb]
 y_coord = [vec[1] for vec in g_emb]
 
 plt.clf()
 plt.scatter(x_coord, y_coord)
 plt.xlabel("Dimension 1")
 plt.ylabel("Dimension 2")
 plt.title("2 Dimensional Representation of Graph Embeddings on Randomly Generated Networks")
 plt.show()

これは、ランダムに生成されたグラフのグラフ埋め込み視覚化です。graph2vec アルゴリズムのソース コードは次のとおりです。ここで見つかります。 (https://karateclub.readthedocs.io/en/latest/_modules/karateclub/graph_embedding/graph2vec.html)

概要

埋め込みは、離散グラフをベクトル表現にマッピングする関数です。グラフ データ、ノード エンベディング、エッジ エンベディング、グラフ エンベディングからさまざまな形式のエンベディングを生成できます。 3 種類の埋め込みはすべて、グラフの初期構造と特徴を X 次元の数値にマッピングするベクトル表現を提供します。

以上がグラフ埋め込みの概要: ノード、エッジ、グラフの埋め込み方法と Python の実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。