Graph Transformers研究进展综述

随着图结构数据在各种实际场景中的广泛应用,对其进行有效建模和处理的需求日益增加。Graph Transformers(GTs)作为一类使用Transformers处理图数据的模型,能够有效缓解传统图神经网络(GNN)中存在的过平滑和过挤压等问题,因此可以学习到更好的特征表示。根据对近年来GTs相关文献的研究,将现有的模型架构分为两类:第一类通过绝对编码和相对编码向Transformers中加入图的位置和结构信息,以增强Transformers对图结构数据的理解和处理能力;第二类根据不同的方式(串行、交替、并行)将GNN与Transformers进行结合,以充分利用两者的优势。介绍了GTs在信息安全、药物发现和知识图谱等领域的应用,对比总结了不同用途的模型及其优缺点。最后,从可扩展性、复杂图、更好的结合方式等方面分析了GTs未来研究面临的挑战。

基于Graph Transformer的半监督异配图表示学习模型

现有的图卷积网络(GCN)模型基于同配性假设,无法直接应用于异配图的表示学习,且许多异配图表示学习的研究工作受消息传递机制的限制,导致节点特征混淆和特征过度挤压而出现过平滑问题。针对这些问题,提出一种基于Graph Transformer的半监督异配图表示学习模型HPGT(HeteroPhilic Graph Transformer)。首先,使用度连接概率矩阵采样节点的路径邻域,再通过自注意力机制自适应地聚合路径上的节点异配连接模式,编码得到节点的结构信息,用节点的原始属性信息和结构信息构建Transformer层的自注意力模块;其次,将每个节点自身的隐层表示与它的邻域节点的隐层表示分离更新以避免节点通过自注意力模块聚合过量的自身信息,再把每个节点表示与它的邻域表示连接,得到单个Transformer层的输出,另外,将所有的Transformer层的输出跳连到最终的节点隐层表示以防止中间层信息丢失;最后,使用线性层和Softmax层将节点的隐层表示映射到节点的预测标签。实验结果表明,与无结构编码(SE)的模型相比,基于度连接概率的SE能为Transformer层的自注意力模块提供有效的偏差信息,HPGT平均准确率提升0.99%~11.98%;与对比模型相比,在异配数据集(Texas、Cornell、Wisconsin和Actor)上,模型节点分类准确率提升0.21%~1.69%,在同配数据集(Cora、CiteSeer和PubMed)上,节点分类准确率分别达到了0.8379、0.7467和0.8862。以上结果验证了HPGT具有较强的异配图表示学习能力,尤其适用于强异配图节点分类任务。

Markov Chains Based on Random Generalized 1-Flipper Operations for Connected Regular Multi-digraphs

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.

Full Graph Methods of Switched Current Circuit Solution

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.

DEGENERATE OPTIMAL BASIS GRAPHS IN LINEAR PROGRAMMING

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.

Graph Transformer for Communities Detection in Social Networks

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.

Mechatronic Modeling and Domain Transformation of Multi-physics Systems

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.

Knowledge Graph Enhanced Transformers for Diagnosis Generation of Chinese Medicine

Chinese medicine(CM)diagnosis intellectualization is one of the hotspots in the research of CM modernization.The traditional CM intelligent diagnosis models transform the CM diagnosis issues into classification issues,however,it is difficult to solve the problems such as excessive or similar categories.With the development of natural language processing techniques,text generation technique has become increasingly mature.In this study,we aimed to establish the CM diagnosis generation model by transforming the CM diagnosis issues into text generation issues.The semantic context characteristic learning capacity was enhanced referring to Bidirectional Long Short-Term Memory(BILSTM)with Transformer as the backbone network.Meanwhile,the CM diagnosis generation model Knowledge Graph Enhanced Transformer(KGET)was established by introducing the knowledge in medical field to enhance the inferential capability.The KGET model was established based on 566 CM case texts,and was compared with the classic text generation models including Long Short-Term Memory sequence-to-sequence(LSTM-seq2seq),Bidirectional and Auto-Regression Transformer(BART),and Chinese Pre-trained Unbalanced Transformer(CPT),so as to analyze the model manifestations.Finally,the ablation experiments were performed to explore the influence of the optimized part on the KGET model.The results of Bilingual Evaluation Understudy(BLEU),Recall-Oriented Understudy for Gisting Evaluation 1(ROUGE1),ROUGE2 and Edit distance of KGET model were 45.85,73.93,54.59 and 7.12,respectively in this study.Compared with LSTM-seq2seq,BART and CPT models,the KGET model was higher in BLEU,ROUGE1 and ROUGE2 by 6.00–17.09,1.65–9.39 and 0.51–17.62,respectively,and lower in Edit distance by 0.47–3.21.The ablation experiment results revealed that introduction of BILSTM model and prior knowledge could significantly increase the model performance.Additionally,the manual assessment indicated that the CM diagnosis results of the KGET model used in this study were highly consistent with the practical diagnosis results.In conclusion,text generation technology can be effectively applied to CM diagnostic modeling.It can effectively avoid the problem of poor diagnostic performance caused by excessive and similar categories in traditional CM diagnostic classification models.CM diagnostic text generation technology has broad application prospects in the future.

Graph-Segmenter:graph transformer with boundary-aware attention for semantic segmentation

Thetransformer-based semantic segmentation approaches,which divide the image into different regions by sliding windows and model the relation inside each window,have achieved outstanding success.However,since the relation modeling between windows was not the primary emphasis of previous work,it was not fully utilized.To address this issue,we propose a Graph-Segmenter,including a graph transformer and a boundary-aware attention module,which is an effective network for simultaneously modeling the more profound relation between windows in a global view and various pixels inside each window as a local one,and for substantial low-cost boundary adjustment.Specifically,we treat every window and pixel inside the window as nodes to construct graphs for both views and devise the graph transformer.The introduced boundary-awareattentionmoduleoptimizes theedge information of the target objects by modeling the relationship between the pixel on the object's edge.Extensive experiments on three widely used semantic segmentation datasets(Cityscapes,ADE-20k and PASCAL Context)demonstrate that our proposed network,a Graph Transformer with Boundary-aware Attention,can achieve state-of-the-art segmentation performance.

Towards automated software model checking using graph transformation systems and Bogor

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.

Using Markov Chain Based Estimation of Distribution Algorithm for Model-Based Safety Analysis of Graph Transformation

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 FOR THE PRIZE-COLLECTING STEINER TREE PROBLEM AND THE MAXIMUM-WEIGHT CONNECTED SUBGRAPH PROBLEM TO SAP

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.

A Family of Inertial Manifolds of Coupled Kirchhoff Equations

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 Ek is obtained by using the Hadamard graph transformation method, and the Lipschitz constant lF of F is further estimated. Finally, a family of inertial manifolds satisfying the spectral interval condition is obtained.

A Family of Inertial Manifolds for a Class of Asymmetrically Coupled Generalized Higher-Order Kirchhoff Equations

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.

Test-driven verification/validation of model transformations

Why is it important to verify/validate model transformations？ The motivation is to improve the quality of the trans- formations, and therefore the quality of the generated software artifacts. Verified/validated model transformations make it possible to ensure certain properties of the generated software artifacts. In this way, verification/validation methods can guarantee different requirements stated by the actual domain against the generated/modified/optimized software products. For example, a verified/ validated model transformation can ensure the preservation of certain properties during the model-to-model transformation. This paper emphasizes the necessity of methods that make model transformation verified/validated, discusses the different scenarios of model transformation verification and validation, and introduces the principles of a novel test-driven method for verifying/ validating model transformations. We provide a solution that makes it possible to automatically generate test input models for model transformations. Furthermore, we collect and discuss the actual open issues in the field of verification/validation of model transformations.

THE PERIODIC CAPACITATED ARC ROUTING PROBLEM LINEAR PROGRAMMING MODEL, METAHEURISTIC AND LOWER BOUNDS

The Periodic Capacitated Arc Routing Problem (PCARP) generalizes the well known NP-hard Capacitated Arc Routing Problem (CARP) by extending the single period to multi-period horizon. The Capacitated Arc Routing Problem (CARP) is defined on an undirected network in which a fleet of identical vehicles is based at a depot node. A subset of edges, called tasks, must be serviced by a vehicle. The CARP consists of determining a set of feasible vehicle trips that minimizes the total cost of traversed edges. The PCARP involves the assignment of tasks to periods and the determination of vehicles trips in each period, to minimize the total cost on the whole horizon. This new problem arises in various real life applications such as waste collection, mail delivery, etc. In this paper, a new linear programming model and preliminary lower bounds based on graph transformation are proposed. A meta-heuristic approach - Scatter Search (SS) is developed for the PCARP and evaluated on a large variety of instances.