Grafikoak datuak irudikatzeko modu indartsua dira, entitateen arteko harremanak modu berezian atzemateko hainbat aplikaziotan. Sare sozialak, proteina-interakzioak, garraio-sistemak edo gomendio-motorrak modelatzen ari zaren ala ez, grafikoek modu naturalean adierazten eta aztertzen dituzte interdependentzia konplexu horiek. Gaur egungo datuetan oinarritutako munduan, entitateen arteko harremanak ulertzea entitateak beraiek ulertzea bezain garrantzitsua da sarritan; hor dira grafikoak benetan distiratsuak.
Estekaren iragarpena grafikoen analitikaren oinarrizko zereginetako bat da, nodoen (grafiko batean irudikatutako entitateen) arteko konexioen (edo esteken) iragarpena dakar. Imajinatu sare sozial batean lagun berriak gomendatzea, kolaborazio posibleak aipamen grafiko akademiko batean iragartzea edo erabiltzaileen eta produktuen arteko etorkizuneko elkarrekintzak aurreikustea merkataritza elektronikoko ezarpenean. Horiek guztiak esteken iragarpenaren adibide dira. Zeregin honek sareak zabaltzen laguntzen du, falta den informazioa ondorioztatzen eta anomaliak detektatzen laguntzen du. Erabiltzaileen esperientzia hobetzetik iruzurra detektatzeko hobekuntzara bitarteko aplikazioetarako, esteken iragarpena arrakastarako funtsezko osagaia da.
Esteken iragarpena ilustratzeko, Stanford Network Analysis Project (SNAP)-eko Twitch Social Network datu-multzoa erabiliko dugu. Datu multzo honek Twitch streaming plataformako erabiltzaileen arteko lotura sozialak jasotzen ditu, non nodoek Twitch erabiltzaileak ordezkatzen dituzten eta ertzek haien arteko adiskidetasuna adierazten duten. Datu-multzoa ondo egituratuta dago, eta erraza da aurrez prozesatzea eta lan egitea.
Jarraituz gero, proiektu bat konfiguratu, datuak aldez aurretik prozesatzen, eredu bat eraikitzen eta mundu errealeko datu-multzo batean estekak iragartzeko ebaluatzen ikasiko duzu.
Grafiko egituratutako datuekin lan egiteak erronka bereziak dakartza, eta hor sartzen dira Graph Neural Networks (GNN) . GNNak grafikoen datuekin lan egiteko bereziki diseinatutako neurona-sare mota bat dira. Tamaina finkoko sarreran funtzionatzen duten sare neuronal tradizionalek ez bezala, GNNek grafikoen tamaina arbitrarioak kudea ditzakete eta datuen barneko konektibitate ereduak aprobetxatu ditzakete. Nodo baten inguruko informazioa batuta, GNNek nodoaren atributuak eta grafikoaren egitura jasotzen dituzten irudikapenak ikasten dituzte, eta oso eraginkorrak dira nodoen sailkapena, esteken iragarpena eta grafikoen sailkapena bezalako zereginetarako.
Deep Graph Library ( DGL.ai ) GNN-ak erraztasunez eta eraginkortasunez eraikitzeko tresna-multzo indartsua da. DGL-rekin, garatzaileek punta-puntako GNN arkitekturak aprobetxa ditzakete hainbat zeregin aurre egiteko, esteken iragarpena barne. DGL-k grafiko homogeneoekin zein heterogeneoekin lan egiteko erabilgarritasun sorta bat eskaintzen du, ikertzaile zein profesionalentzat tresna polifazetikoa bihurtuz. GNNen ezarpena sinplifikatuz, DGL-k aukera ematen dizu soluzio berritzaileak garatzen gehiago bideratzeko, azpiko konplexutasun teknikoetan nahastu beharrean.
Oinarri hau kontuan izanda, murgil gaitezen esteken iragarpen eredu bat eraikitzen GNNak eta DGL.ai erabiliz.
Lehenengo urratsa gure proiektua konfiguratzea da beharrezko liburutegiak inportatuz:
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
Entrenamendurako datuak prestatzeko, lehenik Twitch datu-multzoa kargatuko dugu, grafiko gisa irudikatuko dugu eta, ondoren, prestakuntza- eta proba-multzoetan banatuko dugu. DGLDataset -etik heredatzen den klase pertsonalizatu bat sortuko dugu, datuak kargatzeko prozesua egituratzen eta grafikoekin lotutako eragiketak errazten lagunduko duena.
Hona hemen datu multzoa sortzeko eta aurreprozesatzeko kodea:
# 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
Orain gure datu multzoa hasieratzen dugu grafikoaren datuak kargatzeko.
# init the dataset dataset = SocialNetworkDataset() g = dataset[0]
Hurrengo urratsa prestakuntza eta proba multzoak sortzea da. Ertzak 80/20 ratio batean banatuko ditugu entrenatzeko eta probak egiteko. Bi multzoetarako lagin positiboak (dauden ertzak) eta negatiboak (ez dauden ertzak) sortzen ditugu. Grafiko handiagoetarako, DGL-ren dgl.sampling
utilitateak lagungarriak izan daitezke, baina hemen, grafiko osoa memorian sartzen da. Hona hemen prestakuntza eta proba multzoak sortzeko kodea:
# 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())
Graph Sample and Agregate (GraphSAGE) sare neuronal konboluzional bat erabiliko dugu grafikoan nodo bakoitzaren egitura eta ezaugarriak jasotzen dituzten nodoen irudikapenak ikasteko, txertaketak izenez ere ezagutzen direnak. GraphSAGE funtzionatzen du nodo bakoitzaren bizilagunen ezaugarrien informazioa batuz, nodo bakoitzaren irudikapen esanguratsu bat sortzeko. Prozesu honek, auzokideen agregazioa izenez ezagutzen dena, ereduak grafikoan eredu aberats eta lokalizatuak ikastea ahalbidetzen du.
GraphSAGE geruza bakoitzean, ereduak agregazio-funtzio bat aplikatzen du (kasu honetan, "batez bestekoa" funtzioa) aldameneko nodoetatik informazioa biltzeko, eta gero nodoaren ezaugarri propioekin konbinatzen da. Geruza konboluzional bat baino gehiago pilatzeak ereduari gero eta urrunago dauden nodoetatik informazioa harrapatzeko aukera ematen du, grafikoaren barruan nodo bakoitzaren ikuspegia eraginkortasunez zabalduz.
Ereduaren errendimendua hobetzeko eta gehiegizko egokitzapena murrizteko, geruza bakoitzaren ondoren uztea aplikatuko dugu.
Eraiki dezagun orain GraphSAGE eredua hiru geruza konboluzionalekin , datuen bidez nola pasatzen diren definitzeko forward
funtzio batekin batera:
# 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
Hirugarren geruzaren ( h
) ondorengo irteerak nodoen txertaketak ditu. Bi nodoren artean ertz bat (edo lotura) izateko probabilitatea aurreikusteko, Geruza Anitzeko Perceptron (MLP) iragarlea erabiliko dugu. MLP honek bi nodoren txertaketak hartzen ditu sarrera gisa eta haien artean ertz bat izateko probabilitatea adierazten duen puntuazioa kalkulatzen du.
# 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 iragarleak honela funtzionatzen du:
Geruzatutako hurbilketa honek iragarleak nodo bikoteen arteko erlazio konplexuak harrapatzeko eta ertz baten existentziaren probabilitate gisa interpretatu daitekeen ertz-puntuazioa kalkulatzeko aukera ematen du.
Gure eredua eraginkortasunez entrenatzeko, esteken iragarpenean ereduaren errendimendua kuantifikatu dezakeen galera-funtzioa behar dugu. Zeregin hau sailkapen arazo bitar bat denez, lotura bakoitza existitzen den edo ez dagoenez, entropia gurutzatua (BCE) erabiltzen dugu galera-funtzio gisa. Gurutze-entropia bitarrak ereduaren aurreikusitako puntuazioen eta benetako etiketen arteko desadostasuna neurtzen du (1 lehendik dagoen esteka baterako, 0 loturarik ez dagoenerako). _with_logits
bertsioa erabiltzen dugu, gure ereduak puntuazio gordinak (logits) ateratzen dituelako probabilitateak baino. BCEren bertsio hau egonkorragoa da logitekin lan egiten denean, funtzio sigmoidea eta entropia gurutzatua urrats batean konbinatzen baititu.
Hona hemen galerak kalkulatzen dituen kodea:
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)
Eredua ebaluatzeko, Area Under the ROC Curve (AUC) metrika erabiltzen dugu. AUC egokia da esteken iragarpenerako, datu desorekatuak modu eraginkorrean kudeatzen dituelako , non lagin negatiboak (ez dauden ertzak) lagin positiboak baino askoz ohikoagoak diren. AUC puntuazioak ereduak lehendik dauden estekak existitzen ez direnak baino maila altuagoan zenbaterainoko maila ematen dituen adierazten digu.
Hona hemen AUC kalkulatzeko kodea:
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)
Oharra: detach()
erabiltzen dugu konputazio grafikotik tentsoreak kentzeko, AUC-a kalkulatzeko aukera ematen digu gradienteak eragin gabe.
Orain prest gaude eredua trebatzeko. Hasteko, eredua, iragarlea eta optimizatzailea instantziatuko ditugu eta entrenamendu-begizta definituko dugu . Ikaskuntza-tasa, ezkutuko geruzaren tamaina eta uztea-tasa ere zehaztuko ditugu, beste hiperparametro batzuen artean. Hemen hiperparametroen optimizazioa landuko ez dugun arren, ikaskuntza-tasa-planifikatzaile bat erabiliko dugu ikasketa-tasa doitzeko galera lautada bat bada, hau da, aro kopuru jakin batean (kasu honetan, 25) gutxitzeari uzten dio. Antolatzaileak ikaskuntza-tasa erdira murrizten du hori gertatzen denean, eta horrek ereduari modu eraginkorragoan bat egiten lagundu diezaioke.
Hona hemen eredua hasieratzeko eta prestakuntza konfiguratzeko kodea:
# 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}')
Exekutatu dezagun kodea eta azter dezagun irteera:
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
Ikus dezakegunez, ereduak 0,92 inguruko AUC bat lortzen du, aurreikuspen-errendimendu sendoa adierazten duena . Kontuan izan ikasketa-tasa 500 eta 600 aroen artean murrizten dela galera egonkortzen denean. Doikuntza honek sintonizazio finagoa ahalbidetzen du, galerak txikiagotzea ekarriz. Puntu jakin baten ondoren, galera eta AUC egonkortu egiten dira, ereduak bat egin duela adieraziz.
Ebaluatu dezagun probako datuen eredua (entrenamenduan erabili ez zena) eta ea ondo orokortzen den:
# 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}')
Emaitza hau da:
Test loss: 0.675215482711792, Test AUC: 0.866213400711374
Probako AUC entrenamenduko AUCa baino zertxobait txikiagoa da, gehiegizko egokitze txikia adierazten du. Hala ere, 0,866ko AUC-ak erakusten du ereduak oraindik ondo funtzionatzen duela ikusten ez diren datuetan . Hiperparametroak sintonizatzeak orokortzea hobe dezake, batez ere gehiegizko egokitzea kezkagarria bada.
Gure trebatu ereduarekin, orain grafikoan nodoen arteko loturak izateko probabilitatea iragar dezakegu . Nodo-pare posible guztien iragarpenak sortuko ditugu, balizko konexio berriak identifikatzeko aukera emanez.
ndata['h']
atributuan gordeta, esteken iragarpenerako sarrera gisa balioko dute.
Hona hemen urrats hauen kodea:
# 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)
Bikote hautagai guztien iragarpenak ditugula, edozein nodo zehatzen arteko lotura probabilitatea egiaztatu dezakegu . Adibidez, azter ditzagun hasierako datu multzoan zuzenean konektatuta ez dauden 1773 eta 7005 nodoen arteko loturaren puntuazioa eta probabilitatea:
# 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}%')
Hau da emaitza:
Pair index: tensor([11066978]) Pair link score: 0.7675977945327759 Link probability: 68.30010414123535%
Gure ereduaren arabera, 1773 eta 7005 erabiltzaileen artean lotura izateko %68,3ko probabilitatea dago.
Argitalpen honetan, grafiko sozial batean lotura berriak iragartzeko eredu bat arrakastaz eraiki dugu , Graph Neural Networks eta DGL esteken iragarpenerako erabiltzen direla frogatuz. Datu multzo txiki samarra erabiltzeak tokiko makina batean modu eraginkorrean lan egiteko aukera eman zigun. Hala ere, grafikoak milioika edo milioika nodo eta ertzetara igotzen diren heinean, horiek kudeatzeko irtenbide aurreratuagoak behar dira, adibidez, GPU klusterretan banatutako prestakuntza.
Hurrengo urrats gisa, eskala handiko grafikoak maneiatzeko eta hodei-inguruneetan esteken iragarpena ezartzeko planteamenduak aztertuko ditugu, teknika hauek ekoizpen-mailako datu-multzoetan aplikatzeko aukera emanez.