一种轻量级的高效图顶点重排方法

摘要

本发明涉及一种轻量级的高效图顶点重排方法，所述方法包括以下步骤：S1：加载需进行ID重排的图，并进行预处理，确定种子点；S2：选择种子点，并通过种子点生成超顶点；S3：根据超顶点为需进行ID重排的图的顶点分配新ID，从而实现图顶点重排。本发明通过合并低入度顶点再分配ID的方法，使得合并顶点的共同邻居拥有相近的ID。由于本发明在进行ID重排时总是依据当前顶点直接相连的顶点信息，属于局部信息，在实现局部最优的同时追求快速完成重排操作，故本发明的重排操作亦是高效的，可有效图提高图顶点重排效率。

说明书

技术领域

本发明涉及图计算领域，更具体地，涉及一种轻量级的高效图顶点重排方法。

背景技术

由于图能够很好地表示现实的各种关系，并且可以通过各种图算法来发挖掘图结构中潜在的事实，故图计算有很多应用。然而，大规模图谱的计算需要操作的数据量非常大，为了更高效地完成图计算，学者试图从多个方面进行优化，包括图计算环境的完善、算法层面的优化以及图数据的预处理等方面。其中图数据的预处理在图算法执行之前，不涉及具体图算法，不需要对原有算法进行修改，故某一确定图经过一次预处理后，可以在新图上进行不同图算法的单次或者多次计算。

以上的图计算预处理方法具体指对图顶点ID重新进行分配方法。用图结构表示现实关系时，需要为每个图顶点分配一个唯一的ID，便于图的存储与图计算。图计算主要包括邻居信息获取与本地计算两个阶段，顶点需要获取其邻居的信息，具体地是通过边表获取其邻居的ID，进而访问该ID所对应的数据。具体应用上，常常使用数组来按序存储所有顶点的数据，顶点的ID对应数组的下标，可通过<数组+ID>直接访问该顶点的数据。对数组元素的访问分为顺序访问方式和不规则访问方式，两者在数据的访问效率上差异较大。顺序访问方式可以很好地利用空间局部性原理，以提高cache的命中率，从而加快计算速度，故应该尽最大可能实现对数组的访问是按序。此外，数组中高频访问的元素应该常驻cache，以获得更多数据访问的时间局部性效益，加快计算速度。

在图顶点ID重排方面已有较广较深入的研究，根据不同方法完成重排所需要消耗的时间长短可分为耗时型与轻量级ID重排方法。经某ID重排方法得到图顶点新ID，如果在该新图上完成相同图计算所需的时间相对原图更少，则称该方法的重排结果是高效的，否则是低效的；如果该方法完成重排所需要的时间远大于图算法的计算时间，则称该方法的重排操作是低效的，称为耗时型ID重排方法，否则是高效的，称为轻量级ID重排方法。

耗时型ID重排方法以Gorder(H.Wei,J.X.Yu,C.Lu,and X.Lin.Speedup graphprocessing by graph ordering.In ACM SIGMOD,2016.)为代表。Gorder通过分析给出，结构上相邻的顶点应该拥有相近的ID，即拥有许多共同邻居的顶点，它们ID应该是相近的。形式描述如等式①，第一部分表示顶点u与顶点v的共同邻居个数，取值为共同邻居总个数，第二部分表示顶点u与v是否为邻居顶点，取值为1或者0。Gorder为顶点分配新ID时追求F(Φ)的最大化，可得较高效的重排结果，其中F(Φ)由等式②计算所得。但是Gorder亦说明，最小化F(Φ)是一个NP难问题，在大规模的图数据上直接使用该法进行重排，所需要的重排时间很长，重排操作是低效的，不适用于实际应用，故Gorder提出一种近似计算方法来进行重排，其重排思想与最大化F(Φ)是一致的，故其重排效果也是高效的，但是其重排操作仍然是低效的。

S(u,v)＝S

轻量级ID重排方法多是仅考虑顶点的度(与该顶点直接相连的顶点个数，下同)对重排效果的影响，其重排操作是高效的，但是其重排效果是低效的，如DBG(P.Faldu,J.Diamond,and B.Grot.A closer look at lightweight graph reordering.In IEEEIISWC,2019.)。DBG为顶点分配新ID时考虑顶点的度，通过聚类方法为顶点分配新ID，使得高频访问的顶点拥有相近的ID，理论上可以获得较高的局部性效益。但是由于此类方法仅考虑顶点的度，不结合更多的图结构特性，所以该类方法并不能保证其重排效果。因为实际应用的图规模很大，高频访问的顶点相对较多，而计算机的cache容量有限，不能同时容纳所有高频访问的顶点信息。如果高频访问的顶点在图结构上距离较远，而此时不正确地为这类高频访问的顶点分配相邻ID，cache容量的限制会导致很多即将被访问的高频顶点被置换出cache，降低cache的命中率，影响计算效率。Norder(E.Lee,J.Kim,K.Lim,S.H.Noh,and J.Seo.Pre-select static caching and neighborhood ordering for BFS-likealgorithms on disk-based graph engines.In USENIX ATC,2019.)在考虑顶点度的基础上，结合顶点的邻居信息，其重排操作效果相对是高效的，而且操作效果相对也是高效的；但由于Noder考虑的邻居信息是局部性的，其重排效果相对于Gorder是要低很多的。

发明内容

本发明为克服上述现有技术所述的图顶点重排效率不高的缺陷，提供一种轻量级的高效图顶点重排方法。

所述方法包括以下步骤：

S1：加载需进行ID重排的图，并进行预处理，确定种子点；

S2：选择种子点，并通过种子点生成超顶点；

S3：根据超顶点为需进行ID重排的图的顶点分配新ID，从而实现图顶点重排。

优选地，S1包括以下步骤：

S1.1：加载需要进行ID重排的图G＝(V，E)，V表示图的顶点集，E表示图的边集，|V|、|E|分别表示顶点数目与边数目；

然后存储整图信息，根据顶点的入度设置该顶点的标志位is_trivial，入度大于给定阈值λ则设置is_trivial＝true，否则设置is_trivial＝false；

S1.2：设定重排规则，并选定种子点。

优选地，存储整图信息采用压缩稀疏行(Compressed Sparse Row，CSR)的方式进行存储。

优选地，S1.2具体为：为了重排结果能够复现，设定从G的原ID最小的顶点开始进行ID重排，选定种子带你seed，其中，原ID最小的顶点为初始种子点。

其中，种子点的选定方法如下：

(1)当需进行ID重排的图的连通分量还有未分配新ID的顶点时，选择已经分配新ID的顶点的一个未分配ID的顶点当成种子点；

(2)当需进行ID重排的图的连通分量所有顶点均获得了新ID，从剩下的、未进行ID分配的连通分量中选择一个顶点当成种子点；

(3)以上(1)、(2)符合要求的顶点可能有多个，故选择原ID相对最小的顶点当成种子点。

(4)初始种子点的选取就是根据以上的(2)进行的。

优选地，S2具体为：

以初始种子点seed为中心，将其k跳内的低入度且还未分配新ID的顶点合并成超顶点H，得其超图结构；

其中，超图结构的顶点为合并后的超顶点。超顶点为逻辑概念，实为顶点集合。

优选地，超顶点的生成包括：

S2.1：初始化需进行ID重排的图的所有顶点ID分配标志位assigned＝false，置所有顶点新ID为Φ(*)＝-1，种子点seed＝-1，设辅助变量move_id＝1(表示当前可分配的新ID)，辅助变量v＝-1(表示当前可参与分配的顶点原ID)。

S2.2：通过超顶点生成函数Fusion(seed)得到超顶点H：

优选地，S2.2包括以下步骤：

S2.2.1：输入种子点seed，设置超顶点H＝{seed}；

S2.2.2：

S2.2.3：检查顶点u的分配标志位assigned，分配标志位assigned为true则跳过对该顶点的进一步操作(即不对该顶点进行操作)，分配标志位assigned为false则将该点添加至H中。

S2.2.4：逐个对其他相连出边邻居重复以上操作(S2.2.1-S2.2.3)，合并所有未分配邻居顶点后，合并跳数加一；

S2.2.5：对H中新添的顶点重复执行以上步骤(S2.2.1-S2.2.4)，直至跳数hop达到给定的合并跳数k，一次合并操作完成，输出超顶点H；即将种子点k跳内的低入度顶点合并入H后输出。

优选地，S3包括以下步骤：

S3.1：先为S2生成的超顶点H分配连续ID，再为超顶点H的邻居顶点分配新ID；更新以上已获得新ID的顶点的分配标志位assigned＝true。

S3.2：从超顶点H的邻居顶点中选择一个顶点当成种子点seed，当种子点seed的某个连通分量的顶点全部获得新ID后，选择剩余连通分量中原ID最小的顶点当成种子点seed，执行S2，直至所有顶点均获得唯一的新ID。

优选地，为超顶点H的邻居顶点分配新ID的分配规则为：首先为高入度邻居顶点分配连续ID，再为低入度邻居顶点分配连续ID。

与现有技术相比，本发明技术方案的有益效果是：本发明通过合并低入度顶点再分配ID的方法，使得合并顶点的共同邻居拥有相近的ID。本发明所述方法可有效图提高图顶点重排效率。

附图说明

图1为实施例1所述轻量级的高效图顶点重排方法。

图2为图顶点ID再分配示意图。

图3为图顶点ID再分配流程图。

图4为通过种子点生成超顶点的流程图。

图5为对需进行ID重排的图进行编号重排的过程图。

具体实施方式

附图仅用于示例性说明，不能理解为对本专利的限制；

为了更好说明本实施例，附图某些部件会有省略、放大或缩小，并不代表实际产品的尺寸；

对于本领域技术人员来说，附图中某些公知结构及其说明可能省略是可以理解的。

下面结合附图和实施例对本发明的技术方案做进一步的说明。

实施例1

本实施例提供一种轻量级的高效图顶点重排方法，如图1所示，所述方法包括以下步骤：

S1：加载需进行ID重排的图，并进行预处理，确定种子点。

S1.1：加载需要进行ID重排的图G＝(V，E)，V表示图的顶点集，E表示图的边集，|V|、|E|分别表示顶点数目与边数目。采用压缩稀疏行(Compressed Sparse Row,CSR)的方式存储整图信息。根据顶点的入度设置该顶点的标志位is_trivial，入度大于给定阈值λ则设置is_trivial＝true，否则设置is_trivial＝false。

S1.2：为了重排结果能够复现，本方法设定从原ID最小的顶点开始进行ID重排，选定种子点seed，其中，选定原ID最小的顶点为初始种子点。

S2：以种子点seed为中心，将其k跳内的低入度且还未分配新ID的顶点合并成超顶点H，得其超图结构，超图的顶点为合并后的超顶点。

以上步骤S2中，选择seed并通过seed生成超顶点H，进而为顶点分配新ID，图顶点ID再分配如图2所示，具体分配过程如下(如图3所示)：

S2.1：初始化需进行ID重排的图的所有顶点ID分配标志位assigned＝false，置所有顶点新ID为Φ(*)＝-1，种子点seed＝-1，设辅助变量move_id＝1(表示当前可分配的新ID)，辅助变量v＝-1(表示当前可参与分配的顶点原ID)。

S2.2：通过超顶点生成函数Fusion(seed)得到H(见图4)，具体包括以下步骤：

S2.2.1：设置超顶点H＝{seed}，

S2.2.2：

S2.2.3：检查顶点u的分配标志位assigned，true则跳过对该顶点的进一步操作，false则将该点添加至H中。

S2.2.4：逐个对其他相连出边邻居重复以上步骤。合并所有未分配邻居顶点后，合并跳数加一。

S2.2.5：对H中新添的顶点重复执行以上步骤，直至跳数hop达到给定的合并跳数k，一次合并操作完成，输出超顶点H。

S3：根据超顶点为需进行ID重排的图的顶点分配新ID，从而实现图顶点重排。

S3.1：先为以上生成的H分配连续ID，再为H的邻居顶点分配新ID，首先为高入度邻居顶点分配连续ID，再为低入度邻居顶点分配连续ID。更新以上已获得新ID的顶点的分配标志位assigned＝true。

换句话说，S3.1的具体操作为：为S2得到的H分配新ID，再为H直接相连的顶点分配新ID。具体地，首先为其中标志位is_trivial＝false的邻居顶点分配新ID，然后为标志位is_trivial＝true的顶点分配新ID。将已完成分配的顶点的标志位is_assigned设置为true。

S3.2：从以上H的邻居顶点中选择一个顶点当成seed，当种子点seed的某个连通分量的顶点全部获得新ID后，选择剩余连通分量中原ID最小的顶点当成种子点seed，执行步骤S2，直至所有顶点均获得唯一的新ID。

换句话说，S3.2的具体操作为：从H的邻居顶点中选择一个顶点当成seed，执行2.2。如果当前连通分量的所有顶点均已获得新ID，则从剩余连通分量中选择原ID最小的顶点当成seed，执行2.2，直至所有顶点均获得唯一的新ID。

作为一个具体的实施例，下面结合具体实例对本实施例进行说明：

以图5(a)为例，本实施例进行编号重排的过程如下(见图5)，设定入度阈值λ＝1，合并跳数k＝1，当前可分配的新ID号为0；由于例图规模较小，此例设定仅从出边邻居中选择seed：

步骤1：从未获得新ID的顶点中选择原ID最小的当成seed：符合条件的为1号顶点，选择seed＝1。

步骤2：生成超顶点：合并seed顶点k跳内、入度小于λ、还未分配新ID的顶点，1号顶点1跳内、入度小于λ、还未分配新ID的顶点为3，7号顶点，将(1，3，7)合并成超顶点，见图5(a)。

步骤3：为超顶点中未获得新ID的顶点分配新ID：当前可分配的新ID号为0，所以原ID为1，3，7的顶点对应新ID为1，2，3。当前可分配的新ID号为4。

步骤4：为超顶点未获得新ID的邻居分配新ID：超顶点的邻居中编号5，9，6为高入度顶点(按序给超顶点的每个顶点的高入度顶点分配新ID，即先为1号顶点的高入度邻居分配新ID，再到3号顶点的高入度邻居，最后是7号顶点的高入度邻居，下同)，10为低入度顶点(低入度邻居的ID分配顺序与以上高入度邻居的分配顺序一致，下同)。当前可分配的新ID号为4，所以原ID为5，9，6，10的顶点对应的新ID为4，5，6，7。当前可分配的新ID号为8，见图5(b)。

步骤5：从邻居中选择seed：由于此处设定仅从出边邻居中选择seed，5，9，6，10的出边邻居均获得新ID。

步骤6：从未获得新ID的顶点中选择原ID最小的当成seed：符合条件的为2号顶点，选择seed＝2。

步骤7：生成超顶点：合并seed顶点k跳内入度小于λ、还未分配新ID的顶点，2号顶点1跳内、入度小于λ、还未分配新ID的顶点为8号顶点，将(2，8)合并成超顶点，见图5(b)。

步骤8：为超顶点中未获得新ID的顶点分配新ID：当前可分配的新ID号为8，所以原ID为2，8的顶点对应新ID为8，9。当前可分配的新ID号为10。

步骤9：为超顶点未获得新ID的邻居分配新ID：超顶点的邻居中编号4为高入度顶点。当前可分配的新ID号为10，所以原ID为4的顶点对应的新ID为10。当前可分配的新ID号为11，见图5(c)。

步骤10：从邻居中选择seed：选择seed＝4；

步骤11：生成超顶点：合并seed顶点k跳内入度小于λ、还未分配新ID的顶点，4号顶点1跳内、入度小于λ、还未分配新ID的顶点为11号顶点，将(4，11)合并成超顶点，见图5(c)。

步骤12：为超顶点中未获得新ID的顶点分配新ID：当前可分配的新ID号为11，所以原ID为11的顶点对应的新ID为11。当前可分配的新ID号为12。(此处原ID为4的顶点已获得新ID，不能重复分配)。

步骤13：为超顶点未获得新ID的邻居分配新ID：超顶点邻居均已获得新ID，不能重复分配。

步骤14：重排完成，结果见图5(d)。

本实施例通过合并相邻低入度顶点再分配机制以及区分高低入度分配顺序的ID分配方法。其中合并相邻低入度顶点是为了以一种快速的方法确定顶点之间的共同邻居集合，相关研究表明，共同邻居越多的顶点之间应该拥有相邻的ID，顶点ID之间的临近性应该和顶点在图结构上的临近性是一致性的，有了此映射关系，在具体图计算进行数据访问时，能够获得更高的局部性效益，提高计算效率。区分高低入度顶点的ID分配顺序是为了使得高频访问的顶点之间的ID是相近的，此类顶点被频繁访问，ID相近可以提高此类顶点驻留cache的可能性。因为某一确定的顶点一般具有高入度邻居与低入度邻居，由于cache容量的限制，如果高入度顶点ID相去较远，对低入度邻居与高入度邻居的访问可能会导致某些即将被访问的高入度顶点被置换出cache，降低cache的命中率。

附图中描述位置关系的用语仅用于示例性说明，不能理解为对本专利的限制；

显然，本发明的上述实施例仅仅是为清楚地说明本发明所作的举例，而并非是对本发明的实施方式的限定。对于所属领域的普通技术人员来说，在上述说明的基础上还可以做出其它不同形式的变化或变动。这里无需也无法对所有的实施方式予以穷举。凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明权利要求的保护范围之内。