Heterogeneous Attributed Graph Learning via Neighborhood-Aware Star Kernels
This addresses a bottleneck in graph learning for domains like social networks and bioinformatics, though it appears incremental as an enhancement to existing kernel methods.
The paper tackled the problem of measuring similarity in attributed graphs with heterogeneous attributes by proposing the Neighborhood-Aware Star Kernel (NASK), which achieved superior performance over 16 state-of-the-art baselines on 15 benchmarks.
Attributed graphs, typically characterized by irregular topologies and a mix of numerical and categorical attributes, are ubiquitous in diverse domains such as social networks, bioinformatics, and cheminformatics. While graph kernels provide a principled framework for measuring graph similarity, existing kernel methods often struggle to simultaneously capture heterogeneous attribute semantics and neighborhood information in attributed graphs. In this work, we propose the Neighborhood-Aware Star Kernel (NASK), a novel graph kernel designed for attributed graph learning. NASK leverages an exponential transformation of the Gower similarity coefficient to jointly model numerical and categorical features efficiently, and employs star substructures enhanced by Weisfeiler-Lehman iterations to integrate multi-scale neighborhood structural information. We theoretically prove that NASK is positive definite, ensuring compatibility with kernel-based learning frameworks such as SVMs. Extensive experiments are conducted on eleven attributed and four large-scale real-world graph benchmarks. The results demonstrate that NASK consistently achieves superior performance over sixteen state-of-the-art baselines, including nine graph kernels and seven Graph Neural Networks.