Learning Strictly Orthogonal p-Order Nonnegative Laplacian Embedding via Smoothed Iterative Reweighted Method

Haoxuan Yang, Kai Liu, Hua Wang, Feiping NieIJCAI 2019 · DOI

TL;DR

This paper introduces a novel method for Laplacian Embedding (LE) that enforces both strict orthogonality and nonnegativity constraints, crucial for stable and interpretable clustering. They propose a "Smoothed Iterative Reweighted Method" to efficiently solve this challenging optimization problem, demonstrating superior performance and robustness on various datasets.

What Problem Does This Paper Address?

High-dimensional data is notoriously difficult to analyze and visualize. Laplacian Embedding (LE) is a powerful technique to uncover the intrinsic geometry of such data by representing relationships as a graph. However, standard LE can produce solutions that are hard to interpret (e.g., mixed positive and negative values) and can be sensitive to outliers.

To address this, Nonnegative Laplacian Embedding (NLE) was developed, enforcing nonnegativity for easier interpretation. However, NLE often sacrifices orthogonality, which is vital for preventing degenerate solutions (where data points collapse) and ensuring good clustering performance. Furthermore, traditional LE methods often use the squared L2-norm distance, which is known to be sensitive to outliers. This paper tackles the challenge of simultaneously achieving strict orthogonality, nonnegativity, and robustness against outliers by using a generalized p-order L2-norm distance in the LE objective. This combination leads to a nonsmooth and nonconvex optimization problem that is difficult to solve.

Methods

The core contribution is a new optimization framework for "Strictly Orthogonal p-Order Nonnegative Laplacian Embedding" (PO-NLE). The key methodological innovations are:

  • Generalized p-Order L2-Norm Distance: Instead of the standard squared L2-norm, the paper uses the p-th order of the L2-norm distance (0 < p < 2). This is motivated by recent work showing that using non-squared norms can improve robustness to outliers. When p < 1, the objective focuses more on minimizing the majority of local data pair distances.
  • Smoothed Iterative Reweighted Method: To handle the nonsmoothness introduced by the p-th order norm and the nonconvexity of the problem, the authors propose a novel iterative algorithm. This method explicitly adds a small "smoothness term" (δI) to the objective, which improves numerical stability and allows for theoretical convergence proofs. This is a key theoretical contribution, as previous methods often lacked formal analysis of such terms.
  • Alternating Direction Method of Multipliers (ADMM): For a specific subproblem within the iterative framework (related to the orthogonal constraint), the paper leverages ADMM to ensure the orthogonality constraint is strictly met.

Datasets

The paper evaluates their method on a variety of datasets:

  • Synthetic Data Set: Used to illustrate the algorithm's convergence and the gradual separation of clusters.
  • UCI Machine Learning Data Repository: Four datasets are used: Wine, Iris, Glass, and Ionosphere.
  • Image Datasets: Three datasets are mentioned: MNIST, AT&T, and Caltech101.

No new benchmark datasets were introduced.

Key Insights and Ideas

  • Orthogonality is Crucial for Robustness: The paper strongly emphasizes that strict orthogonality is not just about preventing degenerate solutions but is critical for achieving good clustering performance and robustness, especially compared to methods like NLE that relax this constraint.
  • p-Order Norms for Robustness: Using a p-th order L2-norm (especially with p < 2) is shown to be effective in making the embedding less sensitive to outliers, a common problem in real-world data.
  • Smoothness Term for Stability: The explicit introduction of a smoothness term (δI) in their iterative reweighted method is a significant theoretical contribution, enabling rigorous convergence proofs and improving numerical stability, which was a weakness in prior related methods.
  • Direct Clustering from Embeddings: The nonnegativity constraint allows for direct interpretation of the embedding as cluster membership probabilities, eliminating the need for a separate post-processing clustering step (like K-means) which can be unstable.

Key Results

  • Superior Clustering Performance: The proposed PO-NLE method consistently outperforms NLE, Normalized Cut (NCut), and standard Laplacian Embedding (LE) in terms of clustering accuracy and purity across multiple datasets, especially on noisy data.
  • Guaranteed Orthogonality: Empirical results (visualized by XTX heatmaps) clearly show that their method achieves strictly orthogonal embeddings, unlike NLE which often fails to do so.
  • Robustness to Noise: The method demonstrates significantly better performance degradation on noisy datasets compared to its counterparts.
  • Convergence: The proposed smoothed iterative reweighted method is theoretically proven to converge, and empirical results (objective function plots) confirm this.

Limitations and Future Work

  • Parameter Tuning: While the paper highlights the benefit of p < 2, the optimal value of 'p' might still require tuning for different datasets. The paper mentions that "the optimal solution is usually obtained when p is less than 2 and close to 1 (it depends on data sets)".
  • Computational Complexity: While the method is efficient, the paper mentions that the detailed procedures for solving the ADMM optimization problem will be supplied in an extended journal version, suggesting that the full computational analysis might be elaborated further.
  • Future Work: The authors suggest that their smoothed iterative reweighted method can be broadly applied to other machine learning problems that involve minimizing objectives with p-th order L2-norms, lp-norms, or Schatten p-norms.

Summary updated

BibTeX
@inproceedings{yang2019learning,
  author = {Haoxuan Yang and Kai Liu and Hua Wang and Feiping Nie},
  title = {{Learning Strictly Orthogonal p-Order Nonnegative Laplacian Embedding via Smoothed Iterative Reweighted Method}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/561},
}

Loading related content...

Figure