The present disclosure describes approaches to camera re-localization using a graph neural network (GNN). A re-localization model includes encoding an input image into a feature map. The model retrieves reference images from an image database of a previously scanned environment based on the feature map of the image. The model builds a graph based on the image and the reference images, wherein nodes represent the image and the reference images, and edges are defined between the nodes. The model may iteratively refine the graph through auto-aggressive edge-updating and message passing between nodes. With the graph built, the model predicts a pose of the image based on the edges of the graph. The pose may be a relative pose in relation to the reference images, or an absolute pose.