Source-linked AI summary
Learning Combinatorial Embedding Networks for Deep Graph Matching
Runzhong Wang, Junchi Yan, Xiaokang Yang
TL;DR
Graph matching requires effective node and structural affinity modeling despite combinatorial complexity and noise. The paper learns these affinities end to end with deep graph embeddings and supervised permutation loss, achieving state-of-the-art performance while supporting variable node counts and cross-category learning. An iterative cross-graph variant was unstable and degraded performance, so the simpler design was retained.
Problem
Graph matching needs affinity models that capture node and higher-order structure robustly against noise, whereas traditional predefined parametric functions have limited flexibility.
Method
The paper uses an end-to-end deep pipeline with graph convolutional node embeddings, learned intra- and cross-graph affinities, Sinkhorn assignment, and permutation cross-entropy loss.
Results
The method achieves state-of-the-art graph-matching performance, outperforming peer methods in accuracy and showing learning across different object categories.
Takeaways & Limitations
Permutation-based learning and shared graph embeddings provide a flexible graph-matching framework for varying node counts and category settings.
Takeaways & Limitations
An iterative cross-graph affinity design degraded performance and produced unstable training, limiting the paper to a simpler cross-graph component.
Abstract
from arXiv · showhide
Graph matching refers to finding node correspondence between graphs, such that the corresponding node and edge's affinity can be maximized. In addition with its NP-completeness nature, another important challenge is effective modeling of the node-wise and structure-wise affinity across graphs and the resulting objective, to guide the matching procedure effectively finding the true matching against noises. To this end, this paper devises an end-to-end differentiable deep network pipeline to learn the affinity for graph matching. It involves a supervised permutation loss regarding with node correspondence to capture the combinatorial nature for graph matching. Meanwhile deep graph embedding models are adopted to parameterize both intra-graph and cross-graph affinity functions, instead of the traditional shallow and simple parametric forms e.g. a Gaussian kernel. The embedding can also effectively capture the higher-order structure beyond second-order edges. The permutation loss model is agnostic to the number of nodes, and the embedding model is shared among nodes such that the network allows for varying numbers of nodes in graphs for training and inference. Moreover, our network is class-agnostic with some generalization capability across different categories. All these features are welcomed for real-world applications. Experiments show its superiority against state-of-the-art graph matching learning methods.
1. Introduction and Preliminaries
Graph matching seeks node correspondences that maximize node and structural affinity, but its combinatorial complexity and noisy settings make affinity modeling central. This paper proposes supervised deep affinity learning with permutation-based optimization, graph embeddings, and flexible node counts.
- Motivation: Graph matching establishes node correspondences by maximizing unary node and pairwise or higher-order structural similarity.Its robustness supports applications including visual tracking, action recognition, robotics, and 3-D reconstruction.
- Problem formulation: NP-completeness makes graph matching difficult, motivating approximate techniques for quadratic assignment formulations.The permutation matrix represents correspondence, while the affinity matrix encodes node-to-node and edge-to-edge affinities.
- Motivation: Traditional Gaussian-kernel and distance-based affinity models have limited flexibility for arbitrary structures, noise, and outliers.An inappropriate affinity model can make the matching solver struggle to find a useful global optimum.
- Proposed approach: The proposed supervised pipeline uses permutation loss with a Sinkhorn relaxation, providing a combinatorial objective that supports arbitrary numbers of graph nodes.The loss compares the predicted assignment with the ground-truth permutation through cross entropy.
- Proposed approach: Graph convolutional embeddings jointly learn node features, implicit higher-order structure, and cross-graph affinity through shared node-to-node layers.The shared design supports different node counts between graph pairs during training and testing.
- Experiments: Experiments and ablations show effectiveness of the permutation loss, feature extraction, graph convolutional embedding, and cross-graph affinity components.The method outperforms deep-learning peer and in accuracy, while also demonstrating learning across object categories.
2. Related Work
Related work spans shallow affinity learning, deep affinity networks, graph neural embeddings, and learned combinatorial solvers. The paper positions its contribution as end-to-end affinity learning that combines graph embeddings with differentiable assignment.
- Affinity learning: Prior affinity-learning methods commonly use shallow distance and kernel models, including weighted Euclidean distances and Gaussian similarity functions.A unified shallow parametric model can represent several earlier approaches.
- Affinity learning: Deep method learns graph-matching affinity with neural networks but uses pixel-offset loss and does not model node embeddings.The paper argues these choices fit graph matching less well and omit local structure beyond second-order information.
- Graph embeddings: Graph neural networks provide learnable high-order node embeddings for non-Euclidean graph data, motivating the paper’s use of graph convolutional networks.The cited earlier embedding methods cannot support end-to-end graph-matching learning, whereas GCN parameters are learned end to end.
- Combinatorial optimization: Other neural approaches learn combinatorial solvers for problems such as graph coloring, TSP, and quadratic assignment with predefined affinities.The paper instead learns the affinity function itself, leaving potential integration with learned solvers.
- Positioning: The proposed model encodes structural affinity in node embeddings, relaxes graph matching to linear assignment, and solves it with a Sinkhorn layer.This contrasts with methods that learn a solver from a predefined affinity matrix.
3. Proposed Approach
The proposed pipeline learns graph affinities and differentiable node permutations jointly from image features and graph structure. It uses graph embeddings to encode higher-order information and Sinkhorn-based permutation supervision for flexible matching.
- PIA-GM and PCA-GM combine deep image-structure processing with differentiable permutation prediction through a Sinkhorn network.PCA-GM adds cross-graph feature aggregation, whereas PIA-GM embeds only intra-graph features.
- CNN-extracted node features are aggregated by graph convolution to encode local structure and higher-order information in node embeddings.The graph convolution aggregates features from adjacent nodes and the node itself, while the initial node state is its CNN feature.
- Cross-graph aggregation uses a predicted doubly-stochastic similarity matrix to transfer features between nodes of the two graphs.The cross-graph message-passing scheme replaces the intra-graph adjacency matrix with the predicted correspondence matrix and its transpose.
- Embedding structure affinity into node-to-node scores reduces the traditional second-order affinity matrix to a linear affinity matrix while retaining higher-order information.The learned affinity function can use a bilinear mapping followed by an exponential function, with τ controlling discrimination as τ approaches zero from above.
- Sinkhorn alternates row and column normalization to produce a doubly-stochastic prediction, followed by Hungarian post-processing to obtain a permutation at test time.The Sinkhorn layer is differentiable, while the permutation loss compares its prediction with the ground-truth permutation using cross entropy.
4. Experiments
Experiments evaluate graph-matching accuracy on synthetic noisy graphs and natural-image benchmarks, comparing learned affinity models, losses, and peer methods. The proposed models generally outperform competing approaches and show cross-category generalization.
- Metrics and peer methods: Matching accuracy is computed from predicted and ground-truth permutation matrices as the fraction of correctly matched keypoint pairs.
- Metrics and peer methods: PCA-GM uses stacked intra-graph and cross-graph embedding layers with a permutation loss, while PIA-GM uses intra-graph embedding layers with the same loss.Both models use shared VGG16 features and Sinkhorn-based permutation prediction.
- Synthetic graphs: Synthetic experiments show PCA-GM remains robust to feature deformation and complicated graph structure under varying keypoint counts and noise levels.Each trial averages accuracy over 10 generated graph pairs.
- Pascal VOC Keypoints: On Pascal VOC Keypoint, PIA-GM, PIA-GM-OL, and PCA-GM outperform competing methods in most categories and in mean accuracy over 20 categories.The reported comparisons attribute gains to linear-assignment loss, learned embedding with Sinkhorn, and cross-graph embedding.
- Willow ObjectClass: On Willow ObjectClass, PCA-GM almost surpasses all competing methods in all categories while remaining class-agnostic.Models initialized from Pascal VOC can be fine-tuned on Willow for higher evaluation results.
- Generalization and ablations: Confusion-matrix experiments indicate that PCA-GM maintains accuracy across similar categories, while embedding and permutation loss provide better behavior than their alternatives.Rows denote training categories, columns denote testing categories, and colors are normalized within each category matrix.
5. Conclusion
The paper presents a deep-learning framework that learns graph affinity with deep networks and uses permutation loss for arbitrary graph transformations. Experiments and ablations report state-of-the-art performance for the proposed method.
- The framework parameterizes graph affinity with deep networks and uses permutation loss to account for arbitrary transformations between graphs.
- Extensive experiments, ablations, and peer comparisons report state-of-the-art performance for the proposed method.