Seasonal-to-decadal climate prediction is crucial for decision-making in a number of industries, but forecasts on these timescales have limited skill. Here, we develop a data-driven method for selecting optimal analogs for seasonal-to-decadal analog forecasting. Using an interpretable neural network, we learn a spatially-weighted mask that quantifies how important each grid point is for determining whether two climate states will evolve similarly. We show that analogs selected using this weighted mask provide more skillful forecasts than analogs that are selected using traditional spatially-uniform methods. This method is tested on two prediction problems within a perfect model framework using the Max Planck Institute for Meteorology Grand Ensemble: multi-year prediction of North Atlantic sea surface temperatures, and seasonal prediction of El Niño Southern Oscillation. This work demonstrates a methodical approach to selecting analogs that may be useful for improving seasonal-to-decadal forecasts and understanding their sources of skill.