A Novel Higher-order Weisfeiler-Lehman Graph Convolution

Clemens Damke, Vitalik Melnikov, Eyke Hüllermeier
Proceedings of The 12th Asian Conference on Machine Learning, PMLR 129:49-64, 2020.

Abstract

Current GNN architectures use a vertex neighborhood aggregation scheme, which limits their discriminative power to that of the 1-dimensional Weisfeiler-Lehman (WL) graph isomorphism test. Here, we propose a novel graph convolution operator that is based on the 2-dimensional WL test. We formally show that the resulting 2-WL-GNN architecture is more discriminative than existing GNN approaches. This theoretical result is complemented by experimental studies using synthetic and real data. On multiple common graph classification benchmarks, we demonstrate that the proposed model is competitive with state-of-the-art graph kernels and GNNs.

Cite this Paper

BibTeX
@InProceedings{pmlr-v129-damke20a, title = {A Novel Higher-order Weisfeiler-Lehman Graph Convolution}, author = {Damke, Clemens and Melnikov, Vitalik and H{\"u}llermeier, Eyke}, booktitle = {Proceedings of The 12th Asian Conference on Machine Learning}, pages = {49--64}, year = {2020}, editor = {Pan, Sinno Jialin and Sugiyama, Masashi}, volume = {129}, series = {Proceedings of Machine Learning Research}, month = {18--20 Nov}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v129/damke20a/damke20a.pdf}, url = {https://proceedings.mlr.press/v129/damke20a.html}, abstract = {Current GNN architectures use a vertex neighborhood aggregation scheme, which limits their discriminative power to that of the 1-dimensional Weisfeiler-Lehman (WL) graph isomorphism test. Here, we propose a novel graph convolution operator that is based on the 2-dimensional WL test. We formally show that the resulting 2-WL-GNN architecture is more discriminative than existing GNN approaches. This theoretical result is complemented by experimental studies using synthetic and real data. On multiple common graph classification benchmarks, we demonstrate that the proposed model is competitive with state-of-the-art graph kernels and GNNs.} }
Endnote
%0 Conference Paper %T A Novel Higher-order Weisfeiler-Lehman Graph Convolution %A Clemens Damke %A Vitalik Melnikov %A Eyke Hüllermeier %B Proceedings of The 12th Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Sinno Jialin Pan %E Masashi Sugiyama %F pmlr-v129-damke20a %I PMLR %P 49--64 %U https://proceedings.mlr.press/v129/damke20a.html %V 129 %X Current GNN architectures use a vertex neighborhood aggregation scheme, which limits their discriminative power to that of the 1-dimensional Weisfeiler-Lehman (WL) graph isomorphism test. Here, we propose a novel graph convolution operator that is based on the 2-dimensional WL test. We formally show that the resulting 2-WL-GNN architecture is more discriminative than existing GNN approaches. This theoretical result is complemented by experimental studies using synthetic and real data. On multiple common graph classification benchmarks, we demonstrate that the proposed model is competitive with state-of-the-art graph kernels and GNNs.
APA
Damke, C., Melnikov, V. & Hüllermeier, E.. (2020). A Novel Higher-order Weisfeiler-Lehman Graph Convolution. Proceedings of The 12th Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 129:49-64 Available from https://proceedings.mlr.press/v129/damke20a.html.

Related Material