Ограничения репрезентативной способности и оценка ошибки обобщения для графовых нейронных сетей

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

Работа направлена на исследование двух проблем, связанных с графовыми нейронными сетями. Во-первых, авторы приводят примеры различных по структуре графов, но неразличимых и для простых, и для более мощных GNN. Во-вторых, они ограничивают ошибку обобщения для графовых нейронных сетей точнее, чем VC-границы.

Введение

Графовые нейронные сети - это модели, которые работают напрямую с графами. Они позволяют учитывать информацию о структуре. Типичная GNN включает в себя небольшое число слоев, которые применяются последовательно, обновляя представления вершин на каждой итерации. Примеры популярных архитектур: GCN, GraphSAGE, GAT, GIN.

Процесс обновления эмбеддингов вершин для любой GNN-архитектуры можно обобщить двумя формулами:

$a_v^{t+1} = AGG \left(h_w^t: w \in \mathcal{N}\left(v\right)\right) \\ h_v^{t+1} = COMBINE \left(h_v^t, a_v^{t+1}\right),$

где AGG - обычно функция, инвариантная к перестановкам (sum, mean, max etc.), COMBINE - функция объединяющая представление вершины и ее соседей.

Дерево вычислений для двухслойной GNN на примере узла A. Источник: https://eng.uber.com/uber-eats-graph-learning/

Более продвинутые архитектуры могут учитывать дополнительную информацию, например, фичи ребер, углы между ребрами и т.д.

В статье рассматривается класс GNN для задачи graph classification. Эти модели устроены так:

Сначала производятся эмбеддинги вершин с помощью L шагов графовых сверток
Из эмбеддингов вершин получают представление графа с помощью инвариантной к перестановкам функций (например, sum, mean, max)
Классификатор предсказывает бинарную метку по представлению графа

Ограничения графовых нейронных сетей

В статье авторы рассматривают ограничения для трех классов GNN:

Локально инвариантные графовые нейронные сети (LU-GNN). Сюда входят вышеупомянутые GCN, GraphSAGE, GAT, GIN и другие
CPNGNN, которая вводит локальный порядок, нумеруя соседние вершины от 1 до d, где d - степень вершины (в оригинальной работе это называют port numbering)
DimeNet, которая оперирует 3D-графами, учитывая расстояния между вершинами и углы между ребрами

Ограничения LU-GNN

Графы G и G неразличимы LU-GNN, так как деревья вычислений будут совпадать для узлов одного цвета, следовательно эмбеддинги, полученные с помощью инвариантной к перестановкам readout-функции, будут одинаковыми. CPNGNN с введением подходящего порядка сможет различать как одноцветные вершины в G и G, так и сами графы.

Ограничения CPNGNN

Однако, существует плохой порядок, при котором и CPNGNN произведет одинаковые эмбеддинги для вершин одного цвета.

Граф S₈ и две копии S₄ различаются в таких характеристиках, как обхват, окружность (длина наименьшего и наибольшего циклов соответственно), радиус, диаметр и количество циклов, но CPNGNN с таким порядком портов и readout-ом, инвариантным к перестановкам, произведет для одинаковые эмбеддинги. А значит, по ним невозможно будет восстановить правильные характеристики для обоих графов.

Здесь CPNGNN с такими же условиями не сможет восстановить характеристики из предыдущего примера для графа G₂ и двух копий G₁. Однако, DimeNet сможет это сделать, так как она учитывает углы, которые не везде совпадают в случае этих графов, например, $\angle A_1B_1C_1$ и $\angle \underline{A}_1\underline{B}_1\underline{C}_1$ .

Ограничения DimeNet

DimeNet не сможет различить G₄ и граф, составленный из двух копий G₃, так как расстояния и углы в этих графах будут идентичны. Значит, она так же не вычислит характеристики обоих графов. Можно заметить, что G₄ и G₃ являются графами S₄ и S₈, натянутыми на куб, а значит, даже усовершенствованная версия DimeNet с нумерацией портов из S₄ и S₈ не будет справляться с этой задачей.

Шаг в сторону более мощных GNN

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

GNN, предложенная авторами работает так:

Шаг DimeNet
Дополнение message-эмбеддинга ребра $m_{uv}^{\left(l\right)}$ геометрической информацией $\Phi_{uv}$ по формуле $\underline{m}_{uv}^{\left(l\right)} = \underline{f}\left(m_{uv}^{\left(l\right)}, \Phi_{uv}\right)$
Получение эмбеддинга вершины с учетом введенного локального порядка $\left(c_v\left(i\right), t_{i, v}\right)$ , где c - i-ый сосед вершины v, t - эмбеддинг порядка.

Формула обновления представления вершины:

$h_{v}^{\left( l + 1 \right)} = f \left( h_{v}^{\left( l \right)}, \underline{m}_{c_v\left( 1 \right)v}^{\left( l \right )}, t_{1, v}, ..., \underline{m}_{c_v\left( d \left( v \right ) \right)v}^{\left( l \right )}, t_{ d \left( v \right ), v} \right )$
Шаг инвариантного к перестановкам readout-а
Классификатор или регрессор в зависимости от задачи

Такая модель позволит различать графы во всех вышеприведенных примерах.

Оценка ошибки обобщения

Авторы рассматривают конкретный класс моделей: LU-GNN, в которой обновление представления вершины происходит согласно

$h_v^{l + 1} = \phi \left( W_1x_v + W_2 \rho \left( \sum_{u \in \mathcal{N} \left( v \right)} g\left( h_u^l \right)\right) \right),$

где $\phi,\ g,\ \rho$ - нелинейные функции активации, x_v - вектор признаков для вершины v, такие, что $\rho \left(0\right) = 0,\ \forall v: \lVert x_v \rVert_2 \le B_x,\ \forall x \in \mathbb{R}^r: \lVert \phi \left( x \right ) \rVert_{\infty} \le b < \infty,\ \phi\left( 0 \right ) = 0,\ g\left( 0 \right ) = 0$ . Также, $\phi,\ g,\ \rho$ липшицевы с константами $C_{\phi},\ C_{g},\ C_{\rho}$ соответственно, а $\lVert W_1 \rVert_2 \le B_1,\ \lVert W_2 \rVert_2 \le B_2$ . $W_1,\ W_2,\ \phi,\ g,\ \rho$ одинаковы на всех слоях GNN.
Далее бинарный классификатор применяется к представлению каждой вершины отдельно и полученные метки усредняются. Параметр $\beta$ бинарного классификатора обладает свойством $\lVert \beta \rVert_2 \le B_{\beta}$ .

Пусть $f\left(G\right)$ - результат применения GNN к графу с меткой $y \in \{0, 1\}$ , $p\left( f \left( G \right ), y \right ) = y \left( 2f \left( G \right ) - 1 \right ) + \left( 1 - y \right ) \left( 1 - 2 f \left( G \right ) \right )$ - разница между вероятностями правильного и неправильного лейбла, $p\left( f \left( G \right ), y \right ) < 0$ только в случае ошибки классификации.

Фукнция потерь, где $a = -p\left( f \left( G \right ), y \right )$ , $\mathbb{I}\left[\right]$ - индикаторная функция:

$loss_{\gamma}\left( a \right ) = \mathbb{I}\left[ a > 0\right ] + (1 + \frac{a}{\gamma})\mathbb{I}\left[ a \in \left[ \gamma, 0 \right ] \right].$

Тогда эмпирическая сложность Радемахера для класса функций предсказания GNN на тренировочном множестве $\{G_j, y_j\}_{j=1}^m$ :

$\hat{\mathcal{R}}\left( f \right) = \frac{1}{m} \sum_{j = 1}^m loss_{\gamma} \left( -p\left( f \left(G_j\right), y_j \right) \right)$

Авторы строят доказательство, пользуясь леммой, в которой утверждается, что с большой вероятностью, ошибку предсказания для GNN можно ограничить суммой ошибки на тренировочной выборке и способностью модели предсказывать класс по эмбеддингу графа. Для класса, рассматриваемого авторами (GNN, которые предсказывают метку графа по меткам большинства вершин), второе слагаемое можно заменить на способность предсказывать класс по вершинам, то есть деревьям вычислений, следовательно можно анализировать эти деревья.

Все вышеописанное было проделано для того, чтобы можно было использовать два факта:

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

Это позволяет вывести границы ошибки обобщения по аналогии с RNN

Cравнение с RNN, видно сходство

В таблице $\mathcal{C}$ - сложность перколяции: $\mathcal{C} = C_{\phi}C_gC_{\rho}B_2$ , r - размер эмбеддинга, d - максимальная степень вершины, m - размер тренировочной выборки, L - количество слоев, $\gamma$ - зазор, зависящий от данных

Эти оценки позволяют существенно более точно оценить ошибку обобщения, по сравнению с работой, где получили оценку $\tilde{\mathcal{O}} \left(r^3N / \sqrt{m} \right)$

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

Выводы

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

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

Трансформеры за последние несколько лет штурмом захватили мир NLP, а сегодня они с успехом применяются в выходящих за рамки NLP приложениях. Они обладают такими возможностями благодаря модулю внимания, который схватывает отношения между всеми словами последовательностей. Но са

Пример расчётного доказательства в Lean

Математики давно используют компьютеры в своей работе как инструменты для сложных вычислений и выполнения рутинных операций перебора. Например, в 1976 году методом компьютерного перебора была доказана

Зарабатывать продажей лекарств, которые заведомо не работают, не только аморально, но и не особо легко. Люди всё-таки обычно не хотят покупать препараты, неэффективность которых была доказана. А вот если вы сумели выдавить заветное p < 0.05 в пользу того, что акупунктура та

В этой статье мы рассмотрим, что такое классификатор, поговорим о мультиклассовой классификации с помощью нейронных сетей. Затем, ознакомившись с контекстом перейдем к основному топику поста к Log-Sum-Exp Trick. Напишем формулы и разберемся, как этот трюк помогает избежать переполнения чисел с плавающей то

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

Призма Вельда-Бланделла

На рубеже четвертого и третьего тысячелетия до нашей эры на Земле возникли две первые цивилизации. В долине Нила после объединения верхнего и нижнего Египта образовалось

Очень много людей с самым разным бэкграундом, и не всегда даже техническим, в последнее время пытаются перейти в data science. И такой ажиотажный интерес - проблема для всех, кто рассматривает переквалификацию в эту сферу. Потому что рынок труда может оказаться наводнён соискателям без опыта.

С точки зрения потенциального работодателя: вы скорее возьмёте выпускника технического вуза, или человека за 40, без профильного опыта

Задача распознавания семантического следования (textual entailment), или импликации (natural language inference), в текстах на естественном языке состоит в определении того, может ли часть текста (посылка, антецедент) подразумеваться или противоречить (или не противоречить) другому фрагменту текст

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

Определение эмоций человека по его речи уже относительно насыщенн

Мне давно нравятся Байесовские сети доверия

Представьте ситуацию: вам нужно воспользоваться оплаченным (как вы думаете) сервисом и вдруг оказывается, что он отключен за неуплату. Такая неприятность портит впечатление от бренда, снижая поток прибыли, а внезапно отключенный клиент может не вернуться к сервису. К старту ку

Работа направлена на исследование двух про

В этой статье мы поговорим о математике градиентного спуска, почему при обучении нейронных сетей применяется стохастический градиентный спуск и о вариации SGD (Stochastic Gradient Descent) с использованием скользящего среднего (SGD с momentum и Nesterov Accelerated Gradient).

Представляем вам версию 0.2 библиотеки глубокого обучения KotlinDL.

KotlinDL 0.2 теперь доступен на Maven Central (до этого он лежал на bintray, но закатилось солнышко земли опенсорсной). Появилось столько всего нового: нов

В конце прошлого года, Booking.com запустил соревнование по построению рекомендательного алгорима для путешественников. Задача наилучшим образом предсказать следующий город для пользователя, основывываясь на предыдущих посещенных городах.

Рекомендации городов в booking.com, картинка

В этой обзорной статье вы узнаете, что такое mesh denoising, какие методы использовались и используются для устранения шума на полигональных сетках (от классических фильтров до передовых графовых нейронных сетей), и получите общее представление о развитии

Кадр из аниме "Жрица и медведь"

До появления YOLO большинство способов обнаружения объектов пытались адаптировать классификаторы для детекции. В YOLO же, обнаружение объектов было сформулировано как

Работа направлена на исследование двух про

Данная статья будет полезна студентам и тем, кто хочет разобраться с тем, как происходит шумоподавление речи (Speech Denoising) с помощью глубокого обучения. На Хабре уже были статьи по данной тематике несколько лет назад (раз, два), но нашей целью является желание дать несколько более глубокое понимание процесса работы со звуком.

Представляем вам версию 0.2 библиотеки глубокого обучения KotlinDL.

Будущее здесь безо всяких преувеличений. В нашей публикации Третий глаз для незрячих рассказывалось о том, как можно облегчить жизнь незрячим людям при помощи нескольких ультразвуковых сенсоров. Сегодня рассказываем о кибернетической руке на основе глубокого обучения, т

Глубокое обучение интересная тема и моя любимая область исследований. Мне очень нравится играть с новыми исследовательскими разработками специалистов по глубокому обучению. Я только что наткнулся на удивительный репозиторий GitHub одного из моих товарищей по группе компьютерно

Представлюсь

Всем привет! Меня зовут Влад Виноградов, я руководитель отдела компьютерного зрения в компании EORA.AI. Мы занимаемся глубоким обучением уже более трех лет и за это время реализовали множество проектов для российских и международных клиентов в которые входила исследовательская часть и обучение моделей. В последнее время мы фокусируемся на решении задач поиска похожих изображений и на текущий момент создали сис

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

TLDR: крохотные модельки обошли модные графовые нейронки в предсказании свойств молекул.
Код: здесь. Берегите Природу.

Работа направлена на исследование двух про

У меня сегодня формат похожий на читаем статьи за вас от ODS, только я взяла несколько связанных.
Отправной точкой служит статья под названием Searching Central Difference Convolutional Networks for Face Anti-Spoofing (2020 г) и мое желание посмотреть немного вглубь на историю методов, в ней использованных.
Я пройдусь по

Привет, Хабр! Продолжаем публиковать рецензии на научные статьи от членов сообщества Open Data Science из канала #ar

	Русский
	English

Ограничения репрезентативной способности и оценка ошибки обобщения для графовых нейронных сетей

Введение

Ограничения графовых нейронных сетей

Ограничения LU-GNN

Ограничения CPNGNN

Ограничения DimeNet

Шаг в сторону более мощных GNN

Оценка ошибки обобщения

Выводы

Сейчас читают

Математика

Перевод Наглядно о том, почему трансформеры работают настолько хорошо

Компьютерное доказательство теории конденсированной математики первый шаг к великому объединению

Перевод Plt0.05, и откуда оно (иногда) берётся

Log-Sum-Exp Trick как свойства функций делают работу классификаторов реальной

Оцениваем открытые и коммерческие цифровые модели рельефа

Тайна списка шумерских царей. Часть 1. Машина времени

Машинное обучение

Стоит ли смотреть в сторону Data science?

Перевод Учимся понимать таблицы на меньшем объеме данных

Распознавание эмоций в записях телефонных разговоров

БСД, или как легко объяснить финансистам их же задачи в терминах машинного обучения

Перевод Оптимизация платежей в Dropbox при помощи машинного обучения

Log-Sum-Exp Trick как свойства функций делают работу классификаторов реальной

Graph neural networks