“There are some things which cannot be learned quickly, and time, which is all we have, must be paid heavily for their acquiring. They are the very simplest things, and because it takes a man’s life to know them the little new that each man gets from life is very costly and the only heritage he has to leave.” - Ernest Hemingway (More…)
News #
I will be updating both good news, bad news and all kinds of news.
Posts #
Generalization
Generalization # Generalization is a critical aspect of machine learning for combinatorial optimization. This section covers approaches to improve generalization across different problem instances and scales. Recent Literature # It’s Not What Machines Can Learn It’s What We Cannot Teach ICML, 2020. paper Gal Yehuda, Moshe Gabel and Assaf Schuster Learning TSP Requires Rethinking Generalization CP, 2021. paper, code Chaitanya K. Joshi, Quentin Cappart, Louis-Martin Rousseau and Thomas Laurent Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness ICLR, 2022. paper
Graph Coloring
Graph Coloring # Graph Coloring is the problem of assigning colors to vertices such that no two adjacent vertices have the same color, with applications in scheduling and frequency assignment. Recent Literature # Deep Learning-based Hybrid Graph-Coloring Algorithm for Register Allocation. Arxiv, 2019. paper Das, Dibyendu and Ahmad, Shahid Asghar and Venkataramanan, Kumar. Neural Models for Output-Space Invariance in Combinatorial Problems ICLR, 2022. paper Nandwani, Yatin and Jain, Vidit and Singla, Parag and others
Graph Edit Distance (GED)
Graph Edit Distance (GED) # Graph Edit Distance measures the minimum cost of transformations needed to change one graph into another. It has applications in pattern matching and graph similarity computation. Recent Literature # SimGNN - A Neural Network Approach to Fast Graph Similarity Computation WSDM, 2019. paper, code Bai, Yunsheng and Ding, Hao and Bian, Song and Chen, Ting and Sun, Yizhou and Wang, Wei Graph Matching Networks for Learning the Similarity of Graph Structured Objects ICML, 2019. paper, code
Graph Matching (GM)
Graph Matching (GM) # Graph Matching is a fundamental combinatorial optimization problem that involves finding correspondences between vertices of two graphs. Recent Literature # Revised Note on Learning Algorithms for Quadratic Assignment with Graph Neural Networks Arxiv, 2017. paper, code Nowak, Alex and Villar, Soledad and Bandeira, S. Afonso and Bruna, Joan Deep Learning of Graph Matching. CVPR, 2018. paper Zanfir, Andrei and Sminchisescu, Cristian ⭐Learning Combinatorial Embedding Networks for Deep Graph Matching. ICCV, 2019. paper, code
Hamiltonian Cycle Problem (HCP)
Hamiltonian Cycle Problem (HCP) # The Hamiltonian Cycle Problem seeks to find a cycle visiting each vertex exactly once. It is NP-complete and is fundamental to understanding NP-hardness. Recent Literature # ⭐A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs NeurIPS, 2021. paper, code Wang, Runzhong and Hua, Zhigang and Liu, Gan and Zhang, Jiayi and Yan, Junchi and Qi, Feng and Yang, Shuang and Zhou, Jun and Yang, Xiaokang