Представьте себе Снупи без Вудстока или Кельвина без Гоббса, друзей без Рэйчел, Бэтмена без Робина или Маугли без Балу. Социальные платформы процветают благодаря способности участников находить подходящих друзей для взаимодействия. Сетевой эффект - это то, что стимулирует рост или время, затрачиваемое и ежедневно активных пользователей в приложении. Это еще более важно для Hike, потому что Hike - это сеть для близких друзей. Поэтому нам нужно сделать так, чтобы найти друзей, пригласить их и добавить в сеть было легко.

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

Создание системы рекомендаций друзей в активной реальной социальной сети, такой как Hike, означает:

  1. Предложения друзей должны быть актуальными - из-за ограниченного пространства на экране одновременно может отображаться только несколько предложений друзей, И это означает, что нам нужно предлагать подходящих людей
  2. Рекомендации друзей должны работать плавно, чтобы новые пользователи могли легко добавлять в сеть
  3. Он должен быть ориентирован на будущее. Сеть развивается со временем, каждый день к ней присоединяются новые пользователи, добавляются друзья, завязываются дружеские отношения между старыми пользователями и т. Д. На основе текущей сети мы хотим иметь возможность прогнозировать предстоящие изменения в сети и давать соответствующие рекомендации.

В Hike мы применяем современные алгоритмы машинного обучения в области обработки естественного языка (NLP), компьютерного зрения, релевантности и рекомендаций, сетевого анализа и т. Д. (Обзор ML @ Hike). Наша модель предложения друзей построена на основе передовых исследований в области глубокого обучения и сетевого анализа. Мы углубились в это и разработали структуру для изучения представления графов в гетерогенных сетях с несколькими типами ребер для рекомендации друзей. И это сработало для нас очень хорошо, поскольку помимо коммерческой выгоды, мы были очень взволнованы, когда это исследование было номинировано на публикацию на Европейской конференции по поиску информации (ECIR) в апреле 2019 года.

Проблема рекомендаций друзей соответствует классической задаче прогнозирования ссылок в социальных сетях. Мы представляем пользователей на нашей платформе как лежащих на графе, где ребра являются связями между пользователями. Имея снимок социальной сети в момент времени t, можем ли мы точно предсказать края, которые будут добавлены в сеть в течение интервала от времени t до заданного времени в будущем t`? Короче говоря, можно ли использовать текущее состояние сети для прогнозирования будущих связей? Традиционные методы прогнозирования ссылок основывались на показателях анализа «близости» узлов в сети. В частности, если соседство двух узлов имеет большое перекрытие, такие методы будут указывать на то, что они с большой вероятностью будут совместно использовать ссылку. Общие соседи, коэффициент Жаккара, метрика Адама-Адара - это разные меры, которые были разработаны для оценки перекрытия между соседними узлами. Существуют также методы контролируемого машинного обучения, которые используют функции узлов для обучения модели классификации. Эти функции не всегда легко доступны и, следовательно, требуют серьезной разработки функций.

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

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

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

Аналогия - вложения слов (word2vec) в текстовые документы - случайные блуждания являются сетевым аналогом предложений. Два популярных метода встраивания узлов:

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

Еще один важный метод изучения встраивания однородных узлов - это node2vec, где случайные блуждания смещены для навигации по окрестностям узла, так что они могут переходить от поиска в ширину (BFS) к обходу поиска в глубину (DFS). Интерполяция между BFS и DFS задается параметром, и для хорошей производительности это требует серьезной настройки.

Рекомендацию друга можно определить как задачу двоичной классификации, которая берет особенности пары пользователей и учится сопоставлять их с 1, если это пара друзей, и 0 в противном случае. Мы можем использовать встраивание сети для получения пользовательских функций. Если u, v - два пользователя, а vec_u, vec_v - соответствующие вложения узлов соответственно, мы можем комбинировать вложения различными способами для создания входных данных для модели классификации, например.

  • Конкатенация, vec = vec_u ⊕ vec_v
  • Среднее значение, vec = (vec_u + vec_v) / n
  • Произведение Адамара, vec = vec_u * vec_v

Обратите внимание, что это все векторные операции. Вектор vec можно рассматривать как вложение ребра ‹u, v›. Затем vec передается в модель машинного обучения, например логистическая регрессия, нейронная сеть и т. д. Для обучения классификатора требуется большой набор помеченных данных известных пар друзей и не друзей, на которых модель «учится»

D = {‹u, v›, label}, где label ∈ {0,1}

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

- Площадь под кривой ROC (AUC)

- Точность при k (P @ k)

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

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

«Контакт» - если пользователи находятся в контактах друг друга.

«Друг» - если пользователи являются друзьями в Hike.

«Чат» - если пользователи общались хотя бы раз в период.

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

Применимость как DeepWalk, так и Node2vec ограничена только однородными сетями с одним типом узлов и отдельным типом ребер между узлами. Существующие методы встраивания сетей, разработанные для однородных сетей, могут быть неприменимы напрямую к гетерогенным сетям. Недавно была предложена методика внедрения metapath2vec для гетерогенных сетей, которая определяет метапуть (последовательность типов узлов) для ограничения случайных блужданий. Однако не очевидно, как определить такой метапуть, поскольку нам часто не хватает интуиции в отношении путей и мета-путей, а также длины метапуть. Более того, для гетерогенной сети с разными типами ребер и множеством ребер между двумя узлами (разнородный мультиграф) не существует интуитивно понятного способа определения метапуть типов ребер. В metapath2vec предлагается глубокая архитектура для изучения встраивания узлов в мультимодальную сеть с узлами изображения и текста. Однако он не распространяется на мультиграф, в котором между парой узлов существуют разные типы ребер. Есть несколько простых расширений Deepwalk для гетерогенной сети.

Несмещенные случайные блуждания генерируются путем присвоения равной вероятности прохождения любого ребра между двумя узлами. Это увеличивает вероятность случайного блуждания к узлу, который имеет несколько ребер от текущего узла. Ограничением является то, что в сети Hike гораздо больше контактов, чем друзей, и даже меньше контактов в чате. Таким образом, случайное блуждание имеет более высокие шансы пройти через грани контакта и в некоторых случаях полностью избегает ребер чата.

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

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

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

  1. Разделите сеть Hike на подсеть друзей, подсеть контактов и подсеть чата, где пользователи связаны через дружбу, список контактов и чат соответственно. Каждый из этих подграфов однороден.
  2. Получите вложения узлов из каждой из этих подсетей с помощью Deepwalk или Node2Vec. Теперь у нас есть представление узла в нескольких пространствах.
  3. В каждом однородном пространстве вложения вычислите вложение ребер из вложений узлов.
  4. Обучите унифицированное неоднородное встраивание ребер для прогнозирования ссылок.

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

Этот метод продемонстрировал превосходные характеристики по сравнению с другими современными методами. Мы сообщили о 20% -ном увеличении показателя AUC по сравнению с методом Deepwalk, а точность 5 увеличилась на 4,4%. Мы также проводили пользовательские эксперименты, отправляя наиболее вероятную дружбу в виде уведомления в приложении, мы наблюдали улучшение на 7,6% по сравнению с исходным уровнем.

Вкратце о проектировании - система имеет автономный и онлайн-компоненты. В автономной системе социальный граф пересчитывается ежедневно, а вложения узлов вычисляются и сохраняются в масштабируемой системе, такой как FIASS, которая создает индекс для облегчения быстрого поиска сходства. Мы также обучаем новую модель рекомендаций на основе нейронных сетей, как обсуждалось ранее. Предложения друзей для пользователя создаются онлайн, где мы ищем встраивание пользовательского узла и выполняем поиск ближайшего соседа, чтобы получить набор кандидатов, которые затем оцениваются с использованием модели нейронной сети. Проверка фильтра Блума гарантирует, что рекомендации не будут повторяться для пользователя. Лучшие k рекомендаций, сгенерированные таким образом, обслуживаются в различных виджетах рекомендаций в приложении Hike. Система изображена на следующем рисунке:

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

Первоначально опубликовано на blog.hike.in 18 декабря 2018 г.