Comparing large graphs efficiently by margins of feature vectors

Measuring the structural similarity of graphs is a challenging and outstanding problem. Most of the classical approaches of the so-called exact graph matching methods are based on graph or subgraph isomorphic relations of the underlying graphs. In contrast to these methods in this paper we introduce a novel approach to measure the structural similarity of directed and undirected graphs that is mainly based on margins of feature vectors representing graphs. We introduce novel graph similarity and dissimilarity measures, provide some properties and analyze their algorithmic complexity. We find that the computational complexity of our measures is polynomial in the graph size and, hence, significantly better than classical methods from, e.g. exact graph matching which are NP-complete. Numerically, we provide some examples of our measure and compare the results with the well-known graph edit distance. (c) 2006 Elsevier Inc. All rights reserved.

Max separation clustering for feature extraction from Optical Emission Spectroscopy Data

This paper proposes max separation clustering (MSC), a new non-hierarchical clustering method used for feature extraction from optical emission spectroscopy (OES) data for plasma etch process control applications. OES data is high dimensional and inherently highly redundant with the result that it is difficult if not impossible to recognize useful features and key variables by direct visualization. MSC is developed for clustering variables with distinctive patterns and providing effective pattern representation by a small number of representative variables. The relationship between signal-to-noise ratio (SNR) and clustering performance is highlighted, leading to a requirement that low SNR signals be removed before applying MSC. Experimental results on industrial OES data show that MSC with low SNR signal removal produces effective summarization of the dominant patterns in the data.

SVM Training Phase Reduction Using Dataset Feature Filtering for Malware Detection

N-gram analysis is an approach that investigates the structure of a program using bytes, characters, or text strings. A key issue with N-gram analysis is feature selection amidst the explosion of features that occurs when N is increased. The experiments within this paper represent programs as operational code (opcode) density histograms gained through dynamic analysis. A support vector machine is used to create a reference model, which is used to evaluate two methods of feature reduction, which are 'area of intersect' and 'subspace analysis using eigenvectors.' The findings show that the relationships between features are complex and simple statistics filtering approaches do not provide a viable approach. However, eigenvector subspace analysis produces a suitable filter.

Developing Approaches for Solving a Telecommunications Feature Subscription Problem

Call control features (e.g., call-divert, voice-mail) are primitive options to which users can subscribe off-line to personalise their service. The configuration of a feature subscription involves choosing and sequencing features from a catalogue and is subject to constraints that prevent undesirable feature interactions at run-time. When the subscription requested by a user is inconsistent, one problem is to find an optimal relaxation, which is a generalisation of the feedback vertex set problem on directed graphs, and thus it is an NP-hard task. We present several constraint programming formulations of the problem. We also present formulations using partial weighted maximum Boolean satisfiability and mixed integer linear programming. We study all these formulations by experimentally comparing them on a variety of randomly generated instances of the feature subscription problem.

Quantitative structure-toxicity relationships for chlorophenols to bioluminescent lux-marked bacteria using atom-based semi-empirical molecular-orbital descriptors

Literature data on the toxicity of chlorophenols for three luminescent bacteria (Vibrio fischeri, and the lux-marked Pseudomonas fluorescens 10586s pUCD607 and Burkholderia spp. RASC c2 (Tn4431)) have been analyzed in relation to a set of computed molecular physico-chemical properties. The quantitative structure-toxicity relationships of the compounds in each species showed marked differences when based upon semi-empirical molecular-orbital molecular and atom based properties. For mono-, di- and tri-chlorophenols multiple linear regression analysis of V. fischeri toxicity showed a good correlation with the solvent accessible surface area and the charge on the oxygen atom. This correlation successfully predicted the toxicity of the heavily chlorinated phenols, suggesting in V. fischeri only one overall mechanism is present for all chlorophenols. Good correlations were also found for RASC c2 with molecular properties, such as the surface area and the nucleophilic super-delocalizability of the oxygen. In contrast the best QSTR for P. fluorescens contained the 2nd order connectivity index and ELUMO suggesting a different, more reactive mechanism. Cross-species correlations were examined, and between V. fischeri and RASC c2 the inclusion of the minimum value of the nucleophilic susceptibility on the ring carbons produced good results. Poorer correlations were found with P. fluorescens highlighting the relative similarity of V. fischeri and RASC c2, in contrast to that of P. fluorescens.