Reweighted Random Walks for Graph Matching



Graph matching is an essential problem in computer vision and machine learning. In this paper, we introduce a random walk view on the problem and propose a robust graph matching algorithm against outliers and deformation. Matching between two graphs is formulated as node selection on an association graph whose nodes represent candidate correspondences between the two graphs. The solution is obtained by simulating random walks with reweighting jumps enforcing the matching constraints on the association graph. Our algorithm achieves noise-robust graph matching by iteratively updating and exploiting the confidences of candidate correspondences. In a practical sense, our work is of particular importance since the real-world matching problem is made difficult by the presence of noise and outliers. Extensive and comparative experiments demonstrate that it outperforms the state-of-the-art graph matching algorithms especially in the presence of outliers and deformation.

paper thumbnail


ECCV 2010 paper. (pdf, 4.53MB)


pdf file (poster), 1.95MB


zip file (MATLAB), 35KB - updated May 2013


zip file (png images), 10.2MB - the image dataset used in Sec.4.3

zip file (MATLAB code and data), 170MB
- additional codes and data with ground truths for image matching demo


Minsu Cho, Jungmin Lee, Kyoung Mu Lee. "Reweighted Random Walks for Graph Matching", European Conference on Computer Vision (ECCV), 2010.

* A high-order generalization of this work is provided in our CVPR2011 paper here.

Experimental Results

We performed intensive experiments for the proposed method in three tasks: (1) synthetically generated random graphs, (2) point matching task using the CMU House image sequence and random point sets, and (3) feature matching using a real image dataset (30 pairs). These three experiments are designed to evaluate the performance of our algorithm (RRWM)[1] on various graph matching tasks and to compare it with other state-of-the-art methods: Spectral Matching (SM)[2], Spectral Matching with Affine Constraints (SMAC)[3], Hyper Graph Matching (HGM)[4], Integer Projected Fixed Point method (IPFP)[5], Graduated Assignment algorithm (GAGM)[6], and Successive Projection Graph Matching (SPGM)[7]. We additionally tested the performance of the random walk matching with conventional row-wise normalization denoted by NRWM. For details, refer to our paper[1].

1. Minsu Cho, Jungmin Lee, Kyoung Mu Lee. "Reweighted Random Walks for Graph Matching", ECCV 2010.
2. M. Leordeanu and M. Hebert. "A Spectral Technique for Correspondence Problems Using Pairwise Constraints", ICCV 2005.
3. T. Cour and P. Srinivasan and J. Shi. "Balanced graph matching", NIPS 2006.
4. R. Zass and A. Shashua. "Probabilistic graph and hypergraph matching", CVPR 2008.
5. M. Leordeanu and M. Herbert. "An Integer Projected Fixed Point Method for Graph Matching and MAP Inference", NIPS 2009.
6. S. Gold and A. Rangarajan. "A Graduated Assignment Algorithm for Graph Matching", PAMI 1996.
7. B. J. van Wyk and M. A. van Wyk. "A pocs-based graph matching algorithm", PAMI 2004.

Random Graph Matching

In this experiment, following the experimental protocol of previous work, e.g. [6,3], we performed a comparative evaluation on random graph matching problems. For details, refer to our paper.

Outliers on Both Graphs
Outliers on only One Graph
Edge Density

Matching on the CMU House sequence

In this section, we performed feature point matching on the CMU House image sequencewhich has been widely used in the previous work and compared with other methods. For details, refer to our paper.
A test example
SM 20/30
RRWM(ours) 30/30
30 by 30 matching accuracy
20 by 30 matching accuracy

Random Point Set Matching

We also performed more general point matching experiment by synthetically generating random point sets.
For this experiment, we followed a conventional point set matching setup . For each trial, two point sets P and Q were generated in 2D domain. As we did in random graph matching problem, nin points are randomly generated as inlier nodes for graph GP. Then, we added the Gaussian noise N(0,&sigma2) for each dimension (x-y coordinates) to construct perturbed graph Q. We also added randomly distributed distracting nPout and nQout outlier points for graph GP and GQ respectively. We adjusted the domain size to locate 10 points in 256 by 256 area. The graph attribute aPij was defined as the Euclidean distance between the nodes (or the points) vPi and vPj in graph GP, and likewise for aQij. The affinity matrix was calculated by Wia,jb = exp(- |aPij - aQab |2/&sigmas2), where the scale factor &sigmas2 was set to 100.
(a) Outliers
(b) Deformation
The above figures show the performance curves for deformation and outlier experiments, respectively. For the deformation experiment in Fig.(b), we experimented with varying deformation noise &sigma varying from 0 to 20 by increments of 2, while fixing the number of inliers nin = 20, outliers nPout=nQout = 0. For the outlier experiment in Fig.(a), the number of outliers nPout=nQout are varied from 0 to 30 by increments of 2, while fixing inlier number nin = 20, deformation noise &sigma = 0. In both experiments, the best 4 methods, RRWM, GAGM, SPGM, and IPFP, provide comparable results and among them RRWM is better than others. With increasing deformation and outliers, we can see that the performance curves of SM show the similar trends as reported in [2]. Note that as outliers or deformation increases, RRWM, GAGM, SPGM, and IPFP largely outperform other methods such as SM, SMAC, HGM, and NRWM. However, as the point set matching problems are relatively easy, the top-ranked methods do not show large performance gaps between them. Nevertheless, note that our RRWM generates consistently the best performance in accuracy, and is most scalable among the top-ranked methods.

Real Image Matching

In this experiment we applied our method to challenging real image matching problems using local feature detectors. We constructed a dataset of 30 image pairs containing various images most of which are collected from Caltech-101 and MSRC datasets, and generated candidate correspondences using the MSER detector[2] and the SIFT descriptor[3]. Using the distance of 128-dim SIFT descriptor, all the possible candidate matches were collected if the feature pair has closer distance in SIFT feature space than a loose threshold &delta = 0.6, allowing multiple correspondences for each feature. To measure the dissimilarity between two candidate region correspondences (i,a) and (j,b), we adopted the mutual projection error function dia;jb used in [1], and set Wia;jb = max( 50 - dia;jb, 0 ). The ground truths were manually labeled for all candidate correspondences of each image pair, and the accuracy and relative objective score were computed and compared with SM, SMAC, and GAGM.

1. Minsu Cho, Jungmin Lee, Kyoung Mu Lee. "Feature Correspondence and Deformable Object Matching via Agglomerative Correspondence Clustering", ICCV 2009.
2. J. Matas, O. Chum, M. Urban and T. Pajdla. "Robust Wide Baseline Stereo from Maximally Stable Extremal Regions", BMVC 2002.
3. David G. Lowe. "Object Recognition from Local Scale-Invariant Features", ICCV 1999.

The results are shown in the following and summarized in Table.1.

Avg. of accuracy (%) 64.01 % 52.08 % 39.74 % 58.74 %
Avg. of relative score (%) 100 % 82.41 % 59.35 % 92.13 %
Table 1. Matching performance on the real image dataset (30 pairs)

In the following figures, the algorithm, true matches per ground truths, and objective scores are captioned. This experiment and the dataset are designed for producing the challenging feature matching problems where unary local features are very ambiguous. Our RRWM clearly outperforms other methods both in accuracy and objective score as summarized in Table.1. Note that the second best, GAGM was about ten times slower than RRWM in this experiment as similar in the previous experiments.

Image pair
Initial matches 780
RRWM 23/24 (20816.4)
SM 12/24 (17010.9)
SMAC 10/24 (19264.6)
GAGM 10/24 (12466.3)
Image pair
Initial matches
RRWM 23/25 (13848.5)
SM 13/25 (5895.8)
SMAC 21/25 (11058.4)
GAGM 23/25 (12080.3)
Image pair
Initial matches
RRWM 7/20 (72156.9)
SM 7/20 (69055.0)
SMAC 8/20 (51361.7)
GAGM 8/20 (37529.4)
Image pair
Initial matches
RRWM 19/31 (25902.2)
SM 10/31 (12653.8)
SMAC 17/31 (20561.3)
GAGM 21/31 (23699.5)
Image pair
Initial matches
RRWM 16/24 (15085.3)
SM 16/24 (14684.7)
SMAC 0/24 (4599.0)
GAGM 16/24 (14224.3)
Image pair
Initial matches
RRWM 26/29 (34369.0)
SM 26/29 (32688.2)
SMAC 22/29 (27474.1)
GAGM 23/29 (29808.9)
Image pair
Initial matches
RRWM 4/5 (872.1)
SM 4/5 (841.9)
SMAC 1/5 (396.7)
GAGM 4/5 (829.0)
Image pair
Initial matches
RRWM 4/6 (1139.0)
SM 1/6 (707.1)
SMAC 2/6 (545.7)
GAGM 4/6 (1013.4)
Image pair
Initial matches
RRWM 8/9 (3387.0)
SM 8/9 (3076.4)
SMAC 5/9 (1766.7)
GAGM 6/9 (3342.7)
Image pair
Initial matches
RRWM 14/20 (8787.2)
SM 10/20 (4961.9)
SMAC 4/20 (3508.5)
GAGM 16/20 (8299.4)
Image pair
Initial matches
RRWM 14/25 (16197.5)
SM 11/25 (10948.8)
SMAC 13/25 (11179.5)
GAGM 15/25 (15941.5)
Image pair
Initial matches
RRWM 18/42 (37346.9)
SM 18/42 (36265.9)
SMAC 16/42 (30407.5)
GAGM 15/42 (30785.1)
Image pair
Initial matches
RRWM 10/25 (27237.3)
SM 9/25 (25298.6)
SMAC 7/25 (17755.1)
GAGM 9/25 (25663.7)
Image pair
Initial matches
RRWM 11/17 (22579.6)
SM 11/17 (22008.0)
SMAC 9/17 (15224.6)
GAGM 9/17 (21941.4)
Image pair
Initial matches
RRWM 10/26 (18446.6)
SM 7/26 (16917.5)
SMAC 8/26 (7154.3)
GAGM 9/26 (18240.5)
Image pair
Initial matches
RRWM 10/26 (21864.6)
SM 9/26 (21152.7)
SMAC 6/26 (12988.2)
GAGM 10/26 (21450.2)
Image pair
Initial matches
RRWM 12/18 (14354.1)
SM 10/18 (12928.8)
SMAC 3/18 (8055.4)
GAGM 12/18 (11530.3)
Image pair
Initial matches
RRWM 6/17 (9566.2)
SM 2/17 (6931.3)
SMAC 4/17 (7675.4)
GAGM 4/17 (8650.4)
Image pair
Initial matches
RRWM 6/16 (14094.6)
SM 6/16 (13841.2)
SMAC 3/16 (10209.3)
GAGM 6/16 (12567.2)
Image pair
Initial matches
RRWM 3/3 (757.3)
SM 3/3 (520.6)
SMAC 1/3 (203.3)
GAGM 3/3 (734.1)
Image pair
Initial matches
RRWM 5/12 (15609.2)
SM 5/12 (14240.5)
SMAC 4/12 (7813.6)
GAGM 5/12 (15249.7)
Image pair
Initial matches
RRWM 6/8 (1921.6)
SM 5/8 (1796.4)
SMAC 1/8 (596.6)
GAGM 6/8 (1886.8) SM
Image pair
Initial matches
RRWM 6/8 (19102.3)
SM 7/8 (17710.9)
SMAC 4/8 (10715.3)
GAGM 5/8 (17999.7)
Image pair
Initial matches
RRWM 12/16 (7468.2)
SM 8/16 (5291.4)
SMAC 9/16 (4829.9)
GAGM 13/16 (7088.3)
Image pair
Initial matches
RRWM 6/16 (9844.3)
SM 3/16 (6950.4)
SMAC 6/16 (6537.3)
GAGM 3/16 (8091.4)
Image pair
Initial matches
RRWM 14/15 (9030.3)
SM 14/15 (7576.9)
SMAC 14/15 (7058.4)
GAGM 13/15 (7976.8)
Image pair
Initial matches
RRWM 6/10 (1531.2)
SM 7/10 (1445.1)
SMAC 6/10 (792.6)
GAGM 5/10 (1374.9)
Image pair
Initial matches
RRWM 6/10 (5983.0)
SM 1/10 (3622.5)
SMAC 2/10 (3407.1)
GAGM 5/10 (5797.7)
Image pair
Initial matches
RRWM 7/10 (4327.2)
SM 6/10 (3491.9)
SMAC 2/10 (1816.5)
GAGM 7/10 (3816.6)
Image pair
Initial matches
RRWM 6/10 (5983.0)
SM 1/10 (3622.5)
SMAC 2/10 (3407.1)
GAGM 5/10 (5797.7)