Multiplication-Free Graph Spectral Embeddings: Bit-Sliced Repeated AX and A⊤ AX Products

Graph spectral embedding methods, such as spectral clustering and Laplacian Eigenmaps, are powerful techniques for uncovering the underlying structure of data by analyzing the eigenvectors of graph matrices. A core computational bottleneck in these methods is the repeated multiplication of a graph's adjacency or Laplacian matrix with a vector, as seen in iterative eigensolvers like the power method. This paper presents a multiplication-free approach to accelerate these critical operations. By representing the graph matrix with integer weights and employing a bit-slicing technique, the matrix-vector products are decomposed into a series of highly efficient Boolean matrix multiplications. This allows the computationally intensive steps to be executed with zero scalar multiplications, relying instead on fast bitwise operations. We demonstrate the method's validity by providing an executable Python implementation for the A_transposed A X product, a key kernel in many spectral methods.