Symbol recognition by error-tolerant subgraph matching betweenregion adjacency graphs

We propose an error-tolerant subgraph isomorphism algorithm formulated in terms of region adjacency graphs (RAG). A set of edit operations to transform one RAG into another one are defined as regions are represented by polylines and string matching techniques are used to measure their similarity. The algorithm follows a branch and bound approach driven by the RAG edit operations. This formulation allows matching computing under distorted inputs and also reaching a solution in a near polynomial time. The algorithm has been used for recognizing symbols in hand drawn diagrams     

The Priority Tree, a HL/HSR Approach for PHIGS

The Programmer's Hierarchical Interactive Grahics System (PHIGS) specifies an interface for programming device-independent computer graphics applications. PHIGS provides a powerful data grouping mechanism, called the PHIGS structure, that may be used to model the geometry of 3D objects. Hidden Line/Hidden Surface Removal (HL/HSR) is a required process to produce realistic solid views of the modeled objects. Modeling clip is an essential process for viewing a clipped portion of the modeled objects. A technique is presented that provides HL/HSR and modeling clip as added utilities to PHIGS. The technique is based on the Binary Space Partitioning (BSP) tree (sometimes called priority tree), and involves a back to front sorting of the primitives of a PHIGS structure network to another PHIGS structure. Modeling clip is achieved by limiting the sorting to those primitives in a specified clip ping region of the object space. The resulting structure when displayed on a raster device produces a realistic view of the possibly clipped object that was originally modeled by the PHIGS structure network.     

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.     

A computational architecture for heterogeneous reasoning

In this paper we describe a computational architecture for applications that support heterogeneous reasoning. Heterogeneous reasoning is, in its most general form, reasoning that employs representations drawn from multiple representational forms. Of particular importance, and the principal focus of the architecture, is heterogeneous reasoning which employs one or more forms of graphical representation, perhaps in combination with sentences (of English or another language, whether natural or scientific). Graphical representations include diagrams, pictures, layouts, blueprints, flowcharts, graphs, maps, tables, spreadsheets, animations, video, and 3D models. By ‘an application that supports heterogeneous reasoning’ we mean an application that allows users to construct, record, edit, and replay a process of reasoning using multiple representations so that the structure of the reasoning is maintained and the informational dependencies and justifications of the individual steps of the reasoning can be recorded.     

Matching graphs with unique node labels

A special class of graphs is introduced in this paper. The graphs belonging to this class are characterised by the existence of unique node labels. A number of matching algorithms for graphs with unique node labels are developed. It is shown that problems such as graph isomorphism, subgraph isomorphism, maximum common subgraph (MCS) and graph edit distance (GED) have a computational complexity that is only quadratic in the number of nodes. Moreover, computing the median of a set of graphs is only linear in the cardinality of the set. In a series of experiments, it is demonstrated that the proposed algorithms run very fast in practice. The considered class makes the matching of large graphs, consisting of thousands of nodes, computationally tractable. We also discuss an application of the considered class of graphs and related matching algorithms to the classification and detection of abnormal events in computer networks.     

A binary linear programming formulation of the graph edit distance

A binary linear programming formulation of the graph edit distance for unweighted, undirected graphs with vertex attributes is derived and applied to a graph recognition problem. A general formulation for editing graphs is used to derive a graph edit distance that is proven to be a metric, provided the cost function for individual edit operations is a metric. Then, a binary linear program is developed for computing this graph edit distance, and polynomial time methods for determining upper and lower bounds on the solution of the binary program are derived by applying solution methods for standard linear programming and the assignment problem. A recognition problem of comparing a sample input graph to a database of known prototype graphs in the context of a chemical information system is presented as an application of the new method. The costs associated with various edit operations are chosen by using a minimum normalized variance criterion applied to pairwise distances between nearest neighbors in the database of prototypes. The new metric is shown to perform quite well in comparison to existing metrics when applied to a database of chemical graphs.     

An Implementer's View of PHIGS

The Programmer's Hierarchical Interactive Graphics System (PHIGS) specifies an interface for programming device-independent computer graphics applications. After a brief review of PHIGS concepts, an experimental environment used to study and evaluate the proposed standard is presented. The basic structure and distribution of function in this PHIGS implementation is discussed. We describe the architecture of a device-independent environment designed to realize the performance essential to the adequate functioning of a PHIGS implementation. The results presented emphasize the PHIGS output model. Full utilization of workstation processing capabilities, minimization of host/workstation interaction and efficient data management are key to our implementation.     

A Library for Developing PHIGS Programming Tools in a PEX Environment

The merger of three-dimensional graphics with the X Window System has recently been standardized by adapting PHIGS, the Programmer's Hierarchical Interactive Graphics System, to the X Window System with PEX, the PHIGS Extension to X. The standard programming library for PEX has been defined to be identical to PHIGS PLUS allowing PHIGS programs to port directly to the X environment. X uses a client server model to run applications as client processes which communicate with a server to perform graphical display and input. For improved performance, the PEX extension defines new server resources to reduce network traffic and to take advantage of graphics hardware existing on high-end servers. A side effect of this distributed model of computation is a distribution of PHIGS structures leading to a relaxation of the exclusive access which a PHIGS application usually maintains over its Central Structure Store. We exploit the distributed nature of a PEX/PHIGS client's Central Structure Store to provide access to it for other applications besides the originating PEX/PHIGS client. We refer to these other applications as tools since one of our primary goals is to create development tools for PHIGS programmers. Rather than concentrate on particular debugging tools, we focus upon easing the process of actually developing tools. Our goal is to supply a collection of routines which can be used by PHIGS programmers to create custom tools or other programs which require access to the graphics data of remote PHIGS processes. Our Tool Development Library provides the PHIGS programmer a small number of management routines which orchestrate the connection and mapping to the data of one or more remote PHIGS applications. Manipulation of remote PHIGS structures is accomplished just as easily as local operations and is performed using standard PHIGS calls. The remote application being accessed requires no changes to its source code. Obvious uses for the Tool Development Library are in the construction of PHIGS tools such as structure browsers, editors and debugging aids. Less obvious is the potential for developing collections of cooperating graphics applications which share graphics data.     

Independency relationships and learning algorithms for singly connected networks

Graphical structures such as Bayesian networks or Markov networks are very useful tools for representing irrelevance or independency relationships, and they may be used to efficiently perform reasoning tasks. Singly connected networks are important specific cases where there is no more than one undirected path connecting each pair of variables. The aim of this paper is to investigate the kind of properties that a dependency model must verify in order to be equivalent to a singly connected graph structure, as a way of driving automated discovery and construction of singly connected networks in data. The main results are the characterizations of those dependency models which are isomorphic to singly connected graphs (either via the d-separation criterion for directed acyclic graphs or via the separation criterion for undirected graphs), as well as the development of efficient algorithms for learning singly connected graph representations of dependency models.     

Extending Teamwork for architecture diagrams

An architecture-flow diagram extension to the Teamwork dataflow diagramming tool is described. The extension, called TWKAFD, manages FIG format files representing architecture-flow and interconnect diagrams and invokes the X Window version of FIG to let designers graphically edit them. Designers edit the diagrams using simple drawing primitives instead of object primitives. TWKAFD uses Teamwork's approach to handling the relationships between dataflow and architecture-flow diagrams, so the designer does not have to learn two sets of behaviors. TWKAFD's diagram library, user interface, restrictions, and merging into Teamwork are discussed. Results of an experiment to extend Teamwork to accommodate architecture models are presented     

Graph edit distance from spectral seriation

This paper is concerned with computing graph edit distance. One of the criticisms that can be leveled at existing methods for computing graph edit distance is that they lack some of the formality and rigor of the computation of string edit distance. Hence, our aim is to convert graphs to string sequences so that string matching techniques can be used. To do this, we use a graph spectral seriation method to convert the adjacency matrix into a string or sequence order. We show how the serial ordering can be established using the leading eigenvector of the graph adjacency matrix. We pose the problem of graph-matching as a maximum a posteriori probability (MAP) alignment of the seriation sequences for pairs of graphs. This treatment leads to an expression in which the edit cost is the negative logarithm of the a posteriori sequence alignment probability. We compute the edit distance by finding the sequence of string edit operations which minimizes the cost of the path traversing the edit lattice. The edit costs are determined by the components of the leading eigenvectors of the adjacency matrix and by the edge densities of the graphs being matched. We demonstrate the utility of the edit distance on a number of graph clustering problems.     

Using perceptual syntax to enhance semantic content in diagrams

Diagrams are essential in documenting large information systems. They capture, communicate, and leverage knowledge indispensable for solving problems and act as cognitive externalizations (intertwining internal and external processes to extract information from the external world to enhance thought). A diagram provides a mapping from the problem domain to the visual representation by supporting cognitive processes that involve perceptual pattern finding and cognitive symbolic operations. However, not all mappings are equal, and for effectiveness we must embed a diagram's representation with characteristics, which lets users easily perceive meaningful patterns. Consequently, a diagram's effectiveness depends to some extent on how well we construct it as an input to our visual system. In our research, we focus on a class of diagrams commonly referred to as graphs or node-link diagrams. Nodes representing entities, objects, or processes, and links or edges representing relationships between the nodes characterize them. Their most common form is outline circles or boxes denoting nodes and lines of different types representing links between the nodes. Entity-relationship diagrams, software structure diagrams, and data-flow models are examples of node-link diagrams used to model the structure of processes, software, or data     

Scale free interval graphs

Scale free graphs have attracted attention by their non-uniform structure that can be used as a model for various social and physical networks. In this paper, we propose a natural and simple random model for generating scale free interval graphs. The model generates a set of intervals randomly under a certain distribution, which defines a random interval graph. The main advantage of the model is its simpleness. The structure/properties of generated graphs are analyzable by relatively simple probabilistic and/or combinatorial arguments, which is different from many other models. Based on such arguments, we show for our random interval graph that its degree distribution follows a power law, and that it has a large average clustering coefficient.     

Self-organizing maps for learning the edit costs in graph matching.

Although graph matching and graph edit distance computation have become areas of intensive research recently, the automatic inference of the cost of edit operations has remained an open problem. In the present paper, we address the issue of learning graph edit distance cost functions for numerically labeled graphs from a corpus of sample graphs. We propose a system of self-organizing maps (SOMs) that represent the distance measuring spaces of node and edge labels. Our learning process is based on the concept of self-organization. It adapts the edit costs in such a way that the similarity of graphs from the same class is increased, whereas the similarity of graphs from different classes decreases. The learning procedure is demonstrated on two different applications involving line drawing graphs and graphs representing diatoms, respectively.     

A Method for the Representation, Evaluation and Display of CSG Models in PHIGS and PHIGS+

The Programmer's Hierarchical Interactive Graphics System (PHIGS) is about to become a standard graphics system ^† which caters for the definition, display and modification of two and three-dimensional graphical data.
PHIGS , however, is mainly a wireframe system, and the PHIGS⁺ , extensions to it have been put forward to allow the incorporation of shaded 3D graphics into PHIGS. ,
One area that is important to a large constituency and which has so far not been considered in PHIGS , and PHIGS⁺ , is that of solid modelling. This paper addresses one aspect of solid modelling by describing a simple method for the representation, evaluation and display of Constructive Solid Geometry (CSG) models in PHIGS , and PHIGS⁺. .     

Local Community Detection Using Link Similarity

Exploring local community structure is an appealing problem that has drawn much recent attention in the area of social network analysis.As the complete information of network is often difficult to obtain,such as networks of web pages,research papers and Facebook users,people can only detect community structure from a certain source vertex with limited knowledge of the entire graph.The existing approaches do well in measuring the community quality,but they are largely dependent on source vertex and putting too strict policy in agglomerating new vertices.Moreover,they have predefined parameters which are difficult to obtain.This paper proposes a method to find local community structure by analyzing link similarity between the community and the vertex.Inspired by the fact that elements in the same community are more likely to share common links,we explore community structure heuristically by giving priority to vertices which have a high link similarity with the community.A three-phase process is also used for the sake of improving quality of community structure.Experimental results prove that our method performs effectively not only in computer-generated graphs but also in real-world graphs.     

Category-theoretic formalization in designing fuzzy intelligent systems

A complex of problems related to the category-theoretic formalization of fuzzy UML diagrams, fuzzy graphs, and fuzzy-graph transformation systems is examined. The basic constraints that must be satisfied by UML diagrams, which are the basis of fuzzy models of intelligent systems, are investigated. The category-theoretic approach is used to analyze the properties of inference specification based on a distributed system of fuzzy-graph transformations. Means for the compositional construction of fuzzy systems are developed using morphisms and categories of fuzzy graphs.     

A novel edge-centric approach for graph edit similarity computation

Graph similarity is an important notion with many applications. Graph edit distance is one of the most flexible graph similarity measures available. The main problem with this measure is that in practice it can only be computed for small graphs due to its exponential time complexity. This paper addresses the high complexity of graph edit distance computations. Specifically, we present CSI_GED, a novel edge-centric approach for computing graph edit distance through common sub-structure isomorphisms enumeration. CSI_GED utilizes backtracking search combined with a number of heuristics to reduce memory requirements and quickly prune away a large portion of the mapping search space. Experiments show that CSI_GED is highly efficient for computing graph edit distance; it outperforms the state-of-the-art methods by over three orders of magnitude. It also shows that CSI_GED scales the computation gracefully to larger and distant graphs on which current methods fail to run. Moreover, we evaluated CSI_GED as a stand-alone graph edit similarity search query method. The experiments show that CSI_GED is effective and scalable, and outperforms the state-of-the-art indexing-based methods by over two orders of magnitude.