proofs

A.1 Proof of Theorem 1 Before proofing Theorem 1, We first demonstrate the superiority of even-hop neighbors over odd-hop neighbors from the perspective of random walks. In a binary node classification task, denote the probability of a random walk of length k that starts and ends with nodes of the same label as pk,k > 0. Suppose the edge homophily level his a random variable that belongs to a uniform distribution in [0,1] and p1 = h, then: Lemma 1. If k is odd, Eh[pk] = 12. If k is even, Eh[pk] 12. Proof. We now provide a brief discussion of the superiority of even-hop neighbors in multi-class node classification tasks following [14].