От структур данных к алгоритмам: предварительное изучение методов графовых сетей

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

Сердце машины Оригинал, автор: Чжу Цзихао, редактор: Цин Линь.

Автор этой статьи, Чжу Цзихао, студент магистратуры Института информационных технологий Китайской академии наук, его основные направления исследований — графовые нейронные сети, визуальные ответы на вопросы и визуальный диалог.

что такое график

Граф — это общая структура данных, используемая для представления объектов и отношений между ними. Среди них объекты также называются узлами или вершинами, а отношения описываются ребрами. В математике это обычно представляется как G=(V,E,A,X), где V={v1,v2...,vn} — набор узлов, E=e_ij — набор ребер, а A является размером |V|Матрица смежности ×|V|используется для представления отношения связи между узлами.Если e_ij∈E, то A_ij=1, X является матрицей признаков размера |V|×d, а i-я строка X X_i: представляет i-е свойство атрибута узлов i, где d — размерность атрибута.

Зачем нужно применять методы машинного обучения на графиках

Графы — это универсальный язык для описания и моделирования сложных систем, повсеместно встречающихся в реальном мире. Например, социальные сети, такие как Facebook и Twitter, представляют собой социальную сеть между людьми; белковые молекулы в человеческом теле составляют биологическую сеть; различные мобильные терминалы представляют собой коммуникационную сеть; интеллектуальное оборудование Интернет вещей (Интернет вещей) образуются между ними, а автомобильные, железные дороги и пути между городами составляют транспортную сеть (Transportation Network) и т.д. Таким образом, он также катализирует ряд задач интеллектуального анализа данных на графиках, таких как рекомендация заинтересованных друзей пользователям, оценка белковых структур, прогнозирование потока трафика, обнаружение аномальных учетных записей и так далее. Однако объем данных в реальных графах огромен, с сотнями миллионов узлов, а внутренняя топологическая структура сложна, поэтому традиционные методы анализа графов, такие как кратчайший путь, DFS, BFS, PageRank и другие алгоритмы, трудно применить к ним. эти задачи. Ввиду широкого применения машинного обучения в области изображений и текстов некоторые исследователи пытаются сочетать методы машинного обучения с графическими данными, что постепенно стало повальным увлечением в области машинного обучения.

Обучение представлению сети, определение вложений графов

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

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

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

На самом деле термины «встраивание в граф», «встраивание в сеть», «обучение с графовым представлением» и «обучение с сетевым представлением» относятся к одному и тому же понятию. Учитывая граф $G=(\mathbf{V,E,A,X})$, встраивание графа должно изучить отображение узлов в векторы: $f:v_i\to \mathbf{y}_i \in R^ d$ , где $d

Классификация методов встраивания графов

Самая большая особенность данных графа заключается в том, что между узлами существует связь, что указывает на то, что узлы в графе не являются полностью независимыми. В дополнение к отношениям связи между узлами, сами узлы также могут содержать информацию, такую ​​как текстовая информация, соответствующая узлам веб-страницы в Интернете.Эти характеристики требуют учета многих факторов при встраивании графа. Из информации, необходимой для обучения, обычно есть три основных источника информации: структура графа, атрибуты узлов и метки узлов, которые можно разделить на неконтролируемое встраивание графа и частично контролируемое встраивание графа на основе этого; другой основан на разных входных данных. , Разделение, например, по направлению края, является ли это гетерогенной сетью и другими свойствами. Однако эти два подразделения не подходят, потому что основное различие между текущими алгоритмами встраивания графов заключается в типе алгоритма, а платформы для одного и того же типа алгоритма похожи.Поэтому эта статья основана на Гамильтоне и др. [1] и Goyal и др. [2] Обзор встраивания графов, обобщение методов встраивания графов в встраивание графов на основе матричной факторизации, встраивание графов на основе случайных блужданий и встраивание графов на основе нейронных сетей (т. е. графовые нейронные сети).

Встраивание графа на основе матричной факторизации

Метод, основанный на разложении матрицы, заключается в том, чтобы выразить отношения между узлами в виде матрицы, а затем разложить матрицу для получения вектора вложения. Матрицы, обычно используемые для представления отношений узлов, включают матрицу смежности, матрицу Лапласа, матрицу вероятности перехода узла, матрицу атрибутов узла и так далее. В зависимости от свойств матрицы применимы различные стратегии декомпозиции. В основном включают локальное линейное вложение (LLE) [3], лапласовские собственные карты [4], SPE [5], GraRep [6] и т. д.

Алгоритм LLE на самом деле является разновидностью многообразного обучения.Алгоритм LLE считает, что каждая точка данных может быть построена с помощью линейной взвешенной комбинации ее соседних узлов. После приведения размерности к низкоразмерному пространству эта линейная связь все еще сохраняется. Лапласианские собственные карты чем-то похожи на LLE.Интуитивная идея состоит в том, чтобы надеяться, что точки, которые связаны друг с другом (точки, соединенные в графе), находятся как можно ближе в уменьшенном размерном пространстве. Чтобы сделать вложение входного графа низкоразмерным представлением и сохранить глобальную топологию графа, Шоу и др. [5] предложили метод встраивания с сохранением структуры (SPE, Structure Preserving Embedding) для встраивания графов в евклидово представление. пространстве, изучая набор линейных неравенств, ограниченных матрицей ядра низкого ранга, которая фиксирует структуру входного графа. SPE значительно улучшает визуализацию графов и сжатие без потерь, превосходя такие методы, как лапласовские собственные карты. [6] полагал, что учет отношения k-порядка между узлами очень важен для понимания глобальных характеристик сети, а учитывая отношения более высокого порядка, полученное представление сети будет лучше. GraRep изучает представления узлов k-порядка по отдельности посредством декомпозиции SVD, а затем объединяет их в качестве окончательного представления, которое может хорошо отражать отношения между удаленными узлами.

методы, основанные на случайных блужданиях

Методы случайного блуждания использовались для аппроксимации многих свойств графов, включая центральность узлов и сходство. Случайные блуждания полезны, когда граф очень большой или наблюдается только часть графа. Некоторые исследователи предложили технику встраивания, которая использует случайные блуждания по графам для получения представлений узлов, наиболее известными из которых являются DeepWalk[7] и node2vec[8].

DeepWalk предлагается на основе вектора слов word2vec. Когда word2vec обучает векторы слов, в качестве входных данных используется корпус, а входными данными для встраивания графа является весь граф, и они кажутся несвязанными. Но авторы DeepWalk обнаружили, что количество ожидаемых вхождений слов и количество посещений узла случайного блуждания на графе до конца подчиняются степенному закону распределения. Поэтому DeepWalk рассматривает узлы как слова и принимает последовательность узлов, полученную путем случайного блуждания, как предложения, а затем напрямую использует ее в качестве входных данных word2vec для получения встроенного представления узлов. Его структура показана на рисунке 1. Сначала метод случайного блуждания используется для генерации стандартной входной последовательности, последовательность моделируется с помощью модели SkipGram для получения векторного представления узла, а затем используется иерархический softmax для решения задачи. задача многомерного вывода узла. Предложение модели DeepWalk предлагает новую исследовательскую идею для встраивания графов, которую можно рассматривать как триггер всплеска исследований встраивания графов.

node2vec улучшает алгоритм DeepWalk, изменяя способ генерации последовательности случайных блужданий. DeepWalk случайным образом выбирает следующий узел последовательности случайных блужданий в соответствии с равномерным распределением. node2vec рассматривает как поиск в ширину (BFS), так и поиск в глубину (DFS). Гровер и др. обнаружили, что поиск в ширину фокусируется на характеристике локальных особенностей в сети, в то время как поиск в глубину может лучше пройти через всю сеть, отражая однородность между узлами. В частности, node2vec вводит функцию смещения поиска, чтобы сбалансировать эти два метода выборки, и корректирует вероятность следующего перехода с помощью параметров p и q.

Другие методы на основе случайного блуждания включают Walklets, LsNet2vec, TriDNR, HARP, DDRW и другие.

Вложения графов на основе нейронных сетей (Graph Neural Networks)

Другой тип метода — это метод обучения представлению графа, который объединяет нейронные сети и графы, также является одним из самых горячих направлений в прошлом году, мы собирательно называем графовые нейронные сети. The Heart of the Machine дал подробное введение в него.Подробности см. В:Модель графа в эпоху глубокого обучения,Цинхуа опубликовал сводный граф сети,Обзор графовых нейронных сетей в Университете Цинхуа:Модели и приложения,Третий маркер обзора нейронной сети графа:Обзор GNN от IEEE Fellow. Он в основном делится на сверточную сеть графа, сеть внимания графа, сеть создания графа, пространственно-временную сеть графа и автокодер графа. Кроме того, его можно разделить на спектральные методы и космические методы. Поскольку спектральные методы должны разлагать собственные векторы матрицы, подавляющее большинство новых предлагаемых методов основаны на пространстве, то есть на том, как распространяется и агрегируется информация об узлах и ребрах. Изображения и текст, по сути, представляют собой регулярные графы со структурой сетки, поэтому естественно думать о расширении моделей, которые были успешно применены в областях CV и NLP, к графам, таким как векторы слов и свертки графов. В последнее время также появились графовые нейронные сети на основе капсул и Graph U-Net на основе модели U-Net для семантической сегментации изображений.

Применение механизма внимания при встраивании графов

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

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

В таблице 1 обобщаются и сравниваются графовые модели нейронных сетей, основанные на механизме внимания, опубликованные за последние два года в соответствии с входом, выходом и задачей. Ниже приводится обзор нескольких репрезентативных моделей. Подробности см. в статье «Внимание». Модели в графах»: обзор» [9].

Команда Йошуа Бенджио MILA предложила Graph Attention Networks (GAT) [10] в 2018 г. Уровень внимания Graph определен в документе. Путем наложения различных слоев внимания может быть сформирована графовая нейронная сеть любой структуры. Архитектура показана на Рисунок. Последний шаг - вычислить коэффициент внимания $\alpha_{ij}$ узлов-соседей узла i. Здесь по-прежнему используется механизм внимания с несколькими головками. Разные цвета на рисунке представляют разные головы.

В отличие от GAT, который является классификацией узлов, DAGCN [11] используется для задач классификации графов. Модель включает в себя два блока внимания, один такой же, как GAT, который используется для свертки графа для получения представления узлов, а другой представляет собой операцию объединения, основанную на внимании, для получения представления всего графа, а затем ввод представление графа в MLP для получения всего графа Классификация графов. Автор считает, что каждый слой классической GCN может захватывать только структурную информацию о районе k-hop, и только H последнего слоя используется для следующего прогноза.По мере увеличения количества сетевых слоев, много информации будет потерян. Идея слоя внимания, предложенная автором, заключается не только в том, чтобы полагаться на результат k-го прыжка, но и в том, чтобы захватывать ценную информацию с каждого предыдущего прыжка.

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

В основном это реализуется через функцию softmax, а также требует функции, которая может вычислять корреляцию между узлом j и узлом 0 на основе атрибутов узла.Например, реализация GAT такова:

где W — обучаемая матрица параметров, которая отображает атрибуты узла в скрытое пространство, а || обозначает конкатенацию.

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

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

Первые два типа внимания в основном сосредоточены на выборе релевантной информации для интеграции в скрытое представление целевого объекта, в то время как третий тип внимания имеет несколько иную цель и называется ходьбой, основанной на внимании. Например, вложение подграфа строится путем выполнения серии обходов входного графа и использования RNN для кодирования информации о посещенном узле. Скрытое состояние RNN в момент времени t кодирует посещенные узлы с 1 по t. Внимание — это функция $f'(h_t)=r_{t+1}$, вход — скрытое состояние в момент времени t, а выход — ранговый вектор, говорящий нам, какой тип узла мы должны отдать приоритет следующему.

Рамка

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

encoder — это функция:

Сопоставьте узел i с вектором вложения $z_i \in R^d$. decoder — это функция, которая принимает набор вложений узлов и декодирует заданную пользователем статистику графа из этих вложений. Например, декодер может предсказать, существует ли ребро между узлами на основе их вложений, или он может предсказать сообщество, к которому принадлежит узел в графе. В принципе доступно множество декодеров, но в большинстве работ используются парные декодеры:

Когда мы применяем попарные декодеры к паре вложений $(z_i,z_j)$, мы получаем восстановление сходства между $v_i$ и $v_j$ в исходном графе, и цель состоит в том, чтобы минимизировать восстановленное сходство. сходство с исходным изображением:

где SG — определяемая пользователем мера сходства между узлами на графе G. Другими словами, цель состоит в том, чтобы оптимизировать модель кодера-декодера, которая может декодировать попарное сходство узлов SG(v_i, v_j) в исходном графе из низкоразмерных вложений узлов z_i и z_j. Например, можно задать SG(v_i, v_j)=A_{ij}, если узлы смежные, сходство узлов определяется как 1, в противном случае — 0. В качестве альтернативы SG можно определить с точки зрения вероятности того, что случайные блуждания фиксированной длины v_i и v_j коллинеарны на графе G. На практике большинство методов достигают цели реконструкции путем минимизации эмпирических потерь L на множестве D пар узлов:

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

Суммировать

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