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

A hallmark of graph neural networks is their ability to distinguish theisomorphism class of their inputs. This study derives hardness results for theclassification variant of graph isomorphism in the message-passing model(MPNN). MPNN encompasses the majority of graph neural networks used today andis universal when nodes are given unique features. The analysis relies on theintroduced measure of communication capacity. Capacity measures how muchinformation the nodes of a network can exchange during the forward pass anddepends on the depth, message-size, global state, and width of thearchitecture. It is shown that the capacity of MPNN needs to grow linearly withthe number of nodes so that a network can distinguish trees and quadraticallyfor general connected graphs. The derived bounds concern both worst- andaverage-case behavior and apply to networks with/without unique features andadaptive architecture -- they are also up to two orders of magnitude tighterthan those given by simpler arguments. An empirical study involving 12 graphclassification tasks and 420 networks reveals strong alignment between actualperformance and theoretical predictions.

How hard is to distinguish graphs with graph neural networks?