Graph Sanitation with Application to Node Classification

• URL: http://arxiv.org/abs/2105.09384v1
• Date: Wed, 19 May 2021 20:22:15 GMT
• Title: Graph Sanitation with Application to Node Classification
• Authors: Zhe Xu and Hanghang Tong
• Abstract summary: We introduce the graph sanitation problem, to answer an question. 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. In particular, it brings up to 25% performance improvement over the existing robust graph neural network methods.
• Score: 41.311131936203715
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 different 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.

Related papers

• Gradient scarcity with Bilevel Optimization for Graph Learning [0.0]
  gradient scarcity occurs when learning graphs by minimizing a loss on a subset of nodes causes edges between unlabelled nodes that are far from labelled ones to receive zero gradients. We give a precise mathematical characterization of this phenomenon, and prove it also emerges in bilevel optimization. To alleviate this issue, we study several solutions: we propose to resort to latent graph learning using a Graph-to-Graph model (G2G), graph regularization to impose a prior structure on the graph, or optimizing on a larger graph than the original one with a reduced diameter.
  arXiv  Detail & Related papers  (2023-03-24T12:37:43Z)
• Edge but not Least: Cross-View Graph Pooling [76.71497833616024]
  This paper presents a cross-view graph pooling (Co-Pooling) method to better exploit crucial graph structure information. Through cross-view interaction, edge-view pooling and node-view pooling seamlessly reinforce each other to learn more informative graph-level representations.
  arXiv  Detail & Related papers  (2021-09-24T08:01:23Z)
• Graph Coarsening with Neural Networks [8.407217618651536]
  We propose a framework for measuring the quality of coarsening algorithm and show that depending on the goal, we need to carefully choose the Laplace operator on the coarse graph. Motivated by the observation that the current choice of edge weight for the coarse graph may be sub-optimal, we parametrize the weight assignment map with graph neural networks and train it to improve the coarsening quality in an unsupervised way.
  arXiv  Detail & Related papers  (2021-02-02T06:50:07Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  We use contrastive loss as a data fidelity term, in order to properly aggregate the observed layers into a representative graph. Experiments show that our method leads to a clustered clusters w.r.t. We learn a clustering algorithm for solving clustering problems.
  arXiv  Detail & Related papers  (2020-10-29T09:58:02Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  We consider the graph link prediction task, which is a classic graph analytical problem with many real-world applications. In this formalism, a link prediction problem is converted to a graph classification task. We propose to seek a radically different and novel path by making use of the line graphs in graph theory. In particular, each node in a line graph corresponds to a unique edge in the original graph. Therefore, link prediction problems in the original graph can be equivalently solved as a node classification problem in its corresponding line graph, instead of a graph classification task.
  arXiv  Detail & Related papers  (2020-10-20T05:54:31Z)
• Contrastive Self-supervised Learning for Graph Classification [21.207647143672585]
  We propose two approaches based on contrastive self-supervised learning (CSSL) to alleviate overfitting. In the first approach, we use CSSL to pretrain graph encoders on widely-available unlabeled graphs without relying on human-provided labels. In the second approach, we develop a regularizer based on CSSL, and solve the supervised classification task and the unsupervised CSSL task simultaneously.
  arXiv  Detail & Related papers  (2020-09-13T05:12:55Z)
• Second-Order Pooling for Graph Neural Networks [62.13156203025818]
  We propose to use second-order pooling as graph pooling, which naturally solves the above challenges. We show that direct use of second-order pooling with graph neural networks leads to practical problems. We propose two novel global graph pooling methods based on second-order pooling; namely, bilinear mapping and attentional second-order pooling.
  arXiv  Detail & Related papers  (2020-07-20T20:52:36Z)
• Multilevel Graph Matching Networks for Deep Graph Similarity Learning [79.3213351477689]
  We propose a multi-level graph matching network (MGMN) framework for computing the graph similarity between any pair of graph-structured objects. To compensate for the lack of standard benchmark datasets, we have created and collected a set of datasets for both the graph-graph classification and graph-graph regression tasks. Comprehensive experiments demonstrate that MGMN consistently outperforms state-of-the-art baseline models on both the graph-graph classification and graph-graph regression tasks.
  arXiv  Detail & Related papers  (2020-07-08T19:48:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.