Time-Optimal APSP and Matrix Multiplication in Classes of Linear Neighborhood Complexity

What the math gives to ML

The paper identifies linear neighborhood complexity (LNC) as a structural condition under which an apparently dense graph operator admits an exact linear-time matrix-vector query after quadratic preprocessing. The transferable asset is not merely sparse graph processing: it is a data structure for repeatedly applying a fixed, potentially dense adjacency operator to arbitrary feature vectors in time proportional to the number of vertices. This can turn dense message passing on structured graphs into an exact O(nd) operation per layer, provided the graph is fixed and belongs to an LNC class. The most direct experiment is to replace dense adjacency aggregation in graph neural networks with the paper's preprocessed operator and measure amortized layer throughput and memory at identical outputs.