Graph Matching: Partial Assignment Problem using Random Clique Complexes
Overview
The matching problem finds the assignment between two finite sets U and V, each of cardinality n, such that the total cost of all matched pairs is minimized. The assignment problem can also be generalized to finding matchings between more than two sets. This is a fundamental problem in computer science and has been motivated by a wide gamut of research areas spanning diverse areas such as structural biology, protein structure comparisons in bioinformatics, and computer vision. Computer vision especially boasts a broad range of applications that include object matching, image registration, stereo matching, shape matching, structure from motion (SfM), and object detection, etc.
Matching problem can be posed as a Graph Matching Problem where each graph’s nodes represent the objects and the edges encode their corresponding connection and/or distances. Thus, the goal is to find Inexact graph matching.
We present an alternate formulation of the partial assignment problem as matching random clique complexes, that are higher-order analogues of random graphs in our ICML 2018 paper titled “Solving Partial Assignment Problems using Random Clique Complexes”. The code of this work is provided here.
Quadratic Assignment Problem
A set of n facilities has to be allocated to a set of n locations. We are given two n × n input matrices F = (f_ij) and D = (d_kl), where f_ij is the flow between facilities i and j and d_kl is the distance between locations k and l. Each product (f_ij).(d_φ(i)φ(j)) represents the flow between facilities i and j multiplied by their distance when facility i is assigned to location φ(i) and facility j is assigned to location φ(j). The objective is to assign each facility to a location such that the total cost is minimized. Formally, the objective function (Koopmans-Beckmann version) is as follows:
Using permutation matrices X = (x_ij) instead of permutations, the QAP can be formulated as the following integer program with quadratic objective function
Challenges
The existing graph matching methods perform poorly when faced with non-similar geometric transformations and when some vertices and/or edges are missing due to occlusions in data. In addition to this, information which can be taken into consideration in higher-order groupings are ignored. This calls for more robust matching methods!
Our Method
Construction of a Random Clique Complex (RCC)
- Let G(n,p) be an Erdős-Rényi graph with a set of n vertices denoted by V, whose edges {v,v’} ∈ C(V,2), are i.i.d Bernoulli(p) distributed.
- Recall, that a k-clique in G(n,p) is a complete subgraph that comprises of k vertices and C(k,2) edges.
- we define our random clique complex χ(G) as the set of all cliques in G such that χ(G) = { σ ∈ [n] |σ is a clique of G }. We denote a set of (k+1)-cliques as χ_k(G).
- The k-skeleton of χ(G), for k ∈ ℕ, is defined as the following quotient space
where ~ is the equivalence relation that identifies faces of σ^(k) to the corresponding faces of σ ∈ χ^(j)(G) where j<k. Finally, χ(G)= ⋃ χ^(k)(G) in which k ranges from 0 to ∞.
k-Skeleton as an adjacency matrix
We represent k-skeleton χ^(k)(G) as an adjacency matrix G^(k,l) whose vertex set is the set of of all (k+1)- cliques in G and in which two vertices (i.e., (k+1)-cliques) are adjacent when they share a common face that has a minimum of l vertices, where k ≥ 1 and 1 ≤ l ≤ k. Such an adjacency matrix is built for each k-skeleton and therefore χ(G) is expressed as a set of matrices {G^(k,l)} in which k ranges from 0 to h, where (k+1) is the dimension of the cliques.
Constrained Quadratic Assignment Problem
Given two h-dimensional random clique complexes χ(G) = {G^(k,l)} and χ(G’) = {G’^(k,l)}, where k ranges from 0 to h, let X={X_0,…, X_h} ∈ Π be a set of permutation matrices such that X_k encodes assignments / matchings from G^(k,l) to G’^(k,l). The combinatorial matching requires the optimal set of permutation matrices that best align χ(G) and χ(G’). More formally, this can be expressed as the following constrained optimization problem
Example
We consider two random graphs G_1 and G_2 with 6 vertices for which we perform higher-order matching from 3-cliques to 1-cliques. For a higher-order matching, we take the neighbourhood of a barycenter of a clique as the barycenters of the other cliques it is connected to. Thus, we place additional nodes of different order in the neighbourhood of each clique in addition to the same order cliques. This information would help the cliques to have more accurate matches.
- Clique Complexes
2. Barycentric Coordinates of Cliques
3. Neighbourhood of 3-Clique
4. Matching 3-Cliques
5. Matching 2-Cliques
6. Matching 1-Cliques
Difficult Datasets
Linear Transformation
We perform affine transformations on CMU House, which is a sequence of N frames extracted from a video. More specifically, we uniformly sample frames (at 20% and 40%) and perform affine transformations (Rotation, Reflection, Shear and Scale) on the selected frames to distort them.
Non-Liner Transformation
For non-affine transformation, we consider two datasets. Please note that non-affine transformation is non-preserving. Images from Magazine dataset is shown below:
Partial Assignment
Partial assignment implies that only subsets of U and V can actually be assigned to each other successfully. This phenomenon is of particular interest to applications where either objects are absent due to incomplete observations, undergo deformations, and/or the objects in question cannot clearly be disambiguated because the objects in question along with their related objects are embedded in clutter.
Implementation
The code for our paper is provided in this github repository. Following are the steps to reproduce the results:
- Clone the repository and set up the MATLAB environment.
git clone https://github.com/charusharma1991/RandomCliqueComplexes_ICML2018.git2. To run the matching model to generate results for “House” dataset for pairwise matching of 111 images, run:
main.mCitation
Please cite the paper if you use this code.
@InProceedings{pmlr-v80-sharma18a,
title = {Solving Partial Assignment Problems using Random Clique Complexes},
author = {Sharma, Charu and Nathani, Deepak and Kaul, Manohar},
booktitle = {Proceedings of the 35th International Conference on Machine Learning},
pages = {4586--4595},
year = {2018},
editor = {Dy, Jennifer and Krause, Andreas},
volume = {80},
series = {Proceedings of Machine Learning Research},
address = {Stockholmsmässan, Stockholm Sweden},
month = {10--15 Jul},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v80/sharma18a/sharma18a.pdf},
url = {http://proceedings.mlr.press/v80/sharma18a.html}
}Thanks for reading this article. For any query or suggestions, please write to charusharma1991@gmail.com.