Gracore Eval

gracore-eval

GraCoRe: Benchmarking Graph Comprehension and Complex Reasoning in Large Language Models — Yuan et al. (2024) (arXiv:2407.02936, 2024)

What this evaluates

Evaluates large language models' ability to comprehend and reason over graph structures presented as textual descriptions. It probes capabilities ranging from basic graph understanding and semantic reasoning to complex graph theory reasoning across pure and heterogeneous graphs.

Datasets

• GraCoRe — total 5140; splits: test (-1); repo https://github.com/ZIKEYUAN/GraCoRe

Metrics

• score (primary) — range: other
  • Task-specific accuracy or F1 score computed per instance, aggregated across 19 tasks and capability dimensions. The paper reports a total aggregate score and average z-scores across models.

Input / output format

Input: Textual descriptions of graph structures (nodes, edges, and optionally semantic attributes like titles/abstracts for heterogeneous graphs). Node identifiers are provided either in sequential order or randomly sorted.

Output: Predictions corresponding to the specific task type (e.g., node classification labels, path sequences, or graph property values). Exact formatting is task-dependent.

Scoring recipe

def compute_gracore_score(predictions, golds, task_type):
    if task_type in ['classification', 'node_classification']:
        return sum(p == g for p, g in zip(predictions, golds)) / len(golds)
    elif task_type in ['path_finding', 'graph_theory']:
        return exact_match_score(predictions, golds)
    # Aggregate across 19 tasks and capability dimensions
    return aggregate_scores(task_results)

Common pitfalls

• Node ordering significantly impacts performance; random sorting degrades results compared to sequential sorting, especially for path reasoning tasks.
• Models optimized for long-context processing do not automatically excel at graph reasoning and may underperform compared to standard models.
• Performance heavily depends on semantic context; removing titles/abstracts from heterogeneous graphs causes significant drops for some models.

Evidence (verbatim from paper)

Tables [3] and [4] present the performance of various LLMs across 19 tasks in the GraCoRe benchmark. Models generally performed better on graph understanding tasks, while graph reasoning proved more challenging. Closed-source models, particularly OpenAI o1, excelled in both areas, achieving the highest score of 1403.8, significantly surpassing other closed-source models.

Citation

@misc{yuan2024gracore,
  title={GraCoRe: Benchmarking Graph Comprehension and Complex Reasoning in Large Language Models},
  author={Yuan et al. (2024)},
  year={2024},
  note={arXiv:2407.02936}
}

• arXiv: 2407.02936