Графическое обучение и геометрическое глубокое обучение - Часть 1

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

Подпишитесь на мой Twitter и присоединяйтесь к сабреддиту Geometric Deep Learning, чтобы получать последние новости в этой сфере.

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

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

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

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

Встраивание графовых сетей

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

Алгоритмы машинного обучения настроены для непрерывных данных, поэтому встраивание всегда выполняется в непрерывное векторное пространство.

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

DeepWalk - Пероцци и др.

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

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

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

Цель состоит в том, чтобы оценить вероятность наблюдения узла vi с учетом всех предыдущих узлов, посещенных до сих пор в ходе случайного блуждания, где Pr () - вероятность, Φ - функция отображения, которая представляет скрытое представление, связанное с каждым узлом v на графике.

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

Для прогнозирования используется метод skip-gram, как и в архитектуре Word2vec для текста. Вместо того, чтобы бегать по корпусу текста, DeepWalk бегает по графу, чтобы изучить вложение. Модель может использовать целевой узел, чтобы предсказать его «контекст», который в случае графа означает его связность, структурную роль и особенности узла.

Хотя DeepWalk относительно эффективен с оценкой O (| V |) , этот подход является трансдуктивным, то есть всякий раз, когда добавляется новый узел, модель необходимо переобучить, чтобы внедрить и изучить новый узел.

Node2vec - Гровер и др.

Вы слышали о Word2vec. Теперь подготовьтесь к… Node2vec (Адитья Гровер и др.)

Node2vec - один из наиболее популярных методов обучения графам - это одна из первых попыток глубокого обучения изучать структурированные данные графа. Интуиция аналогична DeepWalk:

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

Разница между Node2vec и DeepWalk тонкая, но существенная. Node2vec имеет переменную смещения обхода α, которая параметризуется p и q. Параметр p отдает приоритет процедуре поиска в ширину (BFS), а параметр q отдает приоритет процедуре поиска в глубину (DFS). Таким образом, на решение о том, куда идти дальше, влияют вероятности 1 / p или 1 / q.

Как видно из визуализации, BFS идеально подходит для изучения локальных соседей, тогда как DFS лучше подходит для изучения глобальных переменных. Node2vec может переключаться между двумя приоритетами в зависимости от задачи. Это означает, что для одного графика Node2vec может возвращать разные результаты в зависимости от значений параметров. Согласно DeepWalk, Node2vec также принимает скрытое встраивание обходов и использует их в качестве входных данных для нейронной сети для классификации узлов.

Эксперименты показали, что BFS лучше классифицирует по структурным ролям (концентраторы, мосты, выбросы и т. Д.), В то время как DFS возвращает схему классификации, в большей степени ориентированную на сообщества.

Node2vec - один из многих проектов по обучению графам, созданных исследовательской группой Stanford’s SNAP, посвященной аналитике графов. Многие из их работ явились началом многих больших успехов в геометрическом глубоком обучении.

Graph2vec - Нараянан и др.

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

На простом английском языке это уравнение можно записать как: вероятность появления слова (wj) в контексте данного документа (d) равна экспоненте матрицы встраивания документа ( d ~), умноженное на матрицу встраивания слов (w ~ j взято из документа), разделенное на сумма всех экспонент матрицы вложения документа, умноженная на матрицу встраивания слов для каждого слова в списке словарей (V) во всех документах.

Используя аналогию с word2vec, если документ состоит из предложений (который затем состоит из слов), то граф состоит из подграфов (которые затем состоят из узлов).

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

Встраивание структурной глубокой сети (SDNE) - Ван и др.

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

  • Близость первого порядка: два узла считаются похожими, если у них есть общее ребро (попарное сходство).
  • Близость второго порядка: два узла считаются похожими, если они имеют много соседних / смежных узлов.

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

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

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

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

Встраивание крупномасштабной информационной сети (LINE) - Танг и др.

LINE (Jian Tang и др.) Явно определяет две функции; один для близости первого порядка, а другой - для близости второго порядка. В экспериментах, проведенных в рамках исходного исследования, близость второго порядка была значительно лучше, чем первая, и предполагалось, что в том числе более высокие порядки могут нивелировать повышение точности.

Цель LINE - минимизировать разницу между входным и внедренным распределениями. Это достигается за счет расхождения KL:

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

LINE определяет два совместных распределения вероятностей для каждой пары узлов, а затем минимизирует KL-расхождение распределений. Эти два распределения представляют собой матрицу смежности и скалярное произведение встраивания узлов. К.Л. Дивергенция - важная метрика подобия в теории информации и энтропии. Алгоритм используется в вероятностных генеративных моделях, таких как вариационные автоэнкодеры, которые встраивают входные данные автоэнкодера в скрытое пространство, которое становится распределением.

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

Тем не менее, простота и эффективность LINE - это всего лишь пара причин, по которым эта статья стала самой цитируемой в WWW в 2015 году. Эта работа помогла пробудить интерес к графическому обучению как нише в машинном обучении и, в конечном итоге, в глубоком обучении в частности.

Обучение иерархическому представлению для сетей - Чен и др.

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

Следовательно, предполагаемый мотив:

Улучшите решение и избегайте локальных оптимизаций за счет лучшей инициализации веса.

и предлагаемый метод:

Используйте укрупнение графа, чтобы объединить связанные узлы в «надузлы»

был сделан.

HARP - это, по сути, этап предварительной обработки графика, который упрощает график для ускорения обучения.

После огрубления графа он затем генерирует вложение самого грубого «суперузла», за которым следует вложение всего графа (который сам состоит из суперузлов).

Эта стратегия применяется для каждой «надузла» на всем графе.

Поскольку HARP можно использовать вместе с предыдущими алгоритмами внедрения, такими как LINE, Node2vec и DeepWalk. В исходной статье сообщалось о заметных улучшениях до 14% в задачах классификации при сочетании HARP с различными методами встраивания графов: значительный скачок вперед.

В сущности

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

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

Далее мы погрузимся в сложный и элегантный мир сверток графиков!

Ключевые выводы

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

Хотите увидеть больше подобного контента?

Подпишитесь на меня в LinkedIn, Facebook, Instagram и, конечно же, на Medium, чтобы получить больше контента.

Весь мой контент находится на моем веб-сайте, а все мои проекты - на GitHub

Я всегда хочу познакомиться с новыми людьми, сотрудничать или узнать что-то новое, поэтому не стесняйтесь обращаться к [email protected]

Вверх и вперед, всегда и только 🚀