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áří. 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. Predikce spojení Pro ilustraci predikce odkazů použijeme 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. datovou sadu Twitch Social Network 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 . 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ů. grafové neuronové sítě (GNN) 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í. Deep Graph Library ( ) DGL.ai 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 , což pomůže strukturovat proces načítání dat a zjednodušit operace související s grafy. DGLDataset : 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á. Načítání dat grafu : 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. Načítání funkcí uzlu 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 . Pro trénování a testování rozdělíme okraje v . Generujeme jak tak negativní vzorky pro obě sady. Pro větší grafy mohou být užitečné nástroje DGL , ale zde se celý graf vejde do paměti. Zde je kód pro vytvoření školicích a testovacích sad: vytvoření tréninkových a testovacích sad poměru 80/20 pozitivní (existující hrany), (neexistující hrany) 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()) Model: GraphSAGE Convolutional Layers a MLP Predictor Použijeme konvoluční neuronovou síť , abychom se naučili reprezentace uzlů, známé také jako , 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 , umožňuje modelu naučit se bohaté, lokalizované vzory v grafu. Graph Sample and Aggregate (GraphSAGE) vložení sousedská agregace V každé vrstvě GraphSAGE model aplikuje ke sběru informací ze sousedních uzlů, které jsou pak kombinovány s vlastními vlastnostmi uzlu. Skládání umožňuje modelu , čímž se efektivně rozšiřuje pohled každého uzlu v grafu. agregační funkci (v tomto případě „střední“ funkci) více konvolučních vrstev zachytit informace ze stále vzdálenějších uzlů 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 spolu s funkcí, která definuje, jak přes něj protékají data: třemi konvolučními vrstvami forward # 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 ( ) obsahuje vložení uzlů. K předpovědi pravděpodobnosti hrany (nebo spojení) mezi jakýmikoli dvěma uzly použijeme . Tato udávající pravděpodobnost, že mezi nimi existuje hrana. h prediktor Multi-Layer Perceptron (MLP) MLP bere vložení dvou uzlů jako vstup a vypočítává skóre # 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"] funguje následovně: Prediktor MLP Vstupní velikost prediktoru je založena na naučených vloženích uzlů. Protože každá hrana spojuje dva uzly, (každý o velikosti hidden_features), což vede ke vstupní velikosti hidden_features * 2. Vstupní velikost: zřetězíme jejich vložení Tato vrstva zpracovává zřetězená vložení a zpět na hidden_features, přičemž zachovává důležité relační informace mezi uzly. Vrstva 1 (W1): redukuje výstupní dimenzi Tato finální vrstva vytváří jediné pro každý pár uzlů, které představuje mezi nimi. Vrstva 2 (W2): skalární skóre pravděpodobnost existence hrany 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 na predikci spojení. Vzhledem k tomu, že tato úloha je – kde každý odkaz buď existuje nebo neexistuje – používáme jako ztrátovou funkci . 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 , 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. kvantifikovat výkon modelu problémem binární klasifikace binární křížovou entropii (BCE) _with_logits 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 . AUC se dobře hodí pro predikci spojení, protože efektivně , 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í. Area Under the ROC Curve (AUC) zpracovává nevyvážená data 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 , což nám umožňuje vypočítat AUC bez ovlivnění gradientů. detach() Trénink modelu Nyní jsme připraveni trénovat model. Nejprve . Kromě dalších hyperparametrů také určíme rychlost učení, velikost skryté vrstvy a míru výpadků. I když se zde , 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. vytvoříme instanci modelu, prediktoru a optimalizátoru a definujeme trénovací smyčku nebudeme zabývat optimalizací hyperparametrů použijeme plánovač rychlosti učení 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 . 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 . AUC kolem 0,92, což ukazuje na silný prediktivní výkon konvergoval (která nebyla použita během tréninku) a uvidíme, zda dobře zobecňuje: Vyhodnoťme model na testovacích datech # 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 . Další ladění hyperparametrů by mohlo zlepšit zobecnění, zvláště pokud je problémem přefitování. 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 Použití trénovaného modelu k predikci nových odkazů S naším trénovaným modelem mezi uzly v grafu. Vygenerujeme , což nám umožní identifikovat potenciální nová spojení. nyní můžeme předpovídat pravděpodobnost spojení předpovědi pro všechny možné dvojice 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í. Generování kandidátských párů uzlů 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 kandidátského grafu, budou sloužit jako vstupy pro predikci spojení. Vytvoření kandidátského grafu: ndata['h'] 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ž . 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: 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 # 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 v sociálním grafu, demonstrující použití Graph Neural Networks a DGL pro predikci odkazů. 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. jsme úspěšně vytvořili model pro predikci nových odkazů Použití relativně malé datové sady nám umožnilo efektivně pracovat na lokálním počítači. 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.
