GraphBLAS (произносится ) — спецификация API, определяющая стандартные строительные блоки для алгоритмов на графах на языке линейной алгебры. GraphBLAS основан на идее, что разреженная матрица может использоваться для представления графов в виде матрицы смежности или матрицы инцидентности. Спецификация описывает, как операции над графами (например, обход и преобразование графов) могут быть эффективно реализованы с помощью методов линейной алгебры (например, умножения матриц) над различными полукольцами.
Разработка GraphBLAS и различных его реализаций — это непрерывная совместная работа сообщества, включающего представителей промышленности, академической науки и государственных исследовательских лабораторий.
История
Идея о том, что граф можно представить в виде матрицы, а операции над ним выполнять как линейные преобразования и другие операции линейной алгебры над разреженными матрицами, применяется в алгоритмах на графах уже давно. Например, умножение матрицы на вектор может использоваться для выполнения одного шага поиска в ширину.
Стандарт GraphBLAS разрабатывается с 2013 года. Название было выбрано по аналогии с BLAS (Basic Linear Algebra Subprograms) — стандартом для операций над плотными матрицами. Первая официальная версия C API вышла 29 мая 2017 года, актуальная версия — 2.1.0 (декабрь 2023 года).
Описание
Спецификация GraphBLAS (и различные её реализации) предоставляет структуры данных и функции для вычисления операций линейной алгебры. В частности, GraphBLAS определяет объекты разреженных матриц, которые хорошо подходят для графов, где вершины, как правило, связаны с небольшим числом соседей (то есть степень вершины значительно меньше общего числа вершин графа). Спецификация также допускает использование различных полуколец для выполнения операций в разнообразных математических контекстах.
Изначально GraphBLAS создавался для стандартизации анализа графов, однако впоследствии привлёк интерес исследователей из областей машинного обучения и биоинформатики.
Математические основы
Каждая операция над графами в GraphBLAS выполняется над полукольцом, которое состоит из следующих элементов: скалярной операции сложения (⊕); скалярной операции умножения (⊗); носителя (домена значений).
Нулевой элемент (то есть элемент, представляющий отсутствие ребра в графе) также может переопределяться. Примеры алгебр, реализуемых в GraphBLAS:
Алгебра ⊕ ⊗ Домен Нулевой элемент Стандартная арифметика + × ℝ 0 Алгебра max–plus max + {−∞} ∪ ℝ −∞ Алгебра min–plus min + {+∞} ∪ ℝ +∞ Алгебра max–min max min [0, +∞) 0 Алгебра min–max min max (−∞, 0] 0 Поле Галуа GF(2) XOR AND {0, 1} 0
Ключевое наблюдение: при обобщении пары скалярных операций с определением полукольца можно расширить набор примитивов для поддержки широкого класса параллельных алгоритмов на графах. Например, применение алгебры min–plus к разреженным матрицам смежности позволяет вычислять кратчайшие пути в взвешенном графе.
Основные возможности спецификации
Несмотря на то что спецификация GraphBLAS в целом допускает значительную свободу реализации, некоторые функции и детали явно предписываются ею: Объекты GraphBLAS, включая матрицы и векторы, являются непрозрачными структурами данных. Неблокирующий режим исполнения, допускающий ленивое или асинхронное вычисление отдельных операций. Операция присваивания с маской: присваивает элементы матрицы только там, где элементы маски ненулевые. Реализации библиотек должны быть потокобезопасными.
Реализации
Формально спецификация GraphBLAS описана для языка программирования C, однако ряд реализаций создан в духе GraphBLAS на других языках, включая C++, Java и CUDA от Nvidia.
В настоящее время существуют две полностью соответствующие спецификации эталонные реализации. Привязки, предполагающие совместимую реализацию, доступны для языков Python, MATLAB и Julia.
SuiteSparse:GraphBLAS
SuiteSparse:GraphBLAS — полная реализация стандарта GraphBLAS, разработанная Тимоти Дэвисом из Техасского университета A&M. Библиотека определяет набор операций с разреженными матрицами над расширенной алгеброй полуколец с практически неограниченным разнообразием операторов и типов данных.
SuiteSparse:GraphBLAS активно применяется в промышленных приложениях: служит встроенным движком графовой базы данных FalkorDB (ранее RedisGraph от Redis); начиная с версии MATLAB R2021a используется для ускоренного умножения разреженных матриц (операция C = A*B на 20-ядерном процессоре работает до 30 раз быстрее по сравнению с предыдущими версиями).
Разработка SuiteSparse:GraphBLAS поддерживается компаниями Intel, Nvidia, Redis, MIT Lincoln Lab, MathWorks, IBM и Julia Computing.
LAGraph
LAGraph — библиотека высококачественных алгоритмов на графах, построенных поверх GraphBLAS. Если GraphBLAS ориентирован на разработчиков алгоритмов (низкоуровневые примитивы), то LAGraph нацелен непосредственно на конечных пользователей, которым нужны готовые алгоритмы. В первом выпуске LAGraph реализованы версии алгоритмов из набора тестов GAP Benchmark Suite.
Применение
Реализации GraphBLAS нашли применение в высокопроизводительных графовых базах данных (FalkorDB, ранее — RedisGraph) и в научных вычислениях. Помимо анализа графов, стандарт привлёк интерес исследователей машинного обучения и биоинформатики.
Ключевое наблюдение, лежащее в основе GraphBLAS: когда граф представлен разреженной матрицей смежности или инциденций, умножение разреженной матрицы на вектор эквивалентно одному шагу поиска в ширину.
Пример кода
Ниже приведён пример реализации поиска в ширину (BFS) на языке C с использованием GraphBLAS 2.1:
#include <stdlib.h> #include <stdio.h> #include <stdint.h> #include <stdbool.h> #include "GraphBLAS.h"
/* * Дано булево матрицу смежности A размером n×n и исходную вершину s. * Выполняет обход графа в ширину и записывает в v[i] уровень, * на котором посещается вершина i (v[s] == 1). * Если вершина i недостижима из s, элемент v[i] не сохраняется. */ GrB_Info BFS(GrB_Vector *v, GrB_Matrix A, GrB_Index s) { GrB_Index n; GrB_Matrix_nrows(&n, A); /* n = число строк A */ GrB_Vector_new(v, GrB_INT32, n); /* вектор уровней */
GrB_Vector q; GrB_Vector_new(&q, GrB_BOOL, n); /* вершины текущего уровня */ GrB_Vector_setElement(q, (bool)true, s); /* q[s] = true */
int32_t level = 0; GrB_Index nvals; do { ++level; /* v[q] = level */ GrB_apply(*v, GrB_NULL, GrB_PLUS_INT32, GrB_SECOND_INT32, q, level, GrB_NULL); /* q[!v] = q ||.&& A — непосещённые преемники */ GrB_vxm(q, *v, GrB_NULL, GrB_LOR_LAND_SEMIRING_BOOL, q, A, GrB_DESC_RC); GrB_Vector_nvals(&nvals, q); } while (nvals);
GrB_free(&q); return GrB_SUCCESS; }
См. также
BLAS — Basic Linear Algebra Subprograms (стандарт для плотных матриц) Матрица смежности Разреженная матрица Алгоритмы на графах Полукольцо Поиск в ширину Параллельные вычисления
Примечания
Литература
Ссылки
Официальный сайт GraphBLAS Forum SuiteSparse:GraphBLAS на GitHub GraphBLAS C++ API Specification на GitHub Mathematical Foundations of the GraphBLAS (arxiv.org) Graphs, Matrices, and the GraphBLAS: Seven Good Reasons (arxiv.org)
Категория:Линейная алгебра Категория:Алгоритмы на графах Категория:Программные библиотеки Категория:Спецификации программного обеспечения Категория:Дискретная математика Категория:Параллельные вычисления