Nonlinear spectral clustering with C++ GraphBLAS

Dimosthenis Pasadakis & Olaf Schenk & Verner Vlacic & Albert-Jan Yzelman · 2026

Read Nonlinear spectral clustering with C++ GraphBLAS by Dimosthenis Pasadakis & Olaf Schenk & Verner Vlacic & Albert-Jan Yzelman (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-26975.txt.

Introduction

Pasadakis and three co-authors build nonlinear multi-way spectral clustering in the p-norm using a new C++ GraphBLAS interface. Estimating several nonlinear eigenvectors is costly, but their direct algorithm puts key steps in linear algebra over sparse matrices and dense vectors. Tests on toy cases show high-quality clusters by the balanced cut metric, and strong scaling holds up to 8 million nodes and 48 million edges.

Catalog record

CREATORDimosthenis Pasadakis & Olaf Schenk & Verner Vlacic & Albert-Jan Yzelman
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE10098
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.26975

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Nonlinear spectral clustering with C++ GraphBLAS Dimosthenis Pasadakis & Olaf Schenk & Verner Vlacic & Albert-Jan Yzelman Abstract Nonlinear reformulations of the spectral clustering method have gained a lot of recent attention due to their increased numerical benefits and their solid mathematical background. However, the estimation of the multiple nonlinear eigenvectors is associated with an increased computational cost. We present an implementation of a direct multiway spectral clustering algorithm in the p p -norm, for p ∈ ( 1 , 2 ] p\in(1,2] , using a novel C++ GraphBLAS API. The key operations are expressed in linear algebraic terms and are executed over the resulting sparse matrices and dense vectors, parameterized in the algebra pertinent to the computation. We demonstrate the effectiveness and accuracy of our shared-memory algorithm on several artificial test cases. Our numerical examples and comparative results against competitive methods indicate that the proposed implementation attains high quality clusters in terms of the balanced graph cut metric. The strong scaling capabilities of our algorithm are showcased on a range of datasets with up to 8 8 million nodes and 48 48 million edges. I Introduction Spectral clustering is a popular community detection method that can be applied to any kind of data with a suitable similarity metric between them forming a graphical structure. At its core lies the computation of the mutually orthogonal eigenvectors of the graph Laplacian, a symmetric and positive semi-definite matrix, which are treated as the spectral coordinates of the graph, and are subsequently discretized using distance based algorithms [ 1 ] . This eigenspectrum computation offers ample room for parallelization, with both shared and distributed memory implementations widely used [ 2 ] . Nonlinear variants of the method in the p -norm, for p\in(1,2] , that have been proposed lead to a minimization of balanced graph cut metrics, and an increase in the accuracy of the final clustering assignment [ 3 ] . Recently in [ 4 ] , p -spectral clustering was cast as a nonlinear unconstrained optimization problem on the Grassmann manifold [ 5 ] , by approximating the constraint for p -orthogonality with an analogous one for 2 -orthogonality. This approach is not applicable to large-scale data, due to the large number of multiplications of the graph adjacency matrix with the computed eigenvectors that are required for convergence, especially as the value of p tends to 1. GraphBLAS is a standard [ 6 ] for expressing graph computations in the language of linear algebra. Its core concepts are (i) algebraic containers, which correspond to sparse matrices and vectors, (ii) algebraic operators, describing sparse matrix-vector (SpMV) multiplications, and (iii) algebraic relations, an example of which is a generalized semiring under which an SpMV multiplication takes place. The recently introduced C++11 implementation of GraphBLAS [ 7 ] has showcased impressive results on the speed-up of algorithms based on SpMVs [ 8 ] . We express the key operations of the method introduced in [ 4 ] as well as the k-means discretization of the resulting eigenvectors in this C++ GraphBLAS API. This allows us to leverage its auto-parallelisation capabilities, and furnish the first, according to our best knowledge, p -norm spectral clustering algorithm applicable to large-scale data for shared-memory machines. II A C++ GraphBLAS p -spectral clustering algorithm For an undirected weighted graph \mathcal{G}(V,E,\boldsymbol{\mathbb{W}}) where V is the set of n nodes, E the set of edges, and \boldsymbol{\mathbb{W}} the weighted adjacency matrix, estimating a set of k p -eigenvectors on the Grassmann manifold \mathcal{Gr} can be expressed as {\displaystyle\mathop{\hbox{\rm minimize}}_{\boldsymbol{\mathbb{U}}\in\mathcal{Gr}(k,n)}}\;F_{p}(\boldsymbol{\mathbb{U}})=\sum_{\ell=1}^{k}\sum_{i,j=1}^{n}\frac{w_{ij}|u_{i}^{\ell}-u_{j}^{\ell}|^{p}}{2\|\boldsymbol{\mathbb{u}}^{\ell}\|^{p}_{p}},\;\;p\in(1,2]. (1) Let \ell=1,2,\dots,k denote the eigenvector indices, and, at the minimizer, the columns of \mathbf{U}=\left(\mathbf{u}_{1},\dots,\mathbf{u}_{k}\right) approximate the eigenvectors associated with the smallest k eigenvalues of the p -Laplacian operator \boldsymbol{\mathbb{\Delta}}_{p} . For i\in V the p -Laplacian operator is defined as \left(\boldsymbol{\mathbb{\Delta}}_{p}\mathbf{u}\right)_{i}=\sum_{j\in V}w_{ij}\phi_{p}\left(u_{i}-u_{j}\right), with \phi_{p}:\mathbb{R}\rightarrow\mathbb{R} being \phi_{p}(x)=|x|^{p-1}\text{sign}(x), and the p -norm is \|\boldsymbol{\mathbb{u}}\|_{p}=\sqrt[p]{\sum_{i=1}^{n}|u_{i}|^{p}} , for u\in\mathbb{R} . We use the Riemannian optimization software package ROPTLIB [ 9 ] to minimize ( 1 ) for progressively smaller values of p using Newton’s method on the Grassmann manifold, where the solution of the linearized Newton subproblems is handled by a truncated conjugate gradient scheme. The description of the optimization problem is accomplished in ROPTLIB by specifying the function EucGrad which computes the gradient of F_{p}(\boldsymbol{\mathbb{U}}) as well as the function EucHessianEta which computes \boldsymbol{\mathbb{\eta}}\mapsto{\mathcal{H}}\boldsymbol{\mathbb{\eta}}=(\mathcal{H}^{\ell}\eta^{\ell})_{\ell=1}^{k} for arbitrary \boldsymbol{\mathbb{\eta}}\in\mathbb{R}^{k\times n} , where the collection of matrices \mathcal{H}^{1},\dots,\mathcal{H}^{k}\in\mathbb{R}^{n\times n} corresponds to the Hessian of F_{p}(\boldsymbol{\mathbb{U}}) . For illustration, we include our C++ GraphBLAS implementation of EucHessianEta in Algorithm 1 . Here the subroutines ROPTLIBtoGRB and GRBtoROPTLIB serve for I/O from and to the ROPTLIB data structures. The C++ GraphBLAS API leverages the algebraic structure of the ring of real numbers to parallelize the SpMV operation (the grb::vxm primitive). Input: \boldsymbol{\mathbb{\eta}} , a k\times n matrix (D[\ell])_{\ell=1}^{k} , where each D[\ell]=\mathrm{diag}(\mathcal{H}^{\ell}) (H[\ell])_{\ell=1}^{k} , where each H[\ell]=\mathrm{diag}(\mathcal{H}^{\ell})-\mathcal{H}^{\ell} Output: \boldsymbol{\mathbb{r}} , the result of \boldsymbol{\mathbb{\eta}}\mapsto{\mathcal{H}}\boldsymbol{\mathbb{\eta}} 1: grb::Semiring < grb::operators::add < double > , grb::operators::mul < double > , grb::identities::zero, grb::identities::one > reals_ring; 2: std::vector < grb::Vector < double >> grb_eta, grb_res; 3: grb::Vector < double > v, w; 4: ROPTLIBtoGRB( \boldsymbol{\mathbb{\eta}} , grb_eta); 5: for \ell=1 to k do 6: grb::set(v, 0); 7: grb::vxm(v, grb_eta[ \ell ], H[ \ell ], reals_ring); 8: grb::eWiseApply(w, grb_eta[ \ell ]),D[ \ell ], grb::operators::mul < double > ()); 9: grb::eWiseApply(grb_res[ \ell ], w, v, grb::operators::subtract < double > ()); 10: GRBtoROPTLIB(grb_res, \boldsymbol{\mathbb{r}} ); 11: return \boldsymbol{\mathbb{r}} Algorithm 1 The function EucHessianEta . III Numerical Results In order to demonstrate the effectiveness of the C++ GraphBLAS API for implementing the p -spectral clustering method, in Section III-A we report on the quality of the graph cuts obtained, and in Section III-B we present its parallel performance. For our experiments we select 8 matrices from the SuiteSparse matrix collection [ 10 ] with an increasing number of nodes n=2^{r} and edges m\approx 6*2^{r} , for r=16,\dots,23 , corresponding to Delaunay triangulations in a unit square. III-A Quality of graph cuts We identify four clusters C_{i} , i=1,2,3,4 , and compute the value of the balanced graph cut metric \mathrm{RCut}(C_{1},C_{2},C_{3},C_{4})=\sum_{i=1}^{4}\frac{\mathrm{cut}(C_{i},\overline{C_{i}})}{|C_{i}|} . The results for the mid-scale cases with r=\{16,17,18,19\} are summarized in Table I . We compare our method (GrB- p Grass) against traditional spectral clustering (Spec) [ 1 ] and against the first full eigenvector analysis of p -Laplacian leading to direct multiway clustering ( p Multi) [ 3 ] . Method Del. 16 Del. 17 Del. 18 Del. 19 Spec 0.129 0.089 0.062 0.045 p Multi -6.21\% -3.11\% -2.21\% -2.45\% GrB- p Grass \boldsymbol{\mathbb{-8.12}}\% \boldsymbol{\mathbb{-6.43}}\% \boldsymbol{\mathbb{-4.56}}\% \boldsymbol{\mathbb{-4.19}}\% TABLE I : Results in terms of the balanced graph cut metric RCut. We report the baseline (Spec) RCut, and in percentage the reduction of the cut that the methods pMulti and GrB- p Grass (ours) achieved. III-B Parallel performance The strong scaling results of the developed algorithm are illustrated in Figure 1 . In both plots, the dashed red line indicates the ideal scalability. We utilize up to 32 threads for the mid-scale cases (Figure 1(a) ), and up to 88 threads for the large-scale Delaunay graphs with r=\{20,21,22,23\} (Figure 1(b) ). On average, the parallel execution of the algorithm is 5.5\times faster than its sequential variant for

Read the complete text