Graph transformation systems have become a general formal modeling language to describe many models in software development process.Behavioral modeling of dynamic systems and model-to-model transformations are only a ...Graph transformation systems have become a general formal modeling language to describe many models in software development process.Behavioral modeling of dynamic systems and model-to-model transformations are only a few examples in which graphs have been used to software development.But even the perfect graph transformation system must be equipped with automated analysis capabilities to let users understand whether such a formal specification fulfills their requirements.In this paper,we present a new solution to verify graph transformation systems using the Bogor model checker.The attributed graph grammars(AGG)-like graph transformation systems are translated to Bandera intermediate representation(BIR),the input language of Bogor,and Bogor verifies the model against some interesting properties defined by combining linear temporal logic(LTL) and special-purpose graph rules.Experimental results are encouraging,showing that in most cases our solution improves existing approaches in terms of both performance and expressiveness.展开更多
The basis graph \%G\% for a linear programming consists of all bases under pivot transformations. A degenerate optimal basis graph G * is a subgraph of \%G\% induced by all optimal bases at a degenerate optimal verte...The basis graph \%G\% for a linear programming consists of all bases under pivot transformations. A degenerate optimal basis graph G * is a subgraph of \%G\% induced by all optimal bases at a degenerate optimal vertex x 0. In this paper, several conditions for the characterization of G * are presented.展开更多
Circuits with switched current are described by an admittance matrix and seeking current transfers then means calculating the ratio of algebraic supplements of this matrix. As there are also graph methods of circuit a...Circuits with switched current are described by an admittance matrix and seeking current transfers then means calculating the ratio of algebraic supplements of this matrix. As there are also graph methods of circuit analysis in addition to algebraic methods, it is clearly possible in theory to carry out an analysis of the whole switched circuit in two-phase switching exclusively by the graph method as well. For this purpose it is possible to plot a Mason graph of a circuit, use transformation graphs to reduce Mason graphs for all the four phases of switching, and then plot a summary graph from the transformed graphs obtained this way. First the author draws nodes and possible branches, obtained by transformation graphs for transfers of EE （even-even） and OO （odd-odd） phases. In the next step, branches obtained by transformation graphs for EO and OE phase are drawn between these nodes, while their resulting transfer is 1 multiplied by z^1/2. This summary graph is extended by two branches from input node and to output node, the extended graph can then be interpreted by the Mason＇s relation to provide transparent current transfers. Therefore it is not necessary to compose a sum admittance matrix and to express this consequently in numbers, and so it is possible to reach the final result in a graphical way.展开更多
Graphs are used in various disciplines such as telecommunication,biological networks,as well as social networks.In large-scale networks,it is challenging to detect the communities by learning the distinct properties o...Graphs are used in various disciplines such as telecommunication,biological networks,as well as social networks.In large-scale networks,it is challenging to detect the communities by learning the distinct properties of the graph.As deep learning hasmade contributions in a variety of domains,we try to use deep learning techniques to mine the knowledge from large-scale graph networks.In this paper,we aim to provide a strategy for detecting communities using deep autoencoders and obtain generic neural attention to graphs.The advantages of neural attention are widely seen in the field of NLP and computer vision,which has low computational complexity for large-scale graphs.The contributions of the paper are summarized as follows.Firstly,a transformer is utilized to downsample the first-order proximities of the graph into a latent space,which can result in the structural properties and eventually assist in detecting the communities.Secondly,the fine-tuning task is conducted by tuning variant hyperparameters cautiously,which is applied to multiple social networks(Facebook and Twitch).Furthermore,the objective function(crossentropy)is tuned by L0 regularization.Lastly,the reconstructed model forms communities that present the relationship between the groups.The proposed robust model provides good generalization and is applicable to obtaining not only the community structures in social networks but also the node classification.The proposed graph-transformer shows advanced performance on the social networks with the average NMIs of 0.67±0.04,0.198±0.02,0.228±0.02,and 0.68±0.03 on Wikipedia crocodiles,Github Developers,Twitch England,and Facebook Page-Page networks,respectively.展开更多
The properties of generalized flip Markov chains on connected regular digraphs are discussed.The 1-Flipper operation on Markov chains for undirected graphs is generalized to that for multi-digraphs.The generalized 1-F...The properties of generalized flip Markov chains on connected regular digraphs are discussed.The 1-Flipper operation on Markov chains for undirected graphs is generalized to that for multi-digraphs.The generalized 1-Flipper operation preserves the regularity and weak connectivity of multi-digraphs.The generalized 1-Flipper operation is proved to be symmetric.Moreover,it is presented that a series of random generalized 1-Flipper operations eventually lead to a uniform probability distribution over all connected d-regular multi-digraphs without loops.展开更多
The enhanced definition of Mechatronics involves the four underlying characteristics of integrated,unified,unique,and systematic approaches.In this realm,Mechatronics is not limited to electro-mechanical systems,in th...The enhanced definition of Mechatronics involves the four underlying characteristics of integrated,unified,unique,and systematic approaches.In this realm,Mechatronics is not limited to electro-mechanical systems,in the multi-physics sense,but involves other physical domains such as fluid and thermal.This paper summarizes the mechatronic approach to modeling.Linear graphs facilitate the development of state-space models of mechatronic systems,through this approach.The use of linear graphs in mechatronic modeling is outlined and an illustrative example of sound system modeling is given.Both time-domain and frequency-domain approaches are presented for the use of linear graphs.A mechatronic model of a multi-physics system may be simplified by converting all the physical domains into an equivalent single-domain system that is entirely in the output domain of the system.This approach of converting(transforming)physical domains is presented.An illustrative example of a pressure-controlled hydraulic actuator system that operates a mechanical load is given.展开更多
Comorbidity,the co-occurrence of multiple medical conditions in a single patient,profoundly impacts disease management and outcomes.Understanding these complex interconnections is crucial,especially in contexts where ...Comorbidity,the co-occurrence of multiple medical conditions in a single patient,profoundly impacts disease management and outcomes.Understanding these complex interconnections is crucial,especially in contexts where comorbidities exacerbate outcomes.Leveraging insights from the human interactome and advancements in graph-based methodologies,this study introduces transformer with subgraph positional encoding(TSPE)for disease comorbidity prediction.Inspired by biologically supervised embedding,TSPE employs transformer's attention mechanisms and subgraph positional encoding(SPE)to capture interactions between nodes and disease associations.Our proposed SPE proves more effective than Laplacian positional encoding,as used in Dwivedi et al.'s graph transformer,underscoring the importance of integrating clustering and disease-specific information for improved predictive accuracy.Evaluated on real clinical benchmark datasets(RR0 and RR1),TSPE demonstrates substantial performance enhancements over the state-of-the-art method,achieving up to 28.24%higher ROC AUC(receiver operating characteristic-area under the curve)and 4.93%higher accuracy.This method shows promise for adaptation to other complex graph-based tasks and applications.The source code is available at GitHub website(xihan-qin/TSPE-GraphTransformer).展开更多
The ability to assess the reliability of safety-critical systems is one of the most crucial requirements in the design of modern safety-critical systems where even a minor failure can result in loss of life or irrepar...The ability to assess the reliability of safety-critical systems is one of the most crucial requirements in the design of modern safety-critical systems where even a minor failure can result in loss of life or irreparable damage to the environment.Model checking is an automatic technique that verifies or refutes system properties by exploring all reachable states(state space)of a model.In large and complex systems,it is probable that the state space explosion problem occurs.In exploring the state space of systems modeled by graph transformations,the rule applied on the current state specifies the rule that can perform on the next state.In other words,the allowed rule on the current state depends only on the applied rule on the previous state,not the ones on earlier states.This fact motivates us to use a Markov chain(MC)to capture this type of dependencies and applies the Estimation of Distribution Algorithm(EDA)to improve the quality of the MC.EDA is an evolutionary algorithm directing the search for the optimal solution by learning and sampling probabilistic models through the best individuals of a population at each generation.To show the effectiveness of the proposed approach,we implement it in GROOVE,an open source toolset for designing and model checking graph transformation systems.Experimental results confirm that the proposed approach has a high speed and accuracy in comparison with the existing meta-heuristic and evolutionary techniques in safety analysis of systems specified formally through graph transformations.展开更多
Transformations of Steiner tree problem variants have been frequently discussed in the literature. Besides allowing to easily transfer complexity results, they constitute a central pillar of exact state-of-the-art sol...Transformations of Steiner tree problem variants have been frequently discussed in the literature. Besides allowing to easily transfer complexity results, they constitute a central pillar of exact state-of-the-art solvers for well-known variants such as the Steiner tree problem in graphs. In this article transformations for both the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem to the Steiner arborescence problem are introduced for the first time. Furthermore, the considerable implications for practical solving approaches will be demonstrated, including the computation of strong upper and lower bounds.展开更多
In this paper, we study the long-time behavior of the solution of the initial boundary value problem of the coupled Kirchhoff equations. Based on the relevant assumptions, the equivalent norm on E<sub>k</sub&...In this paper, we study the long-time behavior of the solution of the initial boundary value problem of the coupled Kirchhoff equations. Based on the relevant assumptions, the equivalent norm on E<sub>k</sub> is obtained by using the Hadamard graph transformation method, and the Lipschitz constant l<sub>F</sub><sub> </sub>of F is further estimated. Finally, a family of inertial manifolds satisfying the spectral interval condition is obtained.展开更多
In this paper, we study the inertial manifolds for a class of asymmetrically coupled generalized Higher-order Kirchhoff equations. Under appropriate assumptions, we firstly exist Hadamard’s graph transformation metho...In this paper, we study the inertial manifolds for a class of asymmetrically coupled generalized Higher-order Kirchhoff equations. Under appropriate assumptions, we firstly exist Hadamard’s graph transformation method to structure a graph norm of a Lipschitz continuous function, then we prove the existence of a family of inertial manifolds by showing that the spectral gap condition is true.展开更多
In recent years,graph transformers have been demonstrated to be effective learning architectures for various graphbased learning tasks.However,their scalability on large-scale data is usually restricted due to the qua...In recent years,graph transformers have been demonstrated to be effective learning architectures for various graphbased learning tasks.However,their scalability on large-scale data is usually restricted due to the quadratic computational complexity of graph transformers when compared to graph convolutional network(GCN)models.To overcome this issue,in this work,we propose to learn an efficient linear graph transformer by employing graph attention distillation model.The proposed method provides a faster and lighter graph transformer framework for graph data learning tasks.The core of the proposed distillation model is to employ the kernel decomposition approach to rebuild the graph transformer architecture,thereby reducing the quadratic complexity to the linear complexity.Furthermore,to seamlessly transfer the rich learning capacity from the regular graph transformer of teacher branch to its linear student counterpart,we devise a novel graph-attention knowledge distillation strategy to enhance the capabilities of the student network.Empirical evaluations conducted on six commonly employed benchmark datasets validate our model′s superiority,as it consistently outperforms existing methods in terms of both effectiveness and efficiency.展开更多
Distinguishing genuine news from false information is crucial in today’s digital era.Most of the existing methods are based on either the traditional neural network sequence model or graph neural network model that h...Distinguishing genuine news from false information is crucial in today’s digital era.Most of the existing methods are based on either the traditional neural network sequence model or graph neural network model that has become more popularity in recent years.Among these two types of models,the latter solve the former’s problem of neglecting the correlation among news sentences.However,one layer of the graph neural network only considers the information of nodes directly connected to the current nodes and omits the important information carried by distant nodes.As such,this study proposes the Extendable-to-Global Heterogeneous Graph Attention network(namely EGHGAT)to manage heterogeneous graphs by cleverly extending local attention to global attention and addressing the drawback of local attention that can only collect information from directly connected nodes.The shortest distance matrix is computed among all nodes on the graph.Specifically,the shortest distance information is used to enable the current nodes to aggregate information from more distant nodes by considering the influence of different node types on the current nodes in the current network layer.This mechanism highlights the importance of directly or indirectly connected nodes and the effect of different node types on the current nodes,which can substantially enhance the performance of the model.Information from an external knowledge base is used to compare the contextual entity representation with the entity representation of the corresponding knowledge base to capture its consistency with news content.Experimental results from the benchmark dataset reveal that the proposed model significantly outperforms the state-of-the-art approach.Our code is publicly available at https://github.com/gyhhk/EGHGAT_FakeNewsDetection.展开更多
文摘Graph transformation systems have become a general formal modeling language to describe many models in software development process.Behavioral modeling of dynamic systems and model-to-model transformations are only a few examples in which graphs have been used to software development.But even the perfect graph transformation system must be equipped with automated analysis capabilities to let users understand whether such a formal specification fulfills their requirements.In this paper,we present a new solution to verify graph transformation systems using the Bogor model checker.The attributed graph grammars(AGG)-like graph transformation systems are translated to Bandera intermediate representation(BIR),the input language of Bogor,and Bogor verifies the model against some interesting properties defined by combining linear temporal logic(LTL) and special-purpose graph rules.Experimental results are encouraging,showing that in most cases our solution improves existing approaches in terms of both performance and expressiveness.
基金Project supported by the National Natural Science Foundation of China!(19771075)
文摘The basis graph \%G\% for a linear programming consists of all bases under pivot transformations. A degenerate optimal basis graph G * is a subgraph of \%G\% induced by all optimal bases at a degenerate optimal vertex x 0. In this paper, several conditions for the characterization of G * are presented.
文摘Circuits with switched current are described by an admittance matrix and seeking current transfers then means calculating the ratio of algebraic supplements of this matrix. As there are also graph methods of circuit analysis in addition to algebraic methods, it is clearly possible in theory to carry out an analysis of the whole switched circuit in two-phase switching exclusively by the graph method as well. For this purpose it is possible to plot a Mason graph of a circuit, use transformation graphs to reduce Mason graphs for all the four phases of switching, and then plot a summary graph from the transformed graphs obtained this way. First the author draws nodes and possible branches, obtained by transformation graphs for transfers of EE （even-even） and OO （odd-odd） phases. In the next step, branches obtained by transformation graphs for EO and OE phase are drawn between these nodes, while their resulting transfer is 1 multiplied by z^1/2. This summary graph is extended by two branches from input node and to output node, the extended graph can then be interpreted by the Mason＇s relation to provide transparent current transfers. Therefore it is not necessary to compose a sum admittance matrix and to express this consequently in numbers, and so it is possible to reach the final result in a graphical way.
基金The research is funded by the Researchers Supporting Project at King Saud University(Project#RSP-2021/305).
文摘Graphs are used in various disciplines such as telecommunication,biological networks,as well as social networks.In large-scale networks,it is challenging to detect the communities by learning the distinct properties of the graph.As deep learning hasmade contributions in a variety of domains,we try to use deep learning techniques to mine the knowledge from large-scale graph networks.In this paper,we aim to provide a strategy for detecting communities using deep autoencoders and obtain generic neural attention to graphs.The advantages of neural attention are widely seen in the field of NLP and computer vision,which has low computational complexity for large-scale graphs.The contributions of the paper are summarized as follows.Firstly,a transformer is utilized to downsample the first-order proximities of the graph into a latent space,which can result in the structural properties and eventually assist in detecting the communities.Secondly,the fine-tuning task is conducted by tuning variant hyperparameters cautiously,which is applied to multiple social networks(Facebook and Twitch).Furthermore,the objective function(crossentropy)is tuned by L0 regularization.Lastly,the reconstructed model forms communities that present the relationship between the groups.The proposed robust model provides good generalization and is applicable to obtaining not only the community structures in social networks but also the node classification.The proposed graph-transformer shows advanced performance on the social networks with the average NMIs of 0.67±0.04,0.198±0.02,0.228±0.02,and 0.68±0.03 on Wikipedia crocodiles,Github Developers,Twitch England,and Facebook Page-Page networks,respectively.
基金National Natural Science Foundation of China(No.11671258)。
文摘The properties of generalized flip Markov chains on connected regular digraphs are discussed.The 1-Flipper operation on Markov chains for undirected graphs is generalized to that for multi-digraphs.The generalized 1-Flipper operation preserves the regularity and weak connectivity of multi-digraphs.The generalized 1-Flipper operation is proved to be symmetric.Moreover,it is presented that a series of random generalized 1-Flipper operations eventually lead to a uniform probability distribution over all connected d-regular multi-digraphs without loops.
基金supported by research grants from the Natural Sciences and Engineering Research Council(NSERC)of Canada
文摘The enhanced definition of Mechatronics involves the four underlying characteristics of integrated,unified,unique,and systematic approaches.In this realm,Mechatronics is not limited to electro-mechanical systems,in the multi-physics sense,but involves other physical domains such as fluid and thermal.This paper summarizes the mechatronic approach to modeling.Linear graphs facilitate the development of state-space models of mechatronic systems,through this approach.The use of linear graphs in mechatronic modeling is outlined and an illustrative example of sound system modeling is given.Both time-domain and frequency-domain approaches are presented for the use of linear graphs.A mechatronic model of a multi-physics system may be simplified by converting all the physical domains into an equivalent single-domain system that is entirely in the output domain of the system.This approach of converting(transforming)physical domains is presented.An illustrative example of a pressure-controlled hydraulic actuator system that operates a mechanical load is given.
文摘Comorbidity,the co-occurrence of multiple medical conditions in a single patient,profoundly impacts disease management and outcomes.Understanding these complex interconnections is crucial,especially in contexts where comorbidities exacerbate outcomes.Leveraging insights from the human interactome and advancements in graph-based methodologies,this study introduces transformer with subgraph positional encoding(TSPE)for disease comorbidity prediction.Inspired by biologically supervised embedding,TSPE employs transformer's attention mechanisms and subgraph positional encoding(SPE)to capture interactions between nodes and disease associations.Our proposed SPE proves more effective than Laplacian positional encoding,as used in Dwivedi et al.'s graph transformer,underscoring the importance of integrating clustering and disease-specific information for improved predictive accuracy.Evaluated on real clinical benchmark datasets(RR0 and RR1),TSPE demonstrates substantial performance enhancements over the state-of-the-art method,achieving up to 28.24%higher ROC AUC(receiver operating characteristic-area under the curve)and 4.93%higher accuracy.This method shows promise for adaptation to other complex graph-based tasks and applications.The source code is available at GitHub website(xihan-qin/TSPE-GraphTransformer).
文摘The ability to assess the reliability of safety-critical systems is one of the most crucial requirements in the design of modern safety-critical systems where even a minor failure can result in loss of life or irreparable damage to the environment.Model checking is an automatic technique that verifies or refutes system properties by exploring all reachable states(state space)of a model.In large and complex systems,it is probable that the state space explosion problem occurs.In exploring the state space of systems modeled by graph transformations,the rule applied on the current state specifies the rule that can perform on the next state.In other words,the allowed rule on the current state depends only on the applied rule on the previous state,not the ones on earlier states.This fact motivates us to use a Markov chain(MC)to capture this type of dependencies and applies the Estimation of Distribution Algorithm(EDA)to improve the quality of the MC.EDA is an evolutionary algorithm directing the search for the optimal solution by learning and sampling probabilistic models through the best individuals of a population at each generation.To show the effectiveness of the proposed approach,we implement it in GROOVE,an open source toolset for designing and model checking graph transformation systems.Experimental results confirm that the proposed approach has a high speed and accuracy in comparison with the existing meta-heuristic and evolutionary techniques in safety analysis of systems specified formally through graph transformations.
文摘Transformations of Steiner tree problem variants have been frequently discussed in the literature. Besides allowing to easily transfer complexity results, they constitute a central pillar of exact state-of-the-art solvers for well-known variants such as the Steiner tree problem in graphs. In this article transformations for both the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem to the Steiner arborescence problem are introduced for the first time. Furthermore, the considerable implications for practical solving approaches will be demonstrated, including the computation of strong upper and lower bounds.
文摘In this paper, we study the long-time behavior of the solution of the initial boundary value problem of the coupled Kirchhoff equations. Based on the relevant assumptions, the equivalent norm on E<sub>k</sub> is obtained by using the Hadamard graph transformation method, and the Lipschitz constant l<sub>F</sub><sub> </sub>of F is further estimated. Finally, a family of inertial manifolds satisfying the spectral interval condition is obtained.
文摘In this paper, we study the inertial manifolds for a class of asymmetrically coupled generalized Higher-order Kirchhoff equations. Under appropriate assumptions, we firstly exist Hadamard’s graph transformation method to structure a graph norm of a Lipschitz continuous function, then we prove the existence of a family of inertial manifolds by showing that the spectral gap condition is true.
基金supported by National Natural Science Foundation of China(No.62076004)Anhui Provincial Key Research and Development Program,China(No.2022i01020014).
文摘In recent years,graph transformers have been demonstrated to be effective learning architectures for various graphbased learning tasks.However,their scalability on large-scale data is usually restricted due to the quadratic computational complexity of graph transformers when compared to graph convolutional network(GCN)models.To overcome this issue,in this work,we propose to learn an efficient linear graph transformer by employing graph attention distillation model.The proposed method provides a faster and lighter graph transformer framework for graph data learning tasks.The core of the proposed distillation model is to employ the kernel decomposition approach to rebuild the graph transformer architecture,thereby reducing the quadratic complexity to the linear complexity.Furthermore,to seamlessly transfer the rich learning capacity from the regular graph transformer of teacher branch to its linear student counterpart,we devise a novel graph-attention knowledge distillation strategy to enhance the capabilities of the student network.Empirical evaluations conducted on six commonly employed benchmark datasets validate our model′s superiority,as it consistently outperforms existing methods in terms of both effectiveness and efficiency.
基金supported by the National Natural Science Foundation of Xinjiang Province(Nos.2022TSYCTD0019 and 2022D01D32).
文摘Distinguishing genuine news from false information is crucial in today’s digital era.Most of the existing methods are based on either the traditional neural network sequence model or graph neural network model that has become more popularity in recent years.Among these two types of models,the latter solve the former’s problem of neglecting the correlation among news sentences.However,one layer of the graph neural network only considers the information of nodes directly connected to the current nodes and omits the important information carried by distant nodes.As such,this study proposes the Extendable-to-Global Heterogeneous Graph Attention network(namely EGHGAT)to manage heterogeneous graphs by cleverly extending local attention to global attention and addressing the drawback of local attention that can only collect information from directly connected nodes.The shortest distance matrix is computed among all nodes on the graph.Specifically,the shortest distance information is used to enable the current nodes to aggregate information from more distant nodes by considering the influence of different node types on the current nodes in the current network layer.This mechanism highlights the importance of directly or indirectly connected nodes and the effect of different node types on the current nodes,which can substantially enhance the performance of the model.Information from an external knowledge base is used to compare the contextual entity representation with the entity representation of the corresponding knowledge base to capture its consistency with news content.Experimental results from the benchmark dataset reveal that the proposed model significantly outperforms the state-of-the-art approach.Our code is publicly available at https://github.com/gyhhk/EGHGAT_FakeNewsDetection.
