1,404 research outputs found
Unfolding Kernel Embeddings of Graphs: Enhancing Class Separation through Manifold Learning
No full textIn this paper, we investigate the use of manifold learning techniques to enhance the separation properties of standard graph kernels. The idea stems from the observation that when we perform multidimensional scaling on the distance matrices extracted from the kernels, the resulting data tends to be clustered along a curve that wraps around the embedding space, a behavior that suggests that long range distances are not estimated accurately, resulting in an increased curvature of the embedding space. Hence, we propose to use a number of manifold learning techniques to compute a low-dimensional embedding of the graphs in an attempt to unfold the embedding manifold, and increase the class separation. We perform an extensive experimental evaluation on a number of standard graph datasets using the shortest-path (Borgwardt and Kriegel, 2005), graphlet (Shervashidze et al., 2009), random walk (Kashima et al., 2003) and Weisfeiler-Lehman (Shervashidze et al., 2011) kernels. We observe the most significant improvement in the case of the graphlet kernel, which fits with the observation that neglecting the locational information of the substructures leads to a stronger curvature of the embedding manifold. On the other hand, the Weisfeiler-Lehman kernel partially mitigates the locality problem by using the node labels information, and thus does not clearly benefit from the manifold learning. Interestingly, our experiments also show that the unfolding of the space seems to reduce the performance gap between the examined kernels
Measuring graph similarity through continuous-time quantum walks and the quantum Jensen-Shannon divergence
No full textIn 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
Open System Quantum Thermodynamics of Time Varying Graphs
No full textIn this article, we present a novel analysis of time-evolving networks, based on a thermodynamic representation of graph structure. We show how to characterize the evolution of time-varying complex networks by relating major structural changes to thermodynamic phase transitions. In particular, we derive expressions for a number of different thermodynamic quantities (specifically energy, entropy and temperature), which we use to describe the evolutionary behaviour of the network system over time. Since in the real world no system is truly closed and interactions with the environment are usually strong, we assume an open nature of the system. We adopt the Schrödinger picture as the dynamical representation of the quantum system over time. First, we compute the network entropy using a recent quantum mechanical representation of graph structure, connecting the graph Laplacian to a density operator. Then, we assume the system evolves according to the Schrödinger representation, but we allow for decoherence due to the interaction with the environment in a model akin to Environment-Induced Decoherence. We simplify the model by separating its dynamics into (a) an unknown time-dependent unitary evolution plus (b) an observation/interaction process, and this is the sole cause of the changes in the eigenvalues of the density matrix of the system. This allows us to obtain a measure of energy exchange with the environment through the estimation of the hidden time-varying Hamiltonian responsible for the unitary part of the evolution. Using the thermodynamic relationship between changes in energy, entropy, pressure and volume, we recover the thermodynamic temperature. We assess the utility of the method on real-world time-varying networks representing complex systems in the financial and biological domains. We also compare and contrast the different characterizations provided by the thermodynamic variables (energy, entropy, temperature and pressure). The study shows that the estimation of the time-varying energy operator strongly characterizes different states of a time-evolving system and successfully detects critical events occurring during network evolution
A Quantum Jensen-Shannon Graph Kernel for Unattributed Graphs
No full textIn 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
Node Centrality for Continuous-Time Quantum WalksStructural, Syntactic, and Statistical Pattern Recognition
No full textThe study of complex networks has recently attracted increasing interest because of the large variety of systems that can be modeled using graphs. A fundamental operation in the analysis of complex networks is that of measuring the centrality of a vertex. In this paper, we propose to measure vertex centrality using a continuous-time quantum walk. More specifically, we relate the importance of a vertex to the influence that its initial phase has on the interference patterns that emerge during the quantum walk evolution. To this end, we make use of the quantum Jensen-Shannon divergence between two suitably defined quantum states. We investigate how the importance varies as we change the initial state of the walk and the Hamiltonian of the system. We find that, for a suitable combination of the two, the importance of a vertex is almost linearly correlated with its degree. Finally, we evaluate the proposed measure on two commonly used networks
A Continuous-Time Quantum Walk Kernel for Unattributed Graphs
No full textKernel methods provide a way to apply a wide range of learning techniques to complex and structured data by shifting the representational problem from one of finding an embedding of the data to that of defining a positive semidefinite kernel. In this paper, we propose a novel kernel on unattributed graphs where the structure is characterized through the evolution of a continuous-time quantum walk. More precisely, given a pair of graphs, we create a derived structure whose degree of symmetry is maximum when the original graphs are isomorphic. With this new graph to hand, we compute the density operators of the quantum systems representing the evolutions of two suitably defined quantum walks. Finally, we define the kernel between the two original graphs as the quantum Jensen-Shannon divergence between these two density operators. The experimental evaluation shows the effectiveness of the proposed approach. © 2013 Springer-Verlag
- …
