Statistics information of datasets.

Graphs are a representative type of fundamental data structures. They are capable of representing complex association relationships in diverse domains. For large-scale graph processing, the stream graphs have become efficient tools to process dynamically evolving graph data. When processing stream graphs, the subgraph counting problem is a key technique, which faces significant computational challenges due to its #P-complete nature. This work introduces StreamSC, a novel framework that efficiently estimate subgraph counting results on stream graphs through two key innovations: (i) It’s the first learning-based framework to address the subgraph counting problem focused on stream graphs; and (ii) this framework addresses the challenges from dynamic changes of the data graph caused by the insertion or deletion of edges. Experiments on 5 real-word graphs show the priority of StreamSC on accuracy and efficiency.

图是一类典型的基础数据结构，能够表征多领域中的复杂关联关系。针对大规模图处理任务，流图（stream graph）已成为处理动态演化图数据的高效工具。在流图处理场景下，子图计数问题（subgraph counting problem）是一项核心技术，但由于其属于#P完全问题（#P-complete），面临着严峻的计算挑战。本研究提出了StreamSC框架，该框架通过两项关键创新实现流图上子图计数结果的高效估计：其一，它是首个针对流图场景下子图计数问题的基于学习的框架；其二，该框架解决了由边的增删操作引发的数据图动态变化所带来的挑战。在5张真实世界图（real-world graph）数据集上开展的实验验证了StreamSC在准确率与效率上的显著优势。