RB graph

Graph regression Predict the optimal objective value for maximum independent set in the supervised setting, or train node scores with differentiable surrogates and feasibility-preserving decoders for maximum independent set, max-cut, and graph coloring. Evaluated by MAE.

Dataset details

Task

Predict the optimal objective value for maximum independent set in the supervised setting, or train node scores with differentiable surrogates and feasibility-preserving decoders for maximum independent set, max-cut, and graph coloring.

Data

RB-model instances contain n groups of k vertices and use a constraint-tightness parameter p; GraphBench rejection-samples to keep graph sizes in configured ranges and provides small and large variants with 50,000 instances per dataset.

Features

The graphs contain no node or edge attributes. Topology encodes the optimization instance and solver outputs supply supervised optimum-value labels where available.

Splits and evaluation

Supervised objective prediction is evaluated by MAE. In unsupervised runs, the decoded feasible solution is scored by its achieved objective rather than classification accuracy.

Quirks and pitfalls

RB means the RB random constraint graph model, not random bipartite graph. Its planted group structure and tuned hardness parameters differ materially from ER and BA; report the problem, size regime, and learning protocol.

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.8500	KDD 2017 Learning Structural Node Embeddings via Diffusion Wavelets no code KDD 2017 Oct 2017 Oct '17
2	GraphSAGE GNN baseline	0.8100	KDD 2017 Learning Structural Node Embeddings via Diffusion Wavelets no code KDD 2017 Oct 2017 Oct '17
3	GCN GNN baseline	0.7800	KDD 2017 Learning Structural Node Embeddings via Diffusion Wavelets no code KDD 2017 Oct 2017 Oct '17
4	Node2Vec Walk baseline	0.6200	KDD 2017 Learning Structural Node Embeddings via Diffusion Wavelets no code KDD 2017 Oct 2017 Oct '17
5	DeepWalk Walk baseline	0.6000	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