Symmetric Graph Regularized Constraint Propagation

Authors

  • Zhenyong Fu City University of Hong Kong
  • Zhiwu Lu Peking University
  • Horace Ip City University of Hong Kong
  • Yuxin Peng Peking University
  • Hongtao Lu Shanghai Jiao Tong University

Abstract

This paper presents a novel symmetric graph regularization framework for pairwise constraint propagation. We first decompose the challenging problem of pairwise constraint propagation into a series of two-class label propagation subproblems and then deal with these subproblems by quadratic optimization with symmetric graph regularization. More importantly, we clearly show that pairwise constraint propagation is actually equivalent to solving a Lyapunov matrix equation, which is widely used in Control Theory as a standard continuous-time equation. Different from most previous constraint propagation methods that suffer from severe limitations, our method can directly be applied to multi-class problem and also can effectively exploit both must-link and cannot-link constraints. The propagated constraints are further used to adjust the similarity between data points so that they can be incorporated into subsequent clustering. The proposed method has been tested in clustering tasks on six real-life data sets and then shown to achieve significant improvements with respect to the state of the arts.

Downloads

Published

2011-08-04

How to Cite

Fu, Z., Lu, Z., Ip, H., Peng, Y., & Lu, H. (2011). Symmetric Graph Regularized Constraint Propagation. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1), 350-355. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/7897

Issue

Section

AAAI Technical Track: Machine Learning