Cвёрточные графовые сети

Cвёрточные графовые сети (graph convolutional networks) реализуют пересчёт исходных признаковых описаний $\mathbf{x}_i$ соответствующих вершин $v_i$, учитывая контекст, то есть признаковые описания соседних вершин. Пересчёт производится много раз, начиная с $\mathbf{h}^0_i=\mathbf{x}_i$ и получая $\mathbf{h}^1_i,\mathbf{h}^2_i,...\mathbf{h}^K_i$ для каждой вершины $v_i$.

Рассмотрим свёртку, действующую на однослойном изображении (чёрно-белом), в ней пересчёт производился по формуле

$$h_{i}^{k+1}=f\left(\sum_{j\in\text{patch}(i)}w_{j}h_{j}^{k}+b\right),$$

где $b$ - смещение, а $\{w_j\}_j$ - веса для соседних пикселей.

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

$$h_{i}^{k+1}=f\left(w_{0}z_{j}+w_{1}\sum_{j\in\mathcal{N}(i)}h_{j}^{k}+b\right),$$

где $\mathcal{N}(i)$ - множество индексов соседних вершин с вершиной $i$ (соединённых с ней ребром).

Поскольку в графах каждой вершине сопоставляется не одно число, а вектор значений (эмбеддинг вершины), то пересчёт старых эмбеддингов $\mathbf{h}^k_m$ в новые $\mathbf{h}^{k+1}_m$ производится по формулам:

$$\begin{aligned}\mathbf{z}_{n}^{k} & =\text{Aggregate}\left(\left\{ \mathbf{h}_{m}^{k}\right\} _{m\in\mathcal{N}(n)}\right),\\ \mathbf{h}_{n}^{k+1} & =\text{Update}\left(\mathbf{h}_{n}^{k}, \mathbf{z}_{n}^{l}\right), \end{aligned}$$

где

• $\text{Aggregate}\left(\cdot\right)$ - функция, агрегирующая информацию с соседних вершин,

• $\text{Update}\left(\cdot\right)$ - функция, обновляющая информацию о текущей вершине, используя её информацию с предыдущей итерации и агрегированную информацию о её соседях.

$\text{Aggregate}\left(\cdot\right)$ должна быть определена для любого числа соседей и не должна зависеть от порядка их обхода. Применение Argegate, а затем Update операции представляет собой одну итерацию алгоритма обмена сообщениями (message passing neural network [1]), который использует несколько итераций, а начальные значения для вершин определяются их начальными эмбеддингами: $\mathbf{h}^0_n = \mathbf{x}_n, n=1,2,...N.$ Если $\mathbf{x}_n$ не заданы, то их можно инициализировать one-hot закодированным значением числа соседей узла или геометрическими характеристиками вершин (число соседей 1-го, 2-го порядка и др.)

Алгоритм передачи сообщений представлен ниже:

ВХОД:

• ненаправленный граф $G=(V,E)$

• начальные эмбеддинги вершин $\{\mathbf{h}^0_n\}$

• функции $\text{Aggregate}\left(\cdot\right)$ и $\text{Update}\left(\cdot\right)$

АЛГОРИТМ:

для $k=1,2,...K$:

• $\mathbf{z}_{n}^{k} =\text{Aggregate}\left(\left\{ \mathbf{h}_{m}^{k}\right\} _{m\in\mathcal{N}(n)}\right)$

• $\mathbf{h}_{n}^{k+1} =\text{Update}\left(\mathbf{h}_{n}^{k}, \mathbf{z}_{n}^{k}\right)$

ВЫХОД:

• итоговые эмбеддинги вершин $\mathbf{h}^K_n,\; n=1,2,...N.$

Применение $K$ итераций алгоритма обмена сообщениями аналогично применению $K$ свёрточных слоёв при обработке изображений. Функции Argegate и Update имеют свои настраиваемые параметры, причем в общем случае они свои на каждой итерации алгоритма.

Каждая итерация алгоритма передачи сообщений - это слой глубокой графовой сети.

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

Нулевая итерация:

Первая итерация:

Вторая итерация:

Третья итерация:

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

Агрегирующая функция

Функцию Aggregate можно определять по-разному, лишь бы она была определена для любого числа соседей и не зависела от их порядка. Самый простой вариант - через сумму эмбеддингов:

$$\text{Aggregate}\left(\cdot\right)=\sum_{m\in\mathcal{N}(n)}\mathbf{h}_{m}^{k},$$

где $\mathcal{N}(n)$ - множество индексов вершин соединённых ребром с вершиной $n$.

Также можно использовать усреднение:

$$\text{Aggregate}\left(\cdot\right)=\frac{1}{\left|\mathcal{N}(n)\right|}\sum_{m\in\mathcal{N}(n)}\mathbf{h}_{m}^{k}$$

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

Также можно усреднять, учитывая различия в числе соседних узлов у каждого соседа [2]:

$$\text{Aggregate}\left(\cdot\right)=\frac{1}{\sqrt{\left|\mathcal{N}(n)\right|\cdot\left|\mathcal{N}(m)\right|}}\sum_{m\in\mathcal{N}(n)}\mathbf{h}_{m}^{k}$$

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

$$\text{Aggregate}\left(\cdot\right)=\text{maximum}\left(\left\{ \mathbf{h}_{m}^{k}\right\} _{m\in\mathcal{N}(n)}\right)$$

Наиболее общим видом усреднения, способным моделировать любую дифференцируемую зависимость, инвариантную к перенумерации вершин, является использование двух многослойных персептронов (multi-layer perceptron, MLP) со своими настраиваемыми векторами параметров $\mathbf{w}$ и $\mathbf{v}$ [3]:

$$\text{Aggregate}\left(\cdot\right)=\text{MLP}_{\mathbf{w}}\left(\sum_{m\in\mathcal{N}(n)}\text{MLP}_{\mathbf{v}}\left(\mathbf{h}_{m}^{k}\right)\right)$$

В последней формуле вместо суммы можно использовать другие перечисленные выше виды агрегации.

Агрегация со вниманием

Можно использовать механизм внимания (attention mechanism) при агрегации узлов [4] аналогично тому, как он использовался в рекуррентных сетях.

Для этого нужно произвести следующие действия:

1. Вычисляется внимание, с которым узел $v_n$ должен смотреть на каждого своего соседа $v_m$, используя некоторую функцию $g(\cdot)$:

   $$s_{nm}=g(\mathbf{h}^k_n,\mathbf{h}^k_m)$$

2. Коэффициенты внимания пропускаются через SoftMax преобразование:

   $$\left\{ a_{nm}\right\}_{m\in\mathcal{N}(n)}=\text{SoftMax}\left(\left\{ s_{nm}\right\}_{m\in\mathcal{N}(n)}\right)$$

3. Агрегация информации с узлов осуществляется пропорционально найденному вниманию:

   $$\mathbf{z}_{n}^{k}=\sum_{n\in\mathcal{N}(n)}a_{nm}\mathbf{h}_{m}^{k}$$

Например, внимание может вычисляться через билинейную форму с настраиваемой матрицей $W\in\mathbb{R}^{D\times D}$:

$$a_{mn}=\frac{\text{exp}\left(\mathbf{h}_{n}^{T}W\mathbf{h}_{m}\right)}{\sum_{m'\in\mathcal{N}(n)}\text{exp}\left(\mathbf{h}_{n}^{T}W\mathbf{h}_{m'}\right)}$$

В более общем случае внимание может вычисляться через многослойный персептрон:

$$a_{mn}=\frac{\text{exp}\left(\text{MLP}\left(\mathbf{h}_{n},\mathbf{h}_{m}\right)\right)}{\sum_{m'\in\mathcal{N}(n)}\text{exp}\left(\text{MLP}\left(\mathbf{h}_{n},\mathbf{h}_{m'}\right)\right)}$$

Аналогично тому, как это сделано в трансформере, можно применять несколько головок внимания со своими весами, конкатенировать полученные результаты и приводить результат к исходному $D$-мерному пространству эмбеддингов, используя линейный слой.

Обновляющая функция

Типичным способом определения функции Update является использование одного линейного слоя:

$$\mathbf{h}^{k+1}_n=\text{Update}\left(\mathbf{h}_{n}^{k},\mathbf{z}_{n}^{k}\right)=f\left(W\mathbf{h}^{k}+V\mathbf{z}_{n}^{k}+\mathbf{b}\right),$$

где $f(\cdot)$ - функция активации, применяемая поэлементно. Популярное способ передачи сообщений - агрегировать суммированием и использовать одну и ту же матрицу весов для целевого узла и его соседей:

$$\mathbf{h}_{n}^{k+1}=f\left(W\sum_{m\in\mathcal{N}(n)\cup n}\mathbf{h}_{m}^{k}+\mathbf{b}\right)$$

Чтобы облегчить настройку параметров сети, а также частично избавиться от сглаживания эмбеддингов (когда они становятся слишком похожими за счёт повторного усреднения по ним) можно использовать в качестве выхода сумму преобразования с исходным входом (остаточный блок), как было в модели ResNet:

$$\mathbf{h}_{n}^{k+1}=\text{Update}\left(\mathbf{h}_{n}^{k},\mathbf{z}_{n}^{k}\right)+\mathbf{h}_{n}^{k}$$

Альтернативно можно в качестве итогового представления каждой вершины использовать конкатенацию её представлений на всех итерациях передачи сообщений:

$$\mathbf{h}^{\text{final}}_n = [\mathbf{h}^1_n; \mathbf{h}^1_n; ... \mathbf{h}^K_n]$$

Тогда, даже при сглаживании на последних итерациях, эмбеддинги вершин всё равно будут существенно различаться за счёт учёта эмбеддингов с более ранних итераций.

С учётом признаков с разных слоёв сети мы уже сталкивались в модели DenseNet.

Инвариантность к перенумерациям

В матричном виде операции Aggregate и Update можно описать цепочкой преобразований

$$\begin{aligned}H^{1} & =F\left(X,A,W^{1}\right)\\ H^{2} & =F\left(H^{1},A,W^{2}\right)\\ & \cdots\\ H^{K} & =F\left(H^{K},A,W^{K}\right) \end{aligned}$$

где $A$ - матрица смежности вершин, $H^i=[h^i_1,...h^i_N]\in\mathbb{R}^{D\times N}$ - матрица, столбцы которой являются внутренними представлениями узлов на $i$-м шаге алгоритма обмена сообщениями, а $W^i$ - матрица настраиваемых весов на $i$-м шаге.

На каждом шаге алгоритма передачи сообщений преобразование $F(\cdot)$ должно обладать эквивариантностью к перенумерации узлов (equivariance) - если их задать в другом порядке, то его действие останется тем же, что математически записывается в виде

$$H^{k}P = F\left(H^{k}P,\;P^T\cdot A\cdot P,\;W^{k}\right)$$

Задача

Запишите в матричном виде описанные выше операции Aggregate & Update. Для операций усреднения вам понадобится матрица степеней. Для каждой записи в матричном виде докажите, что для неё выполнено свойство эквивариантности. Для этого вам пригодятся формулы пересчёта матрицы данных, матрицы смежности и матрицы, обратной к матрице степеней при перенумерации вершин графа.

Учёт эмбеддингов рёбер и всего графа

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

Обобщённый алгоритм передачи сообщений:

ВХОД:

• ненаправленный граф $G=(V,E)$

• начальные эмбеддинги вершин $\{\mathbf{h}^0_n\}$

• начальные эмбеддинги рёбер $\{\mathbf{e}^0_{nm}\}$

• начальный эмбеддинг графа $\mathbf{g}^0$

• функции $\text{Aggregate}\left(\cdot\right)$ и $\text{Update}\left(\cdot\right)$

АЛГОРИТМ:

для $k=1,2,...K$:

• $\mathbf{e}_{nm}^{k+1}=\text{Update}_{\text{edge}}\left(\mathbf{e}_{nm}^{k},\mathbf{h}_{n}^{k},\mathbf{h}_{m}^{k},\mathbf{g}^{k}\right)$

• $\mathbf{z}_{n}^{k+1}=\text{Aggregate}_{\text{node}}\left(\left\{ \mathbf{e}_{nm}^{k}\right\} _{m\in\mathcal{N}(n)}\right)$

• $\mathbf{h}_{nm}^{k+1}=\text{Update}_{\text{node}}\left(\mathbf{h}_{n}^{k+1},\mathbf{z}_{n}^{k+1},\mathbf{g}^{k}\right)$

• $\mathbf{g}_{n}^{k+1}=\text{Update}\left(\mathbf{g}^{k},\left\{ \mathbf{h}_{n}^{k+1}\right\} ,\left\{ \mathbf{e}_{nm}^{k+1}\right\} \right)$

ВЫХОД:

• итоговые эмбеддинги $\left\{ \mathbf{h}_{n}^{K}\right\} ,\left\{ \mathbf{e}_{nm}^{K}\right\} ,\mathbf{g}^{K}$

Как видим, на каждой итерации

1. вначале обновляются эмбеддинги каждого ребра по эмбеддингам его вершин;

2. затем обновляется эмбеддинг контекста каждой вершины по эмбеддингам связанных с ним рёбер;

3. потом происходит обновление эмбеддинга вершины по её контексту;

4. наконец обновляется эмбеддинг всего графа.

Учёт эмбеддингов рёбер позволяет решать задачи на рёбрах (например, предсказывать тип связи), а эмбеддинг всего графа может учитываться при регрессии/классификации всего графа целиком.

---

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

Литература

1. Gilmer J. et al. Neural message passing for quantum chemistry //International conference on machine learning. – PMLR, 2017. – С. 1263-1272.
2. Kipf T. N., Welling M. Semi-supervised classification with graph convolutional networks //arXiv preprint arXiv:1609.02907. – 2016.
3. Zaheer M. et al. Deep sets //Advances in neural information processing systems. – 2017. – Т. 30.
4. Veličković P. et al. Graph attention networks //arXiv preprint arXiv:1710.10903. – 2017.