Are Graph Convolutional Networks With Random Weights Feasible?
Are Graph Convolutional Networks With Random Weights Feasible?
复制标题
DOI：
10.1109/tpami.2022.3183143
复制
发表时间：
2023-03-01
影响因子：
23.6
通讯作者：
Wu, Xindong
中科院分区：
文献类型：
--
作者：
Huang, Changqin;Li, Ming;Wu, Xindong
图卷积网络（GCN）作为图神经网络的一个突出例子，因其在学习图上节点表示方面的强大能力而受到广泛关注。在采样和/或节点特征聚合方面有各种扩展，以进一步提高 GCN 在各个领域的性能、可扩展性和适用性。尽管如此，学习效率仍有进一步提高的空间，因为在每次训练迭代中使用完整数据集执行批量梯度下降（对于训练（普通）GCN 来说是不可避免的）对于大图来说并不是一个可行的选择。随机特征在加速大规模问题的训练阶段方面的良好潜力促使我们仔细考虑具有随机权重的 GCN 是否可行。为了从理论上和实证上研究这个问题，我们提出了一种称为随机权重图卷积网络（GCN-RW）的新模型，通过使用随机滤波器修改卷积层并同时使用正则化最小二乘损失调整学习目标。对模型的近似上限、结构复杂性、稳定性和泛化性进行了理论分析，并提供了严格的数学证明。 GCN-RW 的有效性和效率在多个基准数据集的半监督节点分类任务上得到了验证。实验结果表明，与一些最先进的方法相比，GCN-RW 可以以更少的训练时间成本实现更好或匹配的精度。
Graph Convolutional Networks (GCNs), as a prominent example of graph neural networks, are receiving extensive attention for their powerful capability in learning node representations on graphs. There are various extensions, either in sampling and/or node feature aggregation, to further improve GCNs' performance, scalability and applicability in various domains. Still, there is room for further improvements on learning efficiency because performing batch gradient descent using the full dataset for every training iteration, as unavoidable for training (vanilla) GCNs, is not a viable option for large graphs. The good potential of random features in speeding up the training phase in large-scale problems motivates us to consider carefully whether GCNs with random weights are feasible. To investigate theoretically and empirically this issue, we propose a novel model termed Graph Convolutional Networks with Random Weights (GCN-RW) by revising the convolutional layer with random filters and simultaneously adjusting the learning objective with regularized least squares loss. Theoretical analyses on the model's approximation upper bound, structure complexity, stability and generalization, are provided with rigorous mathematical proofs. The effectiveness and efficiency of GCN-RW are verified on semi-supervised node classification task with several benchmark datasets. Experimental results demonstrate that, in comparison with some state-of-the-art approaches, GCN-RW can achieve better or matched accuracies with less training time cost.