research-article

Public Access

Node Similarity Preserving Graph Convolutional Networks

Authors:

Jiliang TangAuthors Info & Claims

WSDM '21: Proceedings of the 14th ACM International Conference on Web Search and Data Mining

Pages 148 - 156

https://doi.org/10.1145/3437963.3441735

Published: 08 March 2021 Publication History

Abstract

Graph Neural Networks (GNNs) have achieved tremendous success in various real-world applications due to their strong ability in graph representation learning. GNNs explore the graph structure and node features by aggregating and transforming information within node neighborhoods. However, through theoretical and empirical analysis, we reveal that the aggregation process of GNNs tends to destroy node similarity in the original feature space. There are many scenarios where node similarity plays a crucial role. Thus, it has motivated the proposed framework SimP-GCN that can effectively and efficiently preserve node similarity while exploiting graph structure. Specifically, to balance information from graph structure and node features, we propose a feature similarity preserving aggregation which adaptively integrates graph structure and node features. Furthermore, we employ self-supervised learning to explicitly capture the complex feature similarity and dissimilarity relations between nodes. We validate the effectiveness of SimP-GCN on seven benchmark datasets including three assortative and four disassorative graphs. The results demonstrate that SimP-GCN outperforms representative baselines. Further probe shows various advantages of the proposed framework. The implementation of SimP-GCN is available at https://github.com/ChandlerBang/SimP-GCN.

References

[1]

Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. 2018. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.01261 (2018).

[2]

Jesús Bobadilla, Fernando Ortega, Antonio Hernando, and Abraham Gutiérrez. 2013. Recommender systems survey. Knowledge-based systems, Vol. 46 (2013).

[3]

Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. 2013. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:1312.6203 (2013).

[4]

Jie Chen, Haw-ren Fang, and Yousef Saad. 2009. Fast Approximate kNN Graph Construction for High Dimensional Data via Recursive Lanczos Bisection. Journal of Machine Learning Research, Vol. 10, 9 (2009).

[5]

Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. 2020. Simple and Deep Graph Convolutional Networks. arXiv preprint arXiv:2007.02133 (2020).

[6]

Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. 2016. Convolutional neural networks on graphs with fast localized spectral filtering. In NeurIPS.

[7]

Wei Dong, Charikar Moses, and Kai Li. 2011. Efficient k-nearest neighbor graph construction for generic similarity measures. In WWW.

[8]

Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. 2019. Learning discrete structures for graph neural networks. ICML (2019).

[9]

Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. 2017. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning-Volume 70. JMLR. org.

Digital Library

[10]

Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems.

[11]

Kaveh Hassani and Amir Hosein Khasahmadi. 2020. Contrastive Multi-View Representation Learning on Graphs. arXiv preprint arXiv:2006.05582 (2020).

[12]

Wei Jin, Tyler Derr, Haochen Liu, Yiqi Wang, Suhang Wang, Zitao Liu, and Jiliang Tang. 2020 a. Self-supervised Learning on Graphs: Deep Insights and New Direction. arxiv: cs.LG/2006.10141

[13]

Wei Jin, Yaxin Li, Han Xu, Yiqi Wang, and Jiliang Tang. 2020 b. Adversarial Attacks and Defenses on Graphs: A Review and Empirical Study. arXiv preprint arXiv:2003.00653 (2020).

[14]

Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. 2020 c. Graph Structure Learning for Robust Graph Neural Networks. arXiv preprint arXiv:2005.10203 (2020).

[15]

Thomas N Kipf and Max Welling. 2016a. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016).

[16]

Thomas N Kipf and Max Welling. 2016b. Variational graph auto-encoders. arXiv preprint arXiv:1611.07308 (2016).

[17]

Hang Li, Haozheng Wang, Zhenglu Yang, and Haochen Liu. 2017. Effective representing of information network by variational autoencoder. In Proceedings of the 26th International Joint Conference on Artificial Intelligence. 2103--2109.

[18]

Qimai Li, Zhichao Han, and Xiao-Ming Wu. 2018. Deeper insights into graph convolutional networks for semi-supervised learning. arXiv preprint arXiv:1801.07606 (2018).

[19]

Yingwei Li, Song Bai, Cihang Xie, Zhenyu Liao, Xiaohui Shen, and Alan Yuille. 2019. Regional Homogeneity: Towards Learning Transferable Universal Adversarial Perturbations Against Defenses. arXiv preprint arXiv:1904.00979 (2019).

[20]

Yingwei Li, Song Bai, Yuyin Zhou, Cihang Xie, Zhishuai Zhang, and Alan L Yuille. 2020 a. Learning Transferable Adversarial Examples via Ghost Networks. In AAAI.

[21]

Yaxin Li, Wei Jin, Han Xu, and Jiliang Tang. 2020 b. DeepRobust: A PyTorch Library for Adversarial Attacks and Defenses. arXiv preprint arXiv:2005.06149 (2020).

[22]

Meng Liu, Hongyang Gao, and Shuiwang Ji. 2020 a. Towards Deeper Graph Neural Networks. arXiv preprint arXiv:2007.09296 (2020).

[23]

Meng Liu, Zhengyang Wang, and Shuiwang Ji. 2020 b. Non-Local Graph Neural Networks. arXiv preprint arXiv:2005.14612 (2020).

[24]

Yao Ma and Jiliang Tang. 2020. Deep Learning on Graphs .Cambridge University Press.

[25]

Miller McPherson, Lynn Smith-Lovin, and James M Cook. 2001. Birds of a feather: Homophily in social networks. Annual review of sociology, Vol. 27, 1 (2001), 415--444.

[26]

Mark EJ Newman. 2002. Assortative mixing in networks. Physical review letters, Vol. 89, 20 (2002), 208701.

[27]

Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. 2020. Geom-gcn: Geometric graph convolutional networks. arXiv preprint arXiv:2002.05287 (2020).

[28]

Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. 2019. Dropedge: Towards deep graph convolutional networks on node classification. In ICLR.

[29]

David I Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. 2013. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE signal processing magazine, Vol. 30, 3 (2013), 83--98.

[30]

Yiwei Sun, Suhang Wang, Xianfeng Tang, Tsung-Yu Hsieh, and Vasant Honavar. 2020. Adversarial Attacks on Graph Neural Networks via Node Injections: A Hierarchical Reinforcement Learning Approach. In WWW.

[31]

Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. 2009. Social influence analysis in large-scale networks. In KDD.

[32]

Xianfeng Tang, Huaxiu Yao, Yiwei Sun, Yiqi Wang, Jiliang Tang, Charu Aggarwal, Prasenjit Mitra, and Suhang Wang. 2020. Graph Convolutional Networks against Degree-Related Biases. arXiv preprint arXiv:2006.15643 (2020).

[33]

Petar Velivc ković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2017. Graph attention networks. arXiv preprint arXiv:1710.10903 (2017).

[34]

Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. 2019 b. Adversarial examples on graph data: Deep insights into attack and defense. arXiv preprint arXiv:1903.01610 (2019).

[35]

Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S Yu. 2019 a. A comprehensive survey on graph neural networks. arXiv preprint arXiv:1901.00596 (2019).

[36]

Han Xu, Yao Ma, Haochen Liu, Debayan Deb, Hui Liu, Jiliang Tang, and Anil Jain. 2019. Adversarial attacks and defenses in images, graphs and text: A review. arXiv preprint arXiv:1909.08072 (2019).

[37]

Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. 2018. Representation learning on graphs with jumping knowledge networks. arXiv preprint arXiv:1806.03536 (2018).

[38]

Chaoqi Yang, Ruijie Wang, Shuochao Yao, Shengzhong Liu, and Tarek Abdelzaher. 2020. Revisiting" Over-smoothing" in Deep GCNs. arXiv preprint arXiv:2003.13663 (2020).

[39]

Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. 2020 a. Graph Contrastive Learning with Augmentations. arXiv preprint arXiv:2010.13902 (2020).

[40]

Yuning You, Tianlong Chen, Zhangyang Wang, and Yang Shen. 2020 b. When Does Self-Supervision Help Graph Convolutional Networks? ICML (2020).

[41]

Muhan Zhang and Yixin Chen. 2018. Link prediction based on graph neural networks. In Advances in Neural Information Processing Systems. 5165--5175.

[42]

Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, and Maosong Sun. 2018. Graph neural networks: A review of methods and applications. arXiv preprint arXiv:1812.08434 (2018).

[43]

Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty. 2003. Semi-supervised learning using gaussian fields and harmonic functions. In ICML.

[44]

Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. 2018. Adversarial attacks on neural networks for graph data. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM.

Digital Library

[45]

Daniel Zügner and Stephan Günnemann. 2019. Adversarial attacks on graph neural networks via meta learning. arXiv preprint arXiv:1902.08412 (2019).

Cited By

Zhang ZJiang BTang JLuo B(2025)Label Guided Graph Optimized Convolutional Network for Semi-Supervised LearningIEEE Transactions on Signal and Information Processing over Networks10.1109/TSIPN.2025.352596111(71-84)Online publication date: 2025
https://doi.org/10.1109/TSIPN.2025.3525961
Fu SPeng QHe YWang XZou BXu DJing XYou X(2025)Multilevel Contrastive Graph Masked Autoencoders for Unsupervised Graph-Structure LearningIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2024.335880136:2(3464-3478)Online publication date: Feb-2025
https://doi.org/10.1109/TNNLS.2024.3358801
Zheng ZZhou SXu HGu MXu YLi ALi YGu JBu J(2025)Heterophilous distribution propagation for Graph Neural NetworksNeural Networks10.1016/j.neunet.2024.107014184(107014)Online publication date: Apr-2025
https://doi.org/10.1016/j.neunet.2024.107014
Show More Cited By

Index Terms

Node Similarity Preserving Graph Convolutional Networks
1. Computing methodologies
  1. Machine learning
    1. Learning settings
      1. Semi-supervised learning settings
    2. Machine learning approaches
      1. 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 Retrieval

Graph 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 ...
Node Similarity Preserving Graph Convolutional Network Based on Full-frequency Information for Node Classification
Abstract
Recently, graph neural networks have achieved good performance in graph representation learning. However, most graph neural networks only utilize node low-frequency signals and destroy node similarity when aggregating graph structure and node ...
Similarity-navigated graph neural networks for node classification
Abstract
Graph Neural Networks are effective in learning representations of graph-structured data. Some recent works are devoted to addressing heterophily, which exists ubiquitously in real-world networks, breaking the homophily assumption that nodes ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WSDM '21: Proceedings of the 14th ACM International Conference on Web Search and Data Mining

March 2021

1192 pages

ISBN:9781450382977

DOI:10.1145/3437963

General Chairs:
Liane Lewin-Eytan
Amazon, Israel
,
David Carmel
Amazon, Israel
,
Elad Yom-Tov
Microsoft, Israel
,
Program Chairs:
Eugene Agichtein
Emory University and Amazon, USA
,
Evgeniy Gabrilovich
Google Health, USA

Copyright © 2021 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 ACM 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: 08 March 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

WSDM '21

Sponsor:

WSDM '21: The Fourteenth ACM International Conference on Web Search and Data Mining

March 8 - 12, 2021

Virtual Event, Israel

Acceptance Rates

Overall Acceptance Rate 498 of 2,863 submissions, 17%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

141
Total Citations
View Citations
3,416
Total Downloads

Downloads (Last 12 months)968
Downloads (Last 6 weeks)103

Reflects downloads up to 14 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhang ZJiang BTang JLuo B(2025)Label Guided Graph Optimized Convolutional Network for Semi-Supervised LearningIEEE Transactions on Signal and Information Processing over Networks10.1109/TSIPN.2025.352596111(71-84)Online publication date: 2025
https://doi.org/10.1109/TSIPN.2025.3525961
Fu SPeng QHe YWang XZou BXu DJing XYou X(2025)Multilevel Contrastive Graph Masked Autoencoders for Unsupervised Graph-Structure LearningIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2024.335880136:2(3464-3478)Online publication date: Feb-2025
https://doi.org/10.1109/TNNLS.2024.3358801
Zheng ZZhou SXu HGu MXu YLi ALi YGu JBu J(2025)Heterophilous distribution propagation for Graph Neural NetworksNeural Networks10.1016/j.neunet.2024.107014184(107014)Online publication date: Apr-2025
https://doi.org/10.1016/j.neunet.2024.107014
Xie YLi JZhang S(2025)Adaptive node similarity for DropEdgeNeurocomputing10.1016/j.neucom.2025.129574626(129574)Online publication date: Apr-2025
https://doi.org/10.1016/j.neucom.2025.129574
Xu XYang WLi LZhu XCui JZhang ZWu L(2025)TD-GCN: A novel fusion method for network topological and dynamical featuresChaos, Solitons & Fractals10.1016/j.chaos.2024.115731191(115731)Online publication date: Feb-2025
https://doi.org/10.1016/j.chaos.2024.115731
Shenbagharaman AParamasivan B(2025)Secure and energy efficient routing protocol for underwater wireless sensor network using running city game optimization with XGBoost algorithmApplied Soft Computing10.1016/j.asoc.2024.112615169(112615)Online publication date: Jan-2025
https://doi.org/10.1016/j.asoc.2024.112615
Hssayni EBoufssasse AJoudar NEttaouil M(2025)Novel dropout approach for mitigating over-smoothing in graph neural networksApplied Intelligence10.1007/s10489-025-06285-955:5Online publication date: 21-Jan-2025
https://doi.org/10.1007/s10489-025-06285-9
Ye JAn CYang QLi Z(2025)AoSE-GCN: Attention-Aware Aggregation Operator for Spatial-Enhanced GCNDatabase Systems for Advanced Applications10.1007/978-981-97-5779-4_15(227-242)Online publication date: 11-Jan-2025
https://doi.org/10.1007/978-981-97-5779-4_15
Ju WYi SWang YLong QLuo JXiao ZZhang MLarson K(2024)A survey of data-efficient graph learningProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/896(8104-8113)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.24963/ijcai.2024/896
Wang CLiu YYang YLi WLarson K(2024)HeterGCLProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/265(2397-2405)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.24963/ijcai.2024/265
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten