Multidimensional Dynamic Graph Models And Applications

Many complex systems in the real world can be regarded as graphs or complex networks for modeling and analysis.Unlike most other machine learning methods,which treat research obj ects as independent samples,complex networks are dedicated to studying the interrelationships and underlying laws between things(entities)in complex systems in the real world.The graph model regards all the research objects as a whole and conducts overall structural modeling by considering the relationship between them.Therefore,it has become an effective method for modeling relational data in non-Euclidean spaces.The systematic study of graph models helps us understand the behavior patterns and functional structures of entities in complex systems.It has important applications in social media,recommendation systems,public opinion monitoring,bio-medicine,text analysis,and network security.The complexity of graph data is reflected in the multidimensionality of its information sources,including structural dimensions,content dimensions,membership dimensions,time dimensions,and so on.At the same time,graph data also has the characteristics of small world,power-law distribution,community structure,and dynamic evolution.In addition,the era of big data produces a large number of multidimensional dynamic graph data,which contains rich heterogeneous information and content noise.These complexities have brought unprecedented opportunities and huge challenges to the research of graph algorithms.How to specifically consider the characteristics of complex systems in real life,make full use of multi-dimensional unstructured information to model graph data in a unified manner,and effectively analyze and predict future dynamics has become an important content of complex network research.In view of the various challenges faced by multidimensional dynamic graphs,this article mainly studies the complex multidimensional data comprehensive modeling method of graph algorithms,and its application in tasks such as community discovery,node classification,and node prediction.The main contributions of this article are as follows:(1)Aiming at the problem of multi-dimensional information fusion of dynamic attribute graph data,we propose a dynamic attribute graph community discovery algorithm based on a time series generation model.Traditional complex network analysis methods are mainly aimed at static graph data,but complex networks abstracted in real life are often dynamic.How to better integrate dynamic multi-dimensional information to mine the complex laws hidden behind entity relationships is a difficult point in this research field.Some existing studies have neglected the dependence on the time series,or have not fully utilized the content information of the nodes in the graph.We regard the historical sequence of the dynamic attribute graph as a whole for modeling,and at the same time consider the dynamic characteristics of edges and the contribution of node attributes to the potential membership degree of the class,and propose a dynamic graph community discovery algorithm based on the first-order Markov sequence model and the content observation model.The time series model models the network structure of different time slices through the first-order Markov process.The content observation model models the generation process of the edges and content attributes in the time slice through the content generation process.Based on experiments on a large amount of dynamic attribute graph data,we found that the proposed method can effectively detect the community structure of the dynamic graphs,and can effectively use the attribute information of nodes to further improve the clarity of the community structure.(2)Aiming at the computational complexity of large-scale graph data and the initialization sensitivity of community discovery algorithms,we propose a fast community discovery algorithm based on node centrality measurement.Community detection is an important tool for solving complex network analysis tasks in different fields by mining the potential information of the network structure.Current real-life networks are often large in scale and complex in structure,and many traditional methods cannot handle these networks.Many methods lack prior knowledge in the selection and initialization of the number of model classes.Some quick heuristics ignore the influence of nodes and the importance of central nodes.To solve these problems,we propose a method of network community discovery based on node centrality measurement.We believe that the central node should have high density and dispersion,and designed a node centrality measurement method,which can actively obtain the number of nodes in the community and initialize the community central nodes.At the same time,we propose a sampling strategy based on centrality metrics to improve the convergence speed of the algorithm when dealing with large networks and avoid falling into local optimal solutions.We verify that the proposed community discovery method has better performance and robustness than traditional community discovery methods on large sparse graph data-sets.(3)Aiming at the problem of joint modeling and dynamic prediction of spatialtemporal graph data,we propose a Spatial-temporal graph convolutional neural network model.Deep learning shows strong learning capabilities and excellent performance on largescale structured data,but there are a large number of dynamically changing unstructured data in real life,which poses a huge challenge to the current deep learning technology.For example,in a transportation network,changes in traffic flow conditions are not only time-dependent but also space-dependent.How to use the spatial correlation information of the existing road traffic network and the time-dependent information of the traffic flow data to carry out unified modeling,and to predict the dynamic traffic network in real-time,accurately and efficiently,is the most challenging key technology.In view of the complexity,periodicity,volatility,and suddenness of traffic data,we constructed the Spatial-temporal sequence data of dynamic traffic graphs and proposed a spatial-temporal graph neural network model to fully mine the spatial-temporal association patterns of traffic flows.The model uses a flexible spatial attention mechanism,which can effectively aggregate information from adjacent roads;at the same time,a sequence model based on the self-attention mechanism is used to model the dynamic change process of traffic flow,which can be effectively used in short-term time dependence and global time dependence.The experimental results on various actual dynamic traffic map data also verify the effectiveness and superiority of this model over traditional algorithms.(4)Aiming at the problem of node noise in real graph data and robustness of graph neural networks,we propose a robust graph neural network model based on reinforced sampling strategy learning.The complex graph data in the real world is inevitably full of node noise,which brings great challenges to graph neural networks based on spatial neighbor sampling and feature aggregation.Therefore,to improve the robustness of GNNs to noisy data sets,we propose a spatial sampling strategy model based on reinforcement learning and a two-stage adaptive training framework.Through iterative learning of the reinforced sampling strategy network,benign samples are identified and sampled,thus avoiding noisy samples.For different application scenarios,we extend the learned sampling strategy to node-wise sampling and layer-wise sampling to improve the computational efficiency of the algorithm in the face of large-scale data.A large number of experiments on simulated noise data-sets based on real data and actual noise data-sets show that our algorithm has significant advantages in the face of noisy data compared with the state-of-the-art baseline algorithm.