Partial embedding adjustment framework for link prediction

Abstract

Link prediction is a rudimentary graph analysis task that aims at inferring missing links or future ones that are likely to form, with tremendous scientific and commercial applications in a wide range of domains. Convolutional Graph Neural Networks (ConvGNNs) are an emerging class of graph analytic tools, demonstrating promising results in various graph analytical tasks. ConvGNNs are commonly used as encoders of Graph autoencoder (GAE) frameworks to address unsupervised graph analytic tasks including link prediction. However, link prediction based on graph auto-encoding suffers from a major limitation: the training of the encoder relies on negative (unseen) edges while the reliability of negative edges is not guaranteed in a link prediction problem. Such training scheme degrades the accuracy of the link prediction model, especially in most real-world networks, which are typically sparse with abundant negative edges. Therefore, this study proposes a Partial Embedding Adjustment (PEA) framework for link prediction to handle the above problem. PEA replaces the training targets from the edges used in graph auto-encoding to the edge embedding components whose reliability could be estimated, thus reducing the reliance of training on negative edges. To achieve this, PEA follows an encoder-decoder architecture where the encoder is a ConvGNN and the decoder incorporates the following segments: (1) a mini-batching training scheme with triad sampling (2) two aligned edge embedding construction measures for training and link inference (3) a selection strategy to choose edge embedding components for adjustment. PEA uses the relationships between the nodes of the sampled triads to select and adjust the edge embedding components. The similarity measure of inference would be an indicator of linkage probability. We evaluate PEA based on its ability to correctly distinguish negative and positive edges after training on an incomplete dataset where 5% to 85% of edges are removed randomly. Our experimental evaluations on three popular datasets in this domain, Cora, PubMed, and Citeseer, present an average 9% increase in the AUC-ROC score compared to GAE when 85% of the edges are removed; and show similar performance levels when 10% of edges are removed. These results indicate that replacing auto-encoders with frameworks that take the reliability of negative edges into account can lead to the development of more accurate link prediction models.