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

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

Roman Vitaliyovych Shaptala, Gennadiy Dmytrovych Kyselev

Анотація


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

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


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

Повний текст:

PDF (English)

Посилання


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.