Abstract Conceptual graphs (CGs) have logical backgrounds and support visual reasoning. They are widely studied and used with the development of artificial intelligence. Homomorphic matching is the basic operation for the logical deduction based on CGs, which is a NP-complete problem. When the scale of the CG database is large, how to perform efficient homomorphic matching is a key factor affecting the usage of graph rules. In this paper, the CGs are transformed into labeled undirected graphs which have no multiple edges, then a new hybrid approach is proposed to improve the efficiency of homomorphic matching for graph rules. The hybrid approach is based on the traditional backtrack algorithm with a standard filter, and there are three improvements. Firstly, in the graph data sets, which are generated and enriched by using graph rules, there are frequent patterns occurred. Therefore, optimal homomorphic matching orders (OHMOs) of graph rules can be extracted from the historical graph data. OHMOs can reduce the number of comparisons during searching homomorphisms. Secondly, label type checking orders of nodes in the hypotheses of graph rules are optimized with the frequency statistics method. Using the two-stage optimized label checking orders (OLCOs) can save the calculation time of obtaining the candidate nodes and reduce the comparison times during searching homomorphisms. Thirdly, signatures of nodes in CGs are defined, and we use them to further filter the candidate nodes, then the search space of homomorphic matching is reduced. OHMOs and OLCOs are obtained off-line and signatures are calculated incrementally, so the on-line calculation for searching homomorphisms is seldom affected. At last, a study case is conducted, and the experiment results illustrate that the proposed approach is reasonable and effective.
Paper
Full text
A new hybrid approach to improve the efficiency of homomorphic matching for graph rules
Semantic Scholar · Computer Science · 2019
Abstract
Abstract Conceptual graphs (CGs) have logical backgrounds and support visual reasoning. They are widely studied and used with the development of artificial intelligence. Homomorphic matching is the basic operation for the logical deduction based on CGs, which is a NP-complete problem. When the scale of the CG database is large, how to perform efficient homomorphic matching is a key factor affecting the usage of graph rules. In this paper, the CGs are transformed into labeled undirected graphs which have no multiple edges, then a new hybrid approach is proposed to improve the efficiency of homomorphic matching for graph rules. The hybrid approach is based on the traditional backtrack algorithm with a standard filter, and there are three improvements. Firstly, in the graph data sets, which are generated and enriched by using graph rules, there are frequent patterns occurred. Therefore, optimal homomorphic matching orders (OHMOs) of graph rules can be extracted from the historical graph data. OHMOs can reduce the number of comparisons during searching homomorphisms. Secondly, label type checking orders of nodes in the hypotheses of graph rules are optimized with the frequency statistics method. Using the two-stage optimized label checking orders (OLCOs) can save the calculation time of obtaining the candidate nodes and reduce the comparison times during searching homomorphisms. Thirdly, signatures of nodes in CGs are defined, and we use them to further filter the candidate nodes, then the search space of homomorphic matching is reduced. OHMOs and OLCOs are obtained off-line and signatures are calculated incrementally, so the on-line calculation for searching homomorphisms is seldom affected. At last, a study case is conducted, and the experiment results illustrate that the proposed approach is reasonable and effective.