A Convex-Concave Relaxation Procedure Based Subgraph Matching Algorithm

Zhi-Yong Liu, Hong Qiao
Proceedings of the Asian Conference on Machine Learning, PMLR 25:237-252, 2012.

Abstract

Based on the convex-concave relaxation procedure (CCRP), the (extended) path following algorithms were recently proposed to approximately solve the equal-sized graph matching problem, and exhibited a state-of-the-art performance (Zaslavskiy et al., 2009; Liu et al., 2012). However, they cannot be used for subgraph matching since either their convex or concave relaxation becomes no longer applicable. In this paper we extend the CCRP to tackle subgraph matching, by proposing a convex as well as a concave relaxation of the problem. Since in the context of CCRP, the convex relaxation can be viewed as an initialization of a concave programming, we introduce two other initializations for comparison. Meanwhile, the graduated assignment algorithm is also introduced in the experimental comparisons, which witness the validity of the proposed algorithm.

Cite this Paper

BibTeX
@InProceedings{pmlr-v25-liu12a, title = {A Convex-Concave Relaxation Procedure Based Subgraph Matching Algorithm}, author = {Liu, Zhi-Yong and Qiao, Hong}, booktitle = {Proceedings of the Asian Conference on Machine Learning}, pages = {237--252}, year = {2012}, editor = {Hoi, Steven C. H. and Buntine, Wray}, volume = {25}, series = {Proceedings of Machine Learning Research}, address = {Singapore Management University, Singapore}, month = {04--06 Nov}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v25/liu12a/liu12a.pdf}, url = {https://proceedings.mlr.press/v25/liu12a.html}, abstract = {Based on the convex-concave relaxation procedure (CCRP), the (extended) path following algorithms were recently proposed to approximately solve the equal-sized graph matching problem, and exhibited a state-of-the-art performance (Zaslavskiy et al., 2009; Liu et al., 2012). However, they cannot be used for subgraph matching since either their convex or concave relaxation becomes no longer applicable. In this paper we extend the CCRP to tackle subgraph matching, by proposing a convex as well as a concave relaxation of the problem. Since in the context of CCRP, the convex relaxation can be viewed as an initialization of a concave programming, we introduce two other initializations for comparison. Meanwhile, the graduated assignment algorithm is also introduced in the experimental comparisons, which witness the validity of the proposed algorithm.} }
Endnote
%0 Conference Paper %T A Convex-Concave Relaxation Procedure Based Subgraph Matching Algorithm %A Zhi-Yong Liu %A Hong Qiao %B Proceedings of the Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2012 %E Steven C. H. Hoi %E Wray Buntine %F pmlr-v25-liu12a %I PMLR %P 237--252 %U https://proceedings.mlr.press/v25/liu12a.html %V 25 %X Based on the convex-concave relaxation procedure (CCRP), the (extended) path following algorithms were recently proposed to approximately solve the equal-sized graph matching problem, and exhibited a state-of-the-art performance (Zaslavskiy et al., 2009; Liu et al., 2012). However, they cannot be used for subgraph matching since either their convex or concave relaxation becomes no longer applicable. In this paper we extend the CCRP to tackle subgraph matching, by proposing a convex as well as a concave relaxation of the problem. Since in the context of CCRP, the convex relaxation can be viewed as an initialization of a concave programming, we introduce two other initializations for comparison. Meanwhile, the graduated assignment algorithm is also introduced in the experimental comparisons, which witness the validity of the proposed algorithm.
RIS
TY - CPAPER TI - A Convex-Concave Relaxation Procedure Based Subgraph Matching Algorithm AU - Zhi-Yong Liu AU - Hong Qiao BT - Proceedings of the Asian Conference on Machine Learning DA - 2012/11/17 ED - Steven C. H. Hoi ED - Wray Buntine ID - pmlr-v25-liu12a PB - PMLR DP - Proceedings of Machine Learning Research VL - 25 SP - 237 EP - 252 L1 - http://proceedings.mlr.press/v25/liu12a/liu12a.pdf UR - https://proceedings.mlr.press/v25/liu12a.html AB - Based on the convex-concave relaxation procedure (CCRP), the (extended) path following algorithms were recently proposed to approximately solve the equal-sized graph matching problem, and exhibited a state-of-the-art performance (Zaslavskiy et al., 2009; Liu et al., 2012). However, they cannot be used for subgraph matching since either their convex or concave relaxation becomes no longer applicable. In this paper we extend the CCRP to tackle subgraph matching, by proposing a convex as well as a concave relaxation of the problem. Since in the context of CCRP, the convex relaxation can be viewed as an initialization of a concave programming, we introduce two other initializations for comparison. Meanwhile, the graduated assignment algorithm is also introduced in the experimental comparisons, which witness the validity of the proposed algorithm. ER -
APA
Liu, Z. & Qiao, H.. (2012). A Convex-Concave Relaxation Procedure Based Subgraph Matching Algorithm. Proceedings of the Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 25:237-252 Available from https://proceedings.mlr.press/v25/liu12a.html.

Related Material