Combining domain knowledge with AI and Network Science can enable more effective solutions to complex health challenges at various levels: within individuals (e.g., brain networks), networks of individuals, and networks of populations. While many AI/ML tools exist, off-the-shelf methods often yield suboptimal results, especially when network structures shape underlying processes. Addressing problems in health requires not just computational techniques but also an understanding of data and underlying dynamics. In this talk, I will illustrate this through two projects. The first project was a collaboration with a youth center focused on reducing violence among youth experiencing homelessness. The goal was to identify individuals to recruit in a series of mindfulness workshops who can act as peer change agents to counter overall violence in the community. We collected data on the network (who is influenced by whom) and personal attributes. We developed the "uncertain voter model" to capture the dynamics of violence and non-violence. We developed algorithms to identify the optimal set of peer leaders, taking into account the propensity for accepting intervention, a key aspect missing in prior work. Our pilot study at a youth shelter showed a significant reduction in violence and an increase in mindfulness practice. In the second project, we showed how to predict the emergence of COVID-19 variants by combining dynamics and GNNs. First, we derived the dynamics of variant prevalence across pairs of regions (countries) that apply to a large class of epidemic models. The dynamics motivated the introduction of certain features in the GNN. We demonstrated that our proposed dynamics-informed GNN outperforms all the baselines, including the currently pervasive framework of Physics-Informed Neural Networks (PINNs). Motivated by these projects, we will conclude the talk by highlighting new opportunities in this interdisciplinary area. We will discuss how GNNs, mechanistic models, and optimization algorithms can help address challenges in infectious diseases, mental health, substance use, and HIV-related behavior.