Measuring graph similarity through continuous-time quantum walks and the quantum Jensen-Shannon divergence

In this paper we propose a quantum algorithm to measure the similarity between a pair of unattributed graphs. We design an experiment where the two graphs are merged by establishing a complete set of connections between their nodes and the resulting structure is probed through the evolution of continuous-time quantum walks. In order to analyze the behavior of the walks without causing wave function collapse, we base our analysis on the recently introduced quantum Jensen-Shannon divergence. In particular, we show that the divergence between the evolution of two suitably initialized quantum walks over this structure is maximum when the original pair of graphs is isomorphic. We also prove that under special conditions the divergence is minimum when the sets of eigenvalues of the Hamiltonians associated with the two original graphs have an empty intersection.

A quantum Jensen-Shannon graph kernel for unattributed graphs

In this paper, we use the quantum Jensen-Shannon divergence as a means of measuring the information theoretic dissimilarity of graphs and thus develop a novel graph kernel. In quantum mechanics, the quantum Jensen-Shannon divergence can be used to measure the dissimilarity of quantum systems specified in terms of their density matrices. We commence by computing the density matrix associated with a continuous-time quantum walk over each graph being compared. In particular, we adopt the closed form solution of the density matrix introduced in Rossi et al. (2013) [27,28] to reduce the computational complexity and to avoid the cumbersome task of simulating the quantum walk evolution explicitly. Next, we compare the mixed states represented by the density matrices using the quantum Jensen-Shannon divergence. With the quantum states for a pair of graphs described by their density matrices to hand, the quantum graph kernel between the pair of graphs is defined using the quantum Jensen-Shannon divergence between the graph density matrices. We evaluate the performance of our kernel on several standard graph datasets from both bioinformatics and computer vision. The experimental results demonstrate the effectiveness of the proposed quantum graph kernel.

A quantum Jensen-Shannon graph kernel using discrete-time quantum walks

In this paper, we develop a new graph kernel by using the quantum Jensen-Shannon divergence and the discrete-time quantum walk. To this end, we commence by performing a discrete-time quantum walk to compute a density matrix over each graph being compared. For a pair of graphs, we compare the mixed quantum states represented by their density matrices using the quantum Jensen-Shannon divergence. With the density matrices for a pair of graphs to hand, the quantum graph kernel between the pair of graphs is defined by exponentiating the negative quantum Jensen-Shannon divergence between the graph density matrices. We evaluate the performance of our kernel on several standard graph datasets, and demonstrate the effectiveness of the new kernel.

Attributed graph kernels using the Jensen-Tsallis q-differences

We propose a family of attributed graph kernels based on mutual information measures, i.e., the Jensen-Tsallis (JT) q-differences (for q  ∈ [1,2]) between probability distributions over the graphs. To this end, we first assign a probability to each vertex of the graph through a continuous-time quantum walk (CTQW). We then adopt the tree-index approach [1] to strengthen the original vertex labels, and we show how the CTQW can induce a probability distribution over these strengthened labels. We show that our JT kernel (for q  = 1) overcomes the shortcoming of discarding non-isomorphic substructures arising in the R-convolution kernels. Moreover, we prove that the proposed JT kernels generalize the Jensen-Shannon graph kernel [2] (for q = 1) and the classical subtree kernel [3] (for q = 2), respectively. Experimental evaluations demonstrate the effectiveness and efficiency of the JT kernels.

Characterizing graph symmetries through quantum Jensen-Shannon divergence

In this paper we investigate the connection between quantum walks and graph symmetries. We begin by designing an experiment that allows us to analyze the behavior of the quantum walks on the graph without causing the wave function collapse. To achieve this, we base our analysis on the recently introduced quantum Jensen-Shannon divergence. In particular, we show that the quantum Jensen-Shannon divergence between the evolution of two quantum walks with suitably defined initial states is maximum when the graph presents symmetries. Hence, we assign to each pair of nodes of the graph a value of the divergence, and we average over all pairs of nodes to characterize the degree of symmetry possessed by a graph. © 2013 American Physical Society.

A quantum Jensen-Shannon graph kernel using the continuous-time quantum walk

In this paper, we use the quantum Jensen-Shannon divergence as a means to establish the similarity between a pair of graphs and to develop a novel graph kernel. In quantum theory, the quantum Jensen-Shannon divergence is defined as a distance measure between quantum states. In order to compute the quantum Jensen-Shannon divergence between a pair of graphs, we first need to associate a density operator with each of them. Hence, we decide to simulate the evolution of a continuous-time quantum walk on each graph and we propose a way to associate a suitable quantum state with it. With the density operator of this quantum state to hand, the graph kernel is defined as a function of the quantum Jensen-Shannon divergence between the graph density operators. We evaluate the performance of our kernel on several standard graph datasets from bioinformatics. We use the Principle Component Analysis (PCA) on the kernel matrix to embed the graphs into a feature space for classification. The experimental results demonstrate the effectiveness of the proposed approach. © 2013 Springer-Verlag.

Attributed graph similarity from the quantum Jensen-Shannon divergence

One of the most fundamental problem that we face in the graph domain is that of establishing the similarity, or alternatively the distance, between graphs. In this paper, we address the problem of measuring the similarity between attributed graphs. In particular, we propose a novel way to measure the similarity through the evolution of a continuous-time quantum walk. Given a pair of graphs, we create a derived structure whose degree of symmetry is maximum when the original graphs are isomorphic, and where a subset of the edges is labeled with the similarity between the respective nodes. With this compositional structure to hand, we compute the density operators of the quantum systems representing the evolution of two suitably defined quantum walks. We define the similarity between the two original graphs as the quantum Jensen-Shannon divergence between these two density operators, and then we show how to build a novel kernel on attributed graphs based on the proposed similarity measure. We perform an extensive experimental evaluation both on synthetic and real-world data, which shows the effectiveness the proposed approach. © 2013 Springer-Verlag.

A stable graph-based representation for object recognition through high-order matching

Many Object recognition techniques perform some flavour of point pattern matching between a model and a scene. Such points are usually selected through a feature detection algorithm that is robust to a class of image transformations and a suitable descriptor is computed over them in order to get a reliable matching. Moreover, some approaches take an additional step by casting the correspondence problem into a matching between graphs defined over feature points. The motivation is that the relational model would add more discriminative power, however the overall effectiveness strongly depends on the ability to build a graph that is stable with respect to both changes in the object appearance and spatial distribution of interest points. In fact, widely used graph-based representations, have shown to suffer some limitations, especially with respect to changes in the Euclidean organization of the feature points. In this paper we introduce a technique to build relational structures over corner points that does not depend on the spatial distribution of the features. © 2012 ICPR Org Committee.

Supervised learning of graph structure

Graph-based representations have been used with considerable success in computer vision in the abstraction and recognition of object shape and scene structure. Despite this, the methodology available for learning structural representations from sets of training examples is relatively limited. In this paper we take a simple yet effective Bayesian approach to attributed graph learning. We present a naïve node-observation model, where we make the important assumption that the observation of each node and each edge is independent of the others, then we propose an EM-like approach to learn a mixture of these models and a Minimum Message Length criterion for components selection. Moreover, in order to avoid the bias that could arise with a single estimation of the node correspondences, we decide to estimate the sampling probability over all the possible matches. Finally we show the utility of the proposed approach on popular computer vision tasks such as 2D and 3D shape recognition. © 2011 Springer-Verlag.

Sobolev Type Decomposition of Paley-Wiener-Schwartz Space with Application to Sampling Theory

2000 Mathematics Subject Classification: 94A12, 94A20, 30D20, 41A05.

Stabilization of catalyst particles against sintering on oxide supports with high oxygen ion lability exemplified by Ir-catalyzed decomposition of N2O

Iridium nanoparticles deposited on a variety of surfaces exhibited thermal sintering characteristics that were very strongly correlated with the lability of lattice oxygen in the supporting oxide materials. Specifically, the higher the lability of oxygen ions in the support, the greater the resistance of the nanoparticles to sintering in an oxidative environment. Thus with γ-Al2O3 as the support, rapid and extensive sintering occurred. In striking contrast, when supported on gadolinia-ceria and alumina-ceria-zirconia composite, the Ir nanoparticles underwent negligible sintering. In keeping with this trend, the behavior found with yttria-stabilized zirconia was an intermediate between the two extremes. This resistance, or lack of resistance, to sintering is considered in terms of oxygen spillover from support to nanoparticles and discussed with respect to the alternative mechanisms of Ostwald ripening versus nanoparticle diffusion. Activity towards the decomposition of N2O, a reaction that displays pronounced sensitivity to catalyst particle size (large particles more active than small particles), was used to confirm that catalytic behavior was consistent with the independently measured sintering characteristics. It was found that the nanoparticle active phase was Ir oxide, which is metallic, possibly present as a capping layer. Moreover, observed turnover frequencies indicated that catalyst-support interactions were important in the cases of the sinter-resistant systems, an effect that may itself be linked to the phenomena that gave rise to materials with a strong resistance to nanoparticle sintering.

Wavelet packet decomposition-based fault diagnosis scheme for SRM drives with a single current sensor

Power converters are a key, but vulnerable component in switched reluctance motor (SRM) drives. In this paper, a new fault diagnosis scheme for SRM converters is proposed based on the wavelet packet decomposition (WPD) with a dc-link current sensor. Open- and short-circuit faults of the power switches in an asymmetrical half-bridge converter are analyzed in details. In order to obtain the fault signature from the phase currents, two pulse-width modulation signals with phase shift are injected into the lower-switches of the converter to extract the excitation current, and the WPD algorithm is then applied to the detected currents for fault diagnosis. Moreover, a discrete degree of the wavelet packet node energy is chosen as the fault coefficient. The converter faults can be diagnosed and located directly by determining the changes in the discrete degree from the detected currents. The proposed scheme requires only one current sensor in the dc link, while conventional methods need one sensor for each phase or additional detection circuits. The experimental results on a 750-W three-phase SRM are presented to confirm the effectiveness of the proposed fault diagnosis scheme.

Photocatalytic decomposition of organophosphonates and fluorophenols in irradiated titanium dioxide suspensions

Dimethyl methyl phosphonate (DMMP), diethyl methyl phosphonate (DEMP), and fluorophenols undergo rapid decomposition upon TiO$\sb2$ catalyzed photooxidation in air saturated aqueous solution. The degradation rates of DMMP were determined over a range of temperatures, under solar and artificial irradiation with and without simultaneous sonication. Solar illumination is effective for the degradation and the use of low energy of sonication increases the rate of mineralization. The surface area and the type of TiO$\sb2$ dramatically affect the photoactivity of the catalyst. A number of intermediate products are formed and ultimately oxidized to phosphate and carbon dioxide. Possible reaction mechanisms and pathways for DMMP and DEMP are proposed. The Langmuir-Hinshelwood kinetic parameters for the photocatalysis of fluorophenols suggest modestly different reactivity for each isomer. The adsorption constant is largest for the ortho isomer consistent with the adsorption onto TiO$\sb2$ through both hydroxyl and fluoride groups to form a chelated type structure. ^

Correlation of detector dog alerts to cocaine decomposition products found in illicit forensic specimens

The volatile chemicals which comprise the odor of the illicit drug cocaine have been analyzed by adsorption onto activated charcoal followed by solvent elution and GC/MS analysis. A series of field tests have been performed to determine the dominant odor compound to which dogs alert. All of our data to date indicate that the dominant odor is due to the presence of methyl benzoate which is associated with the cocaine, rather than the cocaine itself. When methyl benzoate and cocaine are spiked onto U.S. currency, the threshold level of methyl benzoate required for a canine to signal an alert is typically 1-10 $\mu$g. Humans have been shown to have a sensitivity similar to dogs for methyl benzoate but with poorer selectivity/reliability. The dominant decomposition pathway for cocaine has been evaluated at elevated temperatures (up to 280$\sp\circ$C). Benzoic acid, but no detectable methyl benzoate, is formed. Solvent extraction and SFE were used to study the recovery of cocaine from U.S. currency. The amount of cocaine which could be recovered was found to decrease with time. ^