Его величество Граф

Графы для меня особенная тема, в них есть нечто таинственное и мощное.

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

Я не буду рассказывать основы графов, они есть в Википедии.

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

Ну что, поехали, будет интересно!

1. Удалить неинтересные столбцы из таблицы (connected components)

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

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

Такие столбцы для архитектурного анализа не интересны (с этой точки зрения они не несут дополнительной ценной информации). Для упрощения надо их убирать. Т.е. если два столбца относятся один-к-одному, можно оставить только один из них. Но надо помнить, что отношения один-к-одному могут также быть между 3мя/4мя… столбцами.

Попытался написать длинный и некрасивый код, который бы это делал. Но потом увидел тут граф и написал это:

# сначала готовим данные для графа # название каждого столбца - вершина # ребро есть только если между вершинами установлено отношение один-к-одному edge_list = [] for col_1, col_2 in it.combinations(df, r=2):     if is_one_one_relation(col_1, col_2):         edge_list.append(cols)  # делаем граф G = nx.Graph() G.add_edges_from(edge_list)  # я сторонник детерминизма, поэтому сначала сортирую каждую компоненту связности # сортировка идет по порядку появления в таблице слева-направо # и только потом удаляю всё кроме первой вершины в каждой компоненте связности ccs = [sorted(cc, key=get_column_pos) for cc in nx.connected_components(G)] to_delete = [cc[1:] for cc in ccs]  # получаем плоский список названий колонок, уже без один-к-одному! # допущение: в шапке таблице нет названий-дубликатов to_delete = list(it.chain.from_iterable(to_delete))

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

2. Упростить граф для визуальной наглядности (transitive reduction)

Опять-таки моя библиотека FlatTableAnalysis. Писал визуализацию графа с функциональными зависимостями между колонками (вершины — колонки таблицы, ребра — функциональные зависимости). Обычно получается сложный портрет. Хочется проще. Один из вариантов удалить ребра, которые «логически» следуют из других.

Транзитивные зависимости

Ребро 1->4 можно и не рисовать. В целом понятно, что из вершины 1 можно дойти до вершины 4. Без ребра 1->4 граф будет заметно проще, а суть сохранится.

В реальных графах не 4 вершины и это все быстро становится не читаемым.

Конечно, данный подход не всегда применим, зависит от задачи. В моём случае, удалить такие ребра было допустимо.

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

# строим граф G = nx.DiGraph() G.add_edges_from(edge_list)  # весь код - одна строчка :) G_tr = nx.transitive_reduction(G)  # тут небольшая особенность # в новый граф надо скопировать данные вершин и ребер вручную из старого G_tr.add_nodes_from(G.nodes(data=True)) G_tr.add_edges_from((u, v, G.edges[u, v]) for u, v in G_tr.edges)

3. Расселить людей учитывая их пожелания (inverted graph, maximal independent set)

Раз в год мы отдыхаем где-нибудь коллегами. В этот раз решили с ночевкой. Решили, что в номерах будем по двое. Каждому прислали формочку от HR, где он отметил список тех, с кем хотел бы заселиться. По сути, на выходе будет табличка с двумя колонками: «сотрудник», «список с кем хочет заселится».

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

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

1. Взять граф пожеланий людей (вершина — человек, ребра — пожелания)

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

3. Далее надо сделать новый граф, особым образом — Рёберный_граф. Каждое ребро старого графа, становится вершиной. Если ребра были смежные в старом графе, то в новом графе между такими вершинами будет ребро.

4. В новом графе, если между двумя вершинами есть ребро, значит обе вершины брать нельзя. Надо взять максимальное количество вершин, но чтобы ребер не было вообще. А это определение maximal independent set алгоритма. Я даже снял короткое видео про это, там понятнее все объяснено.

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

4. Автоматически удалить неточные дубликаты (Minimum vertex cover)

Это мой любимый случай. Есть список из коротких строк. Там есть неточные дубликаты Допустим, установлен какой-то порог по нормированному расстоянию Левенштейна. Как автоматически удалить все неточные дубликаты из такого списка? Вообще, если быть точным, то задача должна звучать так:

Как удалить минимальное количествово строк, после чего никакая пара из оставшихся не будет отвечать определению неточных дубликатов?

Первая мысль — давайте посчитаем Левенштейна по всем парам. Если в паре расстояние менее порога (=неточные дубликаты) — удалим любую вершину из двух. Оказывается, этот метод не гарантирует минимальность. Хотя в реальных задачах, думаю, это оптимальный путь (быстрый и понятный).

Пример невыполнения условия "минимальности", если используем алгоритм выше:    строчки A, B, C A-B - дубликаты B-C - дубликаты A-C - не дубликаты  Есть вероятность того, что наш алгоритм удалит вершины A, С Это избыточно, можно просто B удалить!

Для точного решения этой задачи потребуется такой алгоритм:

1. Посчитать все расстояния, сделать граф (строки — вершины, ребра — расстояния между ними)

2. Удалить все ребра более порога (они не являются дубликатами => нам не интересны)

3. Разбить граф на компоненты связности

4. Для каждой компоненты применить — Minimum vertex cover алгоритм. Логика простая. Мы можем удалять вершины, но надо удалить как можно меньше. После удаления надо, чтобы ребер в графе не было (т.к. на этом шаге у нас были только ребра менее порога, т.е. неточные дубликаты). Алгоритм Minimum vertex cover как раз и даст нам минимальный набор вершин для удаления (чтобы ребер вообще не осталось)

5. Последним шагом надо из исходного набора вершин удалить набор, который получился на шаге 4

   По этой задаче я снял видео, там объясняю решение подробнее.

   На шаге 4 можно было использовать Maximal independent set алгоритм. По идее, результаты должны быть идентичными.

5. Настроить закрытие затрат между производственными подразделениями без циклов (simple cycles, Feedback arc set)

А это прямо боевая задача. Из двух частей.

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

list(nx.simple_cycles(graph)) # код может зависнуть, т.к. в графах может быть огромное кол-во циклов  # поэтому мы делали так: itertools.islice(nx.simple_cycles(graph), 10_000) # и отдавали коллегам посмотреть))

Но, конечно, коллеги на этом не остановились. Они попросили найти способ убрать циклы, чтобы гарантировать, что граф будет feedback_arc_set(weights=None, method=’eades’). Это ровно то что нужно =) Единственное, для применения алгоритма граф надо было переводить из networkx в igraph, а потом обратно (в igraph есть две хорошие utils functions: from_networkx, to_networkx).

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

Так что графы это не только networkx. Но еще иногда igraph,

6. Разбить датасет на 10 частей учитывая пересечения (Balanced Graph Partitioning)

Это, пожалуй, самый сложный случай.

Kaggle — отличное место для получения новых знаний по нейросетям, LLM, обучению энкодеров и т.д. В каком-то смысле, лучше любых курсов.

Встретил там соревнование Learning Equality — Curriculum Recommendations. Немного про задачу. Есть темы, есть обучающие материалы, обе сущности — это просто текстовые строчки. Отношения между ними — многое-ко-многим. Планировалось обучение би-энкодера (BERT) на задачу семантической близости. Для обучения есть датасет. Теперь вопрос, как разделить датасет с учетом 10 K-Folds? (так делал автор 1st prize решения на leaderboard)

Вроде как просто, берем и делим на 10 частей. Но есть нюанс. Так как темы и материалы соотносятся многое-ко-многим, надо поделить так, чтобы пересечений было поменьше. Наглядно про пересечения — под спойлером.

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

Я, как обычно, задался вопросом, а можно ли решить более точным способом?

У нас есть Темы, их обычно меньше. И Материалы, их побольше.

Можно сделать так:

1. Взять наши Темы, это будут вершины графа

2. Каждая Тема имеет связи с какими-то Материалами

3. Давайте сделаем так, что ребра нашего графа — это количество общих Материалов между двумя соответствующими Темами. Пример для понимания под спойлером ниже.

4. Ок, граф есть. Теперь надо разделить граф на две 10 частей. В идеале надо минимизировать сумму весов ребер между всеми частями (т.к. это и есть сила пересечений). Но в такой формулировке, я решения не нашел. Будем минимизировать хотя бы просто количество пересечений Тем между частями.

После поисков я понял, что networkx и igraph не помогут. Там ничего похожего не нашел. Можно, наверное, свести задачу к graph partitioning или community detection, но это всё-таки сильное изменение изначальное задачи.

Пришлось искать другой способ. Нашел статью и git. Почти подходит — алгоритм Balanced Graph Partitioning. Единственное, веса ребер не учитываются, только факт пересечения между частями. Цитата:

«In this paper we consider the problem of (k, ν)-balanced graph partitioning — dividing the vertices of a graph into k almost equal size components (each of size less than ν · n k ) so that the capacity of edges between different components is minimized.»

На полном графе из kaggle я алгоритм не проверял, там сотни тысяч вершин и ребер. Поэтому есть подозрение, что будут проблемы со скоростью. Однако решение через Balanced Graph Partitioning — наиболее близкое к идеальному математическому. Что для меня было важно.

Еще примеры инструментов, в основе которых — прямо или косвенно лежит граф

Визуализация — применяем библиотеку graphviz, для простых случаев networkx. Для нагруженных графов можно сделать community detection и рисовать только их. Иначе может получиться паутина.

Деревья (частный случай графа) — постоянно встречаются. Справочники часто представлены в виде иерархии (сотрудники, материалы, компании). Договоры могут быть представлены в виде иерархии (если используют системную нумерацию: 1 — 1.1 — 1.1.1 — 1.1.2 и т.д.).

Openstreetmap — недавно решали задачу получения транспортных расстояний между адресами. Открытое решение сильно связано с графами. Базируется на networkx. Части графа карт можно даже скачать локально для использования.

Задачка про волка, козу и капусту (river crossing puzzle) — в бизнесе встречается не часто)) но удивительно, что размер лодки для гарантированного решения связан с Minimum vertex cover алгоритмом.

Движок расчетов в MS Excel — под капотом работает так: из всех ячеек с формулами формируется граф связей — DAG (случаи циклических ссылок мы не берем). Затем делается топологическая сортировка и далее последовательно, ячейка за ячейкой, проводятся расчеты по формулам.

И многое другое имеет определенную связь с графами: BERT self-attention, Page rank алгоритм, Finite-state machine, python AST дерево, бизнес-процессы…

Как начать использовать графы на практике? Пара советов

Видеть граф

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

Знать базовые метрики графа

Когда логически понятно где граф, сразу надо задаваться следующими вопросами про его базовую топологию:

1. Сколько вершин

2. Сколько ребер

3. Есть ли петли (когда вершина сама с собой связана ребром)

4. Есть ли кратные ребра (например, между двумя вершинами два ребра в ненаправленном графе, не частое явление)

5. Сколько компонент связности в графе (набор вершин, которые прямо или косвенно связаны по ребрам, формирует одну компоненту связности)

Портрет графа

Далее можно думать, надо ли рисовать портрет графа (так называется визуальное представление графа). Часто это помогает увидеть структуру, которую не видно по метрикам.

Формулировать задачу в терминах графа

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