Was thinking that the adjacency matrix that describes the graph you extract from the image will produce a string you can chunk and do a fast search on, and then it's a standard similarity/distance string search in Redis, or a probabilistic filter.
The compute on the indexing images would be relatively expensive, but the speed of a similarity search would be super fast, with the caveat that I don't know how image search is done today, and it probably should do something like this anyway.
The graph idea could work, but the algorithm produces slightly different results each time it is ran. It still could be really interesting to try!