@TOC

简介

Hello！
非常感谢您阅读海轰的文章，倘若文中有错误的地方，欢迎您指出～
 
ଘ(੭ˊᵕˋ)੭
昵称：海轰
标签：程序猿｜C++选手｜学生
简介：因C语言结识编程，随后转入计算机专业，获得过国家奖学金，有幸在竞赛中拿过一些国奖、省奖…已保研
学习经验：扎实基础 + 多做笔记 + 多敲代码 + 多思考 + 学好英语！
 
唯有努力💪
 
【每日一读】每天浅读一篇论文，了解专业前沿知识，培养阅读习惯（阅读记录 仅供参考）

论文简介

原文链接：https://dl.acm.org/doi/10.1145/3448016.3452797

期刊：SIGMOD '21: Proceedings of the 2021 International Conference on Management of Data （CCF A类）

年度：2021年6月18日（发表日期）

ABSTRACT

本文提出了一种将大图缩减为小图的方案。它将过时的部分、恒星、派系和路径收缩成超级节点。超级节点为每个查询类 Q 携带一个概要 S Q 以抽象收缩部分的关键特征以回答 Q 的查询。收缩方案提供紧凑的图形表示并优先考虑最新数据。更好的是，它是通用且无损的。我们展示了同一个收缩图能够同时支持多个查询类，无论它们的查询是否基于标签、本地或非本地。此外，这些查询的现有算法可以很容易地通过在可能的情况下使用概要来计算准确的答案，并且仅在必要时才解压缩超级节点。作为概念证明，我们展示了如何将现有算法用于子图同构、三角形计数和最短距离到收缩图。我们还提供了一种增量收缩算法来响应更新。我们通过实验验证，收缩方案平均减少了 71.2% 的图，并将这些查询的评估分别提高了 1.53、1.42 和 2.14 倍。

1 INTRODUCTION

图在人工智能、知识库、搜索、推荐、商业交易、欺诈检测和社交网络分析中得到普遍使用。现实世界中的图通常很大，例如，电子商务公司的交易图很容易有数十亿个节点和数万亿条边。更糟糕的是，图计算通常是昂贵的，例如，通过子图同构的图模式匹配是棘手的。这些突出了开发加速图计算技术的必要性。

在这个主题上有很多工作，要么通过使图紧凑，例如图摘要 [37] 和压缩 [7]，要么通过构建索引来加速查询回答 [46]。先前的工作通常针对特定类别的查询，例如，查询保留压缩 [22] 和 2 跳标记 [13] 用于可达性查询。然而，在实践中，多个应用程序通常同时在同一个图上运行。在不同的应用程序之间切换压缩方案是不可行的。为每个使用中的查询类构建索引也太昂贵了。

另一个挑战来自过时的数据。作为一个真实的例子，考虑从一家电信公司的 IT 数据库转换而来的图表。这些数据库是多年来分阶段开发的，并且具有包含数百个属性的大型模式。大约 80% 的属性是从早期版本中复制而来的，并且多年来没有被触及。没有人能说出这些属性的用途，但没有人有胆量因为害怕信息丢失而放弃它们。结果，大部分图表已过时。再举一个例子，Twitter 中有大量的僵尸账户。据《纽约时报》报道，Lady Gaga 的粉丝中有 71% 是假的或不活跃的，而贾斯汀比伯的这一比例为 58%。过时的数据会导致大量的时间和空间成本，并且常常会混淆查询答案。

这些挑战引发了几个问题。是否有可能找到通用且无损的图形的紧凑表示？也就是说，我们希望将大图缩减为更小的形式。此外，使用相同的表示，我们希望同时计算不同类别查询的准确答案。此外，该表示能否在不丢失信息的情况下将最新数据与过时组件分开？我们能否将现有的查询评估算法调整为紧凑形式，而无需从头开始重新开发算法？此外，我们能否有效且增量地维护表示以响应对原始图的更新？

贡献和组织。本文提出了一种通过扩展图收缩来应对这些挑战的新方法。（1）收缩方案（第 2 节）。我们提出了一种将大图缩减为较小图的方案。它将过时的组件、星、派系、进入超级节点的路径收缩，并优先处理最新数据。对于每个查询类 Q，超级节点带有一个概要 S Q，它记录了回答 Q 的查询所需的关键特征。与图汇总和压缩相反，该方案是通用且无损的。收缩图对所有查询类 Q 保留相同的拓扑结构，并且相同的概要 S Q 对同一 Q 中的所有查询起作用。只有 S Q 对于不同的类 Q 可能会有所不同。

(2) 概念证明（第 3 节）。我们表明现有的查询评估算法可以很容易地适应收缩图。简而言之，我们扩展算法来处理超级节点。对于 Q 中的查询 Q，如果超级节点的概要 S Q 包含足够的信息来回答 Q，我们将使用它，并且仅在必要时才对超级节点进行解约。我们选择三个不同的查询类：子图同构（SubIso）、三角形计数（TriC）和最短距离（Dist），基于以下二分法：

• 基于标签的 (SubIso) 与非基于标签的 (TriC, Dist)；
• 本地（SubIso，TriC）与非本地（Dist）；和
• 拓扑约束（Dist ≺ TriC ≺ SubIso）。

我们展示了如何轻松地将这些查询的现有算法调整为收缩图，而不会增加它们的复杂性。更好的是，所有这些查询都可以在不解压缩拓扑结构的情况下得到回答，除了一些过时部分的超级节点。

(3) 增量收缩（第 4 节）。我们开发了一种增量算法来维护收缩图以响应对原始图的更新，这可能会改变拓扑结构和时间戳。我们证明了该算法是有界的 [44]，即它最多需要 O(|AFF|2) 时间，其中 |AFF|是受更新影响的区域的大小，而不是整个（可能很大）图的大小。

(4) 实证评估（第 5 节）。使用 9 个真实的图表，我们通过实验验证了以下内容。平均而言，(a) 收缩方案将图表减少了 71.2%。 (b) 收缩分别使 SubIso、TriC 和 Dist1.53、1.42 和 2.14 倍快。 © 我们三个收缩方案的总空间成本占 Turboiso [26]、HINDEX [43] 和 PLL [3] 指数的 9.8%。当 MC [38] 和 kNN [50] 也在同一个图上运行时，它是 6.1%。每个的概要占空间的 7.3%。因此，该方案可随着同一图上的应用程序数量而扩展。 (d) 收缩过时数据使常规查询和时态查询的效率分别平均提高了 1.23 倍和 1.88 倍。 (e) 我们的（增量）收缩方案可以很好地适应图和更新，例如，在具有 1.1 亿个节点和边的图上采用 103 秒。

2 A GRAPH CONTRACTION SCHEME

预赛。我们从基本符号开始。假设标签和时间戳分别有两个无限集 Θ 和 Γ。

图表。我们考虑无向图 G = (V , E, L,T )，其中 (a)V 是节点的有限集，(b) E ⊆ V × V 是边包，© 对于每个节点 v ∈ V , L(v) 是 Θ 中的一个标签； (d) T 是一个偏函数：对于每个节点 v ∈ V，如果定义了 T (v)，它是 Γ 中的一个时间戳，表示 v 或其相邻边最后一次更新的时间。

查询。图查询是从图 G 到另一个对象的可计算函数，例如布尔值、图和关系。例如，图模式匹配查询是一个图模式 Q，用于查找 G 中与 Q 同构的子图集，用 Q(G) 表示。三角形计数是查找 G 中所有三角形的常量查询。

查询类 Q 是一组相同“类型”的查询，例如所有图形模式。我们也将 Q 称为应用程序。在实践中，多个应用程序同时在同一个图 G 上运行。

2.1 Contraction Scheme

图收缩方案是三元组 ⟨fC , S, fD ⟩，其中 (1) fC 是一个收缩函数，使得给定图 G，Gc = fC (G) 是通过将某些子图 H 收缩为超节点从 G 推导出的图vH ;我们将 H 称为收缩到 vH 的子图，和 Gc 作为 G 由 fC 的收缩图； (2) S 是一组概要函数，使得对于每个使用的查询类 Q，存在 S Q ∈ S，它用概要 S Q (vH ) 注释 Gc 的每个超节点 vH； (3) fD 是一个去收缩函数，它将 Gc 中的每个超节点 vH 恢复到它的收缩子图 H 。

示例 1：图 1(a) 中的图 G 是 Twitter 网络的一部分。节点表示用户 (u)、推文 (t)、关键字 (k) 或用户的特征，例如 id (i)、名称 (n)、关注者数量 (f) 和到其他帐户的链接(l)。一条边表示以下内容： (1) (u, u′)，一个用户跟随另一个用户； (2) (u, t)，用户发布推文； (3) (t, t′)，一条推文转推另一条推文； (4) (t, k)，一条推文标记一个关键词； (5) (k, k′)，两个关键词高度相关； (6) (u, k)，用户对某个关键词感兴趣；或 (7) 用户具有特征，例如 (i, l)。在 G 中，虚线矩形中的子图收缩为超节点，产生如图 1（b）所示的收缩图 Gc。 SubIso 的概要 SSubIso 如图 1(d) 所示，将在第 3.1 节中详细说明。

在我们正式定义 fC、S、fD 之前，请注意以下几点。

• (1) 收缩方案是通用的。 (a) 注意 fC 、 Gc 和 fDare 独立于应用程序，即，无论 Q 在收缩图上运行什么查询类，它们都保持不变。 (b) 虽然 Sis 依赖于应用程序，但它与查询无关，即所有查询 Q ∈ Q 使用由 S Q 注释的相同概要。
• (2) 由于概要 S 和去收缩函数 fD ，收缩方案是无损的。正如将在第 3 节中看到的，用于查询类 Q 的现有算法 A 可以很容易地适应收缩图并计算精确的查询答案。当在超节点 vH 处评估查询 Q ∈ Q 时，A 检查 vH 处的概要 S Q (vH )是否有足够的信息用于 Q；如果是，它使用 S Q (vH ) 而不进行解压缩，否则通过恢复其子图 viafD 来解压缩 vH。在任何一种情况下，Q 的答案都不会丢失或扭曲。

我们接下来给出 fC 、 S 和 fD 的细节。我们的目标是在空间成本和查询评估成本之间取得平衡。当一个图被过度收缩时，即当收缩到单个超级节点的子图太大或太小时，尽管收缩图 Gc 可能占用更少的空间，但去收缩成本会上升。此外，概要越详细，需要的去收缩的可能性就越小，但会产生更高的空间开销。

(1) 收缩功能。函数 fC 将 G 中的子图收缩为 Gc 中的超级节点。为了简化讨论，我们收缩以下基本结构作为概念证明。

(a) 过时组件：由时间戳早于阈值 t0 的节点组成的连通子图

(b) 拓扑组件：以 clique、star 和 path 为例。

我们用 range[kl , ku ] 中的节点数收缩子图以避免过度收缩（有关选择，请参见第 5 节）。

函数 fC 将图 G 中的每个节点 v 映射到收缩图 Gc 中的超节点，如果 v 落入 (a) 或 (b) 中的子图 H 之一，则该超节点为 vH，否则为节点 v 本身。

在示例 1 中，函数 fC 将每个虚线矩形中的节点映射到其对应的超节点，例如，fC (i1) = fC (n1) = fC (f1) =fC (l1) = vH 1, fC (k1) = 。 . . = fC (k5) = vH 2 和 fC (t2) = t2。

直观地说，过时的组件帮助我们优先处理最新数据，拓扑组件减少了在回答查询时不必要的检查。如第 5 节所示，团、星、路径和过时组件对收缩率的贡献率为 12.9%、19.4%、0.5% 和 67.2%，对查询加速的贡献率为 37.8%、21.4%、2.2% 和 38.4%分别回答过程。

(2) 收缩图。对于图 G，其由 fC 收缩的图为 Gc= fC (G) = (Vc , Ec , f ′C )，其中 (a) Vc 是从 G 映射的一组超节点，如上所述； (b) Ec ⊆ Vc × Vc 是一个超边包，如果存在节点 v1 和 v2 使得 fC (v1) = vH 1, fC (v2) = vH 2 并且(v1, v2) ∈ E; © f ′C 是 fC 的反函数，即 f′C (vH ) = {(v, L(v)) | fC (v) = vH}。在示例 1 中，f′C 将图 1(b) 的 Gc 中的每个超节点映射回图 1(a) 中相应矩形中的节点，例如，f′C (vH 1)= {(i1, id ), (n1, name), (f1, follower), (l1, link)}。

(3) 概要。对于使用中的每个查询类 Q，S 中都有一个概要函数 S Qis，以保留回答 Q 中的查询所必需的特征。例如，当 Q 是图形模式类时，在每个超节点 vH 处，S Q (vH ) 由以下类型组成vH 和 fD (vH) 最显着的特征，例如星的中心节点和路径的排序节点列表。我们将在第 3 节中给出关于 S Q 的更多细节。正如在那里还将看到的那样，f’C 和概要 S Q 一起通常足以回答 Q 中的查询，而无需解压缩。

请注意，并非每个 S Q 都必须驻留在内存中。我们仅在其对应的应用程序 Q 正在使用时才将 S Q 加载到内存中。解压缩。函数 fD 恢复收缩到超级节点的子图。更具体地说，对于超节点 vH ，fD (vH ) 恢复了 f 'C (vH ) 中节点之间的边，即由 f 'C (vH ) 诱导的子图。对于一条超边(vH 1, vH 2)，fD(vH 1, vH 2)恢复f′C(vH 1)和f′C(vH 2)之间的边，即节点集f′C的二分子图(vH 1)∪f ′C (vH 2) 和边集 f ′C (vH 1)×f ′C (vH 2)∩E。

也就是说，收缩的子图和边不会被丢弃。必要时可通过 fD 恢复。根据 fD ，可以保证收缩方案是无损的。

例如，函数 fD 从超节点恢复图 1(a) 中的子图，例如，fD (vH 4) 是具有中心节点 u5 并留下 u1、u2、u3 和 u4 的星。它还从超边恢复边，例如 fD (vH 2, vH 3) = {(t1, k1), (k1, k6), (k2, k6)}。

2.2 Contraction algorithm

我们接下来提出一种算法来收缩给定的图 G，表示为 GCon。它首先收缩所有过时的数据以优先处理最新数据。每个过时的组件都是一个连通子图，它只包含时间戳早于阈值 t0 的节点。它是通过在非过时节点处停止的有界广度优先搜索 (BFS) 提取的。剩余的节点被收缩成拓扑组件，例如路径、星、团，或者保留为单例。

不同类型的图具有不同的主导规则结构，例如，集团在社交网络中无处不在，而路径在道路网络中更为普遍。因此，我们确定拓扑组件的顺序以收缩不同类型的图 G，表示为 T (G)。也就是说，我们采用确定性顺序来确保重要的结构更早地收缩和保存。

更具体地说，(1) 对于社交网络和协作图，T (G) = [clique, path, star]; (2) 对于 Web 图，T (G) = [star, clique, path]; (3) 对于道路网络，T (G) = [star, path, clique]。

将这些放在一起，我们在图 2 中展示了 algorithmGCon 的主要驱动因素。给定一个图 G、一个时间戳阈值 t0 和范围 [kl , ku ]，它构造了收缩方案的函数 fC 和 fD。它首先将时间戳早于阈值 t0 的节点收缩为过时的组件（第 1 行）。然后它调用拓扑组件的有序集 T (G) 以根据 G 的类型进行收缩（第 2 行）。接下来，GCon 将拓扑组件按照 T (G) 的顺序收缩为超级节点，并相应地推导出函数 fC 和 fD（第 3-5 行）。更具体地说，它执行以下操作。

(1) 对于路径，它首先提取只有两个邻居的中间节点，并且邻居是断开的。对于仅包含中间节点的每条路径，它构造一个路径组件以及端点的两个邻居。

(2) 对于 cliques，它反复选择一个连接所有选定节点的未收缩节点，并提取一个 clique。

(3) 对于星星，它首先选择一个中心节点。然后它反复选择一个未收缩的节点作为叶子，该叶子（a）连接到中心并且（b）与所有选定的叶子断开连接；它使这些成为明星。

如前所述，无法收缩为任何组件的剩余节点由 fC 映射到它们自己。

例 2：假设图 1(a) 的图 G 的时间戳阈值 t0 大于节点 i1、n1、f1 和 l1 的时间戳，但小于其余节点的时间戳。算法 GCon 的工作原理如下。 (1) 它首先触发有界 BFS，并将 i1、n1、f1 和 l1 收缩到 Gc 中的一个过时组件 vH 1 中。(2) 由于 G 是一个社交网络，它按此顺序收缩 clique、path 和 star。它构建了一个带有节点 k1, 的集团 vH 2。 . . , k5。 (3) 它找到k7、k8、k9、u1、u7和u9作为路径的候选中间节点，并将k7、k8、k9收缩为具有端点k6和t1的路径vH 3 。由于下限 kl = 4，节点 u1、u7 和 u9 无法创建路径。 (4) 它选择 u5 和 u10 作为星星的中心节点，并生成两颗星星 vH 4 和 vH 5。 (5) 节点 t2 是单例的，并且是由 fC 映射到自身

复杂。 (1) 过时的组件可以通过边缘不相交的有界 BFS 在 O(|G |) 时间内收缩； (2) 路径可以在 O(|G |) 时间内构建； (3) 收缩每个clique需要O(|G |)时间，所有clique可以在O(|G |2)内处理； (4) 类似地，所有恒星都可以在 O(|G |2) 内收缩。因此 GCon 最多花费 O(|G |2) 时间。

特性。请注意以下有关收缩方案的内容。 (1) 它是无损的，能够计算出准确的查询答案。 (2) 通用性强，同时支持多种应用。这通常是必要的，因为在 GDB 基准测试中平均有 10 类查询同时在图上运行 [19]。 (3) 它通过将最新数据与过时数据分开来优先处理最新数据。 (4) 提高性能。 (a) 如第 5 节所述，|Gc | ≪ |G |。 (b) 通常不需要去收缩，例如，SubIso 不需要去收缩拓扑组件，而对于 TriC 和 Dist，即使是过时的超级节点也不需要去收缩（第 3 节）。

2.3 Parallel Contraction Algorithm

我们接下来并行化算法 GCon，以加快收缩过程。请注意，收缩是在离线时进行的，然后随着更新而增量维护（第 4 节）。

这个想法是利用数据分区的并行性。给定可用机器和图 G，我们将 G 划分为片段（F1，…，Fn）并将它们分配给 n 个机器。所有机器首先在其本地片段上并行运行 GCon，因为毕竟每个 Fi 本身都是一个图。然后，它们收缩“边界节点”，即具有跨片段边缘的节点。我们通过函数 fC 确保每个节点 v 最多收缩为一个超级节点 vH 。更具体地说，我们概述了由 PCon 表示的并行算法，如下所示。

(1) 使用并行边切分区器“均匀地”分区 G，例如 ParMETIS [31]，这样 G 的每个节点都在一个片段中。

(2) 每台机器在其本地片段上并行运行 GCon。

(3) 对于每个边界节点 v，如果 v 尚未收缩为超级节点，则构建其 ku -neighbor，即在 v 的 ku 跳内仅具有未收缩节点的子图。邻居被并行识别，由机器 M0 协调.协调器 M0 将重叠的邻居合并为一个，并将不相交的邻居分配给 n 台机器。

(4) 每台机器并行收缩其分配的子图。

当步骤（3）中的某些邻居太大时，将它们再次切边分割并按照步骤（1）和（2）进行处理。

可以验证 G 中的每个节点 v 最多收缩为一个超级节点 vH 。 PCon 收缩的图 Gc 可能与 GCon 略有不同，因为边界节点可能以不同的顺序收缩。可以通过按照 T (G) 的顺序对 clique、star 和 path 中的每一个重复步骤 (1)-(4) 来解决此问题。尽管如此，我们通过实验发现这些差异并不足以值得额外的成本。此外，PCon 的收缩图已经是紧凑的，即它们不能进一步收缩。

3 PROOF OF CONCEPT

接下来我们展示了现有的查询评估算法可以很容易地适应收缩图。作为概念证明，我们选择了三个查询类：（1）子图同构（带有局部性的标记查询）； (2) 三角形计数（带有局部性的非标记查询）； (3) 最短距离（非标记和非本地查询）。

非正式地，对于查询 Q ∈ Q，我们检查超级节点 vH 处的 synopsisSQ (vH ) 是否有足够的 Q 信息；如果是，它直接使用 SQ (vH )；否则它会去收缩与 vH 相邻的超边或通过去收缩函数 fD 恢复 vH 的子图。正如将很快看到的，SQ (vH ) 通常提供足够的信息来在 vH 处作为一个整体处理 Q 或安全地跳过 vH 。因此，通过解压缩超边来回答三个类中的查询就足够了，而不需要解压缩任何拓扑组件。

3.1 Graph Pattern Matching with Contraction

我们从契约graphs.Pattern中的图模式匹配开始。图模式是图 Q = (VQ , EQ , LQ )，其中 (1)VQ (resp. EQ ) 是一组模式节点（分别是边），并且 (2) LQ 是分配标签的函数LQ (u) 到每个 u ∈ VQ 。

我们还研究了时间模式 (Q, t)，其中 Q 是上述模式，t 是给定的时间戳（稍后见详细信息）。

为了简化讨论，我们考虑连接模式 Q。这就是说，我们的算法可以适应不连接模式。模式匹配。图 G 中模式 Q 的匹配是与 Q 同构的 G 的子图 G′ = (V′, E′, L′,T′)，即存在双射函数 h : VQ → V′ 使得 (1 ) 对于每个节点 u ∈ VQ ,LQ (u) = L(h(u)); (2) e = (u, u′) 是模式 Q 中的一条边 当且仅当 (h(u), h(u′)) 是图 G 中的一条边并且 LQ (u′) = L(h(u’))。我们用 Q(G) 表示 G 中 Q 的所有匹配的集合。

图 G 中时间模式 (Q, t) 的匹配是 Q(G) 中的匹配 G’，使得对于 G’ 中的每个节点 v，T’(v) > t，即（常规）的匹配模式 Q，其中所有节点的时间戳都晚于 t。我们用 Q(G, t) 表示 (Q, t) 在 G 中的所有匹配。

由 SubIso 表示的图模式匹配问题是在给定模式 Q 和图 G 的情况下计算匹配集 Q(G)。类似地，时间匹配问题是计算给定 (Q, t) 和图 G 的 Q(G, t)，用 SubIsot 表示。

请注意，（1）模式 Q 被标记，即节点由标签匹配。此外，（2）Q具有局部性，即对于Qin G的任何匹配G’以及G’中的任何节点v1和v2，当将G’视为无向图时，v1和v2在dQ跳内。这里 dQ 是 Q 的直径，即 Q 中任意两个节点之间的最大最短距离。

模式匹配的决策问题是NP完全的（参见[24]）；类似的时间匹配。 SubIso 有几种算法，特别是带有索引的 Turboiso [26] 和没有索引的 VF2 [16]。两者都可以适应收缩图。

定理 1：使用线性概要函数，Turboiso 和 VF2 都可以适用于计算 Gc 上的 SubIso 的精确答案，它仅解压缩过时组件的超节点和超节点之间的超边，而不是拓扑组件。

我们为 Turboiso 提供了建设性的证明，因为 (1) 它是子图同构最有效的算法之一，其次是其他 SubIso 算法，例如 [9, 45]，以及 (2) 它采用索引来减少冗余匹配；我们展示了 SubIso 的索引可以通过收缩图继承，即收缩和索引相辅相成。

下面我们首先介绍 SubIso 的概要（第 3.1.1 节），VF2 和 Turboiso 的概要相同。然后我们展示了如何使 Turboiso 适应收缩图（第 3.1.2 节）。

3.1.1 Contraction for SubIso

概要的想法是存储常规结构的类型和关键特征，以便我们可以检查模式匹配而无需解压缩拓扑组件。

…

6 RELATED WORK

收缩。作为传统的图编程技术[25]，节点收缩合并节点，子图收缩将连接的子图替换为超节点。它用于例如单源最短路径 [30]、连通性 [25] 和生成树 [23]。

相比之下，我们使用概要扩展收缩以构建图的紧凑表示作为通用优化方案，这与编程技术背道而驰。

压缩。图压缩已被研究用于社交网络分析 [15]、子图同构 [20、39]、图模拟 [22]、可达性和最短距离 [29]。它通过将等效节点合并为单个节点来计算特定于查询的等效关系。一些压缩方法是查询保留（即无损），例如 [22 , 29 , 39 ]，并且可以在不解压缩的情况下回答压缩图上的特定类型的查询。

我们的收缩方案在以下方面与压缩不同。 (a) 它允许多个应用程序共享同一个收缩图。相比之下，压缩图依赖于查询；没有人支持不同的应用程序在同一个压缩图上运行。 (b) 收缩保证是无损的，而一些压缩方案是有损的，例如 [20]。 © 现有算法可以很容易地适应收缩图。相比之下，压缩通常需要开发新的算法，例如，[39] 需要用于子图同构的分解和连接算法。

总结。图摘要旨在通过聚合节点或子图（参见 [37] 进行调查）来生成大图的抽象或摘要，分类如下。 (1) 节点聚合，例如，GraSS [33] 将节点集群合并为超级节点，这些超级节点标有集群内部和集群之间的边数；它是为邻接、度数和中心性查询而开发的。 SNAP [49] 通过基于属性相似性聚合节点来生成图结构的近似摘要。 (2) 边聚合，例如，[42]通过将边聚合成超边来生成摘要，边的数量与原始图不同。 (3) 简化：OntoVis [47] 不是聚合节点和边，而是丢弃低度节点、重复路径和不重要的节点标签。大多数摘要方法都是有损的，例如 GraSS 和 SNAPretain 部分属性，而 OntoVis 会丢弃节点、边和标签。

在 [17, 27, 48] 中研究了摘要的增量维护。它取决于更新间隔 [48]；短期摘要会占用大量空间，而长期摘要可能会错过更新。为了解决这些问题，[27] 将更新聚合到“频繁”节点和边的图中，并根据整个图上的所有历史更新计算近似摘要。

总结和收缩方案都旨在提供通用的图表示来加速图分析。然而，（1）收缩方案是无损的，并且允许为各种查询类别计算准确的答案。相比之下，摘要通常是有损的，并且最多仅支持某些聚合或近似查询。 (2) 现有的查询回答算法可以很容易地适应收缩图，而新的算法通常必须在图摘要的基础上开发。 (3) 收缩图可以通过有界性和局部性进行增量维护，而摘要维护需要历史更新，并且经常对整个图进行操作[27]。

索引。已经研究了各种指标，例如子图同构 [8, 9, 16, 26, 41]，可达性 [5, 12, 29, 52] 和最短距离 [13, 36]。索引是查询特定的并占用额外空间。

我们的收缩方案与索引不同，它支持同一收缩图上的多个应用程序，而必须为每个查询类构建单独的索引。此外，维护收缩图比索引更有效。这就是说，收缩方案可以用指数来补充，以进一步加速，如 SubIso 所示（第 3.1 节）。

7 CONCLUSION

我们提出了一种收缩方案来使大图变小，作为多个应用程序同时在同一个图上运行的通用优化方案。我们已经证明该方案是通用且无损的。此外，它通过将最新数据与过时数据分开来优先处理最新数据。此外，现有的查询评估算法可以很容易地适应计算准确的答案，通常不需要解压缩拓扑组件。我们的实验结果验证了我们的方案是有效的。

未来工作的一个主题是探索除了路径、星形和集团之外的各种类型的图可以收缩哪些拓扑结构。另一个主题是递归应用收缩方案，并构建收缩层次结构。

结语

文章仅作为个人学习笔记记录，记录从0到1的一个过程

希望对您有一点点帮助，如有错误欢迎小伙伴指正