Мысли и теория

За кулисами алгоритма быстрой случайной проекции для генерации вложений графов

Подробный обзор FastRP и его гиперпараметров

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

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

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



Начало работы с встраиванием графиков
Первый шаг к конвейеру машинного обучения с использованием библиотеки Neo4j Graph Data Science Library в сторонуdatascience.com



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



Twitchverse: Использование встраиваний FastRP для задачи классификации узлов
Извлеките значение отношений с помощью алгоритма встраивания FastRP для создания функций для нисходящего узла… к науке. com



Этот конкретный пост основан на вышеизложенном, а также на моем предыдущем посте, где я показываю создание приборной панели с использованием Streamlit и то, как возиться с сгенерированным Neo4j графом, встраивающим гиперпараметры. Это было создано как для алгоритмов встраивания графов FastRP, так и для node2vec. Я предоставил средства визуализации вложений в двух измерениях с помощью t-SNE.

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



Визуализация встраиваний графов с помощью t-SNE в Python
Как качественно оценить вложения графов Neo4j в сторонуdatascience.com



Кроме того, этот пост является параллельным посту Томаша Братанича: Полное руководство по пониманию алгоритма Node2Vec.



Полное руководство по пониманию алгоритма Node2Vec
Подробное руководство по пониманию алгоритма node2vec и его гиперпараметров в сторонуdatascience.com



Предупреждение!

Скоро математика! Если вы никогда не пытались правильно обработать математику на Medium, это не очень красиво! Я сделаю все возможное…

Происхождение FastRP: лемма Джонсона-Линденштрауса

Алгоритм FastRP был создан H. Chen et. al, о котором вы можете подробно прочитать в оригинальной статье. Я действительно рекомендую эту статью, так как собираюсь извлечь из нее большую пользу. Поскольку математика, лежащая в основе этого алгоритма, является основой алгоритма Neo4j FastRP (даже включая имена переменных), нам нужно немного поговорить об этой математике. Не волнуйтесь ... Я надеюсь, что все не так уж плохо, и я полностью доверяю вам, дорогой читатель, за то, что вы справились с этим!

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

Итак, да, мы пытаемся перейти от p -мерного пространства к d -мерному пространству, где d ‹p. Учитывая эти две точки xᵢ и xⱼ, мы хотим создать некоторое отображение, Ψ, которое преобразует пространство большой размерности в пространство нижней размерности, в то время как в идеале приблизительно выдерживая расстояние между этими двумя точками. По сути, это означает, что мы собираемся решить следующее уравнение:

где наша цель - сохранить ϵ как можно меньше. Тот факт, что это уравнение работает, является леммой JL.

Настоящая уловка здесь в том, чтобы понять, каким должен быть Ψ. Д. Ахлиоптас обнаружил (и описал в этой статье), что вы можете получить удобные для базы данных случайные проекции (собственно, так называется название статьи), используя простой бинарный подбрасывание монеты, случайное число. H. Chen et. al использовал эту идею для реализации матрицы случайных проекций R, которая будет основным моментом нашего сопоставления, которое в конечном итоге будет задано

Фактически, Ли и др. Сообщил, что пока R имеет нулевое среднее значение, попарные расстояния между точками сохраняются - цель уменьшения размерности. Кроме того, Ли показал, что s можно выбрать равным квадратному корню из числа ребер в графе s = sqrt (m), предполагая, что нисходящий поток матрицы (см. ниже) можно считать очень разреженными. Достаточно интересно, что использование этой случайной матрицы проекции может быть быстрее, чем гауссовская случайная проекция на sqrt (m). Однако, в зависимости от разреженности матрицы, выбор s = 3 оказался адекватным в исходной статье Ахлиоптаса.

Так при чем тут графики ???

Я рада, что вы спросили! Да, у нас есть матрица, которая может рандомизировать вещи. Очевидно, мы захотим применить его к какой-то другой матрице. Но какая у нас матрица, вообще связанная с графами?

Матрица смежности - отличное начало! На самом деле, мы собираемся немного улучшить его, создав матрицу перехода A в виде A = D⁻¹S, где S - это матрица смежности, а D - матрица степеней графа (диагональная матрица, дающая степень каждого узла). Давайте быстро визуализируем их, поскольку это сделает размеры последующих матриц более ясными. Предположим, у нас есть взвешенный ориентированный граф, который выглядит следующим образом

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

Мы также можем установить матрицу степеней:

Таким образом, мы можем затем построить матрицу перехода через

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

Теперь мы переходим к обозначениям, которые фактически используются Neo4j-реализацией алгоритма FastRP! Вот с чего мы начнем разбираться с гиперпараметрами.

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

где β - сила нормализации, m - количество ребер, а dⱼ - степень j - й узел. Итак, когда β стремится к бесконечности, мы можем получить

Давайте на секунду подумаем, что это на самом деле означает, особенно когда мы применяем эту матрицу нормализации к матрице перехода. Допустим, у нас есть k- -я степень A ( т.е. мы умножаем A на само k раз ). ij-я запись Aᵏ - это вероятность достижения j из i ровно за k шагов случайного блуждания!

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

Итак, теперь, когда мы знаем, что ...

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

А теперь пора приступить к FastRP!

Учитывая нашу матрицу перехода графа A, размерность внедрения d, силу нормализации β и некоторые веса итераций α₁… αₖ (подробнее об этом через секунду) шаги следующие:

  1. Создайте матрицу случайной проекции Rᵢⱼ
  2. Рассчитайте первую итерацию вложений матриц как N₁ = A ⋅ L ⋅ R
  3. Вычислить последующие значения N для i = 2 .. количества узлов как Nᵢ ← A ⋅ Nᵢ₋₁
  4. Вычислить взвешенную сумму всех значений N

Конечным результатом здесь является умножение матрицы на (n × n) ⋅ (n × n) ⋅ (n × d), в результате чего N имеет размерность (n × d), что мы и хотим (одно d -мерное вложение для каждого n узлов).

Если мы рассмотрим это в контексте леммы LR, напомним, что Ψ был тем, что привело нас от ℝᵖ к ℝᵈ. Итак, если мы рассмотрим, что N = A ⋅ L ⋅ R, тогда это означает, что Ψ = L ⋅ R.

Веса, веса и других весов

Да, у нас есть другой набор весов в наших значениях α выше. Это веса итераций, рассчитанные для каждого Nᵢ, и они требуют отдельного объяснения.

Ясно, что эти веса будут контролировать относительное влияние на окончательное внедрение узла каждого шага, описанного выше. При 1 итерации мы получим вложения только на основе первого соседа каждого узла, что не очень полезно. Так, например, предположим, что у нас есть 4 итерации (т.е. k = 4). Что это на самом деле означает? Ранее мы говорили (выделенный полужирным шрифтом и курсивом выше), что ij -я запись Aᵏ обозначает вероятность достижения i из j ровно за 4 шага. Если вероятность равна нулю до 5 шагов, то Aᵢⱼ равно нулю. Другими словами, с k = 4 мы не можем случайным образом перейти к узлу, который, скажем, находится на расстоянии 5 или более прыжков от графика. Итак, k сообщает нам, какую часть локального окружения вокруг узла мы включаем в наши вложения. Затем мы можем взвесить каждый из шагов случайной проекции, описанных выше, как

На самом деле вложения не будут такими хорошими, если мы будем смотреть только на непосредственных соседей любого заданного узла. Так что, возможно, даже стоит просто игнорировать эти маленькие значения k. Собственно, именно так и поступили авторы. Они заметили, что встраивания подходят с k = 4 и только с использованием A³ и A⁴. Исходя из этого, они устанавливают веса (α₁, α₂, α₃) = (0, 0, 1). В исходной статье они затем оптимизировали свои вложения, параметрически настроив α₄ и β с заданным значением d.

Ух ты! Это много! Стоит ли ???

TL; DR да!

Этот алгоритм одновременно быстрый и простой. Например, авторы сообщили, что при использовании набора данных WWW-200k их процессорное время для FastRP для встраивания составляло 136,0 секунд, тогда как node2vec потребовалось 63,8 дня! При сравнении как с node2vec, так и с другим популярным алгоритмом встраивания, DeepWalk, они наблюдали встраивания, которые давали результаты классификации узлов, которые были, по крайней мере, столь же точными, если не более точными! Существует также множество других алгоритмов встраивания графов, но одна из замечательных особенностей FastRP - это то, насколько он прост. Он также легко расширяется, что позволяет вам включать дополнительную информацию о графике, такую ​​как свойства отдельных узлов, для дальнейшего улучшения ваших встраиваний.

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

Особая благодарность Томазу Братанику и Майклу Хунгеру за их предложения и отзывы к этой публикации.

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