グラフニューラルネットワークと DGL.ai によるグラフ内のリンクの予測

グラフはデータを表現する強力な方法であり、さまざまなアプリケーションにわたるエンティティ間の関係を一意に捉えます。ソーシャル ネットワーク、タンパク質の相互作用、輸送システム、推奨エンジンのいずれをモデル化する場合も、グラフはこれらの複雑な相互依存関係を自然に表現し、分析します。今日のデータ駆動型の世界では、エンティティ間の関係を理解することは、エンティティ自体を理解することと同じくらい重要であることが多く、グラフが真価を発揮するのはこのときです。

リンク予測はグラフ分析の基本的なタスクの 1 つで、ノード (グラフで表現されるエンティティ) 間の接続 (またはリンク) を予測します。ソーシャル ネットワークで新しい友達を推薦したり、学術引用グラフで潜在的なコラボレーションを予測したり、e コマース環境でユーザーと製品間の将来のやり取りを予測したりすることを想像してください。これらはすべて、リンク予測の実際の例です。このタスクは、ネットワークの拡張、不足情報の推測、異常の検出に役立ちます。ユーザー エクスペリエンスの向上から不正検出の改善まで、さまざまなアプリケーションで、リンク予測は成功の重要な要素です。

リンク予測を説明するために、スタンフォード ネットワーク分析プロジェクト (SNAP) のTwitch ソーシャル ネットワーク データセットを使用します。このデータセットは、Twitch ストリーミング プラットフォーム上のユーザー間のソーシャル接続をキャプチャします。ノードは Twitch ユーザーを表し、エッジはそれらの間の友情を表します。データセットは適切に構造化されているため、前処理と操作が簡単です。

手順に従って、プロジェクトの設定方法、データの前処理方法、モデルの構築方法、実際のデータセットでのリンク予測の評価方法を学習します。

グラフニューラルネットワークとディープグラフライブラリ

グラフ構造のデータを扱うには特有の課題があり、ここでグラフ ニューラル ネットワーク(GNN)が役立ちます。GNN は、グラフ データを扱うために特別に設計されたニューラル ネットワークの一種です。固定サイズの入力で動作する従来のニューラル ネットワークとは異なり、GNN は任意のグラフ サイズを処理し、データ内の接続パターンを活用できます。ノードの近隣から情報を集約することにより、GNN はノードの属性とグラフの構造の両方をキャプチャする表現を学習し、ノード分類、リンク予測、グラフ分類などのタスクに非常に効果的です。

Deep Graph Library ( DGL.ai ) は、 GNN を簡単かつ効率的に構築するための強力なツールキットです。DGL を使用すると、開発者は最先端の GNN アーキテクチャを活用して、リンク予測などのさまざまなタスクに取り組むことができます。DGL は、同種グラフと異種グラフの両方を操作するためのさまざまなユーティリティを提供するため、研究者や実務家にとって多目的なツールとなっています。GNN の実装を簡素化することで、DGL を使用すると、基礎となる技術的な複雑さに悩まされることなく、革新的なソリューションの開発に集中できます。

この基礎を念頭に置いて、GNN とDGL.ai を使用してリンク予測モデルの構築に取り掛かりましょう。

プロジェクトの設定

最初のステップは、必要なライブラリをインポートしてプロジェクトをセットアップすることです。

 import json import numpy as np import pandas as pd import dgl from dgl.data import DGLDataset from dgl.nn import SAGEConv import torch import torch.nn as nn from torch.nn.functional import binary_cross_entropy_with_logits, relu, dropout from torch.nn.utils import clip_grad_norm_ from torch.optim.lr_scheduler import ReduceLROnPlateau import itertools import scipy.sparse as sp from sklearn.metrics import roc_auc_score

データの前処理とトレーニングとテストの分割

トレーニング用のデータを準備するには、まず Twitch データセットを読み込み、それをグラフとして表現し、それをトレーニング セットとテスト セットに分割します。 DGLDatasetから継承するカスタム クラスを作成します。これにより、データ読み込みプロセスの構造化とグラフ関連の操作の効率化が促進されます。

1. グラフ データの読み込み: プロセス関数では、データセットからエッジのリストを読み取ります。元のデータセットのエッジは無向 (相互の友情を表す) であるため、逆エッジを追加して、グラフ内の接続が双方向になるようにします。
2. ノード機能の読み込み: 次に、JSON ファイルからノード機能を読み込みます。各ノードには、長さが異なる可能性のある機能のリストがあるため、短い機能リストにはゼロを埋め込んで、すべてのノードで一貫した長さを維持します。

データセットを作成して前処理するコードは次のとおりです。

 # create a dataset that inherits DGLDataset class SocialNetworkDataset(DGLDataset): def __init__(self): super().__init__(name='social_network') def process(self): # load edges edges_df = pd.read_csv('./twitch/ENGB/musae_ENGB_edges.csv') # ensure edges are bidirectional edges_df_rev = edges_df.copy() edges_df_rev.columns = ['to', 'from'] edges_df_rev = edges_df_rev[['from', 'to']] edges_df = pd.concat([edges_df, edges_df_rev], ignore_index=True) edges_df.drop_duplicates(inplace=True) # create a graph using DGL max_node_id = max(edges_df['from'].max(), edges_df['to'].max()) edges_src = torch.from_numpy(edges_df['from'].to_numpy()) edges_dst = torch.from_numpy(edges_df['to'].to_numpy()) self.graph = dgl.graph( (edges_src, edges_dst), num_nodes=max_node_id + 1, ) # load and node features with open('./twitch/ENGB/musae_ENGB_features.json') as f: node_features_dict = json.load(f) # feature lists have various lengths, pad them with zeros max_feature_list_len = max([len(l) for l in node_features_dict.values()]) for k in node_features_dict: if len(node_features_dict[k]) < max_feature_list_len: node_features_dict[k] += [0] * (max_feature_list_len - len(node_features_dict[k])) # set node features in graph node_features_df = pd.DataFrame.from_dict(node_features_dict).T.astype('float64') node_features_np = node_features_df.to_numpy() self.graph.ndata['feat'] = torch.from_numpy(node_features_np).float() def __len__(self): return 1 # only the whole graph is returned def __getitem__(self, idx): return self.graph

グラフデータを読み込むためにデータセットを初期化します。

 # init the dataset dataset = SocialNetworkDataset() g = dataset[0]

次のステップは、トレーニング セットとテスト セットを作成することです。トレーニングとテスト用にエッジを80/20 の比率に分割します。両方のセットに対して、正のサンプル (存在するエッジ)と負のサンプル(存在しないエッジ)の両方を生成します。より大きなグラフの場合は、DGL のdgl.samplingユーティリティが役立ちますが、ここではグラフ全体がメモリに収まります。トレーニング セットとテスト セットを作成するコードは次のとおりです。

 # pick edges for train and test sets (80/20 split) # (for larger graphs, we can use dgl.sampling.negative etc) u, v = g.edges() edge_ids = np.random.permutation(g.num_edges()) test_set_size = int(len(edge_ids) * 0.2) train_set_size = len(edge_ids) - test_set_size # positive samples: existing edges test_positive_u, test_positive_v = u[edge_ids[:test_set_size]], v[edge_ids[:test_set_size]] train_positive_u, train_positive_v = u[edge_ids[test_set_size:]], v[edge_ids[test_set_size:]] # negative samples: nonexistent edges adj = sp.coo_matrix((np.ones(len(u)), (u.numpy(), v.numpy()))) adj_negative = 1 - adj.todense() - np.eye(g.num_nodes()) negative_u, negative_v = np.where(adj_negative != 0) negative_edge_ids = np.random.choice(len(negative_u), g.num_edges()) test_negative_u, test_negative_v = ( negative_u[negative_edge_ids[:test_set_size]], negative_v[negative_edge_ids[:test_set_size]], ) train_negative_u, train_negative_v = ( negative_u[negative_edge_ids[test_set_size:]], negative_v[negative_edge_ids[test_set_size:]], ) # create a training graph by copying the original graph and removing test edges train_g = dgl.remove_edges(g, edge_ids[:test_set_size]) # define positive and negative graphs for train and test sets train_positive_g = dgl.graph((train_positive_u, train_positive_v), num_nodes=g.num_nodes()) train_negative_g = dgl.graph((train_negative_u, train_negative_v), num_nodes=g.num_nodes()) test_positive_g = dgl.graph((test_positive_u, test_positive_v), num_nodes=g.num_nodes()) test_negative_g = dgl.graph((test_negative_u, test_negative_v), num_nodes=g.num_nodes())

モデル: GraphSAGE 畳み込み層と MLP 予測子

Graph Sample and Aggregate (GraphSAGE)畳み込みニューラル ネットワークを使用して、グラフ内の各ノードの構造と特徴の両方をキャプチャするノード表現(埋め込みとも呼ばれます) を学習します。GraphSAGE は、各ノードの近隣から特徴情報を集約して、各ノードの意味のある表現を作成します。近隣集約と呼ばれるこのプロセスにより、モデルはグラフ内の豊富なローカライズされたパターンを学習できます。

各 GraphSAGE レイヤーでは、モデルは集約関数 (この場合は「平均」関数)を適用して近隣ノードから情報を収集し、その情報をノード自体の特徴と組み合わせます。複数の畳み込みレイヤーを積み重ねることで、モデルはますます遠くにあるノードから情報を取得できるようになり、グラフ内の各ノードのビューが効果的に拡張されます。

モデルのパフォーマンスを向上させ、過剰適合を減らすために、各レイヤーの後にドロップアウトを適用します。

次に、 3 つの畳み込み層と、データがどのように流れるかを定義するforward関数を使用して GraphSAGE モデルを構築してみましょう。

 # define the GraphSAGE model with 3 convolutional layers class GraphSAGE(nn.Module): def __init__( self, input_features, hidden_features, output_features, dropout_probability=0.3, ): super(GraphSAGE, self).__init__() self.conv_layer_1 = SAGEConv(input_features, hidden_features, "mean") self.conv_layer_2 = SAGEConv(hidden_features, hidden_features, "mean") self.conv_layer_3 = SAGEConv(hidden_features, output_features, "mean") self.dropout_probability = dropout_probability def forward(self, graph, input_features): # first layer with ReLU activation and dropout h = relu(self.conv_layer_1(graph, input_features)) h = dropout(h, p=self.dropout_probability) # second layer with ReLU activation and dropout h = relu(self.conv_layer_2(graph, h)) h = dropout(h, p=self.dropout_probability) # third layer without dropout h = self.conv_layer_3(graph, h) return h

3 番目のレイヤー ( h ) 以降の出力には、ノードの埋め込みが含まれます。任意の 2 つのノード間のエッジ (またはリンク) の可能性を予測するには、多層パーセプトロン (MLP) 予測子を使用します。この MLP は、2 つのノードの埋め込みを入力として受け取り、それらの間に存在するエッジの確率を示すスコアを計算します。

 # define the MLP predictor class MLPPredictor(nn.Module): def __init__(self, hidden_features): super().__init__() # first linear layer to combine node embeddings self.W1 = nn.Linear(hidden_features * 2, hidden_features) # second linear layer to produce a single score output self.W2 = nn.Linear(hidden_features, 1) def apply_edges(self, edges): # concatenate source and destination node embeddings h = torch.cat([edges.src["h"], edges.dst["h"]], dim=1) # pass through MLP layers to get the edge score score = self.W2(relu(self.W1(h))).squeeze(1) return {'score': score} def forward(self, g, h): with g.local_scope(): g.ndata["h"] = h g.apply_edges(self.apply_edges) return g.edata["score"]

MLP 予測子は次のように動作します。

• 入力サイズ:予測子の入力サイズは、学習したノード埋め込みに基づいています。各エッジは 2 つのノードを接続するため、それらの埋め込み (それぞれのサイズは hidden_features) を連結し、入力サイズは hidden_features * 2 になります。
• レイヤー 1 (W1):このレイヤーは連結された埋め込みを処理し、出力次元を hidden_features に戻して、ノード間の重要な関係情報を保持します。
• レイヤー 2 (W2):この最後のレイヤーは、ノードのペアごとに単一のスカラースコアを生成し、ノード間にエッジが存在する可能性を表します。

この階層化アプローチにより、予測子はノードのペア間の複雑な関係を捕捉し、エッジの存在確率として解釈できるエッジ スコアを計算できます。

損失関数とAUC

モデルを効果的にトレーニングするには、リンク予測におけるモデルのパフォーマンスを定量化できる損失関数が必要です。このタスクはバイナリ分類問題(各リンクが存在するか存在しないか) であるため、損失関数としてバイナリ クロスエントロピー (BCE)を使用します。バイナリ クロスエントロピーは、モデルの予測スコアと実際のラベル (リンクが存在する場合は 1、リンクがない場合は 0) 間の差異を測定します。モデルは確率ではなく生のスコア (ロジット) を出力するため、 _with_logitsバージョンを使用します。このバージョンの BCE は、シグモイド関数とクロスエントロピーを 1 つのステップに組み合わせているため、ロジットを使用する場合により安定しています。

損失を計算するコードは次のとおりです。

 def compute_loss(positive_logits, negative_logits): # concatenate positive and negative scores y_predicted = torch.cat([positive_logits, negative_logits]) # create true labels (1 for existing links, 0 for nonexistent) y_true = torch.cat([torch.ones(positive_logits.shape[0]), torch.zeros(negative_logits.shape[0])]) return binary_cross_entropy_with_logits(y_predicted, y_true)

モデルを評価するために、 ROC 曲線の下の領域 (AUC)メトリックを使用します。AUC は、負のサンプル (存在しないエッジ) が正のサンプルよりもはるかに多い不均衡なデータを効果的に処理するため、リンク予測に適しています。AUC スコアは、モデルが既存のリンクを存在しないリンクよりもどの程度高くランク付けしているかを示します。

AUC を計算するコードは次のとおりです。

 def compute_auc(positive_logits, negative_logits): y_predicted = torch.cat([positive_logits, negative_logits]).detach().numpy() y_true = torch.cat([torch.ones(positive_logits.shape[0]), torch.zeros(negative_logits.shape[0])]).detach().numpy() return roc_auc_score(y_true, y_predicted)

注: detach()使用して計算グラフからテンソルを削除し、勾配に影響を与えずに AUC を計算できるようにします。

モデルのトレーニング

これで、モデルをトレーニングする準備ができました。まず、モデル、予測子、および最適化子をインスタンス化し、トレーニング ループを定義します。また、学習率、非表示層のサイズ、およびドロップアウト率などのハイパーパラメータを指定します。ここではハイパーパラメータの最適化については説明しませんが、損失が横ばい状態になった場合、つまり、設定されたエポック数 (この場合は 25) にわたって損失の減少が止まった場合に、学習率スケジューラを使用して学習率を調整します。これが発生すると、スケジューラは学習率を半分に減らし、モデルの収束をより効率的に行うことができます。

モデルを初期化し、トレーニングを設定するコードは次のとおりです。

 # init the model num_hidden_features = 32 model = GraphSAGE( train_g.ndata['feat'].shape[1], num_hidden_features, num_hidden_features, ) predictor = MLPPredictor(num_hidden_features) # create an optimizer and a learning rate scheduler learning_rate = 0.01 optimizer = torch.optim.Adam( itertools.chain(model.parameters(), predictor.parameters()), lr=learning_rate, ) lr_scheduler = ReduceLROnPlateau(optimizer, mode='min', factor=0.5, patience=25) # train the model num_epochs = 1000 for epoch in range(num_epochs + 1): # forward h = model(train_g, train_g.ndata['feat']) positive_logits = predictor(train_positive_g, h) negative_logits = predictor(train_negative_g, h) loss = compute_loss(positive_logits, negative_logits) # backward optimizer.zero_grad() loss.backward() # clip gradients clip_grad_norm_(model.parameters(), 1.0) optimizer.step() # adjust learning rate based on the loss lr_scheduler.step(loss) # print loss, current learning rate, and AUC if epoch % 100 == 0: last_lr = lr_scheduler.get_last_lr()[0] train_auc = compute_auc(positive_logits, negative_logits) print(f'Epoch: {epoch}, learning rate: {last_lr}, loss: {loss}, AUC: {train_auc}')

コードを実行して出力を調べてみましょう。

 Epoch: 0, learning rate: 0.01, loss: 262.4156188964844, AUC: 0.4934097124994463 Epoch: 100, learning rate: 0.01, loss: 0.5642552375793457, AUC: 0.7473735298706314 Epoch: 200, learning rate: 0.01, loss: 0.4622882306575775, AUC: 0.8431058751115716 Epoch: 300, learning rate: 0.01, loss: 0.40566185116767883, AUC: 0.8777374138645864 Epoch: 400, learning rate: 0.01, loss: 0.38118976354599, AUC: 0.8944719038039551 Epoch: 500, learning rate: 0.01, loss: 0.3690297603607178, AUC: 0.9039401673234729 Epoch: 600, learning rate: 0.005, loss: 0.3579995930194855, AUC: 0.9112366798940639 Epoch: 700, learning rate: 0.005, loss: 0.3557407557964325, AUC: 0.9128097572016495 Epoch: 800, learning rate: 0.005, loss: 0.3510144352912903, AUC: 0.9152937255697913 Epoch: 900, learning rate: 0.00125, loss: 0.3425179123878479, AUC: 0.9202487786553115 Epoch: 1000, learning rate: 0.00015625, loss: 0.3432360589504242, AUC: 0.9198250134354529

ご覧のとおり、モデルは約 0.92 の AUC を達成しており、強力な予測性能を示しています。損失が安定するエポック 500 と 600 の間で学習率が減少することに注目してください。この調整により、より細かい調整が可能になり、損失がわずかに減少します。ある時点以降、損失と AUC が安定し、モデルが収束したことを示します。

テスト データ (トレーニング中に使用されなかったデータ) でモデルを評価し、それが適切に一般化されるかどうかを確認しましょう。

 # evaluate the model on the test data with torch.no_grad(): test_positive_scores = predictor(test_positive_g, h) test_negative_scores = predictor(test_negative_g, h) test_loss = compute_loss(test_positive_scores, test_negative_scores) test_auc = compute_auc(test_positive_scores, test_negative_scores) print(f'Test loss: {test_loss}, Test AUC: {test_auc}')

結果は次のとおりです。

 Test loss: 0.675215482711792, Test AUC: 0.866213400711374

テスト AUC はトレーニング AUC よりわずかに低く、軽度のオーバーフィッティングを示しています。ただし、AUC が 0.866 であることは、モデルが未知のデータに対しても良好なパフォーマンスを発揮していることを示しています。特にオーバーフィッティングが懸念される場合は、ハイパーパラメータをさらに調整することで一般化を改善できる可能性があります。

訓練されたモデルを使用して新しいリンクを予測する

トレーニング済みのモデルを使用すると、グラフ内のノード間のリンクの可能性を予測できるようになりました。すべての可能なノード ペアの予測を生成し、潜在的な新しい接続を識別できるようにします。

1. 候補ノード ペアの生成: まず、自己ループ (ノードからノード自体への接続) を除いて、すべての可能なノード ペアを生成します。これにより、リンク確率を予測する候補ノード ペアが得られます。
2. 候補グラフの作成:次に、これらの候補エッジを使用して DGL グラフを作成し、元のグラフのノード埋め込みを含むモデルを使用します。候補グラフのndata['h']属性に格納されているこれらの埋め込みは、リンク予測の入力として機能します。

これらの手順のコードは次のとおりです。

 # build node pairs, avoid self-loops (with_replacement=False) node_pairs = torch.combinations(torch.arange(g.num_nodes()), r=2, with_replacement=False) candidate_u = node_pairs[:, 0] candidate_v = node_pairs[:, 1] # build a graph with all node pairs candidate_graph = dgl.graph((candidate_u, candidate_v)) candidate_graph_node_embeddings = model(g, g.ndata['feat']) # we use embeddings from the original graph candidate_graph.ndata['h'] = candidate_graph_node_embeddings # use the predictor to predict the existence of links between nodes predicted_scores = predictor(candidate_graph, candidate_graph_node_embeddings)

すべての候補ペアの予測ができたので、特定のノード間のリンク確率を確認できます。たとえば、初期データセットでは直接接続されていないノード 1773 と 7005 間のリンクのスコアと確率を調べてみましょう。

 # find the index of the node pair (1773, 7005) pair_index = torch.where((candidate_u == 1773) & (candidate_v == 7005))[0] print(f'Pair index: {pair_index}') # get the logit score for this pair and compute probability of link existence pair_link_score = predicted_scores[pair_index].item() # logit score print(f'Pair link score: {pair_link_score}') link_probability = torch.sigmoid(torch.tensor(pair_link_score)).item() # apply sigmoid to convert score into probability print(f'Link probability: {link_probability * 100}%')

結果は次のとおりです。

 Pair index: tensor([11066978]) Pair link score: 0.7675977945327759 Link probability: 68.30010414123535%

私たちのモデルによれば、ユーザー 1773 と 7005 の間にリンクが存在する確率は 68.3%です。

結論

この投稿では、ソーシャル グラフ内の新しいリンクを予測するモデルの構築に成功し、リンク予測にグラフ ニューラル ネットワークと DGL を使用する方法を示しました。比較的小規模なデータセットを使用することで、ローカル マシンで効率的に作業できました。ただし、グラフが数百万または数十億のノードとエッジに拡大すると、それらを処理するには、GPU クラスターでの分散トレーニングなどのより高度なソリューションが必要になります。

次のステップでは、大規模なグラフを処理し、クラウド環境でリンク予測を実装するためのアプローチを検討し、これらの手法を本番レベルのデータセットに適用できるようにします。