Solving Partial Assignment Problems using Random Clique Complexes

Charu Sharma, Deepak Nathani, Manohar Kaul
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:4586-4595, 2018.

Abstract

We present an alternate formulation of the partial assignment problem as matching random clique complexes, that are higher-order analogues of random graphs, designed to provide a set of invariants that better detect higher-order structure. The proposed method creates random clique adjacency matrices for each k-skeleton of the random clique complexes and matches them, taking into account each point as the affine combination of its geometric neighborhood. We justify our solution theoretically, by analyzing the runtime and storage complexity of our algorithm along with the asymptotic behavior of the quadratic assignment problem (QAP) that is associated with the underlying random clique adjacency matrices. Experiments on both synthetic and real-world datasets, containing severe occlusions and distortions, provide insight into the accuracy, efficiency, and robustness of our approach. We outperform diverse matching algorithms by a significant margin.

Cite this Paper

BibTeX
@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}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/sharma18a/sharma18a.pdf}, url = {https://proceedings.mlr.press/v80/sharma18a.html}, abstract = {We present an alternate formulation of the partial assignment problem as matching random clique complexes, that are higher-order analogues of random graphs, designed to provide a set of invariants that better detect higher-order structure. The proposed method creates random clique adjacency matrices for each k-skeleton of the random clique complexes and matches them, taking into account each point as the affine combination of its geometric neighborhood. We justify our solution theoretically, by analyzing the runtime and storage complexity of our algorithm along with the asymptotic behavior of the quadratic assignment problem (QAP) that is associated with the underlying random clique adjacency matrices. Experiments on both synthetic and real-world datasets, containing severe occlusions and distortions, provide insight into the accuracy, efficiency, and robustness of our approach. We outperform diverse matching algorithms by a significant margin.} }
Endnote
%0 Conference Paper %T Solving Partial Assignment Problems using Random Clique Complexes %A Charu Sharma %A Deepak Nathani %A Manohar Kaul %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-sharma18a %I PMLR %P 4586--4595 %U https://proceedings.mlr.press/v80/sharma18a.html %V 80 %X We present an alternate formulation of the partial assignment problem as matching random clique complexes, that are higher-order analogues of random graphs, designed to provide a set of invariants that better detect higher-order structure. The proposed method creates random clique adjacency matrices for each k-skeleton of the random clique complexes and matches them, taking into account each point as the affine combination of its geometric neighborhood. We justify our solution theoretically, by analyzing the runtime and storage complexity of our algorithm along with the asymptotic behavior of the quadratic assignment problem (QAP) that is associated with the underlying random clique adjacency matrices. Experiments on both synthetic and real-world datasets, containing severe occlusions and distortions, provide insight into the accuracy, efficiency, and robustness of our approach. We outperform diverse matching algorithms by a significant margin.
APA
Sharma, C., Nathani, D. & Kaul, M.. (2018). Solving Partial Assignment Problems using Random Clique Complexes. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:4586-4595 Available from https://proceedings.mlr.press/v80/sharma18a.html.

Related Material