Neural Graduated Assignment for Maximum Common Edge Subgraphs
This addresses scalability issues in MCES computation for domains such as biology and chemistry, representing a novel method for a known bottleneck.
The paper tackled the Maximum Common Edge Subgraph (MCES) problem, which is important in fields like biology and chemistry, by introducing Neural Graduated Assignment (NGA), an unsupervised method that significantly improves computation time and scalability on large instances while enhancing performance compared to existing methods.
The Maximum Common Edge Subgraph (MCES) problem is a crucial challenge with significant implications in domains such as biology and chemistry. Traditional approaches, which include transformations into max-clique and search-based algorithms, suffer from scalability issues when dealing with larger instances. This paper introduces ``Neural Graduated Assignment'' (NGA), a simple, scalable, unsupervised-training-based method that addresses these limitations. Central to NGA is stacking of differentiable assignment optimization with neural components, enabling high-dimensional parameterization of the matching process through a learnable temperature mechanism. We further theoretically analyze the learning dynamics of NGA, showing its design leads to fast convergence, better exploration-exploitation tradeoff, and ability to escape local optima. Extensive experiments across MCES computation, graph similarity estimation, and graph retrieval tasks reveal that NGA not only significantly improves computation time and scalability on large instances but also enhances performance compared to existing methodologies. The introduction of NGA marks a significant advancement in the computation of MCES and offers insights into other assignment problems.