提出新方法挖掘时间网络中复杂的三元模式，提升分析精度。
Triadic First-Order Logic Queries in Temporal Networks
- 用带阈值的逻辑表达式定义三元查询，支持更丰富的语义。
- 算法FOLTY在近7000万边的图上一小时内完成查询，效率高。
- 适合研究复杂网络动态结构的学者，推动时序图分析新方向。
图论中的模式计数是网络分析的核心问题。给定大规模网络图 $G$，模式 $H$ 是一个小型“结构”子图，用于揭示局部特征。模式挖掘即寻找 $G$ 中所有与 $H $ 匹配的子图。最简单却最具挑战性的情形是 $H $ 包含三个顶点，称为“三元”查询。近期研究关注“时序图挖掘”，即 $G $ 的边带有时间戳（和方向），且 $H $ 带有时间约束。受逻辑与数据库理论启发，本文引入“阈值一阶逻辑（FOL）模式分析）”，适用于大规模时序网络。典型的三元查询如：找出在1小时内构成三角形的三元组。而阈值一阶逻辑查询可表达：“找出所有顶点对 $u,v$，使得在超过一半满足 $(u,w)$ 有边的 $w$ 中，$(v,w)$ 也在一小时内存在边”。我们设计首个算法 FOLTY 来处理此类三元阈值一阶逻辑查询。理论运行时间与稀疏图中时序三角形计数的最佳已知算法相当。通过专用时序数据结构实现高效版本，FOLTY 在包含近7000万条边的图上可在不到一小时完成查询，运行表现优异。本工作有望开启经典模式分析问题的新研究方向。
原文摘要 · Abstract (English)
Motif counting is a fundamental problem in network analysis, and there is a rich literature of theoretical and applied algorithms for this problem. Given a large input network $G$, a motif $H$ is a small "pattern" graph indicative of special local structure. Motif/pattern mining involves finding all matches of this pattern in the input $G$. The simplest, yet challenging, case of motif counting is when $H$ has three vertices, often called a "triadic" query. Recent work has focused on "temporal graph mining", where the network $G$ has edges with timestamps (and directions) and $H$ has time constraints. Inspired by concepts in logic and database theory, we introduce the study of "thresholded First Order Logic (FOL) Motif Analysis" for massive temporal networks. A typical triadic motif query asks for the existence of three vertices that form a desired temporal pattern. An "FOL" motif query is obtained by having both existential and thresholded universal quantifiers. This allows for query semantics that can mine richer information from networks. A typical triadic query would be "find all triples of vertices $u,v,w$ such that they form a triangle within one hour". A thresholded FOL query can express "find all pairs $u,v$ such that for half of $w$ where $(u,w)$ formed an edge, $(v,w)$ also formed an edge within an hour". We design the first algorithm, FOLTY, for mining thresholded FOL triadic queries. The theoretical running time of FOLTY matches the best known running time for temporal triangle counting in sparse graphs. We give an efficient implementation of FOLTY using specialized temporal data structures. FOLTY has excellent empirical behavior, and can answer triadic FOL queries on graphs with nearly 70M edges is less than hour on commodity hardware. Our work has the potential to start a new research direction in the classic well-studied problem of motif analysis.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。