Graph Kernels via Functional Embedding
We propose a representation of graph as a functional object derived from the power iteration of the underlying adjacency matrix. The proposed functional representation is a graph invariant, i.e., the functional remains unchanged under any reordering of the vertices. This property eliminates the difficulty of handling exponentially many isomorphic forms. Bhattacharyya kernel constructed between these functionals significantly outperforms the state-of-the-art graph kernels on 3 out of the 4 standard benchmark graph classification datasets, demonstrating the superiority of our approach. The proposed methodology is simple and runs in time linear in the number of edges, which makes our kernel more efficient and scalable compared to many widely adopted graph kernels with running time cubic in the number of vertices.
Code (0)
등록된 구현이 없습니다.
Tasks
General ClassificationGraph ClassificationSimilar Papers 제목 키워드 기반
WILTing Trees: Interpreting the Distance Between MPNN Embeddings
We investigate the distance function learned by message passing neural networks (MPNNs) in specific tasks, aiming to capture the functional distance between prediction targets that MPNNs implicitly learn. This contrasts …
Scalable Global Alignment Graph Kernel Using Random Features: From Node Embedding to Graph Embedding
Graph kernels are widely used for measuring the similarity between graphs. Many existing graph kernels, which focus on local patterns within graphs rather than their global properties, suffer from significant structure i…
Graph ClassificationGraph EmbeddingFrom Node Embedding to Graph Embedding: Scalable Global Graph Kernel via Random Features
Graph kernels are one of the most important methods for graph data analysis and have been successfully applied in diverse applications. We can generally categorize existing graph kernels into two groups: kernels based on…
Graph EmbeddingReproducing Kernel Hilbert Space, Mercer's Theorem, Eigenfunctions, Nyström Method, and Use of Kernels in Machine Learning: Tutorial and Survey
This is a tutorial and survey paper on kernels, kernel methods, and related fields. We start with reviewing the history of kernels in functional analysis and machine learning. Then, Mercer kernel, Hilbert and Banach spac…
BIG-bench Machine LearningDimensionality ReductionLow-Rank Matrix CompletionConvD: Attention Enhanced Dynamic Convolutional Embeddings for Knowledge Graph Completion
Knowledge graphs generally suffer from incompleteness, which can be alleviated by completing the missing information. Deep knowledge convolutional embedding models based on neural networks are currently popular methods f…
Entity EmbeddingsKnowledge Graph CompletionKnowledge GraphsRelation