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

Классические подходы к завершению матрицы

Одним из распространенных методов рекомендательных систем является использование классических методов машинного обучения для завершения матрицы, метода совместной фильтрации. Учитывая количество пользователей m и количество элементов n, он стремится заполнить недостающие значения в матрице взаимодействия пользователя и элемента R(с размерами mxn). Для этого мы сопоставляем каждого пользователя и элемент с вложением размера k — абстрактным представлением в векторном пространстве. Эти вложения могут охватывать такие функции, как жанры фильмов или демографические данные пользователей, но во многих случаях это скрытые неизвестные функции. Матрица внедрения пользователей U(с размерами mxk) и матрица внедрения элементов I >(с размерами nxk). Чтобы делать прогнозы для пар «пользователь-элемент», мы вычисляем скалярное произведение транспонированной матрицы «Предмет» и матрицы «Пользователь». Первоначально скрытые матрицы инициализируются случайным образом, и мы оптимизируем вложения, используя функцию потерь, основанную на известных взаимодействиях пользователя и элемента.

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

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

Обзор теории графов

Что такое график?

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

Типы диаграмм

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

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

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

Как мы храним графические данные?

Существуют различные способы хранения графических данных. Один из подходов заключается в использовании матрицы смежности, обозначаемой как A ∈ {0, 1}ⁿˣⁿ, гдеn — количество узлов в графе. . Запись (i, j) матрицы, Aᵢ,ⱼ, представляет собой связность между узлами vᵢ и vⱼ, при этом Aᵢ,ⱼ = 1, если есть ребро, соединяющее vᵢ и vⱼ. Для неориентированного графа матрица смежности симметрична, т. е. Aᵢ,ⱼ = Aⱼ,ᵢ. Однако матрицы смежности могут потреблять много памяти для больших и разреженных графов, таких как социальные сети. Это связано с тем, что матрица смежности масштабируется с количеством узлов. В социальной сети с миллионами узлов большинство людей не знают друг друга. Это привело бы к большой матрице, в которой большинство ячеек были бы пустыми.

Чтобы решить эту проблему, представление списка смежности более эффективно использует память.Оно описывает ребра между узлами как кортежи (i,j), где (0,1) представляет собой ребро между узлами 0 и 1. Например, для графа на рис. 5 список смежности будет [(A,B),(B,D),(B,C),(D,C)].

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

Граф нейронных сетей в рекомендательных системах

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

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

Графические слои нейронной сети

Уровень GNN обменивается информацией между всеми непосредственными соседями в графе, чтобы создать новые вложения узлов для каждого узла в графе. В двухуровневой модели GNN каждый узел будет генерировать свои вложения уровня 2 на основе своего соседства с двумя переходами.Окрестность K-переходов относится ко всем узлам, которые находятся на K-ребрах от интересующего узла. >. Это итеративный процесс, в котором соседние переменные «общаются» друг с другом, передавая сообщения, метод передачи сообщений.

На этом изображении мы видим, что представление уровня 2 узла A создается путем агрегирования вложений уровня 1 его непосредственных соседей [B,C,D] и применения преобразования черного ящика. или нейронная сеть к ним. Эти вложения, в свою очередь, генерируются его прямыми соседями вложений уровня-0 [X_A, X_B…X_F], которые являются исходными входными объектами. Каждый уровень создает новое внедрение узла, а внедрение узла на уровне K получает информацию от узлов, которые находятся на расстоянии K прыжков от себя.

Особенности, преимущества и ограничения графовых нейронных сетей

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

  • Инвариантность порядка:GNN инвариантны к порядку, что означает, что порядок маркировки узлов не влияет на результаты. Граф вычислений учитывает связность узлов, а не порядок узлов, используя независимые от порядка функции агрегирования, такие как среднее, максимальное/минимальное объединение для передачи сообщений.
  • Неизменность размера.Каждый узел в GNN имеет собственный граф вычислений, что делает размер GNN неизменным. Это позволяет отдельным узлам обрабатывать и интегрировать информацию на основе их локального окружения, обеспечивая персонализированное и гибкое обучение. На изображении ниже показан график вычислений для каждого из узлов на предыдущем рисунке.

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

Несмотря на свои сильные стороны, GNN также имеют ограничения, которые следует учитывать:

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

Заключение

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

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

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

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