  Dimensionality reduction is a crucial first step for many unsupervised
learning tasks including anomaly detection and clustering. Autoencoder is a
popular mechanism to accomplish dimensionality reduction. In order to make
dimensionality reduction effective for high-dimensional data embedding
nonlinear low-dimensional manifold, it is understood that some sort of geodesic
distance metric should be used to discriminate the data samples. Inspired by
the success of geodesic distance approximators such as ISOMAP, we propose to
use a minimum spanning tree (MST), a graph-based algorithm, to approximate the
local neighborhood structure and generate structure-preserving distances among
data points. We use this MST-based distance metric to replace the Euclidean
distance metric in the embedding function of autoencoders and develop a new
graph regularized autoencoder, which outperforms a wide range of alternative
methods over 20 benchmark anomaly detection datasets. We further incorporate
the MST regularizer into two generative adversarial networks and find that
using the MST regularizer improves the performance of anomaly detection
substantially for both generative adversarial networks. We also test our MST
regularized autoencoder on two datasets in a clustering application and witness
its superior performance as well.
