Papers for

graph analytics engineers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

AscSpMM speeds up sparse matrix math on Ascend neural processors

AscSpMM: Efficient SpMM on Ascend NPUs via Pipelined Vector-Cube Collaboration

Abstract: Neural processing units (NPUs) provide high compute density and energy efficiency through specialized matrix engines and software-managed on-chip memory. However, their libraries primarily target dense computation. Sparse matrix-dense matrix multiplication (SpMM), a key kernel in graph analytics, sparse neural networks, and scientific computing, requires index-driven operand selection, indirect addressing, scattered memory accesses, and load balancing. These requirements conflict with the fixed shapes and contiguous layouts preferred by NPU matrix engines. GPU Tensor Core SpMM methods cannot be directly transferred to NPUs with decoupled vector and matrix engines. We present AscSpMM, which separates irregular operand preparation from regular matrix computation through a parameterized Vector-CSR representation. The vector engine decodes indices and gathers and reorganizes dense operands, while the Cube engine performs matrix multiply-accumulate operations. A double-slot ring buffer enables dependency-aware asynchronous pipelining, while operand reuse and runtime-adaptive tiling reduce cross-engine stalls. On an Ascend 910B3, AscSpMM achieves geometric-mean speedups of 2.36x over GEMM, 19.92x over an existing SpMM implementation, and 5.82x over cuSPARSE on an A100. It reduces matrix-input storage and peak HBM footprint by 48.24% and 22.98% on average, while remaining competitive with specialized GPU Tensor Core SpMM kernels. The code is available at https://github.com/LfLab-AI/Ascend-NPU-SpMM.

Mon 9 NovHardware Architecture
The gist
Multiplying sparse and dense matrices is important for many computing tasks but is hard to do fast on specialized neural chips because of how they handle data. The authors designed AscSpMM, a method that splits the work between two types of processors inside the chip, letting them handle irregular and regular parts separately. This speeds up computation a lot, reduces memory use, and is faster than existing methods on both Ascend and GPU hardware. It also uses smart buffering and tiling strategies to keep both processors busy.
Open → 2611.11823v1

Optimal embeddings improve graph cuts and expansion approximations

Optimal Average Distortion for Non-Expansive Embeddings of Euclidean Metrics into the Line: With applications to cut-matching games and vertex expansion

Abstract: We show that any $n$-point Euclidean metric admits a non-expansive embedding into the line with average distortion at most $O\left(\sqrt{\frac{\log n}{\log\log n}}\right)$, matching a known lower bound. We also present two applications of this result. First, we give a cut-player strategy with an optimal spectral guarantee for the undirected cut-matching game. Second, we give an improved spectral approximation for vertex expansion in high-degree graphs.

Fri 30 OctData Structures and AlgorithmsComputational Geometry
The gist
The paper deals with a way to represent distances between points in a space using just a line, without stretching the distances too much on average. The authors find the best possible way to do this for points in ordinary Euclidean space, matching what was previously known as a minimum limit. They then show how this finding helps create better strategies to split networks into parts efficiently and to estimate how connected nodes are in complex graphs.
Open → 2610.41945v1

Adaptive scheduling improves performance of sparse matrix multiplication

Taming Multi-Dimensional Skew in Sparse Matrix Multiplication with Contention-Aware Scheduling [Technical Report]

Abstract: Sparse general matrix-matrix multiplication (SpGEMM) is a key kernel in graph analytics, relational queries, and machine learning. Yet, its performance remains a significant challenge, due to the inherent sparsity and, more critically, the prevalent skew patterns often found in real-world workloads. This paper investigates this problem and demonstrates that an unbalanced workload distribution is the main culprit, harming performance through two co-existing root causes: first, multi-dimensional skew, where imbalance across computation cost, output density, and data locality cannot be captured by any single balancing metric; and second, cache contention, where dense substructures induce severe on-chip interference. To that end, we propose adaptive morsel scheduling (AMS), a dynamic scheduling framework that decouples skew dimensions via fixed-result-size morsels and integrates contention-aware load balancing (CALB) and data-conscious simultaneous multithreading activator (SMTact) to alleviate cache-level contention, alongside a hybrid accumulation mechanism (HYB) that adaptively selects the best accumulator per morsel. Evaluations across matrix squaring, relational queries, graph analytics, and other sparse matrix kernels show that AMS significantly outperforms state-of-the-art methods on skewed workloads while maintaining comparable performance on non-skewed ones. These gains, along with improved bandwidth utilization, remain valid across a wide range of workloads and hardware systems.

Tue 27 OctDistributed, Parallel, and Cluster ComputingDatabases
The gist
Sparse matrix multiplication is important for many technologies like graph analysis and machine learning but can run slowly because the work isn't evenly spread out. The authors found that the problem comes from uneven workload distribution and interference in the computer’s memory cache. They created a new method called adaptive morsel scheduling (AMS) that splits work carefully and manages memory better. This approach runs faster than current methods on tricky, unbalanced tasks and works well on regular ones too.
Open → 2610.36822v1

Quantum local algorithms exceed classical ones on max k cut graphs

Provable Classical and Quantum Local Algorithms for Max-$k$-Cut and Quantum Advantage at Moderate Girth

Abstract: Broadening the study of quantum optimization algorithms from binary to $k$-element alphabets has been shown to open new avenues for potential quantum advantage. A quantum advantage claim for approximate optimization requires showing that, under the same assumptions, an efficient quantum algorithm provably achieves a better performance than can be proven for the best known efficient classical algorithms. We study local classical and quantum algorithms for Max-$k$-Cut on $d$-regular graphs of girth $g$. We advance classical algorithms for this problem by developing a local vector algorithm based on the explicit vector construction of Thompson, Parekh, and Marwaha (TPM). Our algorithm gives the best provable cut fraction guarantee among known efficient classical algorithms on regular graphs for $k\geq3$. To evaluate the performance of QAOA under identical assumptions of girth and regularity, we develop tensor network techniques for general $d$ and $k \geq 2$. In addition, using an equivalence to a coupled qudit--boson system, we compute the QAOA performance in the infinite-degree limit. Together, these techniques give provable guarantees on QAOA performance on large graphs. Despite the improvements we introduce to the classical algorithm, QAOA achieves a better cut fraction guarantee for depths $p\geq 9$, corresponding to girth $g\geq 20$, for both finite- and infinite-degree regimes. Thus, we obtain an apparent quantum advantage from applying QAOA to the Max-$k$-Cut problem.

Wed 30 SeptData Structures and Algorithms
The gist
Max-k-Cut is a way to split a network into groups to maximize the number of connections between different groups. The authors studied classical and quantum algorithms that work locally on certain structured networks and found that a quantum approach called QAOA can do better than the best classical local methods when the network is large and has certain properties. They improved classical methods too, but beyond a certain point, the quantum algorithm still outperforms them. This suggests that quantum computing can have advantages on specific graph problems under realistic assumptions.
Open → 2609.39042v1