Graph-of-Differences (GoD) introduces anatomy-graph representations to enable medical image re-identification with explicit structural grounding. It computes differences across named anatomical regions and aligns them with global backbone differences, providing clinically auditable, structure-level explanations. GoD improves Rank-1 accuracy by 7.1 pp on fundus and 3.1 pp on CXR, with better performance on zero-shot transfers.