论文阅读：Robust Entity Resolution using Random Graphs
论文题目：Robust Entity Resolution using Random Graphs
发表时间：SIGMOD’18, June 10-15, 2018, Houston, TX, USA
论文作者：Sainyam Galhotra 、 Donatella Firmani、 Barna Saha 、Divesh Srivastava
Indroduction
论文的意思是利用随机图，来完成实体解析(Entity Resolution),那么何为实体解析呢？
根据《实体解析与信息质量》，可以了解到：
实体解析（Entity Resolution）是一种用于判断两条记录是否指向同一事物的过程。
实体这个术语描述了过程的目标是真实世界的事物，比如某个人，地点或者物品。
而解析则描述了回答这样的一个问题的过程：两条不同记录是否指向了同一个真实实体？
尽管实体解析的定义描述的是两条记录之间的关系，但事实上，这个定义也可以被延伸到一个更大的记录集合上，相应的，该过程的输出则聚合了指向同一实体的所有记录的子集/簇。在这样的上下文中，ER的定义也可以解释为：“识别并整合所有定义同一真实世界实体的记录的过程”（Benjelloun,Garcia-Molina, Menestrina, et al., 2009）。
实体解析
例如在上图中，实体解析的意思就是，判断出有哪一些表示的是同一个物体，比如上面的iPhone Two和iPhone 2表示的就是同一个手机。
实体解析
又如上图中，实体解析就是选出哪些照片表示的是同一个人，这里有古天乐，周星驰，张震。
Previous approach
这里介绍以前的方法，我们用上面提到的判断照片是否是同一个人举例，这样做的前提是我们已经得出了，这两个照片是同一个人的概率是多少。怎么得出呢，微软提供了这个服务。
Microsoft tool TwinsOrNot
可以在这个网站，上传照片进行对比识别。
概率图
在进行完，上传对比之后，我们可以得到，上面的概率图，其中绿色就表示为同一个人概率超过0.5的，红色就是低于0.5，线越粗，概率越高，红色虚线说明概率极低。得到概率图之后，就要在此图上运用方法找出所有同一个人的照片了。
基于绿色连接的寻找
在这种方法里，只要是绿色连接的照片我们就认为是同一个人，以此来进行划分，得到结果。显然这种方法并不准确，高度依赖于事先判断的概率，这里就把张震和周星驰当作了同一个人。
基于相似度
每条边上都有相似的概率，这种方法就是把概率特别相近的划分到一起，当作是同一个人。我们可以从上图中看到，这种方法也是错误的，它并没有把所有的周星驰照片都找出来（因为年轻的周星驰和年老的周星驰相似概率并不高）。
正确的划分
正确的划分得到的应该是如图所示的这样，分成了三个组，找出了古天乐、周星驰、张震。
为了准确的找出所有的人，引入了Oracle这个概念，并不是指的数据库公司，而是表示为一种众包的抽象。因为在很多情况下，人去判断是否相似，是要比计算机容易很多的。例如：
Online advertising = Internet ad
人们可以很快的判断出这两者都是网络广告的意思，但计算机却很困难，所以提出的Oracle相当于是一个系统，可以回到如下的问题。
Oracle
而且我们假定，Oracle总是会回答正确。
我们有了Oracle，并且Oracle总是会给出正确的答案，显然可以通过Oracle来回答两张照片是否是同一个人这种问题。那应该如何觉得询问的顺序呢？也就是应该选择哪两张照片去询问呢。
询问顺序
这里有两种方式，其一就是普通的方式，随机选取一对进行询问，显然这种方法是耗时、耗力的。其二就是聪明的方法，根据概率的大小去进行询问，先询问概率大的，因为他们更可能是同一个人。
通常来说，以前使用的方法就是按照边的概率进行询问的方法。
按边的概率询问
在这里我们先访问古天乐那条边，得到的结果是是同一个人。
按边的概率询问
然后询问其他的边，得出了正确你的结果。
按边的概率询问
在询问完成后，得出了正确的结果，完成了实体解析。
询问错误的结果
我们假设的是Oracle总是给出正确的结果，但是如果Oracle给出了错误的结果，
例如在上图中把周星驰和张震当作一个人，那么我们最后的实体解析就是错误的。
错误的结果
Our approach
以前的方法，都是假设Oracle一定会回答正确，但是实际情况中Oracle并不总能回答正确，会得到错误的结果。所以这篇论文就提出了，一个纠正错误的工具。
实体解析处理流程
这是这篇论文中，实体解析的处理流程，实现进行记录的收集，也就是上图的收集那些照片，再之后就是使用前文所讲的策略，以及本文提出的纠错层。
这个纠错层的关键思想有两方面：
1、在并入新结点时，进行多次的判断。
2、通过合并以及分裂过程来进行纠错。
并入新结点
在并入新结点时，我们不再只是查询一对，而是查询许多对，如上图中要将New Node并入其中时，我们会对许多对进行判断，如果相似的值达到了阈值，则认为时一个人，将新结点放入其中。
合并过程
合并过程主要是为了提高recall，也就是召回率，意思就是希望可以找到所有的同一个人照片。主要的过程就是，在两个聚类中的结点，不断的进行询问，判断是否为一个人，然后决定是否合并。
分裂过程
在已经完成的聚类里面，会存在Low confidence node ，就是纸盒部分结点连接，比如图中的张震，这种结点，就很有可能，并不属于这个聚类。所以我们应该想办法对其进行判断。
分裂过程
解决的办法，就是判断Low confidence node和其他结点的相似度，如图中，判断出不相似，那就将其剔除。
前文所说，这是一个纠错的工具，所以会有使用上面的不同，这里介绍了三种不同的使用方法：
使用方法一：
Eager:每一次查询，都使用这个纠错的工具。这样会降低效率，召回率降低，就是不
能找到所有的同一个人的照片，但是准确度会变高。
使用方法二：
Lazy:不使用纠错的工具。这样会让准确度降低，但是召回率变高。
使用方法三：
Adaptive pipeline:高概率的结点就不适用纠错工具，就是两张已经很相似的照片，不
会再使用工具询问。
Experiments
实验结果
上图是在不同的数据集上做的实验，横坐标表示查询的数量，纵坐标表示效果，得分越高，效果越好，从图中看出，Adaptive pipeline的效果是非常好的，仅次于理想情况。
网友评论