The computation of the all-pairs shortest paths is an important graph algorithmic problem.When the graph changes,such as edge deletions/insertions,recalculating the shortest distance of a graph from scratch is costly....The computation of the all-pairs shortest paths is an important graph algorithmic problem.When the graph changes,such as edge deletions/insertions,recalculating the shortest distance of a graph from scratch is costly.In this paper,we investigate how to quickly maintain the shortest distance of the dynamic graph in the distributed memory system.For a distributed system with p processors,the state-of-art algorithm to recompute the shortest distance of a graph with n vertices from scratch requires O(n^(2)/√p)bandwidth cost and O(√plog^(2)p)latency cost.For the insertion of k edges,we give an incremental algorithm with a bandwidth cost of O(nk√p+k^(2))and a latency cost of O(logp).For typical scenarios where k=O(n/√p),the bandwidth and latency costs are reduced by a factor of O(√p)and O(√plogp),respectively.For the deletion of k edges,we give a decremental algorithm with a bandwidth cost of O(nk/√p+k^(2)+n^(2)/log^(3)p+|S|^(2)logp)and a latency cost of O(log^(3)p),where S is the separator size of a constructed graph and is related to the alteration degree of the shortest path of the dynamic graph.When k=O(n/√p)and S=O(n/√p),the bandwidth and latency costs are reduced by a factor of O(√p∕log^(3)p)and O(√p∕logp),respectively.展开更多
Reliable traffic flow prediction is crucial for mitigating urban congestion.This paper proposes Attentionbased spatiotemporal Interactive Dynamic Graph Convolutional Network(AIDGCN),a novel architecture integrating In...Reliable traffic flow prediction is crucial for mitigating urban congestion.This paper proposes Attentionbased spatiotemporal Interactive Dynamic Graph Convolutional Network(AIDGCN),a novel architecture integrating Interactive Dynamic Graph Convolution Network(IDGCN)with Temporal Multi-Head Trend-Aware Attention.Its core innovation lies in IDGCN,which uniquely splits sequences into symmetric intervals for interactive feature sharing via dynamic graphs,and a novel attention mechanism incorporating convolutional operations to capture essential local traffic trends—addressing a critical gap in standard attention for continuous data.For 15-and 60-min forecasting on METR-LA,AIDGCN achieves MAEs of 0.75%and 0.39%,and RMSEs of 1.32%and 0.14%,respectively.In the 60-min long-term forecasting of the PEMS-BAY dataset,the AIDGCN out-performs the MRA-BGCN method by 6.28%,4.93%,and 7.17%in terms of MAE,RMSE,and MAPE,respectively.Experimental results demonstrate the superiority of our pro-posed model over state-of-the-art methods.展开更多
Lateral movement represents the most covert and critical phase of Advanced Persistent Threats(APTs),and its detection still faces two primary challenges:sample scarcity and“cold start”of new entities.To address thes...Lateral movement represents the most covert and critical phase of Advanced Persistent Threats(APTs),and its detection still faces two primary challenges:sample scarcity and“cold start”of new entities.To address these challenges,we propose an Uncertainty-Driven Graph Embedding-Enhanced Lateral Movement Detection framework(UGEA-LMD).First,the framework employs event-level incremental encoding on a continuous-time graph to capture fine-grained behavioral evolution,enabling newly appearing nodes to retain temporal contextual awareness even in the absence of historical interactions and thereby fundamentally mitigating the cold-start problem.Second,in the embedding space,we model the dependency structure among feature dimensions using a Gaussian copula to quantify the uncertainty distribution,and generate augmented samples with consistent structural and semantic properties through adaptive sampling,thus expanding the representation space of sparse samples and enhancing the model’s generalization under sparse sample conditions.Unlike static graph methods that cannot model temporal dependencies or data augmentation techniques that depend on predefined structures,UGEA-LMD offers both superior temporaldynamic modeling and structural generalization.Experimental results on the large-scale LANL log dataset demonstrate that,under the transductive setting,UGEA-LMD achieves an AUC of 0.9254;even when 10%of nodes or edges are withheld during training,UGEA-LMD significantly outperforms baseline methods on metrics such as recall and AUC,confirming its robustness and generalization capability in sparse-sample and cold-start scenarios.展开更多
Knowledge graphs often suffer from sparsity and incompleteness.Knowledge graph reasoning is an effective way to address these issues.Unlike static knowledge graph reasoning,which is invariant over time,dynamic knowled...Knowledge graphs often suffer from sparsity and incompleteness.Knowledge graph reasoning is an effective way to address these issues.Unlike static knowledge graph reasoning,which is invariant over time,dynamic knowledge graph reasoning is more challenging due to its temporal nature.In essence,within each time step in a dynamic knowledge graph,there exists structural dependencies among entities and relations,whereas between adjacent time steps,there exists temporal continuity.Based on these structural and temporal characteristics,we propose a model named“DKGR-DR”to learn distributed representations of entities and relations by combining recurrent neural networks and graph neural networks to capture structural dependencies and temporal continuity in DKGs.In addition,we construct a static attribute graph to represent entities’inherent properties.DKGR-DR is capable of modeling both dynamic and static aspects of entities,enabling effective entity prediction and relation prediction.We conduct experiments on ICEWS05-15,ICEWS18,and ICEWS14 to demonstrate that DKGR-DR achieves competitive performance.展开更多
Large-scale graphs usually exhibit global sparsity with local cohesiveness,and mining the representative cohesive subgraphs is a fundamental problem in graph analysis.The k-truss is one of the most commonly studied co...Large-scale graphs usually exhibit global sparsity with local cohesiveness,and mining the representative cohesive subgraphs is a fundamental problem in graph analysis.The k-truss is one of the most commonly studied cohesive subgraphs,in which each edge is formed in at least k 2 triangles.A critical issue in mining a k-truss lies in the computation of the trussness of each edge,which is the maximum value of k that an edge can be in a k-truss.Existing works mostly focus on truss computation in static graphs by sequential models.However,the graphs are constantly changing dynamically in the real world.We study distributed truss computation in dynamic graphs in this paper.In particular,we compute the trussness of edges based on the local nature of the k-truss in a synchronized node-centric distributed model.Iteratively decomposing the trussness of edges by relying only on local topological information is possible with the proposed distributed decomposition algorithm.Moreover,the distributed maintenance algorithm only needs to update a small amount of dynamic information to complete the computation.Extensive experiments have been conducted to show the scalability and efficiency of the proposed algorithm.展开更多
The increasing popularity of the Internet and the widespread use of information technology have led to a rise in the number and sophistication of network attacks and security threats.Intrusion detection systems are cr...The increasing popularity of the Internet and the widespread use of information technology have led to a rise in the number and sophistication of network attacks and security threats.Intrusion detection systems are crucial to network security,playing a pivotal role in safeguarding networks from potential threats.However,in the context of an evolving landscape of sophisticated and elusive attacks,existing intrusion detection methodologies often overlook critical aspects such as changes in network topology over time and interactions between hosts.To address these issues,this paper proposes a real-time network intrusion detection method based on graph neural networks.The proposedmethod leverages the advantages of graph neural networks and employs a straightforward graph construction method to represent network traffic as dynamic graph-structured data.Additionally,a graph convolution operation with a multi-head attention mechanism is utilized to enhance the model’s ability to capture the intricate relationships within the graph structure comprehensively.Furthermore,it uses an integrated graph neural network to address dynamic graphs’structural and topological changes at different time points and the challenges of edge embedding in intrusion detection data.The edge classification problem is effectively transformed into node classification by employing a line graph data representation,which facilitates fine-grained intrusion detection tasks on dynamic graph node feature representations.The efficacy of the proposed method is evaluated using two commonly used intrusion detection datasets,UNSW-NB15 and NF-ToN-IoT-v2,and results are compared with previous studies in this field.The experimental results demonstrate that our proposed method achieves 99.3%and 99.96%accuracy on the two datasets,respectively,and outperforms the benchmark model in several evaluation metrics.展开更多
Accurate recognition of flight deck operations for carrier-based aircraft, based on operation trajectories, is critical for optimizing carrier-based aircraft performance. This recognition involves understanding short-...Accurate recognition of flight deck operations for carrier-based aircraft, based on operation trajectories, is critical for optimizing carrier-based aircraft performance. This recognition involves understanding short-term and long-term spatial collaborative relationships among support agents and positions from long spatial–temporal trajectories. While the existing methods excel at recognizing collaborative behaviors from short trajectories, they often struggle with long spatial–temporal trajectories. To address this challenge, this paper introduces a dynamic graph method to enhance flight deck operation recognition. First, spatial–temporal collaborative relationships are modeled as a dynamic graph. Second, a discretized and compressed method is proposed to assign values to the states of this dynamic graph. To extract features that represent diverse collaborative relationships among agents and account for the duration of these relationships, a biased random walk is then conducted. Subsequently, the Swin Transformer is employed to comprehend spatial–temporal collaborative relationships, and a fully connected layer is applied to deck operation recognition. Finally, to address the scarcity of real datasets, a simulation pipeline is introduced to generate deck operations in virtual flight deck scenarios. Experimental results on the simulation dataset demonstrate the superior performance of the proposed method.展开更多
Dynamic publishing of social network graphs offers insights into user behavior but brings privacy risks, notably re-identification attacks on evolving data snapshots. Existing methods based on -anonymity can mitigate ...Dynamic publishing of social network graphs offers insights into user behavior but brings privacy risks, notably re-identification attacks on evolving data snapshots. Existing methods based on -anonymity can mitigate these attacks but are cumbersome, neglect dynamic protection of community structure, and lack precise utility measures. To address these challenges, we present a dynamic social network graph anonymity scheme with community structure protection (DSNGA-CSP), which achieves the dynamic anonymization process by incorporating community detection. First, DSNGA-CSP categorizes communities of the original graph into three types at each timestamp, and only partitions community subgraphs for a specific category at each updated timestamp. Then, DSNGA-CSP achieves intra-community and inter-community anonymization separately to retain more of the community structure of the original graph at each timestamp. It anonymizes community subgraphs by the proposed novel -composition method and anonymizes inter-community edges by edge isomorphism. Finally, a novel information loss metric is introduced in DSNGA-CSP to precisely capture the utility of the anonymized graph through original information preservation and anonymous information changes. Extensive experiments conducted on five real-world datasets demonstrate that DSNGA-CSP consistently outperforms existing methods, providing a more effective balance between privacy and utility. Specifically, DSNGA-CSP shows an average utility improvement of approximately 30% compared to TAKG and CTKGA for three dynamic graph datasets, according to the proposed information loss metric IL.展开更多
Under the paradigm of Industry 5.0,intelligent manufacturing transcends mere efficiency enhancement by emphasizing human-machine collaboration,where human expertise plays a central role in assembly processes.Despite a...Under the paradigm of Industry 5.0,intelligent manufacturing transcends mere efficiency enhancement by emphasizing human-machine collaboration,where human expertise plays a central role in assembly processes.Despite advancements in intelligent and digital technologies,assembly process design still heavily relies on manual knowledge reuse,and inefficiencies and inconsistent quality in process documentation are caused.To address the aforementioned issues,this paper proposes a knowledge push method of complex product assembly process design based on distillation model-based dynamically enhanced graph and Bayesian network.First,an initial knowledge graph is constructed using a BERT-BiLSTM-CRF model trained with integrated human expertise and a fine-tuned large language model.Then,a confidence-based dynamic weighted fusion strategy is employed to achieve dynamic incremental construction of the knowledge graph with low resource consumption.Subsequently,a Bayesian network model is constructed based on the relationships between assembly components,assembly features,and operations.Bayesian network reasoning is used to push assembly process knowledge under different design requirements.Finally,the feasibility of the Bayesian network construction method and the effectiveness of Bayesian network reasoning are verified through a specific example,significantly improving the utilization of assembly process knowledge and the efficiency of assembly process design.展开更多
A dynamic graph(DG)is adopted to portray the evolving interplay between nodes in real-world scenarios prevalently.A high-order graph convolutional network(HGCN)is equipped with the ability to represent a DG by the spa...A dynamic graph(DG)is adopted to portray the evolving interplay between nodes in real-world scenarios prevalently.A high-order graph convolutional network(HGCN)is equipped with the ability to represent a DG by the spatial-temporal message passing mechanism built on tensor product.Concretely,an HGCN utilizes the discrete Fourier transform(DFT)to implement temporal message passing and then employs face-wise product to realize spatial message passing.However,DFT is only a special case of assorted time-frequency transforms,which considers the complex temporal patterns partially,thereby resulting in an inaccurate temporal message passing possibly.To address this issue,this study proposes six advanced time-frequency transform-incorporated HGCNs(TF-HGCNs)with discrete Fourier,discrete Hartley,discrete cosine,Haar wavelet,Walsh Hadamard,and slant transforms.In addition,a potent ensemble is built regarding the proposed six TF-HGCNs as the bases.Finally,the corresponding theoretical proof is presented.Empirical studies on six DG datasets demonstrate that owing to diverse time-frequency transforms,the proposed six TF-HGCNs significantly outperform state-of-the-art models in addressing the task of link weight estimation.Moreover,their ensemble outstrips each base's performance.展开更多
The visualization of dynamic graphs is a challenging task owing to the various properties of the underlying relational data and the additional time-varying property.For sparse and small graphs,the most efficient appro...The visualization of dynamic graphs is a challenging task owing to the various properties of the underlying relational data and the additional time-varying property.For sparse and small graphs,the most efficient approach to such visualization is node-link diagrams,whereas for dense graphs with attached data,adjacency matrices might be the better choice.Because graphs can contain both properties,being globally sparse and locally dense,a combination of several visual metaphors as well as static and dynamic visualizations is beneficial.In this paper,a visually and algorithmically scalable approach that provides views and perspectives on graphs as interactively linked node-link and adjacency matrix visualizations is described.As the novelty of this technique,insights such as clusters or anomalies from one or several combined views can be used to influence the layout or reordering of the other views.Moreover,the importance of nodes and node groups can be detected,computed,and visualized by considering several layout and reordering properties in combination as well as different edge properties for the same set of nodes.As an additional feature set,an automatic identification of groups,clusters,and outliers is provided over time,and based on the visual outcome of the node-link and matrix visualizations,the repertoire of the supported layout and matrix reordering techniques is extended,and more interaction techniques are provided when considering the dynamics of the graph data.Finally,a small user experiment was conducted to investigate the usability of the proposed approach.The usefulness of the proposed tool is illustrated by applying it to a graph dataset,such as e co-authorships,co-citations,and a Comprehensible Perl Archive Network distribution.展开更多
Jaundice is a common and complex clinical symptom potentially occurring in hepatology, general surgery, pediatrics, infectious diseases, gynecology, and obstetrics, and it is faidy difficult to distinguish the cause o...Jaundice is a common and complex clinical symptom potentially occurring in hepatology, general surgery, pediatrics, infectious diseases, gynecology, and obstetrics, and it is faidy difficult to distinguish the cause of jaundice in clinical practice, especially for general practitioners in less developed regions. With collaboration between physicians and artificial intelligence engineers, a comprehensive knowledge base relevant to jaundice was created based on demographic information, symptoms, physical signs, laboratory tests, imaging diagnosis, medical histories, and risk factors. Then a diagnostic modeling and reasoning system using the dynamic uncertain causality graph was proposed. A modularized modeling scheme was presented to reduce the complexity of model construction, providing multiple perspectives and arbitrary granularity for disease causality representations. A ＂chaining＂ inference algorithm and weighted logic operation mechanism were employed to guarantee the exactness and efficiency of diagnostic rea- soning under situations of incomplete and uncertain information. Moreover, the causal interactions among diseases and symptoms intuitively demonstrated the reasoning process in a graphical manner. Verification was performed using 203 randomly pooled clinical cases, and the accuracy was 99.01% and 84.73%, respectively, with or without laboratory tests in the model. The solutions were more explicable and convincing than common methods such as Bayesian Networks, further increasing the objectivity of clinical decision-making. The promising results indicated that our model could be potentially used in intelligent diagnosis and help decrease public health expenditure.展开更多
Unsupervised learning methods such as graph contrastive learning have been used for dynamic graph represen-tation learning to eliminate the dependence of labels.However,existing studies neglect positional information ...Unsupervised learning methods such as graph contrastive learning have been used for dynamic graph represen-tation learning to eliminate the dependence of labels.However,existing studies neglect positional information when learning discrete snapshots,resulting in insufficient network topology learning.At the same time,due to the lack of appropriate data augmentation methods,it is difficult to capture the evolving patterns of the network effectively.To address the above problems,a position-aware and subgraph enhanced dynamic graph contrastive learning method is proposed for discrete-time dynamic graphs.Firstly,the global snapshot is built based on the historical snapshots to express the stable pattern of the dynamic graph,and the random walk is used to obtain the position representation by learning the positional information of the nodes.Secondly,a new data augmentation method is carried out from the perspectives of short-term changes and long-term stable structures of dynamic graphs.Specifically,subgraph sampling based on snapshots and global snapshots is used to obtain two structural augmentation views,and node structures and evolving patterns are learned by combining graph neural network,gated recurrent unit,and attention mechanism.Finally,the quality of node representation is improved by combining the contrastive learning between different structural augmentation views and between the two representations of structure and position.Experimental results on four real datasets show that the performance of the proposed method is better than the existing unsupervised methods,and it is more competitive than the supervised learning method under a semi-supervised setting.展开更多
Program slice has many applications such as program debugging, testing, maintenance, and complexity measurement. A static slice consists of all statements in program P that may effect the value of variable v a...Program slice has many applications such as program debugging, testing, maintenance, and complexity measurement. A static slice consists of all statements in program P that may effect the value of variable v at some point p , and a dynamic slice consists only of statements that influence the value of variable occurrence for specific program inputs. In this paper, we concern the problem of dynamic slicing of object oriented programs which, to our knowledge, has not been addressed in the literatures. To solve this problem, we present the dynamic object oriented dependence graph (DODG)which is an arc classified digraph to explicitly represent various dynamic dependence between statement instances for a particular execution of an object oriented program. Based on the DODG, we present a two phase backward algorithm for computing a dynamic slice of an object oriented program.展开更多
Accurate significant wave height(SWH)prediction is essential for the development and utilization of wave energy.Deep learning methods such as recurrent and convolutional neural networks have achieved good results in S...Accurate significant wave height(SWH)prediction is essential for the development and utilization of wave energy.Deep learning methods such as recurrent and convolutional neural networks have achieved good results in SWH forecasting.However,these methods do not adapt well to dynamic seasonal variations in wave data.In this study,we propose a novel method—the spatiotemporal dynamic graph(STDG)neural network.This method predicts the SWH of multiple nodes based on dynamic graph modeling and multi-characteristic fusion.First,considering the dynamic seasonal variations in the wave direction over time,the network models wave dynamic spatial dependencies from long-and short-term pattern perspectives.Second,to correlate multiple characteristics with SWH,the network introduces a cross-characteristic transformer to effectively fuse multiple characteristics.Finally,we conducted experiments on two datasets from the South China Sea and East China Sea to validate the proposed method and compared it with five prediction methods in the three categories.The experimental results show that the proposed method achieves the best performance at all predictive scales and has greater advantages for extreme value prediction.Furthermore,an analysis of the dynamic graph shows that the proposed method captures the seasonal variation mechanism of the waves.展开更多
Dear Editor,This letter proposes the graph tensor alliance attention network(GT-A^(2)T)to represent a dynamic graph(DG)precisely.Its main idea includes 1)Establishing a unified spatio-temporal message propagation fram...Dear Editor,This letter proposes the graph tensor alliance attention network(GT-A^(2)T)to represent a dynamic graph(DG)precisely.Its main idea includes 1)Establishing a unified spatio-temporal message propagation framework on a DG via the tensor product for capturing the complex cohesive spatio-temporal interdependencies precisely and 2)Acquiring the alliance attention scores by node features and favorable high-order structural correlations.展开更多
Accurate prediction of landslide displacement is crucial for effective early warning of landslide disasters.While most existing prediction methods focus on time-series forecasting for individual monitoring points,ther...Accurate prediction of landslide displacement is crucial for effective early warning of landslide disasters.While most existing prediction methods focus on time-series forecasting for individual monitoring points,there is limited research on the spatiotemporal characteristics of landslide deformation.This paper proposes a novel Multi-Relation Spatiotemporal Graph Residual Network with Multi-Level Feature Attention(MFA-MRSTGRN)that effectively improves the prediction performance of landslide displacement through spatiotemporal fusion.This model integrates internal seepage factors as data feature enhancements with external triggering factors,allowing for accurate capture of the complex spatiotemporal characteristics of landslide displacement and the construction of a multi-source heterogeneous dataset.The MFA-MRSTGRN model incorporates dynamic graph theory and four key modules:multilevel feature attention,temporal-residual decomposition,spatial multi-relational graph convolution,and spatiotemporal fusion prediction.This comprehensive approach enables the efficient analyses of multi-source heterogeneous datasets,facilitating adaptive exploration of the evolving multi-relational,multi-dimensional spatiotemporal complexities in landslides.When applying this model to predict the displacement of the Liangshuijing landslide,we demonstrate that the MFA-MRSTGRN model surpasses traditional models,such as random forest(RF),long short-term memory(LSTM),and spatial temporal graph convolutional networks(ST-GCN)models in terms of various evaluation metrics including mean absolute error(MAE=1.27 mm),root mean square error(RMSE=1.49 mm),mean absolute percentage error(MAPE=0.026),and R-squared(R^(2)=0.88).Furthermore,feature ablation experiments indicate that incorporating internal seepage factors improves the predictive performance of landslide displacement models.This research provides an advanced and reliable method for landslide displacement prediction.展开更多
Faster internet, IoT, and social media have reformed the conventional web into a collaborative web resulting in enormous user-generated content. Several studies are focused on such content;however, they mainly focus o...Faster internet, IoT, and social media have reformed the conventional web into a collaborative web resulting in enormous user-generated content. Several studies are focused on such content;however, they mainly focus on textual data, thus undermining the importance of metadata. Considering this gap, we provide a temporal pattern mining framework to model and utilize user-generated content's metadata. First, we scrap 2.1 million tweets from Twitter between Nov-2020 to Sep-2021 about 100 hashtag keywords and present these tweets into 100 User-Tweet-Hashtag (UTH) dynamic graphs. Second, we extract and identify four time-series in three timespans (Day, Hour, and Minute) from UTH dynamic graphs. Lastly, we model these four time-series with three machine learning algorithms to mine temporal patterns with the accuracy of 95.89%, 93.17%, 90.97%, and 93.73%, respectively. We demonstrate that user-generated content's metadata contains valuable information, which helps to understand the users' collective behavior and can be beneficial for business and research. Dataset and codes are publicly available;the link is given in the dataset section.展开更多
Lipases with high thermal stability have greater application in industrial production.Focusing on wild-type lipase and their thermotolerant mutants,this study employs dynamic graph embedding to explore the change of s...Lipases with high thermal stability have greater application in industrial production.Focusing on wild-type lipase and their thermotolerant mutants,this study employs dynamic graph embedding to explore the change of spatiotemporal characteristics in residue-residue interactions,analyzing the relationship between residue mutations and the thermal stability of lipase.K-means clustering is used to analyze the synergistic relationships between residues,revealing that thermotolerant mutants achieve higher thermal stability by enhancing the synergistic interactions between secondary structures,resulting in a more balanced and tightly-knit internal structure.Critical residues are identified using anomaly node detection methods,showing that residues with spatiotemporal instability are mainly distributed on highly flexible loop regions.Specifically,mutations at Tyr89 and Asp132 restrict the motion range of the loops,making the lipase structure more stable.The study demonstrates that mutating highly flexible regions to increase structural rigidity can effectively enhance the thermal stability of lipases.展开更多
Accurately predicting the State of Health(SOH)of lithium-ion batteries is a critical challenge to ensure their reliability and safety in energy storage systems,such as electric vehicles and renewable energy grids.The ...Accurately predicting the State of Health(SOH)of lithium-ion batteries is a critical challenge to ensure their reliability and safety in energy storage systems,such as electric vehicles and renewable energy grids.The intricate battery degradation process is influenced by evolving spatial and temporal interactions among health indicators.Existing methods often fail to capture the dynamic interactions between health indicators over time,resulting in limited predictive accuracy.To address these challenges,we propose a novel framework,Dynamic Graph Learning with Spatial-Temporal Fusion Attention(DGL-STFA),which transforms health indicator series time-data into time-evolving graph representations.The framework employs multi-scale convolutional neural networks to capture diverse temporal patterns,a self-attention mechanism to construct dynamic adjacency matrices that adapt over time,and a temporal attention mechanism to identify and prioritize key moments that influence battery degradation.This combination enables DGL-STFA to effectively model both dynamic spatial relationships and long-term temporal dependencies,enhancing SOH prediction accuracy.Extensive experiments were conducted on the NASA and CALCE battery datasets,comparing this framework with traditional time-series prediction methods and other graph-based prediction methods.The results demonstrate that our framework significantly improves prediction accuracy,with a mean absolute error more than 30%lower than other methods.Further analysis demonstrated the robustness of DGL-STFA across various battery life stages,including early,mid,and end-of-life phases.These results highlight the capability of DGL-STFA to accurately predict SOH,addressing critical challenges in advancing battery health monitoring for energy storage applications.展开更多
基金supported in part by National Natural Science Foundation of China under Grants 61972447 and 61832006.
文摘The computation of the all-pairs shortest paths is an important graph algorithmic problem.When the graph changes,such as edge deletions/insertions,recalculating the shortest distance of a graph from scratch is costly.In this paper,we investigate how to quickly maintain the shortest distance of the dynamic graph in the distributed memory system.For a distributed system with p processors,the state-of-art algorithm to recompute the shortest distance of a graph with n vertices from scratch requires O(n^(2)/√p)bandwidth cost and O(√plog^(2)p)latency cost.For the insertion of k edges,we give an incremental algorithm with a bandwidth cost of O(nk√p+k^(2))and a latency cost of O(logp).For typical scenarios where k=O(n/√p),the bandwidth and latency costs are reduced by a factor of O(√p)and O(√plogp),respectively.For the deletion of k edges,we give a decremental algorithm with a bandwidth cost of O(nk/√p+k^(2)+n^(2)/log^(3)p+|S|^(2)logp)and a latency cost of O(log^(3)p),where S is the separator size of a constructed graph and is related to the alteration degree of the shortest path of the dynamic graph.When k=O(n/√p)and S=O(n/√p),the bandwidth and latency costs are reduced by a factor of O(√p∕log^(3)p)and O(√p∕logp),respectively.
文摘Reliable traffic flow prediction is crucial for mitigating urban congestion.This paper proposes Attentionbased spatiotemporal Interactive Dynamic Graph Convolutional Network(AIDGCN),a novel architecture integrating Interactive Dynamic Graph Convolution Network(IDGCN)with Temporal Multi-Head Trend-Aware Attention.Its core innovation lies in IDGCN,which uniquely splits sequences into symmetric intervals for interactive feature sharing via dynamic graphs,and a novel attention mechanism incorporating convolutional operations to capture essential local traffic trends—addressing a critical gap in standard attention for continuous data.For 15-and 60-min forecasting on METR-LA,AIDGCN achieves MAEs of 0.75%and 0.39%,and RMSEs of 1.32%and 0.14%,respectively.In the 60-min long-term forecasting of the PEMS-BAY dataset,the AIDGCN out-performs the MRA-BGCN method by 6.28%,4.93%,and 7.17%in terms of MAE,RMSE,and MAPE,respectively.Experimental results demonstrate the superiority of our pro-posed model over state-of-the-art methods.
基金supported by the Zhongyuan University of Technology Discipline Backbone Teacher Support Program Project(No.GG202417)the Key Research and Development Program of Henan under Grant 251111212000.
文摘Lateral movement represents the most covert and critical phase of Advanced Persistent Threats(APTs),and its detection still faces two primary challenges:sample scarcity and“cold start”of new entities.To address these challenges,we propose an Uncertainty-Driven Graph Embedding-Enhanced Lateral Movement Detection framework(UGEA-LMD).First,the framework employs event-level incremental encoding on a continuous-time graph to capture fine-grained behavioral evolution,enabling newly appearing nodes to retain temporal contextual awareness even in the absence of historical interactions and thereby fundamentally mitigating the cold-start problem.Second,in the embedding space,we model the dependency structure among feature dimensions using a Gaussian copula to quantify the uncertainty distribution,and generate augmented samples with consistent structural and semantic properties through adaptive sampling,thus expanding the representation space of sparse samples and enhancing the model’s generalization under sparse sample conditions.Unlike static graph methods that cannot model temporal dependencies or data augmentation techniques that depend on predefined structures,UGEA-LMD offers both superior temporaldynamic modeling and structural generalization.Experimental results on the large-scale LANL log dataset demonstrate that,under the transductive setting,UGEA-LMD achieves an AUC of 0.9254;even when 10%of nodes or edges are withheld during training,UGEA-LMD significantly outperforms baseline methods on metrics such as recall and AUC,confirming its robustness and generalization capability in sparse-sample and cold-start scenarios.
基金supported byNationalNatural Science Foundation of China(GrantNos.62071098,U24B20128)Sichuan Science and Technology Program(Grant No.2022YFG0319).
文摘Knowledge graphs often suffer from sparsity and incompleteness.Knowledge graph reasoning is an effective way to address these issues.Unlike static knowledge graph reasoning,which is invariant over time,dynamic knowledge graph reasoning is more challenging due to its temporal nature.In essence,within each time step in a dynamic knowledge graph,there exists structural dependencies among entities and relations,whereas between adjacent time steps,there exists temporal continuity.Based on these structural and temporal characteristics,we propose a model named“DKGR-DR”to learn distributed representations of entities and relations by combining recurrent neural networks and graph neural networks to capture structural dependencies and temporal continuity in DKGs.In addition,we construct a static attribute graph to represent entities’inherent properties.DKGR-DR is capable of modeling both dynamic and static aspects of entities,enabling effective entity prediction and relation prediction.We conduct experiments on ICEWS05-15,ICEWS18,and ICEWS14 to demonstrate that DKGR-DR achieves competitive performance.
基金supported in part by the National Key Research and Development Program of China(No.2020YFB1005900)in part by National Natural Science Foundation of China(No.62122042)in part by Shandong University Multidisciplinary Research and Innovation Team of Young Scholars(No.2020QNQT017)。
文摘Large-scale graphs usually exhibit global sparsity with local cohesiveness,and mining the representative cohesive subgraphs is a fundamental problem in graph analysis.The k-truss is one of the most commonly studied cohesive subgraphs,in which each edge is formed in at least k 2 triangles.A critical issue in mining a k-truss lies in the computation of the trussness of each edge,which is the maximum value of k that an edge can be in a k-truss.Existing works mostly focus on truss computation in static graphs by sequential models.However,the graphs are constantly changing dynamically in the real world.We study distributed truss computation in dynamic graphs in this paper.In particular,we compute the trussness of edges based on the local nature of the k-truss in a synchronized node-centric distributed model.Iteratively decomposing the trussness of edges by relying only on local topological information is possible with the proposed distributed decomposition algorithm.Moreover,the distributed maintenance algorithm only needs to update a small amount of dynamic information to complete the computation.Extensive experiments have been conducted to show the scalability and efficiency of the proposed algorithm.
文摘The increasing popularity of the Internet and the widespread use of information technology have led to a rise in the number and sophistication of network attacks and security threats.Intrusion detection systems are crucial to network security,playing a pivotal role in safeguarding networks from potential threats.However,in the context of an evolving landscape of sophisticated and elusive attacks,existing intrusion detection methodologies often overlook critical aspects such as changes in network topology over time and interactions between hosts.To address these issues,this paper proposes a real-time network intrusion detection method based on graph neural networks.The proposedmethod leverages the advantages of graph neural networks and employs a straightforward graph construction method to represent network traffic as dynamic graph-structured data.Additionally,a graph convolution operation with a multi-head attention mechanism is utilized to enhance the model’s ability to capture the intricate relationships within the graph structure comprehensively.Furthermore,it uses an integrated graph neural network to address dynamic graphs’structural and topological changes at different time points and the challenges of edge embedding in intrusion detection data.The edge classification problem is effectively transformed into node classification by employing a line graph data representation,which facilitates fine-grained intrusion detection tasks on dynamic graph node feature representations.The efficacy of the proposed method is evaluated using two commonly used intrusion detection datasets,UNSW-NB15 and NF-ToN-IoT-v2,and results are compared with previous studies in this field.The experimental results demonstrate that our proposed method achieves 99.3%and 99.96%accuracy on the two datasets,respectively,and outperforms the benchmark model in several evaluation metrics.
基金co-supported by the National Key Research and Development Program of China(No. 2021YFB3301504)the National Natural Science Foundation of China (Nos. 62072415, 62036010, 42301526, 62372416 and 62472389)the National Natural Science Foundation of Henan Province, China (No. 242300421215)
文摘Accurate recognition of flight deck operations for carrier-based aircraft, based on operation trajectories, is critical for optimizing carrier-based aircraft performance. This recognition involves understanding short-term and long-term spatial collaborative relationships among support agents and positions from long spatial–temporal trajectories. While the existing methods excel at recognizing collaborative behaviors from short trajectories, they often struggle with long spatial–temporal trajectories. To address this challenge, this paper introduces a dynamic graph method to enhance flight deck operation recognition. First, spatial–temporal collaborative relationships are modeled as a dynamic graph. Second, a discretized and compressed method is proposed to assign values to the states of this dynamic graph. To extract features that represent diverse collaborative relationships among agents and account for the duration of these relationships, a biased random walk is then conducted. Subsequently, the Swin Transformer is employed to comprehend spatial–temporal collaborative relationships, and a fully connected layer is applied to deck operation recognition. Finally, to address the scarcity of real datasets, a simulation pipeline is introduced to generate deck operations in virtual flight deck scenarios. Experimental results on the simulation dataset demonstrate the superior performance of the proposed method.
基金supported by the Natural Science Foundation of China(No.U22A2099)the Innovation Project of Guangxi Graduate Education(YCBZ2023130).
文摘Dynamic publishing of social network graphs offers insights into user behavior but brings privacy risks, notably re-identification attacks on evolving data snapshots. Existing methods based on -anonymity can mitigate these attacks but are cumbersome, neglect dynamic protection of community structure, and lack precise utility measures. To address these challenges, we present a dynamic social network graph anonymity scheme with community structure protection (DSNGA-CSP), which achieves the dynamic anonymization process by incorporating community detection. First, DSNGA-CSP categorizes communities of the original graph into three types at each timestamp, and only partitions community subgraphs for a specific category at each updated timestamp. Then, DSNGA-CSP achieves intra-community and inter-community anonymization separately to retain more of the community structure of the original graph at each timestamp. It anonymizes community subgraphs by the proposed novel -composition method and anonymizes inter-community edges by edge isomorphism. Finally, a novel information loss metric is introduced in DSNGA-CSP to precisely capture the utility of the anonymized graph through original information preservation and anonymous information changes. Extensive experiments conducted on five real-world datasets demonstrate that DSNGA-CSP consistently outperforms existing methods, providing a more effective balance between privacy and utility. Specifically, DSNGA-CSP shows an average utility improvement of approximately 30% compared to TAKG and CTKGA for three dynamic graph datasets, according to the proposed information loss metric IL.
基金Supported by National Key Research and Development Program(Grant No.2024YFB3312700)National Natural Science Foundation of China(Grant No.52405541)the Changzhou Municipal Sci&Tech Program(Grant No.CJ20241131)。
文摘Under the paradigm of Industry 5.0,intelligent manufacturing transcends mere efficiency enhancement by emphasizing human-machine collaboration,where human expertise plays a central role in assembly processes.Despite advancements in intelligent and digital technologies,assembly process design still heavily relies on manual knowledge reuse,and inefficiencies and inconsistent quality in process documentation are caused.To address the aforementioned issues,this paper proposes a knowledge push method of complex product assembly process design based on distillation model-based dynamically enhanced graph and Bayesian network.First,an initial knowledge graph is constructed using a BERT-BiLSTM-CRF model trained with integrated human expertise and a fine-tuned large language model.Then,a confidence-based dynamic weighted fusion strategy is employed to achieve dynamic incremental construction of the knowledge graph with low resource consumption.Subsequently,a Bayesian network model is constructed based on the relationships between assembly components,assembly features,and operations.Bayesian network reasoning is used to push assembly process knowledge under different design requirements.Finally,the feasibility of the Bayesian network construction method and the effectiveness of Bayesian network reasoning are verified through a specific example,significantly improving the utilization of assembly process knowledge and the efficiency of assembly process design.
基金supported in part by the National Natural Science Foundation of China(62372385,62272078,62002337)Chongqing Natural Science Foundation(CSTB2022NSCQ-MSX1486,CSTB2023NSCQ-LZX0069)。
文摘A dynamic graph(DG)is adopted to portray the evolving interplay between nodes in real-world scenarios prevalently.A high-order graph convolutional network(HGCN)is equipped with the ability to represent a DG by the spatial-temporal message passing mechanism built on tensor product.Concretely,an HGCN utilizes the discrete Fourier transform(DFT)to implement temporal message passing and then employs face-wise product to realize spatial message passing.However,DFT is only a special case of assorted time-frequency transforms,which considers the complex temporal patterns partially,thereby resulting in an inaccurate temporal message passing possibly.To address this issue,this study proposes six advanced time-frequency transform-incorporated HGCNs(TF-HGCNs)with discrete Fourier,discrete Hartley,discrete cosine,Haar wavelet,Walsh Hadamard,and slant transforms.In addition,a potent ensemble is built regarding the proposed six TF-HGCNs as the bases.Finally,the corresponding theoretical proof is presented.Empirical studies on six DG datasets demonstrate that owing to diverse time-frequency transforms,the proposed six TF-HGCNs significantly outperform state-of-the-art models in addressing the task of link weight estimation.Moreover,their ensemble outstrips each base's performance.
文摘The visualization of dynamic graphs is a challenging task owing to the various properties of the underlying relational data and the additional time-varying property.For sparse and small graphs,the most efficient approach to such visualization is node-link diagrams,whereas for dense graphs with attached data,adjacency matrices might be the better choice.Because graphs can contain both properties,being globally sparse and locally dense,a combination of several visual metaphors as well as static and dynamic visualizations is beneficial.In this paper,a visually and algorithmically scalable approach that provides views and perspectives on graphs as interactively linked node-link and adjacency matrix visualizations is described.As the novelty of this technique,insights such as clusters or anomalies from one or several combined views can be used to influence the layout or reordering of the other views.Moreover,the importance of nodes and node groups can be detected,computed,and visualized by considering several layout and reordering properties in combination as well as different edge properties for the same set of nodes.As an additional feature set,an automatic identification of groups,clusters,and outliers is provided over time,and based on the visual outcome of the node-link and matrix visualizations,the repertoire of the supported layout and matrix reordering techniques is extended,and more interaction techniques are provided when considering the dynamics of the graph data.Finally,a small user experiment was conducted to investigate the usability of the proposed approach.The usefulness of the proposed tool is illustrated by applying it to a graph dataset,such as e co-authorships,co-citations,and a Comprehensible Perl Archive Network distribution.
基金supported by the Medical and Health Research Program of Zhejiang Province(No.2015KYB128)the Zhejiang Provincial Natural Science Foundation(No.LQ15H030004),China
文摘Jaundice is a common and complex clinical symptom potentially occurring in hepatology, general surgery, pediatrics, infectious diseases, gynecology, and obstetrics, and it is faidy difficult to distinguish the cause of jaundice in clinical practice, especially for general practitioners in less developed regions. With collaboration between physicians and artificial intelligence engineers, a comprehensive knowledge base relevant to jaundice was created based on demographic information, symptoms, physical signs, laboratory tests, imaging diagnosis, medical histories, and risk factors. Then a diagnostic modeling and reasoning system using the dynamic uncertain causality graph was proposed. A modularized modeling scheme was presented to reduce the complexity of model construction, providing multiple perspectives and arbitrary granularity for disease causality representations. A ＂chaining＂ inference algorithm and weighted logic operation mechanism were employed to guarantee the exactness and efficiency of diagnostic rea- soning under situations of incomplete and uncertain information. Moreover, the causal interactions among diseases and symptoms intuitively demonstrated the reasoning process in a graphical manner. Verification was performed using 203 randomly pooled clinical cases, and the accuracy was 99.01% and 84.73%, respectively, with or without laboratory tests in the model. The solutions were more explicable and convincing than common methods such as Bayesian Networks, further increasing the objectivity of clinical decision-making. The promising results indicated that our model could be potentially used in intelligent diagnosis and help decrease public health expenditure.
文摘Unsupervised learning methods such as graph contrastive learning have been used for dynamic graph represen-tation learning to eliminate the dependence of labels.However,existing studies neglect positional information when learning discrete snapshots,resulting in insufficient network topology learning.At the same time,due to the lack of appropriate data augmentation methods,it is difficult to capture the evolving patterns of the network effectively.To address the above problems,a position-aware and subgraph enhanced dynamic graph contrastive learning method is proposed for discrete-time dynamic graphs.Firstly,the global snapshot is built based on the historical snapshots to express the stable pattern of the dynamic graph,and the random walk is used to obtain the position representation by learning the positional information of the nodes.Secondly,a new data augmentation method is carried out from the perspectives of short-term changes and long-term stable structures of dynamic graphs.Specifically,subgraph sampling based on snapshots and global snapshots is used to obtain two structural augmentation views,and node structures and evolving patterns are learned by combining graph neural network,gated recurrent unit,and attention mechanism.Finally,the quality of node representation is improved by combining the contrastive learning between different structural augmentation views and between the two representations of structure and position.Experimental results on four real datasets show that the performance of the proposed method is better than the existing unsupervised methods,and it is more competitive than the supervised learning method under a semi-supervised setting.
文摘Program slice has many applications such as program debugging, testing, maintenance, and complexity measurement. A static slice consists of all statements in program P that may effect the value of variable v at some point p , and a dynamic slice consists only of statements that influence the value of variable occurrence for specific program inputs. In this paper, we concern the problem of dynamic slicing of object oriented programs which, to our knowledge, has not been addressed in the literatures. To solve this problem, we present the dynamic object oriented dependence graph (DODG)which is an arc classified digraph to explicitly represent various dynamic dependence between statement instances for a particular execution of an object oriented program. Based on the DODG, we present a two phase backward algorithm for computing a dynamic slice of an object oriented program.
基金The National Key R&D Program of China under contract No.2021YFC3101604。
文摘Accurate significant wave height(SWH)prediction is essential for the development and utilization of wave energy.Deep learning methods such as recurrent and convolutional neural networks have achieved good results in SWH forecasting.However,these methods do not adapt well to dynamic seasonal variations in wave data.In this study,we propose a novel method—the spatiotemporal dynamic graph(STDG)neural network.This method predicts the SWH of multiple nodes based on dynamic graph modeling and multi-characteristic fusion.First,considering the dynamic seasonal variations in the wave direction over time,the network models wave dynamic spatial dependencies from long-and short-term pattern perspectives.Second,to correlate multiple characteristics with SWH,the network introduces a cross-characteristic transformer to effectively fuse multiple characteristics.Finally,we conducted experiments on two datasets from the South China Sea and East China Sea to validate the proposed method and compared it with five prediction methods in the three categories.The experimental results show that the proposed method achieves the best performance at all predictive scales and has greater advantages for extreme value prediction.Furthermore,an analysis of the dynamic graph shows that the proposed method captures the seasonal variation mechanism of the waves.
基金supported in part by the National Natural Science Foundation of China(62372385).
文摘Dear Editor,This letter proposes the graph tensor alliance attention network(GT-A^(2)T)to represent a dynamic graph(DG)precisely.Its main idea includes 1)Establishing a unified spatio-temporal message propagation framework on a DG via the tensor product for capturing the complex cohesive spatio-temporal interdependencies precisely and 2)Acquiring the alliance attention scores by node features and favorable high-order structural correlations.
基金the funding support from the National Natural Science Foundation of China(Grant No.52308340)Chongqing Talent Innovation and Entrepreneurship Demonstration Team Project(Grant No.cstc2024ycjh-bgzxm0012)the Science and Technology Projects supported by China Coal Technology and Engineering Chongqing Design and Research Institute(Group)Co.,Ltd.(Grant No.H20230317).
文摘Accurate prediction of landslide displacement is crucial for effective early warning of landslide disasters.While most existing prediction methods focus on time-series forecasting for individual monitoring points,there is limited research on the spatiotemporal characteristics of landslide deformation.This paper proposes a novel Multi-Relation Spatiotemporal Graph Residual Network with Multi-Level Feature Attention(MFA-MRSTGRN)that effectively improves the prediction performance of landslide displacement through spatiotemporal fusion.This model integrates internal seepage factors as data feature enhancements with external triggering factors,allowing for accurate capture of the complex spatiotemporal characteristics of landslide displacement and the construction of a multi-source heterogeneous dataset.The MFA-MRSTGRN model incorporates dynamic graph theory and four key modules:multilevel feature attention,temporal-residual decomposition,spatial multi-relational graph convolution,and spatiotemporal fusion prediction.This comprehensive approach enables the efficient analyses of multi-source heterogeneous datasets,facilitating adaptive exploration of the evolving multi-relational,multi-dimensional spatiotemporal complexities in landslides.When applying this model to predict the displacement of the Liangshuijing landslide,we demonstrate that the MFA-MRSTGRN model surpasses traditional models,such as random forest(RF),long short-term memory(LSTM),and spatial temporal graph convolutional networks(ST-GCN)models in terms of various evaluation metrics including mean absolute error(MAE=1.27 mm),root mean square error(RMSE=1.49 mm),mean absolute percentage error(MAPE=0.026),and R-squared(R^(2)=0.88).Furthermore,feature ablation experiments indicate that incorporating internal seepage factors improves the predictive performance of landslide displacement models.This research provides an advanced and reliable method for landslide displacement prediction.
基金supported by the National Natural Science Foundation of China(grant no.61573328).
文摘Faster internet, IoT, and social media have reformed the conventional web into a collaborative web resulting in enormous user-generated content. Several studies are focused on such content;however, they mainly focus on textual data, thus undermining the importance of metadata. Considering this gap, we provide a temporal pattern mining framework to model and utilize user-generated content's metadata. First, we scrap 2.1 million tweets from Twitter between Nov-2020 to Sep-2021 about 100 hashtag keywords and present these tweets into 100 User-Tweet-Hashtag (UTH) dynamic graphs. Second, we extract and identify four time-series in three timespans (Day, Hour, and Minute) from UTH dynamic graphs. Lastly, we model these four time-series with three machine learning algorithms to mine temporal patterns with the accuracy of 95.89%, 93.17%, 90.97%, and 93.73%, respectively. We demonstrate that user-generated content's metadata contains valuable information, which helps to understand the users' collective behavior and can be beneficial for business and research. Dataset and codes are publicly available;the link is given in the dataset section.
基金supported by the National Natural Science Foundation of China(Grant number 62161050).
文摘Lipases with high thermal stability have greater application in industrial production.Focusing on wild-type lipase and their thermotolerant mutants,this study employs dynamic graph embedding to explore the change of spatiotemporal characteristics in residue-residue interactions,analyzing the relationship between residue mutations and the thermal stability of lipase.K-means clustering is used to analyze the synergistic relationships between residues,revealing that thermotolerant mutants achieve higher thermal stability by enhancing the synergistic interactions between secondary structures,resulting in a more balanced and tightly-knit internal structure.Critical residues are identified using anomaly node detection methods,showing that residues with spatiotemporal instability are mainly distributed on highly flexible loop regions.Specifically,mutations at Tyr89 and Asp132 restrict the motion range of the loops,making the lipase structure more stable.The study demonstrates that mutating highly flexible regions to increase structural rigidity can effectively enhance the thermal stability of lipases.
基金sponsored by the National Key Research and Development Program of China(No.2023YFB4606200)Key Program of Science and Technology of Yunnan Province,China (No.202302AB080020)Key Project of Shanghai Zhangjiang National Independent hnovation Demonstration Zone,China(No.ZJ2021-2D-006).
文摘Accurately predicting the State of Health(SOH)of lithium-ion batteries is a critical challenge to ensure their reliability and safety in energy storage systems,such as electric vehicles and renewable energy grids.The intricate battery degradation process is influenced by evolving spatial and temporal interactions among health indicators.Existing methods often fail to capture the dynamic interactions between health indicators over time,resulting in limited predictive accuracy.To address these challenges,we propose a novel framework,Dynamic Graph Learning with Spatial-Temporal Fusion Attention(DGL-STFA),which transforms health indicator series time-data into time-evolving graph representations.The framework employs multi-scale convolutional neural networks to capture diverse temporal patterns,a self-attention mechanism to construct dynamic adjacency matrices that adapt over time,and a temporal attention mechanism to identify and prioritize key moments that influence battery degradation.This combination enables DGL-STFA to effectively model both dynamic spatial relationships and long-term temporal dependencies,enhancing SOH prediction accuracy.Extensive experiments were conducted on the NASA and CALCE battery datasets,comparing this framework with traditional time-series prediction methods and other graph-based prediction methods.The results demonstrate that our framework significantly improves prediction accuracy,with a mean absolute error more than 30%lower than other methods.Further analysis demonstrated the robustness of DGL-STFA across various battery life stages,including early,mid,and end-of-life phases.These results highlight the capability of DGL-STFA to accurately predict SOH,addressing critical challenges in advancing battery health monitoring for energy storage applications.
