@inproceedings{
huang2023graph,
title={Graph Neural Networks Benefit from Structural Information Provably: A Feature Learning Perspective},
author={Wei Huang and Yuan Cao and Haonan Wang and Xin Cao and Taiji Suzuki},
booktitle={NeurIPS 2023 Workshop on Mathematics of Modern Machine Learning},
year={2023},
url={https://openreview.net/forum?id=zarvq21MVP}
}
Graph neural networks (GNNs) have shown remarkable capabilities in learning from graph-structured data, outperforming traditional multilayer perceptrons (MLPs) in numerous graph applications. Despite these advantages, there has been limited theoretical exploration into why GNNs are so effective, particularly from the perspective of feature learning. This study aims to address this gap by examining the role of graph convolution in feature learning theory under a specific data generative model. We undertake a comparative analysis of the optimization and generalization between two-layer graph convolutional networks (GCNs) and their convolutional neural network (CNN) counterparts. Our findings reveal that graph convolution significantly enhances the regime of low test error over CNNs. This highlights a substantial discrepancy between GNNs and MLPs in terms of generalization capacity, a conclusion further supported by our empirical simulations on both synthetic and real-world datasets.
Graph Neural Networks Benefit from Structural Information Provably: A Feature Learning Perspective
Wei Huang Yuan Cao Haonan Wang Xin Cao Taiji Suzuki