Triadic First-Order Logic Queries in Temporal Networks

<<< All talks

Triadic First-Order Logic Queries in Temporal Networks

When	Friday, February 7, 2025, 1:30 PM – 2:30 PM (MT)
Where	WEB L112

Abstract

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. Such networks are common representations for communication networks, citation networks, financial transactions, etc. 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 existence and universal quantifiers with thresholds. 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 triadic FOL queries, whose theoretical running time matches the best known running time for sparse graphs. Specifically, our algorithms run in time 𝑂 (m $\alpha \log \sigma_{\max}$). Here, $m$ is the number of temporal edges in the input graph, $\alpha$ is its degeneracy (maximum core number), and the $\sigma_{\max}$ is the maximum edge multiplicity. Our procedures can be efficiently implemented, and FOLTY has good empirical behavior. For example, we can answer triadic FOL queries on graphs with nearly 70M edges in less than an hour on commodity hardware. We believe that our work could start a new research direction in the classic well-studied problem of motif analysis.

Speaker

Tags: algorithms & theory data management networks & graphs

---

Part of the Data Science & AI Lecture Series. Something wrong on this page? Edit _data/talks/2025-02-07-omkar-bhalerao.toml.