  Homophily principle, i.e., nodes with the same labels are more likely to be
connected, has been believed to be the main reason for the performance
superiority of Graph Neural Networks (GNNs) over Neural Networks on node
classification tasks. Recent research suggests that, even in the absence of
homophily, the advantage of GNNs still exists as long as nodes from the same
class share similar neighborhood patterns. However, this argument only
considers intra-class Node Distinguishability (ND) but neglects inter-class ND,
which provides incomplete understanding of homophily on GNNs. In this paper, we
first demonstrate such deficiency with examples and argue that an ideal
situation for ND is to have smaller intra-class ND than inter-class ND. To
formulate this idea and study ND deeply, we propose Contextual Stochastic Block
Model for Homophily (CSBM-H) and define two metrics, Probabilistic Bayes Error
(PBE) and negative generalized Jeffreys divergence, to quantify ND. With the
metrics, we visualize and analyze how graph filters, node degree distributions
and class variances influence ND, and investigate the combined effect of intra-
and inter-class ND. Besides, we discovered the mid-homophily pitfall, which
occurs widely in graph datasets. Furthermore, we verified that, in real-work
tasks, the superiority of GNNs is indeed closely related to both intra- and
inter-class ND regardless of homophily levels. Grounded in this observation, we
propose a new hypothesis-testing based performance metric beyond homophily,
which is non-linear, feature-based and can provide statistical threshold value
for GNNs' the superiority. Experiments indicate that it is significantly more
effective than the existing homophily metrics on revealing the advantage and
disadvantage of graph-aware modes on both synthetic and benchmark real-world
datasets.
