English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Recent work shows that the expressive power of Graph Neural Networks (GNNs)in distinguishing non-isomorphic graphs is exactly the same as that of theWeisfeiler-Lehman (WL) graph test. In particular, they show that the WL testcan be simulated by GNNs. However, those simulations involve neural networksfor the 'combine' function of size polynomial or even exponential in the numberof graph nodes $n$, as well as feature vectors of length linear in $n$.  We present an improved simulation of the WL test on GNNs with\emph{exponentially} lower complexity. In particular, the neural networkimplementing the combine function in each node has only a polylogarithmicnumber of parameters in $n$, and the feature vectors exchanged by the nodes ofGNN consists of only $O(\log n)$ bits. We also give logarithmic lower boundsfor the feature vector length and the size of the neural networks, showing the(near)-optimality of our construction.

Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks