ivantipow 7 фев в 09:59

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

14 мин

25K

Блог компании Ozon TechData Mining*Алгоритмы*Big Data*Машинное обучение*

Кейс

✏️ Технотекст 2023

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

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

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

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

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

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

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

product_id1	product_id2	is_duplicate
1	2	True
1	3	True
1	4	False
2	3	True
2	5	False
4	5	True

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

Baseline

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

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

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

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

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

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

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

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

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

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

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

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

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

Классический пример — карате-клуб Закари. В этом примере набор данных представляет собой социальный граф, вершинами которого являются участники карате-клуба, а рёбра — общение между ними вне клуба. История гласит, что в клубе произошёл раскол из-за конфликта между владельцем клуба и тренером. Впоследствии одни участники образовали новый клуб, другие остались в старом. Задача 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. Элемент этой матрицы A_ij равняется количеству рёбер из i-ой вершины в j-ую вершину графа. В нашем случае элементы матрицы будут принимать только два значения: 1, если товары в паре предсказываются дубликатами; 0, если нет. Например, для графа выше:

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

$A_{ij}= A_{ji}$

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

$d_i = \sum_j A_{ij} = \sum_j A_{ji}$

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

$D= \text{diag}(d)= \begin{pmatrix} d_1 & 0 & \dots & 0\\ 0 & d_2 & \dots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \dots & d_n\\ \end{pmatrix}$

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

$D= \text{diag}(d)= \begin{pmatrix} 2 & 0 & 0 & 0 & 0\\ 0 & 2 & 0 & 0 & 0\\ 0 & 0 & 2 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}$

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

$S = D^{-1/2} A D^{-1/2}$

где

$D^{-1/2} = \begin{pmatrix} \frac{1}{\sqrt{d_1}} & 0 & \dots & 0\\ 0 & \frac{1}{\sqrt{d_2}} & \dots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \dots & \frac{1}{\sqrt{d_n}}\\ \end{pmatrix}$

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

$P = D\text{}^{-\text{1}} A$

где

$D^{-1} = \begin{pmatrix} \frac{1}{d_1} & 0 & \dots & 0\\ 0 & \frac{1}{d_2} & \dots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \dots & \frac{1}{d_n}\\ \end{pmatrix}$

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

$D^{-1}= \begin{pmatrix} \frac{1}{2} & 0 & 0 & 0 & 0\\ 0 & \frac{1}{2} & 0 & 0 & 0\\ 0 & 0 & \frac{1}{2} & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}$

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

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

Алгоритм Label Spreading

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

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

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

Находим для графа матрицу смежности A.
Вычисляем степени вершин графа d.
Строим матрицу степеней D.
Вычисляем нормализованную матрицу смежности S.
Инициализируем исходные метки. Как это сделать показано далее.
В цикле, пока решение не сойдётся или не достигнем максимального количества итераций:

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

$Y(t+1)=\alpha S Y(t) + (1 - \alpha) Y(0), \quad \alpha \in [0, 1]$

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

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

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

$\text{predicts} = \underset{\text{label}}{\text{arg max }} Y$

Псевдокод

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

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

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

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

$\lim_{t\rightarrow\infty}Y(t) = \lim_{t\rightarrow\infty} [\alpha S Y(t-1) + (1 - \alpha) Y(0)]$ $\hat{Y} = \alpha S \hat{Y} + (1 - \alpha) Y(0)$

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

$\hat{Y} = (I-\alpha S)^{-1} (1 - \alpha) Y(0)$

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

Подробнее с выводом этих формул и алгоритмом можно ознакомиться в лекции [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,
)

Код 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 может оставить прежними или скорректировать исходные метки в зависимости от согласованности с остальными метками узлов графа.

Label Propagation

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

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

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

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

Находим матрицу смежности A.
Вычисляем степени вершин графа d.
Строим матрицу степеней D.
Вычисляем переходную матрицу P.
Инициализируем исходные метки.
В цикле, пока решение не сойдётся или не достигнем максимального количества итераций:

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

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

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

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

$\text{predicts} = \underset{\text{label}}{\text{arg max }} Y$

Псевдокод

Пример

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

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

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

Код 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 лежит идея о том, что у вершины графа метка / кластер / сообщество будет таким же, как и у её соседей.

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

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

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

Этот алгоритм похож на метод ближайших соседей 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 может привести к случаям, когда решение будет осциллировать и не будет сходиться. Например:

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

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

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

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

Пример

Давайте посмотрим, как работает 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).

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

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

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

Большой граф, состоящий из товаров-дубликатов.

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

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

Выводы

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

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

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

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

David P. Williamson, “Spectral Graph Theory”: https://people.orie.cornell.edu/dpw/orie6334/Fall2016/lecture7.pdf
Mark Crovella, "Linear Algebra, Geometry, and Computation”: https://www.cs.bu.edu/fac/crovella/cs132-book/L19PageRank.html#random-walks-on-undirected-graphs.
Zhou, Dengyong, et al. "Learning with local and global consistency." Advances in neural information processing systems 16 (2003)
L. Zhukov, “Label propagation on graphs”: https://youtu.be/F4f247IyOTs?si=Dw6FOFtfBtM3ITVs
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)
А. Вичугова, “Графовая аналитика больших данных с Apache Spark GraphX”: https://bigdataschool.ru/blog/what-is-pregel-and-how-it-is-realized-in-spark-graphx.html
Н. Ешкеев, “Обработка больших и очень больших графов. Pregel”: https://habr.com/ru/articles/754598/
GraphX Programming Guide: https://spark.apache.org/docs/latest/graphx-programming-guide.html
Reza Zadeh, "Pregel and GraphX”: https://stanford.edu/~rezab/classes/cme323/S16/notes/Lecture16/Pregel_GraphX.pdf
GraphFrames User Guide. Label Propagation Algorithm (LPA): https://graphframes.github.io/graphframes/docs/_site/user-guide.html#label-propagation-algorithm-lpa
А. Дьяконов, “Выделение сообществ (Community Detection)”: https://www.youtube.com/watch?v=eNnfeOM3KVE
Albert-László Barabási, “Network Science”: http://networksciencebook.com/chapter/9

Теги:

Хабы:

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

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

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

Baseline

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

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

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

Community Detection в матчинге

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

Алгоритм Label Spreading

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

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

Пример

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

Label Propagation

Пример

Static Label Propagation. Unsupervised learning

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

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

Пример

Custom Algorithm на Spark. Semi-supervised Static LPA

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

Выводы

Публикации

Информация