In many applications of graph-based methods, from evolutionary biology to machine learning, we need to understand what makes two graphs similar. Likewise, if we want to analyse dynamical processes on graphs, we must quantify change. However, it is not at all obvious how to measure the distance between two graphs. In many situations, naive approaches such as graph edit distance are neither semantically adequate nor computationally feasible. In my talk, I will discuss fundamentally diferent approaches to measuring the distance between two graphs, highlighting algorithmic aspects and connections between these approaches.