Graph Alignment Eval

graph-alignment-eval

Graph Alignment for Benchmarking Graph Neural Networks and Learning Positional Encodings — Lagesse et al. (2025) (arXiv:2505.13087, 2025)

What this evaluates

Evaluates a model's ability to perform structural graph alignment by predicting a node-to-node correspondence between two graphs that maximizes shared edges. It probes the model's capacity for equivariant representation learning and combinatorial optimization on graph structures.

Datasets

• Graph Alignment Benchmark (Synthetic & Real-world) — total ?; splits: test (-1)

Metrics

• Accuracy (primary) — range: percent
  • Percentage of correctly mapped nodes between the predicted permutation and the ground truth alignment.

Input / output format

Input: Pair of graphs (G, G_tilde) with N vertices each, represented by edge_index tensors and constant node features (e.g., all 1s).

Output: Similarity matrix Sigma in R^{N x N}, from which a permutation is extracted via the Hungarian algorithm.

Scoring recipe

def compute_accuracy(pred_perm, true_perm):
    correct = sum(1 for i in range(len(true_perm)) if pred_perm[i] == true_perm[i])
    return (correct / len(true_perm)) * 100

Common pitfalls

• The exact Graph Alignment Problem is NP-hard, so ground truth permutations are typically generated synthetically rather than computed from arbitrary graphs.
• Evaluation relies on solving a continuous relaxation (similarity matrix) via the Hungarian algorithm, which may not perfectly recover the discrete ground truth if the model's output is noisy.
• Node features are explicitly set to constants to isolate structural understanding, which differs from standard GNN benchmarks that rely on rich node attributes.

Evidence (verbatim from paper)

During evaluation, we extract a permutation from Sigma by solving the Linear Assignment Problem (see [2]), which maximizes the overall similarity. Accuracy is defined as the percentage of correctly mapped nodes.

Citation

@misc{lagesse2025graphalignment,
  title={Graph Alignment for Benchmarking Graph Neural Networks and Learning Positional Encodings},
  author={Lagesse et al. (2025)},
  year={2025},
  note={arXiv:2505.13087}
}

• arXiv: 2505.13087