张璇-2016.10.28组会-在大规模异构网络中的原路径检测

xuanzhang

标题：在大规模异构网络中的原路径检测（Discovering Meta-Paths in Large Heterogeneous Information Networks）
报告人：张璇
摘要：异构网络实际上是一个图模型，图模型由点和边组成。图中的点和边都有自己的类标签（如，在社交网络中，主要节点是人，那么人就是图中点的类标签；主要边是好友关系，那么好友关系就是边的类标签），我们可以利用这些信息进行更加精准的预测。由于真实网络大多是异构信息网络（点的种类大于1或边的种类大于1），所以本文主要致力于如何在异构网络中找到跟目标问题最为相关meta-paths. 现有的寻找相关meta-paths的方法主要有两种: 一种是由专家根据专业知识给出相关的meta-paths; 一种是通过计算机的方法找出相关的meta-paths. 对于规模愈来愈大的异构网络研究，通过方法一来指定meta-paths的方法并不现实，专家通常会忽略较长的meta-paths，而往往这些较长的meta-paths对预测问题的研究有很大的帮助；另外，通过现有计算机的方法，想要找到最相关的meta-paths，需要枚举所有的可能，这有着极高的时间复杂度，尤其当数据量不断增大时，就成为NP-hard问题。而本文提出的方法是在没有已知meta-paths的情况下，使用贪心策略，自动生成相关的meta-paths。本文的实验就是在大规模的真实异构信息网络YAGO(Yet Another Great Ontology,主要是从维基百科提取的结构数据)和DBLP（Digital Bibliography & Library Project，主要包含文献目录信息）中进行的，并通过连接预测的方法验证了选取meta-paths的准确性和有效性。
本文的主要工作：
（1）提出自动生成meta-paths的Forward Stagewise Path Generation算法。
（2）基于贪心策略设计了方便用于图遍历的贪心树结构。
（3）做了大量的实验，证明选取meta-paths是有效的，并跟现有的一些链接预测方法进行比对。
创新点：
（1）提出自动生成meta-paths算法。
（2）结合现有的两种相似性计算方法（Path count和Path-constrained Random Walk）,提出用Biased Path-constrained Random Walk方法去计算节点间相似性。
（3）可以从实验结果中发现一些跟现有认知相悖的结论。

实验测试：选取真实网络中的部分数据，应用作者提出的算法，通过连接预测检验meta-paths的有效性。

术语解释：
meta-path：一组由结点标签和边标签构成的序列


参考论文：
[1] Meng C, Cheng R, Maniu S, et al. Discovering meta-paths in large heterogeneous information networks[C]//Proceedings of the 24th International Conference on World Wide Web. ACM, 2015: 754-764.
http://www.www2015.it/documents/proceedings/proceedings/p754.pdf

报告ppt: