TL;DR
This paper introduces a novel High-Order Co-Clustering (HOCC) method that uses a strictly orthogonal and symmetric $l_1$-norm Nonnegative Matrix Tri-Factorization (NMTF) approach. This method is designed to be more robust to outliers and achieve better clustering results than previous methods by enforcing strict orthogonality and using $l_1$-norm for outlier resistance.
What Problem Does This Paper Address?
Traditional clustering methods often focus on a single data type. High-Order Co-Clustering (HOCC) aims to address this by simultaneously clustering multiple related data types (e.g., user preferences, movie ratings, and social connections). Existing HOCC methods often rely on squared residual errors, making them susceptible to outliers that can skew clustering results. Furthermore, many methods suffer from "soft clustering," where cluster assignments are not distinct, and can get trapped in suboptimal solutions due to the limitations of traditional optimization algorithms like Multiplicative Updating Algorithm (MUA). This paper tackles these issues by proposing a more robust and accurate HOCC method.
Methods
The core of this paper is the development of a novel optimization objective for HOCC: a strictly orthogonal and symmetric $l_1$-norm Nonnegative Matrix Tri-Factorization (NMTF).
- $l_1$-Norm for Robustness: Instead of the traditional squared Frobenius norm (which is sensitive to outliers), the paper uses the $l_1$-norm. This makes the objective function more resilient to noisy data and extreme values.
- Symmetric NMTF: The formulation involves a symmetric NMTF, which is a generalization of co-clustering to multiple data types.
- Strict Orthogonality Constraint: A key innovation is the strict enforcement of orthogonal constraints on the membership matrices ($G$). This is crucial for obtaining unique solutions and avoiding soft clustering, leading to more distinct cluster assignments.
- Alternating Direction Method of Multipliers (ADMM): Due to the non-differentiable nature of the $l_1$-norm and the complexity of the orthogonal constraints, traditional optimization methods like MUA are not suitable. The authors propose using the ADMM algorithm, which is well-suited for solving such convex optimization problems by breaking them into smaller, manageable subproblems. This allows for rigorous mathematical derivation and guarantees convergence.
- Graph Regularization (Optional): The paper also extends the method to incorporate intra-type information using graph regularization, further improving clustering by leveraging relationships within each data type.
Datasets
The authors created a new multi-relational dataset from the ACL-IMDB dataset. This dataset consists of movie reviews and is used to construct three relational matrices:
- Comment-word matrix: Represents the relationship between comments and words.
- User-comment matrix: Captures the relationship between users and their comments.
- User-word matrix: Derived from the other two matrices.
Noise was intentionally added to these matrices to simulate real-world data imperfections and test the robustness of the proposed method.
Key Insights and Ideas
- $l_1$-norm is crucial for outlier resistance in HOCC: The paper demonstrates that moving from $l_2$ (squared error) to $l_1$-norm significantly improves robustness in the presence of noisy data, a common issue in large datasets.
- Strict orthogonality is key to distinct clusters: Enforcing strict orthogonality on the membership matrix ($G$) is shown to be vital for avoiding soft clustering and achieving more interpretable and well-separated clusters.
- ADMM is a powerful tool for complex NMTF problems: The paper highlights ADMM's effectiveness in handling the non-differentiability of $l_1$-norm and the complex orthogonal constraints, offering a more rigorous solution than traditional MUA-based methods.
- HOCC with multiple relational data types can outperform single-type clustering: The experimental results suggest that leveraging inter-type relationships (and optionally intra-type relationships) leads to better clustering performance.
Key Results
- Improved Clustering Accuracy: The proposed $l_1$-norm ADMM method consistently achieved higher clustering accuracies and Normalized Mutual Information (NMI) compared to traditional methods like K-means, ONMTF, GNMF, and MUA-based NMTF variants, especially when noise was present.
- Lower Local Minima: The method was able to find lower local minima in the objective function compared to MUA-based methods, indicating a better overall solution.
- Faster Convergence: The ADMM-based approach was observed to be faster per iteration than MUA-based methods, often taking only 1/3 to 1/2 the time.
- Strictly Orthogonal Membership Matrix: The method successfully produced strictly orthogonal membership matrices ($G$), as visualized in the heatmap comparisons, unlike MUA-based methods which often resulted in soft clustering.
- Robustness to Regularization Parameter: The $l_1$-norm objective function demonstrated robustness to changes in the regularization parameter ($\lambda$), maintaining higher accuracy than $l_2$-norm counterparts.
Limitations and Future Work
- Computational Cost: While faster per iteration than MUA, ADMM can still be computationally intensive for very large datasets. The paper mentions that some derivation details are omitted due to space limitations and will be provided in an extended journal version, suggesting potential for further optimization.
- Two-Type Relational Data Results: The paper notes that experimental results on two-type relational data were omitted due to space constraints but will be included in the extended journal version.
- Generalizability: While the paper demonstrates effectiveness on a specific multi-relational dataset, further validation on a wider range of real-world multi-type datasets would strengthen the claims.
- Future Work: The authors suggest that their ADMM-based framework is flexible and could be extended to solve other non-smooth, non-convex optimization problems, indicating a promising direction for future research.
Summary updated