论文导读 | 滑动窗口模型下含重复边的图流上的三角形近似计数算法_fast, accurate and provable triangle counting in f

北京大学 苟向阳博士

 

编者按：

北京大学数据管理实验室苟向阳博士关于滑动窗口模型下的图流上三角形近似计数的论文 《Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges》 被 SIGMOD 2021 接收。

由于很多图模型应用场景对于动态性的天然需求，图流分析近年来得到了越来越多的关注。由于图流规模大，更新速度快的特点，对其进行精确存储和分析从时间和空间上都有巨大的代价。相比之下高效的近似查询算法是一种更好的选择。此外，由于很多应用对于时效性的需求，降低图流中旧数据项的重要性，并在适当时机删除它们往往也是必需的。这种老化机制一般被描述为滑动窗口模型。然而，在滑动窗口模型下，对含重复边的图流进行近似三角形计数依然是一个有待解决的问题。本文中，我们提出了名为SWTC （Sliding Window Triangle Counting） 的算法。该算法使用独创策略来维护一个基于滑动窗口的无偏的，限定大小的样本，从而实现对滑动窗口内三角形数目的估算。实验表明该算法相比已有工作组合而成的基准算法，具有更高的准确度。

 

论文地址：

https://github.com/StreamingTriangleCounting/TriangleCounting

（或点击文末“阅读原文”跳转）

 

背景介绍

 

 

 

三角形计数是图上的基本问题之一。大量的应用，如社区发现 [1]，异常探测 [2] 等都是以三角形计数为基础的。大规模图数据上的精确三角形计数需要消耗大量时间，因此往往采用近似算法作为替代，相关方法在最近的十几年内已经得到了广泛的研究。然而，随着互联网的不断发展，图数据的组织形式有了新的变化。在社交网络，通信网络等应用中产生的图数据往往被组织为图流的形式，即一系列持续不断到达的边。在这条边序列中，相同的边可能出现多次，即重复边 (duplicate edge)。此外，由于图流数据会持续不断地产生，对全部的图流数据进行存储和分析是十分困难的。而且大多数应用都对数据具有时效性的要求。因此，我们在处理图流时往往采用滑动窗口 (sliding window) 模型，即只分析最近的一段时间内到达的边组成的动态图。在滑动窗口模型下对含重复边的图流数据进行近似三角形计数仍是一个有待研究的领域。我们的论文对这一问题进行了研究，提出了滑动窗口三角形近似计数算法 SWTC (sliding window triangle counting)。

 

问题定义

 

 

图流 （streaming graph）：如上文所说，图流为一个持续不断到达的边组成的序列，序列的每一个元素为两个点之间的一条边。这条边可以有向也可以无向。在三角形计数问题中，三角形的定义一般是无向的，因此我们在此问题中将图流中的边也考虑为无向。每一个元素还具有一个时间戳，标识元素到达的时间。同一条边在图流中可以出现多次，即为重复边 (duplicate edge)。

 

 

图 1 图流及滑动窗口示例

滑动窗口 （sliding window）：假设当前时刻为 T， 则一个大小为 N 的滑动窗口即为从时刻 T-N 到时刻 T 之间到达的图流元素的集合，在集合之外的边被认为已过期，不再有效。我们在此问题中使用的上述定义为基于时间的滑动窗口，而还有一种定义为基于计数的滑动窗口，即最近到达的 N 个元素。相比之下，基于时间的滑动窗口更为常用，而且，基于计数的窗口可以简单地转化为基于时间的窗口，只需要给每一个元素赋予一个与其到达序号相同的时间戳。

图 1 展示了一个图流及滑动窗口的示例。

快照图 (snapshot graph)：快照图即为当前滑动窗口内的边组成的图。这个图随着滑动窗口的变化而在不断变化中。由于图流中存在重复边，我们给快照图中的每条边标记一个频率，即为该边在滑动窗口中出现的次数。

二项计数 (binary counting) 和带权计数 (weighted counting): 在含重复边的快照图中计数三角形有两种方法。二项计数只计数互异三角形的数目。带权计数则将每一个三角形的权重标记为三条边的频率之积，并计数快照图中所有三角形的权重和。我们也可以从另一个视角看待带权计数，我们将一条边的多次出现视为多条不同的平行边，则一个权重为 w 的带权三角形也可以视为 w 个由不同的平行边三元组组成的三角形。相比之下，二项计数则过滤掉重复的平行边，在剩余的不含重的边中计数三角形。

 

 

SWTC算法

 

 

SWTC 算法为基于采样的近似计数算法，即维护一个从快照图中抽取出的小规模样本图，在此样本图中计数三角形数目，以此来估算整个快照图中的三角形数目。根据二项计数还是带权计数的选择不同，采样和估算的方法也会有所区别，我们首先以二项计数为例说明算法，之后再推广到带权计数上。在用SWTC 对三角形数目进行二项计数时，算法可以大概分为两部分，样本图的维护，以及估算滑动窗口内的互异边数目，最终我们将根据两部分的结果估算快照图中的三角形数目。下面我们对两部分分别进行介绍：

样本图的维护

我们对滑动窗口内的边进行无偏采样，采样结果组成的图即为样本图。二项计数中，此采样过程要求过滤掉滑动窗口内的重复边，且剩余的每条互异边加入样本图的概率相同。我们希望样本图具有一个明确的空间消耗上限，使得我们可以在应用中为其提前分配足够的内存。我们不能选择简单的固定概率采样方法，因为图流的流量在不断变化，滑动窗口内的边数也在不断变化，若采样概率固定，则样本大小与滑动窗口内的边数成正比，是难以估算大小的。此外，在前人工作中已经证明了若要在滑动窗口内维护一个固定大小 k的样本，至少需要 O(log⁡(n)k) 的空间，其中 n 为当前滑动窗口内的边数，如上文所说，n 是难以估计的。当我们希望空间消耗有固定的上限，即为 O(k) 时，我们只能维护一个限定大小的样本，即样本大小不超过 k， 但可能小于 k。因此，我们最终目标是设计一种与限定大小的采样方法。我们沿用了前人工作 PartitionCT [3] 的框架。PartitionCT用于含重复边图流上的二项计数，拥有固定的空间消耗。但是其没有考虑滑动窗口模型。我们在它的基础上，加入了处理滑动窗口中边过期的方法，形成了新的采样方法。

我们使用一个哈希函数将图流中的边划分为 k 个子流。我们为每一条边 e 计算一个范围在 [0,k) 的哈希值 H(e), 并将此边划分到子流 H(e) 中。在每个子流中，我们使用另一个哈希函数为每一条边计算一个范围在 [0,1) 内的优先级 G(e)，然后采样其中优先级最高的边作为子流的样本，最终将k 个子流的样本边合起来作为样本图。这一框架与PartitionCT 类似，但是在滑动窗口模型下，寻找每个子流中优先级最高的边会变得十分困难。有些边可能在到达时，因为优先级小于现有样本边而不被采样，但当现有样本边过期后，它又成为了滑动窗口内优先级最大的边，即新的样本边。若我们只维护当前样本边，那么在样本边过期后我们就难以找到后继样本，因为应当被采样的边可能在之前已经到达而且没有被保存。然而，若将所有可能在未来被采样的边保存下来，又会消耗大量的存储空间，违反我们限定空间消耗的初衷。因此，我们需要仔细设计采样方法。

在SWTC 中，我们将图流划分为若干个固定长度的片段 (slice)， 每一个片段包含 N 个时间单元内，即和滑动窗口的时间长度相同。这些片段的分割隔点被称为路标 (landmark)，为固定的时间点，我们将路标记为， 并用表示从时刻到图流中到达的边，表示滑动窗口。图1中也展示了片段的示例，滑动窗口和片段均为6个时间单元。显然，滑动窗口最多与两个片段相交，我们将这两个片段记为与， 其中与为 T 之前最近的两个路标。当前时刻 T 正好在一个路标上时，滑动窗口只和最近的一个片段相交。我们在每个子流中，维护最近两个片段里优先级最大的边，记为与。这一过程较为简单，因为每个片段的起始和结束时刻都是确定的，对于片段， 我们只需要在时刻开始维护一个变量，并在每次有新的边被划分到子流  中时，比较其优先级与的优先级，若新边具有更高优先级，则替换，直到时刻。同理我们也可以只用一个变量来维护 内优先级最高的边。之后我们根据二者的时间戳和优先级，选择其中至多一个作为此子流中的样本。

图 2 SWTC 不同情况示例

具体来说，在子流中存在三种情况。第一种情况是 与均在滑动窗口内，我们将其中优先级更高的记录为中的样本。第二种情况则是 已经过期，然后滑动窗口仍与片段相交。此时我们比较与 的优先级，若的优先级更高（或相同），则我们可以选择其为该子流中的样本，因为中的所有边优先级都不超过，自然也不超过，而 自身又是内优先级最高的边，因此其为整个内优先级最高的边，自然也是滑动窗口内优先级最高的边。而如果的优先级小于，那么我们无法将其选为样本边，因为在与滑动窗口的相交区域内，可能存在边优先级高于 而小于。此种情况下我们无法在此子流选出样本边。随着时间推移，情况二会演变为情况三，即为滑动窗口只与相交，此时我们可以选择  为样本边。之后情况三会再演变为情况一，三种情况交替出现。

我们在每个子流中都有一定概率 p 选出样本边，最终得到的样本大小的期望为 pk。因为我们选出的边为子流中在滑动窗口内最高优先级的边，而优先级的产生和子流的划分都是随机的，因此滑动窗口内每条边被采样的概率相同。因为我们使用哈希函数进行子流划分和优先级计算，同一条边总是被分到同一子流，并得到相同的优先级，因此重复边不会影响采样的结果。所以我们最终得到的样本为二项计数意义下的无偏样本。观察图2中的三种情况可知，只有当与 中优先级最高的边在滑动窗口内时，我们才可以在该子流中选出样本。因此，每个子流中选出样本边的概率p 为， 其中 | ∙ | 表示集合内互异元素的数目。这一概率随着时间推移不断变化，当图流流量稳定 (即片段内互异边数目和时间长度成正比时)，这一概率在 0.5 到 1 的范围内波动，平均值为 0.75。在此算法中，我们在每一个子流中保存两条边，小消耗的空间大小为 O(k)。

使用上述采样算法的流程如下：在每次有新边 e 到达时，我们取 p=H(e)，将 e 映射到子流中，比较的优先级和 e 的优先级，若的优先级较高，则直接丢弃 e 并结束更新。否则，我们替换，并比较 e 和的优先级大小，若仍是 e 优先级较高，则将 e 加入样本图，并将该子流中的原样本边从样本图中删除。

 

此外，我们还需要维护一条由当前样本边按照时序排列而成的链表，每当最旧的边时间戳小于 T-N 时，则将其从样本图中删除。当时刻到达一个路标时，我们还需要令 k 个子流中的而，标识着一次片段的交替。此外，若子流中原先没有样本边，我们将现在的加入样本图。

 

在上述采样过程中，我们需要持续记录样本图中三角形的数目 tc，我们可以在每次有样本边 e 被添加或者删除时，从计数器 tc 上增加或减少该边在样本图中形成的三角形数目。而后者需要我们计算 e 的两个端点的邻居列表的交集。

滑动窗口内互异边数目的估算

除了维护样本图之外，我们还需要对滑动窗口内互异边数目进行估算，这一参数在估算快照图中三角形数目时至关重要。重复边的存在，以及边过期，特别是非样本边的过期（我们无法发觉非样本边的过期，因为我们没有保存它们），使得这一估算十分困难，我们无法直接用已有工作例如 Hyperloglog 算法 [4] 去估算，因为这些算法不支持滑动窗口模型。我们注意到，SWTC已经将图流划分为了若干固定的片段，而Hyperloglog 算法能够在这些片段上实施。因此，我们首先使用Hyperloglog算法估算与滑动窗口相交的两个片段内的互异边的数目，然后再以此为依据估算滑动窗口内的互异边的数目。

在每个子流中，我们已经保存了最近的两个片段和 中优先级最高的边，我们取二者中最高的优先级，记为。是 内的所有边优先级的最大值，而这些优先级是由 [0,1) 范围内的均匀分布哈希函数 G(∙) 产生的。我们可以将其转换为一组服从的几何分布的变量, 则为中的最大值，k 个子流中的便组成了一个  上的 Hyperloglog sketch，我们可以利用其估算的值，计算方法为，其中对于 k>128 (为了让采样估测足够准确，k一般需要取数十万，远大于128)。关于 Hyperloglog 算法的具体分析，可以参考原论文 [4]。这一估算过程不需要任何额外空间消耗。

 

得到后，我们还需要用其估算，注意上文分析中提到，一个子流得到有效样本边的概率，而 p 可以通过统计 k 个子流中有效样本的数量来估算， 之后我们用便可以估算出滑动窗口中边的数目。与样本图中的三角形数目 tc 一样，n 也可以被持续记录，我们可以在每次有子流中最大优先级发生变化时对 n 进行修改。

三角形数目的估算

我们用样本图中的三角形数目 tc，样本图中的边数 m 以及如上文所述方法估算出的滑动窗口内互异边数量 n，估算快照图中的三角形数目， 我们可以在图流流入的过程中用上述算法持续监视三角形数目的变化。这一计算方式的原因在于，每条边都有相同的概率被加入 m 个样本中，而三角形三条边均被加入样本的概率即为，这也是每个三角形被加入样本图的概率。我们用样本图中的三角形数目除以这一概率，得到的即为快照图中三角形数目的估计值。

进一步的改进与扩展

在上述算法中存在一些效率上的问题。在每一个路标时刻，会有大量的新样本边被加入样本图，对这些样本边产生的三角形计数会消耗大量的时间，导致短时间内算法的阻塞，无法处理新到达的边。为了解决这一问题，我们又提出了 vision counting 策略，即预测下一个路标时刻的三角形数目。对于图一中case 2 的情况，子流中不存在样本边，但是我们可以将 提前加入样本图，作为一条未来可能生效的潜在样本边。在三角形计数器 tc 中，我们不计数包含这些潜在样本边的三角形，但是我们另使用一个计数器 vc，在其中同时计数当前样本边和潜在样本边组成的三角形。在路标时刻，我们只需要令 tc=vc，并将那些潜在样本边设置为有效，不需要进行大量的三角形计算。这一策略相当于把路标时刻的高计算负载均摊到了其他时刻。

在扩展到带权计数时，我们只需要将用于进行子流划分和优先级计算的两个哈希函数 H(⋅) 和 G(⋅) 替换为随机函数。如此一来，同一条边出现多次时，可能被划分到不同的子流并得到不同的优先级，也就是说这些重复边被看作了独立的平行边。在样本图中，我们也需要进行带权计数。其他的流程和二项计数没有区别。

 

实验结果

我们的实验分为了二项计数和带权计数两部分。现有工作中缺乏在我们的问题设定下的三角形近似计数算法，因此，二项计数实验中，我们和PartitionCT 框架加滑动窗口采样计数BPS 算法 [5] 组合成的 baseline 算法作对比。在带权计数中，我们除了和 baseline 对比外，还和已有的两种带权计数算法 WRS [6] 和 ThinkD [7] 作了对比，这两种算法用于含边删除的图流上的三角形计数。与滑动窗口模型不同，这两种算法要求在每次有边删除时，都被明确告知删除边，这使得我们必须要将整个滑动窗口中的边及其时间戳保存下来才能应用这两种算法，这将消耗大量的内存，而且使得内存使用缺乏上限，我们会在实验中看出这样做的弊端。

在实验参数和测试指标上，我们的baseline 算法和SWTC 算法都只有一个参数 k，且二者具有相同的 k时拥有相同的内存消耗。我们定义采样率 (Sample Rate) 为 k 除以窗口长度，其中窗口长度以图流中数据项到达的平均时间间隔为单位。我们通过改变采样率来控制 k，这样避免了样本过小带来较大误差。注意在应用中窗口长度是不变的，而数据项到达的平均间隔根据历史数据估算即可。因此我们算法在运行时有着明确的空间使用上限，不会随着图流流量改变而改变。我们实验测试的主要指标为相同内存消耗下样本集合的大小和三角形估算的准确率，前者用有效样本集大小 (valid sample size) 来表示，后者用平均相对误差MAPE 来表示，即为，其中表示估算出的三角形数量，而 τ 则为滑动窗口中实际的三角形数量。

在数据集选择上，我们在下面实验中主要使用了三个数据集：

StackOverflow: 从StackOverflow论坛上获取的用户交互信息图，点代表用户而边代表用户交互（回答问题，留言等），包含63497050 条边（含重复）和2601977个点。

Yahoo network: 从yahoo 的开源数据集中获取的网络流数据集，点代表IP地址而边表示两个IP之间的通信，包含561754369 条边（含重复）和 33635059 个点。

Actor：描述演员合作关系的图，点代表演员而每条边表示两个演员之间的一次合作，包含33115812条边（含重复）和382219个点。

前两个数据集包含时间戳信息，而第三个数据集不包含时间戳信息，我们为其中的边随机生成了时间戳。我们将每个数据集中所有的边按照时间戳顺序提供给算法以模拟图流。每当滑动窗口向前滑动时（即算法处理过的边的最大时间戳增加），我们设置一个测试点，测量样本集大小和三角形估测的相对误差，最终取所有测试点的平均值作为实验结果。

 

二项计数

图3展示了baseline 算法和SWTC算法的效果随着滑动窗口大小的变化趋势。我们固定采样率为 4%。从图中我们可以看出，SWTC 算法相比 baseline 算法，在相同条件下有更大的样本大小，更小的相对误差。两种算法的样本集大小会随着窗口增大而增大，这是因为固定采样率的情况下，窗口增大导致子流数目也会增多。而在图 (c) 中我们可以看出，随着窗口增大，MAPE也会有一定程度的下降，这是因为在更大的边集合里采集更多的样本时，预测会更加稳定，因为随机性带来的误差会相对更小。

图4展示了baseline 算法和SWTC算法的效果随着采样率变化的趋势。我们固定窗口大小为35M。从图中我们可以看出，两种算法的样本集大小会随着采样率提高而增大，这也是因为更高的采样率带来了更大的 k，也就是子流数目。此外，两种算法的MAPE也会随着采样率的提升而下降，因为在窗口大小不变的情况下，更大的样本集带来了更高的准确率。此外，在采样率变化的过程中，SWTC 仍比 baseline 方法具有更高的准确度。 

图 3 算法性能随窗口大小变化趋势

图 4 算法性能随采样率变化趋势

带权计数

图 5 带权计数中各种算法的相对误差

在带权计数中，我们使用了 StackOverflow 数据集，设置窗口大小为 4.5M, 并改变算法使用的内存来进行实验，结果如图5 所示。如上文所说，WRS 和 ThinkD 算法需要按时序保存滑动窗口内的所有边才能工作。我们统计在整个图流流入的过程中滑动窗口内边数的变化，发现最大为 5.4M。因此 WRS 和 ThinkD 算法至少需要能保存 5.4M 边的空间才能工作，而用单链表按时序保存 5.4 M 边及其时间戳需要 172.8 M 空间，因此在图中，这两种算法从180M 内存消耗处才开始具有折线。我们可以看到这两种算法需要至少 240M 内存才能具有 4% 以下的 MAPE， 而baseline 算法和 SWTC 算法只需要 60M 内存就能具有相同的MAPE。此外，在整个折线的变化过程中，SWTC 在相同内存消耗下仍比 baseline 具有更低的MAPE。

更多的实验结果，如 vision counting 的效果，边重复率对算法准确率的影响等，可以参考我们的论文。

 

参考文献

[1]Berry J W, Hendrickson B, LaViolette R A, et al. Tolerating thecommunity detection resolution limit with edge weighting[J]. Physical Review E,2011, 83(5): 056119.

[2]Becchetti L, Boldi P, Castillo C, et al. Efficient algorithms forlarge-scale local triangle counting[J]. ACM Transactions on Knowledge Discoveryfrom Data (TKDD), 2010, 4(3): 1-28.

[3]Wang P, Qi Y, Sun Y, et al. Approximately counting triangles inlarge graph streams including edge duplicates with a fixed memory usage[J].Proceedings of the VLDB Endowment, 2017, 11(2): 162-175.

[4]Flajolet P, Fusy É, Gandouet O, et al. Hyperloglog: the analysis ofa near-optimal cardinality estimation algorithm[C]//Discrete Mathematics andTheoretical Computer Science. Discrete Mathematics and Theoretical ComputerScience, 2007: 137-156.

[5]Gemulla R, Lehner W. Sampling time-based sliding windows in boundedspace[C]// Proceedings of the 2008 ACM SIGMOD international conference onManagement of data. 2008: 379-392.

[6] Lee D, Shin K, Faloutsos C. Temporal locality-aware sampling foraccurate triangle counting in real graph streams[J]. The VLDB Journal, 2020,29(6): 1501-1525.

[7] Shin K, Oh S, Kim J, et al. Fast, accurate and provable trianglecounting in fully dynamic graph streams[J]. ACM Transactions on KnowledgeDiscovery from Data (TKDD), 2020, 14(2): 1-39.