  In many real-world applications such as social network analysis, knowledge
graph discovery, biological network analytics, and so on, graph data management
has become increasingly important and has drawn much attention from the
database community. While many graphs (e.g., Twitter, Wikipedia, etc.) are
usually involving over time, it is of great importance to study the dynamic
subgraph matching (DSM) problem, a fundamental yet challenging graph operator,
which continuously monitors subgraph matching results over dynamic graphs with
a stream of edge updates. To efficiently tackle the DSM problem, we carefully
design a novel vertex dominance embedding approach, which effectively encodes
vertex labels that can be incrementally maintained upon graph updates. Inspire
by low pruning power for high-degree vertices, we propose a new degree grouping
technique over basic subgraph patterns in different degree groups (i.e., groups
of star substructures), and devise degree-aware star substructure synopses
(DAS^3) to effectively facilitate our designed vertex dominance and range
pruning strategies. We develop efficient algorithms to incrementally maintain
dynamic graphs and answer DSM queries. Through extensive experiments, we
confirm the efficiency of our proposed approaches over both real and synthetic
graphs.
