Enhanced graph-based dimensionality reduction with repulsion Laplaceans

Graph-based methods for linear dimensionality reduction have recently attracted much attention and research efforts. The main goal of these methods is to preserve the properties of a graph representing the affinity between data points in local neighborhoods of the high-dimensional space. It has been observed that, in general, supervised graph-methods outperform their unsupervised peers in various classification tasks. Supervised graphs are typically constructed by allowing two nodes to be adjacent only if they are of the same class. However, such graphs are oblivious to the proximity of data from different classes. In this paper, we propose a novel methodology which builds on ‘repulsion graphs’, i.e., graphs that model undesirable proximity between points. The main idea is to repel points from different classes that are close by in the input high-dimensional space. The proposed methodology is generic and can be applied to any graph-based method for linear dimensionality reduction. We provide ample experimental evidence in the context of face recognition, which shows that the proposed methodology (i) offers significant performance improvement to various graph-based methods and (ii) outperforms existing solutions relying on repulsion forces.     

Quotients of Gaussian graphs and their application to perfect codes

A graph-based model of perfect two-dimensional codes is presented in this work. This model facilitates the study of the metric properties of the codes. Signal spaces are modeled by means of Cayley graphs defined over the Gaussian integers and denoted as Gaussian graphs. Codewords of perfect codes will be represented by vertices of a quotient graph of the Gaussian graph in which the signal space has been defined. It will be shown that any quotient graph of a Gaussian graph is indeed a Gaussian graph. This makes it possible to apply previously known properties of Gaussian graphs to the analysis of perfect codes. To illustrate the modeling power of this graph-based tool, perfect Lee codes will be analyzed in terms of Gaussian graphs and their quotients.     

A graph grammars based framework for querying graph-like data

The widespread use of graph-based models for representing data collections (e.g. object-oriented data, XML data, etc.) has stimulated the database research community to investigate the problem of defining declarative languages for querying graph-like databases. In this paper, a new framework for querying graph-like data based on graph grammars is proposed. The new paradigm allows us to verify structural properties of graphs and to extract sub-graphs. More specifically, a new form of query (namely graph query) is proposed, consisting in a particular graph grammar which defines a class of graphs to be matched on the graph representing the database. Thus, differently from path queries, the answer of a graph query is not just a set of nodes, but a subgraph, extracted from the input graph, which satisfies the structural properties defined by the graph grammar. Expressiveness and complexity of different forms of graph queries are discussed, and some practical applications are shown.     

Domain ontology graph model and its application in Chinese text classification

This paper proposes an ontology learning method which is used to generate a graphical ontology structure called ontology graph. The ontology graph defines the ontology and knowledge conceptualization model, and the ontology learning process defines the method of semiautomatic learning and generates ontology graphs from Chinese texts of different domains, the so-called domain ontology graph (DOG). Meanwhile, we also define two other ontological operations—document ontology graph generation and ontology graph-based text classification, which can be carried out with the generated DOG. This research focuses on Chinese text data, and furthermore, we conduct two experiments: the DOG generation and ontology graph-based text classification, with Chinese texts as the experimental data. The first experiment generates ten DOGs as the ontology graph instances to represent ten different domains of knowledge. The generated DOGs are then further used for the second experiment to provide performance evaluation. The ontology graph-based approach is able to achieve high text classification accuracy (with 92.3 % in f-measure) over other text classification approaches (such as 86.8 % in f-measure for tf–idf approach). The better performance in the comparative experiments reveals that the proposed ontology graph knowledge model, the ontology learning and generation process, and the ontological operations are feasible and effective.     

Semi-supervised classification using multiple clusterings

Graph determines the performance of graph-based semi-supervised classification. In this paper, we investigate how to construct a graph from multiple clusterings and propose a method called Semi-Supervised Classification using Multiple Clusterings (SSCMC in short). SSCMC firstly projects original samples into different random subspaces and performs clustering on the projected samples. Then, it constructs a graph by setting an edge between two samples if these two samples are clustered in the same cluster for each clustering. Next, it combines these graphs into a composite graph and incorporates the resulting composite graph with a graph-based semi-supervised classifier based on local and global consistency. Our experimental results on two publicly available facial images show that SSCMC not only achieves higher accuracy than other related methods, but also is robust to input parameters.     

Protein classification by matching and clustering surface graphs

In this paper, we address the problem of comparing and classifying protein surfaces with graph-based methods. Comparison relies on matching surface graphs, extracted from the surfaces by considering concave and convex patches, through a kernelized version of the Softassign graph-matching algorithm. On the other hand, classification is performed by clustering the surface graphs with an EM-like algorithm, also relying on kernelized Softassign, and then calculating the distance of an input surface graph to the closest prototype. We present experiments showing the suitability of kernelized Softassign for both comparing and classifying surface graphs.     

Approximation of graph edit distance based on Hausdorff matching

Graph edit distance is a powerful and flexible method for error-tolerant graph matching. Yet it can only be calculated for small graphs in practice due to its exponential time complexity when considering unconstrained graphs. In this paper we propose a quadratic time approximation of graph edit distance based on Hausdorff matching. In a series of experiments we analyze the performance of the proposed Hausdorff edit distance in the context of graph classification and compare it with a cubic time algorithm based on the assignment problem. Investigated applications include nearest neighbor classification of graphs representing letter drawings, fingerprints, and molecular compounds as well as hidden Markov model classification of vector space embedded graphs representing handwriting. In many cases, a substantial speedup is achieved with only a minor loss in accuracy or, in one case, even with a gain in accuracy. Overall, the proposed Hausdorff edit distance shows a promising potential in terms of flexibility, efficiency, and accuracy.     

Semi-supervised classification based on random subspace dimensionality reduction

Graph structure is vital to graph based semi-supervised learning. However, the problem of constructing a graph that reflects the underlying data distribution has been seldom investigated in semi-supervised learning, especially for high dimensional data. In this paper, we focus on graph construction for semi-supervised learning and propose a novel method called Semi-Supervised Classification based on Random Subspace Dimensionality Reduction, SSC-RSDR in short. Different from traditional methods that perform graph-based dimensionality reduction and classification in the original space, SSC-RSDR performs these tasks in subspaces. More specifically, SSC-RSDR generates several random subspaces of the original space and applies graph-based semi-supervised dimensionality reduction in these random subspaces. It then constructs graphs in these processed random subspaces and trains semi-supervised classifiers on the graphs. Finally, it combines the resulting base classifiers into an ensemble classifier. Experimental results on face recognition tasks demonstrate that SSC-RSDR not only has superior recognition performance with respect to competitive methods, but also is robust against a wide range of values of input parameters.     

基于语义关系对的SVG图形搜索引擎

个性化图形搜索打破了传统的查询方式搜索,将基于关键词的查询方式转变为基于图形的查询方式,使图形的查询具有一定的语义关系,查询结果也更加准确。该文给出一种基于语义关系对的SVG图形搜索引擎。目前大多数浏览器不直接支持SVG图形,但通过该文提出的SVG图形解析器和SVG图形显示器可以对网络上的SVG图形进行检索和显示。     

基于空间句法和最短路径的图核

针对图模式识别领域中现有图核方法对反映图本身拓扑结构的节点特征挖掘不够充分的问题,提出了基于空间句法和最短路径的图核。借鉴建筑学与城市规划学科中的空间句法理论构造分布于图节点上的拓扑特征的量化描述,基于此提出了可表示、计算,正定、适用范围较广的空间句法核和基于最短路径的空间句法核,进而借助支持向量机实现了非精确图匹配。不同于其他图核方法,该方法对图的拓扑特征表达能力强,通用性较好。实验结果表明,所设计的图核在分类精度方面相较于最短路径核有较显著的改善。     

Graph-based representations and techniques for image processing and image analysis

In this paper we will discuss the use of some graph-based representations and techniques for image processing and analysis. Instead of making an extensive review of the graph techniques in this field, we will explain how we are using these techniques in an active vision system for an autonomous mobile robot developed in the Institut de Robòtica i Informàtica Industrial within the project “Active Vision System with Automatic Learning Capacity for Industrial Applications (CICYT TAP98-0473)”. Specifically we will discuss the use of graph-based representations and techniques for image segmentation, image perceptual grouping and object recognition. We first present a generalisation of a graph partitioning greedy algorithm for colour image segmentation. Next we describe a novel fusion of colour-based segmentation and depth from stereo that yields a graph representing every object in the scene. Finally we describe a new representation of a set of attributed graphs (AGs), denominated function-described graphs (FDGs), a distance measure for matching AGs with FDGs and some applications for robot vision.     

The Grasper-CL graph management system

Grasper-CL is a system for manipulating and displaying graphs, and for building graph-based user interfaces for application programs. It is implemented in COMMON LISP and CLIM, and has been proven by use in a number of applications. Grasper-CL includes several advances in graph drawing. It contains a graph abstract datatype plus a comprehensive and novel language of operations on that datatype. The appearance of Grasper-CL graphs can be tailored by a wide variety of shape parameters that allow the application to customize the display of nodes and edges for different domains. Default values for shape parameters can be established at several levels. Grasper-CL employs a toolbox approach to graph layout: the system contains a suite of graph layout algorithms that can be applied individually, or in combination to produce hierarchical graph layouts. The system also contains an interactive graph browser.     

基于l1范数和k近邻叠加图的半监督分类算法*

为了构造一个能够较好反映数据真实分布的图以提高分类性能,文中提出基于l¹范数和k近邻叠加图的半监督分类算法。首先构造一个l¹范数图,作为主图,然后构造一个k近邻图,作为辅图,最后将二者按一定比例叠加,得到l¹范数和k近邻叠加(LNKNNS)图。实验中选择标记样本比例从5%到25%,将基于LNKNNS图的半监督分类算法在USPS数据库上对比其它图(指数权重图、k近邻图、低秩表示图和l¹范数图)的算法。实验表明,文中算法的分类识别率更高,更适合基于图的半监督学习。     

一种基于图的关联规则挖掘改进算法

本文提出了一种基于图的关联规则挖掘的改进算法。首先介绍了基于图的关联规则挖掘算法;然后,在此基础上对原算法进行了修改,通过在图中查找完全子图来寻找频繁项集;最后,对原算法、改进算法和Apriori算法的优缺点进行了简单的比较分析。     

Intelligent fault diagnosis for rolling bearings based on graph shift regularization with directed graphs

Graph shift regularization is a new and effective graph-based semi-supervised classification method, but its performance is closely related to the representation graphs. Since directed graphs can convey more information about the relationship between vertices than undirected graphs, an intelligent method called graph shift regularization with directed graphs (GSR-D) is presented for fault diagnosis of rolling bearings. For greatly improving the diagnosis performance of GSR-D, a directed and weighted k-nearest neighbor graph is first constructed by treating each sample (i.e., each vibration signal segment) as a vertex, in which the similarity between samples is measured by cosine distance instead of the commonly used Euclidean distance, and the edge weights are also defined by cosine distance instead of the commonly used heat kernel. Then, the labels of samples are considered as the graph signals indexed by the vertices of the representation graph. Finally, the states of unlabeled samples are predicted by finding a graph signal that has minimal total variation and satisfies the constraint given by labeled samples as much as possible. Experimental results indicate that GSR-D is better and more stable than the standard convolutional neural network and support vector machine in rolling bearing fault diagnosis, and GSR-D only has two tuning parameters with certain robustness.     

A graph-based generic type system for object-oriented programs

We present a graph-basedmodel of a generic type system for an OO language. The type system supports the features of recursive types, generics and interfaces, which are commonly found in modern OO languages such as Java. In the classical graph theory, we define type graphs, instantiation graphs and conjunction graphs that naturally illustrate the relations among types, generics and interfaces within complex OO programs. The model employs a combination of nominal and anonymous nodes to represent respectively types that are identified by names and structures, and defines graph-based relations and operations on types including equivalence, subtyping, conjunction and instantiation. Algorithms based on the graph structures are designed for the implementation of the type system. We believe that this type system is important for the development of a graph-based logical foundation of a formal method for verification of and reasoning about OO programs.     

ArA*summarizer: An Arabic text summarization system based on subtopic segmentation and using an A* algorithm for reduction

Automatic text summarization is a field situated at the intersection of natural language processing and information retrieval. Its main objective is to automatically produce a condensed representative form of documents. This paper presents ArA*summarizer, an automatic system for Arabic single document summarization. The system is based on an unsupervised hybrid approach that combines statistical, cluster-based, and graph-based techniques. The main idea is to divide text into subtopics then select the most relevant sentences in the most relevant subtopics. The selection process is done by an A* algorithm executed on a graph representing the different lexical–semantic relationships between sentences. Experimentation is conducted on Essex Arabic summaries corpus and using recall-oriented understudy for gisting evaluation, automatic summarization engineering, merged model graphs, and n-gram graph powered evaluation via regression evaluation metrics. The evaluation results showed the good performance of our system compared with existing works.     

Hyperspectral image classification using graph-based wavelet transform

ABSTRACT

Graph-based methods are developed to efficiently extract data information. In particular, these methods are adopted for high-dimensional data classification by exploiting information residing on weighted graphs. In this paper, we propose a new hyperspectral texture classifier based on graph-based wavelet transform. This recent graph transform allows extracting textural features from a constructed weighted graph using sparse representative pixels of hyperspectral image. Different measurements of spectral similarity between representative pixels are tested to decorrelate close pixels and improve the classification precision. To achieve the hyperspectral texture classification, Support Vector Machine is applied on spectral graph wavelet coefficients. Experimental results obtained by applying the proposed approach on Airborne Visible/Infrared Imaging Spectrometer (AVIRIS) and Reflective Optics System Imaging Spectrometer (ROSIS) datasets provide good accuracy which could exceed 98.7%. Compared to other famous classification methods as conventional deep learning-based methods, the proposed method achieves better classification performance. Results have shown the effectiveness of the method in terms of robustness and accuracy.     

Hard examples for the bounded depth Frege proof system

We prove exponential lower bounds on the size of a bounded depth Frege proof of a Tseitin graph-based contradiction, whenever the underlying graph is an expander. This is the first example of a contradiction, naturally formalized as a 3-CNF, that has no short bounded depth Frege proofs. Previously, lower bounds of this type were known only for the pigeonhole principle and for Tseitin contradictions based on complete graphs.Our proof is a novel reduction of a Tseitin formula of an expander graph to the pigeonhole principle, in a manner resembling that done by Fu and Urquhart for complete graphs.In the proof we introduce a general method for removing extension variables without significantly increasing the proof size, which may be interesting in its own right.