基于多任务学习图卷积模型的航空网络节点分类

doi:10.12305/j.issn.1001-506X.2022.07.31

摘要/Abstract

摘要：

准确识别航空网络关键节点, 做好针对性防护, 对于保证航空网络正常运行至关重要。传统的方法, 如基于复杂网络中心性指标的方法, 或基于机器学习的算法, 只单一考虑网络结构或节点特征来评价节点的重要性。然而评价节点的重要性应该同时考虑网络结构特征和节点特征。为解决上述问题, 本文提出了一种名为多任务图卷积网络(multi tasks graph convolution network, MTGCN)航空网络节点分类模型, 该模型在图卷积网络的基础上, 引入多任务学习及自适应加权策略, 将“节点—节点相关性”作为辅助任务加入模型的训练过程中, 并根据训练情况自适应分配各任务权重。3个不同规模的航空网络数据集中的仿真实验表明本文所提模型的性能优于现有的图卷积模型, 为图卷积在航空网络节点分类方向的应用提供了思路。

关键词: 航空网络, 图神经网络, 节点分类, 多任务学习

Abstract:

Accurate identification of key nodes in airline networks and targeted protection are essential to ensure the normal operation of airline networks. Traditional methods, such as those based on complex network centrality metrics or machine learning-based algorithms, only consider the network structure or node features to evaluate the importance of nodes. However, the importance of nodes should be evaluated by considering both the network structure and node features. To solve this problem, this paper proposes a node classification model named multi tasks graph convolution network (MTGCN), which introduces multi-task learning and adaptive weighting strategy into graph convolution network, adds node-node correlation as an auxiliary task to the training process of the model, and adaptively assigns weights to each task according to the training condition. The results show that the proposed model outperforms the existing graph convolutional model and provides an idea for the application of graph convolution network in aviation networks node classification.

Key words: airline network, graph neural network, node classification, multi task learning

中图分类号:

TP391.4

樊成, 王布宏, 田继伟. 基于多任务学习图卷积模型的航空网络节点分类[J]. 系统工程与电子技术, 2022, 44(7): 2341-2349.

Cheng FAN, Buhong WANG, Jiwei TIAN. Node classification of airline network based on the graph convolution network model with multi-task learning[J]. Systems Engineering and Electronics, 2022, 44(7): 2341-2349.

图/表 10

图1

表1

表2

图2

表3

图3

表4

表5

图4

图5

参考文献 37

1	CHEN Y , WANG J , JIN F J . Robustness of China's air transport network from 1975 to 2017[J]. Physica A: Statistical Mechanics and its Applications, 2020, 53 (9): 128- 141.
2	YANG H H , AN S . Critical nodes identify-cation in complex networks[J]. Symmetry, 2020, 12 (1): 123- 136. doi: 10.3390/sym12010123
3	GAYDOS D A , PETRASOVA A , COBB R C , et al. Forecasting and control of emerging infectious forest disease through participatory modelling[J]. Philosophical Trans.of the Royal Society B, 2019, 374 (1776): 283- 291.
4	ZHANG X , ZHAN C J , CHI K T . Modeling the dynamics of cascading failures in power systems[J]. IEEE Journal on Emerging and Selected Topics in Circuits and Systems, 2017, 7 (2): 192- 204. doi: 10.1109/JETCAS.2017.2671354
5	CAI Q , ALAM S , DUONG V . On robustness paradox in air traffic networks[J]. IEEE Trans.on Network Science and Engineering, 2020, 7 (4): 3087- 3099. doi: 10.1109/TNSE.2020.3015728
6	LORDAN O , SALLAN M J , SIMO P . Robustness of the air transport network[J]. Transportation Research: Part E, 2014, 68 (9): 155- 163.
7	闫玲玲, 陈增强, 张青. 基于度和聚类系数的中国航空网络重要性节点分析[J]. 智能系统学报, 2016, 11 (5): 586- 593.
	YAN L L , CHEN Z Q , ZHANG Q . Analysis of key nodes in China's aviation network based on the degree centrality indicator and clustering coefficient[J]. CAAI Trans.on Intelligent Systems, 2016, 11 (5): 586- 593.
8	PRADHAN P , ANGELIYA C U , JALAN S . Principal eigenvector localization and centrality in networks: revisited[J]. Physica A: Statistical Mechanics and its Applications, 2020, 55 (4): 124- 139.
9	SALAVATI C , ABDOLLAHPOURI A , MANBARI Z . Ranking nodes in complex networks based on local structure and improving closeness centrality[J]. Neurocomputing, 2018, 336, 36- 45.
10	TANG J J , LI Z T , GAO F , et al. Identifying critical metro stations in multiplex network based on D-S evidence theory[J]. Physica A: Statistical Mechanics and its Applications, 2021, 57 (4): 74- 85.
11	KOTSIANTIS S B . Decision trees: a recent overview[J]. Artificial Intelligence Review, 2013, 39 (4): 261- 283. doi: 10.1007/s10462-011-9272-4
12	丁世飞, 齐丙娟, 谭红艳. 支持向量机理论与算法研究综述[J]. 电子科技大学学报, 2011, 40 (1): 2- 10.
	DING S F , QI B J , TAN H Y . An overview on theory and algorithm of support vector machines[J]. Journal of University of Electronic Science and Technology of China, 2011, 40 (1): 2- 10.
13	李佳威, 吴明功, 温祥西, 等. 基于最小连通支配集的复杂网络关键节点与连边识别方法[J]. 系统工程与电子技术, 2019, 41 (11): 2541- 2549.
	LI J W , WU M G , WEN X X , et al. Identifying key nodes and edges of complex networks based on the minimum connected dominating set[J]. Systems Engineering and Electronics, 2019, 41 (11): 2541- 2549.
14	INUWADUTSE I , LIPTROTT M , KORKONTZELOS I . Detection of spam-posting accounts on Twitter[J]. Neurocomputing, 2018, 315 (11): 496- 511.
15	ZHENG X H , ZENG Z P , CHEN Z Y , et al. Detecting spammers on social networks[J]. Neurocomputing, 2015, 159 (7): 27- 34.
16	CAI J , LUO J W , WANG S L , et al. Feature selection in machine learning: a new perspective[J]. Neurocomputing, 2018, 300 (7): 70- 79.
17	朱凯利, 朱海龙, 刘靖宇, 等. 基于图卷积神经网络的交通流量预测[J]. 智能计算机与应用, 2019, 9 (6): 168- 177. doi: 10.3969/j.issn.2095-2163.2019.06.035
	ZHU K L , ZHU H L , LIU J Y , et al. Traffic flow prediction based on graph convolutional neural network[J]. Intelligent Computer and Applications, 2019, 9 (6): 168- 177. doi: 10.3969/j.issn.2095-2163.2019.06.035
18	刘晓玲, 刘柏嵩, 王洋洋. 一种基于图卷积网络的文本多标签学习方法[J]. 小型微型计算机系统, 2021, 42 (3): 531- 535. doi: 10.3969/j.issn.1000-1220.2021.03.014
	LIU X L , LIU B S , WANG Y Y . Text multi-label learning method based on graph convolutional networks[J]. Journal of Chinese Computer Systems, 2021, 42 (3): 531- 535. doi: 10.3969/j.issn.1000-1220.2021.03.014
19	YU E Y , WANG Y P , FU Y , et al. Identifying critical nodes in complex networks via graph convolutional networks[J]. Knowledge Based Systems, 2020, 198 (21): 893- 899.
20	WU Z H , PAN S R , CHEN F W , et al. A compre hensive survey on graph neural networks[J]. IEEE Trans.on Neural Networks and Learning Systems, 2021, 32 (1): 4- 24. doi: 10.1109/TNNLS.2020.2978386
21	KIPF T, WELLING M. Semi-supervised classification with graph convolutional networks[EB/OL]. [2021-05-25]. https://arxiv.org/abs/1609.02907v3, 2016-09-09/2021-05-25.
22	VELICKOVIC P, CUCURULL G, CASANOVA A, et al. Graph attention networks[EB/OL]. [2021-05-25]. https://arxiv.org/abs/1710.10903, 2017-10-30/2021-05-25.
23	WANG Z , WANG B H , XU N . SAR ship detection in complex background based on multi-feature fusion and non-local channel attention mechanism[J]. International Journal of Remote Sensing, 2021, 42 (19): 7519- 7550. doi: 10.1080/01431161.2021.1963003
24	HAMILTON W L , YING R , LESKOVEC J . Inductive representation learning on large graphs[J]. Advances in Neural Information Process Systems, 2017, 1706 (2216): 1024- 1034.
25	ZHAO G H , JIA P , ZHOU A , et al. InfGCN: identifying influential nodes in complex networks with graph convolutional networks[J]. Neurocomputing, 2020, 414 (11): 18- 26.
26	LI Q M, HAN Z C, WANG X M. Deeper insights into graph convolutional networks for semi-supervised learning[C]//Proc. of the AAAI Conference on Artificial Intelligence, 2018: 124-137.
27	CHEN D, LIN Y K, LI W, et al. Measuring and relieving the over-smoothing problem for graph neural networks from the topological view[C]//Proc. of the AAAI Conference on Artificial Intelligence, 2020: 3438-3445.
28	CARUANA R . Multitask learning[J]. Autonomous Agents and Multi-Agent Systems, 1998, 27 (1): 95- 133.
29	VANDENHENDE S, GEORGOULIS S, VAN GANSBEKE W, et al. Multi-task learning for dense prediction tasks: a survey[EB/OL]. [2021-05-25]. https://arxiv.org/abs/2004.13379.
30	张钰, 刘建伟, 左信. 多任务学习[J]. 计算机学报, 2020, 43 (7): 1340- 1378.
	ZHANG Y , LIU J W , ZUO X . Survey of multi task learning[J]. Chinese Journal of Computers, 2020, 43 (7): 1340- 1378.
31	CHEN Z, BADRINARAYANAN V, LEE C Y, et al. Grad-norm: gradient normalization for adaptive loss balancing in deep multi task networks[C]//Proc. of the International Conference on Machine Learning, 2018: 794-803.
32	RIBEIRO L F R, SAVERSE P H P, FIGUEIREDO D R. Struc2vec: learning node representations from structural identity[C]// Proc. of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2017: 385-394.
33	WU J, HE J R, XU J J. DEMO-Net: degree-specific graph neural networks for node and graph classification[C]//Proc. of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019: 406-415.
34	WU S M, FLACH P, FERRI C. An improved model selection heuristic for AUC[C]//Proc. of the European Conference on Machine Learning, 2007: 478-489.
35	HAND D J . Evaluating diagnostic tests: the area under the ROC curve and the balance of errors[J]. Statistics in Medicine, 2010, 29 (14): 1502- 1510.
36	KINGMA D P, BA J. Adam: a method for stochastic optimization[EB/OL]. [2021-05-25]. https://arxiv.org/abs/1412.6980, 2014-12-22/2021-05-25.
37	SRIVASTAVA N , HINTON G , KRIZHE-VSKY A , et al. Dropout: a simple way to prevent neural networks from overfitting[J]. The Journal of Machine Learning Research, 2014, 15 (1): 1929- 1958.

数据集	节点数	边数	最大度值	最大直径	节点类型
Brazil	131	1 038	80	4	4
Europe	399	5 995	202	5	4
USA	1 190	13 599	238	8	4

结果	预测为正常	预测为异常
实际为正常	True positive(TP)	False negative(FN)
实际为异常	False positive(FP)	True negative(TN)

数据集	模型	AUC	Micro-F1	Macro-F1
巴西	GCN	0.794	0.596	0.522
	GAT	0.783	0.623	0.543
	GraphSAGE	0.714	0.581	0.487
	DEMO-Net	0.806	0.652	0.572
	MTGCN	0.817	0.687	0.597
欧洲	GCN	0.593	0.537	0.473
	GAT	0.611	0.524	0.481
	GraphSAGE	0.558	0.487	0.452
	DEMO-Net	0.624	0.532	0.491
	MTGCN	0.656	0.548	0.503
美国	GCN	0.704	0.513	0.553
	GAT	0.713	0.534	0.561
	GraphSAGE	0.663	0.474	0.524
	DEMO-Net	0.724	0.557	0.568
	MTGCN	0.751	0.627	0.582

数据集	权重	迭代次数
数据集	权重	100	200	300	400	500	600	700	800	900	1 000
巴西	λ_n	0.776 6	0.987 1	1.280 0	1.236 7	1.198 20	1.148 6	1.128 3	1.111 9	1.125 5	1.139 2
巴西	λ_p	1.319 4	1.198 3	1.018 6	0.937 7	0.834 1	0.838 4	0.838 5	0.839 2	0.829 7	0.839 2
欧洲	λ_n	0.814 3	1.128 4	1.062 1	1.112 5	1.112 0	1.118 6	1.123 9	1.117 9	1.118 3	1.118 4
欧洲	λ_p	1.176 6	1.087 1	0.925 8	0.843 5	1.278 8	1.088 6	0.973 9	0.952 1	0.931 5	0.924 4
美国	λ_n	0.981 1	1.087 1	1.080 0	1.297 3	0.851 2	1.123 4	1.125 4	1.197 6	1.198 4	1.203 1
美国	λ_p	1.241 1	1.314 8	1.143 7	1.082 0	1.045 3	0.845 2	0.931 5	0.938 6	0.941 5	0.949 2

数据集	模型	准确率	Micro-F1	Macro-F1
巴西	with AT	0.817	0.687	0.597
巴西	without AT	0.792	0.656	0.582
欧洲	with AT	0.656	0.548	0.503
欧洲	without AT	0.631	0.523	0.491
美国	with AT	0.751	0.627	0.582
美国	without AT	0.734	0.608	0.571