【Anton博士论文】图结构相似性与表示，210页pdf

从社交网络到Web和大脑结构，图是各种系统的一种自然表示。即使当数据没有显式地相互连接时，将其转换成图表以便进一步分析通常也是很方便的。许多涉及图的任务，如链接预测、社区检测和分类，依赖于图中节点或图整体之间的各种相似度定义。然而，这种相似性大多是隐式的，这意味着物体在某些空间中不被特征向量表示。相比之下，现代机器学习方法要求明确表示欧几里得空间中的对象。为了在图数据上利用机器学习的能力，我们必须具有适当的图的显式表示。

本论文研究针对图结构数据表示的有效的算法。我们关注的是算法的可扩展性，因为它们必须有能力处理Web大小的图，以能够应对实践。局部图算法具有这种能力; 我们引入可扩展的局部算法来表示节点，边，和整个图作为向量在欧氏空间。通过潜在相似性来研究表征，使我们能够阐明以前的工作，并将非常理想的特性引入我们提出的模型。值得注意的是，我们介绍了第一个随时表示图节点的算法。对于整个图的情况，我们提出了表示，它使图的多尺度比较和其局部逼近的方法。我们通过实验验证了我们的方法并没有为了算法的可扩展性而牺牲表示的表达性。我们介绍了图分析的新应用，并在具有数十亿节点的大规模图上使用我们的方法。

https://bonndoc.ulb.uni-bonn.de/xmlui/handle/20.500.11811/9119