Graph data is ubiquitous in many application domains, including in material science and molecular biology. The rapid advancements in machine learning also lead to different graph learning frameworks, such as message passing (graph) neural networks (MPNNs), graph transformers and higher order variants. In this talk, I will describe some of our recent journeys in attempting to provide better (theoretical) understanding of these graph learning models (e.g, their representation power and limitations in capturing long range interactions in graphs), the pros and cons of different models, and ways to further enhance them in practice. This talk is based on multiple joint work with various collaborators, whom I will mention in the talk.