  We consider the problem of learning a graph from a finite set of noisy graph
signal observations, the goal of which is to find a smooth representation of
the graph signal. Such a problem is motivated by the desire to infer relational
structure in large datasets and has been extensively studied in recent years.
Most existing approaches focus on learning a graph on which the observed
signals are smooth. However, the learned graph is prone to overfitting, as it
does not take the unobserved signals into account. To address this issue, we
propose a novel graph learning model based on the distributionally robust
optimization methodology, which aims to identify a graph that not only provides
a smooth representation of but is also robust against uncertainties in the
observed signals. On the statistics side, we establish out-of-sample
performance guarantees for our proposed model. On the optimization side, we
show that under a mild assumption on the graph signal distribution, our
proposed model admits a smooth non-convex optimization formulation. We then
develop a projected gradient method to tackle this formulation and establish
its convergence guarantees. Our formulation provides a new perspective on
regularization in the graph learning setting. Moreover, extensive numerical
experiments on both synthetic and real-world data show that our model has
comparable yet more robust performance across different populations of observed
signals than existing non-robust models according to various metrics.
