Cвёрточные графовые сети
Cвёрточные графовые сети (graph convolutional networks) реализуют пересчёт исходных признаковых описаний соответствующих вершин , учитывая контекст, то есть признаковые описания соседних вершин. Пересчёт производится много раз, начиная с и получая для каждой вершины .
Рассмотрим свёртку, действующую на однослойном (чёрно-белом) изображении:
где - смещение, а - веса для соседних пикселей.
Специфика свёртки на графах:
-
используется информация только с непосредственных соседних вершин;
-
нет понятий верхнего, нижнего, правого и левого соседей.
Граф может быть повёрнут, но это будет тот же самый граф!
Пересчёт старых эмбеддингов вершин графа в новые производится по формулам:
где
-
- функция, агрегирующая информацию с соседних вершин;
-
- функция, обновляющая информацию о текущей вершине, используя её информацию с предыдущей итерации и агрегированную информацию о её соседях.
Функция должна быть определена для любого числа соседей и не должна зависеть от порядка их обхода, чтобы обеспечить свойство инвариантности к перенумерации вершин. Применение операций Aggregate, а затем Update представляет собой одну итерацию алгоритма обмена сообщениями (message passing neural network [1]), который использует несколько итераций, а начальные значения для вершин определяются их начальными эмбеддингами: Если не заданы, то их можно инициализировать one-hot закодированным значением числа соседей узла или геометрическими характеристиками вершин (число соседей 1-го, 2-го порядка, меры центральности вершин на графе и т. д.)
Алгоритм передачи сообщений представлен ниже:
ВХОД:
ненаправленный граф
начальные эмбеддинги вершин
функции и
АЛГОРИТМ:
для :
ВЫХОД:
- итоговые эмбеддинги вершин
Применение итераций алгоритма обмена сообщениями аналогично применению свёрточных слоёв при обработке изображений. Функции Aggregate и Update имеют свои настраиваемые параметры, причём в общем случае они свои на каждой итерации алгоритма.
Каждая итерация алгоритма передачи сообщений - это слой глубокой графовой сети.
Обратим внимание, что каждая итерация алгоритма повышает область видимости (receptive field) результирующего эмбеддинга на один переход по графу аналогично тому, как его повышает последовательное применение свёрток. Это проиллюстрировано ниже для отдельной вершины.
Нулевая итерация (начальный эмбеддинг):
Первая итерация:
Вторая итерация:
Третья итерация:
Если граф имеет недостаточную связность, то сообщения между вершинами распространяются медленно. В этом случае связность можно искусственно повысить, добавив в граф дополнительную вершину, связанную со всеми остальными (super-node).
Агрегирующая функция
Функцию Aggregate можно определять по-разному, лишь бы она была определена для любого числа соседей и не зависела от порядка их обхода. Самый простой вариант - сумма эмбеддингов:
где - множество индексов вершин, соединённых ребром с вершиной .
Также можно использовать усреднение: