Finding Heterophilic Neighbors via Confidence-based Subgraph Matching for Semi-supervised Node Classification
This addresses the challenge of heterophily in graph-based applications for semi-supervised node classification, representing an incremental improvement over existing methods.
The paper tackles the problem of Graph Neural Networks (GNNs) failing to generalize under heterophilic setups by proposing a two-phased algorithm that uses confidence-based subgraph matching to identify task-irrelevant edges and modifies label propagation, resulting in improved performance and alleviation of over-smoothing on benchmark datasets.
Graph Neural Networks (GNNs) have proven to be powerful in many graph-based applications. However, they fail to generalize well under heterophilic setups, where neighbor nodes have different labels. To address this challenge, we employ a confidence ratio as a hyper-parameter, assuming that some of the edges are disassortative (heterophilic). Here, we propose a two-phased algorithm. Firstly, we determine edge coefficients through subgraph matching using a supplementary module. Then, we apply GNNs with a modified label propagation mechanism to utilize the edge coefficients effectively. Specifically, our supplementary module identifies a certain proportion of task-irrelevant edges based on a given confidence ratio. Using the remaining edges, we employ the widely used optimal transport to measure the similarity between two nodes with their subgraphs. Finally, using the coefficients as supplementary information on GNNs, we improve the label propagation mechanism which can prevent two nodes with smaller weights from being closer. The experiments on benchmark datasets show that our model alleviates over-smoothing and improves performance.