Graph Learning for Combinatorial Optimization: A Survey of State-of-the-Art
Tóm tắt
Graphs have been widely used to represent complex data in many applications, such as e-commerce, social networks, and bioinformatics. Efficient and effective analysis of graph data is important for graph-based applications. However, most graph analysis tasks are combinatorial optimization (CO) problems, which are NP-hard. Recent studies have focused a lot on the potential of using machine learning (ML) to solve graph-based CO problems. Most recent methods follow the two-stage framework. The first stage is graph representation learning, which embeds the graphs into low-dimension vectors. The second stage uses machine learning to solve the CO problems using the embeddings of the graphs learned in the first stage. The works for the first stage can be classified into two categories, graph embedding methods and end-to-end learning methods. For graph embedding methods, the learning of the the embeddings of the graphs has its own objective, which may not rely on the CO problems to be solved. The CO problems are solved by independent downstream tasks. For end-to-end learning methods, the learning of the embeddings of the graphs does not have its own objective and is an intermediate step of the learning procedure of solving the CO problems. The works for the second stage can also be classified into two categories, non-autoregressive methods and autoregressive methods. Non-autoregressive methods predict a solution for a CO problem in one shot. A non-autoregressive method predicts a matrix that denotes the probability of each node/edge being a part of a solution of the CO problem. The solution can be computed from the matrix using search heuristics such as beam search. Autoregressive methods iteratively extend a partial solution step by step. At each step, an autoregressive method predicts a node/edge conditioned to current partial solution, which is used to its extension. In this survey, we provide a thorough overview of recent studies of the graph learning-based CO methods. The survey ends with several remarks on future research directions.
Tài liệu tham khảo
Abe K, Xu Z, Sato I, Sugiyama M (2019) Solving np-hard problems on graphs with extended alphago zero. arXiv:1905.11623
Bai Y, Ding H, Bian S, Chen T, Sun Y, Wang W (2019) SimGNN: a neural network approach to fast graph similarity computation. In: Proceedings of the ACM international conference on web search and data mining (WSDM’19), pp 384–392
Bai Y, Ding H, Gu K, Sun Y, Wang W (2020) Learning-based efficient graph similarity computation via multi-scale convolutional set matching. In: Proceedings of the AAAI conference on artificial intelligence (AAAI’20), pp 3219–3226
Bai Y, Xu D, Wang A, Gu K, Wu X, Marinovic A, Ro C, Sun Y, Wang W (2020) Fast detection of maximum common subgraph via deep Q-learning. arXiv:2002.03129
Bengio Y, Lodi A, Prouvost A (2018) Machine learning for combinatorial optimization: A methodological tour d’horizon. arXiv:1811.06128
Bonner S, Kureshi I, Brennan J, Theodoropoulos G, McGough AS, Obara B (2019) Exploring the semantic content of unsupervised graph embeddings: an empirical study. Data Sci Eng 4(3):269–289
Cai H, Zheng VW, Chang K (2018) A comprehensive survey of graph embedding: problems, techniques, and applications. IEEE Trans Knowl Data Eng 30(09):1616–1637
Cao S, Lu W, Xu Q (2015) GraRep: learning graph representations with global structural information. In: Proceedings of ACM international on conference on information and knowledge management (CIKM’15), pp 891–900
Chami I, Abu-El-Haija S, Perozzi B, Ré C, Murphy K (2020) Machine learning on graphs: a model and comprehensive taxonomy. arXiv:2005.03675
Chang L (2019) Efficient maximum clique computation over large sparse graphs. In: Proceedings of ACM SIGKDD international conference on knowledge discovery and data mining (KDD’19), pp 529–538
Chen F, Wang YC, Wang B, Kuo CCJ (2020) Graph representation learning: a survey. APSIPA Trans Signal Inf Process 9:e15
Chen H, Yin H, Chen T, Nguyen QVH, Peng W, Li X (2019) Exploiting centrality information with graph convolutions for network representation learning. In: IEEE international conference on data engineering (ICDE’19), pp 590–601
Cui P, Wang X, Pei J, Zhu W (2019) A survey on network embedding. IEEE Trans Knowl Data Eng 31(5):833–852
Dai H, Khalil EB, Zhang Y, Dilkina B, Song L (2017) Learning combinatorial optimization algorithms over graphs. In: Proceedings of international conference on neural information processing systems (NIPS’17), pp 6351–6361
Dareddy MR, Das M, Yang H (2019) Motif2Vec: Motif aware node representation learning for heterogeneous networks. In: 2019 IEEE international conference on big data (Big Data’19), pp 1052–1059
Dave VS, Zhang B, Chen PY, Al Hasan M (2019) Neural-brane: neural bayesian personalized ranking for attributed network embedding. Data Sci Eng 4(2):119–131
Deudon M, Cournut P, Lacoste A, Adulyasak Y, Rousseau LM (2018) Learning heuristics for the TSP by policy gradient. In: International conference on the integration of constraint programming, artificial intelligence, and operations research, pp 170–181
Devlin J, Chang MW, Lee K, Toutanova K (2019) BERT: Pre-training of deep bidirectional transformers for language understanding. Proc Conf N Am Chapter Assoc Comput Linguist Hum Lang Technol 1:4171–4186
Du X, Yan J, Zha H (2019) Joint link prediction and network alignment via cross-graph embedding. In: Proceedings of international joint conference on artificial intelligence, IJCAI’19, pp 2251–2257
Duvenaud DK, Maclaurin D, Iparraguirre J, Bombarell R, Hirzel T, Aspuru-Guzik A, Adams RP (2015) Convolutional networks on graphs for learning molecular fingerprints. Adv Neural Inf Process Syst 28:2224–2232
Fan W, Ma Y, Li Q, He Y, Zhao E, Tang J, Yin D (2019) Graph neural networks for social recommendation. In: The world wide web conference, pp 417–426
Fan Z, Peng Y, Choi B, Xu J, Bhowmick SS (2014) Towards efficient authenticated subgraph query service in outsourced graph databases. IEEE Trans Serv Comput 7(4):696–713
Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J ACM 42(6):1115–1145
Grover A, Leskovec J (2016) Node2Vec: Scalable feature learning for networks. In: Proceedings of ACM SIGKDD international conference on knowledge discovery and data mining (KDD’16), pp 855–864
Hamilton WL, Ying R, Leskovec J (2017) Inductive representation learning on large graphs. In: Proceedings of international conference on neural information processing systems (NIPS’17), pp 1025–1035
Hamilton WL, Ying R, Leskovec J (2017) Representation learning on graphs: methods and applications. IEEE Data Eng Bull
Håstad J (1999) Clique is hard to approximate within \(n^{1-\varepsilon }\). Acta Math 182(1):105–142
Hopfield J, Tank D (1985) Neural computation of decisions in optimisation problems. Biol Cybern 52:141–152
Huang J, Patwary MMA, Diamos GF (2019) Coloring big graphs with alphagozero. CoRR arXiv:1902.10162
Huang W, Zhang T, Rong Y, Huang J (2018) Adaptive sampling towards fast graph representation learning. In: Proceedings of international conference on neural information processing systems (NIPS’18), pp 4563–4572
Huang X, Lakshmanan LV, Xu J (2019) Community search over big graphs. Morgan & Claypool Publishers, New York
Jin W, Barzilay R, Jaakkola T (2018) Junction tree variational autoencoder for molecular graph generation. Proc Int Conf Mach Learn 80:2323–2332
Joshi CK, Cappart Q, Rousseau LM, Laurent T, Bresson X (2020) Learning TSP requires rethinking generalization. arXiv:2006.07054
Joshi CK, Laurent T, Bresson X (2019) An efficient graph convolutional network technique for the travelling salesman problem. CoRR arXiv:1906.01227
Khot S (2001) Improved inapproximability results for maxclique, chromatic number and approximate graph coloring. In: Proceedings IEEE symposium on foundations of computer science, pp 600–609
Kipf TN, Welling M (2017) Semi-supervised classification with graph convolutional networks. In: International conference on learning representations (ICLR’17)
Kool W, van Hoof H, Welling M (2019) Attention, learn to solve routing problems! In: International conference on learning representations
Lamb LC, Garcez AD, Gori M, Prates MO, Avelar PH, Vardi MY (2020) Graph neural networks meet neural-symbolic computing: a survey and perspective. In: Proceedings of international joint conference on artificial intelligence (IJCAI’20), pp 4877–4884
Le Q, Mikolov T (2014) Distributed representations of sentences and documents. In: Proceedings of international conference on international conference on machine learning, vol 32, ICML’14, pp II–1188–II–1196
Lemos H, Prates MOR, Avelar PHC, Lamb LC (2019) Graph colouring meets deep learning: Effective graph neural network models for combinatorial problems. CoRR arXiv:1903.04598
Li Y, Gu C, Dullien T, Vinyals O, Kohli P (2019) Graph matching networks for learning the similarity of graph structured objects. In: Proceedings of international conference on machine learning (ICML’19), pp 3835–3845
Li Z, Chen Q, Koltun V (2018) Combinatorial optimization with graph convolutional networks and guided tree search. In: Proceedings of international conference on neural information processing systems (NIPS’18), pp 537–546
Mazyavkina N, Sviridov S, Ivanov S, Burnaev E (2020) Reinforcement learning for combinatorial optimization: a survey. arXiv:2003.03600
Meng L, Zhang J (2019) IsoNN: Isomorphic neural network for graph representation learning and classification. CoRR arXiv:1907.09495
Mikolov T, Sutskever I, Chen K, Corrado G, Dean J (2013) Distributed representations of words and phrases and their compositionality. In: Proceedings of the 26th international conference on neural information processing systems (NIPS’13), pp 3111–3119
Milan A, Rezatofighi SH, Garg R, Dick A, Reid I (2017) Data-driven approximations to np-hard problems. In: Thirty-first AAAI conference on artificial intelligence
Mnih V, Kavukcuoglu K, Silver D, Rusu AA, Veness J, Bellemare MG, Graves A, Riedmiller M, Fidjeland AK, Ostrovski G et al (2015) Human-level control through deep reinforcement learning. Nature 518(7540):529–533
Narayanan A, Chandramohan M, Chen L, Liu Y, Saminathan S, Subgraph2Vec: learning distributed representations of rooted sub-graphs from large graphs
Nazi A, Hang W, Goldie A, Ravi S, Mirhoseini A (2019) GAP : Generalizable approximate graph partitioning framework. URL ICLR workshop
Nguyen H, Murata T (2017) Motif-aware graph embeddings. In: Proceedings of international joint conference on artificial intelligence (IJCAI’17), pp 1–1
Nowak A, Villar S, Bandeira AS, Bruna J (2017) A note on learning algorithms for quadratic assignment with graph neural networks. In: Proceeding of international conference on machine learning (ICML’17), pp 22–22
Ou M, Cui P, Pei J, Zhang Z, Zhu W (2016) Asymmetric transitivity preserving graph embedding. In: Proceedings of ACM SIGKDD international conference on knowledge discovery and data mining (KDD’16), pp 1105–1114
Papadimitriou CH, Vempala S (2006) On the approximability of the traveling salesman problem. Combinatorica 26(1):101–120
Peng Y, Choi B, He B, Zhou S, Xu R, Yu X (2016) VColor: A practical vertex-cut based approach for coloring large graphs. In: IEEE international conference on data engineering (ICDE’16), pp 97–108
Peng Y, Fan Z, Choi B, Xu J, Bhowmick SS (2015) Authenticated subgraph similarity searchin outsourced graph databases. IEEE Trans Knowl Data Eng 27(7):1838–1860
Perozzi B, Al-Rfou R, Skiena S (2014) DeepWalk: Online learning of social representations. In: Proceedings of ACM SIGKDD international conference on knowledge discovery and data mining (KDD’14), pp 701–710
Prates M, Avelar P, Lemos H, Lamb L, Vardi M (2019) Learning to solve NP-Complete problems - a graph neural network for decision TSP. In: Proceedings of AAAI conference on artificial intelligence (AAAI’19), pp 4731–4738
Ribeiro LF, Saverese PH, Figueiredo DR (2017) Struc2Vec: Learning node representations from structural identity. In: Proceedings of ACM SIGKDD international conference on knowledge discovery and data mining (KDD’17), pp 385–394
Sato R, Yamada M, Kashima H (2019) Approximation ratios of graph neural networks for combinatorial problems. In: Proceedings of the neural information processing systems (NIPS’19)
Smith-Miles K (1999) Neural networks for combinatorial optimization: a review of more than a decade of research. INFORMS J Comput 11:15–34
Sutton RS, Barto AG (2018) Reinforcement learning: an introduction. MIT Press, Cambridge
Tang J, Qu M, Mei Q (2015) PTE: Predictive text embedding through large-scale heterogeneous text networks. In: Proceedings of ACM SIGKDD international conference on knowledge discovery and data mining (KDD’15), pp 1165–1174
Tang J, Qu M, Wang M, Zhang M, Yan J, Mei Q (2015) LINE: Large-scale information network embedding. In: Proceedings of international conference on world wide web (WWW’15), pp 1067–1077
Tsitsulin A, Mottin D, Karras P, Müller E (2018) VERSE: Versatile graph embeddings from similarity measures. In: Proceedings of world wide web conference (WWW’18), pp 539–548
Tu K, Cui P, Wang X, Yu PS, Zhu W (2018) Deep recursive network embedding with regular equivalence. In: Proceedings of ACM SIGKDD international conference on knowledge discovery & data mining (KDD’18), pp 2357–2366
Veličković P, Cucurull G, Casanova A, Romero A, Liò P, Bengio Y (2018) Graph Attention Networks. In: International conference on learning representations (ICLR)
Vinyals O, Fortunato M, Jaitly N (2015) Pointer networks. Adv Neural Inf Process Syst 28:2692–2700
Wang D, Cui P, Zhu W (2016) Structural deep network embedding. In: Proceedings of ACM SIGKDD International conference on knowledge discovery and data mining (KDD’16), pp 1225–1234
Wang R, Yan J, Yang X (2019) Learning combinatorial embedding networks for deep graph matching. In: Proceedings of the IEEE international conference on computer vision (ICCV’19), pp 3056–3065
Wasserman S, Faust K et al (1994) Social network analysis: methods and applications, vol 8. Cambridge University Press, Cambridge
Wu Y, Song W, Cao Z, Zhang J, Lim A (2019) Learning improvement heuristics for solving the travelling salesman problem. CoRR arXiv:1912.05784
Wu Z, Pan S, Chen F, Long G, Zhang C, Yu PS (2019) A comprehensive survey on graph neural networks. CoRR arXiv:1901.00596
Yanardag P, Vishwanathan S (2015) Deep graph kernels. In: Proceedings of ACM sigkdd international conference on knowledge discovery and data mining (KDD’15), pp 1365–1374
Yang Y, Wang X, Song M, Yuan J, Tao D (2019) SPAGAN: Shortest path graph attention network. In: Proceedings of international joint conference on artificial intelligence (IJCAI’19), pp 4099–4105
Yu Y, Lu Z, Liu J, Zhao G, Wen J (2019) RUM: Network representation learning using motifs. In: IEEE international conference on data engineering (ICDE’19), pp 1382–1393
Yue X, Wang Z, Huang J, Parthasarathy S, Moosavinasab S, Huang Y, Lin SM, Zhang W, Zhang P, Sun H (2019) Graph embedding on biomedical networks: methods, applications and evaluations. Bioinformatics 36(4):1241–1251
Zhang D, Yin J, Zhu X, Zhang C (2020) Network representation learning: a survey. IEEE Trans Big Data 6(1):3–28
Zhang F, Yuan NJ, Lian D, Xie X, Ma WY (2016) Collaborative knowledge base embedding for recommender systems. In: Proceedings of ACM SIGKDD international conference on knowledge discovery and data mining (KDD’16), pp 353–362