The Power of Graph Convolutional Networks to Distinguish Random Graph Models: Short Version
Graph convolutional networks (GCNs) are a widely used method for graph representation learning. We investigate the power of GCNs, as a function of their number of layers, to distinguish between different random graph models on the basis of the embeddings of their sample graphs. In particular, the graph models that we consider arise from graphons, which are the most general possible parameterizations of infinite exchangeable graph models and which are the central objects of study in the theory of dense graph limits. We exhibit an infinite class of graphons that are well-separated in terms of cut distance and are indistinguishable by a GCN with nonlinear activation functions coming from a certain broad class if its depth is at least logarithmic in the size of the sample graph. These results theoretically match empirical observations of several prior works. Finally, we show a converse result that for pairs of graphons satisfying a degree profile separation property, a very simple GCN architecture suffices for distinguishability. To prove our results, we exploit a connection to random walks on graphs.
Code (0)
등록된 구현이 없습니다.
Tasks
Graph Representation LearningRepresentation LearningMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Fundamental Limits of Deep Graph Convolutional Networks
Graph convolutional networks (GCNs) are a widely used method for graph representation learning. To elucidate the capabilities and limitations of GCNs, we investigate their power, as a function of their number of layers, …
Graph ClassificationGraph Representation LearningRepresentation LearningRandom Features Strengthen Graph Neural Networks
Graph neural networks (GNNs) are powerful machine learning models for various graph learning tasks. Recently, the limitations of the expressive power of various GNN models have been revealed. For example, GNNs cannot dis…
Graph LearningLet's Agree to Degree: Comparing Graph Convolutional Networks in the Message-Passing Framework
In this paper we cast neural networks defined on graphs as message-passing neural networks (MPNNs) in order to study the distinguishing power of different classes of such models. We are interested in whether certain arch…
On the Universality of Graph Neural Networks on Large Random Graphs
We study the approximation power of Graph Neural Networks (GNNs) on latent position random graphs. In the large graph limit, GNNs are known to converge to certain "continuous" models known as c-GNNs, which directly enabl…
Stochastic Block ModelAttacking Graph Neural Networks with Bit Flips: Weisfeiler and Lehman Go Indifferent
Prior attacks on graph neural networks have mostly focused on graph poisoning and evasion, neglecting the network's weights and biases. Traditional weight-based fault injection attacks, such as bit flip attacks used for …
Graph Neural NetworkGraph Property PredictionProperty Prediction