Researchers urgently seek novel antibiotics amidst the ongoing antibiotic resistance crisis. This study introduces a deep learning-guided approach, combining machine learning and explainable graph algorithms, to explore chemical spaces for potential antibiotics. Testing over 12 million compounds, the team identified substructure-based rationales for antibiotic activity and low cytotoxicity. Empirical testing revealed a promising compound with selective activity against drug-resistant strains, demonstrating the potential of this approach in explaining and discovering new antibiotic structural classes.