Два сапога — пара, а три — уже community: как алгоритмы на графах помогают собирать группы товаров

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

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

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

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

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

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

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

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

Baseline

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

Можно взять все предсказания с дубликатами и по цепочке, транзитивно собрать их в кластер. Например, если нашли пары [1, 2], [2, 4] и [4, 3], то склеить их в кластер [1, 2, 3, 4]. На языке теории графов такой подход можно было бы назвать выделением компонент связности.

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

Представим, что у нас есть две группы товаров: [1-8], соответствующие iPhone 14, и [9-16] с iPhone 15 Plus. Пусть модель корректно сматчила каждый товар с каждым в группе (True Positive предсказания). Всего таких True Positive предсказаний: TP = 2 * 8 * (8 - 1) / 2 = 56. Также предположим, что модель по ошибке сматчила два разных товара — [3, 15] (False Positive). Наличие одного False Positive предсказания на 56 True Positive в транзитивном подходе приведёт к образованию одного кластера [1-16] из двух разных товаров:

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

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

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

В качестве признаков, например, использовать эмбеддинг (от embedding) — вектор, описывающий какую-либо сущность.</p>" data-abbr="эмбеддинги">эмбеддинги на картинках и названиях товара.

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

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

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

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

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

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

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

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

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

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

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

Community Detection в матчинге

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

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

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

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

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

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

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

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

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

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

Нормализованная матрица смежности (normalized adjacency matrix) S (см. [1]):

где

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

где

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

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

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

Алгоритм Label Spreading

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

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

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

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

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

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

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

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

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

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

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

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

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

Псевдокод

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

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

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

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

Тогда решение:

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

Подробнее с выводом этих формул и алгоритмом можно ознакомиться в лекции [4].

Пример

Рассмотрим пример распространения меток по графу при помощи 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,
)

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 используется «мягкая» фиксация исходных меток, то есть мы разрешаем их изменять. Например, если обратить внимание на gif выше, то видно, что на первой итерации исходно заданные узлы «моргают», поскольку к ним поступает информация от соседей, у которых ещё нет метки.

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

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

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

Label Propagation

Label Propagation — алгоритм, схожий с Label Spreading, который исторически появился раньше [5].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Псевдокод

Пример

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

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

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. В цикле, пока решение не сойдётся или не достигнем максимального количества итераций, каждой вершине обновляем метку на ту, которая чаще встречается у её соседей. Если среди соседей самых часто встречаемых меток несколько, выбираем случайную.

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

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

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

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

При работе с большим объёмом данных для ускорения вычислений часто задачу распределяют по множеству исполнителей (executors). Для работы с графами, например, существует концепция Pregel (Parallel Graph Google). Подробнее про неё и про map-reduce подход на графах можно прочитать в [6-9].

Для запуска Static Label Propagation на большом объёме данных можно воспользоваться пакетом GraphFrames для Apache Spark [10]

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 LPA от многих других unsupervised алгоритмов является отсутствие гиперпараметров. В реализации на Spark единственный параметр, который можем определить, — максимальное количество итераций.

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

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

Custom Algorithm на Spark. Semi-supervised Static LPA

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

В 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).

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

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

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

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

Выводы

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

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

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