Faster Kernels for Graphs with Continuous Attributes via Hashing

While state-of-the-art kernels for graphs with discrete labels scale well to graphs with thousands of nodes, the few existing kernels for graphs with continuous attributes, unfortunately, do not scale well. To overcome this limitation, we present hash graph kernels, a general framework to derive kernels for graphs with continuous attributes from discrete ones. The idea is to iteratively turn continuous attributes into discrete labels using randomized hash functions. We illustrate hash graph kernels for the Weisfeiler-Lehman subtree kernel and for the shortest-path kernel. The resultingnovel graph kernels are shown to be, both, able to handle graphs with continuous attributes and scalable to large graphs and data sets. This is supported by our theoretical analysis and demonstrated by an extensive experimental evaluation.

• Publication year

  2016

• Venue

  Industrial Conference on Data Mining

• Publication date

  2016-10-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/ICDM.2016.0142arXiv 1610.00064
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Graph Invariant Kernels

  2015influential reference
• Explicit Versus Implicit Graph Feature Maps: A Computational Phase Transition for Walk Kernels

  2014cited by this paper
• Propagation kernels: efficient graph kernels from propagated information

  2014cited by this paper
• Scalable kernels for graphs with continuous attributes

  2013cited by this paper
• Subgraph Matching Kernels for Attributed Graphs

  2012cited by this paper
• Fast Random Walk Graph Kernel

  2012cited by this paper
• Weisfeiler-Lehman Graph Kernels

  2011cited by this paper
• LIBSVM: A library for support vector machines

  2011cited by this paper
• Efficient graphlet kernels for large graph comparison

  2009cited by this paper
• A Linear-Time Graph Kernel

  2009cited by this paper
• Nearest neighbor search : the old, the new, and the impossible

  2009cited by this paper
• Graph Kernels

  2008cited by this paper
• Image Classification with Segmentation Graph Kernels

  2007cited by this paper
• Random Features for Large-Scale Kernel Machines

  2007cited by this paper
• Training linear SVMs in linear time

  2006cited by this paper
• Shortest-path kernels on graphs

  2005cited by this paper
• Protein function prediction via graph kernels

  2005cited by this paper
• Cyclic pattern kernels for predictive graph mining

  2004cited by this paper
• Locality-sensitive hashing scheme based on p-stable distributions

  2004cited by this paper
• Extensions of marginalized graph kernels

  2004cited by this paper
• Marginalized Kernels Between Labeled Graphs

  2003cited by this paper
• On Graph Kernels: Hardness Results and Efficient Alternatives

  2003cited by this paper
• Design of experiments for the NIPS 2003 variable selection benchmark

  2003cited by this paper
• Expressivity versus efficiency of graph kernels

  2003cited by this paper
• Probability Inequalities for Sums of Bounded Random Variables

  1994cited by this paper

• Optimization-Free Graph Embedding via Distributional Kernel for Community Detection

  2026cites this paper
• Heterogeneous Graph Embedding Made More Practical

  2025cites this paper
• Hierarchical Abstracting Graph Kernel

  2025cites this paper
• A graph backdoor detection method for data collection scenarios

  2025influential citation
• Dual Boost-Driven Graph-Level Clustering Network

  2025cites this paper
• Rethinking the message passing for graph-level classification tasks in a category-based view

  2025cites this paper
• Rhomboid Tiling for Geometric Graph Deep Learning

  2025cites this paper
• Topology-aware Reinforcement Feature Space Reconstruction for Graph Data

  2024cites this paper
• Rethinking Graph Classification Problem in Presence of Isomorphism

  2024cites this paper
• Optimal Transport-Based Network Alignment: Graph Classification of Small Molecule Structure-Activity Relationships in Biology

  2024cites this paper
• WLPlan: Relational Features for Symbolic Planning

  2024cites this paper
• Graph Learning for Numeric Planning

  2024cites this paper
• Optimal Transport Based Graph Kernels for Drug Property Prediction

  2024cites this paper
• DPGAN: A Dual-Path Generative Adversarial Network for Missing Data Imputation in Graphs

  2024cites this paper
• Wasserstein Distance-Based Graph Kernel for Enhancing Drug Safety and Efficacy Prediction *

  2024cites this paper
• SNN-PDE: Learning Dynamic PDEs from Data with Simplicial Neural Networks

  2024cites this paper
• Descriptive Kernel Convolution Network with Improved Random Walk Kernel

  2024cites this paper
• Gaussian process regression with Sliced Wasserstein Weisfeiler-Lehman graph kernels

  2024cites this paper
• EMP: Effective Multidimensional Persistence for Graph Representation Learning

  2024cites this paper
• Tensor-view Topological Graph Neural Network

  2024cites this paper
• Towards Long-Tailed Recognition for Graph Classification via Collaborative Experts

  2023cites this paper
• A Systematic Approach to Universal Random Features in Graph Neural Networks

  2023cites this paper
• MPSketch: Message Passing Networks via Randomized Hashing for Efficient Attributed Network Embedding

  2023cites this paper
• RAHNet: Retrieval Augmented Hybrid Network for Long-tailed Graph Classification

  2023cites this paper
• Multi-proximity based embedding scheme for learning vector quantization-based classification of biochemical structured data

  2023cites this paper
• SCHash: Speedy Simplicial Complex Neural Networks via Randomized Hashing

  2023influential citation
• On Learning Embeddings at the Intersection of Communities and Roles

  2023cites this paper
• Multi-scale Wasserstein Shortest-path Filtration Kernels on Graphs

  2023cites this paper
• Data Imputation from the Perspective of Graph Dirichlet Energy

  2023cites this paper
• Topological Pooling on Graphs

  2023cites this paper
• Alzheimer's disease classification based on graph kernel SVMs constructed with 3D texture features extracted from MR images

  2022cites this paper
• Generating Counterfactual Hard Negative Samples for Graph Contrastive Learning

  2022influential citation
• SpeqNets: Sparsity-aware Permutation-equivariant Graph Networks

  2022cites this paper
• Taxonomy of Benchmarks in Graph Representation Learning

  2022cites this paper
• On a linear fused Gromov-Wasserstein distance for graph structured data

  2022cites this paper
• The PWLR Graph Representation: A Persistent Weisfeiler-Lehman scheme with Random Walks for Graph Classification

  2022influential citation
• GraphQNTK: Quantum Neural Tangent Kernel for Graph Data

  2022influential citation
• On Local Distributions in Graph Signal Processing

  2022cites this paper
• Investigating Transfer Learning in Graph Neural Networks

  2022cites this paper
• Handling Missing Data via Max-Entropy Regularized Graph Autoencoder

  2022cites this paper
• Metric Distribution to Vector: Constructing Data Representation via Broad-Scale Discrepancies

  2022cites this paper
• TopoAttn-Nets: Topological Attention in Graph Representation Learning

  2022cites this paper
• Gradual Weisfeiler-Leman: Slow and Steady Wins the Race

  2022cites this paper
• Filtration Curves for Graph Representation

  2021influential citation
• Color Refinement and Its Applications

  2021cites this paper
• DGSD: Distributed graph representation via graph statistical properties

  2021cites this paper
• Theoretically Improving Graph Neural Networks via Anonymous Walk Graph Kernels

  2021cites this paper
• Predicting Single-Substance Phase Diagrams: A Kernel Approach on Graph Representations of Molecules.

  2021cites this paper
• The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphs

  2021cites this paper
• Isolation Graph Kernel

  2021influential citation
• A Comparative Study of Marginalized Graph Kernel and Message-Passing Neural Network

  2021cites this paper
• A Regularized Wasserstein Framework for Graph Kernels

  2021cites this paper
• Unsupervised Large-Scale Social Network Alignment via Cross Network Embedding

  2021cites this paper
• Trainability for Universal GNNs Through Surgical Randomness

  2021cites this paper
• Weisfeiler and Leman go Machine Learning: The Story so far

  2021influential citation
• Kernel-Based Structural-Temporal Cascade Learning for Popularity Prediction

  2021cites this paper
• A systematic approach to random data augmentation on graph neural networks

  2021cites this paper
• A Principled Approach to Analyze Expressiveness and Accuracy of Graph Neural Networks

  2020cites this paper
• Distance metric learning for graph structured data

  2020cites this paper
• Learning Deep Graph Representations via Convolutional Neural Networks

  2020influential citation
• CommPOOL: An Interpretable Graph Pooling Framework for Hierarchical Graph Representation Learning

  2020cites this paper
• Tree++: Truncated Tree Based Graph Kernels

  2020influential citation
• Graph Kernels: State-of-the-Art and Future Challenges

  2020influential citation
• Unsupervised Structural Embedding Methods for Efficient Collective Network Mining

  2020cites this paper
• Transport based Graph Kernels

  2020cites this paper
• Neighborhood Preserving Kernels for Attributed Graphs

  2020cites this paper
• Towards Expressive Graph Representations for Graph Neural Networks

  2020cites this paper
• Network entropy using edge-based information functionals

  2020cites this paper
• Ordinal Pattern Kernel for Brain Connectivity Network Classification

  2020cites this paper
• Multi-view adaptive graph convolutions for graph classification

  2020influential citation
• TUDataset: A collection of benchmark datasets for learning with graphs

  2020cites this paper
• Hierarchical and Unsupervised Graph Representation Learning with Loukas's Coarsening

  2020cites this paper
• DeepMap: Learning Deep Representations for Graph Classification

  2020cites this paper
• word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data

  2020cites this paper
• Graph Pooling with Representativeness

  2020cites this paper
• A graph similarity for deep learning

  2020cites this paper
• Graph kernels based on linear patterns: Theoretical and experimental comparisons

  2019cites this paper
• Kernel Methods for Graph-structured Data Analysis

  2019cites this paper
• SPI-GCN: A Simple Permutation-Invariant Graph Convolutional Network

  2019cites this paper
• SAGE: SCALABLE ATTRIBUTED GRAPH EMBED-

  2019cites this paper
• Learning Structural Node Representations Using Graph Kernels

  2019cites this paper
• Understanding Isomorphism Bias in Graph Data Sets

  2019cites this paper
• Distribution of Node Embeddings as Multiresolution Features for Graphs

  2019cites this paper
• Machine learning approaches for drug virtual screening

  2019cites this paper
• Learning Interpretable Metric between Graphs: Convex Formulation and Computation with Graph Mining

  2019cites this paper
• Wasserstein Weisfeiler-Lehman Graph Kernels

  2019influential citation
• Graph Kernels: A Survey

  2019cites this paper
• Towards a practical k-dimensional Weisfeiler-Leman algorithm

  2019cites this paper
• A survey on graph kernels

  2019cites this paper
• RetGK: Graph Kernels based on Return Probabilities of Random Walks

  2018cites this paper
• A Property Testing Framework for the Theoretical Expressivity of Graph Kernels

  2018cites this paper
• Graph Classification with 2 D Convolutional Neural Networks

  2018cites this paper
• A Comprehensive Evaluation of Graph Kernels for Unattributed Graphs

  2018cites this paper
• Message Passing Graph Kernels

  2018cites this paper
• Recent Advances in Kernel-Based Graph Classification

  2017cites this paper
• A Unifying View of Explicit and Implicit Feature Maps for Structured Data: Systematic Studies of Graph Kernels

  2017influential citation
• Kernel based learning on hierarchical image representations : applications to remote sensing data classification. (Apprentissage à base de noyaux sur représentations d'images arborescentes : applications à la classification des images de télédétection)

  2017cites this paper
• Glocalized Weisfeiler-Lehman Graph Kernels: Global-Local Feature Maps of Graphs

  2017cites this paper
• Graph Classification with 2D Convolutional Neural Networks

  2017cites this paper
• A unifying view of explicit and implicit feature maps of graph kernels

  2017influential citation