Finding Heterophilic Neighbors via Confidence-based Subgraph Matching for Semi-supervised Node Classification

Abstract

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.

Proceedings of the 31st ACM International Conference on Information & Knowledge Management

References in corpus (5)

• Simple and Deep Graph Convolutional Networks
• How to Find Your Friendly Neighborhood: Graph Attention Design with Self-Supervision
• Unifying Graph Convolutional Neural Networks and Label Propagation
• Gromov-Wasserstein Learning for Graph Matching and Node Embedding
• Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification?