Leveraging Label Non-Uniformity for Node Classification in Graph Neural Networks

• URL: http://arxiv.org/abs/2305.00139v1
• Date: Sat, 29 Apr 2023 01:09:56 GMT
• Title: Leveraging Label Non-Uniformity for Node Classification in Graph Neural Networks
• Authors: Feng Ji and See Hian Lee and Hanyang Meng and Kai Zhao and Jielong Yang and Wee Peng Tay
• Abstract summary: In node classification using graph neural networks (GNNs), a typical model generates logits for different class labels at each node. We introduce the key notion of label non-uniformity, which is derived from the Wasserstein distance between the softmax distribution of the logits and the uniform distribution. We theoretically analyze how the label non-uniformity varies across the graph, which provides insights into boosting the model performance.
• Score: 33.84217145105558
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In node classification using graph neural networks (GNNs), a typical model generates logits for different class labels at each node. A softmax layer often outputs a label prediction based on the largest logit. We demonstrate that it is possible to infer hidden graph structural information from the dataset using these logits. We introduce the key notion of label non-uniformity, which is derived from the Wasserstein distance between the softmax distribution of the logits and the uniform distribution. We demonstrate that nodes with small label non-uniformity are harder to classify correctly. We theoretically analyze how the label non-uniformity varies across the graph, which provides insights into boosting the model performance: increasing training samples with high non-uniformity or dropping edges to reduce the maximal cut size of the node set of small non-uniformity. These mechanisms can be easily added to a base GNN model. Experimental results demonstrate that our approach improves the performance of many benchmark base models.

Related papers

• GRAPES: Learning to Sample Graphs for Scalable Graph Neural Networks [2.4175455407547015]
  Graph neural networks learn to represent nodes by aggregating information from their neighbors. Several existing methods address this by sampling a small subset of nodes, scaling GNNs to much larger graphs. We introduce GRAPES, an adaptive sampling method that learns to identify the set of nodes crucial for training a GNN.
  arXiv  Detail & Related papers  (2023-10-05T09:08:47Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• Seq-HGNN: Learning Sequential Node Representation on Heterogeneous Graph [57.2953563124339]
  We propose a novel heterogeneous graph neural network with sequential node representation, namely Seq-HGNN. We conduct extensive experiments on four widely used datasets from Heterogeneous Graph Benchmark (HGB) and Open Graph Benchmark (OGB)
  arXiv  Detail & Related papers  (2023-05-18T07:27:18Z)
• Distributional Signals for Node Classification in Graph Neural Networks [36.30743671968087]
  In graph neural networks (GNNs) both node features and labels are examples of graph signals, a key notion in graph signal processing (GSP) In our framework, we work with the distributions of node labels instead of their values and propose notions of smoothness and non-uniformity of such distributional graph signals. We then propose a general regularization method for GNNs that allows us to encode distributional smoothness and non-uniformity of the model output in semi-supervised node classification tasks.
  arXiv  Detail & Related papers  (2023-04-07T06:54:42Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• Neural Graph Matching for Pre-training Graph Neural Networks [72.32801428070749]
  Graph neural networks (GNNs) have been shown powerful capacity at modeling structural data. We present a novel Graph Matching based GNN Pre-Training framework, called GMPT. The proposed method can be applied to fully self-supervised pre-training and coarse-grained supervised pre-training.
  arXiv  Detail & Related papers  (2022-03-03T09:53:53Z)
• Structure-Aware Label Smoothing for Graph Neural Networks [39.97741949184259]
  Representing a label distribution as a one-hot vector is a common practice in training node classification models. We propose a novel SALS (textitStructure-Aware Label Smoothing) method as an enhancement component to popular node classification models.
  arXiv  Detail & Related papers  (2021-12-01T13:48:58Z)
• Graph Neural Networks with Feature and Structure Aware Random Walk [7.143879014059894]
  We show that in typical heterphilous graphs, the edges may be directed, and whether to treat the edges as is or simply make them undirected greatly affects the performance of the GNN models. We develop a model that adaptively learns the directionality of the graph, and exploits the underlying long-distance correlations between nodes.
  arXiv  Detail & Related papers  (2021-11-19T08:54:21Z)
• Explicit Pairwise Factorized Graph Neural Network for Semi-Supervised Node Classification [59.06717774425588]
  We propose the Explicit Pairwise Factorized Graph Neural Network (EPFGNN), which models the whole graph as a partially observed Markov Random Field. It contains explicit pairwise factors to model output-output relations and uses a GNN backbone to model input-output relations. We conduct experiments on various datasets, which shows that our model can effectively improve the performance for semi-supervised node classification on graphs.
  arXiv  Detail & Related papers  (2021-07-27T19:47:53Z)
• GraphSMOTE: Imbalanced Node Classification on Graphs with Graph Neural Networks [28.92347073786722]
  Graph neural networks (GNNs) have achieved state-of-the-art performance of node classification. We propose a novel framework, GraphSMOTE, in which an embedding space is constructed to encode the similarity among the nodes. New samples are synthesize in this space to assure genuineness.
  arXiv  Detail & Related papers  (2021-03-16T03:23:55Z)
• Unifying Graph Convolutional Neural Networks and Label Propagation [73.82013612939507]
  We study the relationship between LPA and GCN in terms of two aspects: feature/label smoothing and feature/label influence. Based on our theoretical analysis, we propose an end-to-end model that unifies GCN and LPA for node classification. Our model can also be seen as learning attention weights based on node labels, which is more task-oriented than existing feature-based attention models.
  arXiv  Detail & Related papers  (2020-02-17T03:23:13Z)

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.