research-article

Public Access

Generating Counterfactual Hard Negative Samples for Graph Contrastive Learning

Authors:

Guandong XuAuthors Info & Claims

WWW '23: Proceedings of the ACM Web Conference 2023

Pages 621 - 629

https://doi.org/10.1145/3543507.3583499

Published: 30 April 2023 Publication History

All formats PDF

Abstract

Graph contrastive learning has emerged as a powerful unsupervised graph representation learning tool. The key to the success of graph contrastive learning is to acquire high-quality positive and negative samples as contrasting pairs to learn the underlying structural semantics of the input graph. Recent works usually sample negative samples from the same training batch with the positive samples or from an external irrelevant graph. However, a significant limitation lies in such strategies: the unavoidable problem of sampling false negative samples. In this paper, we propose a novel method to utilize Counterfactual mechanism to generate artificial hard negative samples for Graph Contrastive learning, namely CGC. We utilize a counterfactual mechanism to produce hard negative samples, ensuring that the generated samples are similar but have labels that differ from the positive sample. The proposed method achieves satisfying results on several datasets. It outperforms some traditional unsupervised graph learning methods and some SOTA graph contrastive learning methods. We also conducted some supplementary experiments to illustrate the proposed method, including the performances of CGC with different hard negative samples and evaluations for hard negative samples generated with different similarity measurements. The implementation code is available online to ease reproducibility1.

References

[1]

Bijaya Adhikari, Yao Zhang, Naren Ramakrishnan, and B. Aditya Prakash. 2018. Sub2Vec: Feature Learning for Subgraphs. In Advances in Knowledge Discovery and Data Mining - 22nd Pacific-Asia Conference, PAKDD 2018, Melbourne, VIC, Australia, June 3-6, 2018, Proceedings, Part II(Lecture Notes in Computer Science, Vol. 10938), Dinh Q. Phung, Vincent S. Tseng, Geoffrey I. Webb, Bao Ho, Mohadeseh Ganji, and Lida Rashidi (Eds.). Springer, 170–182. https://doi.org/10.1007/978-3-319-93037-4_14

Digital Library

[2]

Karsten M. Borgwardt and Hans-Peter Kriegel. 2005. Shortest-Path Kernels on Graphs. In Proceedings of the 5th IEEE International Conference on Data Mining (ICDM 2005), 27-30 November 2005, Houston, Texas, USA. IEEE Computer Society, 74–81. https://doi.org/10.1109/ICDM.2005.132

Digital Library

[3]

Karsten M. Borgwardt, Cheng Soon Ong, Stefan Schönauer, S. V. N. Vishwanathan, Alexander J. Smola, and Hans-Peter Kriegel. 2005. Protein function prediction via graph kernels. In Proceedings Thirteenth International Conference on Intelligent Systems for Molecular Biology 2005, Detroit, MI, USA, 25-29 June 2005. 47–56. https://doi.org/10.1093/bioinformatics/bti1007

Digital Library

[4]

Kevin Clark, Minh-Thang Luong, Quoc V. Le, and Christopher D. Manning. 2020. ELECTRA: Pre-training Text Encoders as Discriminators Rather Than Generators. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net. https://openreview.net/forum¿id=r1xMH1BtvB

[5]

Wenqi Fan, Xiaorui Liu, Wei Jin, Xiangyu Zhao, Jiliang Tang, and Qing Li. 2022. Graph trend filtering networks for recommendation. In Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval. 112–121.

Digital Library

[6]

Kaveh Hassani and Amir Hosein Khas Ahmadi. 2020. Contrastive Multi-View Representation Learning on Graphs. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event(Proceedings of Machine Learning Research, Vol. 119). PMLR, 4116–4126. http://proceedings.mlr.press/v119/hassani20a.html

[7]

Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross B. Girshick. 2020. Momentum Contrast for Unsupervised Visual Representation Learning. In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020. Computer Vision Foundation / IEEE, 9726–9735. https://doi.org/10.1109/CVPR42600.2020.00975

[8]

Wei Jin, Xiaorui Liu, Xiangyu Zhao, Yao Ma, Neil Shah, and Jiliang Tang. 2022. Automated Self-Supervised Learning for Graphs. In 10th International Conference on Learning Representations (ICLR 2022).

[9]

Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net. https://openreview.net/forum¿id=SJU4ayYgl

[10]

S. Kullback and R. A. Leibler. 1951. On Information and Sufficiency. The Annals of Mathematical Statistics 22, 1 (1951), 79 – 86. https://doi.org/10.1214/aoms/1177729694

[11]

Xiao-Hui Li, Caleb Chen Cao, Yuhan Shi, Wei Bai, Han Gao, Luyu Qiu, Cong Wang, Yuanyuan Gao, Shenjia Zhang, Xun Xue, and Lei Chen. 2022. A Survey of Data-Driven and Knowledge-Aware eXplainable AI. IEEE Trans. Knowl. Data Eng. 34, 1 (2022), 29–49. https://doi.org/10.1109/TKDE.2020.2983930

Digital Library

[12]

Tomás Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013. Efficient Estimation of Word Representations in Vector Space. In 1st International Conference on Learning Representations, ICLR 2013, Scottsdale, Arizona, USA, May 2-4, 2013, Workshop Track Proceedings, Yoshua Bengio and Yann LeCun (Eds.). http://arxiv.org/abs/1301.3781

[13]

Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. 2020. TUDataset: A collection of benchmark datasets for learning with graphs. CoRR abs/2007.08663(2020). arXiv:2007.08663https://arxiv.org/abs/2007.08663

[14]

Christopher Morris, Nils M. Kriege, Kristian Kersting, and Petra Mutzel. 2016. Faster Kernels for Graphs with Continuous Attributes via Hashing. In IEEE 16th International Conference on Data Mining, ICDM 2016, December 12-15, 2016, Barcelona, Spain, Francesco Bonchi, Josep Domingo-Ferrer, Ricardo Baeza-Yates, Zhi-Hua Zhou, and Xindong Wu (Eds.). IEEE Computer Society, 1095–1100. https://doi.org/10.1109/ICDM.2016.0142

[15]

Annamalai Narayanan, Mahinthan Chandramohan, Rajasekar Venkatesan, Lihui Chen, Yang Liu, and Shantanu Jaiswal. 2017. graph2vec: Learning Distributed Representations of Graphs. CoRR abs/1707.05005(2017). arXiv:1707.05005http://arxiv.org/abs/1707.05005

[16]

Francesco Orsini, Paolo Frasconi, and Luc De Raedt. 2015. Graph Invariant Kernels. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, Qiang Yangand Michael J. Wooldridge (Eds.). AAAI Press, 3756–3762. http://ijcai.org/Abstract/15/528

[17]

Judea Pearl and Dana Mackenzie. 2018. The Book of Why: The New Science of Cause and Effect (1st ed.). Basic Books, Inc., USA.

[18]

Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang, Ming Ding, Kuansan Wang, and Jie Tang. 2020. GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training. In KDD ’20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA, USA, August 23-27, 2020. ACM, 1150–1160. https://doi.org/10.1145/3394486.3403168

Digital Library

[19]

Joshua David Robinson, Ching-Yao Chuang, Suvrit Sra, and Stefanie Jegelka. 2021. Contrastive Learning with Hard Negative Samples. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net. https://openreview.net/forum¿id=CR1XOQ0UTh-

[20]

Ida Schomburg, Antje Chang, Christian Ebeling, Marion Gremse, Christian Heldt, Gregor Huhn, and Dietmar Schomburg. 2004. BRENDA, the enzyme database: updates and major new developments. Nucleic Acids Res. 32, Database-Issue (2004), 431–433. https://doi.org/10.1093/nar/gkh081

[21]

Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. 2011. Weisfeiler-Lehman Graph Kernels. J. Mach. Learn. Res. 12(2011), 2539–2561. http://dl.acm.org/citation.cfm¿id=2078187

Digital Library

[22]

Nino Shervashidze, S. V. N. Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten M. Borgwardt. 2009. Efficient graphlet kernels for large graph comparison. In Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics, AISTATS 2009, Clearwater Beach, Florida, USA, April 16-18, 2009(JMLR Proceedings, Vol. 5), David A. Van Dyk and Max Welling (Eds.). JMLR.org, 488–495. http://proceedings.mlr.press/v5/shervashidze09a.html

[23]

Fan-Yun Sun, Jordan Hoffmann, Vikas Verma, and Jian Tang. 2020. InfoGraph: Unsupervised and Semi-supervised Graph-Level Representation Learning via Mutual Information Maximization. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net. https://openreview.net/forum¿id=r1lfF2NYvH

[24]

Aäron van den Oord, Yazhe Li, and Oriol Vinyals. 2018. Representation Learning with Contrastive Predictive Coding. CoRR abs/1807.03748(2018). arXiv:1807.03748http://arxiv.org/abs/1807.03748

[25]

Petar Velickovic, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R. Devon Hjelm. 2019. Deep Graph Infomax. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net. https://openreview.net/forum¿id=rklz9iAcKQ

[26]

S. V. N. Vishwanathan, Nicol N. Schraudolph, Risi Kondor, and Karsten M. Borgwardt. 2010. Graph Kernels. J. Mach. Learn. Res. 11(2010), 1201–1242. http://portal.acm.org/citation.cfm¿id=1859891

Digital Library

[27]

S Wachter, BDM Mittelstadt, and C Russell. 2018. Counterfactual explanations without opening the black box: automated decisions and the GDPR. Harvard Journal of Law and Technology 31, 2 (2018), 841–887.

[28]

Cong Wang, Xiao-Hui Li, Haocheng Han, Shendi Wang, Luning Wang, Caleb Chen Cao, and Lei Chen. 2021. Counterfactual Explanations in Explainable AI: A Tutorial. In KDD ’21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, Singapore, August 14-18, 2021, Feida Zhu, Beng Chin Ooi, and Chunyan Miao (Eds.). ACM, 4080–4081. https://doi.org/10.1145/3447548.3470797

Digital Library

[29]

Zhirong Wu, Yuanjun Xiong, Stella X. Yu, and Dahua Lin. 2018. Unsupervised Feature Learning via Non-Parametric Instance Discrimination. In 2018 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2018, Salt Lake City, UT, USA, June 18-22, 2018. Computer Vision Foundation / IEEE Computer Society, 3733–3742. https://doi.org/10.1109/CVPR.2018.00393

[30]

Jun Xia, Lirong Wu, Jintao Chen, Ge Wang, and Stan Z. Li. 2021. Debiased Graph Contrastive Learning. CoRR abs/2110.02027(2021). arXiv:2110.02027https://arxiv.org/abs/2110.02027

[31]

Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019. How Powerful are Graph Neural Networks¿. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net. https://openreview.net/forum¿id=ryGs6iA5Km

[32]

Haoran Yang, Hongxu Chen, Shirui Pan, Lin Li, Philip S. Yu, and Guandong Xu. 2022. Dual Space Graph Contrastive Learning. CoRR abs/2201.07409(2022). arXiv:2201.07409https://arxiv.org/abs/2201.07409

[33]

Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. 2020. Graph Contrastive Learning with Augmentations. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual. https://proceedings.neurips.cc/paper/2020/hash/3fe230348e9a12c13120749e3f9fa4cd-Abstract.html

[34]

Han Zhao, Xu Yang, Zhenru Wang, Erkun Yang, and Cheng Deng. 2021. Graph Debiased Contrastive Learning with Joint Representation Clustering. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021, Zhi-Hua Zhou (Ed.). ijcai.org, 3434–3440. https://doi.org/10.24963/ijcai.2021/473

[35]

Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. 2021. Graph Contrastive Learning with Adaptive Augmentation. In WWW ’21: The Web Conference 2021, Virtual Event / Ljubljana, Slovenia, April 19-23, 2021. ACM / IW3C2, 2069–2080. https://doi.org/10.1145/3442381.3449802

Digital Library

Cited By

Zhang KSang GCheng JLiu ZZhang Y(2025)Negative sampling strategy based on multi-hop neighbors for graph representation learningExpert Systems with Applications10.1016/j.eswa.2024.125688263(125688)Online publication date: Mar-2025
https://doi.org/10.1016/j.eswa.2024.125688
Yang HWang YZhao XChen HYin HLi QXu G(2024)Multi-Level Graph Knowledge Contrastive LearningIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.346653036:12(8829-8841)Online publication date: Dec-2024
https://doi.org/10.1109/TKDE.2024.3466530
Wang HYang XSun JZhang SChen CHua XLuo X(2024)Look Into Gradients: Learning Compact Hash Codes for Out-of-Distribution RetrievalIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.342526836:12(8730-8743)Online publication date: Dec-2024
https://doi.org/10.1109/TKDE.2024.3425268
Show More Cited By

Index Terms

Generating Counterfactual Hard Negative Samples for Graph Contrastive Learning
1. Computing methodologies
  1. Artificial intelligence
    1. Knowledge representation and reasoning
      1. Semantic networks
  2. Machine learning
    1. Learning paradigms
      1. Unsupervised learning

Recommendations

Negative samples selecting strategy for graph contrastive learning
Abstract
Graph neural networks (GNNs) have emerged as a successful method on graph structured data. Limited by expensive labeled data, contrastive learning has been adopted to the graph domain. In most existing node-level graph contrastive learning ...
AFANS: Augmentation-Free Graph Contrastive Learning with Adversarial Negative Sampling
Advanced Intelligent Computing Technology and Applications
Abstract
Graph Contrastive Learning (GCL) has emerged as a highly promising methodology in graph representation learning, mainly due to its label-independent nature. The construction of positive and negative samples is crucial for the effectiveness of GCL. ...
Heterogeneous data augmentation in graph contrastive learning for effective negative samples
Abstract
Graph contrastive learning (GCL) aims to contrast positive–negative counterparts, whereas graph data augmentation (GDA) in GCL is employed to generate positive–negative samples. Existing GDA techniques, such as 1-dimensional (1D) feature masking, ...
Highlights
- Earlier graph data augmentation methods are more likely to augment homogeneous views.
- We introduce a framework (DAENS) based on 2D masking to create heterogeneous views.
- DAENS improves the node classification up to 5.84% accuracy ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WWW '23: Proceedings of the ACM Web Conference 2023

April 2023

4293 pages

ISBN:9781450394161

DOI:10.1145/3543507

Copyright © 2023 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

SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 April 2023

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

Huawei Innovation Research Program
NSF (National Science Foundation)
HKIDS Early Career Research Grant
Australian Research Council
Ant Group (CCF-Ant Research Fund)
APRC - CityU New Research Initiatives
SIRG - CityU Strategic Interdisciplinary Research Grant

Conference

WWW '23

Sponsor:

SIGWEB

WWW '23: The ACM Web Conference 2023

April 30 - May 4, 2023

TX, Austin, USA

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
711
Total Downloads

Downloads (Last 12 months)433
Downloads (Last 6 weeks)67

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang KSang GCheng JLiu ZZhang Y(2025)Negative sampling strategy based on multi-hop neighbors for graph representation learningExpert Systems with Applications10.1016/j.eswa.2024.125688263(125688)Online publication date: Mar-2025
https://doi.org/10.1016/j.eswa.2024.125688
Yang HWang YZhao XChen HYin HLi QXu G(2024)Multi-Level Graph Knowledge Contrastive LearningIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.346653036:12(8829-8841)Online publication date: Dec-2024
https://doi.org/10.1109/TKDE.2024.3466530
Wang HYang XSun JZhang SChen CHua XLuo X(2024)Look Into Gradients: Learning Compact Hash Codes for Out-of-Distribution RetrievalIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.342526836:12(8730-8743)Online publication date: Dec-2024
https://doi.org/10.1109/TKDE.2024.3425268
Chae GLee JKim S(2024)Contrastive Learning with Hard Negative Samples for Chest X-ray Multi-Label ClassificationApplied Soft Computing10.1016/j.asoc.2024.112101(112101)Online publication date: Aug-2024
https://doi.org/10.1016/j.asoc.2024.112101
Roschewitz Mde Sousa Ribeiro FXia TKhara GGlocker B(2024)Counterfactual Contrastive Learning: Robust Representations via Causal Image SynthesisData Engineering in Medical Imaging10.1007/978-3-031-73748-0_3(22-32)Online publication date: 25-Oct-2024
https://doi.org/10.1007/978-3-031-73748-0_3
Liu LCai LZhang CZhao XGao JWang WLv YFan WWang YHe MLiu ZLi QChen HDuh WHuang HKato MMothe JPoblete B(2023)LinRec: Linear Attention Mechanism for Long-term Sequential Recommender SystemsProceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3539618.3591717(289-299)Online publication date: 19-Jul-2023
https://dl.acm.org/doi/10.1145/3539618.3591717

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

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

Media

Figures

Other

Tables

View Table of Contents