SYNTOLOGY HomeExplorerAtlasCodeMethodologyAboutDevelopersFeedPricing
Paper · 2403.03880 · NeurIPS · 2024

Almost Surely Asymptotically Constant Graph Neural Networks

Ben Finkelshtein, Sam Adam-Day, Michael Benedikt İsmail, İlkan Ceylan

arXiv · PDF · Open in the Atlas

Code that ran

We have not lifted any functions out of this paper's repositories yet, so there is nothing we have run. The repositories linked to it are listed below.

Repositories linked to this paper

Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.

Abstract

We present a new angle on the expressive power of graph neural networks (GNNs) by studying how the predictions of real-valued GNN classifiers, such as those classifying graphs probabilistically, evolve as we apply them on larger graphs drawn from some random graph model. We show that the output converges to a constant function, which upper-bounds what these classifiers can uniformly express. This strong convergence phenomenon applies to a very wide class of GNNs, including state of the art models, with aggregates including mean and the attention-based mechanism of graph transformers. Our results apply to a broad class of random graph models, including sparse and dense variants of the Erdős-Rényi model, the stochastic block model, and the Barabási-Albert model. We empirically validate these findings, observing that the convergence phenomenon appears not only on random graphs but also on some real-world graphs.

For agents

The same record, over MCP at https://syntology.ai/mcp:

get_harvested_code_for_paper("2403.03880")
get_code_for_paper("2403.03880")
have("2403.03880")

The run record, dated, one paper per request, free:

curl https://syntology.ai/api/ran/2403.03880.json

A badge for a README (the split and the date, never a ratio):

[![Syntology run record](https://syntology.ai/api/ran/2403.03880.svg)](https://syntology.ai/paper/2403.03880)

Connect an agent — have() is free.