  Given a graph G, a budget k and a misinformation seed set S, Influence
Minimization (IMIN) via node blocking aims to find a set of k nodes to be
blocked such that the expected spread of S is minimized. This problem finds
important applications in suppressing the spread of misinformation and has been
extensively studied in the literature. However, existing solutions for IMIN
still incur significant computation overhead, especially when k becomes large.
In addition, there is still no approximation solution with non-trivial
theoretical guarantee for IMIN via node blocking prior to our work. In this
paper, we conduct the first attempt to propose algorithms that yield
data-dependent approximation guarantees. Based on the Sandwich framework, we
first develop submodular and monotonic lower and upper bounds for our
non-submodular objective function and prove the computation of proposed bounds
is \#P-hard. In addition, two advanced sampling methods are proposed to
estimate the value of bounding functions. Moreover, we develop two novel
martingale-based concentration bounds to reduce the sample complexity and
design two non-trivial algorithms that provide (1-1/e-\epsilon)-approximate
solutions to our bounding functions. Comprehensive experiments on 9 real-world
datasets are conducted to validate the efficiency and effectiveness of the
proposed techniques. Compared with the state-of-the-art methods, our solutions
can achieve up to two orders of magnitude speedup and provide theoretical
guarantees for the quality of returned results.
