Разработка методов работы с графами больших размеров в облачной инфраструктуре

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

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

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

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

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

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

Сначала в Т-Банке мы начали использовать графовые инструменты: JanusGraph, HugeGraph и networkit, это дало нам первое представление об особенностях инструментов работы с графами. Но на больших графах (более 750 млн вершин, 30 млрд связей) столкнулись с обстоятельствами:

1. Скорость обработки данных для аналитики оказалась значительно ниже той, которая нужна для проверки гипотез на временных рядах, построенных на измерениях (срезах) графа большого размера на определенный момент. При этом требования к аппаратным ресурсам оказались значительно выше расчетных.
2. Низкая скорость импорта сырых данных в БД и экспорта результата глобальных расчетов.
3. Сложность универсального решения аналитики реального времени над точечными вершинами и локальными областями, сочетающего асинхронные вычисления глобальных метрик над всем графом.
4. Конфиденциальная природа корпоративных данных большого размера требует применения специальных технологических решений во внутренней инфраструктуре. Большая часть данных и приложений в нашей компании связана с внутренними операциями и не может быть развернута в публичном облаке. В то время как объемы этих данных требуют высокой масштабируемости и отказоустойчивости решения по данным.

Работа с большими (миллиарды ребер), и очень большими (сотни миллиардов ребер) графами формирует важнейшие технические вызовы:

1. Применять оптимальные по памяти высокоэффективные алгоритмы, потому что необходимо работать с графом большого размера с минимальным числом пересылок данных и максимальной локальностью, чтобы повысить эффективность вычислений.
2. Контролировать вычислительные сложности аналитических алгоритмов, чтобы найти решение за разумное время, которое соответствовало бы ожиданиям бизнеса и возможностям вычислительной инфраструктуры.
3. Исследовать, способы распределенного хранения структурированных графовых данных в БД и объектных облачных хранилищах, интеграцию с аналитическими платформами. Кроме того, позволяет ли применение специализированных форматов данных оптимизировать требования к инфраструктуре и повысить эффективность доступа к данным графа в разнообразных сценариях работы. Это важно из-за больших объемов как исходного графа, так результатов аналитических вычислений над ним, поэтому они требуют особых мер хранения и обработки.
4. Интегрировать инструменты аналитических вычислений над графами и результаты их работы в бизнес-процессы так, чтобы аналитики могли их применять с наименьшими дополнительными трудностями.
5. Решить вопрос об эффективном распараллеливании и балансировке нагрузки между вычислительными ядрами, который ставят вершины с огромным числом связей (супер узлов) в графах
6. Существенно доработать инструменты и технологии для обработки графов в части потребления аппаратных ресурсов и коммуникационного профиля, потому что часто они не приспособлены к обработке графов больших размеров
7. Сделать обоснованный выбор наиболее полезных для бизнеса графовых метрик из всего многообразия теоретических знаний, накопленных индустрией за десятилетия. При этом некоторые алгоритмы, крайне полезные на графах малого размера, на больших данных графа настолько сложны вычислительно, что разработка и поиск новых решений и алгоритмов становятся непременным условием.

Решения, подготовленные RnD-центром можно разделить на два направления.

Создание, обогащение и дистрибуция графов. В рамках этого направления мы:

• Изучаем графовые БД — JanusGraph, ArangoDB, Nebula, GraphScope — и способы распределенной обработки данных большого графа внутри БД. В качестве распределенного хранилища данных исследуем Cassandra, Scylla, Greenplum и специализированные форматы хранения в S3, что гарантирует надежность, масштабируемость и скорость доступа к данным.
• Проводим исследования специализированных языков запросов Gremlin, AQL, Cypher, GQL для сценариев OLTP и OLAP, позволяющие в режиме реального времени работать с аналитикой на графе.
• Ищем технологии, которые дают возможность эффективно работать с очень большими графами, хранящимися в Data Warehouse или Data Lakehouse. В сотрудничестве с подразделением нашего центра Profiles Platform построили OLAP/OLTP-кластер графовой БД JanusGraph + Spark + Cassandra.
• Подготовили каталог решений базовых аналитических задач на графах для распространения знаний о языке обхода графов Gremlin среди сотрудников бизнес-линий.
• Реализовали процесс получения 2-hop и 3-hop окружения.

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

На существующих данных от бизнес-линий из DWH с помощью наших новых инструментов мы построили графовые метрики с гранулярностью 1 месяц для периода 2021—2023:

• Меры подобия вершин (Jaccard Similarity, коэффициент Dice-Sørensen). Полезны в определении дубликатов или тесных связей.
• Меры центральности (PageRank, LeaderRank, Katz). Применяются для поиска наиболее влиятельных лиц или ключевых узлов.
• Алгоритмы обнаружения связанных компонент внутри графа. Позволяют обнаруживать изолированные или, напротив, сильно связанные подграфы.
• Кластеризация графа с использованием алгоритмов определения сообществ (например, таким как, Louvain). Дает инструмент поиска мошеннических сообществ.

Метрики можно уже использовать в процессах компании.

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

Задачи, которые мы описали, решаются на уже существующих вычислительных ресурсах компании, например на высокопроизводительном Single Node SMP узле, и с использованием Spark-кластера. Это позволяет интегрировать наши аналитические инструменты и результаты в процессы на Airflow для проведения расчетов и дает возможность в короткие сроки обрабатывать исторические данные больших графов и проводить проверку гипотез полезности метрик на графе, используя ретро тесты в моделях разных бизнес-линий.

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

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

Для реализации цели планируем:

• Глубже разобраться в эффективных подходах хранения больших графов для обеспечения высоких RPS, self-service Ad-hoc аналитики, OLTP- и OLAP-сценариев
• Найти способы повышать качество больших данных используя графы.
• Работать над созданием и применением алгоритмов на темпоральных (динамических) графах, потому что они позволяют значительно снизить вычислительную сложность работы с историческими данными.
• Ускорить процессы валидации и оценки полезности графовых метрик, выявления аномальных или просто важных особенностей, сообществ, шаблонов и прочих свойств любых целевых графов в бизнесе.