Geographic entities from the vertical aerial images can be viewed as discrete objects and represented as nodes in a graph, linked to each other by edges capturing their spatial relationships. Over time, the natural and man made landscape may evolve and thus also their graph representations. This paper addresses the challenging problem of the retrieval and fuzzy matching of graphs to localize near-identical geographical areas across time. Several use-case scenarios are proposed for the end-to-end learning of a graph embedding using Graph Neural Networks (GNN), along with an effective baseline without learning. The results demonstrate the efficiency of our approach, that enables efficient similarity reasoning for novel hand-engineered cross-time graph data. Code and data processing scripts are available online 1 .