Abstract
Parallel and energy-efficient searching of the shortest paths on a large graph is challenging. Conventional methods commonly used are sequential and computing intensive, rendering them inadequate for addressing large-scale and real-time situations. Here, we propose a highly parallel, computation- and energy-efficient approach to shortest path-based graph learning based on an emerging memristor spiking neural network via algorithm-device codesign. The shortest path is obtained parallelly in nature using simultaneous spike traveling instead of arithmetic calculation, achieving extremely low time and space complexity. A nonlinear weight mapping approach is proposed to counterbalance the neuron intrinsic nonlinearity to guarantee accuracy to support large-scale graphs. The memristor hardware capability is experimentally demonstrated in unsupervised and supervised classification tasks. The estimated energy efficiency of 517.82 giga-traversal edges per second per watt outperforms field programmable gate arrays by three to four orders of magnitude, providing a pathway toward highly energy-efficient graph computing hardware.