Saišu prognozēšana grafikos, izmantojot grafiku neironu tīklus un DGL.ai

Grafiki ir spēcīgs veids, kā attēlot datus, unikāli tverot attiecības starp entītijām dažādās lietojumprogrammās. Neatkarīgi no tā, vai modelējat sociālos tīklus, proteīnu mijiedarbību, transporta sistēmas vai ieteikumu dzinējus, grafiki dabiski attēlo un analizē šīs sarežģītās savstarpējās atkarības. Mūsdienu uz datiem balstītajā pasaulē izpratne par attiecībām starp entītijām bieži ir tikpat svarīga kā pašu entītiju izpratne — tieši šeit grafiki patiešām spīd.

Saites prognozēšana ir viens no pamata uzdevumiem grafiku analīzē, kas ietver savienojumu (vai saišu) prognozēšanu starp mezgliem (grafikā attēlotajām entītijām). Iedomājieties, ka iesakāt jaunus draugus sociālajā tīklā, prognozējat potenciālo sadarbību akadēmiskā citātu diagrammā vai prognozējat turpmāko mijiedarbību starp lietotājiem un produktiem e-komercijas vidē — šie visi ir saikņu prognozēšanas piemēri darbībā. Šis uzdevums palīdz paplašināt tīklus, secināt trūkstošo informāciju un atklāt anomālijas. Lietojumprogrammām, sākot no lietotāja pieredzes uzlabošanas līdz krāpšanas atklāšanas uzlabošanai, saišu prognozēšana ir galvenā panākumu sastāvdaļa.

Lai ilustrētu saites prognozēšanu, mēs izmantosim Twitch sociālā tīkla datu kopu no Stenfordas tīkla analīzes projekta (SNAP). Šī datu kopa tver sociālos sakarus starp lietotājiem Twitch straumēšanas platformā, kur mezgli apzīmē Twitch lietotājus, bet malas - draudzību starp tiem. Datu kopa ir labi strukturēta, tāpēc to ir viegli apstrādāt un ar to strādāt.

Sekojot līdzi, jūs uzzināsit, kā iestatīt projektu, iepriekš apstrādāt datus, izveidot modeli un novērtēt to saites prognozēšanai reālās pasaules datu kopā.

Grafu neironu tīkli un dziļo grafiku bibliotēka

Strādājot ar grafiski strukturētiem datiem, rodas unikālas problēmas, un tieši šeit parādās grafiskie neironu tīkli (GNN) . GNN ir neironu tīkla veids, kas īpaši izstrādāts darbam ar grafiku datiem. Atšķirībā no tradicionālajiem neironu tīkliem, kas darbojas ar fiksēta izmēra ievadi, GNN var apstrādāt patvaļīgus grafikus un izmantot datu savienojamības modeļus. Apkopojot informāciju no mezgla kaimiņiem, GNN apgūst attēlojumus, kas tver gan mezgla atribūtus, gan diagrammas struktūru, padarot tos ļoti efektīvus tādiem uzdevumiem kā mezglu klasifikācija, saišu prognozēšana un grafiku klasifikācija.

Deep Graph Library ( DGL.ai ) ir jaudīgs rīku komplekts, lai viegli un efektīvi izveidotu GNN. Izmantojot DGL, izstrādātāji var izmantot vismodernākās GNN arhitektūras, lai risinātu dažādus uzdevumus, tostarp saišu prognozēšanu. DGL nodrošina virkni utilītu darbam gan ar viendabīgiem, gan neviendabīgiem grafikiem, padarot to par daudzpusīgu rīku gan pētniekiem, gan praktiķiem. Vienkāršojot GNN ieviešanu, DGL ļauj vairāk koncentrēties uz novatorisku risinājumu izstrādi, nevis iegrimt pamatā esošajās tehniskajās sarežģītībās.

Paturot prātā šo pamatu, pievērsīsimies saišu prognozēšanas modeļa izveidei, izmantojot GNN un DGL.ai.

Projekta iestatīšana

Pirmais solis ir mūsu projekta iestatīšana, importējot vajadzīgās bibliotēkas:

 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

Datu priekšapstrāde un vilciena testa sadalījums

Lai sagatavotu datus apmācībai, mēs vispirms ielādēsim Twitch datu kopu, attēlosim to kā diagrammu un pēc tam sadalīsim apmācības un testēšanas kopās. Mēs izveidosim pielāgotu klasi, kas pārņem no DGLDataset , kas palīdzēs strukturēt datu ielādes procesu un racionalizēt ar grafiku saistītās darbības.

1. Grafika datu ielāde : Procesa funkcijā mēs sākam ar malu saraksta nolasīšanu no datu kopas. Tā kā sākotnējās datu kopas malas ir nenovirzītas (attēlo savstarpēju draudzību), mēs pievienojam apgrieztās malas, lai nodrošinātu, ka mūsu grafikā savienojumi ir divvirzienu.
2. Mezglu funkciju ielāde : pēc tam mēs ielādējam mezgla līdzekļus no JSON faila. Katram mezglam ir funkciju saraksts, kuru garums var atšķirties, tāpēc mēs saīsinām funkciju sarakstus ar nullēm, lai saglabātu konsekventu garumu visos mezglos.

Tālāk ir norādīts kods datu kopas izveidei un pirmapstrādei.

 # 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

Tagad mēs inicializējam savu datu kopu, lai ielādētu diagrammas datus.

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

Nākamais solis ir izveidot apmācības un testēšanas komplektus . Mēs sadalīsim malas attiecībā 80/20 apmācībai un testēšanai. Mēs ģenerējam gan pozitīvus (esošas malas) , gan negatīvus paraugus (neesošas malas) abām kopām. Lielākiem grafikiem var noderēt DGL utilītas dgl.sampling , taču šajā gadījumā viss grafiks ietilps atmiņā. Šis ir kods, lai izveidotu apmācības un testēšanas komplektus:

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

Modelis: GraphSAGE Convolutional Layers un MLP Predictor

Mēs izmantosim Graph Sample and Aggregate (GraphSAGE) konvolucionālo neironu tīklu, lai uzzinātu mezglu attēlojumus, ko sauc arī par iegulšanu , kas tver gan katra mezgla struktūru, gan funkcijas diagrammā. GraphSAGE darbojas, apkopojot funkciju informāciju no katra mezgla kaimiņiem, lai izveidotu jēgpilnu katra mezgla attēlojumu. Šis process, kas pazīstams kā kaimiņu apkopošana , ļauj modelim apgūt bagātīgus, lokalizētus diagrammas modeļus.

Katrā GraphSAGE slānī modelis izmanto apkopošanas funkciju (šajā gadījumā "vidējo" funkciju), lai savāktu informāciju no blakus esošajiem mezgliem, kas pēc tam tiek apvienota ar paša mezgla funkcijām. Vairāku konvolucionālu slāņu sakraušana ļauj modelim tvert informāciju no arvien attālākiem mezgliem , efektīvi paplašinot katra mezgla skatu diagrammā.

Lai uzlabotu modeļa veiktspēju un samazinātu pārmērīgu pielāgošanu, pēc katra slāņa mēs piemērosim atlaišanu .

Tagad izveidosim GraphSAGE modeli ar trim konvolucionālajiem slāņiem , kā arī forward funkciju, lai noteiktu, kā caur to plūst dati:

 # 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

Izvade pēc trešā slāņa ( h ) satur mezglu iegulšanu. Lai prognozētu malas (vai saites) iespējamību starp jebkuriem diviem mezgliem, mēs izmantosim daudzslāņu uztveres (MLP) prognozētāju . Šis MLP izmanto divu mezglu iegulšanu kā ievadi un aprēķina punktu skaitu, kas norāda malas iespējamību starp tiem.

 # 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 prognozētājs darbojas šādi:

• Ievades lielums: prognozētāja ievades lielums ir balstīts uz apgūto mezglu iegulšanu. Tā kā katra mala savieno divus mezglus, mēs savienojam to iegulšanas (katra lieluma hidden_features), kā rezultātā tiek iegūts ieejas lielums hidden_features * 2.
• 1. slānis (W1): šis slānis apstrādā savienotās iegulšanas un samazina izvades dimensiju atpakaļ uz hidden_features, saglabājot svarīgu relāciju informāciju starp mezgliem.
• 2. slānis (W2): šis pēdējais slānis katram mezglu pārim rada vienu skalāro rādītāju , kas atspoguļo iespējamību, ka starp tiem pastāv mala .

Šī slāņveida pieeja ļauj prognozētājam uztvert sarežģītas attiecības starp mezglu pāriem un aprēķināt malas punktu skaitu, ko var interpretēt kā malas pastāvēšanas varbūtību.

Zaudējuma funkcija un AUC

Lai efektīvi apmācītu mūsu modeli, mums ir nepieciešama zaudējumu funkcija, kas var kvantitatīvi noteikt modeļa veiktspēju saites prognozēšanā. Tā kā šis uzdevums ir binārās klasifikācijas problēma — kur katra saite pastāv vai neeksistē, mēs izmantojam bināro krustentropiju (BCE) kā zaudējumu funkciju. Binārā krustentropija mēra neatbilstību starp modeļa prognozētajiem rādītājiem un faktiskajām iezīmēm (1 esošai saitei, 0, ja nav saites). Mēs izmantojam versiju _with_logits , jo mūsu modelis izvada neapstrādātus rādītājus (logits), nevis varbūtības. Šī BCE versija ir stabilāka, strādājot ar logits, jo tā apvieno sigmoīdu funkciju un krustentropiju vienā solī.

Šeit ir kods, kas aprēķina zaudējumus:

 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)

Lai novērtētu modeli, mēs izmantojam metriku Platība zem ROC līknes (AUC) . AUC ir labi piemērots saišu prognozēšanai, jo tas efektīvi apstrādā nelīdzsvarotus datus , kur negatīvi paraugi (neesošas malas) ir daudz biežāk sastopami nekā pozitīvi paraugi. AUC rezultāts sniedz mums priekšstatu par to, cik labi modelis sarindo esošās saites augstāk nekā neesošās.

Šeit ir kods AUC aprēķināšanai:

 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)

Piezīme. Mēs izmantojam detach() lai noņemtu tensorus no aprēķina grafika, ļaujot mums aprēķināt AUC, neietekmējot gradientus.

Modeļa apmācība

Tagad mēs esam gatavi apmācīt modeli. Lai sāktu, mēs izveidosim modeli, prognozētāju un optimizētāju un definēsim apmācības cilpu . Mēs arī norādīsim mācīšanās ātrumu, slēptā slāņa lielumu un atmešanas līmeni, kā arī citus hiperparametrus. Lai gan mēs šeit neaptveram hiperparametru optimizāciju , mēs izmantosim mācīšanās ātruma plānotāju , lai pielāgotu mācīšanās ātrumu, ja zudumu plato, tas nozīmē, ka tas pārstāj samazināties noteiktu laiku skaitu (šajā gadījumā 25). Kad tas notiek, plānotājs uz pusi samazina mācīšanās ātrumu, kas var palīdzēt modelim efektīvāk konverģēt.

Šis ir kods modeļa inicializācijai un apmācības iestatīšanai:

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

Palaidīsim kodu un pārbaudīsim izvadi:

 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

Kā redzam, modelis sasniedz AUC aptuveni 0,92, kas norāda uz spēcīgu paredzamo veiktspēju . Ievērojiet, ka, kad zudums stabilizējas, mācīšanās ātrums tiek samazināts starp 500. un 600. laikiem. Šī pielāgošana ļauj veikt precīzāku noregulējumu, tādējādi radot nelielu zaudējumu samazināšanos. Pēc noteikta punkta zudums un AUC stabilizējas, norādot, ka modelis ir konverģēts .

Novērtēsim modeli uz testa datiem (kas netika izmantots apmācības laikā) un pārbaudīsim, vai tas labi vispārina:

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

Rezultāts ir:

 Test loss: 0.675215482711792, Test AUC: 0.866213400711374

Pārbaudes AUC ir nedaudz zemāks par treniņa AUC, kas norāda uz nelielu pārmērību. Tomēr AUC 0,866 parāda, ka modelis joprojām darbojas labi, izmantojot neredzētus datus . Turpmāka hiperparametru regulēšana varētu uzlabot vispārināšanu, it īpaši, ja bažas rada pārmērīga pielāgošana.

Apmācītā modeļa izmantošana jaunu saišu prognozēšanai

Izmantojot mūsu apmācīto modeli, mēs tagad varam paredzēt saišu iespējamību starp diagrammas mezgliem. Mēs ģenerēsim prognozes visiem iespējamiem mezglu pāriem , ļaujot mums noteikt potenciālos jaunus savienojumus.

1. Kandidātu mezglu pāru ģenerēšana : vispirms mēs ģenerējam visus iespējamos mezglu pārus, izņemot pašcilpas (mezgla savienojumus ar sevi). Tas dod mums kandidātu mezglu pārus, kuriem mēs vēlamies paredzēt saites varbūtības.
2. Kandidātu diagrammas izveide: pēc tam mēs izveidojam DGL grafiku ar šīm kandidāta malām un izmantojam modeli ar mezglu iegulšanu no sākotnējā grafika. Šīs iegulšanas, kas saglabātas kandidātdiagrammas atribūtā ndata['h'] , kalpos kā ievades saites prognozēšanai.

Tālāk ir norādīts šo darbību kods.

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

Tagad, kad mums ir prognozes visiem kandidātu pāriem, mēs varam pārbaudīt saiknes varbūtību starp jebkuriem konkrētiem mezgliem . Piemēram, pārbaudīsim punktu skaitu un saites iespējamību starp mezgliem 1773 un 7005, kas nav tieši saistīti sākotnējā datu kopā:

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

Šis ir rezultāts:

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

Saskaņā ar mūsu modeli pastāv 68,3% varbūtība, ka starp lietotāju 1773 un 7005 tiks izveidota saikne .

Secinājums

Šajā ziņojumā mēs veiksmīgi izveidojām modeli jaunu saišu prognozēšanai sociālajā diagrammā, parādot Graph neironu tīklu un DGL izmantošanu saišu prognozēšanai. Salīdzinoši nelielas datu kopas izmantošana ļāva mums efektīvi strādāt vietējā mašīnā. Tomēr, tā kā diagrammas mērogojas līdz miljoniem vai miljardiem mezglu un malu, to apstrādei ir nepieciešami progresīvāki risinājumi, piemēram, sadalīta apmācība GPU klasteros.

Nākamajā darbībā mēs izpētīsim pieejas lielapjoma diagrammu apstrādei un saišu prognozēšanas ieviešanai mākoņa vidē, lai jūs varētu izmantot šīs metodes ražošanas līmeņa datu kopām.