[ Russian ] [ English ]

Графовые зависимости: обзор формализмов, задач, алгоритмов

Антон Черников
СПбГУ

Доклад посвящен типам функциональных зависимостей для графовых данных. В общем случае функциональная зависимость на графе представляет собой правило вида Q[A > B], связывающее топологический шаблон подграфа Q с логическим условием A > B, которое должно выполняться для его вершин и рёбер. Пример такой зависимости типа GFD представлен на Рис. 1.


Рис. 1. Пример: GFD и ее вложения.

Подобные зависимости имеют приложения при поиске противоречий, разрешении сущностей, расширении баз знаний, оптимизации запросов и выявлении мошенничества. Кроме того, зависимости на графах помогают задать целостность и семантику данных в случае реальных графов (социальные сети, финансовые транзакции, базы знаний и др.), так как те, в отличие от табличных данных, зачастую не имеют схемы.

В докладе описываются и классифицируются основные типы графовых зависимостей, представляются задачи их поиска и валидации.Также рассматриваются общие схемы алгоритмов для этих задач.

Для наглядности в ходе доклада будут подробно разобраны четыре типа графовых зависимостей, представляющих разные классы формализмов:

  1. Графовая функциональная зависимость (Graph Functional Dependency) из класса строгих графовых ограничений целостности, соединяющая топологический паттерн (структуру зависимости) с равенством значений атрибутов;
  2. Паттерн-ассоциативное правило (Graph Pattern Association Rule) из класса графовых ассоциативных правил, позволяющее выявлять в графах статистически частые закономерности и скрытые связи (на основе поддержки и достоверности);
  3. Порождающая графовая зависимость (Graph Generating Dependency) из класса порождающих зависимостей, позволяющая на основе найденного шаблона автоматически генерировать в графе новые вершины и рёбра;
  4. Приближённая зависимость сущностей (Approximate Graph Entity Dependency) из класса приближённых зависимостей, ослабляющая ограничения, позволяя находить зависимости в графах с ошибками.

Каждый тип снабжается определением и примерами использования.

В заключении мы коснемся эволюции концепции зависимостей от слабоструктурированных данных (XML) к современным графовым формализмам, а также поговорим об актуальных направлениях развития области таких как нейросетевые подходы (GNN). Наконец, вкратце, затронем вопросы программной реализации в системе Desbordante.

Литература:

  1. Fan Wenfei, Fan Zhe, Tian Chao и Dong Xin Luna. Keys for graphs // Proc. VLDB Endow. — 2015. — Авг. — Т. 8, № 12. — С. 1590–1601. — https://doi.org/10.14778/2824032.2824056
  2. Vincent Millist W., Liu Jixue и Liu Chengfei. Strong functional dependencies and their application to normal forms in XML // ACM Trans. Database Syst. — 2004. — Сент. — Т. 29, № 3. — С. 445–462. — https://doi.org/10.1145/1016028.1016029
  3. Fan Wenfei, Wu Yinghui и Xu Jingbo. Functional Dependencies for Graphs // Proceedings of the 2016 International Conference on Management of Data. — New York, NY, USA : Association for Computing Machinery, 2016. — SIGMOD ’16. — С. 1843–1857. — https://doi.org/10.1145/2882903.2915232
  4. Fan Wenfei и Lu Ping. Dependencies for Graphs // Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. — New York, NY, USA : Association for Computing Machinery, 2017. — PODS ’17. — С. 403–416. — https://doi.org/10.1145/3034786.3056114
  5. Shimomura Larissa Capobianco. Graph Profiling with Graph Generating Dependencies // PhD@VLDB. — 2022.
  6. Agrawal Rakesh, Imielinski Tomasz и Swami Arun. Mining Association Rules Between Sets of Items in Large Databases // Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data. — 1993. — С. 207–216.
  7. Fan Wenfei, Wang Xin, Wu Yinghui и Xu Jingbo. Association rules with graph patterns // Proc. VLDB Endow. — 2015. — Авг. — Т. 8, № 12. — С. 1502–1513. — https://doi.org/10.14778/2824032.2824048
  8. Kivinen Jyrki и Mannila Heikki. Approximate Inference of Functional Dependencies from Relations // Theoretical Computer Science. — 1995. — Т. 149, № 1. — С. 129–149.
  9. Zhao Sibo, Zhou Guangtong, Kwashie Selasi, Bewong Michael, Nofong Vincent M., Zhang Yidi, Hu Junwei, Qin Li и Feng Zaiwen. FastAGEDs+: Fast Approximate Graph Entity Dependency Discovery // Expert Systems. — 2025. — Т. 42, № 11. — С. e70152. — https://onlinelibrary.wiley.com/doi/abs/10.1111/exsy.70152
  10. Alipourlangouri Morteza. Temporal Dependencies for Graphs // Proceedings of the 2021 International Conference on Management of Data. — New York, NY, USA : Association for Computing Machinery, 2021. — SIGMOD ’21. — С. 2881–2883. — https://doi.org/10.1145/3448016.3450586
  11. Namaki Mohammad Hossein, Wu Yinghui, Song Qi, Lin Peng, and Ge Tingjian. Discovering Graph Temporal Association Rules // Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. — New York, NY, USA : Association for Computing Machinery, 2017. — CIKM ’17. — P. 1697–1706. — https://doi.org/10.1145/3132847.3133014
  12. Vo Loan TH, Cao Jinli, Rahayu J Wenny и др. Discovering Conditional Functional Dependencies in XML Data // ADC. — 2011. — С. 143–152.
  13. Kwashie Selasi, Liu Lin, Liu Jixue, Stumptner Markus, Li Jiuyong и Yang Lujing. Certus: An effective entity resolution approach with graph differential dependencies (GDDs) // Proceedings of the VLDB Endowment. — 2019. — Т. 12, № 6. — С. 653–666.
  14. Song Shaoxu, Cheng Hong, Yu Jeffrey Xu и Chen Lei. Repairing vertex labels under neighborhood constraints // Proceedings of the VLDB Endowment. — 2014. — Т. 7, № 11. — С. 987–998.
  15. Broder Andrei, Das Shirshanka, Fontoura Marcus, Ghosh Bhaskar, Josifovski Vanja, Shanmugasundaram Jayavel и Vassilvitskii Sergei. Efficiently evaluating graph constraints in content-based publish/subscribe // Proceedings of the 20th International Conference on World Wide Web. — New York, NY, USA : Association for Computing Machinery, 2011. — WWW ’11. — С. 497–506. — https://doi.org/10.1145/1963405.1963476
  16. Jin Ruoming, Hong Hui, Wang Haixun, Ruan Ning и Xiang Yang. Computing label-constraint reachability in graph databases // Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data. — New York, NY, USA : Association for Computing Machinery, 2010. — SIGMOD ’10. — С. 123–134. — https://doi.org/10.1145/1807167.1807183
  17. Fan Wenfei, Liu Xueli, Lu Ping, and Tian Chao. Catching Numeric Inconsistencies in Graphs // Proceedings of the 2018 International Conference on Management of Data. — New York, NY, USA : Association for Computing Machinery, 2018. — SIGMOD ’18. — P. 381–393. — https://doi.org/10.1145/3183713.3183753
  18. Fan Wenfei, Wu Yinghui, and Xu Jingbo. Adding Counting Quantifiers to Graph Patterns // Proceedings of the 2016 International Conference on Management of Data. — New York, NY, USA : Association for Computing Machinery, 2016. — SIGMOD ’16. — P. 1215–1230. — https://doi.org/10.1145/2882903.2882937
  19. Sasaki Yuya and Karras Panagiotis. Mining Path Association Rules in Large Property Graphs // Proceedings of the 33rd ACM International Conference on Information and Knowledge Management. — New York, NY, USA : Association for Computing Machinery, 2024. — CIKM ’24. — P. 1994–2003. — https://doi.org/10.1145/3627673.3679525
  20. Fan Wenfei, Jin Ruochun, Liu Muyang, Lu Ping, Tian Chao и Zhou Jingren. Capturing associations in graphs // Proc. VLDB Endow. — 2020. — Июль. — Т. 13, № 12. — С. 1863–1876. — https://doi.org/10.14778/3407790.3407795
  21. Fan Wenfei, Fu Wenzhi, Jin Ruochun, Liu Muyang, Lu Ping и Tian Chao. Making It Tractable to Catch Duplicates and Conflicts in Graphs // Proc. ACM Manag. Data. — 2023. — Май. — Т. 1, № 1. — https://doi.org/10.1145/3588940
  22. Dong Bowen, Wang Wenjun, Sun Lifei, Liu Xueli и Mai Zhenzhen. Anomaly Detection Using Graph Anomaly Rules // Big Data Mining and Analytics. — 2025. — Т. 8, № 5. — С. 1075–1091.
Supported by Synthesis Group