NDLI: A Path Following Algorithm for the Graph Matching Problem

Content Provider	IEEE Xplore Digital Library
Author	Zaslavskiy, M. Bach, F. Vert, J.-P.
Copyright Year	1979
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.
Sponsorship	IEEE Computer Society
Page Count	16
File Size	2896777
Starting Page	2227
Ending Page	2242
File Format	PDF
ISSN	01628828
Volume Number	31
Issue Number	12
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2009-12-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Machine learning algorithms Bioinformatics Proteins Quadratic programming Stochastic processes Interpolation Optimization methods Retina Gradient methods Machine learning image processing. Graph algorithms graph matching convex programming gradient methods machine learning classification Pattern Recognition Graph Theory Discrete Mathematics Mathematics of Computing Constrained optimization Convex programming Quadratic programming methods Optimization Numerical Analysis Learning Artificial Intelligence Object recognition Scene Analysis Image Processing and Computer Vision Computing Methodologies
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Artificial Intelligence Computational Theory and Mathematics Computer Vision and Pattern Recognition Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Dynamic Programming and Graph Algorithms in Computer Vision

A path following algorithm for the graph matching problem

A path following algorithm for the graph matching problem

Data Fusion and Multicue Data Matching by Diffusion Maps

Learning Graph Matching

Graph Matching by Simplified Convex-Concave Relaxation Procedure

Performance Comparison of Scene Matching Techniques

Dinkelbach NCUT: An Efficient Framework for Solving Normalized Cuts Problems with Priors and Convex Constraints

Path Similarity Skeleton Graph Matching

A Path Following Algorithm for the Graph Matching Problem

Similar Documents

Dynamic Programming and Graph Algorithms in Computer Vision

A path following algorithm for the graph matching problem

A path following algorithm for the graph matching problem

Data Fusion and Multicue Data Matching by Diffusion Maps

Learning Graph Matching

Graph Matching by Simplified Convex-Concave Relaxation Procedure

Performance Comparison of Scene Matching Techniques

Dinkelbach NCUT: An Efficient Framework for Solving Normalized Cuts Problems with Priors and Convex Constraints

Path Similarity Skeleton Graph Matching

A Path Following Algorithm for the Graph Matching Problem