VLDB '11 | PathSim: Meta Path-Based Top-K Similarity Search in Heterogeneous Information Networks

[jasperzhong]

https://www.ccs.neu.edu/home/yzsun/papers/vldb11_topKSim.pdf

很早的工作，提出了meta-path的重要概念.

[jasperzhong]

异构图有多种关系，meta-path其实就是关系的组合.

这篇paper本身是提出meta-path概念，然后算两个node的相关性的，提出了叫PathSim的方法. 非常简单，给定一个meta-path，和两个node x和y，算x -> y多少个paths，算x -> x多少个paths，算y -> y多少个paths，带进去算一下就得到了x和y的similarity.

然后定义了commuting matrix概念，其实就是多个关系的adjacency matrix的乘积.

有了commuting matrix，计算pathsim非常方便，直接 $s(x_i, xj) = \frac{2M{i, j}}{M{i, i} + M{j, j}}$

[jasperzhong]

后面还谈了PathSim的一些优化，如何deal with sparse graph. 略.

[jasperzhong]

漏了一个graph schema的概念，表示各个node type之间的relationship.