  Graph neural networks (GNNs) realize great success in graph learning but
suffer from performance loss when meeting heterophily, i.e. neighboring nodes
are dissimilar, due to their local and uniform aggregation. Existing attempts
of heterophilous GNNs incorporate long-range or global aggregations to
distinguish nodes in the graph. However, these aggregations usually require
iteratively maintaining and updating full-graph information, which limits their
efficiency when applying to large-scale graphs. In this paper, we propose
SIGMA, an efficient global heterophilous GNN aggregation integrating the
structural similarity measurement SimRank. Our theoretical analysis illustrates
that SIGMA inherently captures distant global similarity even under
heterophily, that conventional approaches can only achieve after iterative
aggregations. Furthermore, it enjoys efficient one-time computation with a
complexity only linear to the node set size $\mathcal{O}(n)$. Comprehensive
evaluation demonstrates that SIGMA achieves state-of-the-art performance with
superior aggregation and overall efficiency. Notably, it obtains 5$\times$
acceleration on the large-scale heterophily dataset \emph{pokec} with over 30
million edges compared to the best baseline aggregation.
