  The theory of sampling and recovery of bandlimited graph signals has been
extensively studied. However, in many cases, the observation of a signal is
quite coarse. For example, users only provide simple comments such as "like" or
"dislike" for a product on an e-commerce platform. This is a particular
scenario where only the sign information of a graph signal can be measured. In
this paper, we are interested in how to sample based on sign information in an
online manner, by which the direction of the original graph signal can be
estimated. The online signed sampling problem of a graph signal can be
formulated as a Markov decision process in a finite horizon. Unfortunately, it
is intractable for large size graphs. We propose a low-complexity greedy signed
sampling algorithm (GSS) as well as a stopping criterion. Meanwhile, we prove
that the objective function is adaptive monotonic and adaptive submodular, so
that the performance is close enough to the global optimum with a lower bound.
Finally, we demonstrate the effectiveness of the GSS algorithm by both
synthesis and realworld data.
