Graph sparsification with graph convolutional networks
Graph sparsification with graph convolutional networks
复制标题
DOI：
10.1007/s41060-021-00288-8
复制
发表时间：
2021-10
影响因子：
2.4
通讯作者：
Jiayu Li;Tianyun Zhang;Hao Tian;Shengmin Jin;M. Fardad;R. Zafarani
中科院分区：
文献类型：
--
作者：
Jiayu Li;Tianyun Zhang;Hao Tian;Shengmin Jin;M. Fardad;R. Zafarani
图表在全球范围内以及科学和工程领域无处不在。一些强大的分类器被提出来对图中的节点进行分类，例如图卷积网络（GCN）。然而，随着图的大小不断增长，由于使用整个图，大图上的节点分类可能会耗费空间和时间。因此，提出了一些问题，特别是，是否可以在保持节点分类的预测性能的同时修剪图的一些边，或者在特定子图而不是整个图上训练分类器，而节点分类的性能损失有限。为了解决这些问题，我们提出了稀疏图卷积网络（SGCN），这是一种神经网络图稀疏器，通过修剪一些边来稀疏化图。我们将稀疏化表述为一个优化问题，并通过乘子交替方向法 (ADMM) 来解决它。实验表明，与随机剪枝、Spectral Sparsifier 和 DropEdge 等其他稀疏器相比，SGCN 可以识别 GCN 中节点分类的高效子图。我们还表明，SGCN 提供的稀疏图可以作为 GCN 的输入，这会带来与 GCN、DeepWalk、GraphSAGE 和 GAT 中原始图更好或相当的节点分类性能。我们从低通滤波器的角度分析 SGCN 的性能，从而深入了解 SGCN 为何表现良好。
Graphs are ubiquitous across the globe and within science and engineering. Some powerful classifiers are proposed to classify nodes in graphs, such as Graph Convolutional Networks (GCNs). However, as graphs are growing in size,node classificationon large graphs can be space and time consuming due to using whole graphs. Hence, some questions are raised, particularly, whether one can prune some of the edges of a graph while maintaining prediction performance for node classification, or train classifiers on specific subgraphs instead of a whole graph with limited performance loss in node classification. To address these questions, we proposeSparsified Graph Convolutional Network(SGCN), a neural network graph sparsifier that sparsifies a graph by pruning some edges. We formulate sparsification as an optimization problem and solve it by an Alternating Direction Method of Multipliers (ADMM). The experiment illustrates that SGCN can identify highly effective subgraphs for node classification in GCN compared to other sparsifiers such as Random Pruning, Spectral Sparsifier and DropEdge. We also show that sparsified graphs provided by SGCN can be inputs to GCN, which leads to better or comparable node classification performance with that of original graphs in GCN, DeepWalk, GraphSAGE, and GAT. We provide insights on why SGCN performs well by analyzing its performance from the view of a low-pass filter.