Как алгоритмы на графах помогают собирать группы товаров

Та же статья на русском языке

Скажи мне кто твой друг, и я скажу кто ты

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

Портрет Группы: общие друзья/подписчики Влада и Кости

Один из графов по комментариям и лайкам на 35к профилей (общение под постами за некую неделю)

Зачем всё это? Изначально по приколу, но надеюсь, вы тут с благими намерениями.


Привет, Хабр! Меня зовут Иван Антипов, я занимаюсь ML в команде матчинга Ozon. Наша команда разрабатывает алгоритмы поиска одинаковых товаров на сайте. Это позволяет покупателям находить более выгодные предложения, экономя время и деньги.

В этой статье мы обсудим кластеризацию на графах, задачу выделения сообществ, распад карате-клуба, self-supervised и unsupervised задачи — и как всё это связано с матчингом.

Что такое матчинг и зачем он нужен?

Под матчингом (matching) будем подразумевать сравнение двух схожих объектов (в нашем случае товаров) с целью найти эквивалентные. Соответственно, матчи или товары-дубликаты — это одинаковые товары, имеющие общие характеристики и свойства, предлагаемые разными продавцами.

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

Читайте также  Откройте для себя День ИТ-знаний 2021: раскройте свой технологический потенциал

Матчинг на пальцах

Классический пайплайн поиска товаров-дубликатов обычно состоит из двух этапов: подбор кандидатов и проверка пар моделью. В качестве подбора кандидатов хорошо подходит алгоритм KNN (к каждому товару ищем ближайших по картинке или тексту), но на больших объёмах данных это работает слишком долго, поэтому используют ANN (HNSW, IVF, LSH и др.). ANN работает не так точно, но хорошо подходит для быстрого подбора большого количества потенциальных пар. На втором этапе модель проверяет, являются пары кандидатов дубликатами или нет. На выходе пайплайна получается набор пар товаров и предсказания для них (Таблица 1):

Товар 1 Товар 2 Предсказание
А Б Да
В Г Нет

У товара может быть более одного дубликата, и хочется их объединять в одну группу, один кластер. Как это можно сделать?

Что такое социальный граф (и почему люди заблуждаются относительно него)

Александр Сон

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

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

Source: LeewayHertz.com

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

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

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

Вы управляете своей лентой, или ваша лента управляет вами?

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

Централизованные социальные графы и их проблемы

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

Проблема доступа к данным

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

Монополия на данные и инфраструктуру

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

Открытые протоколы и будущее

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

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

В будущем децентрализованных социальных сетей

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

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

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

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

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

В децентрализованном будущем

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

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

Портрет Группы

Портрет Группы показывает граф общих коллективов и общих друзей/подписчиков группы анализируемых профилей, связи профилей между собой до 2-х рукопожатий (1 рукопожатие – друг/подписчик, 2 – общие друзья).

Граф

Отличия этого графа от графа Портрета Пользователя в следующем:

  • Дополнительно в легенде показывается процент принадлежности профилей группы к каждому из анализируемых. Пример: в группе 5 все профили – это друзья/подписчики Кости и только 2% из них являются друзьями/подписчиками Влада
  • Дополнительно информация ноды включает в себя: с кем дружит/на кого подписан из анализируемых профилей

Портрет Группы: общие друзья/подписчики Влада и Кости

Таблица коллективов

Отличия от Портрета Пользователя в следующем:

  • Рассчитывается всё для всех анализируемых профилей, друзья/подписчики считаются общими для всей группы исследуемых профилей
  • Людей – количество профилей в группе, количество для каждого из исследуемых, и общие для всех – общие друзья/подписчики всех исследуемых
  • Из них подписчики – количество подписчиков для каждого из исследуемых в оной группе (процент подписчиков от числа профилей (столбец Людей: конкретный исследуемый))
  • Общие друзья – пересечение общих друзей/подписчиков для каждых 2-х, 3-х, 4-х, и тд исследуемых из всех исследуемых профилей (показываются только существующие общие)

Всё экстраполируется с одного исследуемого в Портрете Пользователя на всех исследуемых в Портрете Группы для графа, таблицы коллективов, графиков географии, лидеров, возраста и анализа сообществ. Бонус: дополнительно к Портрету Группы строится Карта Нетворкинга для 2-х рукопожатий всех исследуемых.


Как работает Lens Protocol

Теперь, когда мы знаем, как построен социальный граф, не сложно будет понять механику работы Lens Protocol, который является таким же графом, только на блокчейне и состоит из двух базовых элементов:

  • Пользователи: представлены в виде NFT-профилей. Каждый профиль — это динамический токен ERC-721, держатель которого получает доступ ко всем данным пользователя на площадке. Сам профиль привязан к криптокошельку и хранится пользователем, а не Lens Protocol.

  • Взаимодействия: в Lens Protocol реализован набор взаимодействий между пользователями, а также между профилями и контентом, который мы подробнее разберем чуть ниже. Эти взаимодействия строятся на основ смарт-контрактов и NFT.

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

Как алгоритмы на графах помогают собирать группы товаров

Каждый цветок — NFT-профиль, а его корни — это действия, которые выполняет пользователь по отношению к другим пользователям или своему профилю. Теперь разберем подробнее каждый элемент:

NFT-профили

Как алгоритмы на графах помогают собирать группы товаров

Важно: на данный момент Lens Protocol на стадии закрытой беты, поэтому минтить ProfileNFT могут только пользователи из одобренного списка. Чтобы проверить, доступен ли вашему адресу минт ProfileNFT подключите его на официальном сайте Lens. Если же вы не попали в белый список, то можно купить ProfileNFT на OpenSea или другом маркетплейсе.

Активности профилей

Архитектура Lens Protocol четко детерминирована и имеет исчерпывающий перечень активностей и взаимодействий между профилями, впрочем, как и любая Web2-соцсеть. Так, пользователи Web3 соцсетей на базе Lens могут:

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

    • ончейн — ссылка, на содержание, которая записывается в ProfileNFT.

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

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

  • Комментировать (Comment): эта функция не отличается от комментариев на Web2-площадках, но каждый комментарий на Lens содержит идентификатор поста, которого он касается и тоже записывается в ProfileNFT. Это позволяет отслеживать с какими постами взаимодействовал пользователь, даже если это комментарий второго или третьего уровня.

  • Отражать (Mirror): аналог ретвита или репоста в традиционных социальных сетях. Зеркала Lens позволяют пользователю опубликовать пост в своем профиле, сохраняя при этом ссылку на оригинальный контент и его автора.

Каждое отражение имеет свою запись в ProfileNFT, то есть за зеркалом закрепляется оригинальный линк и можно например отследить, сколько пользователей перешло по этому линку на оригинальный пост.

  • Коллекционировать (Collect): модуль Collect добавляет функцию мгновенного минта NFT со ссылкой на контент оригинального поста. Если сравнивать с Web2, то это больше всего напоминает функцию Сохранить, только вместо копии файла на кошельке пользователя минтится полноценная NFT, которую можно передавать.

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

Важно: Модули Collect, Comment и Mirror имеют гибкую настройку логики взаимодействия. Например, разработчики или владелец оригинального поста может установить условие, согласно которому создавать зеркало или комментировать могут только подписанные на него пользователи, а для минта CollectNFT нужно заплатить определенную сумму или, например, холдить другую NFT.

Также Lens Protocol разработал модуль личных сообщений. Он реализован через блокчейн-протокол XMTP и позволяет профилям обмениваться прямыми, зашифрованными сообщениями. Шифровка данных основана на адресе кошелька пользователя, поэтому даже если передать ProfileNFT, его владелец не сможет получить доступ к личным сообщениям.

Послесловие

Мега аналитика

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

Планируется добавить дерево родственников и тд. Да и много чего ещё, но всё равно ждём ваших идей!

Baseline

Транзитивный подход

Транзитивный подход формирования групп товаров-дубликатов.

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

Когда видишь фотографии нескольких последних моделей iPhone

Кластеризация

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

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

Какие недостатки у такого подхода?

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

  2. Скорость. При таком подходе часто необходимо считать расстояние каждого товара с каждым.

  3. Низкая точность в подходе на картиночных и текстовых эмбеддингах. Использовать векторное представление для картинок и названий выгодно на первых этапах пайплайна при подборе кандидатов, где основная задача — получить максимальный выигрыш в полноте, то есть найти как можно больше пар дубликатов. Однако такие эмбеддинги не содержат «метаинформации» о товарах, например, атрибутов. Это влияет на точность, которая важна при сборе итоговых кластеров.

Портрет Пользователя

Если для графа достаточно получитьсписок друзей и подписчиков, то в Портрете Пользователя достаются страницы целиком вместе с подписками и другими открытыми данными, это занимает в среднем в 6 раз больше времени. Так вот, помимо графа, в Портрете Пользователя есть:

1) Граф

Ещё пару слов об оном. Граф разбит на группы близости друзей и подписчиков пользователя. У каждой группы есть свой цвет. Связи внутри группы имеют цвет этой группы, связи с другими группами – серые. Круги – друзья, квадраты – подписчики пользователя, самого пользователя на графе нет. Сплошная линия – дружеская связь. Пунктирная со стрелкой показывает "кто на кого подписан".

Функциональность. Все точки-пикчи можно перемещать. При нажатии (наведении) на ноду (точка-пикча) – подробная информация и подсветка всех его связей. При поиске – подсветка связей. Можно подсветить несколько человек, выбирая их на графе и в поиске. Поиск работает по любой части имени или ID. Рядом с легендой есть кнопка «Физика включена» – при перемещении ноды, связанной с другими, оные будут или не будут перемещаться вслед за перетаскиваемой нодой. Позволяет сделать кастомное расположение нод на свой вкус.

Подробная информация ноды включает в себя: имя (+ ссылка на профиль), номер группы на графе, статус страницы (публичная, приватная, забаненная, заблокированная, удалённая), ID, с кем дружит/на кого подписан, возраст, число друзей и подписчиков, город, родной город, образование, популярность в группе графа (работает примерно так: чем больше связей, тем больше популярность), связи (число связей с другими нодами графа), работу (+ ссылка на место работы), связи с другими группами (номера групп: процент связей с этими группами; выделенная группа – группа с которой больше всего связей, выделенная группа не всегда является группой, в которой находится оный профиль), активность (+ ссылка на активность).

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

2) Таблица коллективов

Мега таблица всего обо всём. Столбцы:

Таблица Коллективов (1-я часть)

* выделены более редкие/важные события, числа могут быть слегка другими

3) География

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

Выводятся города, где хотя бы 2 человека с одной группы

Пример: Волгоград в "родном городе" указали 2 человека из зеленой группы, а на графике "город" эта зеленая группа разбрелась еще на Москву и Питер. Это одноклассники – кто-то поступил в столицы, многие остались. К аналогичному выводу можно прийти, смотря странички в боте на «своих» друзей.

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

4) Лидеры групп

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

Функциональность. Наводим на круг-профиль – видим имя и количество связей. Кликая на группы справа, они убираются/появляются на графике, двойной клик – смотрим выделенную группу. Можно перемещать графики и увеличивать графики, если мелко или не влезла инфа.

5) Возраст

Возраст разбит на группы, возрастные группы и пол. На этом шаге можно идентифицировать группу, которую я описал как "родственники", ведь они попали в 40+ и пошли в Одноклассники 😎

Функциональность. Наводим на столбец/линию «Общее» – видим возрастную группу, число попавших в нее из конкретной группы, номер группы. Кликая на группы справа, они убираются/появляются на графике, двойной клик – смотрим выделенную группу. Можно перемещать графики и увеличивать графики, если мелко или не влезла инфа.

6) Анализ сообществ

Самой первойизображена круговая диаграмма типов сообществ разбитых по категориям ("Юмор", "Новости", “Остальное до 1%” и тд). Это общие интересы группы по всем их подпискам (пример: у 10 профилей по 100 подписок, на диаграмме учтены типы всех 1000 сообществ). Функциональность. При наведении/тапе показывается тип категории и число подписок группы на этот тип категории.

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

Третий график общих пабликов. Сразу видно какое отношение данная группа-коллектив имеет к анализируемому профилю. Функциональность. При наведении/тапе показывается название сообщества, количество профилей группы, подписанных на него, и тематика ("Блог", "Музыкант" и тд) сообщества. Можно перемещать график вверх/вниз, если мелко или не влезла инфа. Черные столбцы – паблики с тематикой: «Городское сообщество». «Преобладающие» (≥6*) паблики выделены жирным.

Можно перемещать графики, если столбцов много. При наведении – доп. инфа, если не видно – подвинь график влево

7) Расширения

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

Бонус. Метрики групп

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


Оглавление

1. Как читать свой граф или друга: построение графа

2. Портрет Пользователя

3. Портрет Группы

4. Карта Нетворкинга


Как это выглядит на реальных данных?

Рассмотрим несколько графов и сообщества, которые удаётся в них найти на реальных данных товаров.

Модель успешно справляется с графами, состоящими из одинаковых товаров. Поскольку такой граф достаточно полный (количество рёбер в нем порядка n (n - 1) / 2, где n — количество товаров в графе), то все вершины в нем попадают в один кластер:

Граф, состоящий из одинаковых товаров.

При наличии False Positive предсказаний (ошибочно сматченных товаров) алгоритм успешно разделяет их по разным кластерам:

Граф товаров, состоящий из двух кластеров.

Граф товаров из нескольких кластеров.

Как читать свой граф или друга

Как изучить граф:

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

номера групп идут по убыванию участников

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

Немного теории, понятной всем:

  • Модулярность – это мера крутизны того, как мы разбиваем граф на группы. Чем сильнее кучкуются вершины внутри группы и меньше связей между группами, тем круче модулярность (ближе к 1)

  • Разбиваем на кластеры (группы друзей/подписчиков): чтобы найти группы друзей/подписчиков, используем алгоритм Лувена и очень-очень-очень много оптимизаций (работа с большими графами – это не работа с малыми графами; банально, но факт). Общий алгоритм Лувена оценивает разбиение по модулярности и старается сделать её максимальной. По-простому: ищет такое разделение, где связей внутри групп много, а между группами мало

  • Размещаем точки-ноды:

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


Label Propagation

Основные отличия в нём:

  1. В алгоритме есть запрет на обновление изначально заданных меток Yk.

  2. Метки обновляются по другому правилу. Для обновления меток используется не нормализованная матрица смежности S, а переходная матрица P.

Алгоритм поиска решения следующий:

  1. Находим матрицу смежности A.

  2. Вычисляем степени вершин графа d.

  3. Строим матрицу степеней D.

  4. Вычисляем переходную матрицу P.

  5. Инициализируем исходные метки.

  6. В цикле, пока решение не сойдётся или не достигнем максимального количества итераций:

а. обновляем матрицу предсказаний Y по следующей итеративной формуле:

здесь Yk — изначально заданные метки узлов. Они с течением времени не обновляются.

б. обновляем номер итерации:

  1. Для каждого узла выбираем наиболее уверенную метку:

Псевдокод

Пример

Возьмём тот же граф, что и в Label Spreading. Зададим такие же начальные метки.

Распространение меток в графе при помощи алгоритма Label Propagation. Цвет вершины определяет её сообщество, интенсивность — уверенность алгоритма.

Ошибок в итоговых метках нет. Также заметим, что заданные метки Yk остаются постоянными.

Код Label Propagation


import networkx as nx

import numpy as np





num_iteration = 100 



A = nx.adjacency_matrix(G).todense()



d = np.sum(A, axis = 1)

D = np.diag(1 / d)



P = D @ A



Y0 = np.zeros((len(G.nodes), 2))

Y0[3, 0], Y0[3, 1] = 0, 1

Y0[35, 0], Y0[35, 1] = 1, 0



Y = Y0

for _ in range(num_iteration):

    Y = P @ Y

    Y[3, 0], Y[3, 1] = Y0[3, 0], Y0[3, 1]

    Y[35, 0], Y[8, 1] = Y0[35, 0], Y0[35, 1]

Static Label Propagation. Unsupervised learning

В двух алгоритмах выше мы рассматривали распространение изначально заданных на части узлов меток. В ML подобного рода задачи относят к классу semi-supervised learning.

На самом деле алгоритмы распространения меток можно использовать, и не имея информации об исходных метках, например, для кластеризации на графах — unsupervised learning.

Давайте рассмотрим один из таких алгоритмов.

В основе алгоритма Static Label Propagation лежит идея о том, что у вершины графа метка / кластер / сообщество будет таким же, как и у её соседей.

Сам алгоритм работает следующим образом:

  1. Изначально каждой вершине графа присваиваем свою уникальную метку.

  2. В цикле, пока решение не сойдётся или не достигнем максимального количества итераций, каждой вершине обновляем метку на ту, которая чаще встречается у её соседей. Если среди соседей самых часто встречаемых меток несколько, выбираем случайную.

Схема работы Static Label Propagation. Цвет вершины соответствует значению метки / кластера.

Этот алгоритм похож на метод ближайших соседей KNN на графах. Заметим, что на каждом шаге происходит обновление меток всех узлов.

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

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

Community detection на больших данных. Label Propagation на Spark


from graphframes import GraphFrame





# Dataframe с вершинами графа

vertices = spark_session.range(1, 9)



# Dataframe с ребрами графа

edges = spark_session.createDataFrame([

    (1, 2), (1, 4), (2, 1), (2, 3), (2, 4),

    (3, 2), (3, 4), (4, 1), (4, 2), (4, 3),

    (5, 6), (5, 7), (5, 8), (6, 5), (6, 8),

    (7, 5), (7, 8), (8, 5), (8, 6), (8, 7),

    (3, 5), (5, 3)

], ["src", "dst"])



graph = GraphFrame(vertices, edges)



lpa_predicts = graph.labelPropagation(maxIter=3)

Пример того, что получается на выходе:

Цвет вершины соответствует ее кластеру.

Простой способ улучшить алгоритм

Обновление меток для каждого узла на каждой итерации в Static LPA может привести к случаям, когда решение будет осциллировать и не будет сходиться. Например:

Что с этим делать? При обновлении меток можно выбирать метки не только среди соседей, но и добавлять к ним метку самой вершины, то есть давать возможность вершине не менять свою метку.

Это можно реализовать следующими способами:

  1. Добавить в код алгоритма логику сохранения метки в узле

  2. Добавить в граф петли (петля — ребро, которое выходит и входит в одну и ту же вершину). Таким образом, вершина станет сама себе соседом.

Такой простой трюк может повлиять на качество решения и его сходимость.

Пример

Давайте посмотрим, как работает Static LPA на графе, в котором есть несколько community. Для этого сгенерируем случайный граф с 7 кластерами.

Код для генерации графа


import numpy as np

import networkx as nx





seed = 2

np.random.seed(seed)



num_clusters = 7

sizes_clusters = np.random.randint(low=10, high=80, size=num_clusters)

p_in = np.random.uniform(low=0.1, high=0.95, size=num_clusters)

p_out = np.random.uniform(low=0.0, high=0.01, size=(num_clusters, num_clusters))

p = (p_out + p_out.T) / 2

np.fill_diagonal(p, p_in)



G = nx.stochastic_block_model(

    sizes=sizes_clusters,

    p=p,

    seed=seed,

)

Поиск кластеров в графе при помощи алгоритма Static Label Propagation. Цвет вершины определяет её сообщество.

Одной из отличительных особенностей Static LPA от многих других unsupervised алгоритмов является отсутствие гиперпараметров. В реализации на Spark единственный параметр, который можем определить, — максимальное количество итераций.

Static LPA начинает решать задачу с состояния, когда каждая вершина графа имеет уникальную метку, со временем количество кластеров (меток) должно уменьшаться и сходиться к какому-то значению.

Количество кластеров в Static LPA на синтетическом графе.

Видно, что к 4-ой итерации количество кластеров перестало меняться. Также на gif выше видно, что метки узлов перестали обновляться — решение сошлось.

Custom Algorithm на Spark. Semi-supervised Static LPA

Unsupervised подход в LPA при поиске групп товаров-дубликатов удобен, когда нет никаких известных кластеров, и их нужно инициализировать с нуля. После того как некоторые кластеры уже существуют, и в пайплайн поступают новые товары, может быть удобно не запускать с нуля кластеризацию на графах (unsupervised), а инициализировать метки уже известных кластеров товаров-дубликатов и доразмечать метки на новых товарах (semi-supervised).

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

В Spark’овой реализации Label Propagation исходные метки всех узлов задаются неизвестными (unsupervised). Что делать в semi-supervised подходе? Мы можем написать свой алгоритм распространения меток на Spark.

В качестве примера реализуем Static LPA с частично известными метками:


from pyspark.sql import functions as F

from graphframes import GraphFrame

from graphframes.lib import AggregateMessages as AM





max_iter = 5



vertices = spark_session.createDataFrame([

	"""Кортежи: (id_вершины, начальная_метка_вершины).

	Для известных узлов проставляем известные метки.

	Для неразмеченных узлов -- уникальные

	"""

], ["id", "label"])



edges = spark_session.createDataFrame([

	"""Кортежи, соответствующие рёбрам: 

	(id_вершины_1, id_вершины_2)

	"""

], ["src", "dst"])



for _ in range(max_iter):

    g = GraphFrame(vertices, edges)

    vertices = g.aggregateMessages(

        F.mode(AM.msg).alias("label"),

        sendToDst=AM.src["label"],

    )

Aggregate messages сначала передаёт сообщения между вершинами, затем выполняет их агрегирование для каждой вершины. В нашем примере в качестве сообщений передаются метки src узлов в узлы dst, а агрегирующей функцией в Static LPA является мода (mode).

Карта Нетворкинга

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

Обозначу без повторений отличия Карты Нетворкинга от Портрета Пользователя:

1) Граф

На графе изображены только друзья/подписчики до 3-го колена (друг друга – это 2-е колено). Друзья/подписчики первого рукопожатия исследуемого имеют с ним одинаковый цвет (“зеленый”, “синий”, “красный” и тд), Если круги первых рукопожатий каждого из двух исследуемых имеют общие связи, то цвет этих связей – смесь цветов исследуемых. У каждого исследуемого есть свой цвет, чтобы можно было удобно раскрашивать связи 2-го и 3-го колена. Исследуемые расположены по кругу.

Карта Нетворкинга 3-х исследуемых до 3-х рукопожатий

Функциональность. Внизу графа есть кнопка «Физика включена».

Подробная информация ноды включает в себя: имя (+ ссылка на профиль), статус страницы (публичная, приватная, забаненная, заблокированная, удалённая), ID, возраст, город, родной город, школы, образование, работу (+ ссылка на место работы), список с кем дружит/на кого подписан (+ ссылка на профиль, жирные – исследуемые), активность (+ ссылка на активность).

Карта Нетворкинга 12-ти исследуемых до 2-х рукопожатий


Выделение сообществ. Community Detection

Задача выделения сообществ (community detection) представляет собой кластеризацию на графах.

Что будем понимать под сообществом?

  1. Внутри сообщества связей (рёбер) много, вершины плотно связаны.

  2. Связей, соединяющих сообщество с остальными, мало.

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

Классический пример — карате-клуб Закари. В этом примере набор данных представляет собой социальный граф, вершинами которого являются участники карате-клуба, а рёбра — общение между ними вне клуба. История гласит, что в клубе произошёл раскол из-за конфликта между владельцем клуба и тренером. Впоследствии одни участники образовали новый клуб, другие остались в старом. Задача community detection на основе информации о связях между участниками клуба нужно определить, к какому из двух сообществ примкнул каждый спортсмен после раскола.

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

Community Detection в матчинге

На основе найденных пар дубликатов можем построить граф, вершинами которого будут товары, а наличие ребра между ними соответствует предсказанию модели, что эти вершины — дубликаты. Цвет вершины определяется её меткой. Метка / label / сообщество / community / кластер — id группы товаров-дубликатов. На рисунках каждому кластеру соответствует свой цвет.

Граф, построенный на результатах Таблицы 1.

На практике, как правило, предсказания модели на парах кандидатов имеют высокое значение precision = TP / (TP + FP), близкое к 1. Иными словами, доля ошибочно сматченных пар (False Positives) мала по сравнению с корректно сматченными (True Positives), потому в графе False Positives рёбер много меньше, чем True Positives. Это позволяет свести задачу к поиску сообществ в графах.

Некоторые моменты из теории графов

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

Для описания графов и работы с ними введём следующие понятия.

Матрица смежности (adjacency matrix) A. Элемент этой матрицы Aij равняется количеству рёбер из i-ой вершины в j-ую вершину графа. В нашем случае элементы матрицы будут принимать только два значения: 1, если товары в паре предсказываются дубликатами; 0, если нет. Например, для графа выше:

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

Степень вершины графа di — это количество рёбер, выходящих из вершины i или, что то же самое в нашем случае, входящих в неё

D — диагональная матрица степеней (degree matrix):

Для примера выше:

Переходная матрица (transition matrix) P:

В нашем примере:

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

Алгоритм Label Spreading

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

Предположим, что мы знаем метки некоторых вершин. Обозначим их Yk.

Тогда алгоритм Label Spreading будет выглядеть следующим образом:

  1. Находим для графа матрицу смежности A.

  2. Вычисляем степени вершин графа d.

  3. Строим матрицу степеней D.

  4. Вычисляем нормализованную матрицу смежности S.

  5. Инициализируем исходные метки. Как это сделать показано далее.

  6. В цикле, пока решение не сойдётся или не достигнем максимального количества итераций:

а. обновляем матрицу предсказаний Y по следующей итеративной формуле:

Здесь первое слагаемое отвечает за то, что каждая вершина обновляет свою метку на основе информации о метках своих соседей, второе — за сохранение информации об исходных метках. alpha — параметр, который отвечает за мягкую фиксацию исходных меток узлов и обеспечивает баланс между обновлением меток и их начальными значениями. При alpha близком к 0, сохраняем информацию о начальных значениях меток, то есть практически не обновляем их. Напротив, при alpha близком к 1, позволяем алгоритму забывать информацию о начальных метках. Также в формуле: t — номер итерации, Y(0) — исходные метки, Y(t) — матрица предсказаний, элемент Yij(t) которой — уверенность алгоритма в том, что i-ый узел имеет j-ую метку на итерации t. Под уверенностью подразумеваем некоторое число, которое лежит в диапазоне от 0 до 1 и показывает, насколько модель уверена в своём предсказании — чем больше число, тем более уверена. Матрица Y содержит для каждой вершины графа вектор предсказаний, представляющий собой уверенности в принадлежности вершины к каждому сообществу.

б. обновляем номер итерации:

  1. Для каждого узла выбираем наиболее уверенную метку:

Псевдокод

Как задаются начальные метки?

Для простоты представим, что у нас есть граф из 6 вершин и 2 сообщества. Предположим, нам известно, что первый узел относится к первому сообществу, третий узел — ко второму, а для остальных вершин сообщество нужно определить. Тогда

Решение в явном виде

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

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

Пример

Рассмотрим пример распространения меток по графу при помощи Label Spreading. Для этого сгенерируем случайный граф из двух сообществ. Зададим в качестве известных метки для двух случайных вершин и посмотрим, как они распространяются с течением времени.

Код для генерации графа


import numpy as np

import networkx as nx





seed = 0

np.random.seed(seed)



num_clusters = 2

sizes_clusters = np.random.randint(low=20, high=41, size=num_clusters)

p_in = np.random.uniform(low=0.1, high=0.4, size=num_clusters)

p_out = np.random.uniform(low=0.0, high=0.06, size=(num_clusters, num_clusters))

p = (p_out + p_out.T) / 2

np.fill_diagonal(p, p_in)



G = nx.stochastic_block_model(

    sizes=sizes_clusters,

    p=p,

    seed=seed,

)

Код Label Spreading


import networkx as nx

import numpy as np





# В графе много узлов, а начальные метки определены только

# для двух вершин. Потому чтобы изначально неизвестные

# метки узлов не сильно тормозили распространение известных, 

# задаем alpha близким к 1.

alpha = 0.99

num_iteration = 8



A = nx.adjacency_matrix(G).todense()



d = np.sum(A, axis=1)

D = np.diag(1 / np.sqrt(d))



S = D @ A @ D



# S можно также найти через normalized Laplacian matrix:

# l = scipy.sparse.csgraph.laplacian(A, normed=True)

# S = np.eye(len(l)) - l



Y0 = np.zeros((len(G.nodes), 2))

Y0[3, 0], Y0[3, 1] = 0, 1

Y0[35, 0], Y0[35, 1] = 1, 0



Y = Y0

for _ in range(num_iteration):

    Y = alpha * S @ Y + (1 - alpha) * Y0

Распространение меток в графе при помощи алгоритма Label Spreading. Цвет вершины определяет ее сообщество, интенсивность — уверенность алгоритма.

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

Особенность алгоритма

В Label Spreading используется «мягкая» фиксация исходных меток, то есть мы разрешаем их изменять. Например, если обратить внимание на gif выше, то видно, что на первой итерации исходно заданные узлы «моргают», поскольку к ним поступает информация от соседей, у которых ещё нет метки.

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

Label Spreading может обновить метку центрального синего узла из-за того, что у всех соседей метка красная.

Таким образом, Label Spreading может оставить прежними или скорректировать исходные метки в зависимости от согласованности с остальными метками узлов графа.

Выводы

Кластеризация на графах — один из этапов поиска групп одинаковых товаров, который позволяет находить кластеры товаров-дубликатов с достаточно большой полнотой (completeness), сравнимой с транзитивным подходом, который мы обсуждали в начале. При том делать это более аккуратно, не умножая ошибки из-за False Positive предсказаний, то есть сохранять однородность (homogeneity) кластеров.

У большинства алгоритмов распространения меток временная сложность порядка O(m), где m — количество рёбер. Некоторые из них, например Static LPA, можно запускать распределённо. Это делает такие алгоритмы масштабируемыми и позволяет их использовать на больших объёмах данных.

На самом деле, на графах товаров можно заниматься не только поиском кластеров. Например, можно использовать Page Rank для поиска самых «важных» вершин в графе. Впрочем, это уже другая история.

Полезные ссылки

  1. David P. Williamson, “Spectral Graph Theory”: https://people.orie.cornell.edu/dpw/orie6334/Fall2016/lecture7.pdf

  2. Mark Crovella, "Linear Algebra, Geometry, and Computation”: https://www.cs.bu.edu/fac/crovella/cs132-book/L19PageRank.html#random-walks-on-undirected-graphs.

  3. Zhou, Dengyong, et al. "Learning with local and global consistency." Advances in neural information processing systems 16 (2003)

  4. L. Zhukov, “Label propagation on graphs”: https://youtu.be/F4f247IyOTs?si=Dw6FOFtfBtM3ITVs

  5. Xiaojin, Zhu, and Ghahramani Zoubin. "Learning from labeled and unlabeled data with label propagation." Tech. Rep., Technical Report CMU-CALD-02–107, Carnegie Mellon University (2002)

  6. А. Вичугова, “Графовая аналитика больших данных с Apache Spark GraphX”:https://bigdataschool.ru/blog/what-is-pregel-and-how-it-is-realized-in-spark-graphx.html

  7. Н. Ешкеев**, “**Обработка больших и очень больших графов. Pregel”: https://habr.com/ru/articles/754598/

  8. GraphX Programming Guide: https://spark.apache.org/docs/latest/graphx-programming-guide.html

  9. Reza Zadeh, "Pregel and GraphX”: https://stanford.edu/~rezab/classes/cme323/S16/notes/Lecture16/Pregel_GraphX.pdf

  10. А. Дьяконов, “Выделение сообществ (Community Detection)”: https://www.youtube.com/watch?v=eNnfeOM3KVE

  11. Albert-László Barabási, “Network Science”: http://networksciencebook.com/chapter/9

Понравилась статья? Поделиться с друзьями:
ТВОЙ ВК
Добавить комментарий