A Multilayer Approach to Subgraph Matching in HP-graphs

Visual modeling is widely used nowadays, but the existing modeling platforms cannot meet all the user requirements. Visual languages are usually based on graph models, but the graph types used have significant restrictions. A new graph model, called HP-graph, whose main element is a set of poles, the subsets of which are combined into vertices and edges, has been previously presented to solve the problem of insufficient expressiveness of the existing graph models. Transformations and many other operations on visual models face a problem of subgraph matching, which slows down their execution. A multilayer approach to subgraph matching can be a solution for this problem if a modeling system is based on the HP-graph. In this case, the search is started on the higher level of the graph model, where vertices and hyperedges are compared without revealing their structures, and only when a candidate is found, it moves to the level of poles, where the comparison of the decomposed structures is performed. The description of the idea of the multilayer approach is given. A backtracking algorithm based on this approach is presented. The Ullmann algorithm and VF2 are adapted to this approach and are analyzed for complexity. The proposed approach incrementally decreases the search field of the backtracking algorithm and helps to decrease its overall complexity. The paper proves that the existing subgraph matching algorithms except ones that modify a graph pattern can be successfully adapted to the proposed approach.

1. Koznov D.V. Methodology and tools for domain-specific modeling. Doctor Degree thesis. Saint-Petersburg, 2016, 430 p. (in Russian) / Кознов Д.В. Методология и инструментарий предметно-ориентированного моделирования. Диссертация доктора технических наук. СПб., 2016 г., 430 стр.

2. A formalism for describing software systems and computational processes for cyclic parallel processing of real time data. Information and control systems, 2006, no. 2, pp. 8-13 (in Russian) / Стручков И.В. Формализм для описания программных систем и вычислительных процессов циклической параллельной обработки данных реального времени. Информационно-управляющие системы, вып. 2, 2006, стр. 8-13.

3. Courcelle B. Recognizable Sets of Graphs, Hypergraphs and Relational Structures: A Survey. Lecture Notes in Computer Science, vol. 3340, 2005, pp. 1-11.

4. Power J., Tourlas K. Abstraction in Reasoning about Higraph-Based Systems. Lecture Notes in Computer Science, vol. 2620, 2003, pp. 392-408.

5. Sukhov A.O. Development of tools for creating visual subject-oriented languages. PhD thesis, Moscow, 2013, 256 p. (in Russian) / Сухов А.О. Разработка инструментальных средств создания визуальных предметно-ориентированных языков. Диссертация кандидата физико-математическиъх наук. М., 2013 г. 256 стр.

6. Mikov A.I. Performance evaluation: textbook. Krasnodar, Kuban State University, 2013, 89 p.

7. Suvorov N.M., Lyadova L.N. HP-Graph as a Basis of a DSM Platform Visual Model Editor. Suvorov N.M., Lyadova L.N. HP-Graph as a Basis of a DSM Platform Visual Model Editor. Trudy ISP RAN/Proc. ISP RAS, vol. 32, issue 2, 2020. pp. 149-160. DOI: 10.15514/ISPRAS–2020–32(2)–12.

8. Parra F. Dean T. Survey of Graph Rewriting applied to Model Transformations. In Proc. of the 2nd International Conference on Model-Driven Engineering and Software Development, 2014, pp. 431 441.

9. Ehrig H., Ehrig K., Prange U., Taentzer G. Fundamentals of Algebraic Graph Transformation. Springer 2006, 403 p.

10. Yan X., Yu P.S., Han J. Graph Indexing: A Frequent Structure-based Approach. In Proc. of the ACM SIGMOD International Conference on Management of Data, 2004, pp. 335-346.

11. Fan W. Graph pattern matching revised for social network analysis. In Proc. of the 15th International Conference on Database Theory, 2012, pp. 8 21.

12. Liu C., Lio B., Kropatsch W, eds. Advances in Graph-based Pattern Recognition. Pattern Recognition Letters, vol. 87, 2017, 230 p.

13. Pržulj N., Corneil D.G., Jurisica I. Efficient Estimation of Graphlet Frequency Distributions in Protein–protein Interaction Networks. Bioinformatics, vol. 22, no. 8, 2006, pp. 974-980.

14. Han M., Kim H. et al Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together. In Proc. of the ACM SIGMOD International Conference on Management of Data, 2019, pp. 1429 1446.

15. Carletti V., Foggia P. et al. Challenging the Time Complexity of Exact Subgraph Isomorphism for Huge and Dense Graphs with VF3. In: IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 40, no. 4, 2018, pp. 804-818.

16. Ren X., Wang J. Exploiting Vertex Relationships in Speending up Subgraph Isomorphism over Large Graphs. Proceedings of the VLDB Endowment, vol. 8, no. 5, 2015, pp. 617-628.

17. Lee J., Han W. et ak. An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases. In: Proceedings if the VLDB Endowment, vol. 6, no. 2, 2012, pp. 133-144.

18. Seriy A.P., Lyadova L.N. An Approach to Graph Matching in the Component of Model Transformations. In Proc. of the 7th Spring/Summer Young Researchers’ Colloquium on Software Engineering, 2013, pp. 41-46.

19. Ullmann J.R. An Algorithm for Subgraph Isomorphism. Journal of the ACM, vol. 23, no. 1, 1976, pp. 31-42.

20. Cordella L.P., Foggia P. et al. (Sub)Graph Isomorphism Algorithm for Matching Large Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 10, 2004, pp. 1367-1372.

21. Carletti V., Foggia P., Vento M. VF2 Plus: An Improved version of VF2 for Biological Graphs. Lecture Notes in Computer Science, vol. 9069, 2015, pp. 168-177.

22. Carletti V., Foggia P. et al. Challenging the time complexity of exact subgraph isomorphism for huge and dense graphs with VF3. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 40, no. 4, 2018, pp. 804-818.

23. Han W., TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases. In Proc. of the ACM SIGMOD International Conference on Management of Data, 2013, pp. 337-348.

24. Bi F., Chang L., Lin X., Qin L., Zhang W. Efficient Subgraph Matching by Postponing Cartesian Products. In Proc. of the ACM SIGMOD International Conference on Management of Data, 2016, pp. 1199-1214.

25. Shang H., Zhang Y., Lin X., Yu J.X. Taming verification hardness: an efficient algorithm for testing subgraph isomorphism. Proceedings if the VLDB Endowment, vol. 1, no. 1, 2008, pp. 364-375.

26. Zhao P., Han J. On graph query optimization in large networks. Proceedings if the VLDB Endowment, vol. 3, 2010, pp. 340-351.