Neighborhood Preserving Kernels for Attributed Graphs

Area of Science:

• Graph Machine Learning
• Kernel Methods
• Data Mining

Background:

• Attributed graphs contain vector information and discrete labels on nodes/edges.
• Graph kernels are crucial for comparing graph structures in machine learning.
• Existing methods may not fully capture neighborhood information in attributed graphs.

Purpose of the Study:

• To design a novel reproducing kernel for attributed graphs.
• To define graph similarity based on neighborhood information using product graphs.
• To improve performance in graph classification tasks.

Main Methods:

• Formulated a kernel as a weighted sum of an R-convolution kernel (for attributes) and an optimal assignment kernel (for labels).
• Utilized a product graph formulation to process neighborhood information.
• Extended concepts to shortest path analysis and integrated with Weisfeiler-Lehman algorithm.
• Incorporated the kernel into Support Vector Machines (SVMs).

Main Results:

• The proposed kernel effectively processes both attribute and label information.
• Demonstrated a recursive relationship between the kernel and the Weisfeiler-Lehman color refinement algorithm.
• Achieved superior performance on real-world datasets compared to existing graph kernels.

Conclusions:

• The novel kernel provides a robust framework for analyzing attributed graphs.
• The product graph formulation enables effective neighborhood-aware comparisons.
• The method shows significant potential for advancing graph-based machine learning.