Демистификация машинного обучения на основе графов

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

Графики для представления данных: пример

Давайте рассмотрим простой пример: сеть цитирования CORA [2] — это набор данных, который содержит набор статей и их цитирования: он состоит из 2708 узлов,где каждый узел представляет документ/статью, а ребра — связь между двумя документами через цитаты. Кроме того, для каждого документа существует набор слов, указывающий на наличие слова в документе (1433словарь слов). В то время как пакет слов — это разреженное представление документов, встраивание документов (например, Doc2Vec) может дать нам плотное представление, которое более удобно для алгоритма, основанного на расстоянии.

На рис.1 мы видим 6 статей, которые разделены между двумя группами по информатике (C) и физике (P). Если бы нам нужно было угадать метки бумаги 1 и 6, одним из способов было бы использовать простую модель ML, используя другие помеченные примеры, просто основанные на представлении документов в виде набора слов (или получить еще больше фантазий и создать вложения для эти слова и документы), но нужно ли нам это? Просто взглянув на отношения между узлами, а не на характеристики узлов, мы можем отнести эти две статьи к соответствующим группам, возможно, даже не заглядывая в их словесное содержание.

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

Сигналы графика = отдельные функции узла + структура графика

Графики также могут представлять разнородные точки данных и включать их в различные алгоритмы; например, в приведенном выше примере представьте, что мы также хотим представлять авторов:

А как насчет обучения?

Но как ML может извлечь из этого выгоду? разве нам не нужны табличные данные для многих стандартных алгоритмов машинного обучения? ответ - да, методы ML все еще могут использовать преимущества графического представления через:

— Создание вложений графиков для одновременного захвата узловых функций и структуры графика и их использования в качестве табличных функций.

— Использование алгоритмов Graph native Learning.

— Использование графовых нейронных сетей (GNN)

Встраивания графиков

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

Но как еще мы можем закодировать структуру графа? давайте просто прогуляемся наугад…

Представьте, что мы просим авторов в цифре. 1, чтобы совершить несколько прогулок по графу, по случайным путям, теперь можете ли вы сказать, ближе ли автор a к автору b, чем автор d, просто взглянув на эти пройденные пути? правильно! если два узла находятся ближе на графе, они, вероятно, разделят больше путей во время случайных блужданий. Один из способов количественной оценки этой концепции — преобразовать обходы в последовательности посещенных узлов и применить алгоритм word2vec для создания встраивания этих последовательностей узлов (вместо последовательностей слов)… довольно аккуратно, да? В дополнение к узлам мы также можем встраивать ребра и подграфы, но вложения узлов являются наиболее практичным типом вложений графов.

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

Алгоритм Node2Vec [3] просто упаковывает шаги, описанные выше (предвзятые случайные блуждания, за которыми следует Word2Vec) под одним зонтиком. Хотя Node2Vec, вероятно, является наиболее интуитивно понятным алгоритмом встраивания узлов, это не единственный способ: Fast Random Projection (FastRP) [4] — это алгоритм встраивания узлов, основанный на лемме Джонссона-Линденштрауса, согласно которой можно проецировать n векторы произвольной размерности в размерности O(log(n)) и при этом сохраняют попарные расстояния между точками: даже случайная линейная проекция может удовлетворять этому свойству. Node2Vec может стать очень медленным, поскольку мы увеличиваем длину обхода, и fastRP может быть быстрой альтернативой, хотя выбор оптимальных весов итераций не всегда интуитивно понятен.

Конечно, существует больше алгоритмов встраивания узлов в дополнение к встраиваниям ребер или даже графов/подграфов, но они не так распространены.

Графическое обучение

Алгоритмы обучения на основе графов используют структуру графа для обучения. Хорошо известные собственные графовые алгоритмы:

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

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

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

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

Граф нейронных сетей

GNN — это модели глубокого обучения, которые нацелены на захват структуры графа в дополнение к обычным функциям узла. Вы можете сказать, что рекуррентные нейронные сети (RNN) и сверточные нейронные сети (CNN) уже кодируют некоторый уровень структуры в сети, так что же такого особенного в GNN? большинство реальных сетей не имеют ни входных измерений фиксированного размера, ни даже окрестностей фиксированного размера, кроме того, порядок узлов также не является фиксированным; В отличие от RNN и CNN, GNN инвариантны к перестановкам, а также работают с произвольными входными данными и размером окрестности. Нам понадобится полный курс для выпускников, чтобы охватить GNN, но здесь мы рассмотрим их наиболее важные операции, фильтрацию и объединение, а также одну из популярных архитектур GNN: GraphSAGE.

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