TY - JOUR AU - Fu, Zhenyong AU - Lu, Zhiwu AU - Ip, Horace AU - Peng, Yuxin AU - Lu, Hongtao PY - 2011/08/04 Y2 - 2024/03/29 TI - Symmetric Graph Regularized Constraint Propagation JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 25 IS - 1 SE - AAAI Technical Track: Machine Learning DO - 10.1609/aaai.v25i1.7897 UR - https://ojs.aaai.org/index.php/AAAI/article/view/7897 SP - 350-355 AB - <p> 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. </p> ER -