关联发现 工作内容阶段性总结 刘达欣 2015-8-31

目录 背景 宏观方法 具体方法的调研 具体方法的选择

背景 问题：发掘两个实体间的所有关系。实体关系基于Dbpedia的关联ttl文件给出，将实体信息映射到字典，并将实体关联的多重关系忽略，关联发现问题便建模成了普通图里的路径发现问题(边长函数为l=1)。 Baseline做法：双向广度优先搜索(BiBFS)。以hop=4为例，BFS的搜索空间为n4,其中n为图的平均度。而双向BiBFS的搜索空间为2n2。 1

1 背景 Baseline做法的问题：双向BFS，但面临着性能不佳的问题。 实验表明在Dbpiedia中有边数14M条，顶点数(实体)12M个， 4M个为非孤立点。取10K个节点对做实验，平均每对实体关联搜索hop=4时，用时3s左右，hop=5的用时在40s左右，hop=6时则达到了3分半，这是不能接受的。 1

2 宏观方法 基本思路：在BiBFS执行时，实际上搜索了许多不会产生路径的节点，尝试使用距离oracle进行剪枝。 分析：以hop=4为例以下是距离oracle的剪枝示意图 2

宏观方法 模拟oracle实验： 实验方法：从Dbpedia中挑选100（由于时间关系）对实体进行了距离orcale模拟实验。实验思想为使用两次BiBFS模拟oracle剪枝工作：第一次BiBFS的结果朴素进行，第二次BiBFS的过程中使用第一次BiBFS求得的所有路径引导剪枝(如果oracle能够精确回答任意两点间最短距离，那么这两种剪枝最后的效果应该一致)。 2

宏观方法 模拟oracle实验： 实验结果：以下为100对实体关联对的模拟实验结果。根据100对的结果计算出的平均加速时间为61.93%。可见oracle确实可以大幅提速。特别的，在hop=4的路径中如果经过了hub节点，baseline方法可能会在5分钟之后抛出oom异常。 2

具体方法的调研 调研： 在一篇总结性文章中给出了图的(近似)距离 oracle构建研究现状总结。文章最后也给出了复杂 网络的距离orcale。方法总结有 1. 三角法(triangulation) 2. 两跳覆盖(two-hop covers) 3.核心边缘法(core-fringe) 4.嵌入法(Embedding) 3

具体方法的调研 各方法基本思路： 1.三角法基于d(s,t)<d(s,v)+d(v,t)的三角不等式计算(近似)距离。三角法要求选取一个顶点集V的子集作为里程碑，并计算保存里程碑间的距离信息、每个顶点v的邻域距离信息。 2.两跳覆盖法基于捷径(shortcut)、距离标号法。基本思想是任意s,t至少存在一个位于s-t最短路径上的节点v属于l(s)∩l(t)，l(s)和l(t)分别为s,t的标注。 3.核心边缘法，利用了许多无标度网络(scale-free network)核心之外拥有相当小的树宽(tree-width) 的属性。 4.嵌入法，调研工作还在继续。 3

具体方法的调研 性能比较： 1.三角法中要求存储里程碑间，节点与里程碑间的距离信息。存在着α=2,3的近似距离oracle，和精确距离oracle。空间复杂度浮动于O(n4/3)-O(n7/4)之间。并且如果图中的任意两点距离比较近的话，会使得产生绕路现象。 2.两跳覆盖法的一个实现Akiba[2013]的空间复杂度为 O(wmlogn)，其中m为边数，n为顶点数，w为树宽。可见如果图的树宽比较小，那么空间上是较优的。查询时间为O(wlogn)。 3

4 具体方法的选择 针对三角法和两跳覆盖法，最新的两种实现分别为Agarwal et al.[2012]，以及Akiba[2013]两种精确距离oracle。下面介绍 两种方法的实现。 Agarwal et al.[2012]精确三角法： 1.对于每个点u，以概率 抽取为里程碑，其中α为参数，deg(u)为u的度。这保证了中心点(hub)能尽可能选为里程碑。计算所有里程碑间的距离，存于oracle 2.对于每个顶点v，设其与里程碑集的最短距离为d,计算v的邻域(到v距离小于等于d的点，等于d的点为v的边缘)并保存。 3.对于查询的任意点s,t。若s在t的领域或者t在s的领域，最短距离直接返回最短路径，若s或t任一为里程碑，直接返回最短路径。否则,求s与t边缘的交集R，若R非空，则最短路径为 ，其中v属于R。否则调大参数α。 𝑃 𝑠 = 𝑚 𝛼𝑛 𝑛 • 2𝑛 𝑚 •deg(𝑢 4 𝑑(𝑠,𝑡)=𝑑(𝑠,𝑣)+𝑑(𝑣,𝑡

4 具体方法的选择 Akiba[2013]两跳覆盖法： Akiba[2013]基于剪枝的BFS算法。对于每个顶点v，计算一个v的标号集合l(v)={u,duv}。U为顶点集V的子集，duv为u-v的距离。所有l(v)的集合构成了一个索引(index)记为L。定义任意(s,t)的L查询返回L中计算得到的s-t最短距离。QUERY(s,t,L)=min{dvs+dvt | (v,dvs)∈L(s),(v,dvt)∈L(t)}。索引(实际上的oracle)的构造通过n次的剪枝BFS构造。第k次(处理节点vk)的索引Lk(u)有Lk(u)=Lk-1(u)∪{(vk,d)}。其中d为vk与u距离，QUERY(vk,u,Lk-1)>d。如果QUERY(vk,u,Lk-1)<=d则剪掉u，并不再BFS中遍历其后继。 Akiba[2013]的方法确保了对任意s,t至少存在一个位于s-t最短路径上的节点属于l(s)∩l(t)。并证明了通过剪枝BFS得到的标号集为最小标号集(标号中没有冗余信息)。其性能取决于vk的顺序，顺序取得好，多次BFS的后几次边收敛得快(遍历节点少)。在复杂网络中可以根据节点的度进行排序处理(利用了复杂网络的特性之一)。 4

具体方法的选择 Agarwal et al.[2012]三角法：存在一定的缺陷(可能漏解)，如果图的节点对平均距离比较小，会产生绕路。而在Akiba[2013]的实现中，如果图的平均距离比较小，则需要较大的参数α来覆盖查询，换句话说空间需求变大。后续的实验表明Dbpedia的平均距离比较小。一下为实验的结果分布。 4

具体方法的选择 Akiba[2013]两跳覆盖法：其面临的主要问题是内存占用可能太大，需要实验尝试一下内存会不会溢出。 4

下一步计划 后续的工作将围绕oracle的构建展开，包括模拟oracle进一步实验，对不同oracle实现的可行性实验，调研其他两种尚未涉足的oracle构建方法 参考文献: R. Agarwal, M. Caesar, P. B. Godfrey, and B. Y. Zhao. 2012. Shortest paths in less than a millisecond. In 5th Workshop on Online Social Networks (WOSN). //三角法精确距离 T. Akiba, Y. Iwata, and Y. Yoshida. 2013. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In ACM SIGMOD International Conference on Management of Data (SIGMOD). 349–360. //两跳覆盖精确距离 4