graph matching
**Graph Matching** is the **computational problem of finding the optimal node-to-node correspondence (alignment) between two graphs that maximizes the preservation of edge structure** — determining which node in Graph A corresponds to which node in Graph B such that connected pairs in one graph map to connected pairs in the other, with applications spanning computer vision (skeleton tracking), biology (protein network alignment), and pattern recognition.
**What Is Graph Matching?**
- **Definition**: Given two graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$, graph matching seeks a mapping $pi: V_1 o V_2$ that maximizes agreement between the two graph structures: $max_pi sum_{(i,j) in E_1} mathbb{1}[(pi(i), pi(j)) in E_2]$ — the number of edges in $G_1$ whose corresponding pairs are also edges in $G_2$. This is the quadratic assignment problem (QAP), which is NP-hard in general.
- **Exact vs. Inexact Matching**: Exact matching (graph isomorphism) requires a perfect one-to-one correspondence preserving all edges. Inexact matching (error-tolerant matching) allows mismatches and seeks to minimize the total structural disagreement. Real-world applications almost always require inexact matching because observed graphs contain noise, missing edges, and spurious connections.
- **One-to-One vs. Many-to-Many**: Standard graph matching assumes a one-to-one node correspondence ($|V_1| = |V_2|$). When graphs have different sizes, matching becomes a partial assignment problem — some nodes in the larger graph are left unmatched, requiring additional deletion costs and making the optimization harder.
**Why Graph Matching Matters**
- **Visual Object Tracking**: In video analysis, objects are represented as skeletal graphs (joints connected by bones). Matching the skeleton graph in Frame $t$ to Frame $t+1$ establishes the joint correspondence needed for pose tracking — the left elbow in Frame 1 maps to the left elbow in Frame 2, even when the person has moved significantly.
- **Biological Network Alignment**: Aligning protein-protein interaction (PPI) networks across species (human vs. mouse) reveals conserved functional modules and orthologous protein relationships. Graph matching identifies which human protein corresponds to which mouse protein based on their interaction patterns, complementing sequence-based homology with network-based evidence.
- **Document and Image Comparison**: Graphs extracted from images (scene graphs, region adjacency graphs) or documents (dependency parse trees, knowledge graphs) enable structural comparison through graph matching — two images are similar if their scene graphs match well, providing a more robust comparison than pixel-level or feature-level metrics.
- **Neural Graph Matching**: Deep graph matching networks (DGMC, GMN) learn to compute soft correspondences between graphs using cross-graph attention — node $i$ in $G_1$ attends to all nodes in $G_2$ to find its best match, producing a continuous relaxation of the discrete matching problem that is differentiable and end-to-end trainable.
**Graph Matching Approaches**
| Approach | Type | Key Property |
|----------|------|-------------|
| **Hungarian Algorithm** | Exact (bipartite) | $O(N^3)$ for bipartite assignment |
| **Spectral Matching** | Approximate | Uses leading eigenvectors of affinity matrix |
| **Graduated Assignment** | Continuous relaxation | Softmax annealing from soft to hard matching |
| **DGMC (Deep Graph Matching)** | Neural | Cross-graph attention + Sinkhorn normalization |
| **VF2/VF3** | Exact subgraph | Backtracking with pruning heuristics |
**Graph Matching** is **network alignment** — solving the correspondence puzzle of which node in one graph maps to which node in another, enabling structural comparison across domains from computer vision to molecular biology to software analysis.