ВИКОРИСТАННЯ ВЕКТОРНИХ ПРЕДСТАВЛЕНЬ ГРАФІВ ДЛЯ ПРОГНОЗУВАННЯ ЗВ’ЯЗКІВ У WIKIPEDIA

Автор(и)

  • Roman Vitaliyovych Shaptala Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського», Ukraine https://orcid.org/0000-0002-4367-5775
  • Gennadiy Dmytrovych Kyselev Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського», Ukraine https://orcid.org/0000-0003-2682-3593

DOI:

https://doi.org/10.20998/2079-0023.2019.01.09

Ключові слова:

векторні представлення даних, прогноз зв’язків, Wikipedia2vec, Role2vec, AttentionWalk, Walklets, метод головних компонентів

Анотація

Прогнозування зв'язків є важливою областю дослідження в аналізі мереж та теорії графів, яка намагається відповісти на питання, чи можуть два вузли у графі в майбутньому мати зв’язок. На сьогоднішній день графи повсюдно присутні у нашому житті (соціальні мережі, електротехніка, дороги і т.д.), тому проблема має вирішальне значення для розвитку інтелектуальних додатків. У минулому були запропоновані методи вирішення задачі прогнозування зв’язків за допомогою алгебраїчних формулювань і евристик, однак їхня виразність і переносимість не були задовільними. Останнім часом методи побудови векторних представлень зросли у популярності через їх ефективність і здатність передавати знання між завданнями. Натхненний знаменитим в машинному навчанні та обробці природних мов дослідницьким підходом Word2Vec, ці методи намагаються вивчити розподілене векторне представлення. Після цього бінарний класифікатор, заданий парою таких векторів, прогнозує ймовірність існування зв'язку між закодованими вузлами. У даній роботі ми розглянемо декілька підходів до вбудовування графіків для проблеми прогнозування зв’язків у Wikipedia, а саме Wikipedia2vec, Role2vec, AttentionWalk та Walkets. Прогнозування посилань у контексті Wikipedia – це знаходження сторінок, які пов'язані через певні смислові відносини. Ми оцінюємо точність прогнозування на відокремленому наборі зв’язків і показуємо, який з методів краще знаходить асоціації між сутностями у Вікіпедії. Отримані результати включають якісні (метод головних компонентів для зменшення розмірності та візуалізації) і кількісні (точність) відмінності між запропонованими методами. У рамках висновку наводяться подальші дослідницькі питання, включаючи нові архітектури побудови векторних представлень та створення загальноприйнятого тесту ефективності таких представлень.

Біографії авторів

Roman Vitaliyovych Shaptala, Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського»

аспірант кафедри системного проектування Навчально-наукового комплексу «Інститут прикладного системного аналізу», Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського»

Gennadiy Dmytrovych Kyselev, Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського»

кандидат технічних наук, старший науковий співробітник, доцент, заступник завідувача кафедри системного проектування Навчально-наукового комплексу «Інститут прикладного системного аналізу», Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського»

Посилання

Martínez V., Berzal F., Cubero J. C. A survey of link prediction in complex networks. ACM Computing Surveys (CSUR). 2017, vol. 49, no. 4, article 69.

Minervini P., Costabello L., Muñoz E., Nováček V., Vandenbussche P. Y. Regularizing knowledge graph embeddings via equivalence and inversion axioms. Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Cham, Springer Publ., 2017, vol. 10534, pp. 668–683.

Dong X., Gabrilovich E., Heitz G., Horn W., Lao N., Murphy K., Strohmann T., Sun S., Zhang W. Knowledge vault: A web-scale approach to probabilistic knowledge fusion. Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. New York, ACM Publ., 2014, pp. 601–610.

Bollacker K., Evans C., Paritosh P., Sturge T., Taylor J. Freebase: a collaboratively created graph database for structuring human knowledge. Proceedings of the 2008 ACM SIGMOD international conference on Management of data. Vancouver, ACM Publ., 2008, pp. 1247–1250.

Auer S., Bizer C., Kobilarov G., Lehmann J., Cyganiak R., Ives Z. Dbpedia: A nucleus for a web of open data. The semantic web. Berlin, Heidelberg, Springer Publ., 2007, pp. 722–735.

Goyal P., Ferrara E. Graph embedding techniques, applications, and performance: A survey. Knowledge-Based Systems. 2018, vol. 151, pp.78–94.

Ahmed N. K., Rossi R., Lee J. B., Willke T. L., Zhou R., Kong X., Eldardiry H. Learning role-based graph embeddings. StarAI workshop, IJCAI 2018. arXiv preprint arXiv:1802.02896. 2018.

Abu-El-Haija S., Perozzi B., Al-Rfou R., Alemi A. A. Watch your step: Learning node embeddings via graph attention. Advances in Neural Information Processing Systems. Vol. 31. Curran Associates, Inc. Publ., 2018, pp. 9180–9190.

Perozzi B., Kulkarni V., Chen H., Skiena S. Don't Walk, Skip! Online Learning of Multi-scale Network Embeddings. Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. New York, ACM Publ., 2017, pp. 258–265.

Yamada I., Asai A., Shindo H., Takeda H., Takefuji Y. Wikipedia2Vec: An Optimized Implementation for Learning Embeddings from Wikipedia. arXiv preprint arXiv:1812.06280. 2018.

Mikolov T., Sutskever I., Chen K., Corrado G. S., Dean J. Distributed representations of words and phrases and their compositionality. Advances in neural information processing systems. Vol. 2. Curran Associates, Inc. Publ., 2013, pp. 3111–3119.

Kingma D. P., Ba J. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980. 2014.

West R., Pineau J., Precup D. June. Wikispeedia: An online game for inferring semantic distances between concepts. Twenty-First International Joint Conference on Artificial Intelligence. Pasadena, 2009, pp. 1598–1603.

##submission.downloads##

Як цитувати

Shaptala, R. V., & Kyselev, G. D. (2019). ВИКОРИСТАННЯ ВЕКТОРНИХ ПРЕДСТАВЛЕНЬ ГРАФІВ ДЛЯ ПРОГНОЗУВАННЯ ЗВ’ЯЗКІВ У WIKIPEDIA. Вісник Національного технічного університету «ХПІ». Серія: Системний аналiз, управління та iнформацiйнi технологiї, (1), 48–52. https://doi.org/10.20998/2079-0023.2019.01.09

Номер

№ 1 (2019)

Розділ

ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ

Ліцензія

Авторське право (c) 2019 Вісник Національного технічного університету «ХПІ». Серія: Системний аналiз, управління та iнформацiйнi технологiї

Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:

  • Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.
  • Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.
  • Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).