Graph sparsification with graph convolutional networks

Jiayu Li, Tianyun Zhang, Hao Tian, Shengmin Jin, Makan Fardad, Reza Zafarani

Research output: Contribution to journalArticlepeer-review

Abstract

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 classification on 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 propose Sparsified 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.

Original languageEnglish (US)
JournalInternational Journal of Data Science and Analytics
DOIs
StateAccepted/In press - 2021

Keywords

  • Graph convolutional network
  • Graph sparsification
  • Node classification

ASJC Scopus subject areas

  • Information Systems
  • Modeling and Simulation
  • Computer Science Applications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Graph sparsification with graph convolutional networks'. Together they form a unique fingerprint.

Cite this