SCFV+ algorithm computes forest matrix diagonals 10x faster on 20M+ node graphs

Computing the diagonal of a forest matrix is critical for network science and machine learning tasks like centrality analysis and graph kernels. Existing state-of-the-art algorithms rely on fast Laplacian solvers, which fail on directed graphs. In a new paper published at The Web Conference 2024, Haoxin Sun and Zhongzhi Zhang introduce three sampling-based algorithms: SCF, SCFV, and SCFV+. SCF extends Wilson’s algorithm to sample spanning converging forests, leveraging a probabilistic interpretation of the diagonal elements. To combat high variance in forest sampling, SCFV applies matrix-vector iteration inspired by opinion dynamics, reducing variance but leaving a potentially large cross-product term in its error bound.

SCFV+ eliminates that cross-product term entirely with a new iterative equation, achieving provably lower variance. The authors prove SCFV+ guarantees relative error with high probability while maintaining linear time complexity relative to node count – a theoretical improvement over all prior methods. Experiments on real-world networks (including massive graphs with over 20 million nodes) show SCF, SCFV, and SCFV+ deliver better estimation accuracy and faster runtime than Laplacian solver baselines, especially on directed graphs where previous techniques break down.