Graph Sanitation with Application to Node Classification

Zhe Xu, Boxin Du, Hanghang Tong

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

Abstract

The past decades have witnessed the prosperity of graph mining, with a multitude of sophisticated models and algorithms designed for various mining tasks, such as ranking, classification, clustering and anomaly detection. Generally speaking, the vast majority of the existing works aim to answer the following question, that is, given a graph, what is the best way to mine it? In this paper, we introduce the graph sanitation problem, to answer an orthogonal question. That is, given a mining task and an initial graph, what is the best way to improve the initially provided graph? By learning a better graph as part of the input of the mining model, it is expected to benefit graph mining in a variety of settings, ranging from denoising, imputation to defense. We formulate the graph sanitation problem as a bilevel optimization problem, and further instantiate it by semi-supervised node classification, together with an effective solver named GaSoliNe. Extensive experimental results demonstrate that the proposed method is (1) broadly applicable with respect to various graph neural network models and flexible graph modification strategies, (2) effective in improving the node classification accuracy on both the original and contaminated graphs in various perturbation scenarios. In particular, it brings up to 25% performance improvement over the existing robust graph neural network methods.

Original languageEnglish (US)
Title of host publicationWWW 2022 - Proceedings of the ACM Web Conference 2022
PublisherAssociation for Computing Machinery
Pages1136-1147
Number of pages12
ISBN (Electronic)9781450390965
DOIs
StatePublished - Apr 25 2022
Event31st ACM World Wide Web Conference, WWW 2022 - Virtual, Online, France
Duration: Apr 25 2022Apr 29 2022

Publication series

NameWWW 2022 - Proceedings of the ACM Web Conference 2022

Conference

Conference31st ACM World Wide Web Conference, WWW 2022
Country/TerritoryFrance
CityVirtual, Online
Period4/25/224/29/22

Keywords

  • graph mining
  • graph sanitation
  • node classification

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Software

Fingerprint

Dive into the research topics of 'Graph Sanitation with Application to Node Classification'. Together they form a unique fingerprint.

Cite this