Theoretical Analysis

A.1 Graph Spectrum Consider an undirected graph G =( V,E)whose adjacency matrix is symmetric. Following notations in Section 2, we denote the eigendecomposition of the normalized graph adjacency and Laplacian matrices respectively as A = UMU > and L = VNV >, where M = diag(µ1,,µn), |µ1| |µ2| | µn|, N = diag( 1,, n), 0= 1 < 2 n, and U,V are the matrices of corresponding eigenvectors. We also immediately have A2 = UM 2U> = U U>, f = |µf |2. Intuitively, since L = I A, the leading eigenvalues µ1,µ2, of A correspond to the smallest of those 1, 2, of L. These eigenvalues are known as the low-frequency spectrum of the graph that correlates to graph connectivity. Specially, 2 > 0if and only if the graph is connected, which is our case. Similarly, small values of µf and large values of i represent the high frequency part of the graph. Graph spectrum is a graph invariant despite the status of node labels. We plot the spectrum computed by A2Prop of 7 heterophilous graphs and 2 homophilous graphs in Figure 4, which shows the leading k eigenvalues µ1,µ2,,µk. The figure indicates the importance of high-frequency information in graphs under heterophily. For appropriately large heterophilous graphs penn94, arxiv-year, genius, and twitch-gamers, the spectrum converges slowly to 0. In other words, even high-frequency parts with large f still exhibit relatively large eigenvalues compared to the dominant µ1. In contrast, the homophilous protein and reddit are significant in low frequency of a few eigenvalues. Hence, during the iterative propagation, the topology information carried by these high-frequency components can be preserved to enhance performance.