Predikce odkazů v grafech pomocí Graph Neuron Networks a DGL.ai

Grafy představují účinný způsob, jak reprezentovat data, jedinečně zachycující vztahy mezi entitami v celé řadě aplikací. Ať už modelujete sociální sítě, proteinové interakce, dopravní systémy nebo doporučovací nástroje, grafy přirozeně reprezentují a analyzují tyto složité vzájemné závislosti. V dnešním světě založeném na datech je porozumění vztahům mezi entitami často stejně důležité jako pochopení entit samotných – zde grafy skutečně září.

Predikce spojení je jedním ze základních úkolů v grafové analýze, který zahrnuje predikci spojení (nebo vazeb) mezi uzly (entitami znázorněnými v grafu). Představte si doporučování nových přátel na sociální síti, předpovídání potenciální spolupráce v akademickém citačním grafu nebo předpovídání budoucích interakcí mezi uživateli a produkty v prostředí elektronického obchodu – to vše jsou příklady predikce odkazů v akci. Tento úkol pomáhá rozšiřovat sítě, odvodit chybějící informace a odhalit anomálie. Pro aplikace, od vylepšování uživatelského zážitku až po zlepšení detekce podvodů, je predikce odkazů klíčovou složkou úspěchu.

Pro ilustraci predikce odkazů použijeme datovou sadu Twitch Social Network z projektu Stanford Network Analysis Project (SNAP). Tato datová sada zachycuje sociální spojení mezi uživateli na streamovací platformě Twitch, kde uzly představují uživatele Twitche a hrany představují přátelství mezi nimi. Datový soubor je dobře strukturovaný, což usnadňuje předzpracování a práci s ním.

Tím, že budete postupovat dále, se naučíte, jak nastavit projekt, předzpracovat data, vytvořit model a vyhodnotit je pro predikci propojení v reálném datovém souboru.

Grafové neuronové sítě a knihovna hlubokých grafů

Práce s grafově strukturovanými daty představuje jedinečné výzvy a zde přichází na řadu grafové neuronové sítě (GNN) . GNN jsou typem neuronové sítě speciálně navržené pro práci s grafovými daty. Na rozdíl od tradičních neuronových sítí, které fungují na vstupu s pevnou velikostí, mohou GNN zpracovávat libovolné velikosti grafů a využívat vzory připojení v datech. Agregací informací od sousedů uzlu se GNN učí reprezentace, které zachycují jak atributy uzlů, tak strukturu grafu, což je činí vysoce efektivními pro úkoly, jako je klasifikace uzlů, predikce odkazů a klasifikace grafů.

Deep Graph Library ( DGL.ai ) je mocná sada nástrojů pro snadné a efektivní vytváření GNN. S DGL mohou vývojáři využít nejmodernější architektury GNN k řešení různých úkolů, včetně predikce odkazů. DGL poskytuje řadu nástrojů pro práci s homogenními i heterogenními grafy, což z něj činí všestranný nástroj pro výzkumníky i odborníky z praxe. Zjednodušením implementace GNN vám DGL umožňuje zaměřit se více na vývoj inovativních řešení, než abyste se zabředli do základních technických složitostí.

S ohledem na tento základ se pojďme ponořit do vytváření modelu predikce spojení pomocí GNN a DGL.ai .

Nastavení projektu

Prvním krokem je nastavení našeho projektu importem požadovaných knihoven:

 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

Předzpracování dat a rozdělení vlak-test

Abychom připravili data pro trénink, nejprve načteme datovou sadu Twitch, znázorníme ji jako graf a poté ji rozdělíme na tréninkové a testovací sady. Vytvoříme vlastní třídu, která zdědí z DGLDataset , což pomůže strukturovat proces načítání dat a zjednodušit operace související s grafy.

1. Načítání dat grafu : Ve funkci procesu začneme načtením seznamu hran z datové sady. Vzhledem k tomu, že hrany v původním datovém souboru jsou neorientované (představující vzájemná přátelství), přidáme opačné hrany, abychom zajistili, že spojení budou v našem grafu obousměrná.
2. Načítání funkcí uzlu : Dále načteme funkce uzlu ze souboru JSON. Každý uzel má seznam prvků, které se mohou lišit délkou, takže kratší seznamy prvků doplníme nulami, abychom zachovali stejnou délku ve všech uzlech.

Zde je kód pro vytvoření a předběžné zpracování datové sady:

 # 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

Nyní inicializujeme naši datovou sadu, abychom načetli data grafu.

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

Dalším krokem je vytvoření tréninkových a testovacích sad . Pro trénování a testování rozdělíme okraje v poměru 80/20 . Generujeme jak pozitivní (existující hrany), tak negativní vzorky (neexistující hrany) pro obě sady. Pro větší grafy mohou být užitečné nástroje DGL dgl.sampling , ale zde se celý graf vejde do paměti. Zde je kód pro vytvoření školicích a testovacích sad:

 # 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())

Model: GraphSAGE Convolutional Layers a MLP Predictor

Použijeme konvoluční neuronovou síť Graph Sample and Aggregate (GraphSAGE) , abychom se naučili reprezentace uzlů, známé také jako vložení , které zachycují jak strukturu, tak vlastnosti každého uzlu v grafu. GraphSAGE funguje tak, že agreguje informace o funkcích ze sousedů každého uzlu a vytváří smysluplnou reprezentaci pro každý uzel. Tento proces, známý jako sousedská agregace , umožňuje modelu naučit se bohaté, lokalizované vzory v grafu.

V každé vrstvě GraphSAGE model aplikuje agregační funkci (v tomto případě „střední“ funkci) ke sběru informací ze sousedních uzlů, které jsou pak kombinovány s vlastními vlastnostmi uzlu. Skládání více konvolučních vrstev umožňuje modelu zachytit informace ze stále vzdálenějších uzlů , čímž se efektivně rozšiřuje pohled každého uzlu v grafu.

Abychom zvýšili výkon modelu a omezili přesazení, použijeme po každé vrstvě výpadek .

Pojďme nyní sestavit model GraphSAGE se třemi konvolučními vrstvami spolu s forward funkcí, která definuje, jak přes něj protékají data:

 # 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

Výstup za třetí vrstvou ( h ) obsahuje vložení uzlů. K předpovědi pravděpodobnosti hrany (nebo spojení) mezi jakýmikoli dvěma uzly použijeme prediktor Multi-Layer Perceptron (MLP) . Tato MLP bere vložení dvou uzlů jako vstup a vypočítává skóre udávající pravděpodobnost, že mezi nimi existuje hrana.

 # 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"]

Prediktor MLP funguje následovně:

• Vstupní velikost: Vstupní velikost prediktoru je založena na naučených vloženích uzlů. Protože každá hrana spojuje dva uzly, zřetězíme jejich vložení (každý o velikosti hidden_features), což vede ke vstupní velikosti hidden_features * 2.
• Vrstva 1 (W1): Tato vrstva zpracovává zřetězená vložení a redukuje výstupní dimenzi zpět na hidden_features, přičemž zachovává důležité relační informace mezi uzly.
• Vrstva 2 (W2): Tato finální vrstva vytváří jediné skalární skóre pro každý pár uzlů, které představuje pravděpodobnost existence hrany mezi nimi.

Tento vrstvený přístup umožňuje prediktoru zachytit složité vztahy mezi páry uzlů a vypočítat skóre hrany, které lze interpretovat jako pravděpodobnost existence hrany.

Ztrátová funkce a AUC

Abychom náš model efektivně trénovali, potřebujeme ztrátovou funkci, která dokáže kvantifikovat výkon modelu na predikci spojení. Vzhledem k tomu, že tato úloha je problémem binární klasifikace – kde každý odkaz buď existuje nebo neexistuje – používáme jako ztrátovou funkci binární křížovou entropii (BCE) . Binární křížová entropie měří nesrovnalost mezi předpokládanými skóre modelu a skutečnými štítky (1 pro existující odkaz, 0 pro žádný odkaz). Používáme verzi _with_logits , protože náš model poskytuje spíše nezpracovaná skóre (logits) než pravděpodobnost. Tato verze BCE je stabilnější při práci s logity, protože kombinuje sigmoidní funkci a křížovou entropii do jednoho kroku.

Zde je kód, který počítá ztrátu:

 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)

K vyhodnocení modelu používáme metriku Area Under the ROC Curve (AUC) . AUC se dobře hodí pro predikci spojení, protože efektivně zpracovává nevyvážená data , kde jsou negativní vzorky (neexistující hrany) mnohem častější než pozitivní vzorky. Skóre AUC nám dává představu o tom, jak dobře model řadí existující odkazy výše než neexistující.

Zde je kód pro výpočet 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)

Poznámka: K odstranění tenzorů z výpočtového grafu používáme detach() , což nám umožňuje vypočítat AUC bez ovlivnění gradientů.

Trénink modelu

Nyní jsme připraveni trénovat model. Nejprve vytvoříme instanci modelu, prediktoru a optimalizátoru a definujeme trénovací smyčku . Kromě dalších hyperparametrů také určíme rychlost učení, velikost skryté vrstvy a míru výpadků. I když se zde nebudeme zabývat optimalizací hyperparametrů , použijeme plánovač rychlosti učení k úpravě rychlosti učení, pokud se ztráta ustálí – to znamená, že přestane klesat po nastavený počet epoch (v tomto případě 25). Plánovač sníží rychlost učení na polovinu, když k tomu dojde, což může pomoci modelu efektivněji konvergovat.

Zde je kód pro inicializaci modelu a nastavení školení:

 # 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}')

Spusťte kód a prozkoumejte výstup:

 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

Jak můžeme vidět, model dosahuje AUC kolem 0,92, což ukazuje na silný prediktivní výkon . Všimněte si, že rychlost učení se sníží mezi epochami 500 a 600, když se ztráta stabilizuje. Toto nastavení umožňuje jemnější ladění, což vede k malému snížení ztrát. Po určitém okamžiku se ztráta a AUC stabilizují, což naznačuje, že model konvergoval .

Vyhodnoťme model na testovacích datech (která nebyla použita během tréninku) a uvidíme, zda dobře zobecňuje:

 # 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}')

Výsledkem je:

 Test loss: 0.675215482711792, Test AUC: 0.866213400711374

Testovací AUC je o něco nižší než tréninkové AUC, což ukazuje na drobné přesazení. Avšak AUC 0,866 ukazuje, že model stále funguje dobře na neviditelných datech . Další ladění hyperparametrů by mohlo zlepšit zobecnění, zvláště pokud je problémem přefitování.

Použití trénovaného modelu k predikci nových odkazů

S naším trénovaným modelem nyní můžeme předpovídat pravděpodobnost spojení mezi uzly v grafu. Vygenerujeme předpovědi pro všechny možné dvojice uzlů , což nám umožní identifikovat potenciální nová spojení.

1. Generování kandidátských párů uzlů : Nejprve vygenerujeme všechny možné páry uzlů, s výjimkou vlastních smyček (spojení z uzlu k sobě samému). To nám dává kandidátní páry uzlů, pro které chceme předpovědět pravděpodobnosti spojení.
2. Vytvoření kandidátského grafu: Poté vytvoříme DGL graf s těmito kandidátskými hranami a použijeme model s vloženými uzly z původního grafu. Tato vložení, uložená v atributu ndata['h'] kandidátského grafu, budou sloužit jako vstupy pro predikci spojení.

Zde je kód pro tyto kroky:

 # 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)

Nyní, když máme předpovědi pro všechny kandidátské páry, můžeme zkontrolovat pravděpodobnost spojení mezi libovolnými konkrétními uzly . Podívejme se například na skóre a pravděpodobnost spojení mezi uzly 1773 a 7005, které nejsou přímo propojeny v počáteční sadě dat:

 # 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}%')

Toto je výsledek:

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

Podle našeho modelu existuje 68,3% pravděpodobnost propojení mezi uživatelem 1773 a 7005 .

Závěr

V tomto příspěvku jsme úspěšně vytvořili model pro predikci nových odkazů v sociálním grafu, demonstrující použití Graph Neural Networks a DGL pro predikci odkazů. Použití relativně malé datové sady nám umožnilo efektivně pracovat na lokálním počítači. Protože se však grafy škálují až na miliony nebo miliardy uzlů a hran, jejich zpracování vyžaduje pokročilejší řešení, jako je distribuované školení na clusterech GPU.

Jako další krok prozkoumáme přístupy ke zpracování rozsáhlých grafů a implementaci predikce propojení v cloudových prostředích, což vám umožní aplikovat tyto techniky na datové sady na úrovni produkce.