Возлюби своих соседей: сила графовых нейронных сетей

Рэй Айер и Томас Цзян в рамках курсового проекта Stanford CS224W.

Введение

Сети окружают нас повсюду. От анализа того, как COVID распространяется по всему миру, до понимания потоков капитала в экономике и даже размышлений о наших собственных дружеских отношениях, почти любое явление в мире можно описать с точки зрения взаимосвязанных отношений. С ростом Интернета произошел взрыв данных — данных о пользователях, продуктах, контенте и многом другом. Многие крупнейшие компании в мире — Facebook, Google, Amazon — заработали триллионы долларов, найдя способы использовать эти данные и анализировать их для получения значимой информации. Большая часть этих данных слишком сложна для хранения в простых таблицах или списках. Скорее, эти области требуют более мощной модели для представления не только самих сущностей, но и взаимодействий между ними. Графики предоставляют нам мощный язык для выражения этих данных.

Проблема в том, что в большинстве реальных условий эти графики не статичны — они постоянно меняются, появляются новые объекты и новые отношения между ними. TikTok будет добавлять миллионы новых пользователей каждый день, каждый со своими уникальными предпочтениями в отношении контента. Формулируя данные в виде графа, мы можем использовать методы машинного обучения, чтобы делать выводы о невидимых свойствах узлов, отношениях между узлами через ребра и общей структуре графа на основе существующих данных — мы называем это задачами прогнозирования на уровне узла, на уровне ребра и на уровне графа. В этой статье мы сосредоточимся только на методах классификации на уровне узлов, начиная с самых основ с помощью традиционных методов классификации и заканчивая внедрением графовых нейронных сетей (GNN). Мы рассмотрим многие причины, по которым GNN стали современными (SOTA) в задачах прогнозирования на уровне узлов.

Графики

Прежде всего — как мы формально определяем граф?

Графы — это структуры данных, содержащие узлы и ребра. Узел представляет объект в графе, а ребро представляет собой соединение между двумя узлами. Обычно графы определяются как G=(V,E), где V — набор узлов, а E — набор ребер между двумя узлами.

Для моделирования более сложных настроек мы можем даже иметь типы узлов и ребер, которые мы называем гетерогенными графами.

Почему графики важны и почему мы их используем?

Графики — это гибкая абстракция, которую можно использовать для моделирования множества различных задач. Именно это обобщение делает графики очень мощными инструментами для реализации методов ИИ. Если мы подумаем о других областях ИИ, таких как NLP и Vision, то это просто упрощение графиков. Для НЛП мы можем использовать графы для моделирования слов и символов с узлами и соседними словами или символами с ребрами. Для Vision мы можем использовать графики для моделирования пикселей изображения в двумерной матрице с узлами и ребрами в решетчатой структуре. Это означает, что графы можно использовать для решения более сложных задач, поскольку их можно упростить для многих популярных в настоящее время областей. Однако графы также предоставляют более интуитивный способ работы с абстрактными понятиями, такими как отношения и взаимодействия; они обеспечивают визуальный способ думать о них и формируют естественную основу для анализа отношений.

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

Набор данных

В этой статье мы сосредоточимся на использовании набора данных ogbn-arxiv для изучения методов классификации узлов. Этот набор данных представляет собой ориентированный граф, который представляет собой сеть цитирования между исследовательскими работами по компьютерным наукам, опубликованными на arXiv. [5]

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

Функции узла: каждый узел на графике имеет связанный 128-мерный вектор признаков, который вычисляется путем усреднения вложений слов в его заголовке и аннотации.

Разделение набора данных: в отличие от случайного разделения данные разбиваются более реалистичным образом в зависимости от даты публикации документов. А именно, в реальных условиях модель будет обучена на существующих исторических документах и развернута для прогнозирования класса недавно опубликованных документов. Таким образом, обучающий набор содержит все статьи, опубликованные до 2017 г., проверочный набор — все статьи, опубликованные в 2018 г., а тестовый набор — все статьи, опубликованные с 2019 г.

Задача прогнозирования: классификация узлов

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

Обзор подхода: от не-GNN к GNN

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

Распространение метки
Ванильный МЛП
MLP с функциями Node2Vec
ГрафикSAGE

Следуйте вместе с нашей связанной записной книжкой Google Colab здесь, чтобы воспроизвести наши результаты!

Раздел I: Методы, отличные от GNN

Распространение метки

Одной из самых основных проблем прогнозирования на уровне узлов, не требующих использования нейронных сетей, является алгоритм распространения меток. Идея распространения меток заключается в том, что при наличии некоторых немаркированных узлов в графе мы используем итеративный алгоритм для присвоения меток этим немаркированным точкам путем распространения меток по набору данных с использованием вероятностного реляционного классификатора. [1]. При этом мы предполагаем, что ребра между двумя узлами несут понятие сходства. Абстрактно это означает, что если два узла соединены, весьма вероятно, что эти два узла имеют схожие свойства. Конкретно, эта интуиция распространяется на наш набор данных, потому что, если данная немаркированная статья цитирует или цитируется многими другими помеченными статьями по заданной теме, вполне вероятно, что статьи имеют общую тему!

Идея вероятностного реляционного классификатора заключается в распространении меток узлов по сети с использованием распределения вероятностей. Здесь мы впервые вводим понятие передачи сообщений, когда узлы отправляют сообщения соседним узлам. Для заданного класса мы делаем это путем инициализации всех помеченных узлов значениями истинности (0 или 1) и инициализацией всех непомеченных узлов значением 0,5, а затем обновлением всех узлов в случайном порядке до сходимости или до достижения максимального количества итераций. Правило обновления для каждого узла v и метки c задается следующим образом:

В PyG эта модель невероятно проста в реализации и требует НУЛЕВЫХ обучаемых параметров:

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

Многослойный персептрон (MLP)

MLP является одной из самых основных архитектур модели нейронной сети, в которой исходные входные функции узла «передаются вперед» через несколько уровней вычислений для получения выходных данных, соответствующих распределению вероятностей по прогнозируемым классам. Ниже мы приводим визуальное представление этого процесса:

Обычно в моделях MLP у нас есть функции активации ReLU на каждом скрытом слое и функция активации Softmax на выходном уровне.

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

Функция Softmax полезна тем, что она создает «мягкие метки» для данных, поскольку по замыслу она выводит распределение вероятностей по классам. Вот почему Softmax используется в качестве функции активации последнего слоя.

МЛП с Node2Vec

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

Мы решаем эту проблему, вводя Node2Vec. Node2Vec — это «алгоритмический фреймворк для репрезентативного обучения на графах». В Node2Vec мы изучаем отображение узлов в низкоразмерное векторное пространство, которое максимизирует вероятность сохранения сетевых окрестностей узлов. Другими словами, Node2Vec встраивает узлы с похожими сетевыми соседями в пространстве признаков так, что похожие узлы имеют аналогичные вложения. [4]

Node2Vec работает, имитируя предвзятые случайные блуждания, уравновешивая компромисс между локальным и глобальным представлением сети. Это достигается путем определения возвращаемого параметра p (т. е. возврата к предыдущему узлу) и входящего параметра q (интуитивно «соотношение» исходящего/ DFS и внутреннее исследование/исследование BFS), как показано в примере ниже:

В PyG мы можем обучать наши вложения Node2Vec следующим образом:

Ниже мы построили обученные вложения Node2Vec для 1000 случайно выбранных узлов из нашего набора данных Arxiv. Мы проецируем их в 2 измерения, используя TSNE, и раскрашиваем узлы в зависимости от связанного с ними класса. Мы видим, что Node2Vec, который учитывает ТОЛЬКО структуру соседства, показывает некоторую четкую кластеризацию узлов по связанным с ними темам.

В этом подходе мы объединяем эти обученные вложения узлов с нашими исходными функциями узла и передаем эти расширенные функции в наш исходный MLP. Как мы увидим в разделе результатов, это значительно повышает производительность нашей модели!

Правильно и гладко (C&S)

Правильный и гладкий (C&S) — это недавний коллективный метод классификации SOTA. Это метод постобработки, призванный помочь очень простым базовым предикторам повысить производительность за счет рассеивания ошибок обучения по графу.

C&S следует следующей трехэтапной процедуре:

Предиктор базы поездов
Используйте базовый предиктор, чтобы предсказать программные метки всех узлов.
Постобработайте прогнозы, используя структуру графа, чтобы получить окончательные прогнозы всех узлов.

Идея, лежащая в основе C&S, заключается в том, что мы ожидаем, что ошибки в базовом предсказателе будут иметь положительную корреляцию вдоль ребер графа. Это означает, что для данного узла v ошибка в этом узле увеличивает вероятность аналогичной ошибки у соседей v. В связи с этим мы должны распределить эту неопределенность по всему графу.

Формально это делается путем распространения ошибок обучения E по краям, заданным формулой:

где A-тильда - нормированная матрица диффузии

и D представляет собой матрицу степеней.

Это можно реализовать с помощью нескольких строк кода, используя полезную библиотеку PyG:

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

Раздел II: Методы GNN

Как мы можем включить функции узла, а также структуру соседства вокруг узла в граф вычислений самой нашей модели? Войдите в графические нейронные сети!

Структура дизайна

Мы вводим понятие графовой нейронной сети (GNN). Основанные на концепции Node2Vec, GNN представляют собой метод глубокого обучения для изучения низкоразмерных вложений для узлов в графе.

На высоком уровне существует 5 ключевых аспектов структуры проектирования GNN:

Сообщение

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

Агрегация

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

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

Связность слоев

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

Увеличение графика

GNN работают, строя вычислительный граф по необработанному входному графу. Иногда для повышения производительности необходимо увеличить график. Есть два основных способа добиться этого:

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

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

Задача обучения

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

Ниже приведен анимированный GIF-файл, который представляет собой полный прямой проход GNN для создания встраивания для определенного узла в игрушечном графе:

В прилагаемом Colab мы реализовали три популярных слоя GCN, чтобы вы могли сравнить и сопоставить:

Граф сверточной сети (GCN)
ГрафикSAGE
Сеть графического внимания (GAT)

Ниже мы углубимся в один из этих слоев, GraphSAGE, чтобы понять, как он работает.

Глубокое погружение: GraphSAGE

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

В приведенном выше псевдокоде цикл представляет, как несколько слоев GraphSAGE могут быть сложены вместе, как обсуждалось в предыдущем разделе. В каждой итерации цикла мы видим этап передачи, агрегирования и обновления сообщений, происходящий для каждого узла в строках 4 и 5. В коде PyTorch с помощью PyG модель GraphSAGE может быть реализована в относительно небольшом количестве строк. код:

Мы видим, что большая часть внутренней логики может быть абстрагирована слоем SAGEConv. На самом деле, PyG также предоставляет множество полностью реализованных моделей, позволяющих быстро экспериментировать — мы могли бы инициализировать нашу модель одной строкой:

from torch_geometric.nn import GraphSAGE
model = GraphSAGE(in_channels, hidden_channels, num_layers, out_channels, dropout)

Мы обучаем модель, используя выбранную нами функцию потерь (например, кросс-энтропию) и оптимизатор (например, стохастический градиентный спуск, Адам), аналогично другим настройкам глубокого обучения:

Полученные результаты

Краткое содержание

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

Результаты GraphSAGE — глубокое погружение

На приведенных ниже графиках показан процесс обучения для нашей модели GraphSAGE за 500 эпох:

Кроме того, мы создали GIF-файл, изображающий встраивания узлов, спроектированных с помощью TSNE, на протяжении всего процесса обучения, чтобы показать, как узлы физически разделяются/группируются по классам с течением времени, что имеет смысл благодаря тому, как мы определили нашу цель обучения:

Оценка/Обсуждение

Узлы и окрестности

Как мы видели в нашем блиц-туре по вышеупомянутым моделям, недостаточно рассматривать только функции узла в отдельности (т. е. ванильный MLP) или делать прогнозы только на основе структуры графа (т. е. распространения меток). Лучшие модели учитывают индивидуальные характеристики ОБЕИХ узлов, а также контекст их локальных/глобальных окрестностей, чтобы делать прогнозы. Это интуиция, почему наша самая производительная модель была постобработана GraphSAGE с помощью Correct и Smooth.

Сила C&S

Правильный и сглаженный служит мощным этапом предварительной обработки, который практически не зависит от модели. Как мы убедились эмпирически, это работает особенно хорошо, когда простые модели, такие как MLP, используются в качестве базового предиктора, что приводит к значительному повышению производительности. Однако даже со сложными моделями GNN, такими как GraphSAGE, мы наблюдали небольшое увеличение точности теста. Интуитивно, поскольку дизайн GNN уже фиксирует соединения соседей посредством передачи сообщений, имеет смысл то, что C&S не дает столь резкого улучшения, как это было при постобработке модели MLP.

Проблема чрезмерного сглаживания

Почему 10-слойный GraphSAGE показал такую низкую производительность?

В отличие от других настроек глубокого обучения (например, CNN, RNN), где дополнительные слои обычно приводят к более высокой производительности, когда мы накладываем слишком много слоев, мы страдаем от проблемы чрезмерного сглаживания. Со временем все вложения узлов сходятся к одному и тому же значению.

Чтобы понять, почему это происходит, подумайте о «рецепторном поле» для GNN: общем наборе узлов, которые передавали сообщения интересующему узлу. Для любой пары узлов по мере увеличения числа слоев ЗНС увеличивается и размер окрестности, что приводит к высокой степени перекрытия рецептивного поля этих узлов. В конечном итоге это приводит к тому, что узлы становятся менее различимыми, поэтому вложения сходятся. Это изображено визуально ниже:

Соображения масштабируемости

Мы смогли обучить нашу модель с помощью полнопакетного обучения, поскольку наш набор данных был относительно небольшим, а связи между узлами были относительно редкими. Но что происходит в условиях, когда граф очень большой и плотно связанный, например, вся социальная сеть Facebook? Чтобы упростить вычисления, мы вводим понятие выборки соседей: на каждом уровне GNN вместо агрегирования сообщений от каждого соседнего узла мы выбираем не более чем H соседей:

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

Заключение

Возлюби ближнего своего, как самого себя. В этом посте мы рассмотрели различные подходы к проблеме классификации узлов. Мы начали с подходов, отличных от GNN, которые рассматривали ТОЛЬКО структуру связности графа или функции узла в отдельности. Затем мы поняли, что можем добиться более высокой производительности, объединив их с дополнением Node2Vec. Оттуда мы увидели, как простой этап постобработки C&S может улучшить наши результаты. Наконец, мы рассмотрели современные архитектуры GNN, показав, как они достигают наилучшей производительности в этой задаче, создавая вложения на основе функций узла, а также агрегируя сообщения, передаваемые из их окружения. Мы надеемся, что из наших экспериментов и анализа, проведенного в нашем Colab, и из этой статьи вы сможете увидеть невероятную силу и потенциал графовых нейронных сетей для решения самых разных задач сейчас и в будущем!