Здравствуйте! Сегодня мы обсудим довольно сложную тему — графовые сверточные сети, или GCN. Мы разберём все её ключевые принципы и постараемся понять, как они применяются для анализа графовых структур. Ну и...приступ!
Введение
GCN (Graph Convolutional Networks) — это масштабируемый подход к полуконтролируемому обучению, который применяется к данным, представленным в виде графов. Он основывается на принципах сверточных нейронных сетей (CNN).
Выбор сверточной архитектуры в GCN объясняется тем, что она предлагает локализованное приближение первого порядка спектральных сверток для графов. Локализованное приближение означает, что мы рассматриваем не всю структуру графовой сети, а лишь небольшую группу узлов и связей. Первый порядок указывает на размер этого локального приближения: поскольку это первый порядок, то мы будем изучать только ближайших соседей выбранного узла. Спектральная свертка — это более общее понятие, которое охватывает методы, использующие спектр графа для извлечения информации. Мы вернемся к этому более подробно позже.
Метод
Рассмотрим задачу классификации узлов в графе, где информация о метках доступна лишь для небольшого числа узлов. Эту задачу можно сформулировать как графо-ориентированное полу-контрольное обучение, в котором информация о метках распределяется по графу. Это достигается с помощью явной графо-ориентированной регуляризации, например, с использованием регуляризационного члена Лапласа в функции потерь.
Теперь давайте подробнее рассмотрим функцию потерь, используемую для классификации узлов в графе с учетом графовой регуляризации.
Формула состоит из двух частей:
-
Контролируемая потеря (оценивает, насколько хорошо модель предсказывает метки для известных узлов):
где Y — множество узлов с известными метками,
— конкретная истинная метка узла, а 
— предсказанная вероятность для этой метки. 𝜆 — весовой коэффициент. -
Регуляризационная потеря (улучшает обобщающую способность):
где
— элемент матрицы смежности графа, который стремится к 1, если узлы i и j связаны, и к 0, если нет. 
и 
— векторные представления (или "эмбеддинги") узлов i и j.
Если два узла связаны (то есть 
= 1), мы хотим уменьшить разницу между их представлениями f(Xi) и f(Xj). Это означает, что если узлы близки в графе, их предсказания должны быть похожи.
В этой работе мы кодируем структуру графа напрямую (представления графа с помощью определенного типа данных), используя модель нейронной сети f(X, A). Мы обучаем модель на контролируемой цели L0 для всех узлов с метками, что позволяет избежать явной графово-ориентированной регуляризации в функции потерь.
Ускоренное вычисление свертки
В этом разделе мы подробно рассмотрим теоретическую основу конкретной модели GCN. Первым шагом станет изучение правила распространения информации между слоями.
Здесь 
, где 𝐴 – матрица смежности неориентированного графа (графа без направления), а 
– единичная матрица. Зачем мы добавляем эту 𝐴 в нашу формулу?
Этот процесс демонстрирует, что каждый узел может взаимодействовать не только с соседями, но и сам с собой, что улучшает его представление в процессе работы сети.
Теперь давайте рассмотрим, что такое 
. Это 
, которое показывает, сколько ребер выходит из узла i в графе. Но почему 
? Дело в том, что узлы в графах могут иметь разное количество связей. Без нормализации, узлы с большим числом связей будут значительно влиять на результаты, и модель может стать нестабильной.
Перейдем к 
– это обучаемая матрица весов, где 𝑙 обозначает слой (как в сверточной сети). 𝜎 – наша функция активации (Relu, sigmoid, tanh и т.п.). И наконец, 
представляет собой матрицу признаков узлов на 𝑙 слое нейронной сети GCN.
Spectral Graph Convolution или спектральные графовые свертки
Для начала давайте по быстрому разберемся в спектральной свертки. Смысл спектральной свертки заключается в том, что мы хотим применять некоторую операцию фильтрации (свёртки) к сигналам на графе. Этот сигнал может представлять разные данные (например, активность людей в социальных сетях). Спектральная свертка позволяет нам изучать сигналы, используя свойства графа (структура и его связи).
Теперь рассмотрим более углубленно, спектральные графовые свертки (позволяют анализировать графы через из частоты(на сколько сильно связаны узлы)), определенные как умножение сигнала 
(скаляр для каждой вершины) с фильтром 
(тот же фильтр, что и в сверточной сети(окошко 3х3), но только здесь фильтр состоит из диагональной матрицы), параметризованным 
(содержат информацию о том, как следует усиливать или ослаблять значения сигнала на каждой из N вершин графа.) в диапазоне Фурье(позволяет выделить частотные компоненты сигнала, что облегчает анализ его свойств) , т.е.:
где U — это матрица собственных векторов нормализованного лапласиана графа (
) , с диагональной матрицей собственных значений 
и 
— преобразованием Фурье графа сигнала x. Мы можем рассматривать 
как функцию собственных значений 
(Лапласиан графа (
, где -
— диагональная матрица степеней, где каждый элемент 
равен степени вершины 
(количеству рёбер, соединяющих её с другими вершинами)) т.е. 
. Однако использование этой формулы требует больших вычислительных ресурсов, поэтому был предложен другой вариант.
Здесь мы предлагает использовать многочлены Чебышева для апроксимации (предсказание в диапазоне) функции фильтра 
где 
это пересчитанное 
. И опять же где 
обозначает наибольший собственный вектор 
.
теперь является вектором коэффициентов Чебышёва. Полиномы Чебышёва рекурсивно определяются как. 
при 
и 
. Теперь не много подравняем формулу для более точного определения и получим.
В общем все тоже самое только мы заменяем 
на
, но нахождение L прежнее 
. Кстати 
это максимальное расстояние шагов от центрального узла.
Хорошо, давайте снова упростим наше уравнения до такого вида:
Где мы будем приближать 
(параметр являющимся компромиссом между сложностью модели и стабильностью её обучения). 
и 
будут свободными параметрами. Про все остальное уже говорили.
Однако если у вас будет проблема с переобучением или может вы захотите ускорить процесс минимазацией числа операций. То можем просто убрать один свободный параметр, что приведет к:
Классификация узлов с неполным контролем
Введя простую, но гибкую модель
(
данные, 
матрица смежности) для эффективного распространения информации по графам, мы можем вернуться к проблеме полу-контролируемого классифицирования узлов. Как ранее было сказано мы можем ослабить определенные предположения , обычно делаемые в рамках графового полу-контролируемого обучения, путем внедрения контекста как данных 
, так и структуры графа 
в нашу модель
. Это позволяет нам использовать дополнительную информацию, которая может быть неявно представлена в матрице смежности, такой как связи между узлами, даже если сами узлы не помечены.
Примеры:
В этом разделе мы рассмотрим двухслойную GCN для полу-контролируемого классифицирования узлов на графе с симметричной матрицей смежности (матрица, которая удовлетворяет условию (
, где A может быть двоичной или взвешенной( матрица состоящий из 0 и 1 или матрица со любыми значениями). Сначала мы вычисляем (
(используется для нормализации матрицы смежности графа) на этапе предварительной обработки. Затем наша модель принимает простую форму:
Здесь 
— это матрица весов для скрытого слоя, которая связывает входные данные с скрытыми нейронами и имеет (
) признаковых карт.
— это матрица весов, связывающая скрытые нейроны с выходами. Функция активации softmax, определяемая как:
где 
, применяется по строкам(на выходном слое выводит вектор вероятностей сумма которых не превышает 1).
(То есть этим всем мы определяем выходной слой, что он будет выводить).
И на последок рассмотрим как мы будем оценивать нашу ошибку для полу-контролируемой многоклассовой классификации. А будем мы ее оценивать с помощью cross-entropy по всем маркированным примерам:
Где 
— это индикаторная переменная, указывающая на наличие метки для узла
и класса f . 
— это предсказанная вероятность того, что узел 
принадлежит классу f . А 
— множество индексов узлов, которые имеют метки.
Ну и сама сверточная графовая сеть (GCN)
Вот как будет выглядеть схема многослойной графовой сверточной сети (GCN). На рисунке (a) слева изображен входной слой с C входными каналами, а справа — F признаковыми картами на выходном слое, а также скрытые слои.
В (b) представлена визуализация активаций скрытых слоев, созданная с помощью t-SNE на основе данных Cora. Для классификации документов, отличающихся по цвету, используются 5% меток.
На этом всё! Надеюсь, мне удалось объяснить, что такое GCN, простыми словами. Если у вас остались вопросы, пишите в комментариях, и я с радостью отвечу на них.
Автор: Lightcart
