Symmetric Graph Regularized Constraint Propagation


  • 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


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.




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



AAAI Technical Track: Machine Learning