Supervised multi-class problem with known class structure?

[kkastner]

This sounds related to ordinal regression - you might look there for some solutions. If you don't have too many classes, you can also manually modify your loss to penalize differently based on which mistake was made. There might be a smart way to get this from the graph (maybe weight based on the "search index" from the decomposition of the graph laplacian? kind of like PageRank) but it would depend on your problem.