Dual-Number Associative Arrays for One-Pass Provenance and Sensitivity
Timothy Habashy, Hayden Jananthan, Jeremy Kepner
原文摘要
Associative arrays and GraphBLAS express sparse computations as matrix operations over a chosen semiring, but the result normally contains only the ordinary value. We define a dual-number extension $D_k(S)=S\ltimes S^k$ that carries this value together with $k$ independent auxiliary channels in the same computation. We prove that the construction is a split square-zero extension of any commutative semiring. Over min-plus, the auxiliary value is the weight of the shortest walk constrained to use the corresponding edge, excluding the weight of that edge. This gives an exact shortest-path membership test for that edge, although ties return the union of the edges on all optimal paths. We implement the min-plus construction using sparse \texttt{python-graphblas} operations, with a fixpoint test that checks the value and auxiliary components together. We validate the implementation across 18,692 checks, including 2,825 tied target pairs. On random graphs with 100,000 vertices and 32 seed edges, the dual method is $3.39\times$ faster than the sequential algorithm but $1.50\times$ slower than a min-plus-specific batched method. This difference is largely explained by the dual method requiring $1.55\times$ as many sweeps. Thus, the main contribution is a general algebraic approach with competitive sparse performance, rather than information that specialized min-plus algorithms cannot already compute.
cs.DS