Эта серия постов посвящена концепции и приложениям графовых нейронных сетей (GNN), которые представляют собой модель машинного обучения, применяемую к графоструктурированным данным. Серия состоит из трех частей:
- Часть I объясняет, что такое графически структурированные данные и как они представлены. В этой части также представлена концепция графового машинного обучения и GNN.
- Часть II содержит более подробную информацию о варианте GNN, называемом графовой сверточной сетью (GCN).
- Часть III, которая является этой частью, описывает различные приложения GNN к реальным данным, классифицированные по уровням задач, упомянутым в первой части.
1. Задачи на уровне узла
Задача уровня узла направлена на предсказание некоторых свойств узлов во входных данных графа. Прогнозы могут быть дискретными метками классов, т. е. классификацией узлов, или непрерывными величинами, т. е. регрессией узлов.
1.1 Классификация узлов
Клуб карате Закари. Популярным примером классификации узлов является задача клуба карате Закари [1]. В этой задаче дан граф, описывающий социальные отношения между 34 членами клуба каратэ, включая администратора и инструктора. Преимущество между двумя участниками означает их взаимодействие вне клуба. После серьезного конфликта между админом и инструктором клуба клуб разделился на две части; половина участников присоединилась к новому клубу, основанному инструктором, а остальные остались с администратором, который нанял нового инструктора для обучения участников. Задача состоит в том, чтобы предсказать, в какой клуб (старый или новый) решил вступить каждый участник, кроме админа и инструктора.
Классификация научных статей.Еще одно возможное применение графового машинного обучения — классифицировать тему научной статьи по графу, описывающему отношения цитирования между статьями. Узел на графике представляет научную статью. Каждый узел связан с вектором признаков, например, взвешенным вектором слов TF/IDF или бинарным вектором, обозначающим, содержит ли статья некоторые ключевые слова. Ребро на графе, которое является неориентированным и невзвешенным, представляет собой цитирование. Два известных набора данных для этой задачи включают наборы данных Cora и PubMed. В наборе данных Cora приведен график, представляющий работы по машинному обучению с семью метками классов (например, генетические алгоритмы, нейронные сети, обучение с подкреплением). Он состоит из 2708 узлов и 5429 ребер. В наборе данных PubMed приведен более крупный граф с 19 717 узлами и 44 338 ребрами, но количество меток классов для прогнозирования меньше, всего три класса (например, статьи об экспериментальном диабете, диабете 1-го типа и диабете 2-го типа). Пример использования графового ML для решения этих проблем приводится в статье Monti et al. [2].
1.2 Регрессия узла
Прогнозирование трафика. Недавно Cui et al. [3] сообщили о применении графовой нейронной сети (GNN) для прогнозирования трафика. Граф используется для моделирования состояния трафика дорожной сети, в котором узел представляет собой станцию мониторинга, а ребро представляет собой сегмент дороги, описывающий, как связаны две станции мониторинга. Каждая станция мониторинга использует некоторые датчики для получения информации об условиях движения (например, скорости движения, времени в пути, объеме). Учитывая исторические условия движения и структуру дороги, представленную на графике, Cui et al. [3] обучила GNN обрабатывать график и прогнозировать будущие условия трафика на каждой станции мониторинга (рис. 1).
2. Пограничные задачи
В то время как задача на уровне узла нацелена на прогнозирование свойства каждого узла, задача на уровне ребра фокусируется на прогнозировании существования ребра между двумя узлами или прогнозировании некоторых свойств ассоциации с ребром на входе графа. Задачи граничного уровня часто называют проблемами прогнозирования ссылок.
2.1 Прогнозирование ссылок
Система рекомендаций. Совместная фильтрация — это подход к созданию системы рекомендаций. Он может предсказать, как пользователю понравится целевой элемент, на основе информации о предпочтениях или оценках многих других пользователей. Эта рейтинговая информация может быть представлена в виде матрицы элементов пользователя, в которой элемент (i, j) в матрице указывает рейтинг пользователяi для элемента j. Обычно эта матрица является неполной, поскольку мы не можем собрать эту информацию от всех пользователей по всем элементам; поэтому требуется метод завершения матрицы. Как показано на рис. 2, van den Berg et al. [4] предложил рассматривать эту проблему как задачу прогнозирования ссылок. Двудольный график пользователей и элементов создается на основе наблюдаемых оценок рейтинга в незавершенной матрице рейтинга. Затем этот график передается в обученный GNN для прогнозирования оценок рейтинга ненаблюдаемых ссылок.
Создание графа сцены: Ян и др. [5] сделал попытку использовать GNN для создания графа сцены для представления контента во входном изображении. Как показано на рис. 3, их метод сначала применяет детектор объектов для обнаружения объектов, появляющихся на входном изображении. Исходный граф, в котором узел представляет обнаруженный объект, и каждый узел соединен друг с другом ребром. Затем исходный граф обрезается, чтобы удалить маловероятные отношения между объектами. Затем используется сверточная сеть графа на основе внимания (GCN) для обработки сокращенного графа и прогнозирования меток ребер, которые представляют отношения (например, рядом, позади, рядом) между объектами.
3. Задачи графического уровня
Как описано в предыдущих разделах, задачи уровня узла и уровня ребра предсказывают некоторые свойства или значения, связанные с каждым узлом или каждым ребром соответственно. Однако задача на уровне графа рассматривает входной граф как единое целое и стремится предсказать его свойства. С одной стороны, если предсказываемое свойство имеет метки дискретного класса, мы называем эту задачу задачей классификации графа. С другой стороны, если он направлен на предсказание непрерывного свойства графа, он называется задачей регрессии графа. Кроме того, задача на уровне графа может быть направлена на сравнение двух входных графов и вычисление расстояния или сходства между ними. Такая задача называется сопоставлением графов.
3.1 Классификация графиков
Классификация изображений: Monti et al. [2] сообщили о применении графового ML для решения задачи классификации изображений. Они экспериментировали с хорошо известным набором данных классификации рукописных цифр под названием MNIST. Входное изображение представляется в виде графика. Как показано на рис. 4, они экспериментировали с двумя структурами графа: 1) структурой регулярной сетки, в которой каждый пиксель, представленный в виде узла, соединен со своими восемью соседями по сетке, и 2) структурой суперпикселя, в которой узел представляет суперпиксель (т. е. группа соседних пикселей, принадлежащих одному и тому же сегменту), и между двумя соединенными суперпикселями существует граница. GCN с тремя сверточными слоями графа, чередующимися со слоями объединения графов, используется для обработки входного графа, чтобы предсказать его метку класса.
Визуальный ответ на вопрос: Teny et al. [6] предложил метод на основе GNN для решения задачи визуального ответа на вопрос (VQA). В их настройках VQA даются два входа, т. Е. 1) входное изображение сцены и 2) вопрос, связанный с изображением сцены, а выходом является метка класса ответа из заранее определенного списка возможных ответов. Как показано на рис. 5, два графа, а именно граф сцены и граф вопроса, передаются в GNN для обработки графов и, наконец, предсказания ответа на входной вопрос с учетом изображения сцены. На графе сцены узел представляет обнаруженный объект на сцене, а ребро представляет пространственные отношения между двумя объектами. На графе вопросов узел представляет слово во входном вопросе, а ребро представляет тип синтаксической зависимости, например, определитель (det), наречный модификатор (advmod) или номинальное подлежащее (nsubject) между двумя словами. Их модель GNN поддерживает различные типы ответов, включая да/нет, число и другие.
3.2 График регрессии
Предсказание молекулярных свойств:Yang et al. [7] сообщили о применении GCN для предсказания молекулярных свойств данной молекулы, представленной в виде структуры графа, в которой узел представляет собой атом в молекуле, а ребро представляет собой химическую связь между двумя атомами. Свойства атома (например, атомная масса, тип атома, количество связей, в которых участвует атом) используются для построения вектора признаков для его описания. Точно так же каждая химическая связь связана с вектором признаков, описывающим ее свойства, такие как тип связи. Предсказываемые молекулярные свойства могут быть представлены либо в виде меток дискретных классов (классификация), либо в виде непрерывных величин (регрессия). Эксперименты с 19 общедоступными и 16 частными промышленными данными показывают многообещающие результаты при сравнении других моделей машинного обучения, таких как случайные леса или нейронные сети с прямой связью.
3.3 Сопоставление графиков
Классификация рукописных букв/слов: Riba et al. [8] сообщили об использовании метода на основе GNN для вычисления расстояния редактирования между двумя графами (рис. 6). Это расстояние редактирования говорит нам, насколько похожи два графика. Они используют сиамскую сеть, состоящую из двух идентичных GNN, для решения этих задач сопоставления графов. Они также сообщили о применении своей сети для задач классификации рукописных букв и слов. Как показано на рис. 7, буква или слово представлены в виде графа. В этом случае узел представляет собой двумерное положение точки на букве или слове, а ребро обозначает соединение между двумя точками. Классификация выполняется путем подачи графика неизвестной буквы/слова и графика, представляющего каждую известную букву/слово, зарегистрированных в их системе, для вычисления их сходства. Метка класса буквы/слова, которая дает наилучший показатель сходства, является прогнозируемым ответом.
4. Резюме
Мы представили несколько приложений GNN, классифицированных по уровням задач, то есть уровням узлов, ребер и графов. В каждом приложении мы объяснили, какие данные должны быть представлены в виде графа, какие узлы и ребра представляют, и как использовать GNN для решения задачи. В приведенной выше таблице собраны все приложения, которые мы обсуждали в этой заключительной части серии.
Рекомендации
[2] Ф. Монти, Д. Боскаини, Дж. Маски, Э. Родола, Дж. Свобода и М. М. Бронштейн, «Геометрическое глубокое обучение на графах и многообразиях с использованием смешанных моделей CNN, 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) , 2017. С. 5425–5434.»
[3] З. Цуй, К. Хенриксон, Р. Ке и Ю. Ван, «Сверточная рекуррентная нейронная сеть графа трафика: платформа глубокого обучения для изучения и прогнозирования трафика в масштабе сети, в IEEE Transactions on Intelligent Transport Systems, т. 21, нет. 11, стр. 4883–4894, ноябрь 2020 г.»
[4] Р. ван ден Берг, Т. Н. Кипф и М. Веллинг, «Пополнение сверточной матрицы графа, препринт arXiv, arXiv: 1706:02263, 2017.»
[5] Дж. Ян, Дж. Лу, С. Ли, Д. Батра и Д. Парих, «Graph R-CNN для генерации графа сцены, В: В. Феррари, М. Хеберт, К. Сминчисеску и Ю. Вайс (ред. ) Computer Vision — ECCV 2018, Lecture Notes in Computer Science, vol 11205, Springer, Cham, 2018.»
[6] Д. Тени, Л. Лю и А. Ван Ден Хенгель, «Графические представления для визуальных ответов на вопросы, Конференция IEEE по компьютерному зрению и распознаванию образов (CVPR), 2017 г., 2017 г., стр. 3233– 3241.»
[7] К. Ян, К. Суонсон, В. Джин, К. Коли, П. Эйден, Х. Гао, А. Гусман-Перес, Т. Хоппер, Б. Келли, М. Матеа, А. Палмер, В. Сеттелс, Т. Яаккола, К. Дженсен и Р. Барзилай, «Анализ изученных молекулярных представлений для предсказания свойств, Журнал химической информации и моделирования, том. 59, нет. 8, стр. 3370–3388, 2019.»
[8] П. Риба, А. Фишер, Дж. Льядос и А. Форнес, «Изучение расстояний графа с помощью нейронных сетей с передачей сообщений, 24-я Международная конференция по распознаванию образов (ICPR), 2018 г., 2018 г., стр. 2239–2244. .»
Автор: Sertis Vision Lab
Первоначально опубликовано наhttps://www.sertiscorp.com/
