A user parameter-free approach for mining robust sequential classification rules

Recent years have witnessed extensive studies of graph classification due to the rapid increase in applications involving structural data and complex relationships. To support graph classification, all existing methods require that training graphs should be relevant (or belong) to the target class, but cannot integrate graphs irrelevant to the class of interest into the learning process. In this paper, we study a new universum graph classification framework which leverages additional “non-example” graphs to help improve the graph classification accuracy. We argue that although universum graphs do not belong to the target class, they may contain meaningful structure patterns to help enrich the feature space for graph representation and classification. To support universum graph classification, we propose a mathematical programming algorithm, ugBoost, which integrates discriminative subgraph selection and margin maximization into a unified framework to fully exploit the universum. Because informative subgraph exploration in a universum setting requires the search of a large space, we derive an upper bound discriminative score for each subgraph and employ a branch-and-bound scheme to prune the search space. By using the explored subgraphs, our graph classification model intends to maximize the margin between positive and negative graphs and minimize the loss on the universum graph examples simultaneously. The subgraph exploration and the learning are integrated and performed iteratively so that each can be beneficial to the other. Experimental results and comparisons on real-world dataset demonstrate the performance of our algorithm.     

Motorcycle graph enumeration from quadrilateral meshes for reverse engineering

Recently proposed quad-meshing techniques allow the generation of high-quality semi-regular quadrilateral meshes. This paper outlines the generation of quadrilateral segments using such meshes. Quadrilateral segments are advantageous in reverse engineering because they do not require surface trimming or surface parameterization. The motorcycle graph algorithm of Eppstein et al. produces the motorcycle graph of a given quadrilateral mesh consisting of quadrilateral segments. These graphs are preferable to base complexes, because the mesh can be represented with a smaller number of segments, as T-joints (where the intersection of two neighboring segments does not involve the whole edge or the vertex) are allowed in quadrilateral segmentation.The proposed approach in this study enumerates all motorcycle graphs of a given quadrilateral mesh and optimum graph for reverse engineering is then selected. Due to the high computational cost of enumerating all these graphs, the mesh is cut into several sub-meshes whose motorcycle graphs are enumerated separately. The optimum graph is then selected based on a cost function that produces low values for graphs whose edges trace a large number of highly curved regions in the model. By applying several successive enumeration steps for each sub-mesh, a motorcycle graph for the given mesh is found. We also outline a method for the extraction of feature curves (sets of highly curved edges) and their integration into the proposed algorithm. Quadrilateral segments generated using the proposed techniques are validated by B-spline surfaces.     

A Bayesian nonparametric approach to modeling motion patterns

The most difficult??and often most essential??aspect of many interception and tracking tasks is constructing motion models of the targets. Experts rarely can provide complete information about a target??s expected motion pattern, and fitting parameters for complex motion patterns can require large amounts of training data. Specifying how to parameterize complex motion patterns is in itself a difficult task. In contrast, Bayesian nonparametric models of target motion are very flexible and generalize well with relatively little training data. We propose modeling target motion patterns as a mixture of Gaussian processes (GP) with a Dirichlet process (DP) prior over mixture weights. The GP provides an adaptive representation for each individual motion pattern, while the DP prior allows us to represent an unknown number of motion patterns. Both automatically adjust the complexity of the motion model based on the available data. Our approach outperforms several parametric models on a helicopter-based car-tracking task on data collected from the greater Boston area.     

Graph mining for discovering infrastructure patterns in configuration management databases

A configuration management database (CMDB) can be considered to be a large graph representing the IT infrastructure entities and their interrelationships. Mining such graphs is challenging because they are large, complex, and multi-attributed and have many repeated labels. These characteristics pose challenges for graph mining algorithms, due to the increased cost of subgraph isomorphism (for support counting) and graph isomorphism (for eliminating duplicate patterns). The notion of pattern frequency or support is also more challenging in a single graph, since it has to be defined in terms of the number of its (potentially, exponentially many) embeddings. We present CMDB-Miner, a novel two-step method for mining infrastructure patterns from CMDB graphs. It first samples the set of maximal frequent patterns and then clusters them to extract the representative infrastructure patterns. We demonstrate the effectiveness of CMDB-Miner on real-world CMDB graphs, as well as synthetic graphs.     

Local Editing of Procedural Models

Procedural modeling is used across many industries for rapid 3D content creation. However, professional procedural tools often lack artistic control, requiring manual edits on baked results, diminishing the advantages of a procedural modeling pipeline. Previous approaches to enable local artistic control require special annotations of the procedural system and manual exploration of potential edit locations. Therefore, we propose a novel approach to discover meaningful and non‐redundant good edit locations (GELs). We introduce a bottom‐up algorithm for finding GELs directly from the attributes in procedural models, without special annotations. To make attribute edits at GELs persistent, we analyze their local spatial context and construct a meta‐locator to uniquely specify their structure. Meta‐locators are calculated independently per attribute, making them robust against changes in the procedural system. Functions on meta‐locators enable intuitive and robust multi‐selections. Finally, we introduce an algorithm to transfer meta‐locators to a different procedural model. We show that our approach greatly simplifies the exploration of the local edit space, and we demonstrate its usefulness in a user study and multiple real‐world examples.     

Automatic evolution of programs for procedural generation of terrains for video games

Nowadays the video game industry is facing a big challenge to keep costs under control as games become bigger and more complex. Creation of game content, such as character models, maps, levels, textures, sound effects and so on, represent a big slice of total game production cost. Hence, the video game industry is increasingly turning to procedural content generation to amplify the cost-effectiveness of the efforts of video game designers. However, procedural methods for automated content generation are difficult to create and parametrize. In this work we study a genetic programming-based procedural content technique to generate procedural terrains that do not require parametrization, thus, allowing to save time and help reducing production costs. Generated procedural terrains present aesthetic appeal; however, unlike most techniques involving aesthetic, our approach does not require a human to perform the evaluation. Instead, the search is guided by the weighted sum of two morphological metrics: terrain accessibility and obstacle edge length. The combination of the two metrics allowed us to find a wide range of fit terrains that present more scattered obstacles in different locations than our previous approach with a single metric. Procedural terrains produced by this technique are already in use in a real video game.     

SkyGraph: an algorithm for important subgraph discovery in relational graphs

A significant number of applications require effective and efficient manipulation of relational graphs, towards discovering important patterns. Some example applications are: (i) analysis of microarray data in bioinformatics, (ii) pattern discovery in a large graph representing a social network, (iii) analysis of transportation networks, (iv) community discovery in Web data. The basic approach followed by existing methods is to apply mining techniques on graph data to discover important patterns, such as subgraphs that are likely to be useful. However, in some cases the number of mined patterns is large, posing difficulties in selecting the most important ones. For example, applying frequent subgraph mining on a set of graphs the system returns all connected subgraphs whose frequency is above a specified (usually user-defined) threshold. The number of discovered patterns may be large, and this number depends on the data characteristics and the frequency threshold specified. It would be more convenient for the user if “goodness” criteria could be set to evaluate the usefulness of these patterns, and if the user could provide preferences to the system regarding the characteristics of the discovered patterns. In this paper, we propose a methodology to support such preferences by applying subgraph discovery in relational graphs towards retrieving important connected subgraphs. The importance of a subgraph is determined by: (i) the order of the subgraph (the number of vertices) and (ii) the subgraph edge connectivity. The performance of the proposed technique is evaluated by using real-life as well as synthetically generated data sets.     

Efficient relational calculation for software analysis

Calculating with graphs and relations has many applications in the analysis of software systems, for example, the detection of design patterns or patterns of problematic design and the computation of design metrics. These applications require an expressive query language, in particular, for the detection of graph patterns, and an efficient evaluation of the queries even for large graphs. In this paper, we introduce RML, a simple language for querying and manipulating relations based on predicate calculus, and CrocoPat, an interpreter for RML programs. RML is general because it enables the manipulation not only of graphs (i.e., binary relations), but of relations of arbitrary arity. CrocoPat executes RML programs efficiently because it internally represents relations as binary decision diagrams, a data structure that is well-known as a compact representation of large relations in computer-aided verification. We evaluate RML by giving example programs for several software analyses and CrocoPat by comparing its performance with calculators for binary relations, a Prolog system, and a relational database management system.     

基于因子图模型的动态图半监督聚类算法

针对动态图的聚类主要存在着两点不足:首先, 现有的经典聚类算法大多从静态图分析的角度出发, 无法对真实网络图持续演化的特性进行有效建模, 亟待对动态图的聚类算法展开研究, 通过对不同时刻图快照的聚类结构进行分析进而掌握图的动态演化情况.其次, 真实网络中可以预先获取图中部分节点的聚类标签, 如何将这些先验信息融入到动态图的聚类结构划分中, 从而向图中的未标记节点分配聚类标签也是本文需要解决的问题.为此, 本文提出进化因子图模型(Evolution factor graph model, EFGM)用于解决动态图节点的半监督聚类问题, 所提EFGM不仅可以捕获动态图的节点属性和边邻接属性, 还可以捕获节点的时间快照信息.本文对真实数据集进行实验验证, 实验结果表明EFGM算法将动态图与先验信息融合到一个统一的进化因子图框架中, 既使得聚类结果满足先验知识, 又契合动态图的整体演化规律, 有效验证了本文方法的有效性.     

Design Pattern Detection Using Similarity Scoring

The identification of design patterns as part of the reengineering process can convey important information to the designer. However, existing pattern detection methodologies generally have problems in dealing with one or more of the following issues: identification of modified pattern versions, search space explosion for large systems and extensibility to novel patterns. In this paper, a design pattern detection methodology is proposed that is based on similarity scoring between graph vertices. Due to the nature of the underlying graph algorithm, this approach has the ability to also recognize patterns that are modified from their standard representation. Moreover, the approach exploits the fact that patterns reside in one or more inheritance hierarchies, reducing the size of the graphs to which the algorithm is applied. Finally, the algorithm does not rely on any pattern-specific heuristic, facilitating the extension to novel design structures. Evaluation on three open-source projects demonstrated the accuracy and the efficiency of the proposed method     

Computer aided verification of Lamport's fast mutual exclusionalgorithm using colored Petri nets and occurrence graphs with symmetries

In this paper, we present a computer tool for verification of distributed systems. As an example, we establish the correctness of Lamport's Fast Mutual Exclusion Algorithm. The tool implements the method of occurrence graphs with symmetries (OS-graphs) for Colored Petri Nets (CP-nets). The basic idea in the approach is to exploit the symmetries inherent in many distributed systems to construct a condensed state space. We demonstrate a significant increase in the number of states which can be analyzed. The paper is to a large extent self-contained and does not assume any prior knowledge of CP-nets (or any other kinds of Petri Nets) or OS-graphs. CP-nets and OS-graphs are not our invention. Our contribution is the development of the tool and verification of the example, demonstrating how the method of occurrence graphs with symmetries can be put into practice     

Semidynamic Algorithms for Maintaining Single-Source Shortest Path Trees

We consider the problem of updating a single-source shortest path in either a directed or an undirected graph, with positive real edge weights. Our algorithms for the incremental problem (handling edge insertions and cost decrements) work for any graph; they have optimal space requirements and query time, but their performances depend on the class of the considered graph. The cost of updates is computed in terms of amortized complexity and depends on the size of the output modifications. In the case of graphs with bounded genus (including planar graphs), graphs with bounded arboricity (including bounded degree graphs), and graphs with bounded treewidth, the incremental algorithms require O(log n) amortized time per vertex update, where a vertex is considered updated if it reduces its distance from the source. For general graphs with n vertices and m edges our incremental solution requires O( log n) amortized time per vertex update. We also consider the decremental problem for planar graphs, providing algorithms and data structures with analogous performances. The algorithms, based on Dijkstra's technique [6], require simple data structures that are really suitable for a practical and straightforward implementation. Received January 1995; revised February 1997.     

Identifying FMS repetitive patterns for efficient search-based scheduling algorithm: A colored Petri net approach

The multiple lot size scheduling problem plays a crucial role in minimizing production and setup costs in order to respond to constant fluctuations in customer demands. However, the computational cost to optimize a scheduling problem increases as the lot size of jobs increases, leading to a scalability problem for most scheduling algorithms. This paper presents an efficient search approach based on colored Petri net (CPN) formalism that addresses the state explosion problem of reachability graphs used for finding the optimal solutions to scheduling problems. To reduce the memory requirements, the proposed approach exploits the structural equivalence found in the reachability graphs of flexible manufacturing systems’ (FMS) CPNs to discard states once they are no longer needed to explore the state space. The hypothetical structural equivalence is attributed to the repetitive patterns identified in the execution of manufacturing processes when the lot sizes of jobs are scaled for FMS whose underlying layout configuration is fixed. We present the concept of structural equivalence based on duplicate state detection for FMS of different lot sizes and give sufficient conditions under which the structural equivalence obtained from a few lot size (smaller) instances holds for the same FMS of a larger size. The approach is validated experimentally on different FMS examples which confirm that the behavior of an FMS of any large lot size can be inferred from the FMS of a smaller size. Experimental results indicate that this work performs better than prior search methods and obtains optimal schedules of FMS with large lot sizes. Also, we show that the approach is applicable to FMS problems of similar configurations where the problem size differ by the number of jobs, resources and operations.     

Differentiable Depth for Real2Sim Calibration of Soft Body Simulations

In this work, we present a novel approach for calibrating material model parameters for soft body simulations using real data. We use a fully differentiable pipeline, combining a differentiable soft body simulator and differentiable depth rendering, which permits fast gradient-based optimizations. Our method requires no data pre-processing, and minimal experimental set-up, as we directly minimize the L2-norm between raw LIDAR scans and rendered simulation states. In essence, we provide the first marker-free approach for calibrating a soft-body simulator to match observed real-world deformations. Our approach is inexpensive as it solely requires a consumer-level LIDAR sensor compared to acquiring a professional marker-based motion capture system. We investigate the effects of different material parameterizations and evaluate convergence for parameter optimization in both single and multi-material scenarios of varying complexity. Finally, we show that our set-up can be extended to optimize for dynamic behaviour as well.     

Hinge-free topology optimization with embedded translation-invariant differentiable wavelet shrinkage

In topology optimization applications for the design of compliant mechanisms, the formation of hinges is typically encountered. Often such hinges are unphysical artifacts that appear due to the choice of discretization spaces for design and analysis. The objective of this work is to present a new method to find hinge-free designs using multiscale wavelet-based topology optimization formulation. The specific method developed in this work does not require refinement of the analysis model and it consists of a translation-invariant wavelet shrinkage method where a hinge-free condition is imposed in the multiscale design space. To imbed the shrinkage method implicitly in the optimization formulation and thus facilitate sensitivity analysis, the shrinkage method is made differentiable by means of differentiable versions of logical operators. The validity of the present method is confirmed by solving typical two-dimensional compliant mechanism design problems.     

Using graph rewriting methods for the semi-automatic generation of parametric infrastructure models

For the design of large infrastructure projects such as inner-city subway tracks, it proves necessary to consider differing model scales, ranging from the scale of several kilometers down to a few millimeters. This challenge can be addressed by using multi-scale product models comprising multiple levels of detail (LoD). Ensuring consistency across the different LoDs can be achieved by applying procedural and parametric modeling techniques while creating the model. This results in a flexible multi-scale model that can be easily modified on one scale while other scales are automatically updated. However, the correct application of parametric constraints and procedural dependencies has shown to be a very complex and time-consuming process. To address this issue, this papers presents a semi-automated detailing mechanism, which is based on formal procedures based on graphs and graph transformations. This paper discusses how procedural parametric models based on two-dimensional sketches can be represented by graphs and how detailing steps in the form of parametric modeling operations can be formalized by using rule-based graph rewriting.     

A BSS-based space–time multi-channel algorithm for complex-jamming suppression

This paper considers the problem of suppressing complex-jamming, which contains sidelobe blanket jammings (SLJs), multiple near-mainlobe blanket jammings (multiple-NMLJs) and self-defensive false target jamming (SDJ). We propose a blind source separation (BSS)-based space–time multi-channel algorithm for complex-jamming suppression. The space–time multi-channel consists of spatial multiple beams and temporal multiple adjacent pulse repetition intervals (PRIs). The source signals can be separated by the BSS, owing to their statistical independence. The real target and SDJ can then be obtained by the pulse compression approach, distinguished by echo identification simultaneously. A remarkable feature of the proposed approach is that it does not require prior knowledge about real target or jammings, and it is easy to implement for engineering applications.     

Training of a discrete recurrent neural network for sequence classification by using a helper FNN

This research is concerned with a gradient descent training algorithm for a target network that makes use of a helper feed-forward network (FFN) to represent the cost function required for training the target network. A helper FFN is trained because the cost relation for the target is not differentiable. The transfer function of the trained helper FFN provides a differentiable cost function of the parameter vector for the target network allowing gradient search methods for finding the optimum values of the parameters. The method is applied to the training of discrete recurrent networks (DRNNs) that are used as a tool for classification of temporal sequences of characters from some alphabet and identification of a finite state machine (FSM) that may have produced all the sequences. Classification of sequences that are input to the DRNN is based on the terminal state of the network after the last element in the input sequence has been processed. If the DRNN is to be used for classifying sequences the terminal states for class 0 sequences must be distinct from the terminal states for class 1 sequences. The cost value to be used in training must therefore be a function of this disjointedness and no more. The outcome of this is a cost relationship that is not continuous but discrete and therefore derivative free methods have to be used or alternatively the method suggested in this paper. In the latter case the transform function of the helper FFN that is trained using the cost function is a differentiable function that can be used in the training of the DRNN using gradient descent.Acknowledgement. This work was supported by a discovery grant from the Government of Canada. The comments made by the reviewers are also greatly appreciated and have proven to be quite useful.     

An image-based texture mapping technique for apparel products exhibition and interior design

In this paper, we propose an image-based texture mapping technique for textile products exhibition that does not require geometric representation of 3D models. Under this technique, a texture grid is built interactively for a target area in an original image. This grid acts as the intermediate space between planar space and texture space. The texture coordinate for each pixel in the target area can be calculated based on this grid, and the 3D effect can be successfully realized by further fine adjustment of the grid. This technique can be applied in apparel products exhibition and interior design.     

Visualization of large networks with min-cut plots,A-plots and R-MAT

What does a “normal” computer (or social) network look like? How can we spot “abnormal” sub-networks in the Internet, or web graph? The answer to such questions is vital for outlier detection (terrorist networks, or illegal money-laundering rings), forecasting, and simulations (“how will a computer virus spread?”).The heart of the problem is finding the properties of real graphs that seem to persist over multiple disciplines. We list such patterns and “laws”, including the “min-cut plots” discovered by us. This is the first part of our NetMine package: given any large graph, it provides visual feedback about these patterns; any significant deviations from the expected patterns can thus be immediately flagged by the user as abnormalities in the graph. The second part of NetMine is the A-plots tool for visualizing the adjacency matrix of the graph in innovative new ways, again to find outliers. Third, NetMine contains the R-MAT (Recursive MATrix) graph generator, which can successfully model many of the patterns found in real-world graphs and quickly generate realistic graphs, capturing the essence of each graph in only a few parameters. We present results on multiple, large real graphs, where we show the effectiveness of our approach.