A Path Following Algorithm for the Graph Matching Problem

Francis Bach

Description

A Path Following Algorithm for the Graph Matching Problem Mikhail Zaslavskiy, Francis Bach, and Jean-Philippe Vert Abstract—We propose a convex-concave programming approach for the labeled weighted graph matching problem. The convex- concave programming formulation is obtained by rewriting the weighted graph matching problem as a least-square problem on the set of permutation matrices and relaxing it to two different optimization problems: a quadratic convex and a quadratic concave optimization problem on the set of doubly stochastic matrices. The concave relaxation has the same global minimum as the initial graph matching problem, but the search for its global minimum is also a hard combinatorial problem. We, therefore, construct an approximation of the concave problem solution by following a solution path of a convex-concave problem obtained by linear interpolation of the convex and concave formulations, starting from the convex relaxation. This method allows to easily integrate the information on graph label similarities into the optimization problem, and therefore, perform labeled weighted graph matching. The algorithm is compared with some of the best performing graph matching methods on four data sets: simulated graphs, QAPLib, retina vessel images, and handwritten Chinese characters. In all cases, the results are competitive with the state of the art. Index Terms—Graph algorithms, graph matching, convex programming, gradient methods, machine learning, classification, image processing. Ç 1 INTRODUCTION THE graph matching problem is among the mostimportant challenges of graph processing and plays a central role in various fields of pattern recognition.

• f0?p ?


• convex


• problem can


• concave relaxation


• distance between


• matching problem


• graph matching


• quadratic concave


• pahptk1 ? kagp

Sujets

• Analysis
• Convex

Informations

• Publié par: pefav
• Nombre de lectures: 24
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 31, NO. 12, DECEMBER 2009

A Path Following Algorithm for the Graph Matching Problem Mikhail Zaslavskiy, Francis Bach, and Jean-Philippe Vert

Abstract —We propose a convex-concave programming approach for the labeled weighted graph matching problem. The convex- concave programming formulation is obtained by rewriting the weighted graph matching problem as a least-square problem on the set of permutation matrices and relaxing it to two different optimization problems: a quadratic convex and a quadratic concave optimization problem on the set of doubly stochastic matrices. The concave relaxation has the same global minimum as the initial graph matching problem, but the search for its global minimum is also a hard combinatorial problem. We, therefore, construct an approximation of the concave problem solution by following a solution path of a convex-concave problem obtained by linear interpolation of the convex and concave formulations, starting from the convex relaxation. This method allows to easily integrate the information on graph label similarities into the optimization problem, and therefore, perform labeled weighted graph matching. The algorithm is compared with some of the best performing graph matching methods on four data sets: simulated graphs, QAPLib, retina vessel images, and handwritten Chinese characters. In all cases, the results are competitive with the state of the art.

Index Terms —Graph algorithms, graph matching, convex programming, gradient methods, machine learning, classification, image processing.

Ç

2227

1 I NTRODUCTION graph matching problem is among the most T i H m E portantchallengesofgraphprocessingandplaysa rith A m n s ot t h h e a r ta g r r e ou s p up o p f os m e e d th t o o d b s e in m c o l r u e de s s ca a la p b p l r e o . x T i h m e at p e ri a c l e g t o o - central role in various fields of pattern recognition. Roughly  pay for the scalability is that the solution found is usually speaking, the problem consists in finding a correspondence  only an approximation of the optimal matching. Approx- between vertices of two given graphs, which is optimal in  imate methods may be divided into two groups of some sense. Usually, the optimality refers to the alignment  algorithms. The first group is composed of methods, which of graph structures and, when available, of vertices labels,  use spectral representatio ns of adjacency matrices or although other criteria are possible as well. A nonexhaus-  equivalently embed the vertices into a euclidean space, tive list of graph matching applications includes document  linear ma al processing tasks like optical character recognition [1], [2],  where linear or non tching gorithms can be imageanalysis(2Dand3D)[3],[4],[5],[6],orbioinformatics deployed.ThisapproachwaspioneeredbyUmeyama[1 r 3 e ] - , [7], [8], [9].  while further different methods based on spectral rep Duringthelastdecade,manydifferentalgorithmsfor sentationswereproposedin[3],[ r 4 i ],[5],[14],[15].The graphmatchinghavebeenproposed.Becauseofthe s a e lg co or n i d th g m r s oup wh o i f ch ap w pr o o r x k im d a i t r e ect a l l y go w t i h th ms gr is ap c h om a p dj o a s c e e d nc o y f combinatorial nature of this problem, it is very hard to solve  matrices and typically involve a relaxation of the discrete it exactly for large graphs, however, some methods based on incomplete enumeration may be applied to search for an exact  optimization problem. The most effective algorithms were optimalsolutioninthecaseofsmallorsparsegraphs.Some pro A p n os i e n d te i r n es [ t 6 i ] n , g [ i 1 n 6] s , ta [ n 17 c ] e , o [ f 18 t ] h . egraphmatchingproblemis examples of such algorithms may be found in [10], [11], [12].  the matching of labeled graphs. In that case, graph vertices have associated labels, which may be numbers, categorical . fo M r .Z M a a sl t a h v e s m ki a y ti i c s al wit M h o t r h p e ho C l e o ntr , ef M or in C e o s m P p a u r t i a s t T i e o c n h a , lB 3 i 5 ol r o u g e ya S n a d in t t h - e H C o e n n o t r r e e , variables, etc. The important point is that there is also a gy similarity measure between these labels. Therefore, when 7 M 73 — 05 U9 F 0 o 0 n , t 2 ai 6 n r eb u l e ea d u ’U c l e m d , ex 7 , 52 F 4 r 8 an P c a e r , is a c n e d de t x he 05 I , n F st r i a t n u c t e e . Curie—INSER- we search for the optimal correspondence between vertices, E-mail: [e-mail]. we search a correspondence which matches not only the . F. Bach is with the INRIA—Willow Project Team, Laboratoire d’Informa- structures of the graphs but also vertices with similar labels. t 2 i 3 qu a e ve d n e ue l’ d E ’ c It ol a e lie, N 7 or 52 m 1 al 4 e P S ar u i p s e , ´ r F ie r u a r n e ce. (C E N -m R a S i / l: E f N ra S n /I ci N s. R b I a A ch@ U in M ri R a.f 8 r. 548), Some widely used approaches for this application only use . J.-P. Vert is with the Centre for Computational Biology, Mines ParisTech, the information about similarities between graph labels. In 35 rue Saint-Honore, 77305 Fontainebleau cedex, France, and the Institut vision, one such algorithm is the shape context algorithm Curie—INSERM—U900, 26 rue d’Ulm, 75248 Paris cedex 05, France. proposed in [19], which involves an efficient algorithm of E-mail: [e-mail]. node label construction. Another example is the BLAST- 2 M 0 a 0 n 8; us p c u ri b p li t sh re e c d ei o v n e l d in 3 e 1 3 Ja O n c . t. 2 2 0 0 0 0 8; 8. revised28June2008;accepted15Sept. based algorithms in bioinformatics such as the Inparanoid Recommended for acceptance by R. Zabih. algorithm [20], where correspondence between different t F p o a r m i i nf @ o c r o m m a p ti u o t n er. o o n rg, ob a t n ai d ni r n ef g er r e e n p c r e in I t E s E o E f C t S his Lo a g rt N ic u le m , b p e l r easesende-mailto: protein networks is established on the basis of BLAST TPAMI-2008-01-0070. scores between pairs of proteins. The main advantages of all Digital Object Identifier no. 10.1109/TPAMI.2008.245. these methods are their speed and simplicity. However, the 0162-8828/09/$25.00  2009 IEEE Published by the IEEE Computer Society