Models

ThinkMatch currently contains pytorch source code of the following deep graph matching methods:

Note

For up-to-date benchmark, please refer to paper-with-code.

GMN

Our implementation of the following paper:

  • Andrei Zanfir and Cristian Sminchisescu. “Deep Learning of Graph Matching.” CVPR 2018.

    [paper]

GMN proposes the first deep graph matching pipeline which is end-to-end trainable via supervised learning and gradient descent. It proposes to combine the following components to formulate the graph matching pipeline:

  • VGG16 CNN to extract image features

  • Delaunay triangulation to build graphs

  • Building affinity matrix efficiently via Factorized Graph Matching (FGM)

  • Solving the resulting Quadratic Assignment Problem (QAP) by Spectral Matching (SM) and Sinkhorn algorithm which are differentiable

  • Supervised learning based on pixel offset loss (known as “Robust loss” in the paper)

Benchmark Results

PascalVOC - 2GM

experiment config: experiments/vgg16_gmn_voc.yaml

pretrained model: google drive

model

year

aero

bike

bird

boat

bottle

bus

car

cat

chair

cow

table

dog

horse

mbkie

person

plant

sheep

sofa

train

tv

mean

GMN

2018

0.4163

0.5964

0.6027

0.4795

0.7918

0.7020

0.6735

0.6488

0.3924

0.6128

0.6693

0.5976

0.6106

0.5975

0.3721

0.7818

0.6800

0.4993

0.8421

0.9141

0.6240

Willow Object Class - 2GM

experiment config: experiments/vgg16_gmn_willow.yaml

pretrained model: google drive

model

year

remark

Car

Duck

Face

Motorbike

Winebottle

mean

GMN

2018

0.6790

0.7670

0.9980

0.6920

0.8310

0.7934

SPair-71k - 2GM

experiment config: experiments/vgg16_gmn_spair71k.yaml

pretrained model: google drive

model

year

aero

bike

bird

boat

bottle

bus

car

cat

chair

cow

dog

horse

mtbike

person

plant

sheep

train

tv

mean

GMN

2018

0.5991

0.5099

0.7428

0.4672

0.6328

0.7552

0.6950

0.6462

0.5751

0.7302

0.5866

0.5914

0.6320

0.5116

0.8687

0.5787

0.6998

0.9238

0.6526

File Organization

├── affinity_layer.py
|   the implementation of affinity layer to compute the affinity matrix for GMN
├── displacement_layer.py
|   the implementation of the displacement layer to compute the pixel offset loss
├── model.py
|   the implementation of training/evaluation procedures of GMN
├── model_config.py
|   the declaration of model hyperparameters
└── voting_layer.py
    the implementation of voting layer to compute the row-stotatic matrix with softmax

Credits and Citation

Please cite the following paper if you use this model in your research:

@inproceedings{ZanfirCVPR18,
  author = {A. Zanfir and C. Sminchisescu},
  title = {Deep Learning of Graph Matching},
  booktitle = {IEEE Conference on Computer Vision and Pattern Recognition},
  pages={2684--2693},
  year={2018}
}

PCA-GM

Our implementation of the following papers:

  • Runzhong Wang, Junchi Yan and Xiaokang Yang. “Combinatorial Learning of Robust Deep Graph Matching: an Embedding based Approach.” TPAMI 2020.

    [paper], [project page]

  • Runzhong Wang, Junchi Yan and Xiaokang Yang. “Learning Combinatorial Embedding Networks for Deep Graph Matching.” ICCV 2019. [paper]

PCA-GM proposes the first deep graph matching network based on graph embedding, and it is composed of the following components:

  • VGG16 CNN to extract image features

  • Delaunay triangulation to build graphs

  • Graph Convolutional Network (GCN) with cross-graph convolution to embed graph structure features

  • Solving the resulting Linear Assignment Problem by Sinkhorn network

  • Supervised learning based on cross entropy loss (known as “permutation loss” in this paper)

Such a CNN-GNN-Sinkhorn-CrossEntropy framework has be adopted by many following papers.

PCA-GM is proposed in the conference version. In the journal version, we propose IPCA-GM, whereby the cross-graph convolution step is implemented in an iterative manner. The motivation of the iterative update scheme is that: better embedding features will lead to better cross-graph weight matrix and vice versa.

Benchmark Results

PascalVOC - 2GM

  • PCA-GM

    experiment config: experiments/vgg16_pca_voc.yaml

    pretrained model: google drive

  • IPCA-GM

    experiment config: experiments/vgg16_ipca_voc.yaml

    pretrained model: google drive

model

year

aero

bike

bird

boat

bottle

bus

car

cat

chair

cow

table

dog

horse

mbkie

person

plant

sheep

sofa

train

tv

mean

PCA-GM

2019

0.4979

0.6193

0.6531

0.5715

0.7882

0.7556

0.6466

0.6969

0.4164

0.6339

0.5073

0.6705

0.6671

0.6164

0.4447

0.8116

0.6782

0.5922

0.7845

0.9042

0.6478

IPCA-GM

2020

0.5378

0.6622

0.6714

0.6120

0.8039

0.7527

0.7255

0.7252

0.4455

0.6524

0.5430

0.6724

0.6790

0.6421

0.4793

0.8435

0.7079

0.6398

0.8380

0.9083

0.6770

Willow Object Class - 2GM

  • PCA-GM

    experiment config: experiments/vgg16_pca_willow.yaml

    pretrained model: google drive

  • IPCA-GM

    experiment config: experiments/vgg16_ipca_willow.yaml

    pretrained model: google drive

model

year

remark

Car

Duck

Face

Motorbike

Winebottle

mean

PCA-GM

2019

0.8760

0.8360

1.0000

0.7760

0.8840

0.8744

IPCA-GM

2020

0.9040

0.8860

1.0000

0.8300

0.8830

0.9006

SPair-71k - 2GM

  • PCA-GM

    experiment config: experiments/vgg16_pca_spair71k.yaml

    pretrained model: google drive

  • IPCA-GM

    experiment config: experiments/vgg16_ipca_spair71k.yaml

    pretrained model: google drive

model

year

aero

bike

bird

boat

bottle

bus

car

cat

chair

cow

dog

horse

mtbike

person

plant

sheep

train

tv

mean

PCA-GM

2019

0.6467

0.4571

0.7811

0.5128

0.6381

0.7272

0.6122

0.6278

0.6255

0.6822

0.5906

0.6115

0.6486

0.5773

0.8742

0.6042

0.7246

0.9283

0.6595

IPCA-GM

2020

0.6901

0.5286

0.8037

0.5425

0.6653

0.8001

0.6847

0.7136

0.6136

0.7479

0.6631

0.6514

0.6956

0.6391

0.9112

0.6540

0.8291

0.9750

0.7116

File Organization

├── affinity_layer.py
|   the implementation of affinity layer to compute the affinity matrix for PCA-GM and IPCA-GM
├── model.py
|   the implementation of training/evaluation procedures of PCA-GM and IPCA-GM
└── model_config.py
    the declaration of model hyperparameters

Credits and Citation

Please cite the following paper if you use this model in your research:

@inproceedings{WangICCV19,
  author = {Wang, Runzhong and Yan, Junchi and Yang, Xiaokang},
  title = {Learning Combinatorial Embedding Networks for Deep Graph Matching},
  booktitle = {IEEE International Conference on Computer Vision},
  pages={3056--3065},
  year = {2019}
}

CIE-H

Our implementation of the following paper:

  • Tianshu Yu, Runzhong Wang, Junchi Yan, Baoxin Li. “Learning deep graph matching with channel-independent embedding and Hungarian attention.” ICLR 2020.

    [paper]

CIE-H follows the CNN-GNN-metric-Sinkhorn pipeline proposed by PCA-GM, and it improves PCA-GM from two aspects: 1) A channel-independent edge embedding module for better graph feature extraction; 2) A Hungarian Attention module that dynamically constructs a structured and sparsely connected layer, taking into account the most contributing matching pairs as hard attention during training.

Benchmark Results

PascalVOC - 2GM

experiment config: experiments/vgg16_cie_voc.yaml

pretrained model: google drive

model

year

aero

bike

bird

boat

bottle

bus

car

cat

chair

cow

table

dog

horse

mbkie

person

plant

sheep

sofa

train

tv

mean

CIE-H

2020

0.5250

0.6858

0.7015

0.5706

0.8207

0.7700

0.7073

0.7313

0.4383

0.6994

0.6237

0.7018

0.7031

0.6641

0.4763

0.8525

0.7172

0.6400

0.8385

0.9168

0.6892

Willow Object Class - 2GM

experiment config: experiments/vgg16_cie_willow.yaml

pretrained model: google drive

model

year

remark

Car

Duck

Face

Motorbike

Winebottle

mean

CIE-H

2020

0.8581

0.8206

0.9994

0.8836

0.8871

0.8898

SPair-71k - 2GM

experiment config: experiments/vgg16_cie_spair71k.yaml

pretrained model: google drive

model

year

aero

bike

bird

boat

bottle

bus

car

cat

chair

cow

dog

horse

mtbike

person

plant

sheep

train

tv

mean

CIE-H

2020

0.7146

0.5710

0.8168

0.5672

0.6794

0.8246

0.7339

0.7449

0.6259

0.7804

0.6872

0.6626

0.7374

0.6604

0.9246

0.6717

0.8228

0.9751

0.7334

File Organization

├── model.py
|   the implementation of training/evaluation procedures of BBGM
└── model_config.py
    the declaration of model hyperparameters

some files are borrowed from models/PCA

Credits and Citation

Please cite the following paper if you use this model in your research:

@inproceedings{YuICLR20,
  title={Learning deep graph matching with channel-independent embedding and Hungarian attention},
  author={Yu, Tianshu and Wang, Runzhong and Yan, Junchi and Li, Baoxin},
  booktitle={International Conference on Learning Representations},
  year={2020}
}

NGM

Our implementation of the following paper:

  • Runzhong Wang, Junchi Yan, Xiaokang Yang. “Neural Graph Matching Network: Learning Lawler’s Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matching.” TPAMI 2021. [paper], [project page]

NGM proposes a learnable solver to the Lawler’s Quadratic Assignment Problem (Lawler’s QAP), which is the most general form of graph matching. The learning of Lawler’s QAP is achieved by firstly transforming the Lawler’s QAP to the so-called association graph, and solving Lawler’s QAP can be equivalently transformed into a vertex classification problem on the association graph. Finally, Graph Neural Networks are adopted to solve vertex classification problem as a common technique.

NGM has the following components:

  • (If images as the input) VGG16 CNN to extract image features

  • (If images as the input) Delaunay triangulation to build graphs

  • (If images as the input) Building affinity matrix efficiently via Factorized Graph Matching (FGM)

  • Solving the resulting Quadratic Assignment Problem (QAP) by the proposed Graph Neural Network solver

  • Supervised learning based on cross-entropy (also known as “permutation loss”)

We also show that such a general scheme can be extended to hyper-graph matching (by building a so-called association hypergraph) and multi-graph matching (by adding a spectral multi-matching head).

The first version of NGM/NHGM/NMGM is developed in 2019 with VGG16 CNN in line with GMN. We further develop an improved version NGM-v2/NHGM-v2/NMGM-v2 in 2021 by simply modifying the VGG16 to the improved backbone developed by BBGM.

To summarize, here we include the following models:

  • the original models developed in 2019:

    • NGM: two-graph matching/Lawler’s QAP solver with VGG16

    • NHGM: hyper-graph matching solver with VGG16

    • NMGM: multi-graph matching solver with VGG16

  • the improved v2 models developed in 2021:

    • NGM-v2: two-graph matching/Lawler’s QAP solver with VGG16+SplineConv

    • NHGM-v2: hyper-graph matching solver with VGG16+SplineConv

    • NMGM-v2: multi-graph matching solver with VGG16+SplineConv

Benchmark Results

PascalVOC - 2GM

  • NGM

    experiment config: experiments/vgg16_ngm_voc.yaml

    pretrained model: google drive

  • NHGM

    experiment config: experiments/vgg16_nhgm_voc.yaml

    pretrained model: google drive

  • NGM-v2

    experiment config: experiments/vgg16_ngmv2_voc.yaml

    pretrained model: google drive

  • NHGM-v2

    experiment config: experiments/vgg16_nhgmv2_voc.yaml

    pretrained model: google drive

Since NMGM does not support partial matching, we do not evaluate NMGM on Pascal VOC.

model

year

aero

bike

bird

boat

bottle

bus

car

cat

chair

cow

table

dog

horse

mbkie

person

plant

sheep

sofa

train

tv

mean

NGM

2019

0.5010

0.6350

0.5790

0.5340

0.7980

0.7710

0.7360

0.6820

0.4110

0.6640

0.4080

0.6030

0.6190

0.6350

0.4560

0.7710

0.6930

0.6550

0.7920

0.8820

0.6413

NHGM

2019

0.5240

0.6220

0.5830

0.5570

0.7870

0.7770

0.7440

0.7070

0.4200

0.6460

0.5380

0.6100

0.6190

0.6080

0.4680

0.7910

0.6680

0.5510

0.8090

0.8870

0.6458

NGM-v2

2021

0.6184

0.7118

0.7762

0.7875

0.8733

0.9363

0.8770

0.7977

0.5535

0.7781

0.8952

0.7880

0.8011

0.7923

0.6258

0.9771

0.7769

0.7574

0.9665

0.9323

0.8011

NHGM-v2

2021

0.5995

0.7154

0.7724

0.7902

0.8773

0.9457

0.8903

0.8181

0.5995

0.8129

0.8695

0.7811

0.7645

0.7750

0.6440

0.9872

0.7778

0.7538

0.9787

0.9280

0.8040

Willow Object Class - 2GM & MGM

  • NGM

    experiment config: experiments/vgg16_ngm_willow.yaml

    pretrained model: google drive

  • NHGM

    experiment config: experiments/vgg16_nhgm_willow.yaml

    pretrained model: google drive

  • NMGM

    experiment config: experiments/vgg16_nmgm_willow.yaml

    pretrained model: google drive

  • NGM-v2

    experiment config: experiments/vgg16_ngmv2_willow.yaml

    pretrained model: google drive

  • NHGM-v2

    experiment config: experiments/vgg16_nhgmv2_willow.yaml

    pretrained model: google drive

  • NMGM-v2

    experiment config: experiments/vgg16_nmgmv2_willow.yaml

    pretrained model: google drive

model

year

remark

Car

Duck

Face

Motorbike

Winebottle

mean

NGM

2019

0.8420

0.7760

0.9940

0.7680

0.8830

0.8530

NHGM

2019

0.8650

0.7220

0.9990

0.7930

0.8940

0.8550

NMGM

2019

0.7850

0.9210

1.0000

0.7870

0.9480

0.8880

NGM-v2

2021

0.9740

0.9340

1.0000

0.9860

0.9830

0.9754

NHGM-v2

2021

0.9740

0.9390

1.0000

0.9860

0.9890

0.9780

NMGM-v2

2021

0.9760

0.9447

1.0000

1.0000

0.9902

0.9822

SPair-71k - 2GM

  • NGM

    experiment config: experiments/vgg16_ngm_spair71k.yaml

    pretrained model: google drive

  • NGM-v2

    experiment config: experiments/vgg16_ngmv2_spair71k.yaml

    pretrained model: google drive

  • NHGM-v2

    experiment config: experiments/vgg16_nhgmv2_spair71k.yaml

    pretrained model: google drive

model

year

aero

bike

bird

boat

bottle

bus

car

cat

chair

cow

dog

horse

mtbike

person

plant

sheep

train

tv

mean

NGM

2019

0.6644

0.5262

0.7696

0.4960

0.6766

0.7878

0.6764

0.6827

0.5917

0.7364

0.6391

0.6066

0.7074

0.6089

0.8754

0.6387

0.7979

0.9150

0.6887

NGM-v2

2021

0.6877

0.6331

0.8677

0.7013

0.6971

0.9467

0.8740

0.7737

0.7205

0.8067

0.7426

0.7253

0.7946

0.7340

0.9888

0.8123

0.9426

0.9867

0.8020

NHGM-v2

2021

0.6202

0.5781

0.8642

0.6846

0.6872

0.9335

0.8081

0.7656

0.6919

0.7987

0.6623

0.7171

0.7812

0.6953

0.9824

0.8444

0.9316

0.9926

0.7799

Run QAPLIB Experiments

Our proposed NGM is capable of handling pure combinatorial optimization problems from QAPLIB. We train one model on the problems with the same prefix (which means that they represent the same category of problems), and we set the objective function as the loss, resulting in a self-supervised learning scheme. To further elevate the performance on QAPLIB, we adopt randomly sampling based on Gumbel Sinkhorn.

About the Performance

The quality of solutions of our method is comparative and even better compared with the classic learning-free optimization method Sinkhorn-JA, and the inference time is significantly reduced. For more details, please visit the project page.

Only the NGM Model is Considered for QAPLIB

Since NGM-v2 only improves in image feature extractor which is not relevant to QAPLIB problems, we only test NGM on QAPLIB. Besides, the QAPLIB instances are equivalent to the formulation of two-graph matching problems, thus the hyper-graph and multi-graph variants are not considered for QAPLIB.

How to Run

For experiments on QAPLIB, run

python train_eval_qap.py --config experiments/ngm_qaplib.yaml

and the QAPLIB dataset shall be automatically downloaded. By default, training is run on the first category (bur) and testing is run on all datasets. You may modify the TRAIN.CLASS parameter for different problems.

NOTICE: you may need a large GPU memory (up to 48GB in our experiment) to run NGM on QAPLIB instances up to 150. Adjust the two parameters MAX_TRAIN_SIZE, MAX_TEST_SIZE accordingly to fit the size of your GPU memory.

File Organization

├── geo_edge_feature.py
|   the implementation of used geometric features
├── gnn.py
|   the implementation of used graph neural networks
├── hypermodel.py
|   the implementation of training/evaluation procedures of NHGM
├── hypermodel_v2.py
|   the implementation of training/evaluation procedures of NHGMv2
├── mgmmodel.py
|   the implementation of training/evaluation procedures of NMGM
├── model.py
|   the implementation of training/evaluation procedures of NGM (can handle both graph matching and QAP)
├── model_config.py
|   the declaration of model hyperparameters
├── model_v2.py
|   the implementation of training/evaluation procedures of NGMv2 (can only handle graph matching)
├── model_v2_linsat.py
|   the implementation of training/evaluation procedures of NGMv2 combined with LinSATNet
└── model_v2_topk.py
    the implementation of training/evaluation procedures of NGMv2 combined with topk-GM algorithm and partial matching handling AFA modules

some layers are borrowed from models/BBGM

Credits and Citation

Please cite the following paper if you use this model in your research:

@article{WangPAMI21,
  author = {Wang, Runzhong and Yan, Junchi and Yang, Xiaokang},
  title = {Neural Graph Matching Network: Learning Lawler's Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matching},
  journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
  year={2021}
}

GANN

Our implementation of the following paper:

  • Runzhong Wang, Junchi Yan and Xiaokang Yang. “Graduated Assignment for Joint Multi-Graph Matching and Clustering with Application to Unsupervised Graph Matching Network Learning.” NeurIPS 2020. [paper]

  • Runzhong Wang, Junchi Yan and Xiaokang Yang. “Unsupervised Learning of Graph Matching with Mixture of Modes via Discrepancy Minimization.” TPAMI 2023. [paper][project page]

GANN proposes a self-supervised learning framework by leveraging graph matching solvers to provide pseudo labels to train the neural network module in deep graph matching pipeline. We propose a general graph matching solver for various graph matching settings based on the classic Graduated Assignment (GA) algorithm.

The variants on three different graph matching settings are denoted by different suffixes:

  • GANN-2GM: self-supervised learning graduated assignment neural network for two-grpah matching

  • GANN-MGM: self-supervised learning graduated assignment neural network for multi-grpah matching

  • GANN-MGM3: self-supervised learning graduated assignment neural network for multi-graph matching with a mixture of modes (this setting is also known as multi-graph matching and clustering in the NeurIPS paper)

GANN-MGM notably surpass supervised learning methods on the relatively small dataset Willow Object Class.

Benchmark Results

Willow Object Class - MGM

experiment config: experiments/vgg16_gann-mgm_willow.yaml

pretrained model: google drive

model

year

remark

Car

Duck

Face

Motorbike

Winebottle

mean

GANN-MGM

2020

self-supervised

0.9600

0.9642

1.0000

1.0000

0.9879

0.9906

File Organization

├── graduated_assignment.py
|   the implementation of the graduated assignment algorithm covering all scenarios
├── model.py
|   the implementation of training/evaluation procedures of GANN-GM/MGM/MGM3
└── model_config.py
    the declaration of model hyperparameters

Credits and Citation

Please cite the following papers if you use this model in your research:

@inproceedings{WangNeurIPS20,
  author = {Runzhong Wang and Junchi Yan and Xiaokang Yang},
  title = {Graduated Assignment for Joint Multi-Graph Matching and Clustering with Application to Unsupervised Graph Matching Network Learning},
  booktitle = {Neural Information Processing Systems},
  year = {2020}
}

@article{WangPAMI23,
  title={Unsupervised Learning of Graph Matching With Mixture of Modes Via Discrepancy Minimization},
  author={Wang, Runzhong and Yan, Junchi and Yang, Xiaokang},
  journal={IEEE Transactions of Pattern Analysis and Machine Intelligence},
  year={2023}
}

BBGM

Our implementation of the following paper:

  • Michal Rolínek, Paul Swoboda, Dominik Zietlow, Anselm Paulus, Vít Musil, Georg Martius. “Deep Graph Matching via Blackbox Differentiation of Combinatorial Solvers.” ECCV 2020.

    [paper]

BBGM proposes a new feature extractor by using the global feature of VGG16 and a Spline Convolution module, and such an improved backbone is found effective for image matching problems. NOTE: Spline convolution is officially named as SplineCNN, however, since the term “CNN” is conventionally used for image feature extractors, and SplineCNN works on graphs, here we name it as “Spline Convolution” for disambiguation.

The resulting quadratic assignment problem is solved by a discrete LPMP solver, and the gradient is approximated by the black-box combinatorial solver technique.

Benchmark Results

PascalVOC - 2GM

experiment config: experiments/vgg16_bbgm_voc.yaml

pretrained model: google drive

model

year

aero

bike

bird

boat

bottle

bus

car

cat

chair

cow

table

dog

horse

mbkie

person

plant

sheep

sofa

train

tv

mean

BBGM

2020

0.6187

0.7106

0.7969

0.7896

0.8740

0.9401

0.8947

0.8022

0.5676

0.7914

0.6458

0.7892

0.7615

0.7512

0.6519

0.9818

0.7729

0.7701

0.9494

0.9393

0.7899

Willow Object Class - 2GM & MGM

experiment config: experiments/vgg16_bbgm_willow.yaml

pretrained model: google drive

model

year

remark

Car

Duck

Face

Motorbike

Winebottle

mean

BBGM

2020

0.9680

0.8990

1.0000

0.9980

0.9940

0.9718

SPair-71k - 2GM

experiment config: experiments/vgg16_bbgm_spair71k.yaml

pretrained model: google drive

model

year

aero

bike

bird

boat

bottle

bus

car

cat

chair

cow

dog

horse

mtbike

person

plant

sheep

train

tv

mean

BBGM

2020

0.7250

0.6455

0.8780

0.7581

0.6927

0.9395

0.8859

0.7992

0.7456

0.8315

0.7878

0.7710

0.7650

0.7634

0.9820

0.8554

0.9678

0.9931

0.8215

File Organization

├── affinity_layer.py
|   the implementation of the inner-product with weight affinity layer proposed by BBGM
├── model.py
|   the implementation of training/evaluation procedures of BBGM
├── model_config.py
|   the declaration of model hyperparameters
└── sconv_archs.py
    the implementation of spline convolution (SpilneCNN) operations

Remarks

It is worth noting that our reproduced result of BBGM is different from the result from their paper. By looking into the code released by BBGM, we find that the authors of BBGM filter out keypoints which are out of the bounding box but we do not. Therefore, the number of nodes of graphs in BBGM is smaller than ours, and the graph matching problem is less challenging than ours. In this repository, we modify BBGM to fit into our setting, and we report our reproduced result for fair comparison.

Credits and Citation

This code is developed based on the official implementation of BBGM. The code is modified to fit our general framework.

Please cite the following paper if you use this model in your research:

@inproceedings{RolinekECCV20,
  title={Deep Graph Matching via Blackbox Differentiation of Combinatorial Solvers},
  author={Rol{\'\i}nek, Michal and Swoboda, Paul and Zietlow, Dominik and Paulus, Anselm and Musil, V{\'\i}t and Martius, Georg},
  booktitle={European Conference on Computer Vision},
  pages={407--424},
  year={2020},
  organization={Springer}
}

GCAN

Our implementation of the following paper:

  • Zheheng Jiang, Hossein Rahmani, Plamen Angelov, Sue Black, Bryan M. Williams. “Graph-Context Attention Networks for Size-Varied Deep Graph Matching.” CVPR 2022.

    [paper]

GCAN proposes a deep graph matching pipeline to solve size-varied GM problem. It learns both node-level and graph-level matching. It proposes to combine the following components to formulate the GM pipeline:

  • VGG16 CNN to extract image features

  • Positional encoding and Graph-context attention (GCA) module to extract node features

  • Solving node correspondence via Integer Linear Programming (ILP) attention loss

  • Learning graph-level matching via margin-based pairwise loss

Benchmark Results

IMC-PT-SparseGM-50 - 2GM (unfiltered)

experiment config: experiments/vgg16_gcan_imcpt_50.yaml

pretrained model: google drive

model

year

reichstag

sacre coeur

st peters square

mean

GCAN

2022

0.872

0.551

0.630

0.684

IMC-PT-SparseGM-100 - 2GM (unfiltered)

experiment config: experiments/vgg16_gcan_imcpt_100.yaml

pretrained model: google drive

model

year

reichstag

sacre coeur

st peters square

mean

GCAN

2022

0.804

0.557

0.728

0.696

File Organization

├── cross_attention_layer.py
|   the implementation of cross-attention layer used in GCA module
├── GCA_module.py
|   the implementation of GCA module
├── GCAN_model.py
|   the implementation of training/evaluation procedures of GCAN
├── GCAN_model_topk.py
|   the implementation of training/evaluation procedures of GCAN combined with topk-GM algorithm and partial matching handling AFA modules
├── model_config.py
|   the declaration of model hyperparameters
├── positional_encoding_layer.py
|   the implementation of positional encoding
└── self_attention_layer.py
    the implementation of self-attention layer used in GCA module

Credits and Citation

Please cite the following paper if you use this model in your research:

@InProceedings{JiangCVPR22,
    author={Jiang, Zheheng and Rahmani, Hossein and Angelov, Plamen and Black, Sue and Williams, Bryan M.},
    title={Graph-Context Attention Networks for Size-Varied Deep Graph Matching},
    booktitle={Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)},
    year={2022},
}

AFAT

Our implementation of the following paper:

  • Runzhong Wang, Ziao Guo, Shaofei Jiang, Xiaokang Yang, Junchi Yan. “Deep Learning of Partial Graph Matching via Differentiable Top-K.” CVPR 2023. [paper]

AFAT is a partial matching handling approach, used to resolve partial graph matching problem, i.e., graph matching with the existence of outliers. It includes a topk-GM algorithm to suppress matchings with low confidence, and two AFA modules to predict the number of inliers k. The implementation of topk-GM algorithm and AFA modules is shown in models.AFAT.sinkhorn_topk.py and models.AFAT.k_pred_net.py respectively.

AFAT has the following components:

  • An Optimal Transport (OT) layer utilizing Sinkhorn algorithm with marginal distributions to resolve topk selection problem

  • AFA-U (unified bipartite graph modeling) module to predict the number of inliers k

  • AFA-I (individual graph modeling) module to predict the number of inliers k

  • Greedy-topk algorithm to select matches with topk confidences

We also show that such a general scheme can be readily plugged into SOTA deep graph matching pipelines. We adopt quadratic matching network NGMv2 as the backend graph matching network, and the file models.NGM.model_v2_topk.py can be referred to for details. We also choose linear matching network GCAN as the backend graph matching network, and the file models.GCAN.GCAN_model_topk.py can be referred to for details.

Benchmark Results

PascalVOC - 2GM (unfiltered)

  • NGMv2-AFAT-U

    experiment config: experiments/ngmv2-afat/vgg16_ngmv2-afat-u_voc_stage1.yaml, experiments/ngmv2-afat/vgg16_ngmv2-afat-u_voc_stage2.yaml, experiments/ngmv2-afat/vgg16_ngmv2-afat-u_voc_stage3.yaml

    pretrained model: google drive

  • NGMv2-AFAT-I

    experiment config: experiments/ngmv2-afat/vgg16_ngmv2-afat-i_voc_stage1.yaml, experiments/ngmv2-afat/vgg16_ngmv2-afat-i_voc_stage2.yaml, experiments/ngmv2-afat/vgg16_ngmv2-afat-i_voc_stage3.yaml

    pretrained model: google drive

  • GCAN-AFAT-U

    experiment config: experiments/gcan-afat/vgg16_gcan-afat-u_voc_stage1.yaml, experiments/gcan-afat/vgg16_gcan-afat-u_voc_stage2.yaml, experiments/gcan-afat/vgg16_gcan-afat-u_voc_stage3.yaml

    pretrained model: google drive

  • GCAN-AFAT-I

    experiment config: experiments/gcan-afat/vgg16_gcan-afat-i_voc_stage1.yaml, experiments/gcan-afat/vgg16_gcan-afat-i_voc_stage2.yaml, experiments/gcan-afat/vgg16_gcan-afat-i_voc_stage3.yaml

    pretrained model: google drive

model

year

aero

bike

bird

boat

bottle

bus

car

cat

chair

cow

table

dog

horse

mbkie

person

plant

sheep

sofa

train

tv

mean

NGMv2-AFAT-U

2023

0.457

0.677

0.573

0.449

0.901

0.655

0.499

0.593

0.440

0.620

0.549

0.584

0.586

0.638

0.459

0.948

0.509

0.373

0.742

0.828

0.602

NGMv2-AFAT-I

2023

0.450

0.673

0.559

0.456

0.903

0.646

0.487

0.580

0.447

0.602

0.548

0.572

0.575

0.634

0.452

0.953

0.493

0.416

0.736

0.824

0.599

GCAN-AFAT-U

2023

0.471

0.708

0.581

0.458

0.908

0.665

0.496

0.588

0.506

0.646

0.472

0.605

0.623

0.657

0.463

0.954

0.527

0.474

0.742

0.838

0.620

GCAN-AFAT-I

2023

0.461

0.699

0.561

0.466

0.907

0.661

0.481

0.579

0.499

0.639

0.504

0.590

0.616

0.650

0.447

0.955

0.509

0.492

0.740

0.838

0.616

Willow Object Class - 2GM & MGM

  • NGMv2-AFAT-U

    experiment config: experiments/ngmv2-afat/vgg16_ngmv2-afat-u_willow_stage1.yaml, experiments/ngmv2-afat/vgg16_ngmv2-afat-u_willow_stage2.yaml, experiments/ngmv2-afat/vgg16_ngmv2-afat-u_willow_stage3.yaml

    pretrained model: google drive

  • NGMv2-AFAT-I

    experiment config: experiments/ngmv2-afat/vgg16_ngmv2-afat-i_willow_stage1.yaml, experiments/ngmv2-afat/vgg16_ngmv2-afat-i_willow_stage2.yaml, experiments/ngmv2-afat/vgg16_ngmv2-afat-i_willow_stage3.yaml

    pretrained model: google drive

  • GCAN-AFAT-U

    experiment config: experiments/gcan-afat/vgg16_gcan-afat-u_willow_stage1.yaml, experiments/gcan-afat/vgg16_gcan-afat-u_willow_stage2.yaml, experiments/gcan-afat/vgg16_gcan-afat-u_willow_stage3.yaml

    pretrained model: google drive

  • GCAN-AFAT-I

    experiment config: experiments/gcan-afat/vgg16_gcan-afat-i_willow_stage1.yaml, experiments/gcan-afat/vgg16_gcan-afat-i_willow_stage2.yaml, experiments/gcan-afat/vgg16_gcan-afat-i_willow_stage3.yaml

    pretrained model: google drive

model

year

Car

Duck

Face

Motorbike

Winebottle

mean

NGMv2-AFAT-U

2023

0.826

0.745

0.906

0.739

0.870

0.817

NGMv2-AFAT-I

2023

0.846

0.757

0.920

0.745

0.886

0.831

GCAN-AFAT-U

2023

0.801

0.780

0.906

0.760

0.870

0.823

GCAN-AFAT-I

2023

0.822

0.777

0.927

0.772

0.886

0.837

SPair-71k - 2GM (unfiltered)

  • NGMv2-AFAT-U

    experiment config: experiments/ngmv2-afat/vgg16_ngmv2-afat-u_spair71k_stage1.yaml, experiments/ngmv2-afat/vgg16_ngmv2-afat-u_spair71k_stage2.yaml, experiments/ngmv2-afat/vgg16_ngmv2-afat-u_spair71k_stage3.yaml

    pretrained model: google drive

  • NGMv2-AFAT-I

    experiment config: experiments/ngmv2-afat/vgg16_ngmv2-afat-i_spair71k_stage1.yaml, experiments/ngmv2-afat/vgg16_ngmv2-afat-i_spair71k_stage2.yaml, experiments/ngmv2-afat/vgg16_ngmv2-afat-i_spair71k_stage3.yaml

    pretrained model: google drive

  • GCAN-AFAT-U

    experiment config: experiments/gcan-afat/vgg16_gcan-afat-u_spair71k_stage1.yaml, experiments/gcan-afat/vgg16_gcan-afat-u_spair71k_stage2.yaml, experiments/gcan-afat/vgg16_gcan-afat-u_spair71k_stage3.yaml

    pretrained model: google drive

  • GCAN-AFAT-I

    experiment config: experiments/gcan-afat/vgg16_gcan-afat-i_spair71k_stage1.yaml, experiments/gcan-afat/vgg16_gcan-afat-i_spair71k_stage2.yaml, experiments/gcan-afat/vgg16_gcan-afat-i_spair71k_stage3.yaml

    pretrained model: google drive

model

year

aero

bike

bird

boat

bottle

bus

car

cat

chair

cow

dog

horse

mtbike

person

plant

sheep

train

tv

mean

NGMv2-AFAT-U

2023

0.503

0.435

0.638

0.324

0.590

0.601

0.397

0.686

0.361

0.636

0.565

0.463

0.514

0.433

0.770

0.512

0.811

0.894

0.563

NGMv2-AFAT-I

2023

0.504

0.436

0.639

0.321

0.612

0.585

0.380

0.684

0.357

0.627

0.564

0.477

0.519

0.443

0.785

0.507

0.792

0.912

0.564

GCAN-AFAT-U

2023

0.467

0.433

0.658

0.333

0.615

0.549

0.352

0.684

0.377

0.599

0.560

0.476

0.472

0.435

0.803

0.477

0.838

0.890

0.557

GCAN-AFAT-I

2023

0.468

0.443

0.659

0.324

0.615

0.538

0.337

0.684

0.381

0.601

0.563

0.479

0.483

0.438

0.812

0.484

0.829

0.880

0.557

IMC-PT-SparseGM-50 - 2GM (unfiltered)

  • NGMv2-AFAT-U

    experiment config: experiments/ngmv2-afat/vgg16_ngmv2-afat-u_imcpt_50_stage1.yaml, experiments/ngmv2-afat/vgg16_ngmv2-afat-u_imcpt_50_stage2.yaml, experiments/ngmv2-afat/vgg16_ngmv2-afat-u_imcpt_50_stage3.yaml

    pretrained model: google drive

  • NGMv2-AFAT-I

    experiment config: experiments/ngmv2-afat/vgg16_ngmv2-afat-i_imcpt_50_stage1.yaml, experiments/ngmv2-afat/vgg16_ngmv2-afat-i_imcpt_50_stage2.yaml, experiments/ngmv2-afat/vgg16_ngmv2-afat-i_imcpt_50_stage3.yaml

    pretrained model: google drive

  • GCAN-AFAT-U

    experiment config: experiments/gcan-afat/vgg16_gcan-afat-u_imcpt_50_stage1.yaml, experiments/gcan-afat/vgg16_gcan-afat-u_imcpt_50_stage2.yaml, experiments/gcan-afat/vgg16_gcan-afat-u_imcpt_50_stage3.yaml

    pretrained model: google drive

  • GCAN-AFAT-I

    experiment config: experiments/gcan-afat/vgg16_gcan-afat-i_imcpt_50_stage1.yaml, experiments/gcan-afat/vgg16_gcan-afat-i_imcpt_50_stage2.yaml, experiments/gcan-afat/vgg16_gcan-afat-i_imcpt_50_stage3.yaml

    pretrained model: google drive

model

year

reichstag

sacre coeur

st peters square

mean

NGMv2-AFAT-U

2023

0.905

0.587

0.669

0.720

NGMv2-AFAT-I

2023

0.923

0.587

0.667

0.728

GCAN-AFAT-U

2023

0.869

0.594

0.671

0.711

GCAN-AFAT-I

2023

0.910

0.603

0.673

0.729

IMC-PT-SparseGM-100 - 2GM (unfiltered)

  • NGMv2-AFAT-U

    experiment config: experiments/ngmv2-afat/vgg16_ngmv2-afat-u_imcpt_100_stage1.yaml, experiments/ngmv2-afat/vgg16_ngmv2-afat-u_imcpt_100_stage2.yaml, experiments/ngmv2-afat/vgg16_ngmv2-afat-u_imcpt_100_stage3.yaml

    pretrained model: google drive

  • NGMv2-AFAT-I

    experiment config: experiments/ngmv2-afat/vgg16_ngmv2-afat-i_imcpt_100_stage1.yaml, experiments/ngmv2-afat/vgg16_ngmv2-afat-i_imcpt_100_stage2.yaml, experiments/ngmv2-afat/vgg16_ngmv2-afat-i_imcpt_100_stage3.yaml

    pretrained model: google drive

  • GCAN-AFAT-U

    experiment config: experiments/gcan-afat/vgg16_gcan-afat-u_imcpt_100_stage1.yaml, experiments/gcan-afat/vgg16_gcan-afat-u_imcpt_100_stage2.yaml, experiments/gcan-afat/vgg16_gcan-afat-u_imcpt_100_stage3.yaml

    pretrained model: google drive

  • GCAN-AFAT-I

    experiment config: experiments/gcan-afat/vgg16_gcan-afat-i_imcpt_100_stage1.yaml, experiments/gcan-afat/vgg16_gcan-afat-i_imcpt_100_stage2.yaml, experiments/gcan-afat/vgg16_gcan-afat-i_imcpt_100_stage3.yaml

    pretrained model: google drive

model

year

reichstag

sacre coeur

st peters square

mean

NGMv2-AFAT-U

2023

0.817

0.570

0.722

0.703

NGMv2-AFAT-I

2023

0.820

0.570

0.714

0.701

GCAN-AFAT-U

2023

0.826

0.582

0.738

0.715

GCAN-AFAT-I

2023

0.827

0.578

0.724

0.709

File Organization

├── k_pred_net.py
|   the implementation of AFA-I and AFA-U modules
└── sinkhorn_topk.py
    the implementation of topk-GM algorithm and greedy-topk algorithm

Credits and Citation

Please cite the following paper if you use this model in your research:

@InProceedings{WangCVPR23,
    author={Wang, Runzhong and Guo, Ziao and Jiang, Shaofei and Yang, Xiaokang and Yan, Junchi},
    title={Deep Learning of Partial Graph Matching via Differentiable Top-K},
    booktitle={Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)},
    year={2023},
}

LinSAT

Our implementation of the following paper:

  • Runzhong Wang, Yunhao Zhang, Ziao Guo, Tianyi Chen, Xiaokang Yang, Junchi Yan. “LinSATNet: The Positive Linear Satisfiability Neural Networks.” ICML 2023. [paper]

LinSAT aims at encoding constraints into neural networks, through projecting input variables with non-negative constraints turough a differentiable satisfiability layer based on an extension of the classic Sinkhorn algorithm involving jointly encoding multiple sets of marginal distributions.

The partial graph matching problem and the permutation constraints can also be explicitly formulated and resolved via LinSAT.

We choose NGMv2 as the backend graph matching network, and the file models.NGM.model_v2_linsat.py can be referred to for details.

LinSAT has been uploaded to PyPI and you can simply install the package by

$ pip install linsatnet

and import the LinSAT layer by adding from LinSATNet import linsat_layer in your code.

Note that LinSAT is capable of encoding non-negative constraints. You can adopt LinSAT to solve your own problem by devising the problem constraints.

Benchmark Results

PascalVOC - 2GM (unfiltered)

  • NGMv2-LinSAT

    experiment config: experiments/vgg16_ngmv2_linsat_voc-all.yaml

model

year

aero

bike

bird

boat

bottle

bus

car

cat

chair

cow

table

dog

horse

mbkie

person

plant

sheep

sofa

train

tv

mean

NGMv2-LinSAT

2023

0.4547

0.6489

0.5857

0.4915

0.8628

0.6631

0.6079

0.6230

0.4467

0.6121

0.4867

0.6254

0.5974

0.6338

0.4791

0.9253

0.5473

0.3542

0.7674

0.8120

0.6112

Note: In this experiment, we assume that the number of matches k is given, and we only retain k matches during inference. Therefore, it is not fair to compare the above empirical result with that of other partial GM approaches.

Credits and Citation

Please cite the following paper if you use this model in your research:

@InProceedings{WangICML23,
   title={LinSATNet: The Positive Linear Satisfiability Neural Networks},
   author={Runzhong Wang, Yunhao Zhang, Ziao Guo, Tianyi Chen, Xiaokang Yang, Junchi Yan},
   booktitle={ICML},
   year={2023}
}