BA graph

Predict an optimal combinatorial-objective value in the supervised protocol, or learn node scores that a problem-specific decoder turns into a feasible solution in the unsupervised protocol. GraphBench covers maximum independent set, max-cut, and graph coloring.

Synthetic Barabási–Albert preferential-attachment graphs are generated in small and large regimes. The generator controls graph size and the number of edges attached by each newly added node; GraphBench reports 50,000 instances per dataset.

The released problem graphs contain no node or edge features. Their topology is the input; labels or training losses depend on the selected optimization problem and protocol.

Supervised experiments predict the solver-derived optimum and report MAE. Unsupervised experiments minimize a differentiable surrogate, decode node scores to a feasible solution, and evaluate that solution’s objective value.

BA graph names a graph generator, not one classification target. Results must identify the optimization problem, small or large regime, and supervised or unsupervised protocol. Solver-derived labels become expensive and potentially status-dependent for hard instances.