SGCN: A Graph Sparsifier Based on Graph Convolutional Networks

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Graphs are ubiquitous across the globe and within science and engineering. With graphs growing in size, node classification on large graphs can be space and time consuming, even with powerful classifiers such as Graph Convolutional Networks (GCNs). Hence, some questions are raised, particularly, whether one can keep only 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, which we solve by an Alternating Direction Method of Multipliers (ADMM)-based solution. We show that sparsified graphs provided by SGCN can be used as inputs to GCN, leading to better or comparable node classification performance with that of original graphs in GCN, DeepWalk, and GraphSAGE.

Original languageEnglish (US)
Title of host publicationAdvances in Knowledge Discovery and Data Mining - 24th Pacific-Asia Conference, PAKDD 2020, Proceedings
EditorsHady W. Lauw, Ee-Peng Lim, Raymond Chi-Wing Wong, Alexandros Ntoulas, See-Kiong Ng, Sinno Jialin Pan
PublisherSpringer
Pages275-287
Number of pages13
ISBN (Print)9783030474256
DOIs
StatePublished - 2020
Event24th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2020 - Singapore, Singapore
Duration: May 11 2020May 14 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12084 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference24th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2020
CountrySingapore
CitySingapore
Period5/11/205/14/20

Keywords

  • Graph convolutional network
  • Graph sparsification
  • Node classification

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'SGCN: A Graph Sparsifier Based on Graph Convolutional Networks'. Together they form a unique fingerprint.

Cite this