Cited By
View all- Zhao TZhang XWang S(2024)Imbalanced Node Classification With Synthetic Over-SamplingIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.344316036:12(8515-8528)Online publication date: Dec-2024
Disambiguated Node Classification with Graph Neural Networks
Pages 914 - 923
Abstract
Graph Neural Networks (GNNs) have demonstrated significant success in learning from graph-structured data across various domains. Despite their great successful, one critical challenge is often overlooked by existing works, i.e., the learning of message propagation that can generalize effectively to underrepresented graph regions. These minority regions often exhibit irregular homophily/heterophily patterns and diverse neighborhood class distributions, resulting in ambiguity. In this work, we investigate the ambiguity problem within GNNs, its impact on representation learning, and the development of richer supervision signals to fight against this problem. We conduct a fine-grained evaluation of GNN, analyzing the existence of ambiguity in different graph regions and its relation with node positions. To disambiguate node embeddings, we propose a novel method, DisamGCL which exploits additional optimization guidance to enhance representation learning, particularly for nodes in ambiguous regions. DisamGCL identifies ambiguous nodes based on temporal inconsistency of predictions and introduces a disambiguation regularization by employing contrastive learning in a topology-aware manner. DisamGCL promotes discriminativity of node representations and can alleviating semantic mixing caused by message propagation, effectively addressing the ambiguity problem. Empirical results validate the efficiency of DisamGCL and highlight its potential to improve GNN performance in underrepresented graph regions.
Supplemental Material
MP4 File
Supplemental video
- Download
- 21.55 MB
References
[1]
Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. 2019. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference on machine learning. PMLR, 21--29.
[2]
Amir Hosein Khas Ahmadi. 2020. Memory-based graph networks. Ph.,D. Dissertation. University of Toronto (Canada).
[3]
Selahattin Akkas and Ariful Azad. 2022. JGCL: Joint Self-Supervised and Supervised Graph Contrastive Learning. In Companion Proceedings of the Web Conference 2022. 1099--1105.
[4]
Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. 2021. Beyond low-frequency information in graph convolutional networks. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35. 3950--3957.
[5]
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. 2013. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:1312.6203 (2013).
[6]
Deli Chen, Yankai Lin, Guangxiang Zhao, Xuancheng Ren, Peng Li, Jie Zhou, and Xu Sun. 2021. Topology-Imbalance Learning for Semi-Supervised Node Classification. Advances in Neural Information Processing Systems, Vol. 34 (2021).
[7]
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. 2020. A simple framework for contrastive learning of visual representations. In International conference on machine learning. PMLR, 1597--1607.
[8]
Hryhorii Chereda, A. Bleckmann, F. Kramer, A. Leha, and T. Beißbarth. 2019. Utilizing Molecular Network Information via Graph Convolutional Neural Networks to Predict Metastatic Event in Breast Cancer. Studies in health technology and informatics, Vol. 267 (2019), 181--186.
[9]
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. 2020. Adaptive universal generalized pagerank graph neural network. arXiv preprint arXiv:2006.07988 (2020).
[10]
Enyan Dai, Wei Jin, Hui Liu, and Suhang Wang. 2022a. Towards Robust Graph Neural Networks for Noisy Graphs with Sparse Labels. arXiv preprint arXiv:2201.00232 (2022).
[11]
Enyan Dai and Suhang Wang. 2021. Towards self-explainable graph neural network. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management. 302--311.
[12]
Enyan Dai, Tianxiang Zhao, Huaisheng Zhu, Junjie Xu, Zhimeng Guo, Hui Liu, Jiliang Tang, and Suhang Wang. 2022b. A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability. arXiv preprint arXiv:2204.08570 (2022).
[13]
Vijay Prakash Dwivedi and Xavier Bresson. 2020. A generalization of transformer networks to graphs. arXiv preprint arXiv:2012.09699 (2020).
[14]
Wenqi Fan, Y. Ma, Qing Li, Yuan He, Y. Zhao, Jiliang Tang, and D. Yin. 2019. Graph Neural Networks for Social Recommendation. The World Wide Web Conference (2019).
[15]
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. 2017. Neural Message Passing for Quantum Chemistry. In ICML.
[16]
William L. Hamilton, Zhitao Ying, and J. Leskovec. 2017. Inductive Representation Learning on Large Graphs. In NIPS.
[17]
Kaveh Hassani and Amir Hosein Khas Ahmadi. 2020. Contrastive Multi-View Representation Learning on Graphs. ArXiv, Vol. abs/2006.05582 (2020).
[18]
Mingguo He, Zhewei Wei, and Ji rong Wen. 2022. Convolutional Neural Networks on Graphs with Chebyshev Approximation, Revisited. ArXiv, Vol. abs/2202.03580 (2022).
[19]
Mingguo He, Zhewei Wei, Hongteng Xu, et al. 2021. Bernnet: Learning arbitrary graph spectral filters via bernstein approximation. Advances in Neural Information Processing Systems, Vol. 34 (2021), 14239--14251.
[20]
R. Devon Hjelm, Alex Fedorov, Samuel Lavoie-Marchildon, Karan Grewal, Adam Trischler, and Yoshua Bengio. 2018. Learning deep representations by mutual information estimation and maximization. ArXiv, Vol. abs/1808.06670 (2018).
[21]
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay S. Pande, and Jure Leskovec. 2019. Strategies for Pre-training Graph Neural Networks. arXiv: Learning (2019).
[22]
Di Jin, Zhizhi Yu, Cuiying Huo, Rui Wang, Xiao Wang, Dongxiao He, and Jiawei Han. 2021a. Universal graph convolutional networks. Advances in Neural Information Processing Systems, Vol. 34 (2021), 10654--10664.
[23]
Ming Jin, Yizhen Zheng, Yuan-Fang Li, Chen Gong, Chuan Zhou, and Shirui Pan. 2021b. Multi-Scale Contrastive Siamese Networks for Self-Supervised Graph Representation Learning. ArXiv, Vol. abs/2105.05682 (2021).
[24]
Justin M Johnson and Taghi M Khoshgoftaar. 2019. Survey on deep learning with class imbalance. Journal of Big Data, Vol. 6, 1 (2019), 27.
[25]
Wei Ju, Zheng Fang, Yiyang Gu, Zequn Liu, Qingqing Long, Ziyue Qiao, Yifang Qin, Jianhao Shen, Fang Sun, Zhiping Xiao, et al. 2023. A Comprehensive Survey on Deep Graph Representation Learning. arXiv preprint arXiv:2304.05055 (2023).
[26]
Thomas Kipf and M. Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. ArXiv, Vol. abs/1609.02907 (2017).
[27]
Thomas N Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016).
[28]
Phuc H Le-Khac, Graham Healy, and Alan F Smeaton. 2020. Contrastive representation learning: A framework and review. Ieee Access, Vol. 8 (2020), 193907--193934.
[29]
Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel. 2015. Gated graph sequence neural networks. arXiv preprint arXiv:1511.05493 (2015).
[30]
Shuai Lin, Chen Liu, Pan Zhou, Zi-Yuan Hu, Shuojia Wang, Ruihui Zhao, Yefeng Zheng, Liang Lin, Eric Xing, and Xiaodan Liang. 2022. Prototypical graph contrastive learning. IEEE Transactions on Neural Networks and Learning Systems (2022).
[31]
Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár. 2017. Focal loss for dense object detection. In Proceedings of the IEEE international conference on computer vision. 2980--2988.
[32]
Meng Liu, Zhengyang Wang, and Shuiwang Ji. 2021. Non-local graph neural networks. IEEE transactions on pattern analysis and machine intelligence, Vol. 44, 12 (2021), 10270--10276.
[33]
Yixin Liu, Ming Jin, Shirui Pan, Chuan Zhou, Yu Zheng, Feng Xia, and S Yu Philip. 2022. Graph self-supervised learning: A survey. IEEE Transactions on Knowledge and Data Engineering, Vol. 35, 6 (2022), 5879--5900.
[34]
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiaoming Chang, and Doina Precup. 2022. Revisiting Heterophily For Graph Neural Networks. ArXiv, Vol. abs/2210.07606 (2022).
[35]
Felix L. Opolka, Aaron Solomon, C?t?lina Cangea, Petar Velickovic, Pietro Lio', and R. Devon Hjelm. 2019. Spatio-Temporal Deep Graph Infomax. ArXiv, Vol. abs/1904.06316 (2019).
[36]
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. 2019. Geom-GCN: Geometric Graph Convolutional Networks. In International Conference on Learning Representations.
[37]
Bryan Perozzi, Rami Al-Rfou, and S. Skiena. 2014. DeepWalk: online learning of social representations. In KDD '14.
[38]
Weijieying Ren, Lei Wang, Kunpeng Liu, Ruocheng Guo, Lim Ee Peng, and Yanjie Fu. 2022b. Mitigating Popularity Bias in Recommendation with Unbalanced Interactions: A Gradient Perspective. arXiv preprint arXiv:2211.01154 (2022).
[39]
Weijieying Ren, Pengyang Wang, Xiaolin Li, Charles E Hughes, and Yanjie Fu. 2022a. Semi-supervised Drifted Stream Learning with Short Lookback. arXiv preprint arXiv:2205.13066 (2022).
[40]
Weijieying Ren, Tianxiang Zhao, Wei Qin, and Kunpeng Liu. 2023. T-SaS: Toward Shift-aware Dynamic Adaptation for Streaming Data. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management. 4244--4248.
[41]
Yu Rong, Wen bing Huang, Tingyang Xu, and Junzhou Huang. 2019. DropEdge: Towards Deep Graph Convolutional Networks on Node Classification. In International Conference on Learning Representations.
[42]
Neelam Rout, Debahuti Mishra, and Manas Kumar Mallick. 2018. Handling imbalanced data: A survey. In International Proceedings on Advances in Soft Computing, Intelligent Systems and Applications. Springer, 431--443.
[43]
Luana Ruiz, Fernando Gama, and Alejandro Ribeiro. 2020. Gated graph recurrent neural networks. IEEE Transactions on Signal Processing, Vol. 68 (2020), 6303--6318.
[44]
P. Sen, Galileo Namata, M. Bilgic, L. Getoor, B. Gallagher, and T. Eliassi-Rad. 2008. Collective Classification in Network Data. AI Magazine, Vol. 29 (2008), 93--106.
[45]
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. 2018. Pitfalls of Graph Neural Network Evaluation. ArXiv, Vol. abs/1811.05868 (2018).
[46]
Qinghua Shen, Weijieying Ren, and Wei Qin. 2023. Graph Relation Aware Continual Learning. arXiv preprint arXiv:2308.08259 (2023).
[47]
Lei Tang and Huan Liu. 2009. Relational learning via latent social dimensions. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. 817--826.
[48]
Petar Velivc kovi?, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2017. Graph attention networks. arXiv preprint arXiv:1710.10903 (2017).
[49]
Petar Velickovic, William Fedus, William L. Hamilton, Pietro Lio', Yoshua Bengio, and R. Devon Hjelm. 2018. Deep Graph Infomax. ArXiv, Vol. abs/1809.10341 (2018).
[50]
Xiyuan Wang and Muhan Zhang. 2022. How Powerful are Spectral Graph Neural Networks. In International Conference on Machine Learning.
[51]
Yu Wang and Tyler Derr. 2021. Tree decomposed graph neural network. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management. 2040--2049.
[52]
Bingzhe Wu, Jintang Li, Junchi Yu, Yatao Bian, Hengtong Zhang, CHaochao Chen, Chengbin Hou, Guoji Fu, Liang Chen, Tingyang Xu, et al. 2022. A Survey of Trustworthy Graph Learning: Reliability, Explainability, and Privacy Protection. arXiv preprint arXiv:2205.10014 (2022).
[53]
Felix Wu, Tianyi Zhang, Amauri H. de Souza, Christopher Fifty, Tao Yu, and Kilian Q. Weinberger. 2019. Simplifying Graph Convolutional Networks. In International Conference on Machine Learning.
[54]
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. 2020. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems (2020).
[55]
Teng Xiao, Zhengyu Chen, Zhimeng Guo, Zeyang Zhuang, and Suhang Wang. 2022. Decoupled Self-supervised Learning for Non-Homophilous Graphs. arXiv e-prints (2022), arXiv--2206.
[56]
Junjie Xu, Enyan Dai, Xiang Zhang, and Suhang Wang. 2022. HP-GMN: Graph Memory Networks for Heterophilous Graphs. arXiv preprint arXiv:2210.08195 (2022).
[57]
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2018. How Powerful are Graph Neural Networks?. In International Conference on Learning Representations.
[58]
Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. 2021. Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks. 2022 IEEE International Conference on Data Mining (ICDM) (2021), 1287--1292.
[59]
Tianmeng Yang, Yujing Wang, Zhihan Yue, Yaming Yang, Yunhai Tong, and Jing Bai. 2022. Graph Pointer Neural Networks. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 36. 8832--8839.
[60]
Yiding Yang, Zunlei Feng, Mingli Song, and Xinchao Wang. 2020. Factorizable Graph Convolutional Networks. Advances in Neural Information Processing Systems, Vol. 33 (2020).
[61]
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. 2020. Graph Contrastive Learning with Augmentations. ArXiv, Vol. abs/2010.13902 (2020).
[62]
Tianxiang Zhao, Dongsheng Luo, Xiang Zhang, and Suhang Wang. 2022a. On Consistency in Graph Neural Network Interpretation. arXiv preprint arXiv:2205.13733 (2022).
[63]
Tianxiang Zhao, Dongsheng Luo, Xiang Zhang, and Suhang Wang. 2022b. TopoImb: Toward Topology-level Imbalance in Learning from Graphs. ArXiv, Vol. abs/2212.08689 (2022).
[64]
Tianxiang Zhao, Dongsheng Luo, Xiang Zhang, and Suhang Wang. 2023. Towards Faithful and Consistent Explanations for Graph Neural Networks. In Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining. 634--642.
[65]
Tianxiang Zhao, Xianfeng Tang, Xiang Zhang, and Suhang Wang. 2020. Semi-Supervised Graph-to-Graph Translation. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management. 1863--1872.
[66]
Tianxiang Zhao, Xiang Zhang, and Suhang Wang. 2021. GraphSMOTE: Imbalanced Node Classification on Graphs with Graph Neural Networks. In Proceedings of the Fourteenth ACM International Conference on Web Search and Data Mining.
[67]
Tianxiang Zhao, Xiang Zhang, and Suhang Wang. 2022c. Exploring edge disentanglement for node classification. In Proceedings of the ACM Web Conference 2022. 1028--1036.
[68]
Xin Zheng, Yixin Liu, Shirui Pan, Miao Zhang, Di Jin, and Philip S Yu. 2022. Graph neural networks for graphs with heterophily: A survey. arXiv preprint arXiv:2202.07082 (2022).
[69]
T. Zhong, Tianliang Wang, Jiahao Wang, J. Wu, and Fan Zhou. 2020. Multiple-Aspect Attentional Graph Neural Networks for Online Social Network User Localization. IEEE Access, Vol. 8 (2020), 95223--95234.
[70]
Yikai Zhou, Baosong Yang, Derek F. Wong, Yu Wan, and Lidia S. Chao. 2020. Uncertainty-Aware Curriculum Learning for Neural Machine Translation. In Annual Meeting of the Association for Computational Linguistics.
[71]
Yu Zhou, Haixia Zheng, Xin Huang, Shufeng Hao, Dengao Li, and Jumin Zhao. 2022. Graph neural networks: Taxonomy, advances, and trends. ACM Transactions on Intelligent Systems and Technology (TIST), Vol. 13, 1 (2022), 1--54.
[72]
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. 2020c. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, Vol. 33 (2020), 7793--7804.
[73]
Qikui Zhu, Bo Du, and Pingkun Yan. 2020a. Self-supervised Training of Graph Convolutional Networks. ArXiv, Vol. abs/2006.02380 (2020).
[74]
Qi Zhu, Natalia Ponomareva, Jiawei Han, and Bryan Perozzi. 2021a. Shift-Robust GNNs: Overcoming the Limitations of Localized Graph Training data. In Neural Information Processing Systems.
[75]
Yanqiao Zhu, Yichen Xu, Qiang Liu, and Shu Wu. 2021b. An empirical study of graph contrastive learning. arXiv preprint arXiv:2109.01116 (2021).
[76]
Yanqiao Zhu, Yichen Xu, Feng Yu, Q. Liu, Shu Wu, and Liang Wang. 2020b. Deep Graph Contrastive Representation Learning. ArXiv, Vol. abs/2006.04131 (2020).
Index Terms
- Disambiguated Node Classification with Graph Neural Networks
Recommendations
Label-Consistency based Graph Neural Networks for Semi-supervised Node Classification
SIGIR '20: Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information RetrievalGraph neural networks (GNNs) achieve remarkable success in graph-based semi-supervised node classification, leveraging the information from neighboring nodes to improve the representation learning of target node. The success of GNNs at node ...
GraFN: Semi-Supervised Node Classification on Graph with Few Labels via Non-Parametric Distribution Assignment
SIGIR '22: Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information RetrievalDespite the success of Graph Neural Networks (GNNs) on various applications, GNNs encounter significant performance degradation when the amount of supervision signals, i.e., number of labeled nodes, is limited, which is expected as GNNs are trained ...
Global-local graph neural networks for node-classification
AbstractThe task of graph node classification is often approached by utilizing a local Graph Neural Network (GNN), that learns only local information from the node input features and their adjacency. In this paper, we propose to improve the performance ...
Highlights- We propose to learn label features to capture global information of the input graph.
- We fuse label and node features to predict a node-classification map.
- We qualitatively demonstrate our method by illustrating the learnt label and ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
May 2024
4826 pages
ISBN:9798400701719
DOI:10.1145/3589334
- General Chairs:
- Tat-Seng Chua,
- Chong-Wah Ngo,
- Proceedings Chair:
- Roy Ka-Wei Lee,
- Program Chairs:
- Ravi Kumar,
- Hady W. Lauw
Copyright © 2024 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 13 May 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- NSF (National Science Foundation)
- Department of Homeland Security CINA
- Cisco Faculty Research Award
- Army Research Office
Conference
WWW '24
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,899 of 8,196 submissions, 23%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 146Total Downloads
- Downloads (Last 12 months)146
- Downloads (Last 6 weeks)10
Reflects downloads up to 26 Dec 2024
Other Metrics
Citations
Cited By
View all- Zhao TZhang XWang S(2024)Imbalanced Node Classification With Synthetic Over-SamplingIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.344316036:12(8515-8528)Online publication date: Dec-2024
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in