Альтернативные эмбеддинги вершин

Алгоритм передачи сообщений в свёрточных графовых сетях - это основной метод построения эмбеддингов (векторов признаков) вершин графа. В этой главе мы изучим альтернативные способы построения эмбеддингов вершин графа, которые основаны на других принципах. Они не являются такими распространёнными, а приводятся больше для полноты изложения.

Задачей, рассматриваемой в этой главе будет построение $D$-мерных эмбеддингов для одного большого графа, состоящего из $N$ вершин. В дальнейшем полученные эмбеддинги могут использоваться для решения любой задачи на графах.

Эмбеддинги на основе случайных блужданий

Рассмотрим методы построения эмбеддингов, основанные на случайном блуждании по графу (random walk), при котором генерируются пути обхода графа, стартуя из случайных вершин и перемещаясь по нему, выбирая случайных соседей. Начальные эмбеддинги инициализируются случайно либо на основе характеристик, известных для каждой вершины графа. В процессе генерации путей обхода эмбеддинги вершин, оказавшиеся недалеко друг от друга, сближаются.

DeepWalk

В методе DeepWalk [1] из каждой вершины $K$ раз запускается процесс случайного блуждания длины $M$. Если трактовать каждую вершину, как слово, то в результате получается $K\cdot N$ предложений длины $M$ каждое.

Для уточнения эмбеддингов по их расположениям на графе в DeepWalk предлагается использовать метод SkipGram модели Word2Vec, в котором по каждому сгенерированному пути на графе скользит окно ширины $2W+1$, и, настраивается модель, пытающаяся по эмбеддингу центральной вершины окна предсказать другие вершины в том же окне аналогично тому, как в оригинальной модели SkipGram строилась языковая модель, предсказывавшая соседние слова окна по центральному слову. Параметрами настроенной модели и будут эмбеддинги вершин графа с учётом его геометрии, поскольку близким вершинам будут соответствовать более близкие эмбеддинги (с более высоким попарным скалярным произведением).

Идеи расширения метода

Обратим внимание, что используя ту же методологию, можно строить эмбеддинги вершин графа используя C-BOW версию модели Word2Vec или другую языковую модель, использующую слова целиком.

Сравнение DeepWalk и алгоритма передачи сообщений

Метод DeepWalk более экономичен по памяти, чем алгоритм передачи сообщений (message passing algorithm) в классических графовых нейросетях, поскольку передача сообщений требует аккумуляции информации со всех соседей каждой вершины, в то время как настройка DeepWalk предполагает переходы лишь по одной случайно выбираемой каждый раз вершине.

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

Node2Vec

Модель Node2Vec [2] также уточняет эмбеддинги вершин графа, учитывая его геометрию. Она использует тот же механизм построения эмбеддингов, что и DeepWalk:

• каждому узлу графа сопоставляется начальный эмбеддинг (случайно или используя известные характеристики);

• из каждого узла генерируются случайные блуждания (random walks) по соседним узлам;

• в сгенерированных блужданиях перебираются всевозможные последовательности узлов фиксированной длины (окна наблюдений);

• в каждом окне наблюдений модель по эмбеддингу центральной вершины в окне настраивается предсказывать другие вершины в том же окне.

Ключевой идеей Node2Vec является наблюдение, что обход вершин графа из заданной вершины может быть устроен по-разному:

• поиск в ширину (breadth-first search, BFS), при котором обход осуществляется в первую очередь по вершинам в окрестности начальной вершины;

• поиск в глубину (depth-first search, DFS), при котором обход осуществляется таким образом, чтобы уходить максимально далеко от первоначальной вершины.

Эти две стратегии проиллюстрированы ниже красным и синим цветом [2]:

Метод Node2Vec использует случайное блуждание 2-го порядка (2-nd order random walk) с гиперпараметрами $p,q>0$, управляющими характером обхода вершин, больше склоняющимся к обходу в глубину или обходу в ширину.

В частности, если только осуществился переход из вершины $t$ в вершину $v$, то вероятность перехода из вершины $v$ в новую вершину $x$ считается по формуле

$$p(v\to x|v,t)=\begin{cases} \gamma \cdot \frac{1}{p} & \text{если }x=t,\\ \gamma \cdot 1 & \text{если }d\left(t,x\right)=1,\\ \gamma \cdot \frac{1}{q} & \text{если }d\left(t,x\right)=2, \end{cases}$$

где $d(t,x)$ - длина минимального пути от вершины $t$ в вершину $x$, а $\gamma$ - нормировочный множитель, чтобы все вероятности суммировались в единицу.

Пример ненормированных вероятностей перехода из вершины $v$ приведён ниже [2]:

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

Как гиперпараметры $p,q$ влияют на характер обхода графа (в глубину/в ширину)?

При малых значениях $p$ обход будет вестись скорее в ширину, поскольку будут частые возвращения в исходную вершину. Малые значения $q$, наоборот, стимулируют поиск в глубину.

Обход в глубину будет выделять сообщества в графе (подмножества сильно связанных друг с другом вершин напрямую или опосредованно) - у таких узлов будут схожие эмбеддинги.

Обход в ширину будет определять структурные роли вершин (structural roles of nodes), т.е. является ли вершина

• хабом (центральным узлом в сообществе, имеющим короткие пути до остальных вершин сообщества);

• связующим узлом (связывает несколько сообществ между собой);

• периферийной вершиной (находящейся на краю графа).

Рассмотрим граф, состоящий из персонажей романа Виктора Гюго "Отверженные". Узлы соединяются ребром, если персонажи взаимодействовали друг с другом в тексте. Если эмбеддинги вершин извлекать методом Node2Vec, а потом кластеризовать и кластер обозначать цветом, то получим результат ниже, где сверху осуществлялся обход в глубину (и были выделены сообщества персонажей), а снизу - обход в ширину (и были выделены структурные роли каждого персонажа) [2]:

Использование автокодировщика

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

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

Для более общих (семантических) и более компактных эмбеддингов к ним можно применить методы снижения размерности, в частности, извлекать их как внутреннее представление посередине автокодировщика, через который пропущена соответствующая строка матрицы смежности, а сам автокодировщик обучен восстанавливать строки матрицы смежности целиком.

Переобучение

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

Предложенный подход используется, например, в статье [3], в которой предложены способы регуляризации для борьбы с переобучением. Архитектура позволяет выдавать эмбеддинг для новых вершин за один проход по автокодировщику, правда, после появления новых вершин сам автокодировщик нужно донастраивать.

Литература

1. Perozzi B., Al-Rfou R., Skiena S. Deepwalk: Online learning of social representations //Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. – 2014. – С. 701-710.
2. Grover A., Leskovec J. node2vec: Scalable feature learning for networks //Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. – 2016. – С. 855-864.
3. Wang D., Cui P., Zhu W. Structural deep network embedding //Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. – 2016. – С. 1225-1234.