研究院成果被中国计算机学会A类会议ICDE接收

  信息科学与工程学部2020级电子信息专业硕士研究生郜中强同学和2019级计算机科学与技术本科生程传奇同学作为共同一作完成的学术论文“Scalable Motif Counting for Large-scale Temporal Graph”(面向大规模时序图的可扩展Motif计数)于2022年3月24日被中国计算机学会(CCF)A类会议ICDE2022接收。ICDE (IEEE International Conference on Data Engineering) 是电气与电子工程师协会(IEEE)举办的旗舰会议,与SIGMOD、VLDB并称数据管理与数据库领域的三大国际顶级学术会议,入选为中国计算机学会推荐的A类国际学术会议,在国际上享有盛誉并具有广泛的学术影响力。ICDE对论文质量要求极高,近五年平均录用率为19.1%。



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


  郜中强同学本科毕业后留校继续攻读硕士研究生,在计算机科学与技术学院于彦伟副教授指导下,从事大规模时序图挖掘、图表征学习等领域研究。除上述研究外,该研究团队的研究成果已相继命中互联网领域国际顶级会议WWW 2021 (CCF A类会议)、数据挖掘领域国际顶级会议ICDM 2021 (CCF B类会议)。此次成果命中数据工程领域国际顶级会议ICDE,也是该研究团队取得的又一重要突破。


  作为共同一作的本科生程传奇同学曾荣获CCSP全国赛银牌、世界大学生超算竞赛(ASC)二等奖,一直对科研抱有浓厚的兴趣。程传奇同学作为大三本科生在业余时间积极参与科学研究,并作为共同一作发表该成果,这也是中国海洋大学计算机科学与技术学院本科生首次发表CCF A类国际顶级学术会议,对中国海洋大学本科生创新人才培养机制进行了积极有效的探索。


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


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


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