  Many scientific datasets are of high dimension, and the analysis usually
requires visual manipulation by retaining the most important structures of
data. Principal curve is a widely used approach for this purpose. However, many
existing methods work only for data with structures that are not
self-intersected, which is quite restrictive for real applications. A few
methods can overcome the above problem, but they either require complicated
human-made rules for a specific task with lack of convergence guarantee and
adaption flexibility to different tasks, or cannot obtain explicit structures
of data. To address these issues, we develop a new regularized principal graph
learning framework that captures the local information of the underlying graph
structure based on reversed graph embedding. As showcases, models that can
learn a spanning tree or a weighted undirected $\ell_1$ graph are proposed, and
a new learning algorithm is developed that learns a set of principal points and
a graph structure from data, simultaneously. The new algorithm is simple with
guaranteed convergence. We then extend the proposed framework to deal with
large-scale data. Experimental results on various synthetic and six real world
datasets show that the proposed method compares favorably with baselines and
can uncover the underlying structure correctly.
