Графиктер маалыматтарды көрсөтүүнүн күчтүү жолу болуп саналат, ар кандай тиркемелерде объекттер ортосундагы мамилелерди уникалдуу түрдө чагылдырат. Социалдык тармактарды, протеиндердин өз ара аракеттешүүсүн, транспорттук системаларды же сунуш кыймылдаткычтарын моделдеп жатасызбы, графиктер табигый түрдө бул татаал өз ара көз карандылыкты чагылдырат жана талдайт. Бүгүнкү маалыматтарга негизделген дүйнөдө субъекттердин ортосундагы мамилелерди түшүнүү көбүнчө субъекттердин өздөрүн түшүнүү сыяктуу эле маанилүү - бул жерде графиктер чындап жаркырап турат.
Шилтемени болжолдоо - түйүндөрдүн (графиктеги объекттер) ортосундагы байланыштарды (же шилтемелерди) болжолдоону камтыган граф аналитикасынын негизги милдеттеринин бири. Элестеткиле, социалдык тармакта жаңы досторду сунуштоо, академиялык цитата диаграммасында потенциалдуу кызматташууну болжолдоо же электрондук коммерция шартында колдонуучулар менен өнүмдөрдүн ортосундагы келечектеги өз ара аракеттенүүнү болжолдоо - мунун баары аракеттеги шилтемени болжолдоонун мисалдары. Бул тапшырма тармактарды кеңейтүүгө, жетишпеген маалыматты чыгарууга жана аномалияларды аныктоого жардам берет. Колдонуучунун тажрыйбасын жогорулатуудан баштап, алдамчылыкты аныктоону жакшыртууга чейинки колдонмолор үчүн шилтемени алдын ала айтуу ийгиликтин негизги компоненти болуп саналат.
Шилтемелерди алдын ала айтуу үчүн биз Stanford Network Analysis Project (SNAP) долбоорунун Twitch Social Network маалымат топтомун колдонобуз. Бул маалымат топтому Twitch агымдык платформасындагы колдонуучулардын ортосундагы социалдык байланыштарды камтыйт, мында түйүндөр Twitch колдонуучуларын, ал эми четтери алардын ортосундагы достукту билдирет. Берилиштер топтому жакшы структураланган, бул аны алдын ала иштеп чыгууну жана аны менен иштөөнү жеңилдетет.
Аны улантуу менен, сиз долбоорду кантип орнотууну, маалыматтарды алдын ала иштеп чыгууну, моделди курууну жана аны чыныгы дүйнөдөгү маалымат топтомунда шилтемени болжолдоо үчүн баалоону үйрөнөсүз.
График-структураланган маалыматтар менен иштөө уникалдуу кыйынчылыктарды жаратат жана бул жерде График Нейрон тармактары (GNNs) ишке ашат. GNN - бул графикалык маалыматтар менен иштөө үчүн атайын иштелип чыккан нейрондук тармактын бир түрү. Белгиленген өлчөмдөгү киргизүүдө иштеген салттуу нейрон тармактарынан айырмаланып, GNN ыктыярдуу график өлчөмдөрүн башкара алат жана берилиштердин ичиндеги туташуу моделдерин колдоно алат. Түйүндүн кошуналарынан алынган маалыматты топтоо менен, GNN түйүндөрдүн атрибуттарын да, графиктин структурасын да камтыган өкүлчүлүктөрдү үйрөнүшөт, бул аларды түйүндүн классификациясы, шилтемени болжолдоо жана графикти классификациялоо сыяктуу тапшырмалар үчүн абдан натыйжалуу кылат.
Deep Graph Library ( DGL.ai ) бул GNNлерди оңой жана натыйжалуу куруу үчүн күчтүү инструмент. DGL менен иштеп чыгуучулар ар кандай тапшырмаларды, анын ичинде шилтемени болжолдоону чечүү үчүн заманбап GNN архитектураларын колдоно алышат. DGL бир тектүү жана гетерогендүү графиктер менен иштөө үчүн бир катар утилиталарды камсыздайт, бул аны изилдөөчүлөр жана практиктер үчүн ар тараптуу куралга айландырат. GNNлерди ишке ашырууну жөнөкөйлөтүү менен, DGL негизги техникалык татаалдыктарга батып калбастан, инновациялык чечимдерди иштеп чыгууга көбүрөөк көңүл бурууга мүмкүндүк берет.
Ушул негизди эске алуу менен, келгиле, GNNs жана DGL.ai аркылуу шилтемени болжолдоо моделин түзүүгө киришели.
Биринчи кадам талап кылынган китепканаларды импорттоо менен биздин долбоорду түзүү болуп саналат:
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
Тренингге берилиштерди даярдоо үчүн биз алгач Twitch берилиштер топтомун жүктөйбүз, аны график катары көрсөтөбүз, андан кийин аны окутуу жана тестирлөө топтомуна бөлөбүз. Биз DGLDatasetтен мураска алынган ыңгайлаштырылган классты түзөбүз, ал маалыматтарды жүктөө процессин түзүүгө жана графикке байланыштуу операцияларды иретке келтирүүгө жардам берет.
Бул жерде маалымат топтомун түзүү жана алдын ала иштетүү үчүн код:
# 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
График маалыматтарын жүктөө үчүн биз азыр маалымат топтомубузду инициализациялайбыз.
# init the dataset dataset = SocialNetworkDataset() g = dataset[0]
Кийинки кадам окуу жана тестирлөө комплекстерин түзүү болуп саналат. Биз окутуу жана тестирлөө үчүн четтерин 80/20 катышына бөлөбүз. Биз эки топтом үчүн оң (бар болгон четтер) жана терс үлгүлөрдү (болбогон четтер) түзөбүз. Чоңураак графиктер үчүн DGLдин 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())
Графиктин ичиндеги ар бир түйүндүн структурасын да, өзгөчөлүктөрүн да камтыган түйүндөрдү көрсөтүүнү үйрөнүү үчүн График үлгүсү жана Агрегация (GraphSAGE) конволюциялык нейрон тармагын колдонобуз. GraphSAGE ар бир түйүн үчүн маанилүү өкүлчүлүктү түзүү үчүн ар бир түйүндүн кошуналарынан алынган өзгөчөлүктөр маалыматын топтоо аркылуу иштейт. Бул процесс, кошуналарды бириктирүү катары белгилүү, моделге диаграммадагы бай, локализацияланган үлгүлөрдү үйрөнүүгө мүмкүндүк берет.
Ар бир GraphSAGE катмарында модель кошуна түйүндөрдөн маалыматты чогултуу үчүн топтоо функциясын (бул учурда "орто" функциясын) колдонот, андан кийин ал түйүндүн өзүнүн өзгөчөлүктөрү менен бириктирилет. Бир нече конволюциондук катмарларды топтоо моделге барган сайын алыскы түйүндөрдөн маалыматты тартып алууга мүмкүндүк берип, графиктин ичиндеги ар бир түйүндүн көрүнүшүн натыйжалуу кеңейтет.
Моделдин иштешин жогорулатуу жана ашыкча тууралоону азайтуу үчүн, биз ар бир катмардан кийин өчүрүүнү колдонобуз.
Келгиле, эми GraphSAGE моделин үч конволюциондук катмар менен түзөлү, ал аркылуу берилиштер кантип агып жатканын аныктоо үчүн 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
Үчүнчү катмардан кийинки чыгаруу ( h
) түйүн жалгаштырууларын камтыйт. Кандайдыр бир эки түйүндүн ортосундагы чектин (же шилтеменин) ыктымалдыгын болжолдоо үчүн, биз көп катмарлуу кабылдоочу (MLP) болжолдоочуну колдонобуз. Бул MLP эки түйүндү киргизүү катары кабыл алат жана алардын ортосундагы чектин болушу ыктымалдыгын көрсөтүүчү баллды эсептейт.
# 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 болжолдоочу төмөнкүдөй иштейт:
Бул катмарлуу мамиле болжолдоочуга түйүндөрдүн жуптарынын ортосундагы татаал мамилелерди кармап турууга жана чектин бар болуу ыктымалдыгы катары чечмеленүүчү чет упайын эсептөөгө мүмкүндүк берет.
Модельибизди натыйжалуу үйрөтүү үчүн, шилтемени болжолдоо боюнча моделдин иштешин сандык аныктай ала турган жоготуу функциясы керек. Бул милдет бинардык классификация маселеси болгондуктан - ар бир шилтеме бар же жок - биз жоготуу функциясы катары бинардык кросс-энтропияны (BCE) колдонобуз. Бинардык кросс-энтропия моделдин болжолдонгон упайлары менен чыныгы энбелгилердин ортосундагы айырманы өлчөйт (бар болгон шилтеме үчүн 1, шилтеме жок үчүн 0). Биз _with_logits
версиясын колдонобуз, анткени биздин моделибиз ыктымалдыктарды эмес, чийки упайларды (логиттер) чыгарат. BCEнин бул версиясы логиттер менен иштөөдө туруктуураак, анткени ал сигмоиддик функцияны жана кайчылаш энтропияны бир кадамга айкалыштырат.
Бул жерде жоготууларды эсептеген код:
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)
Моделди баалоо үчүн биз ROC ийри сызыгынын астындагы аймакты (AUC) метрикасын колдонобуз. AUC шилтемени болжолдоо үчүн абдан ылайыктуу, анткени ал дисбалансталган маалыматтарды эффективдүү иштетет , мында терс үлгүлөр (болбогон четтери) оң үлгүлөргө караганда алда канча көп кездешет. AUC упайы бизге моделдин учурдагы шилтемелерди жокторго караганда канчалык деңгээлде жогору койгонун сезет.
Бул жерде 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)
Эскертүү: Эсептөө графигинен тензорлорду алып салуу үчүн detach()
колдонобуз, бул градиенттерге таасир этпестен AUCти эсептөөгө мүмкүндүк берет.
Эми биз моделди үйрөтүүгө даярбыз. Баштоо үчүн, биз моделди, болжолдоочуну жана оптимизаторду ишке киргизип, окутуу циклин аныктайбыз . Биз ошондой эле башка гиперпараметрлердин арасында үйрөнүү ылдамдыгын, жашырылган катмардын өлчөмүн жана таштап кетүү ылдамдыгын белгилейбиз. Биз бул жерде гиперпараметрди оптималдаштырууну камтыбасак да, эгерде жоготуу платолору болсо, үйрөнүү ылдамдыгын тууралоо үчүн окуу ылдамдыгын пландаштыргычты колдонобуз , башкача айтканда, ал белгиленген доорлордун санына (бул учурда, 25) азайбай калат. Пландоочу бул болгондо, үйрөнүү ылдамдыгын эки эсеге азайтат, бул моделдин натыйжалуураак биригишине жардам берет.
Моделди инициализациялоо жана окутууну орнотуу үчүн код:
# 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}')
Келгиле, кодду иштетип, натыйжаны карап көрөлү:
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
Көрүнүп тургандай, модель 0,92ге жакын AUCке жетет, бул күчтүү алдын ала көрсөткүчтү көрсөтөт . Жоготуу турукташтырылганда, 500 жана 600 доорлорунун ортосунда үйрөнүү ылдамдыгы азайганына көңүл буруңуз. Бул тууралоо жоготуулардын бир аз төмөндөшүнө алып келүүчү жакшыраак тууралоого мүмкүндүк берет. Белгилүү бир чекиттен кийин, жоготуу жана AUC турукташып, модель жакындашканын көрсөтөт.
Келгиле, моделди тесттик маалыматтар боюнча баалайлы (окутуу учурунда колдонулган эмес) жана ал жакшы жалпыланганын көрөлү:
# 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}')
Натыйжада:
Test loss: 0.675215482711792, Test AUC: 0.866213400711374
Сынактын AUC көрсөткүчү машыгуу AUCтен бир аз төмөн, бул анча-мынча ашыкча тууралоону көрсөтөт. Бирок, AUC 0,866 моделдин дагы деле көрүнбөгөн маалыматтарда жакшы иштешин көрсөтөт . Гиперпараметрлерди андан ары тууралоо жалпылоону жакшыртышы мүмкүн, айрыкча ашыкча тууралоо тынчсыздануу жаратса.
Биздин үйрөтүлгөн моделибиз менен биз графиктеги түйүндөрдүн ортосундагы байланыштардын ыктымалдыгын алдын ала биле алабыз . Биз жаңы туташууларды аныктоого мүмкүндүк берген бардык мүмкүн болгон түйүндөр үчүн божомолдорду түзөбүз.
ndata['h']
атрибутунда сакталган бул кыстармалар шилтемени болжолдоо үчүн киргизүү катары кызмат кылат.
Бул кадамдардын коду:
# 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)
Эми бизде бардык талапкер жуптары үчүн божомолдор бар, биз кандайдыр бир конкреттүү түйүндөрдүн ортосундагы байланыш ыктымалдыгын текшере алабыз . Мисалы, баштапкы маалымат топтомунда түз байланышпаган 1773 жана 7005 түйүндөрүнүн ортосундагы байланыштын упайын жана ыктымалдыгын карап көрөлү:
# 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}%')
Бул жыйынтык:
Pair index: tensor([11066978]) Pair link score: 0.7675977945327759 Link probability: 68.30010414123535%
Биздин моделге ылайык, колдонуучу 1773 жана 7005 ортосундагы байланыштын 68,3% ыктымалдыгы бар.
Бул постто биз шилтемени болжолдоо үчүн Graph Neural Networks жана DGL колдонулушун көрсөтүп, социалдык графиктеги жаңы шилтемелерди алдын ала айтуу моделин ийгиликтүү түздүк . Салыштырмалуу кичинекей маалымат топтомун колдонуу бизге жергиликтүү машинада натыйжалуу иштөөгө мүмкүндүк берди. Бирок, графиктер миллиондогон же миллиарддаган түйүндөрдүн жана четтердин масштабына ээ болгондуктан, аларды иштетүү GPU кластерлери боюнча бөлүштүрүлгөн окутуу сыяктуу өркүндөтүлгөн чечимдерди талап кылат.
Кийинки кадам катары биз масштабдуу графиктерди иштетүү жана булут чөйрөлөрүндө шилтемени болжолдоону ишке ашыруу ыкмаларын изилдейбиз, бул ыкмаларды өндүрүш деңгээлиндеги берилиштер топтомуна колдонууга мүмкүнчүлүк берет.