Novel drug lead identification is a key challenge in the development of new therapies against cancer. While natural compounds were initially preferred for their evolutionary honed properties, high-throughput screening shifted focus to synthetic compounds. This approach, however, has resulted in limited success so far. As a result, recent years have seen a revival of natural products as promising sources for lead discovery. We posit that the recent developments in computational network-based methods for drug development can further push the revival of natural product-based drug discovery. In this dissertation, we introduce novel approaches for therapeutic lead discovery using graph-based deep learning methods. The first part of this dissertation explores the use of graph-based deep learning methods to predict therapeutic leads from molecules found in foods, either as single agents or in combination with existing anticancer drugs. Our results show promise for the exploration of natural compounds and their relationships with drugs across other diseases. In the second part of this dissertation, we outline the limitations of the current lead discovery problem formulation and propose a novel problem formulation that overlaps with lead design, therefore expanding the search space. To solve this problem formulation, we introduce an algorithm that combines the rigor of causal inference with the representation power of graph neural networks. Our algorithm predicts perturbagens that shift cell states from an initial to a desired target state across various genetic and chemical perturbation datasets and opens the door for the development of new, more flexible methods, for lead discovery. By introducing a fresh problem formulation for lead discovery, this dissertation sets the stage for more nuanced and effective strategies to lead discovery in cancer research.