Sharp Bounds for Poly-GNNs and the Effect of Graph Noise
We investigate the classification performance of graph neural networks with graph-polynomial features, poly-GNNs, on the problem of semi-supervised node classification. We analyze poly-GNNs under a general contextual stochastic block model (CSBM) by providing a sharp characterization of the rate of separation between classes in their output node representations. A question of interest is whether this rate depends on the depth of the network $k$, i.e., whether deeper networks can achieve a faster separation? We provide a negative answer to this question: for a sufficiently large graph, a depth $k > 1$ poly-GNN exhibits the same rate of separation as a depth $k=1$ counterpart. Our analysis highlights and quantifies the impact of ``graph noise'' in deep GNNs and shows how noise in the graph structure can dominate other sources of signal in the graph, negating any benefit further aggregation provides. Our analysis also reveals subtle differences between even and odd-layered GNNs in how the feature noise propagates.
Code (0)
등록된 구현이 없습니다.
Tasks
Node ClassificationStochastic Block ModelSimilar Papers 제목 키워드 기반
On the under-reaching phenomenon in message-passing neural PDE solvers: revisiting the CFL condition
This paper proposes sharp lower bounds for the number of message passing iterations required in graph neural networks (GNNs) when solving partial differential equations (PDE). This significantly reduces the need for exha…
Beyond GNNs: A Sample Efficient Architecture for Graph Problems
Despite their popularity in learning problems over graph structured data, existing Graph Neural Networks (GNNs) have inherent limitations for fundamental graph problems such as shortest paths, $k$-connectivity, minimum s…
Generalization BoundsGeneralization Bounds for Spectral GNNs via Fourier Domain Analysis
Spectral graph neural networks learn graph filters, but their behavior with increasing depth and polynomial order is not well understood. We analyze these models in the graph Fourier domain, where each layer becomes an e…
VC dimension of Graph Neural Networks with Pfaffian activation functions
Graph Neural Networks (GNNs) have emerged in recent years as a powerful tool to learn tasks across a wide range of graph domains in a data-driven fashion; based on a message passing mechanism, GNNs have gained increasing…
Ego-GNNs: Exploiting Ego Structures in Graph Neural Networks
Graph neural networks (GNNs) have achieved remarkable success as a framework for deep learning on graph-structured data. However, GNNs are fundamentally limited by their tree-structured inductive bias: the WL-subtree ker…
Inductive BiasNode Classification