Attention Mechanisms in Physics-Inspired Graph Neural Networks for the Max-Cut Problem

Abstract

Physics-Inspired Graph Neural Networks (PI-GNNs) reformulate MAX-CUT as QUBO energy minimization, training a GNN to produce soft binary node assignments without labeled data. The baseline PI-GCN uses static, degree-normalized aggregation, while its attention-augmented counterpart PI-GAT---built on GATv2---introduces additional hyperparameters whose effects remain uncharacterized. This paper addresses that gap through controlled experiments on five Gset benchmark graphs (800--10,000 nodes). The first experiment examines how attention dropout p_attn affects solution quality and convergence stability across 25 seeds per configuration. The second sweeps depth from 1 to 20 layers, quantifying oversmoothing via Dirichlet energy, cosine similarity, and mean absolute deviation. On dense graphs (average degree 10), dropout in [0.10, 0.20] reduces inter-run variance by 30--41% while improving best-cut value; on the sparse graph G70 (average degree 2, diameter 34), any dropout is detrimental. PI-GAT delays oversmoothing onset by one to two layers versus PI-GCN, at 1.5-1.8x computational overhead per layer. These findings establish graph density and diameter as the primary structural determinants of whether dynamic attention benefits the PI-GNN framework.