大型复杂网络中超越成对关系的高阶交互通常建模为超图。分析超图属性(例如三元组计数)至关重要,因为超图能够揭示传统图模型无法捕获的复杂群体交互模式。在现实场景中,此类网络往往规模庞大且动态演化,带来显著的计算挑战。由于缺乏专用软件包与数据结构,大规模动态超图的分析迄今仍基本未被探索。受此研究空白驱动,我们提出 ESCHER——一种以 GPU 为中心的并行数据结构,用于高效且可扩展的超图演化表示(Efficient and Scalable Hypergraph Evolution Representation),旨在高效管理大规模超图的动态演化。我们还设计了一种超图三元组计数更新框架,在动态操作中最小化冗余计算,同时充分挖掘 ESCHER 的能力。我们在多种超图三元组计数类别上验证了该方法的有效性,包括基于超边、基于关联顶点以及时序三元组。在多个大规模真实世界及合成数据集上的实验结果表明,所提方法显著优于现有最先进方法,在基于超边、基于关联顶点和时序三元组三类任务上分别实现了最高达 104.5×、473.7× 和 112.5× 的加速比。
Higher-order interactions beyond pairwise relationships in large complex networks are often modeled as hypergraphs. Analyzing hypergraph properties such as triad counts is essential, as hypergraphs can reveal intricate group interaction patterns that conventional graphs fail to capture. In real-world scenarios, these networks are often large and dynamic, introducing significant computational challenges. Due to the absence of specialized software packages and data structures, the analysis of large dynamic hypergraphs remains largely unexplored. Motivated by this gap, we propose ESCHER, a GPU-centric parallel data structure for Efficient and Scalable Hypergraph Evolution Representation, designed to manage large scale hypergraph dynamics efficiently. We also design a hypergraph triad-count update framework that minimizes redundant computation while fully leveraging the capabilities of ESCHER for dynamic operations. We validate the efficacy of our approach across multiple categories of hypergraph triad counting, including hyperedge-based, incident-vertex-based, and temporal triads. Empirical results on both large real-world and synthetic datasets demonstrate that our proposed method outperforms existing state-of-the-art methods, achieving speedups of up to 104.5x, 473.7x, and 112.5x for hyperedge-based, incident-vertex-based, and temporal triad types, respectively.