[Семидневная проверка] - 1 node2vec алгоритма встраивания графа

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

К методам, основанным на случайном блуждании, в основном относятся DeepWalk и Node2vec. DeepWalk использует случайные блуждания для получения последовательностей узлов, обрабатывает полученные последовательности как предложения и использует word2vec для изучения характеристик узлов, так что локальная структурная информация узлов в графе может быть представлена векторами. Когда две точки имеют на графе больше общих соседей, расстояние между соответствующими векторами становится меньше.Node2vec поддерживает близость высокого порядка между узлами, максимизируя вероятность появления узлов в последовательности, полученной случайным блужданием, балансируя поиск в глубину и поиск в ширину.Эта статья в основном представляет статью, в которой предлагается алгоритм Node2vec.

задний план

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

смысл

Случайная прогулка

к отправной точке $u$ , который имитирует фиксированную длину $l$ Случайное блуждание , $c_i$ первый $i$ точки ( $c_0=u$ ), $c_i$ Генерируется согласно следующему распределению:

$\pi_{vx}$ да $v$ и $x$ Не существует стандартизированной вероятности перехода между $Z$ является нормированной константой.

искать предвзятость $\alpha$

Самый простой способ - иметь смещение случайного блуждания на основе весов ребер. $w_{vx}$ получить, то есть $\pi_{vx}=w_{vx}$

Автор использует два параметра $p$ и $q$ Случайное блуждание второго порядка определяется:И определяет распределение вероятностей, которое представляет вероятность перехода узла к другим соседям, p представляет вероятность возврата, а q представляет вероятность входа и выхода. Когда p и q равны 1, способ ходьбы эквивалентен случайному блужданию в DeepWalk.

Поддельный код

способствовать