Случайные блуждания использовались для захвата топологических характеристик (то есть паттернов ребер) графов со времен DeepWalk. Это делается для получения вложения графов из выборок, взятых во время случайных блужданий. Вложения представляют собой набор многомерных функций на каждом из узлов, S = {f (1),…, f (i),…, f (N)}. Типичное количество размеров заделки находится в диапазоне [100,1000].

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

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

Мы сравнили наш подход с современным алгоритмом построения графиков GraphGAN и заметили, что наш подход требует в 3-4 раза меньшего времени обучения, при этом значительно превосходит GraphGAN и другие современные технологии. передовые методы предсказательной точности. Результаты показывают, что теоретическая модель лучше отражает топологию графа, чем GraphGAN.

Прогнозирование количества ссылок

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

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

Эксперименты

В разреженных сетях наше теоретическое вложение принимает замкнутую форму. Ниже мы покажем с этим приближением, что наш подход превосходит GraphGAN на двух реальных наборах данных.

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

Наборы данных

Мы протестировали набор данных в частной социальной сети и в сети цитирования по астрофизике. Набор данных социальной сети содержит около 134 000 узлов и 357 000 ребер. Сеть цитирования астрофизиков намного плотнее, она состоит из 17 000 узлов и 355 000 ребер. Визуализация нашего частного набора данных показана ниже.

Чтобы сформировать набор данных для обучения и проверки, мы скрываем 10% ребер на графике как положительные образцы и генерируем несвязанные пары как отрицательные образцы для набора проверки. Остальные 90% ребер используются для тренировки.

Результаты

На рисунке ниже показана зависимость точности проверки от времени, затраченного на эксперимент в социальной сети.

В социальной сети наш подход обеспечивает ту же точность проверки, что и модель GraphGAN, в 3-4 раза быстрее из-за того, что наш метод генерации подграфов полностью векторизуем. Мы использовали код, предоставленный авторами для GraphGAN.

Ниже представлена ​​таблица, в которой записаны результаты прогнозирования ссылок с использованием самых современных алгоритмов в сети цитирования астрофизиков. Мало того, что наш подход намного быстрее, чем GraphGAN, мы со значительным отрывом превосходим все современные результаты.

Вывод

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