Triple-negative breast cancer (TNBC) is an aggressive subtype lacking targeted therapies, leading to high relapse rates and poor prognoses. Here, we aimed to identify a synergistic herb pair against TNBC by integrating graph neural networks (GNNs) and a multiscale interactome. We curated TNBC-related biomarkers and constructed an herb–compound–target–disease network by integrating multiple data sources. Using this dataset, we trained and evaluated three GNN architectures—graph convolutional network (GCN), graph attention network, and graph sample-and-aggregate (GraphSAGE)—on 6830 herb pairs annotated with compound and target information. We then applied a biased random walk algorithm to estimate the network effect of herb targets and TNBC-related proteins, identifying new herbal candidates with potential synergy. Among the tested GNNs, GraphSAGE showed the highest performance in distinguishing known versus unknown herb pairs, with significant accuracy gains (p < 0.001). We subsequently performed diffusion profile analysis on top-ranked herbal combinations, revealing key TNBC targets, such as AKT1 and TP53. This multiscale approach illuminated potential synergistic effects within herbal therapies for TNBC. Our findings demonstrate that integrating GNN-driven deep learning with network pharmacology can systematically uncover multi-target herbal therapies for TNBC. Moreover, the molecular network we present can guide the design of materials for the rapid screening of herb–target interactions, aligning this work with emerging sensing technologies.