In this work, we implement a message-passing graph neural network potential within an active-learning framework to tackle the complexity of reduced rutile TiO2 surfaces . This approach enables efficient exploration of a wide range of reconstructed surface terminations, extending beyond what is feasible with conventional DFT methods while retaining DFT-level accuracy. Through MLIPassisted aggressive sampling, we successfully identify numerous stable reconstructions, including a novel subsurface shear plane, marking the first theoretical discovery of this structure. We note that such reconstructions have been seen in the experiment , but the theory was unable to reach them or give atomistic insight. We further examine the electronic properties of this unique surface and validate our findings with experimental data.