Fused Multiply-and-Prune SpGEMM for Bounded-Memory Iterative Graph Diffusion

• André Tomitan Bocces UNESP
• Alexandro Baldassin UNESP

DOI: https://doi.org/10.5753/eradsp.2026.30131

Resumo

Iterative sparse graph algorithms with a bounded-output constraint, requiring that only the top-L entries per output row be retained after each SpGEMM step, cannot be executed at scale by general-purpose sparse linear algebra libraries, which follow a model that materializes the full O(NK²) intermediate product before any row truncation, causing out-of-memory failure or OS thrashing even though the O(NL) final output fits in available memory. We present an engine, named Sparse-CSR, that prevents the intermediate product from ever being instantiated. Evaluated across three hardware tiers on graphs up to N=160,731 nodes, the engine achieves a 400× peak-memory reduction and up to 2.4× wall-clock speedup.

Palavras-chave: SpGEMM, Manifold Learning, High Performance Computing, Memory Optimization, Graph Algorithms, Compressed Sparse Row

Referências

Buluç, A. and Gilbert, J. R. (2012). Parallel sparse matrix–matrix multiplication and indexing: Implementation and experiments. SIAM J. Sci. Comput., 34(4):C170–C191.

Dalton, S., Olson, L. N., and Bell, N. (2015). Optimizing sparse matrix–matrix multiplication for the GPU. ACM Trans. Arch. Code Optim., 12(1):1–29.

Davis, T. A. (2019). Algorithm 1000: SuiteSparse:GraphBLAS: Graph algorithms in the language of sparse linear algebra. ACM Trans. Math. Softw., 45(4):1–25.

Geusebroek, J.-M., Burghouts, G. J., and Smeulders, A. W. M. (2005). The amsterdam library of object images. Int. J. Comput. Vis., 61:103–112.

Guennebaud, G., Jacob, B., et al. (2010). Eigen v3. [link].

Gustavson, F. G. (1978). Two fast algorithms for sparse matrices: Multiplication and permuted transposition. ACM Trans. Math. Softw., 4(3):250–269.

Hou, S., Feng, Y., and Wang, Z. (2017). VegFru: A domain-specific dataset for fine-grained visual categorization. In ICCV, pages 541–549.

Nagasaka, Y., Matsuoka, S., Suzuki, A., and Endo, T. (2019). High-performance sparse matrix–matrix products on Intel KNL and multicore architectures. In Proc. 48th ICPP, pages 1–10.

Pedronette, D. C. G. a., Valem, L. P., Almeida, J., and Torres, R. d. S. (2019). Multimedia retrieval through unsupervised hypergraph-based manifold ranking. IEEE Trans. Image Process., 28(12):5824–5838.

Valem, L. P. and Pedronette, D. C. G. a. (2017). Unsupervised distance learning by reciprocal kNN distance for image retrieval. ACM SIGMultimedia Records, 9(2):1–1.

Xiao, J., Hays, J., Ehinger, K. A., Oliva, A., and Torralba, A. (2010). SUN database: Large-scale scene recognition from abbey to zoo. In CVPR, pages 3485–3492. IEEE.