论文阅读:Efficient Core Maintenance in Large Bipartite Graphs | SIGMOD 2024

还记得我们昨天讨论的《Querying Historical Cohesive Subgraphs over Temporal Bipartite Graphs》这篇论文吗?

https://blog.csdn.net/m0_62361730/article/details/141003301
这篇(还没看的快去看)

这篇论文主要研究如何在时间双向图上查询历史凝聚子图，而《Efficient Core Maintenance in Large Bipartite Graphs》则比较关注动态双向图中的双核维护(维护(𝛼, 𝛽)-核是为了在插入、删除时可以快速找到关键子结构)。两者的主要区别在于前者处理的是时间维度上的子图查询，而后者则是对动态更新的高效维护。然而，两者在处理动态数据方面有相似之处，均需要考虑图的频繁更新对算法效率的影响。

论文简介

《Efficient Core Maintenance in Large Bipartite Graphs》由Wensheng Luo、Qiaoyuan Yang、Yixiang Fang和Xu Zhou撰写。这篇论文主要探讨了如何在大型双向图中高效地维护(𝛼, 𝛽)-核 (bi-core)。(𝛼, 𝛽)-核作为双向图中的一种重要的凝聚子图模型，已在许多实际应用中得到了广泛应用，如产品推荐、欺诈者检测和社区搜索。然而，由于双向图通常是动态的，其顶点和边经常被插入和删除，从头计算(𝛼, 𝛽)-核的成本非常高。为了缓解这个问题，论文提出了一些高效的(𝛼, 𝛽)-核维护算法，通过引入双核数（bi-core numbers）的新概念，有效地减少计算冗余。

甚麽是(𝛼, 𝛽)-核?

(𝛼, 𝛽)-核是图中用于识别重要子结构的一种概念，特别适用于异质信息网络（Heterogeneous Information Networks，HINs）或双向图（Bipartite Graphs）。它是对经典的k-core概念的扩展，旨在捕捉图中的稠密子图或核心部分。

定义

在(𝛼, 𝛽)-核中，α和β分别是图中两种类型节点的度数阈值。具体来说，对于一个双向图G = (U, V, E)，其中U和V是两类节点集，E是连接U和V的边集，(𝛼, 𝛽)-核定义如下：

• 一个子图H = (U’, V’, E’)是图G的(𝛼, 𝛽)-核，当且仅当：
  • 对于每个节点u ∈ U’，其在子图H中的度数（即连接到V’中的节点数）至少为α。
  • 对于每个节点v ∈ V’，其在子图H中的度数（即连接到U’中的节点数）至少为β。

直观理解

(𝛼, 𝛽)-核确保了在子图中，类型U的每个节点至少有α个邻居，且类型V的每个节点至少有β个邻居。这种结构在分析图的密集区域或核心部分时非常有用，因为它过滤掉了那些连接较少、可能不太重要的节点，突出了稠密的子结构。

例子

假设有一个双向图表示学术网络，其中U是作者集合，V是论文集合，边表示作者和论文之间的写作关系。如果我们定义一个(𝛼, 𝛽)-核，比如(3, 2)-核：

• 这意味着在这个子图中，每个作者至少写了3篇论文（α = 3）。
• 每篇论文至少由2个作者共同撰写（β = 2）。

通过这种方式，我们可以识别出那些活跃的作者群体和他们共同撰写的论文，从而揭示学术网络中的关键合作关系。

为甚麽需要维护(𝛼, 𝛽)-核?

在动态图中，因为图的结构经常发生变化，所以维护(𝛼, 𝛽)-核非常重要，不然就得花很多时间重新计算。维护(𝛼, 𝛽)-核可以确保在节点或边插入、删除时，快速调整和更新图中的关键子结构，从而保持分析结果的实时性和准确性。

总结来说，(𝛼, 𝛽)-核是图中重要的稠密子结构识别方法，适用于多种应用场景，通过维护这种核心结构，可以在动态变化的图数据中高效、准确地进行分析和挖掘。

研究背景与动机

双向图广泛用于描述不同类型实体之间的关系，例如电子商务中的用户和商品、金融网络中的欺诈者和账户、合作网络中的作者和论文、生物网络中的基因和蛋白质、社交网络中的用户和页面等。由于双向图在这些领域的广泛应用，挖掘关键子图结构以分析双向图已吸引了大量关注。其中，(𝛼, 𝛽)-核作为双向图上的一种广义的k核模型，已在多种应用中得到了广泛应用。然而，实际应用中的双向图通常是高度动态的，频繁的更新会导致(𝛼, 𝛽)-核的变化，从而影响依赖于(𝛼, 𝛽)-核的下游应用。因此，研究如何高效地维护动态双向图中的(𝛼, 𝛽)-核至关重要。

技术贡献

为了应对上述挑战，论文做出了以下主要贡献：

1. 提出了一种新的双核数（bi-core numbers）概念，用于支持双核的维护。
2. 基于双核数，提出了处理边插入和边删除的高效双核维护算法，有效减少了计算冗余。
3. 在真实和合成数据集上的广泛实验评估表明，所提出的维护算法比最先进的方法快了两个数量级。

• 边插入算法

  • 通过引入双核数的概念，分析顶点双核数的变化范围，提出高效的双核维护算法。实验结果表明，该算法在处理边插入时效率极高。

    算法步骤

    1. 输入：双向图G = (U, V, E)，待插入的边(e = (u, v))
    2. 初始化：标记受影响的节点集A，初始化为空集。
    3. 双核数更新：
       • 若u和v均未达到新的双核数要求，将其加入受影响的节点集A。
       • 对于A中的每个节点，递归更新其邻居节点的双核数，直到所有节点均满足新的双核数要求。

    def insert_edge(G, u, v):
        # 插入边 (u, v)
        G.add_edge(u, v)
        affected_nodes = set()
        
        # 更新双核数
        if G.degree[u] < alpha or G.degree[v] < beta:
            affected_nodes.add(u)
            affected_nodes.add(v)
        
        # 递归更新受影响的节点
        while affected_nodes:
            node = affected_nodes.pop()
            for neighbor in G.neighbors(node):
                if G.degree[neighbor] < alpha or G.degree[neighbor] < beta:
                    affected_nodes.add(neighbor)
                    # 更新邻居节点的双核数
                    G.update_degree(neighbor)
        
        return G
    

    

• 边删除算法

  类似于边插入算法，论文也提出了高效的边删除算法，并通过理论分析证明了算法的有效性。

  算法步骤

  1. 输入：双向图G = (U, V, E)，待删除的边(e = (u, v))
  2. 初始化：标记受影响的节点集A，初始化为空集。
  3. 双核数更新：
     • 若u和v在删除边后不再满足当前双核数要求，将其加入受影响的节点集A。
     • 对于A中的每个节点，递归更新其邻居节点的双核数，直到所有节点均满足新的双核数要求。

  def delete_edge(G, u, v):
      # 删除边 (u, v)
      G.remove_edge(u, v)
      affected_nodes = set()
      
      # 更新双核数
      if G.degree[u] < alpha or G.degree[v] < beta:
          affected_nodes.add(u)
          affected_nodes.add(v)
      
      # 递归更新受影响的节点
      while affected_nodes:
          node = affected_nodes.pop()
          for neighbor in G.neighbors(node):
              if G.degree[neighbor] < alpha or G.degree[neighbor] < beta:
                  affected_nodes.add(neighbor)
                  # 更新邻居节点的双核数
                  G.update_degree(neighbor)
      
      return G
  

  

实验评估

实验部分，论文对所提出的算法在真实和合成数据集上进行了广泛的评估。结果显示，论文所提出的算法在处理动态双向图时，比现有最先进的方法快了两个数量级。此外，实验还验证了算法在不同参数设置下的鲁棒性和有效性。

以下是上面几张图的说明:

图 5：在所有资料集上边插入的效率：

• 这张图比较了在不同资料集（如IMDB、WC、AR等）上使用不同方法（如Re-compute、BUI、TDI、BIT* 和 Edge-Insert）进行边插入时的运行时间。
• 结果显示，Edge-Insert 方法在所有资料集上均具有较高的效率，运行时间显着低于其他方法。

图 6：插入5000条边后受影响的顶点、c-pairs和双核数的数量：

• 这张图展示了在插入5000条边后，各资料集中受影响的顶点数量、c-pairs数量和双核数的更新数量。
• 结果显示，Edge-Insert 方法能有效控制受影响的范围，更新的双核数和受影响的顶点数量相对较少。

图 7：插入边数量的影响（每条边的平均时间）：

• 这张图展示了在不同资料集上，随着插入边数量的增加，每条边的平均运行时间。
• 结果显示，Edge-Insert 方法随着边数量的增加，运行时间增长相对平缓，显示出良好的可扩展性。

图 8：处理边插入的可扩展性测试：

• 这张图展示了在DTI和WT资料集上，Edge-Insert 方法和BIT* 方法在处理不同比例的边插入时的运行时间。
• 结果显示，Edge-Insert 方法在处理大量边插入时，运行时间增长趋势明显低于BIT* 方法。

图 9：在所有资料集上边删除的效率：

• 这张图比较了在不同资料集上使用不同方法（如Re-compute、BUI、TDR、BIT* 和 Edge-Delete）进行边删除时的运行时间。
• 结果显示，Edge-Delete 方法在所有资料集上均具有较高的效率，运行时间显着低于其他方法。

后续研究方向与应用前景

在《Efficient Core Maintenance in Large Bipartite Graphs》论文的基础上，未来的研究可以进一步拓展到更多复杂的动态环境中，例如考虑更多种类的图更新操作（如顶点插入和删除）以及更复杂的双向图结构。此外，探索如何同时维护多个不同参数的双核也是一个重要方向，这在需要同时关注多个社区或子图时尤为重要。随着图数据规模的不断扩大，研究如何在分布式和并行计算环境中高效地维护双核将显得尤为关键。另一个值得探索的领域是将双核维护算法扩展到时序双向图中，以支持时间动态下的双核维护和分析。在实际应用方面，该研究的成果在多个领域具有广泛的应用前景，例如在电子商务推荐系统中，通过维护用户和商品之间的(𝛼, 𝛽)-核，可以高效地识别用户群体和热门商品，从而提高推荐系统的准确性和效率；在社交网络中，维护用户和页面之间的双核，有助于发现兴趣群体和热点话题，推动社交网络的健康发展；在生物网络中，应用双核维护算法可以帮助研究人员更快地发现基因和蛋白质之间的关键关系，推动生物医学研究的进展；在金融网络中，维护账户和交易之间的双核，有助于实时检测和预防欺诈行为，保障金融系统的安全。总的来说，论文在双向图的动态维护方面提供了创新的解决方案，其研究成果对实际应用场景具有重要意义，并为未来的研究提供了丰富的方向和应用前景。

论文地址:https://dl.acm.org/doi/10.1145/3617329