Часть 2. Обзор популярных методов GNN

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

Сверточная сеть Graph (GCN)

GCN является расширением сверточных нейронных сетей (CNN) (которые являются одним из популярных методов глубокого обучения и доказали свою эффективность в решении сложных задач в приложениях для обработки изображений, видео и голоса/речи). Обратите внимание, что в CNN мы обычно работаем с входными данными фиксированного размера (например, голосовой последовательностью продолжительностью 0,5 секунды или изображением 512x512) и с регулярной выборкой, такой как одномерные или двумерные сетки, где есть пространственная локальность и порядок. Однако данные графа или сети имеют более сложную структуру, произвольный размер соседства узлов и отсутствие фиксированного порядка узлов. GCN (см. Defferrard, et al. 2016 и Kipf, et al., 2017) — один из первых методов, разработанных для анализа GNN.

Традиционные GCN работают путем преобразования структуры графа или информации о соседстве/смежности узлов графа в (разреженную и двоичную) матрицу (называемую матрицей смежности, A), а затем с помощью в качестве операции сбора или сбора данных для выбора и усреднения одношаговых окрестностей. Предположим, что каждый узел графа описывается числовым вектором признаков длины M, а все векторы признаков узлов (которые могут включать в себя различные атрибуты, описывающие каждый узел) суммируются и отображаются матрицей X размером N × M, где N — количество узлов в графе.

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

Обратите внимание, что повторение нескольких вышеупомянутых шагов приводит к распространению сетевой информации по узлам графа, что в конечном итоге изменяет характеристики узла. Как только получено окончательное вложение сети (что означает, что после i шагов или использования i слоев GCN, после вычисления вложений узлов H(i) ), обнаружение аномалии в узлах или ребрах может быть выполнено с помощью традиционных методов обнаружения аномалий в ML (рис. 1 и 2). Мы могли бы применить полносвязный (FC) или слой многослойного персептрона (MLP) к изученным функциям графа H(i), чтобы принять окончательное решение. Количество шагов, i, которое определяет желаемый уровень соседства, является выбранным параметром дизайна.

Существует несколько версий GCN, в том числе простая свертка графа (SGC), реляционная GCN (R-GCN) и сеть внимания к графу (GAT). Метод R-GCN позволяет иметь разные отношения узлов, т. е. ребра могут иметь разные типы.

MixHop: применение многомасштабных фильтров соседства при агрегировании

В качестве расширения GCN в методе MixHop Abu-El-Haija, et al. (2019), многомасштабное соседство включается в фильтр GCN путем многократного смешивания представлений признаков соседей в нескольких масштабах. Для каждого слоя в MixHop мы используем соседство переходов 0, 1, 2, …, N и позволяем слою научиться агрегировать все эти переходы одновременно (см. рис. 3 и 4).

Нейронные сети передачи сообщений (MPNN)

MPNN (Gilmer, et al., 2017) является обобщением GCN. Он может включать в себя разнородные графы, что позволяет использовать функции узла, а также функции края, и обеспечивает контроль над тем, когда и как передаются сообщения.

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

В MPNN каждый узел имеет вложение или состояние (или скрытое состояние, обозначаемое h). Начиная с начального встраивания, сообщения генерируются для каждой пары ребер в графе:

См. рис. 5. Здесь мы использовали оператор суммирования в качестве функции агрегирования, но есть и другие варианты.

Обратите внимание, что функция считывания R(.), как мы написали здесь, должна быть инвариантной к перестановке порядков узлов.

Многие методы могут быть описаны как реализация модели MPNN, например, популярная модель нейронной сети с вентилируемым графом (GGNN) Li, et al. (2016), который использует закрытую рекуррентную единицу (GRU) в качестве функции обновления.

Выборка узлов на больших графиках

Чтобы выполнить встраивание графа или изучить представление графа, кажется необходимым использовать все узлы и ребра входного графа, однако это не всегда осуществимо из-за вычислительных затрат. Возможным решением для масштабирования встраивания графов в большие графы является выполнение выборки по соседству или выборки по соседству. Основная идея заключается в том, что для каждого узла вместо использования всей информации о соседстве (т. е. обо всех подключенных соседях k-hop) мы выбираем или отбираем их подмножество для выполнения агрегирования, необходимого для встраивания графа. Например, метод DeepWalk Perozzi, et al. (2014), использовали усеченные случайные блуждания, а затем кодировали их с помощью нейронной сети для получения вложений узлов. Длина обхода, а также количество случайных обходов фиксированы и ограничены, в основном исследуя информацию о локальном графе вокруг каждого узла. В каждом узле обхода метод равномерно (т. е. с равной вероятностью) выбирает следующий шаг среди соседей. Метод GraphSAGE, предложенный Hamilton, et al. (2017) и презентация под названием Майнинг и обучение с помощью графиков в масштабе от Mirrokni, et al. (2020) предлагается для дальнейшего чтения (см. рис. 6).

Другой метод, названный LINE (от Tang, et al., 2015), сохраняет не только отношения первого порядка (наблюдаемая сила связи), но и отношения второго порядка (общие структуры соседства вершин). В методе Node2Vec (от Grover and Leskovec, 2016) используются две разные стратегии выборки для вершин (выборка в ширину и выборка в глубину). Для очень больших сетей граф можно построить и с помощью таких методов, как Grale (автор Halcrow, et al., 2020).

PPRGo (Personalized Page Rank Go): ускорение крупномасштабных графиков с использованием агрегированных вычислений в автономном режиме

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

PageRank — это метод оценки важности веб-страниц с использованием структуры ссылок в Интернете. Это глобальный рейтинг веб-страниц, основанный на их расположении в структуре веб-графика. Его обновленный метод, названный Personalized PageRank (или PPR), см. Andersen, et al., (2016), показал себя как хорошую альтернативу явной передаче сообщений, и его можно использовать для включения информации о многошаговом соседстве узел. Распространение информации на основе PPR соответствует множеству слоев агрегации соседства, где с каждым слоем влияние узла затухает экспоненциально. Однако, поскольку он выполняет дорогостоящую версию степенной итерации, его нелегко масштабировать до больших графов.

Чтобы решить проблему вычислительно затратных агрегаций во время выполнения, метод PPRGo (от Bojchevski, et al., 2020) предварительно вычисляет агрегации (векторы PPR), тем самым экономя вычисления во время выполнения (см. Mirrokni, et al. (2020). )" также). Шаги:

  • Во-первых, мы вычисляем векторы PPR в автономном режиме в масштабе.
  • Затем мы обучаем простую модель MLP, которая принимает функции узла и выводит логиты.
  • Мы агрегируем эти логиты, используя веса «внимания» верхних узлов K в векторе PPR, и используем агрегацию для расчета потерь.
  • При выводе мы используем «степенную итерацию» с ~2–3 итерациями для вычисления аппроксимированного вектора PPR.
  • Аппроксимированный PPR вводится в модель с узлами для получения окончательного прогноза.

PPRGo объединяет наиболее важные узлы в окрестности N-перехода, используя только один шаг вычислений.

Динамическое представление/встраивание графа

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

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

О методах обучения и логического вывода на динамических графах см. Сети временных графов (TGN) для глубокого обучения на динамических графах от Rossi, et al. (2020) и опрос Kazemi, et al. (2020), где описываются различные методы с точки зрения кодировщика-декодера. Например, модель кодера генерирует временные вложения узлов, а декодер является моделью, зависящей от задачи, и может быть, например, моделью NN, которая использует временные вложения соседних узлов в качестве входных данных для выполнения классификации узлов.

Существует несколько других методов встраивания и использования динамических графов, в том числе Lei et al. (2020), Goyal et al. (2019), который представил метод встраивания Dyngraph2vec, который использует рекуррентную нейронную сеть (RNN) для сбора временной информации и изучения встраивания с использованием модели автокодировщика, и Yu et al. (2018), который представил метод встраивания NetWalk.

Связанная литература по обнаружению мошенничества и злоупотреблений

Существует несколько связанных графических работ по обнаружению мошенничества или злоупотреблений. Ли и др. (2020) опубликовал работу по использованию GCN для понимания и классификации финансовых данных. В работе Xu, et al. (2021) о выявлении мошенничества с потребительскими кредитами с помощью GCN. Рао и др. (2020) представил метод, состоящий из части детектора мошенничества и части объяснения для создания графической визуализации (для отображения мошенничества в сравнении с законными транзакциями) из разнородных графических данных, а также параметров детектора. Ванг и др. (2021) представили совместное моделирование графической и временной информации для крупномасштабных графов. Информация о времени и последовательные события для каждого узла кодируются с использованием модели RNN. Затем выходные данные для каждого узла из RNN распространяются по графу с использованием GNN, который использует сетевую информацию в графе, чтобы окончательно принять решение об обнаружении злоупотреблений или выполнить прогнозирование меток для немаркированных пользователей.

Заключение

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

Я хотел бы поблагодарить Генри Чена, Прию Венкат и Джеймса Танга (из Walmart) за то, что они прочитали черновик и предоставили свои содержательные комментарии, которые помогли улучшить этот пост.