Discovering Association Rules with Graph Patterns in Temporal Networks  

作　　者：Chu Huang Qianzhen Zhang Deke Guo Xiang Zhao Xi Wang 

机构地区：[1]Science and Technology on Information Systems Engineering Laboratory,College of Systems Engineering,National University of Defense Technology,Changsha 410073,China

出　　处：《Tsinghua Science and Technology》2023年第2期344-359,共16页清华大学学报（自然科学版（英文版）

基　　金：This work was partially supported by the National Key Research and Development Program(No.2018YFB1800203);National Natural Science Foundation of China(No.U19B2024);Postgraduate Scientific Research Innovation Project of Hunan Province(No.CX20210038).

摘　　要：Discovering regularities between entities in temporal graphs is vital for many real-world applications(e.g.,social recommendation,emergency event detection,and cyberattack event detection).This paper proposes temporal graph association rules(TGARs)that extend traditional graph-pattern association rules in a static graph by incorporating the unique temporal information and constraints.We introduce quality measures(e.g.,support,confidence,and diversification)to characterize meaningful TGARs that are useful and diversified.In addition,the proposed support metric is an upper bound for alternative metrics,allowing us to guarantee a superset of patterns.We extend conventional confidence measures in terms of maximal occurrences of TGARs.The diversification score strikes a balance between interestingness and diversity.Although the problem is NP-hard,we develop an effective discovery algorithm for TGARs that integrates TGARs generation and TGARs selection and shows that mining TGARs is feasible over a temporal graph.We propose pruning strategies to filter TGARs that have low support or cannot make top-k as early as possible.Moreover,we design an auxiliary data structure to prune the TGARs that do not meet the constraints during the TGARs generation process to avoid conducting repeated subgraph matching for each extension in the search space.We experimentally verify the effectiveness,efficiency,and scalability of our algorithms in discovering diversified top-k TGARs from temporal graphs in real-life applications.

关 键 词：temporal networks graph association rule subgraph pattern matching graph mining big graphs 

分 类 号：TP183[自动化与计算机技术—控制理论与控制工程] TP391.1[自动化与计算机技术—控制科学与工程]