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

Graph convolutional networks (GCNs) are a widely used method for graphrepresentation learning. We investigate the power of GCNs, as a function oftheir number of layers, to distinguish between different random graph models onthe basis of the embeddings of their sample graphs. In particular, the graphmodels that we consider arise from graphons, which are the most generalpossible parameterizations of infinite exchangeable graph models and which arethe central objects of study in the theory of dense graph limits. We exhibit aninfinite class of graphons that are well-separated in terms of cut distance andare indistinguishable by a GCN with nonlinear activation functions coming froma certain broad class if its depth is at least logarithmic in the size of thesample graph. These results theoretically match empirical observations ofseveral prior works. Finally, we show a converse result that for pairs ofgraphons satisfying a degree profile separation property, a very simple GCNarchitecture suffices for distinguishability. To prove our results, we exploita connection to random walks on graphs.

The Power of Graph Convolutional Networks to Distinguish Random Graph Models: Short Version