A Functional Representation for Graph Matching
FuDong Wang,
GuiSong Xia,
Nan Xue,
Yipeng Zhang,
Marcello Pelillo
LIESMARS CAPTAIN, Wuhan University, Wuhan, China
School of Computer Science, Wuhan University, Wuhan, China
DAIS, University of Venice, Venice, Italy
Brief overviewThis work presents a functional representation for graph matching (FRGM). From the functional representation perspective, graph matching can be represented in linear formulations: (1) for general graph matching, graphs are identically represented by linear function space , the edge attributes are represented by inner product or metric , and the correspondence between graphs is represented by the linear functional representation map of . Then the general graph matching is cast as finding optimal representation map in the sense of inner product or metric preserving. (2) For Euclidean graph matching with graphs embedded in , the linear representation map can be directly defined on due to the natural linearity of . Further more, we can extend this linear representation map as a new geometric parameterization associative with geometric parameters for graphs under rigid or nonrigid deformations, so we can estimate both the correspondence and geometric transformation between graphs simultaneously. 

Introduction 

Graph matching is widely used to find correspondence between graphstructured datas in computer
vision and pattern recognition.
Generally, graph matching problem is formulated in an optimization
way: finding optimal correspondence between graphs by minimizing or maximizing objective
functions the varying correspondence. However, graph matching that incorporates pairwise
constraints can be cast as a quadratic
assignment problem (QAP), which is NPcomplete and only approximate solutions can be found in polynomial time.


FRGMGAn example of general graph matching with two undirected graphs embedded in lowdimensional manifolds, i.e., 3D faces . The nodeattribute of each graph is computed by heat kernel signature (HKS), and the edgeattribute of each graph is computed as the geodesic distance between nodes. The 3D face dataset is generated from the work of Li Zhang et.al. 



FRGMEAn example of Euclidean graph matching, , the graph nodes are points in . The node attribute is computed by Shape Context , and the edge attribute is computed as the Euclidean distance or vector between two nodes. The images are taken from the CMU house and hotel sequence dataset and PASCAL car and motorbike image dataset . 



FRGMDAn example of matching graphs with geometric deformations. There is a similarity transformation between these two graphs: . Also, noise and outliers are added to . 





Data 

More results 

References

Adaptively Transforming Graph Matching
[paper]
F.D. Wang, N. Xue, Y.P. Zhang, X. Bai, G.S. Xia.
IEEE European Conference on Computer Vision (ECCV), 2018. 
A Functional Representation for Graph Matching
[PDF]
F.D. Wang, G.S. Xia, N. Xue, Y.P. Zhang, M. Pelillo.
IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 2019. 
Factorized Graph Matching
[paper]
[webpage]
F. Zhou and F. De la Torre.
IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 38(9):17741789, 2016. 
An Integer Projected Fixed Point Method for Graph Matching and MAP Inference
[paper]
[webpage]
M. Leordeanu, M. Hebert and R. Sukthankar.
Advances in Neural Information Processing Systems (NIPS), 2009. 
PointSet Registration: Coherent Point Drift
[paper]
[webpage]
Myronenko A., Song X.
IEEE Trans. on Pattern Analysis and Machine Intelligence (TPAMI), vol. 32, issue 12, pp. 22622275.