图神经网络的标签翻转对抗攻击

doi:10.11959/j.issn.1000-436x.2021167

摘要/Abstract

摘要：

为扩展图神经网络对抗攻击类型以填补相关研究空白，提出了评估图神经网络对标签噪声稳健性的标签翻转对抗攻击方法。将对抗攻击的有效性机理提炼为矛盾数据假设、参数差异假设和同分布假设等3种基本假设，并基于3种假设建立标签翻转对抗攻击模型。采用基于梯度的攻击方法，理论证明了基于参数差异假设模型的攻击梯度与基于同分布假设模型的攻击梯度相同，建立2种攻击方法的等价关系。设计实验对比分析了基于不同假设建立模型的优势和不足；大量实验验证了标签翻转攻击模型的有效性。

关键词: 图神经网络, 对抗攻击, 标签翻转, 攻击假设, 稳健性

Abstract:

To expand the adversarial attack types of graph neural networks and fill the relevant research gaps, label flipping attack methods were proposed to evaluate the robustness of graph neural network aimed at label noise.The effectiveness mechanisms of adversarial attacks were summarized as three basic hypotheses, contradictory data hypothesis, parameter discrepancy hypothesis and identically distributed hypothesis.Based on the three hypotheses, label flipping attack models were established.Using the gradient oriented attack methods, it was theoretically proved that attack gradients based on the parameter discrepancy hypothesis were the same as gradients of identically distributed hypothesis, and the equivalence between two attack methods was established.Advantages and disadvantages of proposed models based on different hypotheses were compared and analyzed by experiments.Extensive experimental results verify the effectiveness of the proposed attack models.

Key words: graph neural network, adversarial attack, label flipping, attack hypothesis, robustness

中图分类号:

TP18

吴翼腾, 刘伟, 于洪涛. 图神经网络的标签翻转对抗攻击[J]. 通信学报, 2021, 42(9): 65-74.

Yiteng WU, Wei LIU, Hongtao YU. Label flipping adversarial attack on graph neural network[J]. Journal on Communications, 2021, 42(9): 65-74.

图/表 7

表1

表2

准确率"

k	方法	Polblogs	Cora_ml	Cora	Citeseer
	未扰动	94.54%	86.45%	85.04%	74.20%
	Min-max	92.62%	84.87%	82.38%	73.40%
	Mettack	93.32%	86.03%	84.81%	74.79%
1	Random	94.02%	86.11%	84.20%	73.53%
	$L_{C}$	91.87%	83.54%	80.12%	69.10%
	$\bar{L}$	$90 . 84 %$	$79 . 99 %$	$79 . 22 %$	69.01%
	$L$	91.07%	$79 . 99 %$	79.25%	$68 . 93 %$
	未扰动	95.60%	88.05%	87.08%	74.52%
	Min-max	94.61%	87.61%	85.74%	74.12%
	Mettack	93.70%	87.26%	86.74%	74.86%
2	Random	95.41%	88.04%	86.78%	74.04%
	$L_{C}$	94.75%	87.35%	85.02%	70.77%
	$\bar{L}$	$93 . 56 %$	82.85%	82.23%	$69 . 69 %$
	$L$	93.65%	$82 . 94 %$	$82 . 18 %$	69.78%

表2

图1

图2

图3

表3

k=1时数据集Cora_ml基于不同假设的比较分析"

假设	损失函数						扰动量
假设	损失函数	无扰动	1%	2%	3%	4%	5%	6%	7%	8%	9%	10%
	训练准确率	99.65%	98.51%	98.45%	98.32%	98.13%	97.83%	97.53%	97.18%	96.84%	96.42%	95.95%
	测试准确率	86.45%	85.71%	85.04%	84.43%	83.96%	83.54%	83.10%	82.61%	82.12%	81.70%	81.25%
矛盾数据	$L_{C_{1}}$	77.84	243.80	295.95	337.10	371.11	399.91	428.22	454.47	479.39	503.16	527.14
	${\tilde{L}}_{1}$	102.77	195.60	224.89	250.35	273.50	295.88	318.07	339.39	360.19	380.71	404.29
	$L_{1}$	77.84	180.13	209.41	234.72	257.65	279.80	301.76	322.91	343.53	363.89	387.28
	训练准确率	99.66%	97.83%	96.78%	95.79%	94.93%	93.94%	92.89%	91.98%	91.10%	90.23%	89.30%
	测试准确率	86.45%	85.05%	83.64%	82.28%	81.05%	79.99%	78.85%	77.80%	76.78%	75.78%	74.65%
参数差异	$L_{C_{2}}$	77.85	175.58	181.74	186.29	194.25	199.43	202.84	205.52	209.44	214.92	219.92
	${\tilde{L}}_{2}$	102.78	189.84	217.24	248.54	277.21	310.66	345.39	381.92	417.88	452.05	492.05
	$L_{2}$	77.85	173.25	200.42	231.60	260.22	293.66	328.38	364.88	400.80	434.92	474.88
	训练准确率	99.66%	97.85%	96.83%	95.79%	94.97%	93.96%	92.95%	91.95%	91.02%	90.25%	89.29%
	测试准确率	86.42%	85.12%	83.60%	82.28%	81.12%	79.99%	78.85%	77.80%	76.77%	75.80%	74.68%
同分布	$L_{C_{3}}$	77.87	173.47	181.53	186.50	192.86	197.10	200.70	202.68	206.56	212.37	216.85
	${\tilde{L}}_{3}$	102.80	189.06	216.25	248.45	278.29	315.38	351.02	389.25	425.06	460.38	501.39
	$L_{3}$	77.87	172.48	199.48	231.60	261.39	298.47	334.14	372.40	408.17	443.43	484.41
	训练准确率	99.66%	98.34%	98.21%	97.96%	97.81%	97.59%	97.42%	97.21%	97.01%	96.88%	96.68%
	测试准确率	86.46%	86.70%	86.59%	86.48%	86.23%	86.11%	86.00%	85.86%	85.76%	85.68%	85.56%
随机攻击	$L_{C_{4}}$	77.89	148.36	158.79	166.53	175.08	181.54	188.93	195.55	202.00	207.06	214.97
	${\tilde{L}}_{4}$	102.82	163.38	171.55	179.66	187.36	194.66	201.20	208.75	215.47	221.05	228.50
	$L_{4}$	77.89	147.08	155.27	163.37	171.10	178.37	184.90	192.39	199.09	204.64	212.08

表3

表4

k=2时数据集Cora_ml基于不同假设的比较分析"

假设	损失函数						扰动量
假设	损失函数	无扰动	1%	2%	3%	4%	5%	6%	7%	8%	9%	10%
	训练准确率	96.49%	94.98%	94.88%	94.88%	94.83%	94.69%	94.58%	94.35%	94.11%	93.88%	93.52%
	测试准确率	88.05%	88.21%	87.99%	87.79%	87.68%	87.35%	87.08%	86.87%	86.56%	86.27%	85.96%
矛盾数据	$L_{C_{1}}$	158.58	344.39	420.66	479.22	528.69	572.72	611.05	648.31	683.45	716.71	750.49
	${\tilde{L}}_{1}$	181.84	266.66	292.22	316.58	338.95	360.68	381.91	403.02	424.26	445.29	468.01
	$L_{1}$	158.58	252.93	279.12	303.77	326.28	348.09	369.31	390.45	411.68	432.71	455.41
	训练准确率	96.51%	94.58%	93.38%	92.38%	91.25%	90.05%	88.83%	87.70%	86.54%	85.48%	84.47%
	测试准确率	88.06%	87.64%	86.42%	85.11%	83.91%	82.85%	81.63%	80.48%	79.23%	77.91%	76.60%
参数差异	$L_{C_{2}}$	158.57	269.89	278.94	285.41	292.11	297.75	299.60	302.78	305.69	308.04	312.26
	${\tilde{L}}_{2}$	181.84	265.07	288.56	315.32	341.76	369.31	395.93	426.15	457.87	489.82	530.75
	$L_{2}$	158.57	249.86	273.22	299.88	326.27	353.83	380.44	410.72	442.51	474.52	515.59
	训练准确率	96.50%	94.62%	93.53%	92.42%	91.37%	90.13%	88.86%	87.72%	86.51%	85.47%	84.58%
	测试准确率	88.05%	87.71%	86.50%	85.35%	84.01%	82.94%	81.67%	80.46%	79.23%	78.05%	76.92%
同分布	$L_{C_{3}}$	158.61	268.73	278.24	282.96	290.70	295.65	296.99	302.46	303.10	305.86	310.32
	${\tilde{L}}_{3}$	181.87	265.31	288.51	317.72	345.52	373.91	401.51	432.71	466.63	501.98	546.42
	$L_{3}$	158.61	250.14	273.19	302.31	330.08	358.48	386.07	417.36	451.37	486.81	531.40
	训练准确率	96.51%	94.89%	94.80%	94.77%	94.65%	94.60%	94.55%	94.46%	94.44%	94.36%	94.28%
	测试准确率	88.05%	88.34%	88.29%	88.18%	88.12%	88.04%	88.02%	87.97%	87.86%	87.80%	87.74%
随机攻击	$L_{C_{4}}$	158.59	236.73	254.61	268.65	282.00	293.60	306.80	319.12	330.61	339.74	353.35
	${\tilde{L}}_{4}$	181.85	243.15	249.12	254.59	259.88	264.98	270.04	275.63	280.81	285.24	291.25
	$L_{4}$	158.59	228.03	234.21	239.81	245.25	250.44	255.61	261.28	266.54	271.03	277.14

表4

参考文献 33

[1]	YUAN X Y , HE P , ZHU Q L ,et al. Adversarial examples:attacks and defenses for deep learning[J]. IEEE Transactions on Neural Networks and Learning Systems, 2019,30(9): 2805-2824.
[2]	韦博成, 鲁国斌, 史建清 . 统计诊断引论[M]. 南京: 东南大学出版社, 1991.
	WEI B C , LU G B , SHI J Q . Introduction to statistical diagnosis[M]. Nanjing: Southeast University Press, 1991.
[3]	SZEGEDY C , ZAREMBA W , SUTSKEVER I ,et al. Intriguing properties of neural networks[J]. arXiv Preprint,arXiv:1312.6199, 2013.
[4]	司念文, 张文林, 屈丹 ,等. 基于对抗补丁的可泛化的 Grad-CAM攻击方法[J]. 通信学报, 2021,42(3): 23-35.
	SI N W , ZHANG W L , QU D ,et al. Generalized Grad-CAM attacking method based on adversarial patch[J]. Journal on Communications, 2021,42(3): 23-35.
[5]	ZüGNER D , AKBARNEJAD A , GüNNEMANN S , . Adversarial attacks on neural networks for graph data[C]// Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery ＆Data Mining. New York:ACM Press, 2018: 2847-2856.
[6]	MA J , DING S , MEI Q . Towards more practical adversarial attacks on graph neural networks[C]// Advances in Neural Information Processing Systems. Massachusetts:MIT Press, 2020: 4756-4766.
[7]	LI J , ZHANG H L , HAN Z C ,et al. Adversarial attack on community detection by hiding individuals[C]// Proceedings of The Web Conference 2020. New York:ACM Press, 2020: 917-927.
[8]	BOJCHEVSKI A , GüNNEMANN S , . Adversarial attacks on node embeddings via graph poisoning[J]. arXiv Preprint,arXiv:1809.01093, 2018.
[9]	CHEN L , LI J , PENG J ,et al. A survey of adversarial learning on graphs[J]. arXiv Preprint,arXiv:2003.05730, 2020.
[10]	XU H , MA Y , LIU H C ,et al. Adversarial attacks and defenses in images,graphs and text:a review[J]. International Journal of Automation and Computing, 2020,17(2): 151-178.673-683.
[11]	SUN Y W , WANG S H , TANG X F ,et al. Adversarial attacks on graph neural networks via node injections:a hierarchical reinforcement learning approach[C]// Proceedings of The Web Conference 2020. New York:ACM Press, 2020: 673-683.
[12]	WU Y T , LIU W , HU X B ,et al. Parameter discrepancy hypothesis:adversarial attack for graph data[J]. Information Sciences, 2021,577: 234-244.
[13]	ZüGNER D , GüNNEMANN S , . Adversarial attacks on graph neural networks via meta learning[J]. arXiv Preprint,arXiv:1902.08412, 2019.
[14]	韦博成, 林金官, 解锋昌 . 统计诊断[M]. 北京: 高等教育出版社, 2009.
	WEI B C , LIN J G , XIE F C . Statistical diagnostics[M]. Beijing: Higher Education Press, 2009.
[15]	COOK R D . Detection of influential observation in linear regression[J]. Technometrics, 1977,19(1): 15-18.
[16]	COOK R D . Influential observations in linear regression[J]. Journal of the American Statistical Association, 1979,74(365): 169-174.
[17]	COOK R D , WEISBERG S . Residuals and influence in regression[M]. New York: Chapman and Hall, 1982.
[18]	张宏坡, 程宁, 张博 ,等. 一种基于熵值法的标签翻转攻击方法:CN112700081A[P]. 2021-04-23.
	ZHANG H P , CHENG N , ZHANG B ,et al. A label flipping attack method based on entropy:CN112700081A[P]. 2021-04-23.
[19]	MU?OZ-GONZáLEZ L , BIGGIO B , DEMONTIS A ,et al. Towards poisoning of deep learning algorithms with back-gradient optimization[C]// Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security. New York:ACM Press, 2017: 27-38.
[20]	LIU X , SI S , ZHU X ,et al. A unified framework for data poisoning attack to graph-based semi-supervised learning[C]// Proceedings of the 33rd International Conference on Neural Information Processing Systems. Massachusetts:MIT Press, 2019: 9780-9790.
[21]	JIN W , LI Y , XU H ,et al. Adversarial attacks and defenses on graphs:a review and empirical study[J]. arXiv Preprint,arXiv:2003.00653, 2020.
[22]	费宇, 陈飞, 喻达磊 . 线性和广义线性混合模型及其统计诊断[M]. 科学出版社, 2013.
	FEI Y , CHEN F , YU D L ,et al. Linear and generalized linear mixed models and their statistical diagnosis[M]. Beijing: Science Press, 2013.
[23]	LI Q M , WU X M , LIU H ,et al. Label efficient semi-supervised learning via graph filtering[C]// 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition. Piscataway:IEEE Press, 2019: 9574-9583.
[24]	NT H , MAEHARA T . Revisiting graph neural networks:all we have is low-pass filters[J]. arXiv Preprint,arXiv:1905.09550, 2019.
[25]	WU F , SOUZA A , ZHANG T ,et al. Simplifying graph convolutional networks[C]// International conference on machine learning. Long Beach:PMLR, 2019: 6861-6871.
[26]	WEI B C , SHIH J Q . On statistical models for regression diagnostics[J]. Annals of the Institute of Statistical Mathematics, 1994,46(2): 267-278.
[27]	HOERL A E , KENNARD R W . Ridge regression:biased estimation for nonorthogonal problems[J]. Technometrics, 1970,12(1): 55-67.
[28]	MARQUARDT D W . An algorithm for least-squares estimation of nonlinear parameters[J]. Journal of the Society for Industrial and Applied Mathematics, 1963,11(2): 431-441.
[29]	SEN P , NAMATA G , BILGIC M ,et al. Collective classification in network data[J]. AI Magazine, 2008,29(3): 93.
[30]	MCCALLUM A K , NIGAM K , RENNIE J ,et al. Automating the construction of Internet portals with machine learning[J]. Information Retrieval, 2000,3(2): 127-163.
[31]	ADAMIC L A , GLANCE N . The political blogosphere and the 2004 US election:divided they blog[C]// Proceedings of the 3rd International Workshop on Link Discovery. New York:ACM Press, 2005: 36-43.
[32]	XU K D , CHEN H G , LIU S J ,et al. Topology attack and defense for graph neural networks:an optimization perspective[C]// Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence. Palo Alto:AAAI Press, 2019: 3961-3967.
[33]	陈晋音, 黄国瀚, 张敦杰 ,等. 一种面向图神经网络的图重构防御方法[J]. 计算机研究与发展, 2021,58(5): 1075-1091.
	CHEN J Y , HUANG G H , ZHANG D J ,et al. GRD-GNN:graph reconstruction defense for graph neural network[J]. Journal of Computer Research and Development, 2021,58(5): 1075-1091.

数据集	节点数	连边数	特征维数	分类数
Polblogs	1 222	16 714	1 490	2
Cora_ml	2 810	7 981	2 879	7
Cora	2 485	5 069	1 433	7
Citeseer	2 110	3 668	3 703	6