More Like this

1. Random Graph Matching with Improved Noise Robustness

   Mao, Cheng; Rudelson, Mark; Tikhomirov, Konstantin (August 2021, Proceedings of Machine Learning Research)

   Belkin, Mikhail; Kpotufe, Samory (Ed.)

   Graph matching, also known as network alignment, refers to finding a bijection between the vertex sets of two given graphs so as to maximally align their edges. This fundamental computational problem arises frequently in multiple fields such as computer vision and biology. Recently, there has been a plethora of work studying efficient algorithms for graph matching under probabilistic models. In this work, we propose a new algorithm for graph matching: Our algorithm associates each vertex with a signature vector using a multistage procedure and then matches a pair of vertices from the two graphs if their signature vectors are close to each other. We show that, for two Erdős–Rényi graphs with edge correlation $$1-\alpha$$, our algorithm recovers the underlying matching exactly with high probability when $$\alpha \le 1 / (\log \log n)^C$$, where $$n$$ is the number of vertices in each graph and $$C$$ denotes a positive universal constant. This improves the condition $$\alpha \le 1 / (\log n)^C$$ achieved in previous work. 

   more » « less
2. Random Graph Matching with Improved Noise Robustness

   Mao, Cheng; Rudelson, Mark; Tikhomirov, Konstantin (July 2021, Proceedings of Thirty Fourth Conference on Learning Theory)

   Belkin, Mikhail; Samory Kpotufe (Ed.)

   Graph matching, also known as network alignment, refers to finding a bijection between the vertex sets of two given graphs so as to maximally align their edges. This fundamental computational problem arises frequently in multiple fields such as computer vision and biology. Recently, there has been a plethora of work studying efficient algorithms for graph matching under probabilistic models. In this work, we propose a new algorithm for graph matching: Our algorithm associates each vertex with a signature vector using a multistage procedure and then matches a pair of vertices from the two graphs if their signature vectors are close to each other. We show that, for two Erdős–Rényi graphs with edge correlation 1−α, our algorithm recovers the underlying matching exactly with high probability when α≤1/(loglogn)C, where n is the number of vertices in each graph and C denotes a positive universal constant. This improves the condition α≤1/(logn)C achieved in previous work. 

   more » « less
3. Deep multistage multi-task learning for quality prediction of multistage manufacturing systems

   https://doi.org/10.1080/00224065.2021.1903822  

   Yan, Hao; Sergin, Nurettin Dorukhan; Brenneman, William A.; Lange, Stephen Joseph; Ba, Shan (January 2021, Journal of Quality Technology)

   In multistage manufacturing systems, modeling multiple quality indices based on the process sensing variables is important. However, the classic modeling technique predicts each quality variable one at a time, which fails to consider the correlation within or between stages. We propose a deep multistage multi-task learning framework to jointly predict all output sensing variables in a unified end-to-end learning framework according to the sequential system architecture in the MMS. Our numerical studies and real case study have shown that the new model has a superior performance compared to many benchmark methods as well as great interpretability through developed variable selection techniques. 

   more » « less
4. Analyzing the effects of pixel-scale data fusion in hyperspectral image classification performance

   https://doi.org/10.1117/12.2560106  

   Alvarez, Michael; Theran, Carlos A.; Arzuaga, Emmanuel; Sierra, Heidy (May 2020, SPIE 11392, Algorithms, Technologies, and Applications for Multispectral and Hyperspectral Imagery XXVI)

   Messinger, David W.; Velez-Reyes, Miguel (Ed.)

   Recently, multispectral and hyperspectral data fusion models based on deep learning have been proposed to generate images with a high spatial and spectral resolution. The general objective is to obtain images that improve spatial resolution while preserving high spectral content. In this work, two deep learning data fusion techniques are characterized in terms of classification accuracy. These methods fuse a high spatial resolution multispectral image with a lower spatial resolution hyperspectral image to generate a high spatial-spectral hyperspectral image. The first model is based on a multi-scale long short-term memory (LSTM) network. The LSTM approach performs the fusion using a multiple step process that transitions from low to high spatial resolution using an intermediate step capable of reducing spatial information loss while preserving spectral content. The second fusion model is based on a convolutional neural network (CNN) data fusion approach. We present fused images using four multi-source datasets with different spatial and spectral resolutions. Both models provide fused images with increased spatial resolution from 8m to 1m. The obtained fused images using the two models are evaluated in terms of classification accuracy on several classifiers: Minimum Distance, Support Vector Machines, Class-Dependent Sparse Representation and CNN classification. The classification results show better performance in both overall and average accuracy for the images generated with the multi-scale LSTM fusion over the CNN fusion 

   more » « less
5. Algorithms and Complexities of Matching Variants in Covariate Balancing

   https://doi.org/10.1287/opre.2022.2286  

   Hochbaum, Dorit S.; Levin, Asaf; Rao, Xu (April 2022, Operations Research)

   Here, we study several variants of matching problems that arise in covariate balancing. Covariate balancing problems can be viewed as variants of matching, or b-matching, with global side constraints. We present here a comprehensive complexity study of the covariate balancing problems providing polynomial time algorithms, or a proof of NP-hardness. The polynomial time algorithms described are mostly combinatorial and rely on network flow techniques. In addition, we present several fixed-parameter tractable results for problems where the number of covariates and the number of levels of each covariate are seen as a parameter. 

   more » « less