Многослойный подход к поиску изоморфных подграфов в HP-графах

Визуальное моделирование на данный момент широко распространено, однако существующие платформы, предназначенные для моделирования, не могут удовлетворить все требования пользователей. Визуальные языки, как правило, основаны на графовых моделях, однако графовые формализмы, используемые для представления моделей, обладают существенными ограничениями. Для решения проблемы недостаточной выразительности существующих графовых моделей ранее была представлена новая графовая модель (HP-граф), основным элементом которой является множество полюсов, подмножества которых объединены в вершины и гиперребра. Многие операции над визуальными моделями, включая трансформацию моделей, сталкиваются с проблемой поиска изоморфного подграфа, что оказывает значительное влияние на скорость их выполнения. Многослойная структура HP-графа позволяет снизить временную сложность алгоритмов поиска. Количество операций может быть снижено благодаря тому, что поиск изначально осуществляется на слое вершин и гиперребер, и только в случае нахождения подграфа с желаемыми характеристиками алгоритм переходит на более детальный уровень, где сравниваются наборы соответствующих полюсов и обыкновенных связей отобранных подграфов. Представлено описание идеи многослойного подхода. Предложен алгоритм поиска с возвратом, основанный на этом подходе. Алгоритмы Ульмана и VF2 адаптированы к данному подходу, выполнена оценка их временной сложности. Предложенный подход постепенно сокращает область поиска алгоритмов и помогает уменьшить их общую сложность. В статье доказывается, что существующие алгоритмы сопоставления подграфов, за исключением тех, которые изменяют шаблон графа, могут быть успешно адаптированы к предлагаемому подходу.

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.