Структурные вложения вершин графов на основе анонимных случайных блужданий

Построение вложений графов представляет собой сложную задачу эффективного представления информации о структуре графов в виде векторов в пространстве небольшой размерности, которые будут использоваться в качестве входных данных для решения последующих задач. Мы анализируем задачу построения вложений графа в структурной перспективе; то есть, чтобы учитываать в векторах-вложениях вершины локальную структуру подграфа, окружающего каждый узел. На практике такие вложения полезны для описания реальных сетевых наборов данных, в которых отсутствует дополнительная информация и с четко определенными структурными идентификаторами узлов. Один из главных недостатков, с которыми сталкиваются большинство предлагаемых в литературе моделей, особенно семейство моделей на основе случайных блужданий, заключается в создании вложений, основанных не на структуре, а на гомофилии, и также в их недостаточной устойчивости шуму в данных. Мы предлагаем и анализируем различные подходы к построениею вложений при обучении без учителя, основанные на статистике анонимных блужданий, которые являются теоретически обоснованным механизмом учета структуры графа. Мы успешно имплементировали и сравнили предложенные нами модели с современными моделями на основе случайных блужданий, используя стандартные наборы сетевых данных для задач классификации узлов. Эксперименты показывают, что наша модель значительно превосходит другие подходы. Кроме того, мы осуществили анализ устойчивости полученных вложений к шуму.