Investigating Estimated Kolmogorov Complexity as a Means of
  Regularization for Link Prediction
  Link prediction in graphs is an important task in the fields of network
science and machine learning. We investigate a flexible means of regularization
for link prediction based on an approximation of the Kolmogorov complexity of
graphs that is differentiable and compatible with recent advances in link
prediction algorithms. Informally, the Kolmogorov complexity of an object is
the length of the shortest computer program that produces the object. Complex
networks are often generated, in part, by simple mechanisms; for example, many
citation networks and social networks are approximately scale-free and can be
explained by preferential attachment. A preference for predicting graphs with
simpler generating mechanisms motivates our choice of Kolmogorov complexity as
a regularization term. In our experiments the regularization method shows good
performance on many diverse real-world networks, however we determine that this
is likely due to an aggregation method rather than any actual estimation of
Kolmogorov complexity.
