Области применения аналитики на графах в доменах бизнеса
Почему мы разрабатываем методы работы с графами больших размеров
Данные для аналитиков — основа для принятия решений. При этом один из самых полезных источников знаний — анализ структуры связей между сущностями. Аналитики используют для исследования свойств связей технологии графовой аналитики. Они способны выявлять сложные взаимосвязи в данных и количественно их характеризовать.
Мы в R&
Основным объектом анализа являются графы — структуры, позволяющие представить данные как связанные отношениями сущности, например, пользователи социальных сетей, финансовые транзакции или логистические маршруты. Графы состоят из вершин и ребер и могут содержать широкий набор атрибутов, характеризующий количественно и качественно сущности и связи между ними.
Графы дают глубокое понимание структуры связей в данных, и возможность использовать аналитические алгоритмы для поиска скрытых закономерностей или другой полезной информации. Структуры графов сложно анализировать, но они хорошо моделируют реальный мир вокруг нас и потому содержат уникальные и полезные инсайты, которые сложно получить иными способами.
Работа с графами больших размеров в облачной инфраструктуре позволяет существенно расширить возможности и повысить эффективность аналитики для широкого набора задач компании.
Постановка задачи
Если для аналитики связей использовать специализированные графовые БД и алгоритмы анализа графов, можно получить дополнительные преимущества в производительности и доступных методах анализа перед классическими методами работы с данными. Они позволяют формировать в компании инфраструктуру для работы с графами для задач из разных областей.
Сначала в
- Скорость обработки данных для аналитики оказалась значительно ниже той, которая нужна для проверки гипотез на временных рядах, построенных на измерениях (срезах) графа большого размера на определенный момент. При этом требования к аппаратным ресурсам оказались значительно выше расчетных.
- Низкая скорость импорта сырых данных в БД и экспорта результата глобальных расчетов.
- Сложность универсального решения аналитики реального времени над точечными вершинами и локальными областями, сочетающего асинхронные вычисления глобальных метрик над всем графом.
- Конфиденциальная природа корпоративных данных большого размера требует применения специальных технологических решений во внутренней инфраструктуре. Большая часть данных и приложений в нашей компании связана с внутренними операциями и не может быть развернута в публичном облаке. В то время как объемы этих данных требуют высокой масштабируемости и отказоустойчивости решения по данным.
Цель нашего направления аналитики над графами
- Разработать собственные или адаптировать существующие решения для графовой аналитики, позволяющие бизнесу получить доступ к анализу графовых данных
- Создать инструменты и процессы, которые обеспечиваю высокую производительность, масштабируемость, надежность и минимальные затраты на эксплуатацию.
Технические вызовы
Работа с большими (миллиарды ребер), и очень большими (сотни миллиардов ребер) графами формирует важнейшие технические вызовы:
- Применять оптимальные по памяти высокоэффективные алгоритмы, потому что необходимо работать с графом большого размера с минимальным числом пересылок данных и максимальной локальностью, чтобы повысить эффективность вычислений.
- Контролировать вычислительные сложности аналитических алгоритмов, чтобы найти решение за разумное время, которое соответствовало бы ожиданиям бизнеса и возможностям вычислительной инфраструктуры.
- Исследовать, способы распределенного хранения структурированных графовых данных в БД и объектных облачных хранилищах, интеграцию с аналитическими платформами. Кроме того, позволяет ли применение специализированных форматов данных оптимизировать требования к инфраструктуре и повысить эффективность доступа к данным графа в разнообразных сценариях работы. Это важно
из-за больших объемов как исходного графа, так результатов аналитических вычислений над ним, поэтому они требуют особых мер хранения и обработки. - Интегрировать инструменты аналитических вычислений над графами и результаты их работы в
бизнес-процессы так, чтобы аналитики могли их применять с наименьшими дополнительными трудностями. - Решить вопрос об эффективном распараллеливании и балансировке нагрузки между вычислительными ядрами, который ставят вершины с огромным числом связей (
супер узлов ) в графах - Существенно доработать инструменты и технологии для обработки графов в части потребления аппаратных ресурсов и коммуникационного профиля, потому что часто они не приспособлены к обработке графов больших размеров
- Сделать обоснованный выбор наиболее полезных для бизнеса графовых метрик из всего многообразия теоретических знаний, накопленных индустрией за десятилетия. При этом некоторые алгоритмы, крайне полезные на графах малого размера, на больших данных графа настолько сложны вычислительно, что разработка и поиск новых решений и алгоритмов становятся непременным условием.
Примеры вычислительной сложности алгоритмов аналитики на графах
Наработки
Решения, подготовленные
Создание, обогащение и дистрибуция графов. В рамках этого направления мы:
- Изучаем графовые БД — 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 окружения.
Эффективный анализ графов. Для решения задач этого направления мы создаем инструменты вычисления разнообразных графовых свойств и метрик, полезных в аналитических процессах, пригодных для построения
На существующих данных от
- Меры подобия вершин (Jaccard Similarity, коэффициент
Dice-S ørensen). Полезны в определении дубликатов или тесных связей. - Меры центральности (PageRank, LeaderRank, Katz). Применяются для поиска наиболее влиятельных лиц или ключевых узлов.
- Алгоритмы обнаружения связанных компонент внутри графа. Позволяют обнаруживать изолированные или, напротив, сильно связанные подграфы.
- Кластеризация графа с использованием алгоритмов определения сообществ (например, таким как, Louvain). Дает инструмент поиска мошеннических сообществ.
Метрики можно уже использовать в процессах компании.
У наших инструментов модульная структура, она позволяют легко расширять вычислительную функциональность для реализации дополнительных метрик и возможностей.
Архитектура решения для вычислительных алгоритмов на графах
Задачи, которые мы описали, решаются на уже существующих вычислительных ресурсах компании, например на высокопроизводительном Single Node SMP узле, и с использованием
Планы
Мы хотим создать эффективную и современную технологическую платформу, которая дает возможность:
- работать с большими графами и совершать вычислениям над ними независимо от их природы и размера, для всех заинтересованных
бизнес-линий компании; - использовать лучшие и новейшие технологии работы с графами в распределенных средах.
Для реализации цели планируем:
- Глубже разобраться в эффективных подходах хранения больших графов для обеспечения высоких RPS,
self-service Ad-hoc аналитики, OLTP- и OLAP-сценариев - Найти способы повышать качество больших данных используя графы.
- Работать над созданием и применением алгоритмов на темпоральных (динамических) графах, потому что они позволяют значительно снизить вычислительную сложность работы с историческими данными.
- Ускорить процессы валидации и оценки полезности графовых метрик, выявления аномальных или просто важных особенностей, сообществ, шаблонов и прочих свойств любых целевых графов в бизнесе.