  Graph sampling theory extends the traditional sampling theory to graphs with
topological structures. As a key part of the graph sampling theory, subset
selection chooses nodes on graphs as samples to reconstruct the original
signal. Due to the eigen-decomposition operation for Laplacian matrices of
graphs, however, existing subset selection methods usually require
high-complexity calculations. In this paper, with an aim of enhancing the
computational efficiency of subset selection on graphs, we propose a novel
objective function based on the optimal experimental design. Theoretical
analysis shows that this function enjoys an $\alpha$-supermodular property with
a provable lower bound on $\alpha$. The objective function, together with an
approximate of the low-pass filter on graphs, suggests a fast subset selection
method that does not require any eigen-decomposition operation. Experimental
results show that the proposed method exhibits high computational efficiency,
while having competitive results compared to the state-of-the-art ones,
especially when the sampling rate is low.
