GraphBLAS (произносится /ˈɡræfˌblɑːz/) — спецификация API, определяющая стандартные строительные блоки для алгоритмов на графах на языке линейной алгебры.^[1][2] GraphBLAS основан на идее, что разреженная матрица может использоваться для представления графов в виде матрицы смежности или матрицы инцидентности. Спецификация описывает, как операции над графами (например, обход и преобразование графов) могут быть эффективно реализованы с помощью методов линейной алгебры (например, умножения матриц) над различными полукольцами.^[3]

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

Идея о том, что граф можно представить в виде матрицы, а операции над ним выполнять как линейные преобразования и другие операции линейной алгебры над разреженными матрицами, применяется в алгоритмах на графах уже давно.^[4] Например, умножение матрицы на вектор может использоваться для выполнения одного шага поиска в ширину.

Стандарт GraphBLAS разрабатывается с 2013 года.^[5] Название было выбрано по аналогии с BLAS (Basic Linear Algebra Subprograms) — стандартом для операций над плотными матрицами. Первая официальная версия C API вышла 29 мая 2017 года, актуальная версия — 2.1.0 (декабрь 2023 года).

Спецификация GraphBLAS (и различные её реализации) предоставляет структуры данных и функции для вычисления операций линейной алгебры. В частности, GraphBLAS определяет объекты разреженных матриц, которые хорошо подходят для графов, где вершины, как правило, связаны с небольшим числом соседей (то есть степень вершины значительно меньше общего числа вершин графа). Спецификация также допускает использование различных полуколец для выполнения операций в разнообразных математических контекстах.

Изначально GraphBLAS создавался для стандартизации анализа графов, однако впоследствии привлёк интерес исследователей из областей машинного обучения и биоинформатики.

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

• скалярной операции сложения (⊕);
• скалярной операции умножения (⊗);
• носителя (домена значений).

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

Ключевое наблюдение: при обобщении пары скалярных операций с определением полукольца можно расширить набор примитивов для поддержки широкого класса параллельных алгоритмов на графах. Например, применение алгебры min–plus к разреженным матрицам смежности позволяет вычислять кратчайшие пути в взвешенном графе.

Несмотря на то что спецификация GraphBLAS в целом допускает значительную свободу реализации, некоторые функции и детали явно предписываются ею:

• Объекты GraphBLAS, включая матрицы и векторы, являются непрозрачными структурами данных.
• Неблокирующий режим исполнения, допускающий ленивое или асинхронное вычисление отдельных операций.
• Операция присваивания с маской: присваивает элементы матрицы только там, где элементы маски ненулевые.
• Реализации библиотек должны быть потокобезопасными.

Формально спецификация GraphBLAS описана для языка программирования C, однако ряд реализаций создан в духе GraphBLAS на других языках, включая C++, Java и CUDA от Nvidia.

В настоящее время существуют две полностью соответствующие спецификации эталонные реализации. Привязки, предполагающие совместимую реализацию, доступны для языков Python, MATLAB и Julia.

SuiteSparse:GraphBLAS — полная реализация стандарта GraphBLAS, разработанная Тимоти Дэвисом из Техасского университета A&M.^[6] Библиотека определяет набор операций с разреженными матрицами над расширенной алгеброй полуколец с практически неограниченным разнообразием операторов и типов данных.

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 — библиотека высококачественных алгоритмов на графах, построенных поверх GraphBLAS.^[7] Если 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 (стандарт для плотных матриц)
• Матрица смежности
• Разреженная матрица
• Алгоритмы на графах
• Полукольцо
• Поиск в ширину
• Параллельные вычисления

• Kepner J., Gilbert J. Graph Algorithms in the Language of Linear Algebra (англ.). — Philadelphia: SIAM, 2011. — ISBN 978-0-898719-90-1.
• Davis T. A. Algorithm 1000: SuiteSparse:GraphBLAS: graph algorithms in the language of sparse linear algebra (англ.) // ACM Transactions on Mathematical Software. — 2019. — Vol. 45, no. 4.
• Kepner J. и др. Graphs, Matrices, and the GraphBLAS: Seven Good Reasons (англ.) // Procedia Computer Science. — 2015. — Vol. 51. — P. 905—914.
• Kepner J. и др. Mathematical Foundations of the GraphBLAS (англ.) // IEEE High Performance Extreme Computing Conference (HPEC). — 2016.
• Brock B., Buluç A., Mattson T., McMillan S., Moreira J. GraphBLAS C API Specification, v2.1.0 (англ.) (2023). Дата обращения: 1 января 2024.

• Официальный сайт 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)  (англ.)

На эту статью не ссылаются другие статьи Википедии.

Это делает её менее доступной для читателей. Пожалуйста, установите ссылки, используя инструмент с подсказками для облегчения поиска. (4 мая 2026)