Fast Algorithms for the Label Propagation Operator on Signed Graphs

Diverse applications on signed networks, ranging from leader-follower opinion dynamics to graph semi-supervised learning, fundamentally reduce to solving the discrete Dirichlet boundary value problem. The computational bottleneck of this problem lies in evaluating the entries of the label propagation operator $Q = -L_{U,U}^{-1}L_{U,L}$. While existing approximation methods based on absorbing random walks attempt to address this complexity, they often suffer from high variance and limited precision. To overcome these limitations, we propose MultiTreeQ, a novel and efficient framework designed to approximate the operator's entries with high accuracy. Specifically, MultiTreeQ is constructed based on the Signed Multi-Rooted Spanning Tree and leverages Rao-Blackwellized variance reduction to significantly improve estimation precision. Extensive experiments on real-world networks confirm that MultiTreeQ substantially outperforms existing baselines, scaling to massive graphs with up to 10 million nodes while delivering remarkable improvements in computational efficiency and precision. Our code is available at https://anonymous.4open.science/r/label-propagation-operator-2059/.