  Graph Pattern based Node Matching (GPNM) is to find all the matches of the
nodes in a data graph GD based on a given pattern graph GP. GPNM has become
increasingly important in many applications, e.g., group finding and expert
recommendation. In real scenarios, both GP and GD are updated frequently.
However, the existing GPNM methods either need to perform a new GPNM procedure
from scratch to deliver the node matching results based on the updated GP and
GD or incrementally perform the GPNM procedure for each of the updates, leading
to low efficiency. Therefore, there is a pressing need for a new method to
efficiently deliver the node matching results on the updated graphs. In this
paper, we first analyze and detect the elimination relationships between the
updates. Then, we construct an Elimination Hierarchy Tree (EH-Tree) to index
these elimination relationships. In order to speed up the GPNM process, we
propose a graph partition method and then propose a new updates-aware GPNM
method, called UA-GPNM, considering the single-graph elimination relationships
among the updates in a single graph of GP or GD, and also the cross-graph
elimination relationships between the updates in GP and the updates in GD.
UA-GPNM first delivers the GPNM result of an initial query, and then delivers
the GPNM result of a subsequent query, based on the initial GPNM result and the
multiple updates that occur between two queries. The experimental results on
five real-world social graphs demonstrate that our proposed UA-GPNM is much
more efficient than the state-of-the-art GPNM methods.
