基于图的大规模身份解析

由于我们的标识符由顶点和关系来表示，而顶点之间的关系由边表示，所以我们执行标签传播算法进行身份解析。标签传播可以帮助我们找到标识符的所有连通分量（即，任意两个顶点之间是否有路径？）。我们考虑了好几种工具来执行标签传播算法，最终因为HashMin占内存小，所以选择了它。

TigerGraph 为数据库中的每个类型或内容的顶点提供了方便、唯一的内部数值 ID。执行 HashMin 时，我们首先将标签分配给与TigerGraph 内部ID相等的每个顶点，然后将每个顶点的标签更新为其所有相邻标签中最小的标签值。这个更新过程会重复进行，直到连通分量中的所有顶点都有相同的唯一标签为止。

在标签传播算法连续运行过程中，我们可以向图中导入新数据，同时运行 TTL 使某些顶点和边失效，删除一些被识别为坏数据的顶点等。这样做能改变标识分组，例如，一些连通分量可能会因为失掉一个标识符而分裂成两个分量，又或者相反， 得到一个连接标识符，使得两个较小的连通分量合并成一个较大的分量。这样一来，当重新运行 HashMin 时，相似或相同的标识分组可能会接收不同的标签。但这并不适用于广告服务，因为在多次运行 HashMin 的过程中，我们很难持续追踪标识分组。为了实现在不同的运行时能够持续进行标签，我们采用改良版的 Gale-Shapley 算法，该算法能在连续两次运行之间，对连通分量进行排序和配对，因此，我们就可以用旧标签覆盖已经配对好的连通分量上的新标签。

在运行标签传播算法之后，我们有时会发现一些非常大的连通分量用边连接了多个合成分组（即我们想要保留的分组）。此时，我们采用中心性措施来分离它们。