A Functional Representation for Graph Matching

Fu-Dong Wang, Gui-Song 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 overview

This 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.


Graph matching is widely used to find correspondence between graph-structured 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 pair-wise constraints can be cast as a quadratic assignment problem (QAP), which is NP-complete and only approximate solutions can be found in polynomial time.

We propose a functional representation for graph matching (FRGM) for the purpose of giving geometric interpretations and better approximations for graph matching. We demonstrate our main idea that both the general and Euclidean graph matching can be formulated by functional representation framework. There are four main benefits of FRGM:

  • The functional representation gives a geometric insight for general graph matching: the edge attribute of graph can be formulated as an inner-product or metric on the function space.
  • The functional representation for Euclidean graph matching gives a new parameterization for graphs with geometric deformations, it allows us to estimate the correspondence and geometric deformation alternatively.
  • Due to the representation of pair-wise information ( edge attributes), the space complexity is only , lower than the space complexity of graph matching methods that use affinity matrix.
  • An efficient optimization strategy based on the Frank-Wolfe method is improved to solve the objective functions of both general and Euclidean graph matching.


An example of general graph matching with two undirected graphs embedded in low-dimensional manifolds, i.e., 3D faces . The node-attribute of each graph is computed by heat kernel signature (HKS), and the edge-attribute 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.

Objective values and correspondence map iterations. The binary map means one-to-one correspondence, and soft map can be seen as matching probabilities between nodes.

Display of matching probabilities between graph nodes. The pink lines mean correct matching, and a relatively thin line means smaller matching probability between two nodes.


An 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 .

Objective values and correspondence map iterations. Binary map means one-to-one correspondence, soft map can be seen as matching probabilities between nodes.

Display of the transformed graph (yellow dots) optimization iterations. Each line in pink is the offset vector between node and its correct matching.


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

Display of registration errors registrations.

Display of transformed graphs registrations.

Display of objective values registrations and total iterations. During the iterations in each registration, the objective function value decreases gradually. Finally, the objective function convergences to a stationary state.


More results

unequal-size case: 40-vs-50

equal-size case: 50-vs-50

CMU house sequnce

CMU hotel sequnce

PASCAL car image pairs

PASCAL motorbike image pairs

graphs with similarity deformations, noise and occlusions

graphs with nonrigid deformations, noise and occlusions


  1. 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.
  2. 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.
  3. Factorized Graph Matching [paper] [webpage]
    F. Zhou and F. De la Torre.
    IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 38(9):1774-1789, 2016.
  4. 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.
  5. Point-Set Registration: Coherent Point Drift [paper] [webpage]
    Myronenko A., Song X.
    IEEE Trans. on Pattern Analysis and Machine Intelligence (TPAMI), vol. 32, issue 12, pp. 2262-2275.