Mastering Long-Tail Complexity on Graphs: Characterization, Learning, and Generalization