2024/01/17 by Junfu Wang, Wang, Junfu, Yuanfang Guo +5 · 1 citation
Computer Science · #Advanced Graph Neural Networks #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and ELM #Neural Networks and Applications
paper · pdf · doi:10.48550/arxiv.2401.09125
openalex publication_date 2024/01/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Graphs with heterophily have been regarded as challenging scenarios for Graph Neural Networks (GNNs), where nodes are connected with dissimilar neighbors through various patterns. In this paper, we present theoretical understandings of the impacts of different heterophily patterns for GNNs by incorporating the graph convolution (GC) operations into fully connected networks via the proposed Heterophilous Stochastic Block Models (HSBM), a general random graph model that can accommodate diverse heterophily patterns. Firstly, we show that by applying a GC operation, the separability gains are determined by two factors, i.e., the Euclidean distance of the neighborhood distributions and √(𝔼[deg]), where 𝔼[deg] is the averaged node degree. It reveals that the impact of heterophily on classification needs to be evaluated alongside the averaged node degree. Secondly, we show that the topological noise has a detrimental impact on separability, which is equivalent to degrading 𝔼[deg]. Finally, when applying multiple GC operations, we show that the separability gains are determined by the normalized distance of the l-powered neighborhood distributions. It indicates that the nodes still possess separability as l goes to infinity in a wide range of regimes. Extensive experiments on both synthetic and real-world data verify the effectiveness of our theory.