Graph Gen Benchmark Eval

graph-gen-benchmark-eval

Graph Generative Model for Benchmarking Graph Neural Networks — Minji Yoon et al. (2022) (arXiv:2207.04396, 2022)

What this evaluates

This benchmark evaluates how effectively graph generative models can produce synthetic graphs that serve as reliable proxies for benchmarking Graph Neural Networks. It measures the fidelity of generated graphs by comparing GNN performance metrics trained on synthetic data against those trained on the original real-world graphs.

Datasets

• Cora, Citeseer, Pubmed, AmazonC, AmazonP, MS CS, MS Physic — total ?; splits: train|val|test (-1); repo https://github.com/minjiyoon/CGT

Metrics

• MSE (primary) — range: other
  • Mean Square Error between GNN accuracy on the original graph and GNN accuracy on the synthetic graph across all evaluated GNN models and datasets. Lower values indicate better benchmark reproduction.
• Pearson — range: other
  • Pearson correlation coefficient measuring the linear relationship between GNN performance scores on original versus synthetic graphs. Higher values indicate better preservation of performance rankings.
• Spearman — range: other
  • Spearman rank correlation coefficient measuring the monotonic relationship between GNN performance rankings on original versus synthetic graphs. Higher values indicate better preservation of relative model performance.

Input / output format

Input: Original graph data consisting of adjacency matrices and node feature matrices, or pre-extracted duplicate-encoded computation graphs with fixed adjacency structures.

Output: Synthetic graph data (adjacency matrix and node feature matrix) or generated computation graphs that can be fed into GNN training pipelines.

Scoring recipe

def compute_benchmark_metrics(original_graphs, synthetic_graphs, gnn_models):
    orig_accs = []
    synth_accs = []
    for orig, synth in zip(original_graphs, synthetic_graphs):
        for model in gnn_models:
            orig_accs.append(model.evaluate(orig))
            synth_accs.append(model.evaluate(synth))
    mse = sum((o - s)**2 for o, s in zip(orig_accs, synth_accs)) / len(orig_accs)
    pearson = pearson_correlation(orig_accs, synth_accs)
    spearman = spearman_correlation(orig_accs, synth_accs)
    return mse, pearson, spearman

Common pitfalls

• Baselines designed for small molecule graphs often fail to converge or collapse to uniform node predictions when applied to large-scale citation/co-authorship graphs with high-dimensional features.
• Stronger privacy guarantees (e.g., lower epsilon in DP) do not automatically preserve benchmark effectiveness; careful tuning or alternative methods like K-anonymity are required to maintain low MSE and high correlations.
• Re-identification probability metrics alone do not capture benchmark utility; a method can have low re-identification risk but still produce graphs that yield poor GNN performance rankings.

Evidence (verbatim from paper)

In this experiment, each graph generative model learns the distributions of 7 graph datasets and generates synthetic graphs. Then we train and evaluate 9 GNN models on each pair of original and synthetic graphs, and measure Mean Square Error (MSE) and Pearson/Spearman correlations between the GNN performance on each pair of graphs.

Citation

@misc{yoon2022graph,
  title={Graph Generative Model for Benchmarking Graph Neural Networks},
  author={Minji Yoon et al. (2022)},
  year={2022},
  note={arXiv:2207.04396}
}

• arXiv: 2207.04396