This repo contains matlab files for implementing the permutation synchronization solver of the following paper Robust Multi-object Matching via Iterative Reweighting of the Graph Connection Laplacian. Yunpeng Shi, Shaohan Li, Gilad Lerman. NeurIPS 2020.
IRGCL often outperforms other spectral/SDP permutation synchronization methods. The following figure compares the estimation errors of different algorithms under uniform corruption model.
Put all the files in the same directory and run demo_IRGCL.m. It calls functions Uniform_Topology.m or Nonuniform_Topology.m for generating the data that follow various corruption models. Then it calls function IRGCL.m to solve permutation synchronization. See comments in the begining of each function for details.
We provide 6 different corruption models. 4 for nonuniform topology and 2 for uniform toplogy. Uniform/Nonuniform toplogy refers to whether the corrupted subgraph is Erdos Renyi or not. In other words, the choice of Uniform/Nonuniform toplogy decides how to select edges for corruption. In Uniform_Topology.m, two nodes are connected with probability p. Then edges are independently drawn with probability q for corruption. In Nonuniform_Topology.m, two nodes are connected with probability p. Then with probability p_node_crpt a node is selected so that its neighboring edges will be corrupted. Next, for each selected node, with probability p_edge_crpt an edge (among the neighboring edges of the selected node) is corrupted.
The argument crpt_type in the two functions determines how the corrupted relative permutations are generated for those selected edges. In Uniform_Topology.m, there are 2 options of crpt_type: uniform and self-consistent.
In Nonuniform_Topology.m, there are the following 4 options of crpt_type.
uniform: The corrupted relative permutations are i.i.d follows uniform distribution over the space of permutation group.
self-consistent: The corrupted are relative permutations of another set of absolute permutations. Namely
where those absolute permutations are different from the ground truth and are i.i.d drawn from the uniform distribution in the space of permutation group.
local-biased: Self-consistent corruption with additional sampling rejection procedure so that the expectation of relative permutations deviates away from the ground truth.
local-adv: Extremely malicious corruption that replaces the underlying absolute pemutations from ground truth to
. Namely
. Additional high noise is added to the corruption, otherwise the recovery of the ground truth can be ill-posed.