Forudsigelse af links i grafer med Graph Neural Networks og DGL.ai

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.

Linkforudsigelse 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.

For at illustrere linkforudsigelse vil vi bruge Twitch Social Network-datasættet 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.

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 Graph Neural Networks (GNN'er) 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.

The Deep Graph Library ( DGL.ai ) 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.

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 DGLDataset , som vil hjælpe med at strukturere dataindlæsningsprocessen og strømline grafrelaterede operationer.

1. Indlæsning af grafdata : 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.
2. Indlæser nodefunktioner : 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.

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 oprette trænings- og testsæt . Vi opdeler kanterne i et forhold på 80/20 til træning og test. Vi genererer både positive (eksisterende kanter) og negative prøver (ikke-eksisterende kanter) for begge sæt. For større grafer kan DGL's dgl.sampling værktøjer være nyttige, men her passer hele grafen i hukommelsen. Her er koden til at oprette trænings- og testsæt:

 # 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 Graph Sample and Aggregate (GraphSAGE) konvolutionelt neuralt netværk til at lære noderepræsentationer, også kendt som indlejringer , 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 nabosammenlægning , gør det muligt for modellen at lære rige, lokaliserede mønstre i grafen.

I hvert GraphSAGE-lag anvender modellen en aggregeringsfunktion (i dette tilfælde "mean"-funktionen) for at indsamle information fra naboknudepunkter, som derefter kombineres med nodens egne funktioner. Stabling af flere foldningslag gør det muligt for modellen at fange information fra stadigt fjernere noder , hvilket effektivt udvider hver nodes visning i grafen.

For at forbedre modellens ydeevne og reducere overpasning, anvender vi dropout efter hvert lag.

Lad os nu bygge GraphSAGE-modellen med tre foldningslag sammen med en forward funktion til at definere, hvordan data flyder gennem det:

 # 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 ( h ) indeholder nodeindlejringerne. For at forudsige sandsynligheden for en kant (eller link) mellem to vilkårlige noder, bruger vi en Multi-Layer Perceptron (MLP) prædiktor . Denne MLP tager indlejring af to noder som input og beregner en score, der angiver sandsynligheden for, at der eksisterer en kant mellem dem.

 # 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-prædiktoren fungerer som følger:

• Inputstørrelse: Prædiktorens inputstørrelse er baseret på de indlærte nodeindlejringer. Da hver kant forbinder to noder, sammenkæder vi deres indlejringer (hver af størrelsen hidden_features), hvilket resulterer i en inputstørrelse på hidden_features * 2.
• Layer 1 (W1): Dette lag behandler de sammenkædede indlejringer og reducerer outputdimensionen tilbage til hidden_features, hvilket bevarer vigtig relationel information mellem noderne.
• Lag 2 (W2): Dette sidste lag producerer en enkelt skalarscore for hvert par noder, som repræsenterer sandsynligheden for , at der eksisterer en kant mellem dem.

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 kvantificere modellens ydeevne på linkforudsigelse. Da denne opgave er et binært klassifikationsproblem - hvor hvert link enten eksisterer eller ikke gør - bruger vi binær krydsentropi (BCE) 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 _with_logits , 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.

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 Area Under the ROC Curve (AUC) . AUC er velegnet til linkforudsigelse, fordi den håndterer ubalancerede data 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.

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 detach() til at fjerne tensorerne fra beregningsgrafen, hvilket giver os mulighed for at beregne AUC uden at påvirke gradienter.

Træning af modellen

Nu er vi klar til at træne modellen. Til at starte med vil vi instansiere modellen, forudsigeren og optimizeren og definere træningsløkken . Vi specificerer også indlæringshastigheden, størrelsen på det skjulte lag og frafaldshastigheden, blandt andre hyperparametre. Selvom vi ikke dækker hyperparameteroptimering her, bruger vi en læringshastighedsplanlægger 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.

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 AUC på omkring 0,92, hvilket indikerer stærk prædiktiv ydeevne . 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 konvergeret .

Lad os evaluere modellen på testdataene (som ikke blev brugt under træningen) og se om den generaliserer godt:

 # 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

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 . Yderligere justering af hyperparametre kunne forbedre generaliseringen, især hvis overtilpasning er et problem.

Brug af den trænede model til at forudsige nye links

Med vores trænede model kan vi nu forudsige sandsynligheden for links mellem noder i grafen. Vi genererer forudsigelser for alle mulige nodepar , hvilket giver os mulighed for at identificere potentielle nye forbindelser.

1. Generering af kandidatknudepar : 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.
2. Oprettelse af en kandidatgraf: Vi opretter derefter en DGL-graf med disse kandidatkanter og bruger modellen med nodeindlejringer fra den originale graf. Disse indlejringer, gemt i kandidatgrafens ndata['h'] attribut, vil tjene som input til linkforudsigelse.

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 vi har forudsigelser for alle kandidatpar, kan vi kontrollere koblingssandsynligheden mellem specifikke noder . 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:

 # 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 byggede vi med succes en model til at forudsige nye links i en social graf, der demonstrerer brugen af Graph Neural Networks og DGL til linkforudsigelse. Ved at bruge et relativt lille datasæt kunne vi arbejde effektivt på en lokal maskine. 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.

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.