Given a labeled graph, the frequent-subgraph mining (FSM) problem asks to
find all the $k$-vertex subgraphs that appear with frequency greater than a
given threshold. FSM has numerous applications ranging from biology to network
science, as it provides a compact summary of the characteristics of the graph.
However, the task is challenging, even more so for evolving graphs due to the
streaming nature of the input and the exponential time complexity of the
problem.
In this paper, we initiate the study of the approximate FSM problem in both
incremental and fully-dynamic streaming settings, where arbitrary edges can be
added or removed from the graph. For each streaming setting, we propose
algorithms that can extract a high-quality approximation of the frequent
$k$-vertex subgraphs for a given threshold, at any given time instance, with
high probability. In contrast to the existing state-of-the-art solutions that
require iterating over the entire set of subgraphs for any update, our
algorithms operate by maintaining a uniform sample of $k$-vertex subgraphs with
optimized neighborhood-exploration procedures local to the updates. We provide
theoretical analysis of the proposed algorithms and empirically demonstrate
that the proposed algorithms generate high-quality results compared to
baselines.

本文研究了具有标签的图中的频繁子图挖掘问题，提出了适用于增量和完全动态流设置的算法，以提取给定阈值下的高质量近似频繁 $k$- 顶点子图，通过保持一个均匀采样 $k$- 顶点子图组，并优化围绕更新的邻域探索过程，以及理论分析的支持，我们证明了所提出的算法相对于现有的最先进的解决方案可以产生高质量的结果。