Меню
Публикации
2026
2025
2024
2023
2022
2021
2020
2019
2018
2017
2016
2015
2014
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
Главный редактор
НИКИФОРОВ
Владимир Олегович
д.т.н., профессор
Партнеры
doi: 10.17586/2226-1494-2026-26-2-331-336
УДК 004.896
Предсказание связей в эго-графах с GNN (на англ.яз.)
Читать статью полностью
Язык статьи - английский
Ссылка для цитирования:
Аннотация
Ссылка для цитирования:
Замятин Е.И. Предсказание связей в эго-графах с GNN // Научно-технический вестник информационных технологий, механики и оптики. 2026. Т. 26, № 2. С. 331–336 (на англ. яз.). doi: 10.17586/2226-1494-2026-26-2-331-336
Аннотация
Введение. Задача предсказания связей в графе — одна из ключевых задач в области анализа социальных сетей. В основе одного из распространенных способов построения таких систем лежит идея декомпозиции задачи на два уровня. На первом уровне формируются предсказания возникновения связей внутри эго-графов, на втором — агрегация результатов и формирование итоговой выдачи. Точность таких систем определяется моделью первого уровня. Обычно здесь используют эвристические методы. Основное внимание в данной работе уделено разработке и исследованию новой модели с учителем для улучшения качества предсказаний связей внутри эго-графов. Неоднородность свойств ребер, отсутствие признаков вершин, а также динамическая природа эго-графов выделяют эту задачу среди остальных. Метод. Предлагаемый метод относится к классу графовых нейронных сетей. Его отличительная особенность в способности эффективно учитывать топологию графа вместе со свойствами ребер, при этом не опираясь на признаки вершин. Такой эффект удается достичь за счет моделирования скрытого состояния именно пар вершин, а не каждой вершины в отдельности. Итеративная сущность модели позволяет распространять знание о взаимосвязях вершин, с каждым шагом увеличивая сложность учитываемых структур. Основные результаты. Для замеров эффективности модели была использована база данных Ego-VK, состоящая из набора эго-графов подвыборки пользователей социальной сети «ВКонтакте». Проведено сравнение с классическим методом предсказания связей Adamic-Adar, а также с современными подходами на основе графовых нейронных сетей. Эксперименты показали, что предлагаемая модель значительно превосходит бейзлайны с точки зрения метрики качества ранжирования NDCG@5. Обсуждение. Полученные результаты свидетельствуют о высокой эффективности предложенной модели, а возможность интеграции в декомпозированные системы делает ее широко применимой в индустрии.
Ключевые слова: информационный поиск, рекомендательные системы, графовые нейросети, анализ социальных графов, эго-графы
Благодарности. Работа выполнена в рамках проекта № 625135 «Разработка программных модулей для эффективного обучения и применения моделей глубокого обучения».
Список литературы
Благодарности. Работа выполнена в рамках проекта № 625135 «Разработка программных модулей для эффективного обучения и применения моделей глубокого обучения».
Список литературы
1. KeramatfarA., Rafiee M., Amirkhani H. Graph Neural Networks: a bibliometrics overview // Machine Learning with Applications. 2022.V. 10. P. 100401. https://doi.org/10.1016/j.mlwa.2022.100401
2. Abadal S., Jain A., Guirado R., López-Alonso J., Alarcón E. Computing Graph Neural Networks: a survey from algorithms to accelerators // ACM Computing Surveys (CSUR). 2021. V. 54. N 9. P. 1–38. https://doi.org/10.1145/3477141
3. Ragunathan K., Selvarajah K., Kobti, Z. Link prediction by analyzing common neighbors based subgraphs using convolutional neural network // Frontiers in Artificial Intelligence and Applications. 2020. V. 325. P. 1906-1913. https://doi.org/10.3233/faia200308
4. ZhangM., Chen Y. Link prediction based on graph neural networks // Proc. of the 32nd International Conference on Neural Information Processing Systems. 2018. P. 5171–5181.
5. Epasto A., Lattanzi S., Mirrokni V., Sebe I.O., Taei A., Verma S. Ego-net community mining applied to friend suggestion // Proceedings of the VLDB Endowment. 2015. V. 9. N 4. P. 324–335. https://doi.org/10.14778/2856318.2856327
6. Perozzi B., Al-Rfou R., Skiena S. Deepwalk: online learning of social representations // Proc. of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2014. P. 701–710. https://doi.org/10.1145/2623330.2623732
7. Zhu Z., Zhang Z., Xhonneux L.-P., Tang J. Neural bellman-ford networks: A general graph neural network framework for link prediction // Proc. of the 35th International Conference on Neural Information Processing. 2021. P. 29476–29490.
8. Suri S., Vassilvitskii S. Counting triangles and the curse of the last reducer // Proc. of the 20th International Conference on World Wide Web. 2011. P. 607–614. https://doi.org/10.1145/1963405.1963491
9. Schank T. Algorithmic Aspects of Triangle-Based Network Analysis. Ph.D. dissertation // Universitat Karlsruhe, Fakultat fur Informatik, 2007.
10. ErricaF., Podda M., Bacciu D., Micheli A. A fair comparison of graph neural networks for graph classification // Proc. of the 8th International Conference on Learning Representations. 2020.
11. Gilmer J., Schoenholz S.S., Riley P.F., Vinyals O., Dahl G.E. Neural message passing for quantum chemistry // Proc. of the 34th International Conference on Machine Learning. 2017. V. 70. P. 1263–1272.
12. Hamilton W.L., Ying R., Leskovec J. Inductive representation learning on large graphs // Proc. of the 31st International Conference on Neural Information Processing Systems. 2017. P. 1025–1035.
13. XuD., Ruan Ch., Körpeoglu E., Kumar S., Achan K. Inductive representation learning on temporal graphs//Proc. of the 8th International Conference on Learning Representations. 2020.
14. Velickovic P., Cucurull G., Casanova A., Romero A., Liò P., Bengio Y. Graph attention networks // Proc. of the 6th International Conference on Learning Representations. 2018.
15. Kipf T.N., Welling M. Semi-supervised classification with graph convolutional networks // Proc. of the 5th International Conference on Learning Representations. 2017.
16. Xu K., Hu W., Leskovec J., Jegelka S. How powerful are graph neural networks? // Proc. of the 7th International Conference on Learning Representations. 2019.
17. LemanA.A.,Weisfeiler B. A reduction of a graph to a canonical form and an algebra
arising during this reduction // Nauchno-Technicheskaya Informatsia. Seriya 2. 1968. N 9. P. 12–16.
arising during this reduction // Nauchno-Technicheskaya Informatsia. Seriya 2. 1968. N 9. P. 12–16.
18. Morris C., Ritzert M., Fey M., Hamilton W.L., Lenssen J.E., Rattan G., Grohe M. Weisfeiler and Leman go neural: Higher-order graph neural networks // Proceedings of the AAAI Conference on Artificial Intelligence.2019. V. 33. N 1. P. 4602–4609. https://doi.org/10.1609/aaai.v33i01.33014602
19. Maron H., Ben-Hamu H., Serviansky H., Lipman Y. Provably powerful graph networks // Proc. of the 33rd International Conference on Neural Information Processing Systems. 2019. P. 2156–2167.
20. Morris C., Kriege N.M., Bause F., Kersting K., Mutzel P., Neumann M. Tudataset: A collection of benchmark datasets for learning with graphs // arXiv. 2020. arXiv:2007.08663. https://doi.org/10.48550/arXiv.2007.08663
21. Järvelin K., Kekäläinen J. Cumulated gain-based evaluation of IR techniques // ACM Transactions on Information Systems. 2002. V. 20. N 4. P. 422–446. https://doi.org/10.1145/582415.582418
