Link prediction on network embeddings

Question

A picture is worth a thousand words, so I decided to illustrate how I imagine the procedure of link prediction on network embeddings. In the figure below the LR model stands for the "Logistic regression model".

Train and test networks are composed of an equal number of positive and negative edges (training examples).

My question is: should I learn embeddings on a network defined by positive edges only or should I also consider negative edges in the network embedding process?

Any idea is appreciated.

Answer 1

The short answer is: You are correct, in order to compute node embeddings you only need the "true" train edges. These edges span a training graph which is the input we give NE methods to learn the node embeddings. Non-edges are only used in the binary classification problem.

The longer answer is: The most effective way to compute link predictions from embeddings is via binary classification. The node embeddings first need to be transformed into edge embeddings (e.g. averaging the embeddings of i and j to get the embedding of e=(i,j)) and then solve a binary classification problem. The binary classifier (usually Logistic regression) will take the edge embeddings as examples and try to learn a mapping to their corresponding "label" where these labels are 1 for the "true" edges and 0 for the non-edges. Therefore, in addition to the edge embeddings of "true" graph edges, we need to compute the edge embeddings of a set of non-edges in the graphs (those with label 0). This is what we usually refer to when we talk about negative sampling for LP.

I believe the confusion here comes from the way some popular NE algorithms compute the embeddings. For instance, methods base on matrix factorization directly take the train graph you give as input, compute the adjacency matrix, factorize it and return the node embeddings. Other methods e.g. Deepwalk, Node2vec or LINE have a special way of learning embeddings (Skip-gram from work embedding literature) and require "negative sampling" in the embedding learning process itself. These methods will select, from that train graph you give them, a set of non-edges or paths of non-connected edges to learn which node vectors should be put close together and which should be far. The NE methods will select these samples of non-edges themselves and in different ways, so the user generally doesn't have any control over it.

I hope this clarifies your question.

Answer 2

To add to the other answer,

• If you want just to make predictions, all your data is training data and you can make predictions for data that you have not seen. You do not need to split your data into two parts.

• The splitting is hence only useful to evaluate the performance of link prediction methods. Your drawing above does not reflect a standard machine learning pipeline. Unbiased estimates of performance can be computed only in the following manner: from the train data you construct a model (which here would be two parts; the network embedding and the binary classifier such as logistic regression), from which you can make predictions. You evaluate the predictions on the ground truth that was withheld from the learning process, which is the test set. Hence, the pipeline would be:

Left-hand side: Train network -> Network embedding -> LR model -> Predictions

Right-hand side: Test network -> Evaluation

Cross link from land-hand side ‘Predictions’ directly to right-hand side ‘Evaluation’.

So, the predictions are made from the model (for example logistic regression which is in turn based on a network embedding), which is learned on the training data. This is true not just in this link prediction setting but generally for any machine-learning model evaluation setting.

As an additional remark, there is no way to align network embeddings learned on the train and the test network, so an approach including a new embedding on the test set would not make sense.

Hope fully this clarifies the setting?