Мы расскажем про популярный класс нейронных сетей – графовые сети. Манера повествования позволит понять, как они устроены, даже новичкам в машинном обучении, однако обзор видов сетей и конструкций в них представлен достаточно полный, с использованием специальных терминов. Прямо сейчас есть несколько отличных источников по графовым сетям (см. ссылки в конце), однако этот материал у меня давно лежал (нет, правда, красивых картинок) и перед новым годом появилось время сделать заметку, поэтому я решил его опубликовать.
Предполагаем, что читатель знает, что граф – это пара множеств вершин (V) и рёбер (E), каждое ребро это пара вершин, см. рис 1. Далее рассматриваем неориентированные графы, т.е. считаем, что рёбра – неупорядоченные двухэлементные множества. Графы возникают во многих задачах анализа, особенно, когда есть множество объектов и очевидное множество отношений на нём (например, граф пользователей социальной сети, в котором каждое ребро соответствует дружбе между пользователями).
Проблема обработки графов
Рассмотрим сначала такой вопрос: как подать граф на вход нейронной сети (рис. 3)? Обычная сеть прямого распространения (FFN, Feed Forward Network) работает со входом фиксированной длины, см. рис. 2, поэтому первый естественный вариант – получение по графу вектора фиксированной размерности (представления, или эмбединга). Мы в итоге к нему и придём, пока отметим, что есть и другие техники для его получения, не рассмотренные в этом обзоре, например случайные блуждания по графу.
Другой подход – создание специальных нейронных сетей – «графовых» (Graph neural networks или сокращённо GNNs), которые способны обрабатывать графы. Заметим, что изображение это тоже граф, т.к. это не просто множество пикселей, для каждого пикселя есть соседние и это важная информация, поскольку их значения, как правило, сильно коррелируют, а их сильное различие может означать наличие на изображении в соответствующем месте контрастных переходов: границ объектов. На рис. 4 приведены примеры графов соседства, построенных по матрице пикселей (это т.н. 4- и 8-соседства).
Текст также является графом, правда очень простым, ведь текст это конечное множество слов (и знаков пунктуации, которыми иногда пренебрегают при анализе), на которых введён линейный порядок (есть первое слово, второе и т.д.), соответствующий граф показан на рис. 5.
В общем случае произвольный граф может сильно отличаться от графов, которые соответствуют изображениям и текстам: у него нет чёткой структуры, произвольные степени вершин и т.п. Но всё равно мы получили некоторую подсказку, как обрабатывать графы с помощью нейронных сетей. В частных случаях, когда граф представляет текст или изображение, такие сети должны быть похожи на классические, для работы с текстами и изображениями: свёрточные, рекуррентные, трансформеры и т.д.
Отметим, что в произвольных графах может быть не важен порядок вершин (в отличие от графов изображений и текстов). Поэтому при обработке графов часто важно свойство эквивариантности (Equivariance): если, например, слой сети как-то преобразует метки вершин, то при перенумерации вершин происходит соответствующая перенумерация меток-ответов, см. рис. 6 – здесь две вершины не отличимы с точки зрения структуры графа, поэтому если поменять их метки и пропустить через графовую сеть, то метки-ответы также должны поменяться.
Именно поэтому нельзя просто в обычную свёрточную сеть подать матрицу смежности: здесь вершины вынужденно упорядочены, а результат свёрточного слоя не эквивариантен относительно одновременной одинаковой перестановки строк и столбцов такой матрицы.
Представление вершин (Node representation learning)
Сначала мы рассмотрим довольно узкую задачу – обучение представлений вершин (Node representation learning). На практике мы имеем не просто граф, каждая вершина (и / или ребро) имеет описание, см. рис. 7; будем предполагать, что это признаковое описание – вещественный вектор фиксированной длины. В примере с социальной сетью про каждого пользователя мы можем знать пол, возраст и т.п. Но такое представление не учитывает информацию о структуре графа: оно локальное и не хранит информацию о соседях вершины (т.е. друзьях пользователя).
GNN вычисляют представления вершин в итеративном процессе, разные виды GNN по-разному, каждая итерация соответствует слою сети. Самая простая концепция такого вычисления – нейронное распространение (Neural Message Passing). Вообще, распространение сообщений (Message Passing) довольно известный приём в анализе графов, заключается в том, что каждая вершина имеет некоторое состояние, которое за одну итерацию уточняется по следующей формуле:
здесь и далее N(v) – окрестность вершины v, AGG (AGGREGATE) – функция агрегации (по смыслу она собирает информацию о соседях, например суммируя их состояния), UPDATE – функция обновления состояния вершины (с учётом собранной информации о соседях). Единственное требование, которое накладывается на последние две функции – дифференцируемость, чтобы использовать их в вычислительном графе и вычислять параметры сети методом обратного распространения. Вторую функцию иногда также называют комбинированием (COMBINE), поскольку она учитывает одновременно текущее состояние вершины и агрегацию её соседей. Очевидно, что на одной итерации мы для каждой вершины используем только информацию из её единичной окрестности – её «друзьях», на второй в её обновлённое представление просачивается информация из окрестности второго порядка (друзья друзей), после k-й итерации – из окрестности k-го порядка.
В классических графовых сетях (original GNN, [1],[2]) изменение состояния происходит по очень простой формуле:
т.е. агрегация здесь – обычное суммирование, а при обновлении последнее состояние и результат агрегации пропускаются через линейные слои (домножаются на матрицы), потом их линейная комбинация со смещением пропускается через функцию активации.
[1] Merkwirth Christian, Lengauer Thomas «Automatic Generation of Complementary Descriptors with Molecular Graph Networks»
[2] F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner and G. Monfardini, «The Graph Neural Network Model,«
Одна из самых популярных графовых сетей – GraphSAGE (Graph Sample and Aggregate), здесь практически такая же формула:
в квадратных скобках происходит вертикальная конкатенация (произведение матрицы на конкатенацию соответствует сумме произведений матриц на конкатенированные вектора), но в исходной работе [3] использовались разные агрегации:
1) усреднение – MEAN,
2) LSTM-агрегация (при использовании которой перемешивали соседей),
3) Pooling (линейный слой + пулинг):
Поясним, что при использовании LSTM-агрегации вершины из окрестности упорядочивали и последовательность их представлений подавали в рекуррентную LSTM-сеть. В GraphSAGE добавлен unsupervised loss (не будем его описывать подробно, но идея в том, чтобы у соседних вершин получались похожие представления, а у случайных – непохожие). Также в исходной работе сэмплировали соседей из окрестности (см. рис. 9, для повышения скорости вычисления), полученное состояние нормировалось (но при реализациях иногда этого не делают).
[3] W. L. Hamilton, R. Ying и J. Leskovec «Inductive Representation Learning onLarge Graphs»
В дальнейшем были предложены модификации GraphSAGE, например PinSage [4], в которой производится другое сэмплирование состояний окрестности (для обработки больших графов), в частности, делаются случайные блуждания, сэмплирование производится среди top-k посещённых вершин, а также используется функция активации ReLU, а состояния соседей пропускаются через отдельный модуль перед агрегацией.
[4] R. Ying, R. He, K. Chen, P. Eksombatchai, W. L. Hamilton, and J. Leskovec «Graph convolutional neural networks for web-scale recommender systems»
В графовых сетях термин петли (Self-loops) означает, что в окрестность вершины мы включаем её саму и в формуле её состояние отдельно не фигурирует, например как здесь [5]:
[5] George T. Cantwell, M. E. J. Newman «Message passing on networks with loops»
Обобщения агрегации (Generalized Neighborhood Aggregation)
Чаще агрегация у нас происходила суммированием состояний соседей, хотя можно использовать усреднение (Neighborhood Normalization):
или
Последнее усреднение используется в Graph convolutional networks (GCNs). В [6] показано, что важно правильно выбрать агрегацию, поскольку она может терять некоторую важную информацию, например степень вершины при обычном усреднении.
[6] Thomas N Kipf, Max Welling «Semi-supervised classification with graph convolutional networks»
Ещё одна из популярных агрегаций – Set pooling [7]:
функции f и g реализуются многослойными персептронами deep multi-layer perceptron). Кстати, доказано, что сеть с такой агрегацией является универсальным аппроксиматором.
[7] M. Zaheer, S. Kottur, S. Ravanbakhsh, B. Poczos, R. R. Salakhutdinov, and A. J. Smola. «Deep sets»
Также отметим Janossy pooling [8]:
в котором суммирование производится по всем перестановкам (это в теории, а на практике – по нескольким случайным).
[8] Ryan L. Murphy «Janossy pooling: learning deep permutation-invariant functions for variable-size inputs»
В GIN (Graph Isomorphism Network) используется довольно простая формула для адаптации состояний (и агрегация здесь – обычное суммирование) [9]:
[9] K. Xu и др. «How Powerful are Graph Neural Networks?»
Есть обучаемые агрегации (Learnable Aggregators, [10]), простейший вариант – включение в формулу маскирования (векторов, которые поэлементно умножаются на состояния соседей и являются выходами отдельного обучаемого модуля):
[10] Z. Li и H. Lu. «Learnable Aggregator for GCN»
И, конечно, при агрегации можно использовать механизм внимания (Attention), тогда суммирование состояний соседей производится с коэффициентами внимания:
Могут применяться разные механизмы внимания, в том числе с несколькими головками (не будем их все перечислять), в качестве функции f в оригинальной работе про Neighborhood Attention: Graph Attention Network (GAT) [11] использовалась LeakyReLU. Интерпретация механизма внимания здесь такая – мы смотрим на наших соседей и после этого выбираем коэффициенты в агрегации.
[11] P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio «Graph attention networks»
Проблема адаптации
Основная проблема при использовании описываемого нейронного распространения т.н. чрезмерное сглаживание (over-smoothing): после нескольких итераций пересчёта состояний вершин представления соседних вершин становятся похожими, поскольку у них похожие окрестности. Для борьбы с этим делают
- меньше слоёв агрегации и больше для «обработки признаков»,
- прокидывание слоёв или конкатенацию состояний с предыдыдущих слоёв,
- используют архитектуры, в которых есть эффект памяти (например GRU),
- приёмы с нормировками (поддерживают равной константе сумму квадратов попарных расстояний между представлениями, см. [11b]),
- используют аугментацию, например DropEdge (по смыслу понятно, что это удаление случайных рёбер),
- используют noise regularization.
[11b] Lingxiao Zhao, Leman Akoglu «PairNorm: Tackling Oversmoothing in GNNs»
Для одного из способов конкатенаций состояний в теории графовых сетей есть термин «Jumping Knowledge Connections» [12]:
[12] K. Xu, C. Li, Y. Tian, T. Sonobe, K. Kawarabayashi, and S. Jegelka «Representation learning on graphs with jumping knowledge networks»
В сети DEEPGCNS [13] также используется идея прокидывания, как в DenseNet, но ещё используются разреженные свёртки (dilated convolutions) по аналогии, как это делается в свёрточных сетях: соседи вершины упорядочиваются и агрегация происходят по k из них, для обычной свёртки по первым k, для разреженной с шагом 1: по 1-му, 3-му, 5-му и т.д., см. также рис. 12.
[13] G. Li, M. Muller, A. Thabet, and B. Ghanem «DeepGCNs: Can GCNs go as deep as CNNs?»
Агрегация по графу
До сих пор мы рассматривали способы итеративного уточнения представлений вершин, но начали мы с того, что хорошо бы граф уметь представлять в виде фиксированного вектора. Как это сделать, имея представления вершин? Первый очевидный способ – Graph Pooling – просуммировать полученные представления:
где f – некоторая функция, если она тождественная, то получаем усреднение. В т.н. Readout-слоях [13b] такое усреднение конкатенируется с поэлементным максимумом представлений:
[13b] Cangea, C., Velickovic, P., Jovanovic, N., Kipf, T., and Lio,P. «Towards sparse hierarchical graph classifiers»
Другой подход – считать, что множество вершин это последовательность, следовательно, их представления можно подать на вход LSTM-сети, возможно, с механизмом внимания. В подходе SortPool [14] вершины сортируются (каким-то образом, например по последнему элементу в векторе-представлении), конкатенируются представления первых k вершин и подаются на вход в обычную нейросеть.
[14] M. Zhang, Z. Cui, M. Neumann, Y. Chen «An End-to-End Deep Learning Architecture for Graph Classification»
Также есть группа подходов, в которой итерационно упрощают граф. Вообще-то пулинг в свёрточных слоях для изображений и текстов как раз упрощает граф, поэтому в GNN тоже разумно иметь такую операцию. В SAGPool (Self-Attention Graph Pooling) [15] итерационно получают оценки-рейтинги вершин, оставляют top-вершины. Процесс продолжается, пока не останется одна или до Readout-слоя (так сделано в оригинальной работе). Как следует из названия, в SAGPool используется механизм внимания.
[15] J. Lee, I. Lee, J. Kang «Self-Attention Graph Pooling»
Ещё метод, использующий упрощение графа – DiffPool [16] – на каждой итерации производится кластеризация вершин графа (в терминах теории графовых сетей – «выделение сообществ»), производится агрегация вершин в кластерах, переходим к графу с вершинами, соответствующим сообществам. В MinCutPool [17] кластеризация производится спектральным методом кластеризации (кластеризация в специальном пространстве собственных векторов матрицы, полученной по матрице смежности графа; из-за того, что находятся не все собственные векторы, метод вычислительно эффективен).
[16] R. Ying и др. «Hierarchical Graph Representation Learning with Differentiable Pooling»
[17] Filippo Maria Bianchi «Spectral Clustering with Graph Neural Networks for Graph Pooling»
Использование GNN
Теперь рассмотрим, какие задачи и как решаются с помощью графовых сетей. Из того, что мы знаем на текущий момент:
- на вход сети подаётся граф, каждая вершина которого имеет признаковое описание. Это описание можно считать начальным состоянием (представлением) вершины. См. рис. 16.
- Могут быть слои, которые независимо модифицируют представления (для каждой вершины его представление пропускается через небольшую нейронку). См. (1) на рис. 16.
- Могут быть слои, которые модифицируют представления всех вершин, учитывая представления вершин-соседей. См. (2) на рис. 16.
- Могут быть слои, упрощающие граф (например, уменьшающие число вершин). См. (3) на рис. 16.
- Могут быть слои, получающие представление графа (вектор фиксированной длины) по текущему графу с представлениями вершин. См. (4) на рис. 16.
Обычно такие сети используются для задач:
- предсказания на уровне вершин (node-level predictions), например классификации вершин (node classification),
- предсказания на уровне пар вершин / рёбер (edge-level predictions), например в задаче предсказания вероятности появления ребра в графе (link predictions),
- предсказания на уровне графа (graph-level predictions), например для классификации графов (graph classification).
- для детектирования сообществ (community detection) или предсказания отношений между вершинами графа (relation prediction).
Для предсказания на уровне графа берут представление графа (в чистом виде или пропускают через сеть прямого распространения), функция ошибки зависит от задачи, например в задаче регрессии (по графу определяется вещественное число) можно использовать такую функцию
В задачах на уровне вершин аналогично поступают с представлениями вершин:
в задачах кластеризации вершин (например, детектирования сообществ) кластеризацию проводят в пространстве представлений вершин. В задачах на уровне рёбер работают с конкатенацией представления рёбер или с функцией от пары представлений, например со скалярным произведением представлений:
Графовые сети могут использоваться и в задачах без меток, тогда в функциях ошибки оценивается, насколько согласованы представления вершин и графа, содержащего эти вершины, например в Deep Graph Infomax (DGI) используется ещё дискриминатор, который по паре (представление вершины, представление графа) пытается понять, принадлежит ли вершина графу, отрицательные примеры получаются с помощью модификации исходного графа [18].
[18] Petar Veličković, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, R Devon Hjelm «Deep Graph Infomax»
Аугментации графа
Как и в других областях глубокого обучения, в графовых нейронных сетях используются аугментации – методы увеличения обучающей выборки с помощью модификации исходных данных. В принципе, сэмплирование соседей, которое мы рассматривали, в некотором смысле меняет исходную информацию. Если граф разреженный, то его пополняют рёбрами по принципу «друг моего друга мне друг». Если плотный и большой, то в некоторых задачах берут подграфы.
Что мы не рассмотрели?
Самые важные вопросы, которые мы пока не затронули (но может быть и продолжение поста):
- применение спектральной теории графов в графовых сетях, в том числе, получение других представлений свёрток,
- работа с динамическими графами (которые меняются со временем),
- робастные методы анализа графов,
- генеративные графовые сети,
- самообучение в графовых сетях,
- примеры приложений графовых сетей и библиотеки для реализации GNN.
Ссылки
Есть хорошие источники по графовым сетям. Во-первых, обзорные книги:
- Hamilton «Graph Representation Learning»
- Zhiyuan Liu, Jie Zhou «Introduction to Graph Neural Networks» // 2020
Во-вторых, недавно вышли хорошие обзоры. Здесь многое из них взято:
Наконец, появились хорошие ресурсы на русском языке:
P.S. Первая версия поста была опубликована в блоге компани Dasha.ai
Анализ малых данных 
[…] Читать дальше […]