Teleconnections are recurring patterns in climate anomalies connecting two regions that are far apart from each other and represent the heartbeat of a climate system. They are known to impact and explain the climate variability in many regions of the world and form a critical missing link in the understanding of the atmosphere-ocean interactions and the global climate system. We provide systematic data guided approaches to find such relationships. We presented a graph based approach that generates a single snapshot picture of all the teleconnections on the globe and hence it enables us to precisely study the interactions and changes in behavior over time. It also allows us to discover potentially new connections not known to climate scientists do far. A larger significance of this work, which might impact how climate scientists perceive the climate indices, is that we show that some of the dynamic dipoles defined using our approach (e.g. NAO and ENSO) have a much correlation withglobal temperature anomalies as compared to the static indices. Data guided approaches offer a huge potential for characterizing and discovering unknown relationships and thus advancing climate science.