Neighborhood Preserving Kernels for Attributed Graphs
- URL: http://arxiv.org/abs/2010.06261v1
- Date: Tue, 13 Oct 2020 09:58:50 GMT
- Title: Neighborhood Preserving Kernels for Attributed Graphs
- Authors: Asif Salim, Shiju. S. S, and Sumitra. S
- Abstract summary: 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.
- Score: 0.9176056742068812
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We describe the design of a reproducing kernel suitable for attributed
graphs, in which the similarity between the two graphs is defined based on the
neighborhood information of the graph nodes with the aid of a product graph
formulation. We represent the proposed kernel as the weighted sum of two other
kernels of which one is an R-convolution kernel that processes the attribute
information of the graph and the other is an optimal assignment kernel that
processes label information. They are formulated in such a way that the edges
processed as part of the kernel computation have the same neighborhood
properties and hence the kernel proposed makes a well-defined correspondence
between regions processed in graphs. These concepts are also extended to the
case of the shortest paths. We identified the state-of-the-art kernels that can
be mapped to such a neighborhood preserving framework. We found that the kernel
value of the argument graphs in each iteration of the Weisfeiler-Lehman color
refinement algorithm can be obtained recursively from the product graph
formulated in our method. By incorporating the proposed kernel on support
vector machines we analyzed the real-world data sets and it has shown superior
performance in comparison with that of the other state-of-the-art graph
kernels.
Related papers
- Towards Subgraph Isomorphism Counting with Graph Kernels [45.687427850611314]
Subgraph isomorphism is known as #P-complete and requires exponential time to find the accurate solution.
We pioneeringly investigate the potential in counting subgraph isomorphisms and explore the augmentation of kernel capability through various variants.
We present the results of extensive experiments to demonstrate the effectiveness of the enhanced graph kernels and discuss promising directions for future research.
arXiv Detail & Related papers (2024-05-13T06:33:06Z) - AERK: Aligned Entropic Reproducing Kernels through Continuous-time
Quantum Walks [17.95088104970343]
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.
arXiv Detail & Related papers (2023-03-04T16:48:39Z) - Transductive Kernels for Gaussian Processes on Graphs [7.542220697870243]
We present a novel kernel for graphs with node feature data for semi-supervised learning.
The kernel is derived from a regularization framework by treating the graph and feature data as two spaces.
We show how numerous kernel-based models on graphs are instances of our design.
arXiv Detail & Related papers (2022-11-28T14:00:50Z) - Graph Condensation via Receptive Field Distribution Matching [61.71711656856704]
This paper focuses on creating a small graph to represent the original graph, so that GNNs trained on the size-reduced graph can make accurate predictions.
We view the original graph as a distribution of receptive fields and aim to synthesize a small graph whose receptive fields share a similar distribution.
arXiv Detail & Related papers (2022-06-28T02:10:05Z) - 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) - Transport based Graph Kernels [30.541423115387097]
Graph kernel is a powerful tool measuring the similarity between graphs.
Most of the existing graph kernels focused on node labels or attributes and ignored graph hierarchical structure information.
We propose pyramid graph kernel based on optimal transport (OT)
We evaluate the proposed graph kernels on several benchmark classification tasks and compare their performance with the existing state-of-the-art graph kernels.
arXiv Detail & Related papers (2020-11-02T04:44:27Z) - Graph Pooling with Node Proximity for Hierarchical Representation
Learning [80.62181998314547]
We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology.
Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
arXiv Detail & Related papers (2020-06-19T13:09:44Z) - 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) - Wasserstein-based Graph Alignment [56.84964475441094]
We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph.
We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
arXiv Detail & Related papers (2020-03-12T22:31:59Z) - 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.