In this work, we successfully utilized message-passing graph neural network potentials within an active learning framework to investigate the surface reconstructions of reduced rutile TiO2(110). Our MLIP-MACE approach significantly reduced the computational cost of exploring complex surface reconstructions compared to DFT calculations, enabling the discovery of several novel and stable surface configurations, including a shear plane-induced reconstruction not previously reported. These findings were confirmed experimentally, providing full atomistic incite into the reconstructed surfaces.