A new algorithm for error-tolerant subgraph isomorphism detection

We propose a new algorithm for error-correcting subgraph isomorphism detection from a set of model graphs to an unknown input graph. The algorithm is based on a compact representation of the model graphs. This representation is derived from the set of model graphs in an off-line preprocessing step. The main advantage of the proposed representation is that common subgraphs of different model graphs are represented only once. Therefore, at run time, given an unknown input graph, the computational effort of matching the common subgraphs for each model graph onto the input graph is done only once. Consequently, the new algorithm is only sublinearly dependent on the number of model graphs. Furthermore, the new algorithm can be combined with a future cost estimation method that greatly improves its run-time performance     

Multi-view Contrastive Enhanced Heterogeneous Graph Structure Learning

As a learning method of heterogeneous graph representation, heterogeneous graph neural networks can effectively extract complex structural and semantic information from heterogeneous graphs, and perform excellently in node classification and link prediction tasks to provide strong support for the representation and analysis of knowledge graphs. Due to the existence of some noisy interactions or missing interactions in the heterogeneous graphs, the heterogeneous graph neural network incorporates erroneous neighbor features, thus affecting the overall performance of the model. To solve the above problems, in this paper we proposes a heterogeneous graph structure learning model enhanced by multi-view contrast. Firstly, the semantic information in the heterogeneous graph is maintained by the meta-path, and the similarity graph is generated by calculating the feature similarity among the nodes under each meta-path, which is fused with the meta-path graph to optimize the graph structure. By contrasting the similarity graph and meta-path graph as multiple views, the graph structure is optimized without supervision information, and the dependence on supervision signals is eliminated. Finally, for addressing the problem that the learning ability of the neural network model is insufficient at the initial training stage and there are often erroneous interactions in the generated graph structure, we design a progressive graph structure fusion method. Through incremental weighted addition of meta-path graphs and similarity graphs, the weight of similarity graphs in the fusion is changed. This not only prevents erroneous interactions from being introduced in the initial training stage but also achieves the purpose of employing the interactions in similarity graphs to suppress interference interactions or complete missing interactions, which leads to the optimized heterogeneous structure. Meanwhile, node classification and node clustering are selected as the verification tasks of graph structure learning. The experimental results on four real heterogeneous graph datasets prove that the proposed learning method is feasible and effective. Compared with the optimal comparison model, the performance of this model has been significantly improved under both tasks.     

On the structure of graphs in the Caucal hierarchy

We investigate the structure of graphs in the Caucal hierarchy. We provide criteria concerning the degree of vertices or the length of paths which can be used to show that a given graph does not belong to a certain level of this hierarchy. Each graph in the Caucal hierarchy corresponds to the configuration graph of some higher-order pushdown automaton. The main part of the paper consists of a study of such configuration graphs. We provide tools to decompose and reassemble their runs, and we prove a pumping lemma for higher-order pushdown automata.     

Structure-Preserving Hierarchical Decompositions

A hierarchy tree of a graph G is a rooted tree whose leaves are the vertices of G; the internal nodes are usually called clusters. Hierarchy trees are well suited for representing hierarchical decompositions of graphs. In this paper we introduce the notion of P-validity of hierarchy trees with respect to a given graph property P. This notion reflects the similarity between any high-level representation of G obtained from the hierarchy tree and the topological structure of G. Maintaining the properties of a graph at any level of abstraction is especially relevant in graph drawing applications. We present a structural characterization of P-valid hierarchy trees when the clustered graph is a tree and property P is the acyclicity. Besides being interesting in its own right, our structure theorem can be used in the design of a polynomial time algorithm for recognizing P-valid hierarchy trees.     

Term Graphs for Computing Derivatives in Imperative Languages

Automatic differentiation is a technique for the rule-based transformation of a subprogram that computes some mathematical function into a subprogram that computes the derivatives of that function. Automatic differentiation algorithms are typically expressed as operating on a weighted term graph called a linearized computational graph. Constructing this weighted term graph for imperative programming languages such as C/C++ and Fortran introduces several challenges. Alias and definition-use information is needed to construct term graphs for individual statements and then combine them into one graph for a collection of statements. Furthermore, the resulting weighted term graph must be represented in a language-independent fashion to enable the use of AD algorithms in tools for various languages. We describe the construction and representation of weighted term graphs for C/C++ and Fortran, as implemented in the ADIC 2.0 and OpenAD/F tools for automatic differentiation.     

多视图对比增强的异质图结构学习方法

异质图神经网络作为一种异质图表示学习的方法,可以有效地抽取异质图中的复杂结构与语义信息,在节点分类和连接预测任务上取得了优异的表现,为知识图谱的表示与分析提供了有力的支撑.现有的异质图由于存在一定的噪声交互或缺失部分交互,导致异质图神经网络在节点聚合、更新时融入错误的邻域特征信息,从而影响模型的整体性能.为解决该问题,提出了多视图对比增强的异质图结构学习模型.该模型首先利用元路径保持异质图中的语义信息,并通过计算每条元路径下节点之间特征相似度生成相似度图,将其与元路径图融合,实现对图结构的优化.通过将相似度图与元路径图作为不同视图进行多视图对比,实现无监督信息的情况下优化图结构,摆脱对监督信号的依赖.最后,为解决神经网络模型在训练初期学习能力不足、生成的图结构中往往存在错误交互的问题,设计了一个渐进式的图结构融合方法.通过将元路径图和相似度图递增地加权相加,改变图结构融合过程中相似度图所占的比例,在抑制了因模型学习能力弱引入过多的错误交互的同时,达到了用相似度图中的交互抑制原有干扰交互或补全缺失交互的目的,实现了对异质图结构的优化.选择节点分类与节点聚类作为图结构学习的验证任务,在4种...     

A new document representation using term frequency and vectorized graph connectionists with application to document retrieval

This paper presents a new document representation with vectorized multiple features including term frequency and term-connection-frequency. A document is represented by undirected and directed graph, respectively. Then terms and vectorized graph connectionists are extracted from the graphs by employing several feature extraction methods. This hybrid document feature representation more accurately reflects the underlying semantics that are difficult to achieve from the currently used term histograms, and it facilitates the matching of complex graph. In application level, we develop a document retrieval system based on self-organizing map (SOM) to speed up the retrieval process. We perform extensive experimental verification, and the results suggest that the proposed method is computationally efficient and accurate for document retrieval.     

Cerebral: visualizing multiple experimental conditions on a graph with biological context

Systems biologists use interaction graphs to model the behavior of biological systems at the molecular level. In an iterative process, such biologists obser ve the reactions of living cells under various experimental conditions, view the results in the context of the interaction graph, and then propose changes to the graph model. These graphs ser ve as a form of dynamic knowledge representation of the biological system being studied and evolve as new insight is gained from the experimental data. While numerous graph layout and drawing packages are available, these tools did not fully meet the needs of our immunologist collaborators. In this paper, we describe the data information display needs of these immunologists and translate them into design decisions. These decisions led us to create Cerebral, a system that uses a biologically guided graph layout and incor porates experimental data directly into the graph display. Small multiple views of different experimental conditions and a data-driven parallel coordinates view enable correlations between experimental conditions to be analyzed at the same time that the data is viewed in the graph context. This combination of coordinated views allows the biologist to view the data from many different perspectives simultaneously. To illustrate the typical analysis tasks performed, we analyze two datasets using Cerebral. Based on feedback from our collaboratorsweconcludethat Cerebral is a valuable tool for analyzing experimental data in the context of an interaction graph model.      

Supervision of an industrial steam generator. Part I: Bond graph modelling

Model based supervision of most process engineering plants is difficult due to the complexities arising out of the energetic couplings in the model. Bond graph modelling is a suitable tool to represent the model structures of such processes along with their control system instrumentation. In this paper, bond graph model of a steam generator installation consisting of complex industrial components such as a boiler, a condenser, etc. is developed and validated through experimental observations. It is further shown that the causal properties of bond graphs not only allow validating the model, but they also provide the computational algorithms to eliminate the unknown variables from coupled thermo-fluid models and thus generate analytical redundancy relations (ARR) in terms of measurements and parameters. Structural analysis of the model is used to obtain the fault signatures and also to identify the hardware redundancies in the sensor placement. Thereafter, quantitative evaluations of ARR are used to yield residuals, which are subsequently implemented in an online integrated supervision system described in the sequel to this paper. The fault tolerant control and reconfiguration strategies implemented in that supervision platform are based on the available hardware redundancies in the process, which have been deduced directly from bond graph model using the methodology presented in this paper.     

Efficient subgraph isomorphism detection: a decomposition approach

Graphs are a powerful and universal data structure useful in various subfields of science and engineering. In this paper, we propose a new algorithm for subgraph isomorphism detection from a set of a priori known model graphs to an input graph that is given online. The new approach is based on a compact representation of the model graphs that is computed offline. Subgraphs that appear more than once within the same or within different model graphs are represented only once, thus reducing the computational effort to detect them in an input graph. In the extreme case where all model graphs are highly similar, the run-time of the new algorithm becomes independent of the number of model graphs. Both a theoretical complexity analysis and practical experiments characterizing the performance of the new approach are given     

Defining the semantics of extended genetic graphs

In the present work, the semantics of the Extended Genetic Graph (EGG) is defined in order to eliminate limitations inherent in these graphs in the modelling of an ideal Student Model. The semantics of extended genetic graphs can be defined at two representational levels: conceptual and transactional. First, the student's knowledge as represented by EGG nodes is specified explicitly at the conceptual level using the conceptual graphs (CGs) as a representation. Secondly, the criteria for the definition and use of learning processes such asanalogy, generalization, refinement, component, anddeviation/correction are specified at the transactional level. These criteria are then associated with the conditions of existence of different EGG links as they are implicitly assumed in the semantics of these graphs. Once the conditions of their creation are known, the semantics of EGG links can be represented explicitly by the use of CGs and Predicate Transition Networks (PrTNs). These representations are then used for detecting different types of EGG links.Conceptual graphs combined with PrTNs are able to describe the semantic structures equivalent to those contained implicitly in EGGs. However, the semantics of the combined graph which is based on the results of cognitive psychology, natural language processing, as well as logic, are richer than the semantics of the EGG. Furthermore, the operations provided by the conceptual graph theory combined with the constraint specifications as expressed by PrTNs allow the modification of the learner graph. Thus, our proposed representational framework provides the basis for the construction of a deep dynamical student model. An example from the Boolean Algebra domain demonstrates its feasibility.     

基于图信息的自监督多视角子空间聚类

多视角子空间聚类方法通常用于处理高维度、复杂结构的数据.现有的大多数多视角子空间聚类方法通过挖掘潜在图信息进行数据分析与处理,但缺乏对潜在子空间表示的监督过程.针对这一问题,本文提出一种新的多视角子空间聚类方法,即基于图信息的自监督多视角子空间聚类(SMSC).它将谱聚类与子空间表示相结合形成统一的深度学习框架.SMS...     

Polyhedral object recognition by indexing

In computer vision, the indexing problem is the problem of recognizing a few objects in a large database of objects while avoiding the help of the classical image-feature-to-object-feature matching paradigm. In this paper we address the problem of recognizing three-dimensional (3-D) polyhedral objects from 2-D images by indexing. Both the objects to be recognized and the images are represented by weighted graphs. The indexing problem is therefore the problem of determining whether a graph extracted from the image is present or absent in a database of model graphs. We introduce a novel method for performing this graph indexing process which is based both on polynomial characterization of binary and weighted graphs and on hashing. We describe in detail this polynomial characterization and then we show how it can be used in the context of polyhedral object recognition. Next we describe a practical recognition-by-indexing system that includes the organization of the database, the representation of polyhedral objects in terms of 2-D characteristic views, the representation of this views in terms of weighted graphs and the associated image processing. Finally, some experimental results allow the evaluation of the system performance.     

Distant context aware text generation from abstract meaning representation

Text generation from abstract meaning representation is a fundamental task in natural language generation. An interesting challenge is that distant context could influence the surface realization for each node. In the previous encoder-decoder based approaches, graph neural networks have been commonly used to encode abstract meaning representation graphs and exhibited superior performance over the sequence and tree encoders. However, most of them cannot stack numerous layers, thus being too shallow to capture distant context. In this paper, we propose solutions from three aspects. Firstly, we introduce a Transformer based graph encoder to embed abstract meaning representation graphs. This encoder can stack more layers to encode larger context, while without performance degrading. Secondly, we expand the receptive field of each node, i.e. building direct connections between node pairs, to capture the information of its distant neighbors. We also exploit relative position embedding to make the model aware of the original hierarchy of graphs. Thirdly, we encode the linearized version of abstract meaning representation with the pre-trained language model to get the sequence encoding and incorporate it into graph encoding to enrich features. We conduct experiments on LDC2015E86 and LDC2017T10. Experimental results demonstrate that our method outperforms previous strong baselines. Especially, we investigate the performance of our model on large graphs, finding a larger performance gain. Our best model achieves 31.99 of BLEU and 37.02 of METEOR on LDC2015E86, 34.21 of BLEU, and 39.26 of METEOR on LDC2017T10, which are new states of the art.

     

Querying multimedia presentations based on content

Considers the problem of querying multimedia presentations based on content information. Multimedia presentations are modeled as presentation graphs, which are directed acyclic graphs that visually specify the presentations. We present a graph data model for the specification of multimedia presentations and discuss query languages as effective tools to query and manipulate multimedia presentation graphs with respect to content information. To query the information flow throughout a multimedia presentation, as well as in each individual multimedia stream, we use revised versions of temporal operators Next, Connected and Until, together with path formulas. These constructs allow us to specify and query paths along a presentation graph. We present an icon-based graphical query language, GVISUAL, that provides iconic representations for these constructs and a user-friendly graphical interface for query specification. We also present an OQL-like language, GOQL (Graph OQL), with similar constructs, that allows textual and more traditional specifications of graph queries. Finally, we introduce GCalculus (Graph Calculus), a calculus-based language that establishes the formal grounds for the use of temporal operators in path formulas and for querying presentation graphs with respect to content information. We also discuss GCalculus/S (GCalculus with Sets) which avoids highly complex query expressions by eliminating the universal path quantifier, the negation operator and the universal quantifier. GCalculus/S represents the formal basis for GVISUAL, i.e. GVISUAL uses the constructs of GCalculus/S directly     

Future Event Prediction Based on Temporal Knowledge Graph Embedding

Accurate prediction of future events brings great benefits and reduces losses for society in many domains, such as civil unrest, pandemics, and crimes. Knowledge graph is a general language for describing and modeling complex systems. Different types of events continually occur, which are often related to historical and concurrent events. In this paper, we formalize the future event prediction as a temporal knowledge graph reasoning problem. Most existing studies either conduct reasoning on static knowledge graphs or assume knowledges graphs of all timestamps are available during the training process. As a result, they cannot effectively reason over temporal knowledge graphs and predict events happening in the future. To address this problem, some recent works learn to infer future events based on historical event-based temporal knowledge graphs. However, these methods do not comprehensively consider the latent patterns and influences behind historical events and concurrent events simultaneously. This paper proposes a new graph representation learning model, namely Recurrent Event Graph ATtention Network (RE-GAT), based on a novel historical and concurrent events attention-aware mechanism by modeling the event knowledge graph sequence recurrently. More specifically, our RE-GAT uses an attention-based historical events embedding module to encode past events, and employs an attention-based concurrent events embedding module to model the associations of events at the same timestamp. A translation-based decoder module and a learning objective are developed to optimize the embeddings of entities and relations. We evaluate our proposed method on four benchmark datasets. Extensive experimental results demonstrate the superiority of our RE-GAT model comparing to various baselines, which proves that our method can more accurately predict what events are going to happen.     

图网络层级信息挖掘分类算法综述

深度学习作为人工智能的一个研究分支发展迅速,而研究数据主要是语音、图像和视频等,这些具有规则结构的数据通常在欧氏空间中表示。然而许多学习任务需要处理的数据是从非欧氏空间中生成,这些数据特征和其关系结构可以用图来定义。图卷积神经网络通过将卷积定理应用于图,完成节点之间的信息传播与聚合,成为建模图数据一种有效的方法。尽管图卷积神经网络取得了巨大成功,但针对图任务中的节点分类问题,由于深层图结构优化的特有难点——过平滑现象,现有的多数模型都只有两三层的浅层模型架构。在理论上,图卷积神经网络的深层结构可以获得更多节点表征信息,因此针对其层级信息进行研究,将层级结构算法迁移到图数据分析的核心在于图层级卷积算子构建和图层级间信息融合。本文对图网络层级信息挖掘算法进行综述,介绍图神经网络的发展背景、存在问题以及图卷积神经网络层级结构算法的发展,根据不同图卷积层级信息处理将现有算法分为正则化方法和架构调整方法。正则化方法通过重新构建图卷积算子更好地聚合邻域信息,而架构调整方法则融合层级信息丰富节点表征。图卷积神经网络层级特性实验表明,图结构中存在层级特性节点,现有图层级信息挖掘算法仍未对层级特性节点的...     

Learning communicative actions of conflicting human agents

One of the main problems to be solved while assisting inter-human conflict resolution is how to reuse the previous experience with similar agents. A machine learning technique for handling scenarios of interaction between conflicting human agents is proposed. Scenarios are represented by directed graphs with labelled vertices (for communicative actions) and arcs (for temporal and causal relationships between these actions and their parameters). For illustrative purposes, classification of a scenario is computed by comparing partial matching of its graph with graphs of positive and negative examples. Nearest Neighbour learning is followed by the JSM-based learning which minimised the number of false negatives and takes advantage of a more accurate way of matching sequences of communicative actions. Developed scenario representation and comparative analysis techniques are applied to the classification of textual customer complaints. It is shown that analysing the structure of communicative actions without context information is frequently sufficient to estimate complaint validity. Therefore, being domain-independent, proposed machine learning technique is a good compliment to a wide range of customer relation management applications where formal treatment of inter-human interactions is required in a decision-support mode.     

融合概念和属性信息的领域知识图谱补全方法

针对领域知识图谱具有严格的模式层和丰富的属性信息的特点,提出一种融合概念和属性信息的领域知识图谱补全方法.首先对领域知识图谱模式层中的概念使用可建模语义分层结构的HAKE模型进行嵌入表示,建立基于概念的实例向量表示;其次对数据层的实例三元组和属性三元组进行区分,通过注意力机制对实例的属性和概念进行融合,建立基于属性的实例向量表示;最后对基于概念和基于属性的实例向量表示进行联合训练以实现对实例三元组的评分.使用基于DWY100K数据集构建的知识图谱、MED-BBK-9K 医疗知识图谱和根据某钢铁企业设备故障诊断数据构建的知识图谱进行实验,结果表明所提出方法在领域知识图谱补全中的性能优于现有知识图谱补全方法.