Predicting the Performance of Graph Convolutional Networks with Spectral Properties of the Graph Laplacian
This addresses the challenge of optimizing GCNs for researchers and practitioners by providing a predictive metric, though it is incremental as it builds on known spectral graph theory.
The paper tackles the problem of predicting Graph Convolutional Network (GCN) performance by using the Fiedler value (algebraic connectivity) of the graph Laplacian, showing empirically that it correlates with performance on tasks like node classification across synthetic and real datasets such as Cora, CiteSeer, and Polblogs.
A common observation in the Graph Convolutional Network (GCN) literature is that stacking GCN layers may or may not result in better performance on tasks like node classification and edge prediction. We have found empirically that a graph's algebraic connectivity, which is known as the Fiedler value, is a good predictor of GCN performance. Intuitively, graphs with similar Fiedler values have analogous structural properties, suggesting that the same filters and hyperparameters may yield similar results when used with GCNs, and that transfer learning may be more effective between graphs with similar algebraic connectivity. We explore this theoretically and empirically with experiments on synthetic and real graph data, including the Cora, CiteSeer and Polblogs datasets. We explore multiple ways of aggregating the Fiedler value for connected components in the graphs to arrive at a value for the entire graph, and show that it can be used to predict GCN performance. We also present theoretical arguments as to why the Fiedler value is a good predictor.