Finding Path Motifs in Large Temporal Graphs Using Algebraic Fingerprints

Area of Science:

• Computer Science
• Graph Theory
• Algorithms

Background:

• Temporal graphs represent dynamic networks where connections change over time.
• Pattern detection in these graphs is crucial for various real-world applications.
• Existing methods struggle with the scale and complexity of temporal graph pattern matching.

Purpose of the Study:

• To address pattern-detection problems in vertex-colored temporal graphs.
• To develop an efficient framework for searching temporal paths with specific color multisets.
• To establish complexity results and provide a scalable algorithmic solution.

Main Methods:

• An algebraic-algorithmic framework based on constrained multilinear sieving was designed.
• The framework handles queries for temporal paths containing specified multisets of vertex colors.
• Complexity results for these pattern-detection problems were established.

Main Results:

• The proposed solution demonstrates scalability to massive graphs (billions of edges).
• Efficient performance is achieved even for complex queries (e.g., 10 colors on millions of edges).
• The implementation shows practical edge-linear scalability and high optimization.

Conclusions:

• The developed framework offers a significant advancement in temporal graph pattern detection.
• The approach provides efficient and scalable solutions for complex pattern-matching tasks.
• Publicly available implementation facilitates practical application in diverse domains.