Graph Summarization Methods and Applications: A Survey

ABSTRACT

该综述是对当前最先进的图摘要算法的一个结构化、全面化的概述。它首先阐述了图摘要背后的动机和挑战；然后，根据输入的图的类型对摘要方法进行分类，并根据核心方法对每个类别进行组织；最后，讨论了摘要在现实世界的应用，并通过一些开放问题来总结。

1 INTRODUCTION

由于产生的数据日益增多和快速，数据摘要越来越被需要，因此针对大量数据类型的图摘要方法被提出，而该综述主要是关注相互关联的数据的摘取（即图或者是网络）。接着给出图的定义与示例，同时又阐述了图摘要的好处，如下所示。

• 数据量和存储的减少
• 图算法和查询的加速
• 支持交互分析
• 噪音消除

最后介绍图摘要的应用，并为下文讲述如何获得图摘要做铺垫。

1.1 Challenges

• 数据量巨大
• 数据非常复杂
• “感兴趣”的定义。通常来说，方法只不过是在时间、空间、摘要中保存的信息、摘要中得到的解映射到原始点和边的复杂性的折中。作者根据自己感兴趣的点加以调整，带有主观性。
• 评价。对于一个好的摘要，评估的标准是越来越多样、复杂的。
• 随时间而变化。处理动态的流数据。

1.2 Types of Graph Summaries

• 输入：静态或者动态
• 输入：同构或者异构
• 核心技术：
  • 基于分组和聚合
  • 基于位压缩
  • 基于简化和稀疏化
  • 基于影响
• 输出：摘要的类型
• 输出：不重叠或者重叠的节点
• 主要的目标

1.3 Differences from Prior Surveys

• 综述中包括静态图、带有标签或者额外信息的静态图、动态图
• 将对科研人员有用的信息突出，如表
  
• 我们给出图摘要方法和相关领域的联系
• 介绍图摘要的应用，提出未来研究的问题和机会

2 STATIC GRAPH SUMMARIZATION: PLAIN NETWORKS

2.1 Grouping-Based Methods

2.1.1 Node-Grouping Methods

• 基于点聚类的方法

• 基于点聚合的方法

  • GraSS
  • Weighted Compr
  • COARSENET
  • lp-reconstr.Error
  • Motifs
  • CoSum

2.1.2 Edge-Grouping Methods

• Dednesification
• VNM

2.2 Bit Compression-Based Methods

• Two-part MDL representation
  
  （ps:超点是多个点的汇聚，超边是连接超点的边，且权重可能呈现非线性变化）

• VoG

• 

它也使用MDL来总结，但是前者仅限于根据不重叠的团和二部核来总结图，而VoG支持更多样化的结构或词汇集。此外，还可以扩展词汇表，以满足特定应用程序或领域的需求。

2.3 Simplification-Based Methods

• OntoVis
  OntoVis支持语义抽象、结构抽象和重要性过滤（主要通过节点过滤）
• egocentric abstraction
  
  这是一种四步无监督算法，用于异构社交网络的自我中心信息抽象，使用边而不是节点来过滤

2.4 Influence-Based Methods

• community-level Social Influence(CSI)
  它主要通过信息传播和社会影响分析总结社交网络
• SPINE
  作为CSI的替代方案，将社交网络稀疏化，只保留“解释”信息传播的边——那些将观察到的数据的可能性最大化的边

2.5 Other Types of Graph Summaries

• visualization-based systems
  尽管一些可视化工具在中小型图上作用得很好，但它们无法呈现具有数千或数百万节点的大规模网络，否则就会受到高延迟的影响。这些工具可以从图汇总方法中受益，因为这些方法可以产生更小的网络表示或模式，可以更容易地显示。

• Domain-specific summaries

• latent representations
  有多种方法可以获得潜在空间中网络的低维表示

3 STATIC GRAPH SUMMARIZATION: LABELED NETWORKS

目前，大多数现有的工作只关注节点属性，尽管其他类型的辅助信息在摘要中肯定是有作用的。例如，多模式数据(包括图表、文本、图像和流数据)的联合汇总有各种各样的应用。然而，由于多模态分析的挑战，这些方法在文献中探索不足。

3.1 Grouping-Based Methods

• S-Node representation
  一种新的两级无损图压缩方案，对较低级别有向图使用一种称为参考编码的压缩技术，实现了较高的空间效率，并自然地隔离了与特定查询相关的Web图部分
• SNAP and k-SNAP
  两种流行的数据库风格方法
• CANAL
  为了给用户呈现最有用的摘要，它有三个标准，多样性、覆盖率、简洁度。
• probabilistic
• Zero-Knowledge Privacy
• a “blueprint” for lossless queries on compressed attributed graphs
  压缩属性图的无损查询
• d-summaries
  有损图汇总框架，它是d个摘要的集合，直观上是超图，它们将彼此d跳内的相似实体(即具有相同属性或标签的实体)分组

3.2 Bit Compression-Based Methods

基于位压缩的方法

• SUBDUE
  采用两部分MDL表示。除网络结构之外，MDL编码还考虑了节点和边标签。贪心束搜索用于用元节点迭代替换标记图中最频繁的子图，使MDL开销最小化。自从SUBDUE引入以来，人们提出许多方法来减轻图形上频繁的模式挖掘的复杂性问题，或扩展其在不同设置中的应用。
• AGSUMMARY
  它不直接使用频繁子图挖掘将输入网络的两部分MDL表示最小化，该模型的成本主要包括三部分：节点和属性组的数量、每个组的节点数量、组之间的连接。
• LSH-Based graph summarization
  迭代计算节点邻域上的minhash函数，将这些minhash函数组合成组，在组上计算hash码，然后聚合具有相同hash码的节点
• VEGAS
  总结了基于矩阵分解的影响传播算法在引文网络中的应用。

4 DYNAMIC GRAPH SUMMARIZATION: PLAIN NETWORKS

分析庞大而复杂的数据本身就具有挑战性，因此添加时间维度使分析更加具有挑战性和耗时。尽管如此，大多数网络确实会随着时间的推移而改变。

4.1 Grouping-Based Methods

• NETCONDENSE
  将动态网络扁平化后，NETCONDENSE反复合并相邻节点对和相邻时间对，评估扁平化网络的最大特征值的变化。这个变化按递增顺序排序，并合并最佳节点/时间对，直到达到用户指定的网络大小。
• TCM
  TCM 通过创建和查询d个图sketch并返回最小值来近似各种图查询。当使用的图sketch越多，冲突越小，准确度越高。TCM支持图流上的复杂分析，比如条件节点查询、聚合边权值、聚合节点流、可达路径查询、聚合子图查询和三角形计数。

4.2 Bit Compression-Based Methods

• TIMECRUNCH
  它简洁地描述了一个包含一组重要时间结构的大型动态图。对VoG进行了扩展，作者将时间图汇总形式化为一个信息理论优化问题，其目标是识别局部静态结构的时间行为，从而共同最小化动态图的全局描述长度。（下图为TimeCrunch识别的模式示例）
  

4.3 Influence-Based Methods

• OSNet
  OSNet的输入是时序交互流，表示为标记节点之间的无向边。它的目标是在一个有向图中捕捉级联(例如，新闻的传播)，以揭示动态流。输出摘要由来自原始输入图的带有“感兴趣”节点的子图组成，其中感兴趣度被定义为节点的出度(在扩散过程中感染的节点数量)和最大“传播半径”(从扩散过程的根到节点的路径长度)的线性组合。
• Social Activity

5 GRAPH SUMMARIZATION IN REAL-WORLD APPLICATIONS

5.1 Summarization for Query Handling and Efficiency

根据查询类型，对于各种方法达到的效果以及应用进行了简短的介绍。

5.2 Summarization for Visualization and Pattern Discovery

• OntoVis
  Shen等人将OntoVis应用于一个大型异构电影网络
• VoG
  Shah等人用它可视化了特定类型的结构(例如，派系，二部核bipartite cores)
  摘要还通过维护“有趣的”或“突出的”模式来支持模式发现
• Motif simplified
  Motif simplified可视化了多达8000个节点的简化网络与符号
• SUBDUE
  SUBDUE 是最著名的频繁模式挖掘方法之一，应用于各种领域，如化合物分析、场景分析和CAD电路设计分析

5.3 Summarization for Influence Extraction

• 捕获关键犯罪证据
• COARSENET 应用于56000个节点和560,000个边的级联网络Flixster，证明了大量电影在少数群体中传播，具有多模态分布，这表明电影具有多个传播尺度
• 证明影响关系一般没有表现出任何明确的结构

6 CONCLUSION

6.1 Open Research Problems

• 处理不同输入数据类型
• 汇总带有辅助信息的时间图
• multiview graph 和 multi-layer graph
• 通用查询的无损压缩
• 异构集群
• 目前的评估方法具有高度的应用特异性
• 使用自动从图编码的上下文中学习的深度学习节点，用于图摘要

有问题，欢迎随时留言或指正，thanks。