2021-07-01-balcilar21a.md

title	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
Breaking the Limits of Message Passing Graph Neural Networks	Since the Message Passing (Graph) Neural Networks (MPNNs) have a linear complexity with respect to the number of nodes when applied to sparse graphs, they have been widely implemented and still raise a lot of interest even though their theoretical expressive power is limited to the first order Weisfeiler-Lehman test (1-WL). In this paper, we show that if the graph convolution supports are designed in spectral-domain by a non-linear custom function of eigenvalues and masked with an arbitrary large receptive field, the MPNN is theoretically more powerful than the 1-WL test and experimentally as powerful as a 3-WL existing models, while remaining spatially localized. Moreover, by designing custom filter functions, outputs can have various frequency components that allow the convolution process to learn different relationships between a given input graph signal and its associated properties. So far, the best 3-WL equivalent graph neural networks have a computational complexity in $\mathcal{O}(n^3)$ with memory usage in $\mathcal{O}(n^2)$, consider non-local update mechanism and do not provide the spectral richness of output profile. The proposed method overcomes all these aforementioned problems and reaches state-of-the-art results in many downstream tasks.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	balcilar21a	0	Breaking the Limits of Message Passing Graph Neural Networks	599	608	599-608	599	false	Balcilar, Muhammet and Heroux, Pierre and Gauzere, Benoit and Vasseur, Pascal and Adam, Sebastien and Honeine, Paul	given family Muhammet Balcilar given family Pierre Heroux given family Benoit Gauzere given family Pascal Vasseur given family Sebastien Adam given family Paul Honeine	2021-07-01		Proceedings of the 38th International Conference on Machine Learning	139	inproceedings	date-parts 2021 7 1	http://proceedings.mlr.press/v139/balcilar21a/balcilar21a.pdf	label link Supplementary PDF http://proceedings.mlr.press/v139/balcilar21a/balcilar21a-supp.pdf