GraphEval36K: Benchmarking Coding and Reasoning Capabilities of Large Language Models on Graph Datasets Article Swipe
Qiming Wu
,
Zichen Chen
,
Will Corcoran
,
Misha Sra
,
Ambuj K. Singh
·
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2406.16176
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2406.16176
Large language models (LLMs) have achieved remarkable success in natural language processing (NLP), demonstrating significant capabilities in processing and understanding text data. However, recent studies have identified limitations in LLMs' ability to manipulate, program, and reason about structured data, especially graphs. We introduce GraphEval36K, the first comprehensive graph dataset, comprising 40 graph coding problems and 36,900 test cases to evaluate the ability of LLMs on graph problem-solving. Our dataset is categorized into eight primary and four sub-categories to ensure a thorough evaluation across different types of graphs. We benchmark ten LLMs, finding that private models outperform open-source ones, though the gap is narrowing. We also analyze the performance of LLMs across directed vs undirected graphs, different kinds of graph concepts, and network models. Furthermore, to improve the usability of our evaluation framework, we propose Structured Symbolic Decomposition (SSD), an instruction-based method designed to enhance LLM performance on complex graph tasks. Results show that SSD improves the average passing rate of GPT-4, GPT-4o, Gemini-Pro and Claude-3-Sonnet by 8.38%, 6.78%, 29.28% and 25.28%, respectively.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2406.16176
- https://arxiv.org/pdf/2406.16176
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4400023548
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4400023548Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2406.16176Digital Object Identifier
- Title
-
GraphEval36K: Benchmarking Coding and Reasoning Capabilities of Large Language Models on Graph DatasetsWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2024Year of publication
- Publication date
-
2024-06-23Full publication date if available
- Authors
-
Qiming Wu, Zichen Chen, Will Corcoran, Misha Sra, Ambuj K. SinghList of authors in order
- Landing page
-
https://arxiv.org/abs/2406.16176Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2406.16176Direct 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/2406.16176Direct OA link when available
- Concepts
-
Benchmarking, Computer science, Graph, Natural language processing, Theoretical computer science, Business, MarketingTop 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/W4400023548 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2406.16176 |
| ids.doi | https://doi.org/10.48550/arxiv.2406.16176 |
| ids.openalex | https://openalex.org/W4400023548 |
| fwci | |
| type | preprint |
| title | GraphEval36K: Benchmarking Coding and Reasoning Capabilities of Large Language Models on Graph Datasets |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T10028 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9987000226974487 |
| 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 | Topic Modeling |
| topics[1].id | https://openalex.org/T11273 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9948999881744385 |
| 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 | Advanced Graph Neural Networks |
| topics[2].id | https://openalex.org/T10181 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9936000108718872 |
| 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 | Natural Language Processing Techniques |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C86251818 |
| concepts[0].level | 2 |
| concepts[0].score | 0.8798717260360718 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q816754 |
| concepts[0].display_name | Benchmarking |
| concepts[1].id | https://openalex.org/C41008148 |
| concepts[1].level | 0 |
| concepts[1].score | 0.6734593510627747 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[1].display_name | Computer science |
| concepts[2].id | https://openalex.org/C132525143 |
| concepts[2].level | 2 |
| concepts[2].score | 0.5600541234016418 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q141488 |
| concepts[2].display_name | Graph |
| concepts[3].id | https://openalex.org/C204321447 |
| concepts[3].level | 1 |
| concepts[3].score | 0.4214499890804291 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q30642 |
| concepts[3].display_name | Natural language processing |
| concepts[4].id | https://openalex.org/C80444323 |
| concepts[4].level | 1 |
| concepts[4].score | 0.18396082520484924 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q2878974 |
| concepts[4].display_name | Theoretical computer science |
| concepts[5].id | https://openalex.org/C144133560 |
| concepts[5].level | 0 |
| concepts[5].score | 0.09421125054359436 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q4830453 |
| concepts[5].display_name | Business |
| concepts[6].id | https://openalex.org/C162853370 |
| concepts[6].level | 1 |
| concepts[6].score | 0.0 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q39809 |
| concepts[6].display_name | Marketing |
| keywords[0].id | https://openalex.org/keywords/benchmarking |
| keywords[0].score | 0.8798717260360718 |
| keywords[0].display_name | Benchmarking |
| keywords[1].id | https://openalex.org/keywords/computer-science |
| keywords[1].score | 0.6734593510627747 |
| keywords[1].display_name | Computer science |
| keywords[2].id | https://openalex.org/keywords/graph |
| keywords[2].score | 0.5600541234016418 |
| keywords[2].display_name | Graph |
| keywords[3].id | https://openalex.org/keywords/natural-language-processing |
| keywords[3].score | 0.4214499890804291 |
| keywords[3].display_name | Natural language processing |
| keywords[4].id | https://openalex.org/keywords/theoretical-computer-science |
| keywords[4].score | 0.18396082520484924 |
| keywords[4].display_name | Theoretical computer science |
| keywords[5].id | https://openalex.org/keywords/business |
| keywords[5].score | 0.09421125054359436 |
| keywords[5].display_name | Business |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2406.16176 |
| 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/2406.16176 |
| 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/2406.16176 |
| locations[1].id | doi:10.48550/arxiv.2406.16176 |
| 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.2406.16176 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5101386231 |
| authorships[0].author.orcid | |
| authorships[0].author.display_name | Qiming Wu |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Wu, Qiming |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5104078124 |
| authorships[1].author.orcid | |
| authorships[1].author.display_name | Zichen Chen |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Chen, Zichen |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5099497089 |
| authorships[2].author.orcid | |
| authorships[2].author.display_name | Will Corcoran |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Corcoran, Will |
| authorships[2].is_corresponding | False |
| authorships[3].author.id | https://openalex.org/A5029380651 |
| authorships[3].author.orcid | |
| authorships[3].author.display_name | Misha Sra |
| authorships[3].author_position | middle |
| authorships[3].raw_author_name | Sra, Misha |
| authorships[3].is_corresponding | False |
| authorships[4].author.id | https://openalex.org/A5036639779 |
| authorships[4].author.orcid | https://orcid.org/0000-0002-1997-7140 |
| authorships[4].author.display_name | Ambuj K. Singh |
| authorships[4].author_position | last |
| authorships[4].raw_author_name | Singh, Ambuj K. |
| authorships[4].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/2406.16176 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2024-06-26T00:00:00 |
| display_name | GraphEval36K: Benchmarking Coding and Reasoning Capabilities of Large Language Models on Graph Datasets |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T10028 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9987000226974487 |
| 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 | Topic Modeling |
| related_works | https://openalex.org/W4391375266, https://openalex.org/W2748952813, https://openalex.org/W4238897586, https://openalex.org/W435179959, https://openalex.org/W2619091065, https://openalex.org/W2059640416, https://openalex.org/W1490753184, https://openalex.org/W2284465472, https://openalex.org/W2291782699, https://openalex.org/W1993948687 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2406.16176 |
| 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/2406.16176 |
| 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/2406.16176 |
| primary_location.id | pmh:oai:arXiv.org:2406.16176 |
| 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/2406.16176 |
| 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/2406.16176 |
| publication_date | 2024-06-23 |
| publication_year | 2024 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 79 |
| abstract_inverted_index.40 | 50 |
| abstract_inverted_index.We | 41, 87, 103 |
| abstract_inverted_index.an | 138 |
| abstract_inverted_index.by | 165 |
| abstract_inverted_index.in | 8, 16, 28 |
| abstract_inverted_index.is | 69, 101 |
| abstract_inverted_index.of | 62, 85, 108, 117, 128, 159 |
| abstract_inverted_index.on | 64, 146 |
| abstract_inverted_index.to | 31, 58, 77, 124, 142 |
| abstract_inverted_index.vs | 112 |
| abstract_inverted_index.we | 132 |
| abstract_inverted_index.LLM | 144 |
| abstract_inverted_index.Our | 67 |
| abstract_inverted_index.SSD | 153 |
| abstract_inverted_index.and | 18, 34, 54, 74, 120, 163, 169 |
| abstract_inverted_index.gap | 100 |
| abstract_inverted_index.our | 129 |
| abstract_inverted_index.ten | 89 |
| abstract_inverted_index.the | 44, 60, 99, 106, 126, 155 |
| abstract_inverted_index.LLMs | 63, 109 |
| abstract_inverted_index.also | 104 |
| abstract_inverted_index.four | 75 |
| abstract_inverted_index.have | 4, 25 |
| abstract_inverted_index.into | 71 |
| abstract_inverted_index.rate | 158 |
| abstract_inverted_index.show | 151 |
| abstract_inverted_index.test | 56 |
| abstract_inverted_index.text | 20 |
| abstract_inverted_index.that | 92, 152 |
| abstract_inverted_index.LLMs' | 29 |
| abstract_inverted_index.LLMs, | 90 |
| abstract_inverted_index.Large | 0 |
| abstract_inverted_index.about | 36 |
| abstract_inverted_index.cases | 57 |
| abstract_inverted_index.data, | 38 |
| abstract_inverted_index.data. | 21 |
| abstract_inverted_index.eight | 72 |
| abstract_inverted_index.first | 45 |
| abstract_inverted_index.graph | 47, 51, 65, 118, 148 |
| abstract_inverted_index.kinds | 116 |
| abstract_inverted_index.ones, | 97 |
| abstract_inverted_index.types | 84 |
| abstract_inverted_index.(LLMs) | 3 |
| abstract_inverted_index.(NLP), | 12 |
| abstract_inverted_index.(SSD), | 137 |
| abstract_inverted_index.29.28% | 168 |
| abstract_inverted_index.36,900 | 55 |
| abstract_inverted_index.6.78%, | 167 |
| abstract_inverted_index.8.38%, | 166 |
| abstract_inverted_index.GPT-4, | 160 |
| abstract_inverted_index.across | 82, 110 |
| abstract_inverted_index.coding | 52 |
| abstract_inverted_index.ensure | 78 |
| abstract_inverted_index.method | 140 |
| abstract_inverted_index.models | 2, 94 |
| abstract_inverted_index.reason | 35 |
| abstract_inverted_index.recent | 23 |
| abstract_inverted_index.tasks. | 149 |
| abstract_inverted_index.though | 98 |
| abstract_inverted_index.25.28%, | 170 |
| abstract_inverted_index.GPT-4o, | 161 |
| abstract_inverted_index.Results | 150 |
| abstract_inverted_index.ability | 30, 61 |
| abstract_inverted_index.analyze | 105 |
| abstract_inverted_index.average | 156 |
| abstract_inverted_index.complex | 147 |
| abstract_inverted_index.dataset | 68 |
| abstract_inverted_index.enhance | 143 |
| abstract_inverted_index.finding | 91 |
| abstract_inverted_index.graphs, | 114 |
| abstract_inverted_index.graphs. | 40, 86 |
| abstract_inverted_index.improve | 125 |
| abstract_inverted_index.models. | 122 |
| abstract_inverted_index.natural | 9 |
| abstract_inverted_index.network | 121 |
| abstract_inverted_index.passing | 157 |
| abstract_inverted_index.primary | 73 |
| abstract_inverted_index.private | 93 |
| abstract_inverted_index.propose | 133 |
| abstract_inverted_index.studies | 24 |
| abstract_inverted_index.success | 7 |
| abstract_inverted_index.However, | 22 |
| abstract_inverted_index.Symbolic | 135 |
| abstract_inverted_index.achieved | 5 |
| abstract_inverted_index.dataset, | 48 |
| abstract_inverted_index.designed | 141 |
| abstract_inverted_index.directed | 111 |
| abstract_inverted_index.evaluate | 59 |
| abstract_inverted_index.improves | 154 |
| abstract_inverted_index.language | 1, 10 |
| abstract_inverted_index.problems | 53 |
| abstract_inverted_index.program, | 33 |
| abstract_inverted_index.thorough | 80 |
| abstract_inverted_index.benchmark | 88 |
| abstract_inverted_index.concepts, | 119 |
| abstract_inverted_index.different | 83, 115 |
| abstract_inverted_index.introduce | 42 |
| abstract_inverted_index.usability | 127 |
| abstract_inverted_index.Gemini-Pro | 162 |
| abstract_inverted_index.Structured | 134 |
| abstract_inverted_index.comprising | 49 |
| abstract_inverted_index.especially | 39 |
| abstract_inverted_index.evaluation | 81, 130 |
| abstract_inverted_index.framework, | 131 |
| abstract_inverted_index.identified | 26 |
| abstract_inverted_index.narrowing. | 102 |
| abstract_inverted_index.outperform | 95 |
| abstract_inverted_index.processing | 11, 17 |
| abstract_inverted_index.remarkable | 6 |
| abstract_inverted_index.structured | 37 |
| abstract_inverted_index.undirected | 113 |
| abstract_inverted_index.categorized | 70 |
| abstract_inverted_index.limitations | 27 |
| abstract_inverted_index.manipulate, | 32 |
| abstract_inverted_index.open-source | 96 |
| abstract_inverted_index.performance | 107, 145 |
| abstract_inverted_index.significant | 14 |
| abstract_inverted_index.Furthermore, | 123 |
| abstract_inverted_index.capabilities | 15 |
| abstract_inverted_index.Decomposition | 136 |
| abstract_inverted_index.GraphEval36K, | 43 |
| abstract_inverted_index.comprehensive | 46 |
| abstract_inverted_index.demonstrating | 13 |
| abstract_inverted_index.respectively. | 171 |
| abstract_inverted_index.understanding | 19 |
| abstract_inverted_index.sub-categories | 76 |
| abstract_inverted_index.Claude-3-Sonnet | 164 |
| abstract_inverted_index.problem-solving. | 66 |
| abstract_inverted_index.instruction-based | 139 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 5 |
| citation_normalized_percentile |