Обзор Node2vec: Scalable Feature Learning for Networks

Статья

Вводные

Цель работы получать эмбеддинги вершин графа.

Авторы вдохновлялись SkipGram, поэтому работает по принципу Word2Vec.

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

Принцип работы

• Случайно выбираем центральную вершину v из V
• Сэмплируем вершины W
• Максимизируем правдоподобие соседних вершин W
• Минимизируем правдоподобие несоседних вершин V\W

Лосс

Здесь V - все вершины, а W - соседние вершины.

Как сэмплируем

Генерируем random walk - случайный обход по графу. В результате имеем множестве вершин W, которые считаем соседними вершинами v.

Есть принципиально 2 разных подхода выбирать вершины: BFS и DFS.

Breadth-first Sampling (BFS) - обходим в первую очередь непосредственных соседей центральной вершины.

Depth-first Sampling (DFS) - обходим вершины с нарастанием длины пути до центральной вершины.

Интерпретируемость фичей

BFS выучивает структурные признаки вершин графа - то есть улавливает только локальный контекст, например, группирует в один кластер вершины-мосты, в то время как DFS выучивает более глобальные признаки и больше подходит для, например, поиска сообществ в графе.

Авторы предлагают обощить BFS и DFS в один фреймворк, введя в random walk 2 гиперпараметра p и q

• p - параметр, который отвечает за возвращение, то есть перепосетить вершину вновь. Увеличивая p ( > max(q, 1)) мы ближе к DFS, в противном случае BFS.
• q - in-out параметр, чем он меньше, тем более дальние вершины мы будем посещать вероятнее.

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

Обучается все с помощью обычного SGD, берем любой оптимайзер, обучаем с батчами, совместимо с pytorch в современных реализациях, можем учить на GPU.

Авторы учат фичи вершин, а потом используют их для multi-label классификации и link prediction задачи.

Качество выше, чем у других работ.

Выводы

Как бейзлайн можно брать спектральную кластеризацию, но node2vec классно работает, масштабируется, поддерживает батч обучение на GPU.