Graph Sanitation with Application to Node Classification
Graph Sanitation with Application to Node Classification
复制标题
DOI：
10.1145/3485447.3512180
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Zhe Xu;Hanghang Tong
中科院分区：
文献类型：
--
作者：
Zhe Xu;Hanghang Tong
在过去的几十年里，图挖掘技术繁荣，出现了许多复杂的模型和算法，用于各种挖掘任务，如排序，分类，聚类和异常检测。一般来说，绝大多数现有的工作旨在回答以下问题，即给定一个图，什么是挖掘它的最佳方法？在本文中，我们引入图卫生问题，回答一个正交问题。也就是说，给定一个挖掘任务和一个初始图，改进初始图的最佳方法是什么？通过学习一个更好的图作为挖掘模型的输入的一部分，它有望在各种设置中受益于图挖掘，从去噪，插补到防御。我们制定的图卫生问题作为一个双层优化问题，并进一步实例化它的半监督节点分类，以及一个有效的求解器名为GaSoliNe。大量的实验结果表明，该方法具有广泛的适用性和灵活的图修改策略，能够有效地提高原始图和污染图在各种扰动情况下的节点分类精度.特别是，它带来了高达25%的性能改善，比现有的强大的图神经网络方法。
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.