AERK: Aligned Entropic Reproducing Kernels through Continuous-time Quantum Walks

• URL: http://arxiv.org/abs/2303.03396v1
• Date: Sat, 4 Mar 2023 16:48:39 GMT
• Title: AERK: Aligned Entropic Reproducing Kernels through Continuous-time Quantum Walks
• Authors: Lixin Cui, Ming Li, Yue Wang, Lu Bai, Edwin R. Hancock
• Abstract summary: We develop an Aligned Entropic Reproducing Kernel (AERK) for graph classification. For pairwise graphs, the proposed AERK kernel is defined by computing a reproducing kernel based similarity between the quantum Shannon entropies of their each pair of aligned vertices. The experimental evaluation on standard graph datasets demonstrates that the proposed AERK kernel is able to outperform state-of-the-art graph kernels for graph classification tasks.
• Score: 17.95088104970343
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we develop an Aligned Entropic Reproducing Kernel (AERK) for graph classification. We commence by performing the Continuous-time Quantum Walk (CTQW) on each graph structure, and computing the Averaged Mixing Matrix (AMM) to describe how the CTQW visit all vertices from a starting vertex. More specifically, we show how this AMM matrix allows us to compute a quantum Shannon entropy for each vertex of a graph. For pairwise graphs, the proposed AERK kernel is defined by computing a reproducing kernel based similarity between the quantum Shannon entropies of their each pair of aligned vertices. The analysis of theoretical properties reveals that the proposed AERK kernel cannot only address the shortcoming of neglecting the structural correspondence information between graphs arising in most existing R-convolution graph kernels, but also overcome the problem of neglecting the structural differences between pairs of aligned vertices arising in existing vertex-based matching kernels. Moreover, unlike existing classical graph kernels that only focus on the global or local structural information of graphs, the proposed AERK kernel can simultaneously capture both global and local structural information through the quantum Shannon entropies, reflecting more precise kernel based similarity measures between pairs of graphs. The above theoretical properties explain the effectiveness of the proposed kernel. The experimental evaluation on standard graph datasets demonstrates that the proposed AERK kernel is able to outperform state-of-the-art graph kernels for graph classification tasks.

Related papers

• LSEnet: Lorentz Structural Entropy Neural Network for Deep Graph Clustering [59.89626219328127]
  Graph clustering is a fundamental problem in machine learning. Deep learning methods achieve the state-of-the-art results in recent years, but they still cannot work without predefined cluster numbers. We propose to address this problem from a fresh perspective of graph information theory.
  arXiv  Detail & Related papers  (2024-05-20T05:46:41Z)
• Deep Hierarchical Graph Alignment Kernels [16.574634620245487]
  We introduce Deep Hierarchical Graph Alignment Kernels (DHGAK) to resolve this problem. Specifically, the relational substructures are hierarchically aligned to cluster distributions in their deep embedding space. DHGAK is positive semi-definite and has linear separability in the Reproducing Kernel Hilbert Space.
  arXiv  Detail & Related papers  (2024-05-09T05:08:30Z)
• QESK: Quantum-based Entropic Subtree Kernels for Graph Classification [11.51839867040302]
  We propose a novel graph kernel, namely the Quantum-based Entropic Subtree Kernel (QESK) for Graph Classification. We show how this AMM matrix can be employed to compute a series of entropic subtree representations associated with the classical Weisfeiler-Lehman (WL) algorithm. We show that the proposed QESK kernel can significantly outperform state-of-the-art graph kernels and graph deep learning methods for graph classification problems.
  arXiv  Detail & Related papers  (2022-12-10T07:10:03Z)
• HAQJSK: Hierarchical-Aligned Quantum Jensen-Shannon Kernels for Graph Classification [17.95088104970343]
  We propose a family of novel quantum kernels, namely the Hierarchical Aligned Quantum Jensen-Shannon Kernels (HAQJSK) We show that the proposed HAQJSK kernels reflect richer intrinsic global graph characteristics in terms of the Continuous-Time Quantum Walk (CTQW) Unlike the previous Quantum Jensen-Shannon Kernels associated with the QJSD and the CTQW, the proposed HAQJSK kernels can simultaneously guarantee the properties of permutation invariant and positive definiteness.
  arXiv  Detail & Related papers  (2022-11-05T13:35:04Z)
• Graph Kernel Neural Networks [53.91024360329517]
  We propose to use graph kernels, i.e. kernel functions that compute an inner product on graphs, to extend the standard convolution operator to the graph domain. This allows us to define an entirely structural model that does not require computing the embedding of the input graph. Our architecture allows to plug-in any type of graph kernels and has the added benefit of providing some interpretability.
  arXiv  Detail & Related papers  (2021-12-14T14:48:08Z)
• Non-separable Spatio-temporal Graph Kernels via SPDEs [90.62347738138594]
  We provide graph kernels for principled-temporal modelling on graphs. By providing novel tools for modelling on graphs, we outperform pre-existing graph kernels in real-world applications.
  arXiv  Detail & Related papers  (2021-11-16T14:53:19Z)
• Neighborhood Preserving Kernels for Attributed Graphs [0.9176056742068812]
  We describe the design of a reproducing kernel suitable for attributed graphs. The similarity between the two graphs is defined based on the neighborhood information of the graph nodes. By incorporating the proposed kernel on support vector machines we analyzed the real-world data sets.
  arXiv  Detail & Related papers  (2020-10-13T09:58:50Z)
• Graph Neural Networks with Composite Kernels [60.81504431653264]
  We re-interpret node aggregation from the perspective of kernel weighting. We present a framework to consider feature similarity in an aggregation scheme. We propose feature aggregation as the composition of the original neighbor-based kernel and a learnable kernel to encode feature similarities in a feature space.
  arXiv  Detail & Related papers  (2020-05-16T04:44:29Z)
• Embedding Graph Auto-Encoder for Graph Clustering [90.8576971748142]
  Graph auto-encoder (GAE) models are based on semi-supervised graph convolution networks (GCN) We design a specific GAE-based model for graph clustering to be consistent with the theory, namely Embedding Graph Auto-Encoder (EGAE) EGAE consists of one encoder and dual decoders.
  arXiv  Detail & Related papers  (2020-02-20T09:53:28Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)
• A Hierarchical Transitive-Aligned Graph Kernel for Un-attributed Graphs [11.51839867040302]
  We develop a new graph kernel, namely the Hierarchical Transitive-Aligned kernel, by transitively aligning the vertices between graphs. The proposed kernel can outperform state-of-the-art graph kernels on standard graph-based datasets in terms of the classification accuracy.
  arXiv  Detail & Related papers  (2020-02-08T11:46:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.