Демистификация графовых нейронных сетей — часть 1

Графическое машинное обучение: обзор

Ключевые понятия для начала работы

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

В этом посте мы:

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

Что такое графики?

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

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

  1. Узлы, представляющие сущности (иногда называемые вершинами),
  2. Отношения, представляющие ассоциации или взаимодействия между узлами (иногда называемые ребрами или связями), и
  3. Свойства, представляющие атрибуты узлов или связей.

Что такое графическое машинное обучение (GML)?

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

Один из лучших способов понять GML — изучить различные типы задач машинного обучения, которые он может выполнять. Я разбиваю это на контролируемое и неконтролируемое обучение ниже.

Контролируемые задачи GML

На приведенной ниже диаграмме показаны три наиболее распространенные задачи GML для обучения с учителем:

Чтобы расширить дальше:

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

Неконтролируемые задачи GML

Ниже приведены четыре наиболее распространенных задачи GML для обучения без учителя:

Подробнее об этом:

  1. Обучение представлению. Уменьшение размерности при сохранении важных сигналов является центральной темой для приложений GML. Обучение представлению графа делает это явным образом, создавая низкоразмерные признаки из структур графа, обычно для использования их для последующего исследовательского анализа данных (EDA) и ML.
  2. Обнаружение сообщества (кластеризация для отношений): Обнаружение сообщества — это метод кластеризации для выявления групп плотно связанных узлов в графе. Обнаружение сообщества имеет различные практические применения в обнаружении аномалий, мошенничестве и следственной аналитике, анализе социальных сетей и биологии.
  3. Сходство. Сходство в GML означает поиск и измерение похожих пар узлов в графе. Сходство применимо ко многим вариантам использования, включая рекомендации, разрешение сущностей, а также обнаружение аномалий и мошенничества. Общие методы подобия включают алгоритмы сходства узлов, предсказание топологической связи и K-ближайший-соседний (KNN).
  4. Центральность и поиск путей. Я сгруппировал их вместе, поскольку они, как правило, меньше связаны с задачами машинного обучения и больше с аналитическими показателями. Тем не менее, они по-прежнему технически подходят здесь, поэтому я расскажу о них для полноты картины. Центральность находит важные или влиятельные узлы в графе. Центральность вездесуща во многих случаях использования, включая обнаружение мошенничества и аномалий, рекомендации, цепочку поставок, логистику и проблемы с инфраструктурой. Поиск пути используется для поиска путей с наименьшей стоимостью на графе или для оценки качества и доступности путей. Поиск пути может принести пользу во многих случаях использования, связанных с физическими системами, такими как логистика, цепочка поставок, транспорт и инфраструктура.

Как сжатие является ключом к GML

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

Рассмотрим обычный граф, представленный матрицей смежности, квадратной матрицей, в которой каждая строка и столбец представляют узел. Если отношение идет от узла A к узлу B, ячейка на пересечении строки A и столбца B равна 1; в противном случае он равен 0. Ниже приведены иллюстрации некоторых небольших правильных графов и их матриц смежности.

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

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

Если бы вы могли использовать эти разреженные структуры данных непосредственно для машинного обучения, вам не понадобились бы GNN или какой-либо GML — вы просто включили бы их как функции в обычные модели ML. Однако это невозможно. Он не будет масштабироваться и даже вызовет математические проблемы, связанные со сходимостью и оценкой, что сделает модели машинного обучения плохо определенными и невозможными. В результате фундаментальным ключом к GML является сжатие этих структур данных; возможно, в этом весь смысл GML.

Как выполнить сжатие? - Подходы к графическому машинному обучению

На самом высоком уровне существуют три подхода GML для выполнения этого сжатия.

Классические графовые алгоритмы

Классические графовые алгоритмы включают в себя такие вещи, как PageRank, Лувен и Кратчайший путь Дейкстры. Их можно использовать независимо для неконтролируемого обнаружения сообщества, подобия, центральности или поиска пути. Результаты классических алгоритмов также можно использовать в качестве признаков для обычных последующих моделей, таких как линейная и логистическая регрессии, случайные леса или нейронные сети для выполнения задач GML.

Классические графовые алгоритмы, как правило, просты, с ними легко начать работу, они относительно интерпретируемы и объяснимы. Однако они могут потребовать больше ручной работы и специальных знаний (SME), чем другие подходы GML. Это делает классические графовые алгоритмы хорошим первым выбором для экспериментов и разработки, помогая понять, что лучше всего работает на вашем графе. Они также могут хорошо справляться с более простыми задачами, но более сложные варианты использования могут потребовать перехода к другому подходу GML.

Встраивания графиков, не относящиеся к GNN

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

Встраивание графов включает в себя создание векторов числовых или двоичных признаков для представления узлов, отношений, путей или целых графов. Главный из них — встраивание узлов — является одним из самых фундаментальных и широко используемых. Основная идея состоит в том, чтобы сгенерировать вектор для каждого узла таким образом, чтобы сходство между векторами (например, скалярное произведение) аппроксимировало сходство между узлами в графе. Ниже представлен наглядный пример небольшой сети каратэ-клубов Zachary’s. Обратите внимание, как матрица смежности сжимается до двухмерных векторов вложения для каждого узла и как эти векторы группируются вместе, чтобы отразить структуру сообщества графа. Большинство реальных вложений будут иметь более двух измерений (от 128 до 256 или выше) для представления больших реальных графов с миллионами или миллиардами узлов, но основная интуиция остается той же.

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

Встраивания без GNN могут выиграть от снижения ручной работы и требуемого SME по сравнению с классическими алгоритмами графа. Хотя вложения, отличные от GNN, часто требуют настройки гиперпараметров для правильной работы, их, как правило, легче автоматизировать и обобщить для разных графов. Кроме того, некоторые встраивания не-GNN, такие как FastRP и HashGNN, могут невероятно хорошо масштабироваться для больших графов на обычном оборудовании, поскольку они не требуют обучения модели. Это может быть огромным преимуществом по сравнению с подходами на основе GNN.

Однако вложения, отличные от GNN, также имеют некоторые компромиссы. Они менее интерпретируемы и объяснимы, чем классические графовые алгоритмы, из-за задействования более обобщенных математических операций. Они также обычно являются трансдуктивными, хотя недавние улучшения в Neo4j Graph Data Science позволяют некоторым из них эффективно вести себя как индуктивные в определенных приложениях. Мы рассмотрим трансдуктивные и индуктивные настройки более подробно позже в этой серии; это связано со способностью прогнозировать новые невидимые данные и является важным моментом рассмотрения для GML.

Графические нейронные сети (GNN)

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

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

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

Подробнее о GNN я расскажу в своем следующем блоге GNN: что они собой представляют и почему они важны. Тем временем, если вы хотите начать работу с графовым машинным обучением, ознакомьтесь с Neo4j Graph Data Science. Специалисты по данным и инженеры могут найти техническую документацию для начала работы здесь.

Подведение итогов

Основные выводы из этого поста:

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