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.
Code (0)
등록된 구현이 없습니다.
Tasks
Link PredictionPredictionSimilar Papers 제목 키워드 기반
Network-to-Network Regularization: Enforcing Occam's Razor to Improve Generalization
What makes a classifier have the ability to generalize? There have been a lot of important attempts to address this question, but a clear answer is still elusive. Proponents of complexity theory find that the complexity …
Causal Inference by Stochastic Complexity
The algorithmic Markov condition states that the most likely causal direction between two random variables X and Y can be identified as that direction with the lowest Kolmogorov complexity. Due to the halting problem, ho…
Causal InferenceWahkon: A Statistically Principled Deep RKHS Superposition Network
Deep learning excels at prediction but often lacks finite-sample guarantees and calibrated uncertainty; RKHS (Reproducing Kernel Hilbert Space)-based methods provide those guarantees but struggle to adapt in high dimensi…
SGD Through the Lens of Kolmogorov Complexity
We prove that stochastic gradient descent (SGD) finds a solution that achieves $(1-\epsilon)$ classification accuracy on the entire dataset. We do so under two main assumptions: (1. Local progress) The model accuracy imp…
LEMMAOn the Optimal Expressive Power of ReLU DNNs and Its Application in Approximation with Kolmogorov Superposition Theorem
This paper is devoted to studying the optimal expressive power of ReLU deep neural networks (DNNs) and its application in approximation via the Kolmogorov Superposition Theorem. We first constructively prove that any con…