Interactive graph-matching using active query strategies

• An interactive method is presented to improve the matching between graphs.
• Active strategies are used to select nodes the oracle has to interact with.
• Six different strategies have been adapted from classical active learning.
• We present a practical evaluation with four different graph databases.

Given two graphs, the aim of graph matching is to find the ׳׳best׳׳ matching between the nodes of one graph and the nodes of the other graph. Due to distortions of the data and the complexity of the problem, in some applications, completely automatic processes do not return a satisfactory graph matching. We propose a method to perform active and interactive graph matching in which an active module queries one of the nodes of the graphs and the oracle (human or artificial) returns the node of the other graph it has to be mapped with. The interactive algorithm reaches the matching desired by the user in few interactions, since by imposing a node-to-node mapping, other ones are automatically amended. The method uses any graph matching algorithm that iteratively updates a probability matrix between nodes since it only requires access to the probability matrix and to update the costs between nodes and arcs. We present and practically validate different active strategies.