Здравствуйте! Сегодня мы обсудим довольно сложную тему — графовые сверточные сети, или GCN. Мы разберём все её ключевые принципы и постараемся понять, как они применяются для анализа графовых структур. Ну и...приступ!

Введение

GCN (Graph Convolutional Networks) — это масштабируемый подход к полуконтролируемому обучению, который применяется к данным, представленным в виде графов. Он основывается на принципах сверточных нейронных сетей (CNN).

Выбор сверточной архитектуры в GCN объясняется тем, что она предлагает локализованное приближение первого порядка спектральных сверток для графов. Локализованное приближение означает, что мы рассматриваем не всю структуру графовой сети, а лишь небольшую группу узлов и связей. Первый порядок указывает на размер этого локального приближения: поскольку это первый порядок, то мы будем изучать только ближайших соседей выбранного узла. Спектральная свертка — это более общее понятие, которое охватывает методы, использующие спектр графа для извлечения информации. Мы вернемся к этому более подробно позже.

Метод

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

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

Формула состоит из двух частей:

Контролируемая потеря (оценивает, насколько хорошо модель предсказывает метки для известных узлов):
$\mathcal{L}0=-\sum{i\in Y}{y_i\log{\left(p_i\right)}}$
где Y — множество узлов с известными метками, — конкретная истинная метка узла, а — предсказанная вероятность для этой метки. 𝜆 — весовой коэффициент.
Регуляризационная потеря (улучшает обобщающую способность):
$A_{ij}\ ‖f(X_i )-f(X_j )‖^2$
где $𝐴_{𝑖𝑗}$ — элемент матрицы смежности графа, который стремится к 1, если узлы i и j связаны, и к 0, если нет. и — векторные представления (или "эмбеддинги") узлов i и j.

Если два узла связаны (то есть $𝐴_{𝑖𝑗}$ = 1), мы хотим уменьшить разницу между их представлениями f(Xi) и f(Xj). Это означает, что если узлы близки в графе, их предсказания должны быть похожи.

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

Ускоренное вычисление свертки

В этом разделе мы подробно рассмотрим теоретическую основу конкретной модели GCN. Первым шагом станет изучение правила распространения информации между слоями.

Здесь $\widetilde{A}=A+I_N$ , где 𝐴 – матрица смежности неориентированного графа (графа без направления), а – единичная матрица. Зачем мы добавляем эту 𝐴 в нашу формулу?

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

Теперь давайте рассмотрим, что такое ${\widetilde{D}}^{-\frac{1}{2}}$ . Это $\widetilde{D_{ii}}=\mathrm{\Sigma}j\widetilde{A{ij}}$ , которое показывает, сколько ребер выходит из узла i в графе. Но почему ${\widetilde{D}}^{-\frac{1}{2}}$ ? Дело в том, что узлы в графах могут иметь разное количество связей. Без нормализации, узлы с большим числом связей будут значительно влиять на результаты, и модель может стать нестабильной.

Перейдем к – это обучаемая матрица весов, где 𝑙 обозначает слой (как в сверточной сети). 𝜎 – наша функция активации (Relu, sigmoid, tanh и т.п.). И наконец, представляет собой матрицу признаков узлов на 𝑙 слое нейронной сети GCN.

Spectral Graph Convolution или спектральные графовые свертки

Для начала давайте по быстрому разберемся в спектральной свертки. Смысл спектральной свертки заключается в том, что мы хотим применять некоторую операцию фильтрации (свёртки) к сигналам на графе. Этот сигнал может представлять разные данные (например, активность людей в социальных сетях). Спектральная свертка позволяет нам изучать сигналы, используя свойства графа (структура и его связи).
Теперь рассмотрим более углубленно, спектральные графовые свертки (позволяют анализировать графы через из частоты(на сколько сильно связаны узлы)), определенные как умножение сигнала $x\in R^N$ (скаляр для каждой вершины) с фильтром $g_0=diag{\left(\theta\right)}$ (тот же фильтр, что и в сверточной сети(окошко 3х3), но только здесь фильтр состоит из диагональной матрицы), параметризованным $\theta\in R^N$ (содержат информацию о том, как следует усиливать или ослаблять значения сигнала на каждой из N вершин графа.) в диапазоне Фурье(позволяет выделить частотные компоненты сигнала, что облегчает анализ его свойств) , т.е.:

где U — это матрица собственных векторов нормализованного лапласиана графа ( $L=I_N-D^{-1/2}AD^{-1/2}=U\Lambda U^T$ ) , с диагональной матрицей собственных значений $\Lambda$ и — преобразованием Фурье графа сигнала x. Мы можем рассматривать как функцию собственных значений (Лапласиан графа ( , где - — диагональная матрица степеней, где каждый элемент $D_{ii}$ равен степени вершины (количеству рёбер, соединяющих её с другими вершинами)) т.е. $(g_\theta\left(\Lambda\right)$ . Однако использование этой формулы требует больших вычислительных ресурсов, поэтому был предложен другой вариант.

Здесь мы предлагает использовать многочлены Чебышева для апроксимации (предсказание в диапазоне) функции фильтра где $\widetilde{\mathrm{\Lambda}}$ это пересчитанное $\widetilde{\mathrm{\Lambda}}=(\frac{2}{\lambda_{max}}\Lambda-I_N)$ . И опять же где $\lambda_{max}$ обозначает наибольший собственный вектор .

$\theta^\prime\in R^K$ теперь является вектором коэффициентов Чебышёва. Полиномы Чебышёва рекурсивно определяются как. $T_k\left(x\right)=2xT_{k-1}\left(x\right)-T_{k-2}\left(x\right)$ при $T_0\left(x\right)=1$ и $T_1\left(x\right)=x$ . Теперь не много подравняем формулу для более точного определения и получим.

В общем все тоже самое только мы заменяем $\widetilde{\mathrm{\Lambda}}$ на $\widetilde{L}$ , но нахождение L прежнее $(\widetilde{L})=(\frac{2}{\lambda_{max}}L-I_N)$ . Кстати это максимальное расстояние шагов от центрального узла.

Хорошо, давайте снова упростим наше уравнения до такого вида:

$g_\theta\ast x\approx\theta_0^\prime x+\theta_1^\prime\left(L-I_N\right)x=\theta_0^\prime x-\theta_1^\prime D^{-1/2}AD^{-1/2}x$

Где мы будем приближать $\lambda_{max} ≈ 2$ (параметр являющимся компромиссом между сложностью модели и стабильностью её обучения). $\theta_0^\prime\$ и $\theta_1^\prime\$ будут свободными параметрами. Про все остальное уже говорили.

Однако если у вас будет проблема с переобучением или может вы захотите ускорить процесс минимазацией числа операций. То можем просто убрать один свободный параметр, что приведет к:

$g_\theta\ast x\approx\theta\left(I_N+D^{-\frac{1}{2}}AD^{-\frac{1}{2}}\right)x$

Классификация узлов с неполным контролем

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

Примеры:

В этом разделе мы рассмотрим двухслойную GCN для полу-контролируемого классифицирования узлов на графе с симметричной матрицей смежности (матрица, которая удовлетворяет условию (, где A может быть двоичной или взвешенной( матрица состоящий из 0 и 1 или матрица со любыми значениями). Сначала мы вычисляем ( $\hat{A}=D^{-\frac{1}{2}}AD^{-\frac{1}{2}})$ (используется для нормализации матрицы смежности графа) на этапе предварительной обработки. Затем наша модель принимает простую форму:

$Z=f\left(X,A\right)=\mathrm{softmax}\left(\hat{A}\mathrm{ReLU} \left(\hat{X}W^{\left(0\right)}\right)W^{\left(1\right)}\right)$

Здесь $(W^{\left(0\right)}\in R^{C\times H})$ — это матрица весов для скрытого слоя, которая связывает входные данные с скрытыми нейронами и имеет ( $\ H\$ ) признаковых карт. $(W^{\left(1\right)}\in R^{H\times F})$ — это матрица весов, связывающая скрытые нейроны с выходами. Функция активации softmax, определяемая как: $\mathrm{softmax}\left(x_i\right)=\frac{1}{Z}\exp{\left(x_i\right)}$ где $z=\sum_{i}\ \exp{\left(x_i\right)}$ , применяется по строкам(на выходном слое выводит вектор вероятностей сумма которых не превышает 1).
(То есть этим всем мы определяем выходной слой, что он будет выводить).

И на последок рассмотрим как мы будем оценивать нашу ошибку для полу-контролируемой многоклассовой классификации. А будем мы ее оценивать с помощью cross-entropy по всем маркированным примерам:

Где $(Y_{lf})$ — это индикаторная переменная, указывающая на наличие метки для узла и класса f . $(Z_{lf})$ — это предсказанная вероятность того, что узел принадлежит классу f . А $(\mathcal{Y}_\mathcal{L})$ — множество индексов узлов, которые имеют метки.

Ну и сама сверточная графовая сеть (GCN)

Вот как будет выглядеть схема многослойной графовой сверточной сети (GCN). На рисунке (a) слева изображен входной слой с C входными каналами, а справа — F признаковыми картами на выходном слое, а также скрытые слои.

В (b) представлена визуализация активаций скрытых слоев, созданная с помощью t-SNE на основе данных Cora. Для классификации документов, отличающихся по цвету, используются 5% меток.

На этом всё! Надеюсь, мне удалось объяснить, что такое GCN, простыми словами. Если у вас остались вопросы, пишите в комментариях, и я с радостью отвечу на них.

Под капотом GCN