{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T20:12:41Z","timestamp":1770063161121,"version":"3.49.0"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030937355","type":"print"},{"value":"9783030937362","type":"electronic"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-93736-2_18","type":"book-chapter","created":{"date-parts":[[2022,2,17]],"date-time":"2022-02-17T21:02:28Z","timestamp":1645131748000},"page":"223-237","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Neural Maximum Independent Set"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Pontoizeau","sequence":"first","affiliation":[]},{"given":"Florian","family":"Sikora","sequence":"additional","affiliation":[]},{"given":"Florian","family":"Yger","sequence":"additional","affiliation":[]},{"given":"Tristan","family":"Cazenave","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,2,17]]},"reference":[{"key":"18_CR1","unstructured":"Abe, K., Xu, Z., Sato, I., Sugiyama, M.: Solving NP-hard problems on graphs with extended AlphaGo zero (2020)"},{"issue":"3","key":"18_CR2","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/S0925-7721(98)00028-5","volume":"11","author":"PK Agarwal","year":"1998","unstructured":"Agarwal, P.K., van Kreveld, M., Suri, S.: Label placement by maximum independent set in rectangles. Comput. Geom. 11(3), 209\u2013218 (1998)","journal-title":"Comput. Geom."},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"Akiba, T., Sano, S., Yanase, T., Ohta, T., Koyama, M.: Optuna: a next-generation hyperparameter optimization framework. In: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, pp. 2623\u20132631. Association for Computing Machinery, New York (2019)","DOI":"10.1145\/3292500.3330701"},{"issue":"1","key":"18_CR4","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1002\/jgt.21861","volume":"81","author":"J Alexander","year":"2016","unstructured":"Alexander, J., Mink, T.: A new method for enumerating independent sets of a fixed size in general graphs. J. Graph Theory 81(1), 57\u201372 (2016)","journal-title":"J. Graph Theory"},{"key":"18_CR5","unstructured":"Anthony, T., Tian, Z., Barber, D.: Thinking fast and slow with deep learning and tree search. In: Advances in Neural Information Processing Systems, pp. 5360\u20135370 (2017)"},{"issue":"5439","key":"18_CR6","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"AL Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si, A.L., Albert, R.: Emergence of Scaling in Random Networks. Science 286(5439), 509\u2013512 (1999)","journal-title":"Science"},{"issue":"2","key":"18_CR7","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1016\/j.ejor.2020.07.063","volume":"290","author":"Y Bengio","year":"2021","unstructured":"Bengio, Y., Lodi, A., Prouvost, A.: Machine learning for combinatorial optimization: a methodological tour d\u2019horizon. Eur. J. Oper. Res. 290(2), 405\u2013421 (2021)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"18_CR8","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0167-6377(96)00038-7","volume":"20","author":"JM Bourjolly","year":"1997","unstructured":"Bourjolly, J.M., Laporte, G., Mercure, H.: A combinatorial column generation algorithm for the maximum stable set problem. Oper. Res. Lett. 20(1), 21\u201329 (1997)","journal-title":"Oper. Res. Lett."},{"issue":"6","key":"18_CR9","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1016\/j.orl.2004.03.002","volume":"32","author":"JM Byskov","year":"2004","unstructured":"Byskov, J.M.: Enumerating maximal independent sets with applications to graph colouring. Oper. Res. Lett. 32(6), 547\u2013556 (2004)","journal-title":"Oper. Res. Lett."},{"key":"18_CR10","doi-asserted-by":"crossref","unstructured":"Chen, D., Lin, Y., Li, W., Li, P., Zhou, J., Sun, X.: Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. In: The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, February 7\u201312, 2020, pp. 3438\u20133445. AAAI Press, New York (2020)","DOI":"10.1609\/aaai.v34i04.5747"},{"key":"18_CR11","unstructured":"Chen, M., Wei, Z., Huang, Z., Ding, B., Li, Y.: Simple and deep graph convolutional networks. In: III, H.D., Singh, A. (eds.) Proceedings of the 37th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 119, pp. 1725\u20131735. PMLR, 13\u201318 July 2020"},{"key":"18_CR12","unstructured":"Chen, X., Tian, Y.: Learning to perform local rewriting for combinatorial optimization. In: Wallach, H., Larochelle, H., Beygelzimer, A., d\u2019 Alch\u00e9-Buc, F., Fox, E., Garnett, R. (eds.) Advances in Neural Information Processing Systems, vol. 32. Curran Associates, Inc. (2019)"},{"key":"18_CR13","unstructured":"Chen, Z., et al.: Bridging the gap between spatial and spectral domains: a survey on graph neural networks (2020)"},{"key":"18_CR14","doi-asserted-by":"crossref","unstructured":"Das, K.N., Chaudhuri, B.: Heuristics to find maximum independent set: An overview. In: Deep, K., Nagar, A., Pant, M., Bansal, J.C. (eds.) Proceedings of the International Conference on Soft Computing for Problem Solving (SocProS 2011) 20\u201322 December, 2011, pp. 881\u2013892. Springer, India (2012)","DOI":"10.1007\/978-81-322-0487-9_83"},{"key":"18_CR15","unstructured":"Dwivedi, V.P., Joshi, C.K., Laurent, T., Bengio, Y., Bresson, X.: Benchmarking Graph Neural Networks. arXiv e-prints (2020)"},{"key":"18_CR16","unstructured":"Gasse, M., Ch\u00e9telat, D., Ferroni, N., Charlin, L., Lodi, A.: Exact combinatorial optimization with graph convolutional neural networks. In: Wallach, H.M., Larochelle, H., Beygelzimer, A., d\u2019Alch\u00e9-Buc, F., Fox, E.B., Garnett, R. (eds.) Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8\u201314 December, 2019, Vancouver, BC, Canada, pp. 15554\u201315566 (2019)"},{"issue":"3","key":"18_CR17","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/s00186-019-00696-4","volume":"91","author":"F Gurski","year":"2020","unstructured":"Gurski, F., Rehs, C.: Counting and enumerating independent sets with applications to combinatorial optimization problems. Math. Methods Oper. Res. 91(3), 439\u2013463 (2020)","journal-title":"Math. Methods Oper. Res."},{"key":"18_CR18","unstructured":"Hu, W., et al.: Open graph benchmark: Datasets for machine learning on graphs (2021)"},{"key":"18_CR19","unstructured":"Karalias, N., Loukas, A.: Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs. In: Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M.F., Lin, H. (eds.) Advances in Neural Information Processing Systems, vol. 33, pp. 6659\u20136672. Curran Associates, Inc. (2020)"},{"key":"18_CR20","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among Combinatorial Problems, pp. 85\u2013103. Springer, US (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"18_CR21","unstructured":"Khalil, E., Dai, H., Zhang, Y., Dilkina, B., Song, L.: Learning combinatorial optimization algorithms over graphs. In: Guyon, I., Luxburg, U.V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., Garnett, R. (eds.) Advances in Neural Information Processing Systems, vol. 30. Curran Associates, Inc. (2017)"},{"issue":"4","key":"18_CR22","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s10732-017-9337-x","volume":"23","author":"S Lamm","year":"2017","unstructured":"Lamm, S., Sanders, P., Schulz, C., Strash, D., Werneck, R.F.: Finding near-optimal independent sets at scale. J. Heuristics 23(4), 207\u2013229 (2017)","journal-title":"J. Heuristics"},{"key":"18_CR23","unstructured":"Van der Maaten, L., Hinton, G.: Visualizing data using t-sne. J. Mach. Learn. Res. 9(11) (2008)"},{"key":"18_CR24","doi-asserted-by":"crossref","unstructured":"Mazyavkina, N., Sviridov, S., Ivanov, S., Burnaev, E.: Reinforcement learning for combinatorial optimization: a survey (2020)","DOI":"10.1016\/j.cor.2021.105400"},{"key":"18_CR25","unstructured":"Piotr, B., Marek, K.: On some tighter inapproximability results. Technical report (1999)"},{"issue":"2","key":"18_CR26","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/S0167-6377(00)00060-2","volume":"28","author":"F Rossi","year":"2001","unstructured":"Rossi, F., Smriglio, S.: A branch-and-cut algorithm for the maximum cardinality stable set problem. Oper. Res. Lett. 28(2), 63\u201374 (2001)","journal-title":"Oper. Res. Lett."},{"key":"18_CR27","unstructured":"Rossi, R.A., Ahmed, N.K.: The Network Data Repository with Interactive Graph Analytics and Visualization. In: Bonet, B., Koenig, S. (eds.) Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25\u201330, 2015, Austin, Texas, USA, pp. 4292\u20134293. AAAI Press (2015)"},{"key":"18_CR28","unstructured":"Sato, R., Yamada, M., Kashima, H.: Approximation ratios of graph neural networks for combinatorial problems. In: Wallach, H., Larochelle, H., Beygelzimer, A., d\u2019 Alch\u00e9-Buc, F., Fox, E., Garnett, R. (eds.) Advances in Neural Information Processing Systems, vol. 32. Curran Associates, Inc. (2019)"},{"key":"18_CR29","unstructured":"Sato, R., Yamada, M., Kashima, H.: Random Features Strengthen Graph Neural Networks. CoRR abs\/2002.03155 (2020). https:\/\/arxiv.org\/abs\/2002.03155"},{"issue":"6419","key":"18_CR30","doi-asserted-by":"publisher","first-page":"1140","DOI":"10.1126\/science.aar6404","volume":"362","author":"D Silver","year":"2018","unstructured":"Silver, D., et al.: A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science 362(6419), 1140\u20131144 (2018)","journal-title":"Science"},{"key":"18_CR31","unstructured":"Velickovic, P., Cucurull, G., Casanova, A., Romero, A., Li\u00f2, P., Bengio, Y.: Graph attention networks. In: 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30\u20133 May 2018, Conference Track Proceedings (2018)"},{"key":"18_CR32","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.ic.2017.06.001","volume":"255","author":"M Xiao","year":"2017","unstructured":"Xiao, M., Nagamochi, H.: Exact algorithms for maximum independent set. Inf. Comput. 255, 126\u2013146 (2017)","journal-title":"Inf. Comput."},{"key":"18_CR33","unstructured":"Xu, K.: BHOSLIB: Benchmarks with Hidden Optimum Solutions for Graph Problems (Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring). http:\/\/sites.nlsde.buaa.edu.cn\/~kexu\/benchmarks\/graph-benchmarks.htm"},{"key":"18_CR34","unstructured":"Xu, K., Hu, W., Leskovec, J., Jegelka, S.: How Powerful are Graph Neural Networks? In: 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, 6\u20139 May 2019 (2019)"},{"key":"18_CR35","unstructured":"Yehuda, G., Gabel, M., Schuster, A.: It\u2019s not what machines can learn, it\u2019s what we cannot teach. In: III, H.D., Singh, A. (eds.) Proceedings of the 37th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 119, pp. 10831\u201310841 (2020)"},{"key":"18_CR36","unstructured":"Zhou, J., et al.: Graph neural networks: a review of methods and applications (2019)"}],"container-title":["Communications in Computer and Information Science","Machine Learning and Principles and Practice of Knowledge Discovery in Databases"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-93736-2_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,6]],"date-time":"2022-05-06T02:12:31Z","timestamp":1651803151000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-93736-2_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030937355","9783030937362"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-93736-2_18","relation":{},"ISSN":["1865-0929","1865-0937"],"issn-type":[{"value":"1865-0929","type":"print"},{"value":"1865-0937","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"17 February 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ECML PKDD","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Joint European Conference on Machine Learning and Knowledge Discovery in Databases","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Bilbao","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Spain","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 September 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 September 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ecml2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/2021.ecmlpkdd.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"869","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"210","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"24% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3-4","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3-9","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference was held online due to the COVID-19 pandemic.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}