aghasemian/optimallinkprediction

This page is a companion for our paper on optimal link prediction, written by Amir Ghasemian, Homa Hosseinmardi, Aram Galstyan, Edoardo M. Airoldi, and Aaron Clauset. (arXiv:1909.07578)

optimallinkprediction's Issues

Questions about the train/test split

Is this a correct interpretation of how this works:

By randomly removing edges we're simulating creating a 'past' state of the graph. In the paper you do so twice, so we end up with three 'snapshots' of the graph: G_train < G_ho < G_orig

Then, in the training phase we're trying to predict the 'missing' edges E_ho \ E_train with every non-edge of G_ho as negatives, and in the test phase we're trying to predict the 'missing' edges E_orig \ E_ho with every non-edge of G_orig as negatives.

If that's all correct, why is it necessary to create two snapshots? Why can't we just randomly remove edges once to create: G_past < G_orig, positives are E_orig \ E_past and negatives are non-edges of G_orig, and then just do a random 80-20 split for training/test? In other words, why do training and test have to be separate graphs?

And, if we did want to create two snapshots, why does E_train have to be a strict subset of E_ho? Couldn't we have the random edge removal for G_train and G_ho be independent?

Thanks for any help. I'm trying out something similar to your paper, so thanks for this repo and the paper.

SVD truncation

Hi @Aghasemian

Just spotted a potential bug in the code:

https://github.com/Aghasemian/OptimalLinkPrediction/blob/ce6b1934bab396b8e6283c3afab343ab2aea830f/Code/OLP.py#L429C5-L434

Here, the singular values with large magnitude are assumed to be positive, though in the singular value decomposition, the sign is not uniquely determined. Consequently, it could happen that the principal component is truncated when it is associated with negative singular values.

I think the right implementation is to take the magnitude by np.abs(sig) before truncation.