We develop graph-based surrogate models to predict strain localization in 2D elastic-perfectly plastic porous solids at limit load. Plastic deformation is represented using a Delaunay graph, where nodes correspond to void centers, edges represent potential shear bands, and edge values encode the local integral of the plastic work rate (PWR). Two edge-regression GNN models are built. The first is a purely data-driven model (DDM) that maps local geometric features – edge length and orientation – to PWR. The second is a hybrid model (HM) that augments the GNN with a mechanistic prior from a limit load analysis model (LLAM) and learns a correction to its upper-bound bias. The models are trained on a dataset of 1200 representative volume elements with 20% porosity. The DDM can reliably reconstruct shear band patterns, but its accuracy deteriorates when applied to porosity values different from that seen in training. The HM, like the LLAM, does not fully capture the spatial pattern, but it removes the LLAM systematic bias and achieves uniformly low errors in total work rate for porosities ranging from 10% to 30%. Moreover, the HM requires less training data than the DDM and is more robust across random seeds. These results show that coupling a GNN with a physics-based prior yields a fast and data-efficient surrogate that preserves accuracy in macroscopic quantities while retaining meaningful spatial information, offering a practical route to accelerate micro-mechanical analyses and reduce reliance on expensive finite element simulations.