Neural subgraph counting on stream graphs via localized updates and monotonic learning

Area of Science:

• Computer Science
• Data Science
• Graph Theory

Background:

• Graphs are fundamental data structures representing complex relationships.
• Stream graphs efficiently process dynamically evolving graph data.
• Subgraph counting in stream graphs is computationally challenging (#P-complete).

Purpose of the Study:

• Introduce StreamSC, a novel framework for subgraph counting in stream graphs.
• Address the computational challenges of subgraph counting in dynamic graphs.
• Propose the first learning-based approach for subgraph counting in stream graphs.

Main Methods:

• Developed StreamSC, a learning-based framework.
• Incorporated innovations to handle dynamic graph changes (edge insertions/deletions).
• Evaluated performance on five real-world graphs.

Main Results:

• StreamSC demonstrates high accuracy in subgraph counting.
• StreamSC achieves significant efficiency gains.
• The framework effectively handles dynamic graph evolution.

Conclusions:

• StreamSC offers a priority solution for subgraph counting on stream graphs.
• The learning-based approach effectively tackles #P-complete challenges.
• StreamSC provides an efficient and accurate method for analyzing evolving graph data.