Matching Large Feature Sets based on Hypergraph Models and Structurally Adaptive CUR Decompositions of Compatibility Tensors

Project: Research

View graph of relations


In many data analysis tasks, we need to match two sets of features. For example, in a content-based image search, we match object features in the source and target images. To predict whether two biomolecules will interact with each other, we can study surface curvature and charge distributions of the molecules and match these features. Given two sets of features, we can match them with different orders. When matching at order r, we consider the compatibility or affinity between r features from the source and r features from the target. Then we solve a problem of graph or hypergraph matching. In general, higher-order methods using hypergraph models are more robust for noisy data. However, the size of the compatibility tensor grows exponentially as the matching order r increases. This complexity makes it prohibitive to deal with large feature sets in terms of computer memory and computing time. This project will develop a novel method for hypergraph matching with large sets of features based on adaptive CUR decomposition. Our strategy is to consider the data redundancy of the compatibility tensor, which has a low rank, and we can explore this property to perform more efficient matching. In the CUR decomposition, we can eliminate redundancies and only retain a small number of column, row, and tube fibers, for example, in a third-order tensor, so that the computer memory and computing time requirements can be reduced significantly. We will investigate how to compute adaptive CUR decomposition of tensors to ensure a high matching accuracy. The structural and relational properties of the feature sets will be considered so that we can choose vertex pairs and hyperedges in the source and target hypergraphs effectively. Graph wavelets will be used to compute the compatibility coefficients. Efficient algorithms will be studied for fast updates of CUR decomposition if we need to add or remove hyperedges. Robust methods will be developed to deal with noisy and distorted features. A significant advantage of our approach over the commonly used singular value decomposition (SVD) based technique is that we deal with the compatibility coefficients directly with CUR decomposition in the matching process. In addition to scientific contributions to hypergraph models, tensor theories, and novel data matching methods, our research will find many practical applications. It will deliver powerful computational tools for image analysis, computer vision, and biomolecular modeling. 


Project number9043140
Grant typeGRF
Effective start/end date1/01/22 → …