Abstract:
How can we exploit Label Propagation (LP) to improve the performance of GNN models on heterophilic graphs? Graph Neural Network (GNN) models have received a lot of attent...Show MoreMetadata
Abstract:
How can we exploit Label Propagation (LP) to improve the performance of GNN models on heterophilic graphs? Graph Neural Network (GNN) models have received a lot of attention as a powerful deep learning technology that uses graph structure and features, and has achieved an archived state-of-the-art performance for graph-related tasks. LP has been applied in various studies to improve performance of GNN models. However, LP does not perform well on heterophilic graphs, where nodes of different types are linked with each other, since LP assumes that the graphs inherently exhibits homophily, where similar nodes tend to be linked. Such heterophilic graphs are increasing common nowadays. In this paper, we propose LPkG (Label Propagation on k-Nearest Neighbor Graphs of Graph Autoencoder), a simple but effective method to engage LP to improve the performance of GNN models even on heterophilic graphs. LPkG constructs a supplementary homophilic graph, peforms LP on this graph, and uses the results together with the results of GNN models. The supplementary graph is a k-Nearest Neighbor (k-NN) graph genereated from a latent space computed by Graph Autoencoder (GAE). Experimental results demonstrate that LPkG consistently achieves performance improvement on various heterophilic graph datasets: 2.75% on the Wisconsin dataset, 2.23% on the Texas dataset, and 2.55% on the Cornell dataset.
Date of Conference: 18-21 February 2024
Date Added to IEEE Xplore: 11 April 2024
ISBN Information:
ISSN Information:
References is not available for this document.
Contents Select All
1.
S. Pandit, D. H. Chau, S. Wang and C. Faloutsos, "Netprobe: a fast and scalable system for fraud detection in online auction networks", Proceedings of the 16th international conference on World Wide Web, pp. 201-210, 2007.
2.
J. Zhu, R. A. Rossi, A. Rao, T. Mai, N. Lipka, N. K. Ahmed, et al., Graph neural networks with heterophily, 2021.
3.
J. Zhu, Y. Yan, L. Zhao, M. Heimann, L. Akoglu and D. Koutra, Beyond homophily in graph neural networks: Current limitations and effective designs, 2020.
4.
S. Abu-El-Haija, B. Perozzi, A. Kapoor, N. Alipourfard, K. Lerman, H. Harutyunyan, et al., Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing, 2019.
5.
J. Zhu, Y. Yan, L. Zhao, M. Heimann, L. Akoglu and D. Koutra, "Generalizing graph neural networks beyond homophily", CoRR, vol. abs/2006.11468, 2020.
6.
H. Pei, B. Wei, K. C. Chang, Y. Lei and B. Yang, "Geom-gcn: Geometric graph convolutional networks", CoRR, vol. abs/2002.05287, 2020.
7.
D. Jin, Z. Yu, C. Huo, R. Wang, X. Wang, D. He, et al., "Universal graph convolutional networks", Advances in Neural Information Processing Systems, vol. 34, pp. 10654-10664, 2021.
8.
W. Jin, T. Derr, Y. Wang, Y. Ma, Z. Liu and J. Tang, Node similarity preserving graph convolutional networks, 2021.
9.
M. Liu, Z. Wang and S. Ji, "Non-local graph neural networks", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 44, no. 12, pp. 10270-10276, dec 2022.
10.
S. Qi, W. Wang, B. Jia, J. Shen and S.-C. Zhu, Learning human-object interactions by graph parsing neural networks, 2018.
11.
H. Dong, J. Chen, F. Feng, X. He, S. Bi, Z. Ding, et al., "On the equivalence of decoupled graph convolution network and label propagation", Proceedings of the Web Conference 2021, pp. 3651-3662, 2021.
12.
C. Bellei, H. Alattas and N. Kaaniche, "Label-gcn: An effective method for adding label propagation to graph convolutional networks", arXiv preprint, 2021.
13.
T. N. Kipf and M. Welling, Variational graph auto-encoders, 2016.
14.
X. Zhu and Z. Ghahramani, Learning from labeled and unlabeled data with label propagation, 2002.
15.
X. Zhu, Z. Ghahramani and J. D. Lafferty, "Semi-supervised learning using gaussian fields and harmonic functions", Proceedings of the 20th International conference on Machine learning (ICML-03), pp. 912-919, 2003.
16.
D. Zhou, O. Bousquet, T. Lal, J. Weston and B. Schölkopf, "Learning with local and global consistency", Advances in neural information processing systems, vol. 16, 2003.
17.
X. Zhu, Semi-supervised learning with graphs, Carnegie Mellon University, 2005.
18.
H. Wang and J. Leskovec, "Unifying graph convolutional neural networks and label propagation", CoRR, vol. abs/2002.06755, 2020.
19.
Z. Zhong, S. Ivanov and J. Pang, "Simplifying node classification on heterophilous graphs with compatible label propagation", arXiv preprint, 2022.
21.
X. Zheng, Y. Liu, S. Pan, M. Zhang, D. Jin and P. S. Yu, "Graph neural networks for graphs with heterophily: A survey", arXiv preprint, 2022.
22.
T. N. Kipf and M. Welling, "Semi-supervised classification with graph convolutional networks", arXiv preprint, 2016.
23.
B. Rozemberczki, C. Allen and R. Sarkar, Multi-scale attributed node embedding, 2021.
24.
J. Tang, J. Sun, C. Wang and Z. Yang, "Social influence analysis in large-scale networks", Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 807-816, 2009.
25.
S. K. Maurya, X. Liu and T. Murata, Improving graph neural networks with simple architecture design, 2021.
26.
L. Van Der Maaten and G. Hinton, "Visualizing data using t-sne", Journal of machine learning research, vol. 9, no. 11, 2008.
