Узнайте, как обучать и оптимизировать модели прогнозирования ссылок в библиотеке Neo4j Graph Data Science, чтобы получить наилучшие результаты

В моем предыдущем сообщении в блоге я представил недавно доступный конвейер прогнозирования ссылок в библиотеке Neo4j Graph Data Science. После публикации мне потребовалось больше времени, чтобы копнуть глубже и изучить внутреннюю работу конвейера. По пути я узнал пару вещей, которыми хочу поделиться с вами. Сначала я намеревался показать, как конвейер Link Prediction объединяет свойства узлов для создания входных функций модели Link Prediction. Однако, когда я разрабатывал контент, я заметил несколько идей об использовании алгоритма встраивания FastRP. Поэтому к концу этого сообщения в блоге вы, надеюсь, узнаете больше о модели встраивания FastRP и о том, как можно комбинировать функции нескольких узлов в качестве входных данных для модели прогнозирования ссылок.

Код, использованный в этом посте, доступен на GitHub.

Импорт графика

Мне пришлось найти небольшую сеть, чтобы легко визуализировать результаты по мере продвижения. Я решил использовать интерактивную сеть из первого сезона сериала« Игра престолов , предоставленную Эндрю Бевериджем .

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

Если вы хотите следовать примерам в этом посте, я рекомендую использовать пустой проект в Neo4j Sandbox. Это бесплатный облачный экземпляр базы данных Neo4j, который поставляется с предустановленными плагинами APOC и Graph Data Science.

Набор данных доступен на GitHub, поэтому мы можем легко импортировать его в Neo4j с помощью следующего запроса Cypher:

LOAD CSV WITH HEADERS FROM "https://raw.githubusercontent.com/mathbeveridge/gameofthrones/master/data/got-s1-edges.csv" as row
MERGE (s:Character{name:row.Source})
MERGE (t:Character{name:row.Target})
MERGE (s)-[i:INTERACTS]-(t)
SET i.weight = toInteger(row.Weight)

Конвейер прогнозирования ссылок

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

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

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

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

  • Косинусное расстояние
  • L2 или евклидово расстояние
  • Произведение Адамара

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

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

Разработка функций узла

Вы можете предварительно обработать функции узла перед определением конвейера прогнозирования ссылок. Вы также можете включить их непосредственно в определение конвейера, если вы используете только алгоритмы графа, такие как встраивание узлов или меры центральности в качестве узловых функций. В первом примере мы будем использовать встраивания FastRP в качестве функций узла модели Link Prediction. Следовательно, мы потенциально можем включить их в определение конвейера. Однако сначала мы проведем краткий анализ результатов внедрения узлов, поэтому нам нужно сохранить вложения узлов в граф, прежде чем углубляться в определение конвейера. Начнем с проектирования неориентированного именованного графа. Взгляните на документацию для получения дополнительной информации о внутренней работе библиотеки Graph Data Science.

CALL gds.graph.create('gots1', 'Character', 
  {INTERACTS:{orientation:'UNDIRECTED', properties:'weight'}})

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

CALL gds.louvain.write('gots1', 
  {writeProperty:'louvain', relationshipWeightProperty:'weight'})

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

Теперь мы можем продолжить и выполнить алгоритм встраивания FastRP. Алгоритм создаст вложение или вектор фиксированного размера для каждого узла в графе. Мой друг CJ Sullivan написал отличную статью, объясняющую внутреннюю работу алгоритма FastRP.

CALL gds.fastRP.write('gots1', 
  {writeProperty:'embedding', embeddingDimension:56, relationshipWeightProperty:'weight'})

Сначала мы оценим вложения FastRP с визуализацией графика рассеяния t-SNE. Сохраненные вложения узлов - это векторы длиной 56, как определено параметром embeddingDimension. Алгоритм t-SNE - это алгоритм уменьшения размерности, который мы можем использовать для уменьшения размерности встраивания до двух. Наличие векторов длины два позволяет нам визуализировать их с помощью диаграммы рассеяния. Код Python, который я использовал для уменьшения размерности и визуализации диаграммы рассеяния:

Этот код создает следующую визуализацию:

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

MATCH (c:Character)
WITH {item:id(c), weights: c.embedding} AS userData
WITH collect(userData) AS data
CALL gds.alpha.similarity.cosine.stats({
  data: data,
  topK: 1000,
  similarityCutoff: 0.1
})
YIELD nodes, similarityPairs, min, max, mean, p25, p50, p75, p90, p95, p99
RETURN nodes, similarityPairs, min, max, mean, p25, p50, p75, p90, p95, p99

Результаты

Средний коэффициент подобия косинуса между всеми узлами на графике составляет около 0,5. Около 25% пар узлов имеют косинусное сходство больше 0,81. Узлы настолько похожи в пространстве для встраивания, потому что у нас есть крошечный граф, состоящий всего из 126 узлов. Затем мы оценим косинус и евклидово расстояние между парами узлов, связанных отношениями.

Результаты

Большинство пар узлов, связанных отношениями, имеют большое косинусное сходство. Опять же, это ожидается, поскольку FastRP предназначен для преобразования структуры топологии сети во встраиваемое пространство. Следовательно, мы ожидаем, что соседние узлы в графе будут очень похожи в пространстве вложения. Мы рассмотрим пары узлов, подключенные к сети, с косинусом сходства менее 0,5, поскольку это немного более неожиданно. Во-первых, мы должны пометить их Cypher:

MATCH p=(c1:Character)-[i:INTERACTS]->(c2:Character)
WHERE gds.alpha.similarity.cosine(c1.embedding, c2.embedding) < 0.5
SET i.show = True

А теперь мы можем продолжить и визуализировать их с помощью Neo4j Bloom.

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

Объединитель функций ссылок

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

Объединитель косинусов

Интересно, что первым объединителем, на который мы рассмотрим, является объединитель подобия косинуса.

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

Скрипт Python, который мы будем использовать для прогнозирования ссылок:

Это немного длинный сценарий, поскольку нам нужно определить весь конвейер прогнозирования ссылок для каждой опции объединителя функций ссылок. Наконец, предсказанные ссылки сохраняются в Neo4j, чтобы мы могли визуализировать их с помощью Bloom. В моем предыдущем посте в блоге я сделал пошаговое объяснение конвейера. Как уже упоминалось, я подготовил Блокнот Jupyter со всем кодом, поэтому вам не нужно копировать его напрямую из сообщения в блоге.

Давайте рассмотрим предсказанные ссылки с помощью комбайнера Cosine Link Feature.

Среднее евклидово и косинусное сходство пар узлов, у которых есть предсказанные связи, составляет:

Как мы можем представить, косинусное сходство между узлами предсказанных ссылок в среднем составляет 0,999. Таким образом, результаты согласуются с нашими данными обучения. Кроме того, мы можем немного узнать о встраиваниях FastRP из результатов. Периферийные узлы с низкой степенью очень похожи в пространстве для встраивания, даже если они не связаны напрямую. Например, синие узлы в левой нижней части визуализаций очень похожи. Все четыре узла имеют только одно отношение, и они имеют общие соседние узлы.

Объединитель функций L2-ссылок

Далее мы рассмотрим объединитель функций L2 link. Комбайнер объектов связей L2 вычисляет евклидово расстояние между двумя узловыми объектами.

Результаты почти идентичны сумматору Cosine Link Feature. Похоже, что алгоритм внедрения FastRP оптимизирует сходство косинусных и евклидовых расстояний между соседними узлами в сети.

Объединитель характеристик ссылок Адамара

Объединитель признаков связи Адамара использует продукт Адамара для создания признака связи. Произведение Адамара - это просто поэлементное умножение.

Давайте рассмотрим предсказанные связи, используя объединитель характеристик ссылок Адамара.

Среднее евклидово и косинусное сходство пар узлов, у которых есть предсказанные связи, составляет:

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

Использование нескольких объединителей функций ссылок

В предыдущем примере мы использовали только объединитель функций с одной ссылкой. В случае объединителя функций связи косинуса или L2 мы эффективно использовали только одну входную функцию в модели логистической регрессии. На практике имеет смысл иметь несколько функций ввода, которые лучше всего описывают ваш домен. В качестве демонстрации мы добавим ввод предпочтительных вложений в качестве второй функции ссылки. Глядя на документацию в Neo4j, предпочтительное присоединение определяется как умножение степеней узлов между парой узлов. На практике модель предпочтительного присоединения предполагает, что узлы с более высокой степенью узлов с большей вероятностью образуют новые соединения. К сожалению, мы пока не можем автоматически добавить функцию предпочтительной ссылки для прикрепления, но можем добавить ее вручную. Чтобы добавить функцию ввода предпочтительного присоединения, мы сначала вычислим значения степени узла для всех узлов. Иногда вам нужно нормализовать входные функции с помощью моделей логистической регрессии, поэтому я покажу вам, как масштабировать функции непосредственно в конвейере прогнозирования ссылок. Затем нам просто нужно добавить объединитель функций связи Адамара, который умножает входные матрицы, в данном случае степени узлов. Итак, если я правильно понимаю математику, результирующая функция связи должна представлять предпочтительное присоединение, поскольку мы эффективно умножаем степени узлов между парами узлов.

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

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

Мы получаем следующие результаты, используя объединитель функций косинусных ссылок с вложениями FastRP и объединитель Адамара с масштабированными степенями узлов.

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

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

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

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

Заключение

Мне очень понравилось писать этот пост в блоге, и я много узнал об алгоритме встраивания FastRP и конвейере прогнозирования ссылок. Краткое резюме:

  • FastRP с большей вероятностью назначит высокое сходство между соседними узлами с низкой степенью
  • С другой стороны, косинусное сходство между соединенными узлами разных сообществ может быть меньше 0,5.
  • Комбайнеры функций с несколькими ссылками могут помочь вам лучше описать свой домен.
  • Функции узла масштабирования влияют на результат модели логистической регрессии Link Prediction

Я рекомендую вам начать бесплатный проект Neo4j Sandbox и начать предсказывать новые соединения на ваших графиках. Сообщите мне, как это происходит!

Как всегда, код доступен на GitHub.