Алгоритмы на графах: обзор Graph Data Science

Когда обхода Cypher мало: библиотека готовых графовых алгоритмов и как она работает.

Graph Data Science (GDS) — плагин Neo4j с промышленными реализациями графовых алгоритмов: центральности, обнаружение сообществ, поиск путей, похожесть.

В прошлом уроке мы выжали из Cypher максимум: рекомендации, пути, треугольники. Но как только задача требует «посмотреть на граф целиком и посчитать что-то про каждый узел» — Cypher упирается в потолок. Кто самый влиятельный человек в сети из миллиона? На какие естественные группы распадается граф? У этих вопросов нет короткого паттерна-обхода: ответ требует многократного прохода по всему графу с накоплением чисел. Ровно для этого существует отдельная библиотека GDS — набор отлаженных, многопоточных реализаций классических графовых алгоритмов.

Зачем отдельная библиотека

Cypher отлично ищет паттерны, но плохо подходит для итеративных алгоритмов на всём графе: PageRank, поиск сообществ, центральности требуют многократного прохода по миллионам узлов с накоплением чисел. GDS реализует их на оптимизированном движке, работающем с графом, загруженным в память.

Можно ли тот же PageRank написать вручную на Cypher? Технически да — но это будут десятки строк с ручными итерациями, медленно и хрупко. Это как сортировать массив пузырьком, когда в стандартной библиотеке есть быстрая сортировка: смысл библиотеки именно в том, чтобы дать выверенную, оптимизированную реализацию, которой можно доверять в проде. Поэтому правильный рефлекс такой: «ищу паттерн или путь — пишу Cypher; считаю метрику по всему графу — беру GDS».

Проекция графа

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

CALL gds.graph.project(
  'social',                 // имя проекции
  'Person',                 // какие узлы
  'ЗНАЕТ'                    // какие связи
)

Проекция — ключевая идея, без которой GDS не понять. Вы как бы говорите: «возьми из всей базы только узлы Person и связи ЗНАЕТ, забудь про их свойства и собери компактный граф в памяти под именем social». Дальше алгоритмы гоняются по этому имени. Зачем эта прослойка? Во-первых, итеративному алгоритму нужен граф в форме плотных массивов, а не транзакционного хранилища — так проходы в разы быстрее. Во-вторых, проекция изолирует расчёт: вы можете спокойно считать PageRank на «слепке», пока основная база принимает записи. Проекцию создают один раз, прогоняют по ней несколько алгоритмов, а потом удаляют gds.graph.drop('social'), освобождая память.

Четыре семейства алгоритмов

Пример: PageRank

PageRank измеряет влиятельность узла по входящим связям от других влиятельных узлов (тот самый алгоритм Google). На соцграфе он находит «авторитетов»:

CALL gds.pageRank.stream('social')
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS person, score
ORDER BY score DESC
LIMIT 10

Режим .stream возвращает результат потоком; есть ещё .write (записать score как свойство) и .mutate (записать в проекцию для следующего алгоритма).

Три режима — это не три разных алгоритма, а три способа распорядиться результатом одного и того же расчёта. stream просто отдаёт пары «узел, score» вам на экран — удобно поисследовать. write сохраняет score обратно в основную базу как свойство узла (p.pagerank = ...), чтобы потом фильтровать и сортировать обычным Cypher: «покажи топ-авторитетов в Москве». mutate кладёт результат в саму проекцию, не трогая базу, — это нужно, когда следующий алгоритм должен использовать score предыдущего (например, сначала PageRank, потом фильтрация сообществ по влиятельности). Выбор режима — это вопрос «что я делаю с числом дальше».

Обнаружение сообществ

Louvain группирует узлы в сообщества по плотности связей — так находят кластеры друзей, тематические группы, кольца мошенников:

CALL gds.louvain.stream('social')
YIELD nodeId, communityId
RETURN communityId, count(*) AS members
ORDER BY members DESC

Louvain отвечает на вопрос, который раньше мы лишь нащупывали треугольниками: на какие естественные группы распадается граф. Каждому узлу он присваивает номер сообщества communityId, максимизируя «модулярность» — формальную меру того, насколько внутри групп связей больше, чем между ними. В соцсети это вузовские потоки, рабочие коллективы, землячества; в антифроде — спаянные кольца аккаунтов, которые поодиночке выглядят невинно. Родственный, но более грубый алгоритм — WCC (слабо связные компоненты): он просто делит граф на куски, между которыми вообще нет рёбер, и отлично ловит «осколки» — изолированные группы, оторванные от основной сети.

Центральности: разные смыслы «важности»

Важно понимать, что «влиятельность» бывает разной. PageRank ценит того, на кого ссылаются влиятельные. Degree-центральность — это просто число связей (самый общительный). А Betweenness измеряет, через сколько кратчайших путей проходит узел, то есть находит «мосты» и «привратников»: человека с малым числом друзей, но соединяющего два больших мира. В антифроде именно betweenness-узлы часто оказываются посредниками-обнальщиками. Выбор центральности — это выбор определения «важного» под вашу задачу.

Как работает под капотом

GDS загружает проекцию в компактные массивы в оперативной памяти (не в обычное store-хранилище) и гоняет по ним многопоточные итеративные алгоритмы. PageRank, например, повторяет распространение «веса» по рёбрам до сходимости. Именно поэтому нужна проекция: алгоритму нужен граф в форме, удобной для быстрых проходов, а не транзакционное хранилище. После расчёта результат либо стримится, либо пишется обратно в основную базу как свойства.

Разберём «итеративность» на PageRank. В начале каждому узлу дают равный «вес». На каждой итерации узел раздаёт свой вес поровну по исходящим рёбрам, а сам получает вес от тех, кто ссылается на него. Через несколько проходов числа стабилизируются (сходятся) — это и есть итоговый score. Чтобы такие проходы были быстрыми, проекция хранит граф в виде плотных массивов смежности, по которым процессор бежит без обращений к диску и с хорошей локальностью кэша; работа ещё и распараллеливается по ядрам. Отсюда и требование к памяти: чем больше узлов и рёбер в проекции, тем больше RAM нужно, и поэтому в проекцию берут только нужные метки и типы связей, а не «всё подряд».

Частые ошибки

• Запускать алгоритм без проекции. GDS работает по именованной проекции графа, а не напрямую по базе.
• Путать режимы. stream — посмотреть, write — сохранить в базу, mutate — оставить в проекции для следующего шага.
• Проецировать весь граф зря. Берите в проекцию только нужные метки и типы связей — память не бесконечна.
• Ждать алгоритмы в Community «из коробки». GDS — отдельный плагин; его устанавливают/включают отдельно.

Итоги

• GDS даёт промышленные графовые алгоритмы: центральности, сообщества, пути, похожесть.
• Работа идёт по проекции графа в памяти, результат можно записать обратно.
• PageRank ищет влиятельных, Louvain — сообщества; режимы stream/write/mutate.
• Это плагин для итеративных вычислений, а не замена Cypher-обходам.