论文标题
研究估计的Kolmogorov复杂性作为链接预测的正则化的手段
Investigating Estimated Kolmogorov Complexity as a Means of Regularization for Link Prediction
论文作者
论文摘要
图中的链接预测是网络科学和机器学习领域的重要任务。我们研究了基于图形的kolmogorov复杂性的近似链接预测的灵活方法，该图形的复杂性与链接预测算法的最新进展相兼容。非正式地，对象的kolmogorov复杂性是产生对象的最短计算机程序的长度。复杂的网络通常部分通过简单的机制生成。例如，许多引用网络和社交网络大致不含规模，可以通过优先附件来解释。偏爱用更简单的生成机制预测图的偏爱激发了我们选择Kolmogorov复杂性作为正规化项。在我们的实验中，正则化方法在许多不同的现实世界网络上显示出良好的性能，但是我们确定这可能是由于聚合方法而不是对Kolmogorov复杂性的任何实际估计。
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.
