Skip to content
Назад к результатам поиска

Графовая нейронная сеть — GCN / GAT / GraphSAGE

Год
2017–2018 (major variants)
Тип
Deep learning on graph-structured data

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

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

Три канонических варианта — графовая свёрточная сеть (GCN), представленная Кипфом и Веллингом в 2017 году, графовая сеть с механизмами внимания (GAT), представленная Величковичем и соавт. в 2018 году, и GraphSAGE — различаются способом агрегирования информации о соседях: GCN применяет спектральную свёртку по всей матрице смежности, GAT взвешивает соседей по изученным оценкам внимания, а GraphSAGE выборочно агрегирует локальные окрестности индуктивно, что позволяет обобщать на ранее невидимые узлы.

Интуиция метода

Представьте каждый узел в графе как человека в социальной сети. У этого человека есть свой профиль (признаки), но то, кого он знает, также многое говорит о нём. GNN позволяет каждому узлу многократно собирать сообщения от своих соседей, смешивать эти сообщения со своей собственной информацией и обновлять своё представление — слой за слоем. После нескольких раундов такого обмена в стиле «сплетен» встраивание каждого узла отражает не только его самого, но и локальный подграф вокруг него. GCN делает это с помощью фиксированного симметричного усреднения соседей; GAT решает, каким соседям доверять больше, изучая веса внимания; GraphSAGE выбирает фиксированное подмножество соседей и изучает функцию агрегирования, которая может быть применена к узлам, которые он никогда раньше не видел.

История

Основы применения нейронных сетей к графам были заложены Скарселли и соавт. (2009), но современная эра GNN началась с графовой свёрточной сети (2017) Кипфа и Веллинга, которая упростила спектральную графовую свёртку до эффективной аппроксимации первого порядка с использованием симметричного нормализованного умножения на матрицу смежности. Год спустя Величкович и соавт. (2018) представили графовые сети с механизмами внимания, заменив фиксированное усреднение GCN на обучаемые коэффициенты внимания для каждого ребра, что позволило модели избирательно взвешивать соседей. Одновременно Гамильтон и соавт. (2017) предложили GraphSAGE, индуктивную структуру, которая выбирает окрестности фиксированного размера и изучает функции агрегирования, переносимые на невидимые узлы, что сделало GNN практичными для больших и динамических графов. Эти три работы установили парадигму передачи сообщений, которая теперь лежит в основе большинства исследований GNN.

Когда применять

Используйте GNN, когда ваши данные естественным образом структурированы как граф — социальные сети, сети цитирования, молекулярные графы, графы знаний или любая другая ситуация, где отношения между сущностями несут предсказательный сигнал. Вам нужна матрица признаков узлов и список рёбер. Для осмысленного обучения требуется минимум около 50 узлов. GNN применимы для классификации узлов (предсказание метки для каждого узла), предсказания связей (вывод отсутствующих рёбер) и классификации графов (присвоение метки всему графу). Предположение о гомофилии — связанные узлы, как правило, имеют одну и ту же метку — неявно используется GCN и стандартным GAT; если ваш граф гетерофилен, рассмотрите архитектуры, разработанные для этого случая. Для больших графов обучение полными пакетами является чрезмерно затратным по памяти, и требуется выборка окрестностей мини-пакетами (в стиле GraphSAGE). Если ваш граф имеет менее 20 узлов, более подходящим выбором являются традиционные метрики центральности.

Ограничения и замечания

  • Пересглаживание: стекирование многих слоёв GNN приводит к тому, что все встраивания узлов сходятся к общему значению, ограничивая эффективную глубину примерно 2–4 слоями на практике.
  • Масштабируемость: GCN и GAT с полным пакетом требуют хранения всей матрицы смежности и матрицы признаков в памяти, что нецелесообразно для очень больших графов без выборки или разбиения.
  • Предположение о гомофилии, заложенное в стандартную агрегацию, ухудшает производительность на гетерофильных графах, где соседи, как правило, имеют разные метки.
  • Требуется минимальный размер выборки ~50 узлов; меньшее количество узлов оставляет модель без достаточного сигнала для изучения значимых представлений.

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Совместно использует как признаки узлов, так и топологию графа, превосходя методы, использующие только одно из них.
  • Механизм внимания GAT предоставляет оценки важности для каждого ребра, добавляя интерпретируемость к агрегации.
  • GraphSAGE является индуктивным и может обобщать на узлы и графы, не виденные во время обучения, что позволяет развёртывать его в растущих сетях.
  • Унифицированная структура передачи сообщений охватывает классификацию узлов, предсказание связей и классификацию графов с одной и той же архитектурной основой.

Применение

  • Классификация узлов в сетях цитирования — предсказание темы статьи на основе её содержания и ссылок на цитирование.
  • Открытие лекарств — предсказание молекулярных свойств путём рассмотрения атомов как узлов и химических связей как рёбер.
  • Рекомендательные системы — моделирование пользователей и элементов как двудольного графа и предсказание взаимодействий пользователь-элемент через предсказание связей.
  • Обнаружение мошенничества в сетях финансовых транзакций — выявление аномальных узлов на основе их признаков и структуры окрестности.
  • Завершение графов знаний — вывод отсутствующих отношений между сущностями в крупномасштабных базах знаний.

Как это работает

Как это работает

1

Граф определяется матрицей признаков узлов X (одна строка на узел, один столбец на атрибут) и списком рёбер (или матрицей смежности) A. Неориентированные рёбра являются стандартными для GCN и GAT; GraphSAGE также поддерживает ориентированные графы. Самопетли обычно добавляются к A, чтобы каждый узел был включён в свою собственную агрегацию.

2

Исходные атрибуты узлов нормализуются и, при необходимости, встраиваются в непрерывное векторное пространство. Атрибуты рёбер, если они присутствуют, могут быть включены в качестве дополнительных сигналов. Результатом является плотная матрица признаков, которую будет преобразовывать каждый слой GNN.

3

Каждый слой GNN вычисляет новое представление узла путём агрегирования признаков соседей узла и объединения их с собственными признаками узла с помощью обучаемой матрицы весов и нелинейной функции активации. GCN применяет нормализованное умножение на матрицу смежности (спектральную свёртку); GAT вычисляет коэффициенты внимания softmax для каждого ребра, чтобы влиятельные соседи вносили больший вклад; GraphSAGE случайным образом выбирает окрестность фиксированного размера и применяет дифференцируемый агрегатор (среднее, LSTM или пулинг). Стекирование L слоёв позволяет информации распространяться на L шагов, но слишком большое количество слоёв вызывает пересглаживание, при котором все встраивания узлов сходятся к одному и тому же значению.

4

Финальные встраивания узлов подаются на вход специализированной для задачи головной части. Для классификации узлов слой softmax присваивает вероятности классов каждому узлу. Для предсказания связей внутреннее произведение или MLP оценивает вероятность существования ребра между двумя встраиваниями узлов. Для классификации графов глобальный пулинг (сумма, среднее или иерархический) агрегирует все встраивания узлов в единый вектор уровня графа перед слоем классификации.

5

Производительность модели измеряется на отложенном тестовом наборе с использованием метрик, соответствующих задаче: точность или F1 для классификации узлов и графов, AUC-ROC для предсказания связей. Поскольку графовые наборы данных часто имеют ограниченный размер, трансдуктивная оценка (маски train/val/test на одном и том же графе) или индуктивные разбиения (несвязные подграфы) должны соответствовать сценарию развёртывания.

Частые ошибки

  • Добавление слишком большого количества слоёв GNN вызывает пересглаживание: все встраивания узлов сходятся, и модель теряет дискриминационную способность. Сохраняйте количество слоёв на уровне 2–4 и отслеживайте дисперсию встраиваний.
  • Обучение на полном графе без мини-пакетов является чрезмерно затратным по памяти для больших сетей; используйте выборку соседей в стиле GraphSAGE или методы разбиения графов для графов с более чем несколькими тысячами узлов.
  • Применение трансдуктивно обученной GCN непосредственно к новым, невидимым узлам во время вывода некорректно; используйте индуктивный метод, такой как GraphSAGE, если ваше развёртывание требует обобщения на новые узлы.
  • Игнорирование предположения о гомофилии на гетерофильных графах приводит к плохим результатам; проверьте коэффициент ассортативности графа перед выбором стандартного варианта GNN.
  • При менее чем 20 узлах обучение GNN даёт ненадёжные представления; в этом режиме предпочтительнее традиционный анализ центральности сети.

Часто задаваемые вопросы

С какого варианта GNN мне следует начать — GCN, GAT или GraphSAGE?

GCN — это простейший базовый вариант, который хорошо работает на малых и средних гомофильных графах, где все узлы известны во время обучения. GAT предпочтителен, когда важность соседей варьируется и вам нужны интерпретируемые веса внимания. GraphSAGE — правильный выбор, когда вам нужно обобщать на узлы, не виденные во время обучения, или когда граф слишком велик для обработки полным пакетом.

Что такое пересглаживание и как его избежать?

Пересглаживание происходит, когда многие слои GNN приводят к тому, что все встраивания узлов сходятся к одному и тому же значению, устраняя дискриминационную информацию. На практике 2–4 слоя обычно являются оптимальными. Такие методы, как остаточные связи, сети прыгающих знаний и DropEdge, могут помочь, если необходимы более глубокие архитектуры.

Требуют ли GNN размеченных данных для всех узлов?

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

Насколько большим должен быть граф?

Для осмысленного обучения GNN требуется минимум около 50 узлов. При менее чем 20 узлах модель не может изучить надёжные представления, и более подходящим является традиционный анализ на основе центральности. Для графов с миллионами узлов требуются методы выборки соседей мини-пакетами (как в GraphSAGE) или методы разбиения графов для поддержания приемлемого использования памяти.

Похожие методы

Источники

  1. Kipf, T.N. & Welling, M. (2017). Semi-Supervised Classification with Graph Convolutional Networks. International Conference on Learning Representations (ICLR).

    Открыть ссылку DOI
    Скопировано.
  2. Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., & Bengio, Y. (2018). Graph Attention Networks. International Conference on Learning Representations (ICLR).

    Открыть ссылку DOI
    Скопировано.
  3. Hamilton, W.L. (2020). Graph Representation Learning. Morgan & Claypool.

    Открыть ссылку DOI
    Скопировано.