Grafer er en effektiv måde at repræsentere data på, der unikt fanger relationer mellem enheder på tværs af en lang række applikationer. Uanset om du modellerer sociale netværk, proteininteraktioner, transportsystemer eller anbefalingsmotorer, repræsenterer og analyserer grafer naturligvis disse komplekse indbyrdes afhængigheder. I nutidens datadrevne verden er forståelsen af relationer mellem entiteter ofte lige så vigtig som at forstå entiteterne selv – det er her graferne virkelig skinner. er en af de grundlæggende opgaver i grafanalyse, der involverer forudsigelse af forbindelser (eller links) mellem noder (enheder repræsenteret i en graf). Forestil dig at anbefale nye venner i et socialt netværk, forudsige potentielle samarbejder i en akademisk citationsgraf eller forudsige fremtidige interaktioner mellem brugere og produkter i en e-handelsindstilling – det er alle eksempler på linkforudsigelse i aktion. Denne opgave hjælper med at udvide netværk, udlede manglende information og opdage uregelmæssigheder. For applikationer, der spænder fra at forbedre brugeroplevelsen til at forbedre opdagelse af svindel, er linkforudsigelse en nøgleingrediens for succes. Linkforudsigelse For at illustrere linkforudsigelse vil vi bruge fra Stanford Network Analysis Project (SNAP). Dette datasæt fanger de sociale forbindelser mellem brugere på Twitch-streamingplatformen, hvor noder repræsenterer Twitch-brugere, og kanter repræsenterer venskaber mellem dem. Datasættet er velstruktureret, hvilket gør det nemt at forbehandle og arbejde med. Twitch Social Network-datasættet Ved at følge med vil du lære, hvordan du opsætter et projekt, forbehandler data, bygger en model og evaluerer det til linkforudsigelse på et datasæt fra den virkelige verden. Graph Neurale Networks og Deep Graph Library At arbejde med grafstrukturerede data giver unikke udfordringer, og det er her kommer ind i billedet. GNN'er er en type neurale netværk, der er specielt designet til at arbejde med grafdata. I modsætning til traditionelle neurale netværk, der opererer på input med fast størrelse, kan GNN'er håndtere vilkårlige grafstørrelser og udnytte forbindelsesmønstrene i dataene. Ved at aggregere information fra en nodes naboer lærer GNN'er repræsentationer, der fanger både nodeattributter og grafens struktur, hvilket gør dem yderst effektive til opgaver som nodeklassificering, linkforudsigelse og grafklassificering. Graph Neural Networks (GNN'er) The er et kraftfuldt værktøjssæt til at bygge GNN'er med lethed og effektivitet. Med DGL kan udviklere udnytte state-of-the-art GNN-arkitekturer til at tackle en række forskellige opgaver, herunder linkforudsigelse. DGL tilbyder en række værktøjer til at arbejde med både homogene og heterogene grafer, hvilket gør det til et alsidigt værktøj for både forskere og praktikere. Ved at forenkle implementeringen af GNN'er giver DGL dig mulighed for at fokusere mere på at udvikle innovative løsninger i stedet for at blive hængende i de underliggende tekniske kompleksiteter. Deep Graph Library ( ) DGL.ai Med dette grundlag i tankerne, lad os dykke ned i at bygge en link-forudsigelsesmodel ved hjælp af GNN'er og DGL.ai. Opsætning af projektet Det første trin er at opsætte vores projekt ved at importere de nødvendige biblioteker: 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 Dataforbehandling og opdeling af tog-test For at forberede dataene til træning indlæser vi først Twitch-datasættet, repræsenterer det som en graf og deler det derefter op i trænings- og testsæt. Vi opretter en tilpasset klasse, der arver fra , som vil hjælpe med at strukturere dataindlæsningsprocessen og strømline grafrelaterede operationer. DGLDataset : I procesfunktionen starter vi med at læse listen over kanter fra datasættet. Da kanterne i det originale datasæt er urettede (repræsenterer gensidige venskaber), tilføjer vi omvendte kanter for at sikre, at forbindelserne er tovejs i vores graf. Indlæsning af grafdata : Dernæst indlæser vi nodefunktioner fra en JSON-fil. Hver node har en liste over funktioner, der kan variere i længde, så vi udfylder kortere funktionslister med nuller for at opretholde en ensartet længde på tværs af alle noder. Indlæser nodefunktioner Her er koden til at oprette og forbehandle datasættet: # 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 Vi initialiserer nu vores datasæt for at indlæse grafdataene. # init the dataset dataset = SocialNetworkDataset() g = dataset[0] Det næste trin er at . Vi opdeler kanterne i et til træning og test. Vi genererer både og negative prøver for begge sæt. For større grafer kan DGL's værktøjer være nyttige, men her passer hele grafen i hukommelsen. Her er koden til at oprette trænings- og testsæt: oprette trænings- og testsæt forhold på 80/20 positive (eksisterende kanter) (ikke-eksisterende kanter) 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 og MLP Predictor Vi bruger et konvolutionelt neuralt netværk til at lære noderepræsentationer, også kendt som , der fanger både strukturen og funktionerne i hver node i grafen. GraphSAGE fungerer ved at aggregere funktionsinformation fra hver knudes naboer for at skabe en meningsfuld repræsentation for hver knude. Denne proces, kendt som , gør det muligt for modellen at lære rige, lokaliserede mønstre i grafen. Graph Sample and Aggregate (GraphSAGE) indlejringer nabosammenlægning I hvert GraphSAGE-lag anvender modellen en for at indsamle information fra naboknudepunkter, som derefter kombineres med nodens egne funktioner. Stabling gør det muligt for modellen at , hvilket effektivt udvider hver nodes visning i grafen. aggregeringsfunktion (i dette tilfælde "mean"-funktionen) af flere foldningslag fange information fra stadigt fjernere noder For at forbedre modellens ydeevne og reducere overpasning, anvender vi efter hvert lag. dropout Lad os nu bygge GraphSAGE-modellen med sammen med en funktion til at definere, hvordan data flyder gennem det: tre foldningslag 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 Outputtet efter det tredje lag ( ) indeholder nodeindlejringerne. For at forudsige sandsynligheden for en kant (eller link) mellem to vilkårlige noder, bruger vi en . Denne der angiver sandsynligheden for, at der eksisterer en kant mellem dem. h Multi-Layer Perceptron (MLP) prædiktor MLP tager indlejring af to noder som input og beregner en score, # 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"] fungerer som følger: MLP-prædiktoren Prædiktorens inputstørrelse er baseret på de indlærte nodeindlejringer. Da hver kant forbinder to noder, (hver af størrelsen hidden_features), hvilket resulterer i en inputstørrelse på hidden_features * 2. Inputstørrelse: sammenkæder vi deres indlejringer Dette lag behandler de sammenkædede indlejringer og tilbage til hidden_features, hvilket bevarer vigtig relationel information mellem noderne. Layer 1 (W1): reducerer outputdimensionen Dette sidste lag producerer en enkelt for hvert par noder, som repræsenterer sandsynligheden for at der eksisterer mellem dem. Lag 2 (W2): skalarscore , en kant Denne lagdelte tilgang tillader prædiktoren at fange komplekse relationer mellem par af noder og beregne en kantscore, der kan fortolkes som sandsynligheden for, at en kant eksisterer. Tabsfunktion og AUC For at træne vores model effektivt har vi brug for en tabsfunktion, der kan på linkforudsigelse. Da denne opgave er et - hvor hvert link enten eksisterer eller ikke gør - bruger vi som vores tabsfunktion. Binær krydsentropi måler uoverensstemmelsen mellem modellens forudsagte score og de faktiske etiketter (1 for et eksisterende link, 0 for intet link). Vi bruger versionen , fordi vores model udsender råscores (logits) snarere end sandsynligheder. Denne version af BCE er mere stabil, når du arbejder med logits, da den kombinerer sigmoid-funktionen og krydsentropi i ét trin. kvantificere modellens ydeevne binært klassifikationsproblem binær krydsentropi (BCE) _with_logits Her er koden, der beregner tab: 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) For at evaluere modellen bruger vi metrikken . AUC er velegnet til linkforudsigelse, fordi den effektivt, hvor negative prøver (ikke-eksisterende kanter) er meget mere almindelige end positive prøver. AUC-scoren giver os en fornemmelse af, hvor godt modellen rangerer eksisterende links højere end ikke-eksisterende. Area Under the ROC Curve (AUC) håndterer ubalancerede data Her er koden til at beregne 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) Bemærk: Vi bruger til at fjerne tensorerne fra beregningsgrafen, hvilket giver os mulighed for at beregne AUC uden at påvirke gradienter. detach() Træning af modellen Nu er vi klar til at træne modellen. Til at starte med vil vi . Vi specificerer også indlæringshastigheden, størrelsen på det skjulte lag og frafaldshastigheden, blandt andre hyperparametre. Selvom her, til at justere indlæringshastigheden, hvis tabsplateauerne - hvilket betyder, at det holder op med at falde i et bestemt antal epoker (i dette tilfælde 25). Planlæggeren halverer indlæringshastigheden, når dette sker, hvilket kan hjælpe modellen med at konvergere mere effektivt. instansiere modellen, forudsigeren og optimizeren og definere træningsløkken vi ikke dækker hyperparameteroptimering bruger vi en læringshastighedsplanlægger Her er koden til at initialisere modellen og opsætte træning: # 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}') Lad os køre koden og undersøge outputtet: 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 Som vi kan se, opnår modellen en . Bemærk, at indlæringshastigheden reduceres mellem epoke 500 og 600, når tabet stabiliserer sig. Denne justering giver mulighed for finjustering, hvilket fører til et lille fald i tab. Efter et vist punkt stabiliseres tabet og AUC, hvilket indikerer, at modellen er . AUC på omkring 0,92, hvilket indikerer stærk prædiktiv ydeevne konvergeret Lad os (som ikke blev brugt under træningen) og se om den generaliserer godt: evaluere modellen på testdataene # 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}') Resultatet er: Test loss: 0.675215482711792, Test AUC: 0.866213400711374 . Yderligere justering af hyperparametre kunne forbedre generaliseringen, især hvis overtilpasning er et problem. Test-AUC er lidt lavere end trænings-AUC, hvilket indikerer mindre overfitting. AUC på 0,866 viser dog, at modellen stadig klarer sig godt på usete data Brug af den trænede model til at forudsige nye links Med vores trænede model mellem noder i grafen. Vi genererer , hvilket giver os mulighed for at identificere potentielle nye forbindelser. kan vi nu forudsige sandsynligheden for links forudsigelser for alle mulige nodepar : Vi genererer først alle mulige knudepar, eksklusive selvløkker (forbindelser fra en knude til sig selv). Dette giver os de kandidatknudepar, som vi ønsker at forudsige linksandsynligheder for. Generering af kandidatknudepar Vi opretter derefter en DGL-graf med disse kandidatkanter og bruger modellen med nodeindlejringer fra den originale graf. Disse indlejringer, gemt i kandidatgrafens attribut, vil tjene som input til linkforudsigelse. Oprettelse af en kandidatgraf: ndata['h'] Her er koden til disse trin: # 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) Nu, hvor . Lad os for eksempel undersøge scoren og sandsynligheden for en forbindelse mellem noderne 1773 og 7005, som ikke er direkte forbundet i det indledende datasæt: vi har forudsigelser for alle kandidatpar, kan vi kontrollere koblingssandsynligheden mellem specifikke noder # 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}%') Dette er resultatet: Pair index: tensor([11066978]) Pair link score: 0.7675977945327759 Link probability: 68.30010414123535% Ifølge vores model er der . 68,3 % sandsynlighed for en sammenhæng mellem bruger 1773 og 7005 Konklusion I dette indlæg i en social graf, der demonstrerer brugen af Graph Neural Networks og DGL til linkforudsigelse. Men da grafer skaleres op til millioner eller milliarder af noder og kanter, kræver håndtering af dem mere avancerede løsninger, såsom distribueret træning på GPU-klynger. byggede vi med succes en model til at forudsige nye links Ved at bruge et relativt lille datasæt kunne vi arbejde effektivt på en lokal maskine. Som et næste trin vil vi udforske tilgange til håndtering af grafer i stor skala og implementering af linkforudsigelse i skymiljøer, så du kan anvende disse teknikker til datasæt på produktionsniveau.
