Graph Sparsifications using Neural Network Assisted Monte Carlo Tree Search Article Swipe
Alvin Chiu
,
Mithun Ghosh
,
Reyan Ahmed
,
Kwang-Sung Jun
,
Stephen Kobourov
,
Michael T. Goodrich
·
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2311.10316
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2311.10316
Graph neural networks have been successful for machine learning, as well as for combinatorial and graph problems such as the Subgraph Isomorphism Problem and the Traveling Salesman Problem. We describe an approach for computing graph sparsifiers by combining a graph neural network and Monte Carlo Tree Search. We first train a graph neural network that takes as input a partial solution and proposes a new node to be added as output. This neural network is then used in a Monte Carlo search to compute a sparsifier. The proposed method consistently outperforms several standard approximation algorithms on different types of graphs and often finds the optimal solution.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2311.10316
- https://arxiv.org/pdf/2311.10316
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4388843361
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4388843361Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2311.10316Digital Object Identifier
- Title
-
Graph Sparsifications using Neural Network Assisted Monte Carlo Tree SearchWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2023Year of publication
- Publication date
-
2023-11-17Full publication date if available
- Authors
-
Alvin Chiu, Mithun Ghosh, Reyan Ahmed, Kwang-Sung Jun, Stephen Kobourov, Michael T. GoodrichList of authors in order
- Landing page
-
https://arxiv.org/abs/2311.10316Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2311.10316Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2311.10316Direct OA link when available
- Concepts
-
Computer science, Monte Carlo tree search, Monte Carlo method, Artificial neural network, Graph, Travelling salesman problem, Theoretical computer science, Mathematical optimization, Algorithm, Artificial intelligence, Mathematics, StatisticsTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4388843361 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2311.10316 |
| ids.doi | https://doi.org/10.48550/arxiv.2311.10316 |
| ids.openalex | https://openalex.org/W4388843361 |
| fwci | |
| type | preprint |
| title | Graph Sparsifications using Neural Network Assisted Monte Carlo Tree Search |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T11273 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9970999956130981 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1702 |
| topics[0].subfield.display_name | Artificial Intelligence |
| topics[0].display_name | Advanced Graph Neural Networks |
| topics[1].id | https://openalex.org/T10028 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9955000281333923 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1702 |
| topics[1].subfield.display_name | Artificial Intelligence |
| topics[1].display_name | Topic Modeling |
| topics[2].id | https://openalex.org/T12072 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9925000071525574 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1702 |
| topics[2].subfield.display_name | Artificial Intelligence |
| topics[2].display_name | Machine Learning and Algorithms |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C41008148 |
| concepts[0].level | 0 |
| concepts[0].score | 0.6497390270233154 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[0].display_name | Computer science |
| concepts[1].id | https://openalex.org/C46149586 |
| concepts[1].level | 3 |
| concepts[1].score | 0.5185906887054443 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q11785332 |
| concepts[1].display_name | Monte Carlo tree search |
| concepts[2].id | https://openalex.org/C19499675 |
| concepts[2].level | 2 |
| concepts[2].score | 0.5150315761566162 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q232207 |
| concepts[2].display_name | Monte Carlo method |
| concepts[3].id | https://openalex.org/C50644808 |
| concepts[3].level | 2 |
| concepts[3].score | 0.489510178565979 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q192776 |
| concepts[3].display_name | Artificial neural network |
| concepts[4].id | https://openalex.org/C132525143 |
| concepts[4].level | 2 |
| concepts[4].score | 0.466054767370224 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q141488 |
| concepts[4].display_name | Graph |
| concepts[5].id | https://openalex.org/C175859090 |
| concepts[5].level | 2 |
| concepts[5].score | 0.4567417502403259 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q322212 |
| concepts[5].display_name | Travelling salesman problem |
| concepts[6].id | https://openalex.org/C80444323 |
| concepts[6].level | 1 |
| concepts[6].score | 0.43046391010284424 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q2878974 |
| concepts[6].display_name | Theoretical computer science |
| concepts[7].id | https://openalex.org/C126255220 |
| concepts[7].level | 1 |
| concepts[7].score | 0.3728465735912323 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q141495 |
| concepts[7].display_name | Mathematical optimization |
| concepts[8].id | https://openalex.org/C11413529 |
| concepts[8].level | 1 |
| concepts[8].score | 0.3660331964492798 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[8].display_name | Algorithm |
| concepts[9].id | https://openalex.org/C154945302 |
| concepts[9].level | 1 |
| concepts[9].score | 0.27731242775917053 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q11660 |
| concepts[9].display_name | Artificial intelligence |
| concepts[10].id | https://openalex.org/C33923547 |
| concepts[10].level | 0 |
| concepts[10].score | 0.26193171739578247 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[10].display_name | Mathematics |
| concepts[11].id | https://openalex.org/C105795698 |
| concepts[11].level | 1 |
| concepts[11].score | 0.0 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q12483 |
| concepts[11].display_name | Statistics |
| keywords[0].id | https://openalex.org/keywords/computer-science |
| keywords[0].score | 0.6497390270233154 |
| keywords[0].display_name | Computer science |
| keywords[1].id | https://openalex.org/keywords/monte-carlo-tree-search |
| keywords[1].score | 0.5185906887054443 |
| keywords[1].display_name | Monte Carlo tree search |
| keywords[2].id | https://openalex.org/keywords/monte-carlo-method |
| keywords[2].score | 0.5150315761566162 |
| keywords[2].display_name | Monte Carlo method |
| keywords[3].id | https://openalex.org/keywords/artificial-neural-network |
| keywords[3].score | 0.489510178565979 |
| keywords[3].display_name | Artificial neural network |
| keywords[4].id | https://openalex.org/keywords/graph |
| keywords[4].score | 0.466054767370224 |
| keywords[4].display_name | Graph |
| keywords[5].id | https://openalex.org/keywords/travelling-salesman-problem |
| keywords[5].score | 0.4567417502403259 |
| keywords[5].display_name | Travelling salesman problem |
| keywords[6].id | https://openalex.org/keywords/theoretical-computer-science |
| keywords[6].score | 0.43046391010284424 |
| keywords[6].display_name | Theoretical computer science |
| keywords[7].id | https://openalex.org/keywords/mathematical-optimization |
| keywords[7].score | 0.3728465735912323 |
| keywords[7].display_name | Mathematical optimization |
| keywords[8].id | https://openalex.org/keywords/algorithm |
| keywords[8].score | 0.3660331964492798 |
| keywords[8].display_name | Algorithm |
| keywords[9].id | https://openalex.org/keywords/artificial-intelligence |
| keywords[9].score | 0.27731242775917053 |
| keywords[9].display_name | Artificial intelligence |
| keywords[10].id | https://openalex.org/keywords/mathematics |
| keywords[10].score | 0.26193171739578247 |
| keywords[10].display_name | Mathematics |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2311.10316 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/2311.10316 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2311.10316 |
| locations[1].id | doi:10.48550/arxiv.2311.10316 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | cc-by |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | https://openalex.org/licenses/cc-by |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.2311.10316 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5014753003 |
| authorships[0].author.orcid | https://orcid.org/0009-0009-6863-859X |
| authorships[0].author.display_name | Alvin Chiu |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Chiu, Alvin |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5103977750 |
| authorships[1].author.orcid | |
| authorships[1].author.display_name | Mithun Ghosh |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Ghosh, Mithun |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5001115259 |
| authorships[2].author.orcid | https://orcid.org/0000-0001-6830-9053 |
| authorships[2].author.display_name | Reyan Ahmed |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Ahmed, Reyan |
| authorships[2].is_corresponding | False |
| authorships[3].author.id | https://openalex.org/A5046896406 |
| authorships[3].author.orcid | https://orcid.org/0000-0001-5483-3161 |
| authorships[3].author.display_name | Kwang-Sung Jun |
| authorships[3].author_position | middle |
| authorships[3].raw_author_name | Jun, Kwang-Sung |
| authorships[3].is_corresponding | False |
| authorships[4].author.id | https://openalex.org/A5003147292 |
| authorships[4].author.orcid | https://orcid.org/0000-0002-0477-2724 |
| authorships[4].author.display_name | Stephen Kobourov |
| authorships[4].author_position | middle |
| authorships[4].raw_author_name | Kobourov, Stephen |
| authorships[4].is_corresponding | False |
| authorships[5].author.id | https://openalex.org/A5034971300 |
| authorships[5].author.orcid | https://orcid.org/0000-0002-8943-191X |
| authorships[5].author.display_name | Michael T. Goodrich |
| authorships[5].author_position | last |
| authorships[5].raw_author_name | Goodrich, Michael T. |
| authorships[5].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2311.10316 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2023-11-21T00:00:00 |
| display_name | Graph Sparsifications using Neural Network Assisted Monte Carlo Tree Search |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T11273 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9970999956130981 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1702 |
| primary_topic.subfield.display_name | Artificial Intelligence |
| primary_topic.display_name | Advanced Graph Neural Networks |
| related_works | https://openalex.org/W1525389557, https://openalex.org/W2361554335, https://openalex.org/W2359992618, https://openalex.org/W2054495636, https://openalex.org/W4306878646, https://openalex.org/W2164188042, https://openalex.org/W2913191894, https://openalex.org/W3157689847, https://openalex.org/W4389782626, https://openalex.org/W4376138746 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2311.10316 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2311.10316 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2311.10316 |
| primary_location.id | pmh:oai:arXiv.org:2311.10316 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/2311.10316 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2311.10316 |
| publication_date | 2023-11-17 |
| publication_year | 2023 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 38, 50, 58, 63, 78, 84 |
| abstract_inverted_index.We | 28, 47 |
| abstract_inverted_index.an | 30 |
| abstract_inverted_index.as | 9, 11, 18, 56, 69 |
| abstract_inverted_index.be | 67 |
| abstract_inverted_index.by | 36 |
| abstract_inverted_index.in | 77 |
| abstract_inverted_index.is | 74 |
| abstract_inverted_index.of | 98 |
| abstract_inverted_index.on | 95 |
| abstract_inverted_index.to | 66, 82 |
| abstract_inverted_index.The | 86 |
| abstract_inverted_index.and | 14, 23, 42, 61, 100 |
| abstract_inverted_index.for | 6, 12, 32 |
| abstract_inverted_index.new | 64 |
| abstract_inverted_index.the | 19, 24, 103 |
| abstract_inverted_index.This | 71 |
| abstract_inverted_index.Tree | 45 |
| abstract_inverted_index.been | 4 |
| abstract_inverted_index.have | 3 |
| abstract_inverted_index.node | 65 |
| abstract_inverted_index.such | 17 |
| abstract_inverted_index.that | 54 |
| abstract_inverted_index.then | 75 |
| abstract_inverted_index.used | 76 |
| abstract_inverted_index.well | 10 |
| abstract_inverted_index.Carlo | 44, 80 |
| abstract_inverted_index.Graph | 0 |
| abstract_inverted_index.Monte | 43, 79 |
| abstract_inverted_index.added | 68 |
| abstract_inverted_index.finds | 102 |
| abstract_inverted_index.first | 48 |
| abstract_inverted_index.graph | 15, 34, 39, 51 |
| abstract_inverted_index.input | 57 |
| abstract_inverted_index.often | 101 |
| abstract_inverted_index.takes | 55 |
| abstract_inverted_index.train | 49 |
| abstract_inverted_index.types | 97 |
| abstract_inverted_index.graphs | 99 |
| abstract_inverted_index.method | 88 |
| abstract_inverted_index.neural | 1, 40, 52, 72 |
| abstract_inverted_index.search | 81 |
| abstract_inverted_index.Problem | 22 |
| abstract_inverted_index.Search. | 46 |
| abstract_inverted_index.compute | 83 |
| abstract_inverted_index.machine | 7 |
| abstract_inverted_index.network | 41, 53, 73 |
| abstract_inverted_index.optimal | 104 |
| abstract_inverted_index.output. | 70 |
| abstract_inverted_index.partial | 59 |
| abstract_inverted_index.several | 91 |
| abstract_inverted_index.Problem. | 27 |
| abstract_inverted_index.Salesman | 26 |
| abstract_inverted_index.Subgraph | 20 |
| abstract_inverted_index.approach | 31 |
| abstract_inverted_index.describe | 29 |
| abstract_inverted_index.networks | 2 |
| abstract_inverted_index.problems | 16 |
| abstract_inverted_index.proposed | 87 |
| abstract_inverted_index.proposes | 62 |
| abstract_inverted_index.solution | 60 |
| abstract_inverted_index.standard | 92 |
| abstract_inverted_index.Traveling | 25 |
| abstract_inverted_index.combining | 37 |
| abstract_inverted_index.computing | 33 |
| abstract_inverted_index.different | 96 |
| abstract_inverted_index.learning, | 8 |
| abstract_inverted_index.solution. | 105 |
| abstract_inverted_index.algorithms | 94 |
| abstract_inverted_index.successful | 5 |
| abstract_inverted_index.Isomorphism | 21 |
| abstract_inverted_index.outperforms | 90 |
| abstract_inverted_index.sparsifier. | 85 |
| abstract_inverted_index.sparsifiers | 35 |
| abstract_inverted_index.consistently | 89 |
| abstract_inverted_index.approximation | 93 |
| abstract_inverted_index.combinatorial | 13 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 6 |
| citation_normalized_percentile |