Graph Signal Filter used as dimensionality reduction in spectral clustering
usually requires expensive eigenvalue estimation. We analyze the filter in an
optimization setting and propose to use four orthogonalization-free methods by
optimizing objective functions as dimensionality reduction in spectral
clustering. The proposed methods do not utilize any orthogonalization, which is
known as not well scalable in a parallel computing environment. Our methods
theoretically construct adequate feature space, which is, at most, a weighted
alteration to the eigenspace of a normalized Laplacian matrix. We numerically
hypothesize that the proposed methods are equivalent in clustering quality to
the ideal Graph Signal Filter, which exploits the exact eigenvalue needed
without expensive eigenvalue estimation. Numerical results show that the
proposed methods outperform Power Iteration-based methods and Graph Signal
Filter in clustering quality and computation cost. Unlike Power Iteration-based
methods and Graph Signal Filter which require random signal input, our methods
are able to utilize available initialization in the streaming graph scenarios.
Additionally, numerical results show that our methods outperform ARPACK and are
faster than LOBPCG in the streaming graph scenarios. We also present numerical
results showing the scalability of our methods in multithreading and
multiprocessing implementations to facilitate parallel spectral clustering.

本文提出了四种无正交化方法来替代常用的成本较高的特征值计算，达到降维和聚类的目的，并在数值结果中表明，这些方法在聚类质量和计算成本方面优于传统方法。