ER graph

Graph regression Predict an optimal combinatorial-objective value in the supervised protocol, or learn node scores decoded into feasible solutions in the unsupervised protocol. Graphs have no supplied node or edge features, so topology is the model input. Evaluated by MAE.

Dataset details

Task

Predict an optimal combinatorial-objective value in the supervised protocol, or learn node scores decoded into feasible solutions in the unsupervised protocol. The included problems are maximum independent set, max-cut, and graph coloring.

Data

Synthetic Erdős–Rényi graphs are sampled in small and large regimes by controlling node count and independent edge probability. GraphBench reports 50,000 instances per dataset.

Features

Graphs have no supplied node or edge features, so topology is the model input. Targets and surrogate losses are problem-specific rather than properties of the ER generator itself.

Splits and evaluation

The supervised benchmark reports MAE on optimum values obtained with conventional solvers. The unsupervised benchmark evaluates the objective value after a problem-specific decoder enforces feasibility.

Quirks and pitfalls

ER graph is a generator family, not a single graph-classification dataset. Density strongly controls difficulty, and comparisons are meaningful only when problem, scale, generator parameters, split, and learning protocol match.

Sources

SOTA Progression

new SOTA matches SOTA at that time other proposed result other baseline result

Leaderboard

#	Model	Accuracy ↑	Paper
1	Diffusion Wavelets GNN ★ proposed	0.9300	KDD 2017 Learning Structural Node Embeddings via Diffusion Wavelets no code KDD 2017 Oct 2017 Oct '17
2	GraphSAGE GNN baseline	0.8800	KDD 2017 Learning Structural Node Embeddings via Diffusion Wavelets no code KDD 2017 Oct 2017 Oct '17
3	GCN GNN baseline	0.8500	KDD 2017 Learning Structural Node Embeddings via Diffusion Wavelets no code KDD 2017 Oct 2017 Oct '17
4	Node2Vec Walk baseline	0.7200	KDD 2017 Learning Structural Node Embeddings via Diffusion Wavelets no code KDD 2017 Oct 2017 Oct '17
5	DeepWalk Walk baseline	0.7000	KDD 2017 Learning Structural Node Embeddings via Diffusion Wavelets no code KDD 2017 Oct 2017 Oct '17

SOTA performance set a new SOTA at the time matched the SOTA at the time

Structure

Coverage