  A graph convolutional network (GCN) employs a graph filtering kernel tailored
for data with irregular structures. However, simply stacking more GCN layers
does not improve performance; instead, the output converges to an uninformative
low-dimensional subspace, where the convergence rate is characterized by the
graph spectrum -- this is the known over-smoothing problem in GCN. In this
paper, we propose a sparse graph learning algorithm incorporating a new
spectrum prior to compute a graph topology that circumvents over-smoothing
while preserving pairwise correlations inherent in data. Specifically, based on
a spectral analysis of multilayer GCN output, we derive a spectrum prior for
the graph Laplacian matrix $\mathbf{L}$ to robustify the model expressiveness
against over-smoothing. Then, we formulate a sparse graph learning problem with
the spectrum prior, solved efficiently via block coordinate descent (BCD).
Moreover, we optimize the weight parameter trading off the fidelity term with
the spectrum prior, based on data smoothness on the original graph learned
without spectrum manipulation. The output $\mathbf{L}$ is then normalized for
supervised GCN training. Experiments show that our proposal produced deeper
GCNs and higher prediction accuracy for regression and classification tasks
compared to competing schemes.
