论文阅读报告: 在时间双向图上查询基于时间的的密集子图 | ICDE 2024

摘要

本文提出了一个新的模型（α, β, T）-core，用于在时间双向图上寻找凝聚子图。时间双向图中，不同实体之间的关系随着时间的推移而变化。为了提高查询效率，本文提出了顶点分区和时间分区的历史索引（VH-Index和TH-Index），并进一步提出了时间交集索引（TH*-Index）。实验结果表明，本文提出的模型和算法在多个真实数据集上表现出色。

什么是时间双向图

时间双向图（Temporal Bipartite Graph）是指在图中存在两类不同的顶点集合，并且这些顶点之间的关系（边）随着时间的推移而变化。每条边都有一个时间戳，表示该边在特定时间发生。时间双向图可以用于建模许多现实世界的应用场景，如用户-商品购买关系、作者-论文发表关系等。

时间双向图的构成

1. 顶点集合：

   • 上层顶点集（U）：表示一种类型的实体。例如，在用户-商品购买网络中，上层顶点可以表示用户。
   • 下层顶点集（L）：表示另一种类型的实体。例如，在用户-商品购买网络中，下层顶点可以表示商品。

2. 边集合（E）：

   • 边连接上层顶点和下层顶点，表示两种实体之间的关系。例如，用户购买商品。在时间双向图中，边带有时间戳，表示这种关系发生的时间。

举例说明

我们以一个简化的用户-商品购买网络为例，其中：

• 顶点集U表示用户
• 顶点集L表示商品
• 边表示用户在某一时间购买某一商品
• 每条边都有一个时间戳，表示购买时间

假设有以下用户和商品：

• 用户U: {Alice, Bob, Carol}
• 商品L: {Book, Pen, Notebook}

时间双向图的边集可以如下表示：

• (Alice, Book, 2024-01-01): 表示Alice在2024年1月1日购买了Book

• (Bob, Pen, 2024-01-03): 表示Bob在2024年1月3日购买了Pen

• (Alice, Notebook, 2024-01-05): 表示Alice在2024年1月5日购买了Notebook

• (Carol, Book, 2024-01-06): 表示Carol在2024年1月6日购买了Book

• (Bob, Notebook, 2024-01-07): 表示Bob在2024年1月7日购买了Notebook

  

研究背景

在许多现实世界的应用中，例如作者-论文网络、用户-物品网络等，不同实体之间的关系可以自然地表示为双向图。双向图由两类顶点和连接它们的边组成，这些边只在不同类别的顶点之间存在。在时间双向图中，边不仅连接不同类别的顶点，还带有时间戳，表示这种关系在某一特定时间发生或存在。随着时间的推移，这些关系会发生变化，形成时间双向图。传统的凝聚子图(密集子图)模型没有考虑时间维度，因此无法捕捉关系的动态变化。为了弥补这一不足，本文提出了时间双向图上的（α, β, T）-core模型。

研究问题

本文研究的问题是在时间双向图上找到满足给定度约束的最大子图。具体来说，给定时间窗口T=[ts, te]，以及度约束α和β，目标是找到一个子图，使得在该时间窗口内，上层和下层顶点的度分别至少为α和β。

主要贡献

1. 提出新的凝聚子图模型（α, β, T）-core：该模型结合了时间维度，能够捕捉关系的动态变化。
2. 设计了高效的索引结构：包括顶点分区历史索引（VH-Index）、时间分区历史索引（TH-Index）和时间交集索引（TH*-Index），以提高查询效率。
3. 开发了高效的构建和查询算法：提出了顺序和并行算法，用于高效构建时间交集索引。
4. 实验验证：在10个真实数据集上进行了大量实验，验证了模型和算法的有效性和效率。

预备知识

本文使用了一些基本的数学符号和定义：

• 时间双向图G(V, E)：V表示顶点集，E表示带有时间戳的边集。
• U(G)和L(G)：分别表示上层和下层顶点集。
• 快照G[ts, te]：表示在时间窗口[ts, te]内的子图。
• 度和邻居：顶点u在图G中的度表示为deg(u, G)，邻居集表示为N(u)。

索引的基本思想

1. 顶点分区历史索引（VH-Index）：

   • 基本思想：存储每个顶点在不同时间窗口内的状态，以便快速检索满足（α, β, T）-core条件的顶点。
   • 实现方式：对于每个顶点u，VH-Index存储所有可能的（α, β, T）-core组合的时间窗口。

2. 时间分区历史索引（TH-Index）：

   • 基本思想：通过按时间存储顶点，减少查询过程中需要访问的顶点数量。
   • 实现方式：TH-Index按时间分区存储顶点，将每个时间窗口内的（α, β, T）-core顶点集合存储在一起。

3. 时间交集索引（TH-Index）*：

   • 基本思想：结合VH-Index和TH-Index的优点，既减少存储空间，又提高查询效率。
   • 实现方式：通过存储代表性的时间点，减少冗余信息的存储，并在查询时进行交集计算。

索引的构建

1. 顶点分区历史索引（VH-Index）：

   • 步骤：
     1. 对于每个顶点u和每个可能的α、β组合，计算u在不同时间窗口内的状态。
     2. 存储每个顶点在不同时间窗口内的状态，以便快速查询。
   • 构建算法：
     • 通过对图进行多次遍历，依次计算每个顶点在各个时间窗口内的（α, β, T）-core状态，并将这些状态存储在VH-Index中。

2. 时间分区历史索引（TH-Index）：

   • 步骤：

     1. 按时间窗口对图进行分割，计算每个时间窗口内的（α, β, T）-core顶点集合。
     2. 存储这些顶点集合，以便快速查询。

   • 构建算法：

     • 对于每个时间窗口，计算（α, β, T）-core，并将结果存储在相应的时间分区中。

       

3. 时间交集索引（TH-Index）*：

   • 步骤：
     1. 选取代表性的时间点，计算这些时间点内的（α, β, T）-core。
     2. 存储这些代表性时间点的结果，减少冗余信息。
     3. 在查询时，通过这些代表性时间点进行交集计算，快速得到查询结果。
   • 构建算法：
     • 通过逐步增加时间窗口的大小，计算并存储代表性时间点的（α, β, T）-core，并将结果存储在TH*-Index中。

查询

1. 基于顶点分区历史索引（VH-Index）的查询：

   • 步骤：

     1. 根据查询参数α、β和时间窗口T=[ts, te]，在VH-Index中查找每个顶点u的状态。
     2. 通过二分搜索找到满足条件的时间窗口，收集符合条件的顶点。

   • 算法

     def query_vh_index(VH_Index, alpha, beta, ts, te):
         result = set()
         for vertex in VH_Index:
             time_windows = VH_Index[vertex][alpha][beta]
             for window in time_windows:
                 if window.start >= ts and window.end <= te:
                     result.add(vertex)
         return result
     1
     2
     3
     4
     5
     6
     7
     8

2. 基于时间分区历史索引（TH-Index）的查询：

• 步骤：
  1. 根据查询参数α、β和时间窗口T=[ts, te]，在TH-Index中查找相应时间窗口内的顶点集合。
  2. 通过二分搜索找到符合条件的顶点集合，返回结果。
• 算法：

def query_th_index(TH_Index, alpha, beta, ts, te):
    result = set()
    for t in range(ts, te + 1):
        if TH_Index[alpha][beta][t]:
            result.update(TH_Index[alpha][beta][t])
    return result
1
2
3
4
5
6

3. 基于时间交集索引（TH*-Index）的查询：

• 步骤：

  1. 根据查询参数α、β和时间窗口T=[ts, te]，分别在TH*-Index的前向索引和后向索引中查找符合条件的顶点集合。
  2. 计算前向索引和后向索引的交集，得到最终结果。

• 算法：

  def query_th_star_index(TH_Star_Index, alpha, beta, ts, te):
      forward_result = set()
      backward_result = set()
      
      # 查询前向索引
      for t in range(ts, TH_Star_Index.max_time):
          if TH_Star_Index.forward[alpha][beta][t]:
              forward_result.update(TH_Star_Index.forward[alpha][beta][t])
      
      # 查询后向索引
      for t in range(te, -1, -1):
          if TH_Star_Index.backward[alpha][beta][t]:
              backward_result.update(TH_Star_Index.backward[alpha][beta][t])
      
      # 计算交集
      return forward_result.intersection(backward_result)
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16

实验结果

1. 实验设置：实验在10个真实数据集上进行，评估模型和算法的性能。

2. 结果分析：结果表明，提出的模型和算法在不同数据集上的表现优异，查询效率和索引构建时间均有显著提升。

   

   图7展示了不同数据集上构建TH*-Index的内存使用情况和时间成本。黑色柱状图表示原始图的大小，白色柱状图表示TH*-Index的大小，折线图（带三角形标记）表示构建TH*-Index所需的时间。可以观察到，大多数情况下，TH*-Index的大小显著大于原始图的大小，这表明索引构建会增加内存开销。同时，构建TH*-Index的时间随数据集大小的增加而显著增加，尤其是在较大的数据集（如RU）上，构建时间超过了10^5秒。尽管构建TH*-Index需要较大的内存和时间成本，但它显著提高了查询效率，特别是在需要频繁查询的大规模时间双向图上。因此，对于这些场景，构建TH*-Index是值得的，而在较小数据集或查询频率较低的场景下，则需要权衡索引构建的必要性。

   

结论

本文提出了第一个适用于时间双向图的凝聚子图模型（α, β, T）-core，并设计了高效的索引结构和算法。通过大量实验验证，本文提出的方法在实际应用中具有很高的效率和实用性。未来的研究方向可以包括进一步优化索引结构和算法，以处理更大规模的时间双向图。此外，可以探索该模型在更多实际应用中的潜力，例如社交网络中的社区检测、电子商务中的推荐系统、以及生物网络中的功能模块识别等。这些应用可以利用本文提出的模型和算法，来有效地分析和挖掘数据中的动态关系，从而提供更有价值的见解和服务。

论文地址:https://www.researchgate.net/publication/382506975_Querying_Historical_Cohesive_Subgraphs_Over_Temporal_Bipartite_Graphs