Orderly algorithms for graph generation

The existence of orderly analogues of graph generators proposed by Heap and Farrell is established. The modifications to these algorithms supply practical methods enabling one to generate exhaustive lists of graphs and locally restricted graphs; moreover, the difficulty involved in ensuring that no duplications occur in the list is greatly reduced.     

Automatic, evolutionary test data generation for dynamic software testing

This paper proposes a dynamic test data generation framework based on genetic algorithms. The framework houses a Program Analyser and a Test Case Generator, which intercommunicate to automatically generate test cases. The Program Analyser extracts statements and variables, isolates code paths and creates control flow graphs. The Test Case Generator utilises two optimisation algorithms, the Batch-Optimistic (BO) and the Close-Up (CU), and produces a near to optimum set of test cases with respect to the edge/condition coverage criterion. The efficacy of the proposed approach is assessed on a number of programs and the empirical results indicate that its performance is significantly better compared to existing dynamic test data generation methods.     

图注意力网络的场景图到图像生成模型

目的 目前文本到图像的生成模型仅在具有单个对象的图像数据集上表现良好，当一幅图像涉及多个对象和关系时，生成的图像就会变得混乱。已有的解决方案是将文本描述转换为更能表示图像中场景关系的场景图结构，然后利用场景图生成图像，但是现有的场景图到图像的生成模型最终生成的图像不够清晰，对象细节不足。为此，提出一种基于图注意力网络的场景图到图像的生成模型，生成更高质量的图像。方法 模型由提取场景图特征的图注意力网络、合成场景布局的对象布局网络、将场景布局转换为生成图像的级联细化网络以及提高生成图像质量的鉴别器网络组成。图注意力网络将得到的具有更强表达能力的输出对象特征向量传递给改进的对象布局网络，合成更接近真实标签的场景布局。同时，提出使用特征匹配的方式计算图像损失，使得最终生成图像与真实图像在语义上更加相似。结果 通过在包含多个对象的COCO-Stuff图像数据集中训练模型生成64×64像素的图像，本文模型可以生成包含多个对象和关系的复杂场景图像，且生成图像的Inception Score为7.8左右，与原有的场景图到图像生成模型相比提高了0.5。结论 本文提出的基于图注意力网络的场景图到图像生成模型不仅可以生成包含多个对象和关系的复杂场景图像，而且生成图像质量更高，细节更清晰。     

Automatic urban modeling using volumetric reconstruction with surface graph cuts

The demand for 3D city-scale models has been significantly increased due to the proliferation of urban planning, city navigation, and virtual reality applications. We present an approach to automatically reconstruct buildings densely spanning a large urban area. Our method takes as input calibrated aerial images and available GIS meta-data. Our computational pipeline computes a per-building 2.5D volumetric reconstruction by exploiting photo-consistency where it is highly sampled amongst the aerial images. Our building surface graph cut method overcomes errors of occlusion, geometry, and calibration in order to stitch together aerial images and yield a visually coherent texture-mapped result. Our comparisons show similar quality to the manually modeled buildings of Google Earth, and show improvements over naive texture mapping and over space-carving methods. We have tested our algorithms with a 12 sq km area of Boston, MA (USA), using 4667 images (i.e., 280 GB of raw image data) and producing 1785 buildings.     

Querying massive graph data: A compress and search approach

Querying graph data is a fundamental problem that witnesses an increasing interest especially for massive graph databases which come as a promising alternative to relational databases for big data modeling. In this paper, we study the problem of subgraph isomorphism search which consists to enumerate the embedding of a query graph in a data graph. The most known solutions of this NP-complete problem are backtracking-based and result in a high computational cost when we deal with massive graph databases. We address this problem and its challenges via graph compression with modular decomposition. In our approach, subgraph isomorphism search is performed on compressed graphs without decompressing them yielding substantial reduction of the search space and consequently a significant saving in processing time as well as in storage space for the graphs. We evaluated our algorithms on nine real-word datasets. The experimental results show that our approach is efficient and scalable.     

On labeling in graph visualization

When visualizing graphs, it is essential to communicate the meaning of each graph object via text or graphical labels. Automatic placement of labels in a graph is an NP-Hard problem, for which efficient heuristic solutions have been recently developed. In this paper, we describe a general framework for modeling, drawing, editing, and automatic placement of labels respecting user constraints. In addition, we present the interface and the basic engine of the Graph Editor Toolkit - a family of portable graph visualization libraries designed for integration into graphical user interface application programs. This toolkit produces a high quality automated placement of labels in a graph using our framework. A brief survey of automatic label placement algorithms is also presented. Finally we describe extensions to certain existing automatic label placement algorithms, allowing their integration into this visualization tool.     

Fast processing of graph queries on a large database of small and medium-sized data graphs

We propose a new way of indexing a large database of small and medium-sized graphs and processing exact subgraph matching (or subgraph isomorphism) and approximate (full) graph matching queries. Rather than decomposing a graph into smaller units (e.g., paths, trees, graphs) for indexing purposes, we represent each graph in the database by its graph signature, which is essentially a multiset. We construct a disk-based index on all the signatures via bulk loading. During query processing, a query graph is also mapped into its signature, and this signature is searched using the index by performing multiset operations. To improve the precision of exact subgraph matching, we develop a new scheme using the concept of line graphs. Through extensive evaluation on real and synthetic graph datasets, we demonstrate that our approach provides a scalable and efficient disk-based solution for a large database of small and medium-sized graphs.     

An effective and efficient parallel approach for random graph generation over GPUs

The widespread usage of random graphs   has been highlighted in the context of database applications for several years. This because such data structures turn out to be very useful in a large family of database applications ranging from simulation to sampling, from analysis of complex networks to study of randomized algorithms, and so forth. Amongst others, Erd?s–Rényi _Γv,p${\Gamma }_{v,p}$ is the most popular model to obtain and manipulate random graphs. Unfortunately, it has been demonstrated that classical algorithms for generating Erd?s–Rényi based random graphs do not scale well in large instances and, in addition to this, fail to make use of the parallel processing capabilities of modern hardware. Inspired by this main motivation, in this paper we propose and experimentally assess a novel parallel algorithm for generating random graphs under the Erd?s–Rényi model that is designed and implemented in a Graphics Processing Unit (GPU), called PPreZER. We demonstrate the nice amenities due to our solution via a succession of several intermediary algorithms, both sequential and parallel, which show the limitations of classical approaches and the benefits due to the PPreZER algorithm. Finally, our comprehensive experimental assessment and analysis brings to light a relevant average speedup gain of PPreZER over baseline algorithms.     

Looking for narrow interfaces in automatic differentiation using graph drawing

Automatic differentiation is a powerful technique for evaluating derivatives of functions given in the form of a high-level programming language such as Fortran, C, or C++. This technique is superior, in terms of accuracy, to numerical differentiation because it avoids the truncation error involved in divided difference approximations. In automatic differentiation, the program is treated as a potentially very long composition of elementary functions to which the chain rule of differential calculus is applied over and over again. Because of the associativity of the chain rule, there is room for different strategies computing the same numerical results but whose computational cost may vary significantly. Several strategies exploiting high-level structure of the underlying computer code are known to reduce computational cost as opposed to blindly applying automatic differentiation. An example includes “interface contraction” where one takes advantage of the fact that the number of variables passed between subroutines is small compared with the number of propagated directional derivatives. Unfortunately, these so-called narrow interfaces are not immediately available. The present study investigates the use of the VCG graph drawing tool to recognize narrow interfaces in the computational graph, a certain directed acyclic graph used to represent data dependences of variables in the underlying computer code.     

基于图生成过程的跨领域推荐

推荐系统在各方各面得到充分的应用,时刻影响着日常生活。要训练出一个良好的推荐系统往往需要大量的用户—商品交互数据,但是实际情况下获得的数据往往是十分稀疏的,这往往会使得训练出来的模型过拟合,最后难以获得理想的推荐效果。为了解决这个问题,跨领域推荐系统应运而生。目前大部分的跨领域推荐系统工作都是借鉴传统领域自适应的方法,使用基于特征对齐或者对抗学习的思想将领域不变用户兴趣从有丰富数据的源域迁移到稀疏的目标域上,例如豆瓣电影迁移到豆瓣图书。但是由于不同推荐平台的网络结构有所不同,现有方法暴力提取的领域不变的语义信息容易和结构信息耦合,导致错配现象。而且,现有方法忽略了图数据本身存在的噪声,导致实验效果进一步受到了影响。为了解决这个问题,首先引入了图数据的因果数据生成过程,通过领域特征隐变量和语义特征隐变量、噪声隐变量解耦出来,通过使用每个节点的语义隐变量进行推荐,从而获得领域不变的推荐效果。在多个公开数据集上验证了该方法,并取得了目前最好的实验效果。     

EFSM模型的字符串类型测试数据自动生成

基于软件描述模型的测试数据自动生成研究中,字符串类型测试数据生成是一个研究热点和难点。EFSM模型是一种重要的软件描述模型。分析了EFSM模型的特点,针对面向EFSM模型目标路径的字符串测试数据生成,建立了字符串输入变量模型和操作模型,结合静态测试的特点,给出了通过字符串变量模型在目标路径上的符号执行结果生成字符串类型测试数据的方法。实验结果表明,该方法能够达到预期效果,提高测试生成效率。     

Learning block-preserving graph patterns and its application to data mining

Recently, due to the rapid growth of electronic data having graph structures such as HTML and XML texts and chemical compounds, many researchers have been interested in data mining and machine learning techniques for finding useful patterns from graph-structured data (graph data). Since graph data contain a huge number of substructures and it tends to be computationally expensive to decide whether or not such data have given structural features, graph mining problems face computational difficulties. Let be a graph class which satisfies a connected hereditary property and contains infinitely many different biconnected graphs, and for which a special kind of the graph isomorphism problem can be computed in polynomial time. In this paper, we consider learning and mining problems for  . Firstly, we define a new graph pattern, which is called a block preserving graph pattern (bp-graph pattern) for  . Secondly, we present a polynomial time algorithm for deciding whether or not a given bp-graph pattern matches a given graph in  . Thirdly, by giving refinement operators over bp-graph patterns, we present a polynomial time algorithm for finding a minimally generalized bp-graph pattern for  . Outerplanar graphs are planar graphs which can be embedded in the plane in such a way that all of vertices lie on the outer boundary. Many pharmacologic chemical compounds are known to be represented by outerplanar graphs. The class of connected outerplanar graphs satisfies the above conditions for  . Next, we propose two incremental polynomial time algorithms for enumerating all frequent bp-graph patterns with respect to a given finite set of graphs in  . Finally, by reporting experimental results obtained by applying the two graph mining algorithms to a subset of the NCI dataset, we evaluate the performance of the two graph mining algorithms.     

基于漏洞关联攻击代价的攻击图生成算法

在已有的网络攻击图生成方法的基础上,从漏洞关联的攻击代价出发,设计了一种攻击图生成基本框架,提出了一种基于漏洞关联攻击代价的网络攻击图的自动生成算法。该算法能有效结合漏洞之间的相关性,科学地评估攻击代价,有效删除了攻击代价过高、现实意义不大的攻击路径,简化了攻击图,并通过实验检验了该算法的合理性和有效性。     

面向电厂关键设备故障知识图谱构建的关系抽取方法研究

当今电厂面临着诸多挑战,包括电力设备种类繁多、设备数量庞大、故障类型众多、数据耦合关系复杂以及海量的故障信息数据等。知识图谱能够将各种信息整合、可视化呈现,并支持智能化应用,有助于人们更好地获取、管理和应用知识,从而提高效率、创造价值。运用知识图谱来分析电厂故障数据,有助于深入研究电厂设备故障情况。在构建知识图谱的过程中,关系抽取是关键步骤之一,其准确率直接影响最终知识图谱构建的质量。本文提出了一个面向电厂关键发电设备故障知识图谱构建的关系抽取工具,该工具能将故障信息中海量、异构的数据以及相关故障处理进行可视化表达,同时支持用户交互式地参与到关系抽取的过程中,通过迭代训练来优化关系抽取模型。在实验测试阶段,利用真实电厂设备故障数据进行验证,证明了该工具在显著提高关系抽取的准确率方面的有效性。因此,构建的知识图谱质量得以提升,为电厂管理人员更好地运维管理发电设备提供了重要支持,为管控电厂相关数据以及推动电厂完备建设提供有力支撑。     

Automatic CoDec generation to reduce test engineering cost

TTCN-3 is an abstract language for specification of Abstract Test Suites. Coding of TTCN-3 values into physically transmittable messages and decoding of bitstrings into their TTCN-3 representation has been removed from the language itself and relayed to external and specialized components, called CoDec. CoDec development, either implicitly or explicitly, is a must in any TTCN-3 testing activity. Field experience showed that there is a high cost associated with CoDec development and maintenance. To achieve adequate software engineering practices, a set of types, tools and definitions were developed. This paper unveils gray areas in TTCN-3 architecture and presents a methodological approach to minimize the complexity of CoDec development. Even though the initial field of application is IPv6 testing, the main tool introduced—the CoDec Generator—is a valuable tool in any testing application domain. It is designed to lower the CoDec maintenance costs in all test case lifecycle stages, from development to maintenance. This work has been partly supported by the IST Go4IT European project: .     

Structure and attribute index for approximate graph matching in large graphs

The increasing popularity of graph data in various domains has lead to a renewed interest in developing efficient graph matching techniques, especially for processing large graphs. In this paper, we study the problem of approximate graph matching in a large attributed graph. Given a large attributed graph and a query graph, we compute a subgraph of the large graph that best matches the query graph. We propose a novel structure-aware and attribute-aware index to process approximate graph matching in a large attributed graph. We first construct an index on the similarity of the attributed graph, by partitioning the large search space into smaller subgraphs based on structure similarity and attribute similarity. Then, we construct a connectivity-based index to give a concise representation of inter-partition connections. We use the index to find a set of best matching paths. From these best matching paths, we compute the best matching answer graph using a greedy algorithm. Experimental results on real datasets demonstrate the efficiency of both index construction and query processing. We also show that our approach attains high-quality query answers.     

Automatic learning of cost functions for graph edit distance

Graph matching and graph edit distance have become important tools in structural pattern recognition. The graph edit distance concept allows us to measure the structural similarity of attributed graphs in an error-tolerant way. The key idea is to model graph variations by structural distortion operations. As one of its main constraints, however, the edit distance requires the adequate definition of edit cost functions, which eventually determine which graphs are considered similar. In the past, these cost functions were usually defined in a manual fashion, which is highly prone to errors. The present paper proposes a method to automatically learn cost functions from a labeled sample set of graphs. To this end, we formulate the graph edit process in a stochastic context and perform a maximum likelihood parameter estimation of the distribution of edit operations. The underlying distortion model is learned using an Expectation Maximization algorithm. From this model we finally derive the desired cost functions. In a series of experiments we demonstrate the learning effect of the proposed method and provide a performance comparison to other models.     

Fast planning through planning graph analysis

We introduce a new approach to planning in STRIPS-like domains based on constructing and analyzing a compact structure we call a planning graph. We describe a new planner, Graphplan, that uses this paradigm. Graphplan always returns a shortest possible partial-order plan, or states that no valid plan exists.

We provide empirical evidence in favor of this approach, showing that Graphplan outperforms the total-order planner, Prodigy and the partial-order planner, UCPOP, on a variety of interesting natural and artificial planning problems. We also give empirical evidence that the plans produced by Graphplan are quite sensible. Since searches made by this approach are fundamentally different from the searches of other common planning methods, they provide a new perspective on the planning problem.     

基于攻击图的渗透测试方案自动生成方法

为满足网络安全管理需要,提出一种新的渗透测试方案自动生成方法。该方法利用被测试目标网络脆弱点间的逻辑关系,结合原子攻击知识库,通过前向广度优先搜索策略产生渗透攻击图,然后深度优先遍历渗透攻击图生成渗透测试方案,并基于该方法设计实现渗透测试预案自动生成原型系统。实例表明该方法能够有效生成可行的渗透测试方案。     

Generalized median graph computation by means of graph embedding in vector spaces

The median graph has been presented as a useful tool to represent a set of graphs. Nevertheless its computation is very complex and the existing algorithms are restricted to use limited amount of data. In this paper we propose a new approach for the computation of the median graph based on graph embedding. Graphs are embedded into a vector space and the median is computed in the vector domain. We have designed a procedure based on the weighted mean of a pair of graphs to go from the vector domain back to the graph domain in order to obtain a final approximation of the median graph. Experiments on three different databases containing large graphs show that we succeed to compute good approximations of the median graph. We have also applied the median graph to perform some basic classification tasks achieving reasonable good results. These experiments on real data open the door to the application of the median graph to a number of more complex machine learning algorithms where a representative of a set of graphs is needed.