Abstract
Graph learning on heterophilic graphs is challenging for classic graph neural network models. Recent research addresses this issue by using adaptive graph filters that consider signals with different frequencies. Although such models provide insightful design patterns for heterophilic graph analysis, their practical effect has been overlooked. Previous studies have evaluated adaptive graph filters with a large proportion of training data to demonstrate their effectiveness. However, such dense labeling is often impractical. Empirically, we observed that typical adaptive filters perform badly in weakly-supervised settings, making them easily outperformed by fixed filters. With empirical evidence, we demonstrate that the key reason is that sparse node labels make it difficult to learn effective filters. Fortunately, although labeled nodes are sparse in weakly-supervised settings, graph structures provide substantial supervision by indicating whether an edge is present. Through theoretical analysis on contextual Stochastic Block Models, we show that a good link predictor can imply the knowledge needed by a good node classifier. Therefore, we propose to use the “free labels” from the graph structure to form link prediction tasks and obtain an effective graph filter, which can be used to initialize the node classification model. Experimental results on both synthetic and real-world heterophilic graphs demonstrate the effectiveness of our approach. We also provide an in-depth analysis of the learned filters, which sheds light on the underlying mechanisms of our proposed approach. Codes are available at https://github.com/lucio-win/PKDD2023.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
This value depends on the number of node features, classes, hidden units, hidden layers and propagation layers. The calculation is provided in the supplementary material.
References
Abbe, E.: Community detection and stochastic block models: recent developments. J. Mach. Learn. Res. 18(1), 6446–6531 (2017)
Abboud, R., Ceylan, İ.İ.: Node classification meets link prediction on knowledge graphs. ar**v preprint ar**v:2106.07297 (2021)
Bianchi, F.M., Grattarola, D., Livi, L., Alippi, C.: Graph neural networks with convolutional ARMA filters. IEEE Trans. Pattern Anal. Mach. Intell. 44(7), 3496–3507 (2021)
Bo, D., Wang, X., Shi, C., Shen, H.: Beyond low-frequency information in graph convolutional networks. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, pp. 3950–3957 (2021)
Bojchevski, A., et al.: Scaling graph neural networks with approximate pagerank. In: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2464–2473 (2020)
Chien, E., Peng, J., Li, P., Milenkovic, O.: Adaptive universal generalized pagerank graph neural network. In: 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, 3–7 May 2021 (2021)
Ciotti, V., Bonaventura, M., Nicosia, V., Panzarasa, P., Latora, V.: Homophily and missing links in citation networks. EPJ Data Sci. 5(1), 7 (2016)
Deshpande, Y., Sen, S., Montanari, A., Mossel, E.: Contextual stochastic block models. In: Bengio, S., Wallach, H.M., Larochelle, H., Grauman, K., Cesa-Bianchi, N., Garnett, R. (eds.) Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, Montréal, Canada, 3–8 December 2018, pp. 8590–8602 (2018)
Dong, Y., Ding, K., Jalaian, B., Ji, S., Li, J.: AdaGNN: graph neural networks with adaptive frequency response filter. In: Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 392–401 (2021)
Hamilton, W.L., Ying, Z., Leskovec, J.: Inductive representation learning on large graphs. In: Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems, Long Beach, CA, USA, pp. 1024–1034 (2017)
He, M., Wei, Z., Xu, H., et al.: BernNet: learning arbitrary graph spectral filters via Bernstein approximation. Adv. Neural. Inf. Process. Syst. 34, 14239–14251 (2021)
Kenlay, H., Thanou, D., Dong, X.: Interpretable stability bounds for spectral graph filters. In: International Conference on Machine Learning, pp. 5388–5397. PMLR (2021)
Kingma, D.P., Ba, J.: Adam: A method for stochastic optimization. ar**v preprint ar**v:1412.6980 (2014)
Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. In: 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, 24–26 April 2017, Conference Track Proceedings. OpenReview.net (2017)
Klicpera, J., Bojchevski, A., Günnemann, S.: Predict then propagate: graph neural networks meet personalized pagerank. In: 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, 6–9 May 2019. OpenReview.net (2019)
Levie, R., Isufi, E., Kutyniok, G.: On the transferability of spectral graph filters. In: 2019 13th International conference on Sampling Theory and Applications (SampTA), pp. 1–5. IEEE (2019)
Likhobaba, D., Pavlichenko, N., Ustalov, D.: Toloker Graph: Interaction of Crowd Annotators (2023)
Lim, D., Benson, A.R.: Expertise and dynamics within crowdsourced musical knowledge curation: a case study of the genius platform. In: Proceedings of the International AAAI Conference on Web and Social Media, vol. 15, pp. 373–384 (2021)
Lim, D., et al.: Large scale learning on non-homophilous graphs: new benchmarks and strong simple methods. Adv. Neural. Inf. Process. Syst. 34, 20887–20902 (2021)
Lim, D., et al.: Large scale learning on non-homophilous graphs: new benchmarks and strong simple methods, pp. 20887–20902 (2021)
Lingam, V., Sharma, M., Ekbote, C., Ragesh, R., Iyer, A., Sellamanickam, S.: A piece-wise polynomial filtering approach for graph neural networks. In: Amini, M.R., Canu, S., Fischer, A., Guns, T., Kralj Novak, P., Tsoumakas, G. (eds.) ECML PKDD 2022, Part II. LNCS, vol. 13714, pp. 412–452. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-26390-3_25
McPherson, M., Smith-Lovin, L., Cook, J.M.: Birds of a feather: homophily in social networks. Ann. Rev. Sociol. 27(1), 415–444 (2001)
Pei, H., Wei, B., Chang, K.C., Lei, Y., Yang, B.: Geom-GCN: geometric graph convolutional networks. In: 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, 26–30 April 2020 (2020)
Platonov, O., Kuznedelev, D., Diskin, M., Babenko, A., Prokhorenkova, L.: A critical look at evaluation of GNNs under heterophily: are we really making progress? In: International Conference on Learning Representations
Rozemberczki, B., Allen, C., Sarkar, R.: Multi-scale attributed node embedding. J. Complex Netw. 9(2), cnab014 (2021)
Tang, J., Sun, J., Wang, C., Yang, Z.: Social influence analysis in large-scale networks. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 807–816 (2009)
Velickovic, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., Bengio, Y.: Graph attention networks. In: 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. OpenReview.net (2018)
Wang, X., Zhang, M.: How powerful are spectral graph neural networks. In: International Conference on Machine Learning, pp. 23341–23362. PMLR (2022)
Wu, F., Jr., A.H.S., Zhang, T., Fifty, C., Yu, T., Weinberger, K.Q.: Simplifying graph convolutional networks. In: Proceedings of the 36th International Conference on Machine Learning, ICML 2019, Long Beach, California, USA, 9–15 June 2019, pp. 6861–6871 (2019)
Wu, Z., Pan, S., Long, G., Jiang, J., Chang, X., Zhang, C.: Connecting the dots: multivariate time series forecasting with graph neural networks. In: Gupta, R., Liu, Y., Tang, J., Prakash, B.A. (eds.) KDD 2020: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA, USA, 23–27 August 2020, pp. 753–763. ACM (2020)
Xu, K., Li, C., Tian, Y., Sonobe, T., Kawarabayashi, K., Jegelka, S.: Representation learning on graphs with jum** knowledge networks. In: Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, 10–15 July 2018. Proceedings of Machine Learning Research, vol. 80, pp. 5449–5458. PMLR (2018)
Ying, R., He, R., Chen, K., Eksombatchai, P., Hamilton, W.L., Leskovec, J.: Graph convolutional neural networks for web-scale recommender systems. In: Guo, Y., Farooq, F. (eds.) Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2018, London, UK, 19–23 August 2018, pp. 974–983. ACM (2018)
Zhang, Z., Cui, P., Zhu, W.: Deep learning on graphs: a survey. IEEE Trans. Knowl. Data Eng. 34(1), 249–270 (2022)
Zheng, X., Liu, Y., Pan, S., Zhang, M., **, D., Yu, P.S.: Graph neural networks for graphs with heterophily: A survey. ar**v preprint ar**v:2202.07082 (2022)
Zhu, J., et al.: Graph neural networks with heterophily. In: Thirty-Fifth AAAI Conference on Artificial Intelligence, Virtual Event, 2–9 February 2021, pp. 11168–11176 (2021)
Zhu, J., Yan, Y., Zhao, L., Heimann, M., Akoglu, L., Koutra, D.: Beyond homophily in graph neural networks: current limitations and effective designs. In: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, 6–12 December 2020, virtual (2020)
Acknowledgements
This work is supported by the National University of Defense Technology Foundation under Grant Nos. ZK20-09 and ZK21-17, the Natural Science Foundation of Hunan Province of China under Grant No. 2021JJ40692 and the National Key Research and Development Program of China under Grant 2021YFB0300101.
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Ethics declarations
Ethical Statement
The purpose of this research is to study the performance of adaptive filters on heterophilic graphs in weakly-supervised settings. The research involves the usage of several open-sourced real-world datasets proposed and used by the heterophilic graph learning community. The potential risks associated with the research include the potential privacy issues on these datasets. We take the following measures to minimize these risks: when conducting the experiments, we will not track the original source of the dataset, but use the data anonymized by the dataset builders. The results of the research will be presented in an unbiased and objective manner.
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Wu, X., Wu, H., Wang, R., Li, D., Zhou, X., Lu, K. (2023). Leveraging Free Labels to Power up Heterophilic Graph Learning in Weakly-Supervised Settings: An Empirical Study. In: Koutra, D., Plant, C., Gomez Rodriguez, M., Baralis, E., Bonchi, F. (eds) Machine Learning and Knowledge Discovery in Databases: Research Track. ECML PKDD 2023. Lecture Notes in Computer Science(), vol 14171. Springer, Cham. https://doi.org/10.1007/978-3-031-43418-1_9
Download citation
DOI: https://doi.org/10.1007/978-3-031-43418-1_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-43417-4
Online ISBN: 978-3-031-43418-1
eBook Packages: Computer ScienceComputer Science (R0)
