信息学部研究生和本科生共同发表中国计算机学会A类会议文章

发布者:王乐水发布时间:2022-03-25浏览次数:10

信息科学与工程学部2020级电子信息专业硕士研究生郜中强同学和2019级计算机科学与技术本科生程传奇同学作为共同一作完成的学术论文“Scalable Motif Counting for Large-scale Temporal Graph”(面向大规模时序图的可扩展Motif计数)于2022324日被中国计算机学会(CCFA类会议ICDE2022接收。该论文是在计算机科学与技术学院于彦伟副教授指导下完成该团队前期已相继互联网领域国际顶级会议WWW 2021 (CCF A类会议)、数据挖掘领域国际顶级会议ICDM 2021 (CCF B类会议)上发表文章。此次成果命中数据工程领域国际顶级会议ICDE,是该研究团队取得的又一重要突破同时也是中国海洋大学计算机科学与技术学院本科生首次发表CCF A类国际顶级学术会议,对中国海洋大学本科生创新人才培养机制进行了积极有效的探索。

网络Motif是一类重要的频繁子图,能够有效捕获网络中局部高阶结构,近年来被广泛应用于网络表征学习和各类网络挖掘应用。例如,在电子商务网络中,这种频繁的网络Motif能够有效地建模用户与商品之间的各种互动;在社会网络分析中,也经常使用从大型动态网络中挖掘的Motif来理解人类交流是如何展开的。如何有效地挖掘这类子图结构成为大规模时序图挖掘的瓶颈问题,该研究工作提出了一种高效的并行挖掘框架模型,可有效从大规模时序图上挖掘并计数各类时序Motif实例,有效解决了这一瓶颈问题。


(a) 时序图示例                  (bmotif类型示例

带有时间戳信息的时序图和时序motif示例

ICDE (IEEE International Conference on Data Engineering) 是电气与电子工程师协会(IEEE)举办的旗舰会议,与SIGMODVLDB并称数据管理与数据库领域的三大国际顶级学术会议,入选为中国计算机学会推荐的A类国际学术会议,在国际上享有盛誉并具有广泛的学术影响力。ICDE对论文质量要求极高,平均录用率约为19.1%

通讯员:于彦伟


论文题目:Scalable Motif Counting for Large-scale Temporal Graph

作者:郜中强*,程传奇*,于彦伟,曹磊,黄超,董军宇

简介:时序图分析的一个基本问题是计算连通子图模式(例如,motif)的出现次数,并且广泛应用于各个领域,例如异常检测、结构预测和网络表示学习。然而,由于计算量大或并行性不足等问题,现有的致力于精确计算时序Motif的工作无法扩展到大规模时序图。为此,本文提出了一个可扩展的并行框架来精确计算大规模时序图中的时序Motif。首先,根据时序Motif的不同属性对其进行了分类,然后针对不同类型的Motif设计了定制算法(FAST),这些算法能够提供有效的策略来精确计算每类 Motif的实例。此外,本文还设计了精妙的数据结构,即三维和四维计数器,使所提算法能够根据边的信息和边之间的关系直接识别每个类别的Motif实例,从而显著提高计数效率。基于所提的计数算法,还设计了一个层次并行框架(HARE)─节点间并行以及节点内并行,并充分利用CPU的多线程能力来并行计数所有时序Motif。在16个真实的时序数据集上的大量实验,证明所提的时序Motif 计数框架的优越性和可扩展性,与最新方法相比,实现了高达538倍的加速比。


层次并行框架HARE的可扩展性部分对比结果