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

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

Что такое вложения графа?

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

  • Встраивания вершин: мы кодируем каждую вершину (узел) своим собственным векторным представлением. Мы будем использовать это вложение, когда хотим выполнить визуализацию или прогнозирование на уровне вершин, например визуализация вершин в 2D-плоскости или предсказание новых соединений на основе сходства вершин.
  • Вложения графов. Здесь мы представляем весь граф одним вектором. Эти вложения используются, когда мы хотим делать прогнозы на уровне графа и когда мы хотим сравнить или визуализировать целые графики, например сравнение химических структур.

Позже мы представим несколько часто используемых подходов из первой группы (DeepWalk, node2vec, SDNE) и подход graph2vec из второй группы.

Почему мы используем вложения графов?

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

  • Машинное обучение на графах ограничено. Графы состоят из ребер и узлов. Эти сетевые отношения могут использовать только определенное подмножество математики, статистики и машинного обучения, в то время как векторные пространства имеют более богатый набор инструментов.
  • Вложения - это сжатые представления. Матрица смежности описывает связи между узлами в графе. Это | V | x | V | матрица, где | V | - количество узлов в графе. Каждый столбец и каждая строка в матрице представляют собой узел. Ненулевые значения в матрице указывают, что два узла связаны. Использование матрицы смежности в качестве пространства признаков для больших графов практически невозможно. Представьте себе граф с 1M узлов и матрицей смежности размером 1M x 1M. Вложения более практичны, чем матрица смежности, поскольку они упаковывают свойства узлов в вектор с меньшей размерностью.
  • Векторные операции проще и быстрее, чем сопоставимые операции с графиками.

Вызовы

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

  • Нам нужно убедиться, что вложения хорошо описывают свойства графов. Они должны представлять топологию графа, соединения узлов и окрестности узлов. Производительность прогнозирования или визуализации зависит от качества встраивания.
  • Размер сети не должен снижать скорость процесса встраивания. Графики обычно большие. Представьте себе социальные сети с миллионами людей. Хороший подход к встраиванию должен быть эффективным на больших графах.
  • Существенной проблемой является решение о размерности встраивания. Более длинные вложения сохраняют больше информации, но вызывают более высокую временную и пространственную сложность, чем вложения сортировщика. Пользователи должны идти на компромисс, исходя из требований. В статьях обычно сообщается, что для большинства задач достаточно размера встраивания от 128 до 256. В методе Word2vec выбрали длину встраивания 300.

Word2vec

Прежде чем мы представим подходы к встраиванию графов, я расскажу о методе Word2vec и нейронной сети skip-gram. Они являются основой методов вложения графов. Если вы хотите лучше понять это, я предлагаю проверить этот отличный урок или это видео.

Word2vec - это метод встраивания, который преобразует слова в векторы встраивания. Подобные слова должны иметь похожие вложения. Word2vec использует сеть skip-gram, которая представляет собой нейронную сеть с одним скрытым слоем. Пропускная грамма обучена предсказывать соседнее слово в предложении. Эта задача называется фальшивой, поскольку используется только на этапе обучения. Сеть принимает слово на входе и оптимизируется таким образом, что предсказывает соседние слова в предложении с высокой вероятностью. На рисунке ниже показан пример вводимых слов (отмеченных зеленым) и слов, которые предсказываются. С помощью этой задачи авторы добиваются того, чтобы два похожих слова имели похожие вложения, поскольку вполне вероятно, что два слова с одинаковым значением имеют похожие соседние слова.

Нейронная сеть skip-gram, показанная на рисунке ниже, имеет входной слой, один скрытый слой и выходной слой. Сеть принимает слова с горячим кодированием. Одноразовое кодирование - это вектор с длиной, равной длине словарного словаря, и имеет все нули, кроме одного. Номер один находится на том месте, где в словаре появляется закодированное слово. Скрытый слой не имеет функции активации, его вывод представляет собой вложение слова. Выходной слой - это классификатор softmax, который предсказывает соседние слова. Более подробная информация о скип-грамме доступна в учебнике, о котором я упоминал ранее.

Я представлю четыре подхода к встраиванию графов. Три из них включают узлы, а один - весь граф одним вектором. Они используют принцип встраивания из Word2vec в трех подходах.

Подходы к встраиванию вершин

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

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

Метод в основном состоит из трех шагов:

  • Выборка. Выборка диаграммы осуществляется случайным образом. Выполняется несколько случайных блужданий от каждого узла. Авторы показывают, что достаточно выполнить от 32 до 64 случайных блужданий с каждого узла. Они также показывают, что хорошие случайные блуждания имеют длину около 40 шагов.
  • Обучающая скип-грамма: Случайные прогулки можно сравнить с предложениями в подходе word2vec. Сеть skip-gram принимает узел из случайного блуждания как горячий вектор в качестве входных данных и максимизирует вероятность прогнозирования соседних узлов. Обычно его обучают прогнозировать около 20 соседних узлов - 10 узлов слева и 10 узлов справа.
  • Вычисление вложений: встраивание - это результат скрытого уровня сети. DeepWalk вычисляет вложение для каждого узла в графе.

Метод DeepWalk выполняет случайные блуждания случайным образом, что означает, что вложения плохо сохраняют локальную окрестность узла. Подход Node2vec исправляет это.

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

Остальные шаги встраивания такие же, как у DeepWalk.

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

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

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

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

Суммарные потери в сети рассчитываются как сумма потерь от левого и правого автокодировщика вместе с потерями от средней части.

Подход встраивания графов

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

Graph2vec основан на идее подхода doc2vec, который использует сеть skip-gram. Он получает идентификатор документа на входе и обучается, чтобы максимизировать вероятность предсказания случайных слов из документа.

Подходы Graph2vec состоят из трех шагов:

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

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

Другие подходы к встраиванию

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

  • Подходы встраивания вершин: LLE, собственные карты Лапласа, факторизация графов, GraRep, HOPE, DNGR, GCN, LINE.
  • Подходы встраивания графов: Patchy-san, sub2vec (встраивание подграфов), ядро ​​WL и ядра Deep WL.

использованная литература

[1] Ч. Мэннинг, Р. Сочер, Лекция 2 | Векторные представления Word: word2vec (2017), YouTube.

[2] Б. Пероцци, Р. Аль-Рфу, С. Скиена, DeepWalk: онлайн-обучение социальных представлений (2014), arXiv: 1403.6652.

[3] К. Маккормик. Учебное пособие по Word2Vec - Модель Skip-Gram (2016), http://mccormickml.com.

[4] Т. Миколов, К. Чен, Дж. Коррадо, Дж. Дин, Эффективная оценка представлений слов в векторном пространстве (2013), arXiv: 1301.3781.

[5] А. Нараянан, М. Чандрамохан, Р. Венкатесан, Л. Чен, Ю. Лю, С. Джайсвал, graph2vec: Изучение распределенных представлений графов (2017),
arXiv: 1707.05005 .

[6] П. Гойал, Э. Феррара, Методы вложения графов, приложения и производительность: обзор (2018), Системы, основанные на знаниях.

[7] Д. Ван, П. Цуй, В. Чжу, Structural Deep Network Embedding (2016), Материалы 22-й международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных.

[8] A. Grover, J. Leskovec, node2vec: Scalable Feature Learning for Networks (2016), Труды 22-й международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных.