conference paper published yes Clemens Damke author 481920000-0002-0455-0048 Vitaly Melnikov author 58747 Eyke Hüllermeier author 48129 SinnoJialin Pan editor MasashiSugiyama editor 355 department Asian Conference on Machine Learning 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. https://ris.uni-paderborn.de/download/19953/19954/damke20.pdf application/pdfno https://ris.uni-paderborn.de/download/19953/19955/damke20-supp.pdf application/pdfno PMLR2020Bangkok, Thailand eng graph neural networksWeisfeiler-Lehman testcycle detection 2007.00346 12949-64 C. Damke, V. Melnikov, E. Hüllermeier, in: S. Jialin Pan, M. Sugiyama (Eds.), Proceedings of the 12th Asian Conference on Machine Learning (ACML 2020), PMLR, Bangkok, Thailand, 2020, pp. 49–64. Damke, Clemens, et al. “A Novel Higher-Order Weisfeiler-Lehman Graph Convolution.” <i>Proceedings of the 12th Asian Conference on Machine Learning (ACML 2020)</i>, edited by Sinno Jialin Pan and Masashi Sugiyama, vol. 129, PMLR, 2020, pp. 49–64. @inproceedings{Damke_Melnikov_Hüllermeier_2020, place={Bangkok, Thailand}, series={Proceedings of Machine Learning Research}, title={A Novel Higher-order Weisfeiler-Lehman Graph Convolution}, volume={129}, booktitle={Proceedings of the 12th Asian Conference on Machine Learning (ACML 2020)}, publisher={PMLR}, author={Damke, Clemens and Melnikov, Vitaly and Hüllermeier, Eyke}, editor={Jialin Pan, Sinno and Sugiyama, MasashiEditors}, year={2020}, pages={49–64}, collection={Proceedings of Machine Learning Research} } Damke, C., Melnikov, V., &#38; Hüllermeier, E. (2020). A Novel Higher-order Weisfeiler-Lehman Graph Convolution. In S. Jialin Pan &#38; M. Sugiyama (Eds.), <i>Proceedings of the 12th Asian Conference on Machine Learning (ACML 2020)</i> (Vol. 129, pp. 49–64). Bangkok, Thailand: PMLR. Damke C, Melnikov V, Hüllermeier E. A Novel Higher-order Weisfeiler-Lehman Graph Convolution. In: Jialin Pan S, Sugiyama M, eds. <i>Proceedings of the 12th Asian Conference on Machine Learning (ACML 2020)</i>. Vol 129. Proceedings of Machine Learning Research. Bangkok, Thailand: PMLR; 2020:49-64. C. Damke, V. Melnikov, and E. Hüllermeier, “A Novel Higher-order Weisfeiler-Lehman Graph Convolution,” in <i>Proceedings of the 12th Asian Conference on Machine Learning (ACML 2020)</i>, Bangkok, Thailand, 2020, vol. 129, pp. 49–64. Damke, Clemens, Vitaly Melnikov, and Eyke Hüllermeier. “A Novel Higher-Order Weisfeiler-Lehman Graph Convolution.” In <i>Proceedings of the 12th Asian Conference on Machine Learning (ACML 2020)</i>, edited by Sinno Jialin Pan and Masashi Sugiyama, 129:49–64. Proceedings of Machine Learning Research. Bangkok, Thailand: PMLR, 2020. 199532020-10-08T10:48:38Z2022-01-06T06:54:17Z