What is Graph Matching¶

Introduction¶

Graph Matching (GM) is a fundamental yet challenging problem in pattern recognition, data mining, and others. GM aims to find node-to-node correspondence among multiple graphs, by solving an NP-hard combinatorial problem. Recently, there is growing interest in developing deep learning based graph matching methods.

Graph matching techniques have been applied to the following applications:

Graph Matching Pipeline¶

Solving a real world graph matching problem may involve the following steps:

1. Extract node/edge features from the graphs you want to match.

2. Build affinity matrix from node/edge features.

3. Solve the graph matching problem by GM solvers.

And Step 1 maybe done by methods depending on your application, Step 2&3 can be handled by pygmtools.

The Math Form¶

Let’s involve a little bit math to better understand the graph matching pipeline. In general, graph matching is of the following form, known as Quadratic Assignment Problem (QAP):

$\begin{split}&\max_{\mathbf{X}} \ \texttt{vec}(\mathbf{X})^\top \mathbf{K} \texttt{vec}(\mathbf{X})\\ s.t. \quad &\mathbf{X} \in \{0, 1\}^{n_1\times n_2}, \ \mathbf{X}\mathbf{1} = \mathbf{1}, \ \mathbf{X}^\top\mathbf{1} \leq \mathbf{1}\end{split}$

The notations are explained as follows:

• $$\mathbf{X}$$ is known as the permutation matrix which encodes the matching result. It is also the decision variable in graph matching problem. $$\mathbf{X}_{i,a}=1$$ means node $$i$$ in graph 1 is matched to node $$a$$ in graph 2, and $$\mathbf{X}_{i,a}=0$$ means non-matched. Without loss of generality, it is assumed that $$n_1\leq n_2.$$ $$\mathbf{X}$$ has the following constraints:

• The sum of each row must be equal to 1: $$\mathbf{X}\mathbf{1} = \mathbf{1}$$;

• The sum of each column must be equal to, or smaller than 1: $$\mathbf{X}\mathbf{1} \leq \mathbf{1}$$.

• $$\mathtt{vec}(\mathbf{X})$$ means the column-wise vectorization form of $$\mathbf{X}$$.

• $$\mathbf{1}$$ means a column vector whose elements are all 1s.

• $$\mathbf{K}$$ is known as the affinity matrix which encodes the information of the input graphs. Both node-wise and edge-wise affinities are encoded in $$\mathbf{K}$$:

• The diagonal element $$\mathbf{K}_{i + a\times n_1, i + a\times n_1}$$ means the node-wise affinity of node $$i$$ in graph 1 and node $$a$$ in graph 2;

• The off-diagonal element $$\mathbf{K}_{i + a\times n_1, j + b\times n_1}$$ means the edge-wise affinity of edge $$ij$$ in graph 1 and edge $$ab$$ in graph 2.

Other Materials¶

Readers are referred to the following surveys for more technical details about graph matching:

• Junchi Yan, Shuang Yang, Edwin Hancock. “Learning Graph Matching and Related Combinatorial Optimization Problems.” IJCAI 2020.

• Junchi Yan, Xu-Cheng Yin, Weiyao Lin, Cheng Deng, Hongyuan Zha, Xiaokang Yang. “A Short Survey of Recent Advances in Graph Matching.” ICMR 2016.