Comparing Machine Learning Algorithms For Link Prediction

Maryam Kheirkhahzadeh - markhe@kth.se, Pablo Laso Mielgo - plaso@kth.se, Lucas Trouessin

- lucastr@kth.se

Abstract. In this paper, Instead of predicting node embedding, we predict the link

between each two pairs of nodes using some machine learning algorithms. Link

prediction algorithms aim to extract information about future interactions in the net-

works. We apply cosine similarity on the node embeddings, which is calculated by

the DeepWalk algorithm to train the ML algorithms. We use grid search to tune the

parameters of machine learning models to optimize AUC and compare the results

Some other methods consider second-order heuristics, such as Adamic-Adar (AA)(3). High-order

heuristics consider the whole network, such as SimRank (SR) (6). There are some research that

shows the high-order heuristics have better performance in comparison to the first and second-

order ones (7). Our contribution are as follows:Instead of predicting node embedding, we try to

predict the edge between each two pairs of nodes. We take these steps: 1) find a link-prediction

algorithm based on cosine similarity function which is calculated on the node embeddings in the

social networks. We use the DeepWalk algorithm to find the node embedding. 2) We compare

some machine learning models based on tuning parameters to have a high AUC. In addition, we

show a number of other regression and classification metrics for different ML algorithms which

we have used. We consider Cosine similarity function to train and test our models.

score. These algorithms have been applied to many networks and experiments have shown that

better performance can be achieved. The simplest one is based on the Common Neighbor.

Hasan et al. (10) pointed out that feature set extraction depends on the actual application. They

used bibliographic data set. They compared the results of various classification algorithms, includ-

ing SVMs, decision trees, nearest neighbors, and more. The result shows that SVM is better than

others. However, they used some different features from papers and authors and some other at-

tributes from the network. Benchettara et al. (11) apply supervised machine learning to predict the

links in two-mode social networks. However, these studies don’t consider the dynamic evolution

and diversity of the networks. Although the classification model can improve performance, how to

1

choose the appropriate features is still a problem. Moreover, if the networks are sparse, the positive

3. Data Description. We use the Facebook data set. This link contains 5 different data sets. We

implement different machine learning algorithms on three data sets from the Facebook data set,

consisting of politician edges data set, company edges data set, and government edges data set.

Nodes represent the pages, and edges are mutual likes among them.

We describe the attributes of these data sets here. After calculating node embedding, we map

the data to two dimensions via PCA. The picture of three diagrams are as follows.

Politician edges data set attributes:

• #edges: 41729

• #nodes: 5908

• Clustering coefficient: 0.193

2

• Average path length: 0.166

Government edges data set attributes:

• #edges: 89455

• #nodes: 7057

• Clustering coefficient: 0.205

• Average path length: 0.816

4. Data pre-processing. Networks are based on relationships between nodes. To have a good

representation of networks, we need a data structure that reflects the properties of that network.

3

4.1. DEEPWALK. DeepWalk is an algorithm proposed for learning latent representations of nodes

dimensions 16, 64, and 128. Then we can use these vectors to learn our models and link prediction.

In this paper, we demonstrate the results for dimension 16 since the models have better performance

with this setting.

5. The approach. We see the link prediction model as a classification problem. In fact, the pairs

of nodes with an edge belong to class 1 and the remaining edges belong to class 2. We use cosine

similarity between node embedding vectors to train the models, as we explain in this section.

We use the Gridsearch method to tune the parameters of each machine learning algorithm. We

set Gridsearch to find the best set of parameters based on AUC. So, we can compare AUC of each

model to the AUC of the other models.

5.1. TRAINING BASED ON SIMILARITY METHODS. We should train the models to predict 1 for

each pair of nodes with edge and zero for nodes without edge. Considering memory and time

complexity, we cannot train the model with the node embedding vectors.

5.1.1. TRAIN SET. We choose 10% of edges randomly and keep them for the test phase. There-

of node pairs from non edges set randomly with y test value equal to zero.

5.1.3. SIMILARITY FUNCTION. Each row of the train set corresponds to a pair of nodes, with or

without edges. The corresponding row of y train has 1 for edge and has zero when there is no edge.

We calculate the cosine similarity of this pair of node embedding vectors and save it as one row in

the train set. In fact, we also tested the Euclidean similarity. However, the results were not suitable

enough. Therefore, we decided to demonstrate the results for cosine similarity in this paper.

5.2. METRICS TO EVALUATE OUR ALGORITHM . We compare all the machine learning algo-

rithms based on the calculated AUC. In addition, we demonstrate some other important metrics.

We use two built-in functions predict proba and predict to evaluate the supervised trained model.

4

predict proba accepts a single argument as a test set and returns an array containing the predicted

• Area Under the Curve. AUC represents how much the model is capable of distinguishing

• Recall. The recall is calculated as the ratio between true positive to the total number of

positive samples.

• Precision. The precision is calculated as the ratio between true positive to the summation of

true positives and false positives.

• Brier score. The Brier score measures the mean squared difference between the predicted

probability assigned to the possible outcomes for each item in the test set and the actual

outcome for that item.

• F1-score. The F1-score is a combining measure of precision and recall. In fact, it is defined

as the harmonic mean of the model’s precision and recall.

6. Results. The results show that DecisionTree model has the highest AUC for Politician edges

we show the training time is extremely different for machine learning algorithms in figures 10, 13,

and 16. DecisionTree and LogisticRegression have the lowest training time for the three data sets.

DecisionTree has the lowest MSError with precision equal to three between other ML algo-

rithms for three data sets. See figures 9, 15, and 12.

Considering BrierScore, DecisionTree is in the best three ML algorithms. See figures 9, 15,

and 12.

5

6

7

Figure 14. Metrics for Government edges data set

Figure 15. Metrics for Government edges data set

8

Figure 16. Training time for Government edges data set

7. General difficulties. The most important problem is that tuning parameters for different mod-

els is extremely time-consuming. We use grid search for finding the best set of parameters based

on AUC. The built-in function GridSearchCV implement grid search. We have three data sets,

with 6 machine learning models. we run them with three different dimensions. We implement

node embedding for 16, 64, and 128 dimensions. So running GridSearchCV for 6x6x3 cases is so

expensive and takes time. The results are superb for only dimension equal to 16. Therefore, in this

paper, we have shown the value of metrics for this dimension.

9