Balancing Augmentation with Edge-Utility Filter for Signed GNNs

• URL: http://arxiv.org/abs/2310.16862v1
• Date: Wed, 25 Oct 2023 07:15:01 GMT
• Title: Balancing Augmentation with Edge-Utility Filter for Signed GNNs
• Authors: Ke-Jia Chen, Yaming Ji, Youran Qu, Chuhan Xu
• Abstract summary: Signed graph neural networks (SGNNs) has recently drawn more attention as many real-world networks are signed networks containing two types of edges: positive and negative. The existence of negative edges affects the SGNN robustness on two aspects. One is the semantic imbalance as the negative edges are hard to obtain though they can provide potentially useful information. In this paper, we propose a balancing augmentation method to address the above two aspects for SGNNs. Firstly, the utility of each negative edge is measured by calculating its occurrence in unbalanced structures. Secondly, the original signed graph is selectively augmented with the use of (1) an edge regulator
• Score: 0.20482269513546458
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Signed graph neural networks (SGNNs) has recently drawn more attention as many real-world networks are signed networks containing two types of edges: positive and negative. The existence of negative edges affects the SGNN robustness on two aspects. One is the semantic imbalance as the negative edges are usually hard to obtain though they can provide potentially useful information. The other is the structural unbalance, e.g. unbalanced triangles, an indication of incompatible relationship among nodes. In this paper, we propose a balancing augmentation method to address the above two aspects for SGNNs. Firstly, the utility of each negative edge is measured by calculating its occurrence in unbalanced structures. Secondly, the original signed graph is selectively augmented with the use of (1) an edge perturbation regulator to balance the number of positive and negative edges and to determine the ratio of perturbed edges to original edges and (2) an edge utility filter to remove the negative edges with low utility to make the graph structure more balanced. Finally, a SGNN is trained on the augmented graph which effectively explores the credible relationships. A detailed theoretical analysis is also conducted to prove the effectiveness of each module. Experiments on five real-world datasets in link prediction demonstrate that our method has the advantages of effectiveness and generalization and can significantly improve the performance of SGNN backbones.

Related papers

• Oversmoothing as Loss of Sign: Towards Structural Balance in Graph Neural Networks [54.62268052283014]
  Oversmoothing is a common issue in graph neural networks (GNNs) Three major classes of anti-oversmoothing techniques can be mathematically interpreted as message passing over signed graphs. Negative edges can repel nodes to a certain extent, providing deeper insights into how these methods mitigate oversmoothing.
  arXiv  Detail & Related papers  (2025-02-17T03:25:36Z)
• Why Does Dropping Edges Usually Outperform Adding Edges in Graph Contrastive Learning? [54.44813218411879]
  We introduce a new metric, namely Error Passing Rate (EPR), to quantify how a graph fits the network. Inspired by the theoretical conclusions and the idea of positive-incentive noise, we propose a novel GCL algorithm, Error-PAssing-based Graph Contrastive Learning (EPAGCL) We generate views by adding and dropping edges based on the weights derived from EPR.
  arXiv  Detail & Related papers  (2024-12-11T06:31:06Z)
• ADEdgeDrop: Adversarial Edge Dropping for Robust Graph Neural Networks [53.41164429486268]
  Graph Neural Networks (GNNs) have exhibited the powerful ability to gather graph-structured information from neighborhood nodes. The performance of GNNs is limited by poor generalization and fragile robustness caused by noisy and redundant graph data. We propose a novel adversarial edge-dropping method (ADEdgeDrop) that leverages an adversarial edge predictor guiding the removal of edges.
  arXiv  Detail & Related papers  (2024-03-14T08:31:39Z)
• Learning to Reweight for Graph Neural Network [63.978102332612906]
  Graph Neural Networks (GNNs) show promising results for graph tasks. Existing GNNs' generalization ability will degrade when there exist distribution shifts between testing and training graph data. We propose a novel nonlinear graph decorrelation method, which can substantially improve the out-of-distribution generalization ability.
  arXiv  Detail & Related papers  (2023-12-19T12:25:10Z)
• Efficient Link Prediction via GNN Layers Induced by Negative Sampling [92.05291395292537]
  Graph neural networks (GNNs) for link prediction can loosely be divided into two broad categories. First, emphnode-wise architectures pre-compute individual embeddings for each node that are later combined by a simple decoder to make predictions. Second, emphedge-wise methods rely on the formation of edge-specific subgraph embeddings to enrich the representation of pair-wise relationships.
  arXiv  Detail & Related papers  (2023-10-14T07:02:54Z)
• Finding Heterophilic Neighbors via Confidence-based Subgraph Matching for Semi-supervised Node Classification [1.3190581566723918]
  Graph Neural Networks (GNNs) have proven to be powerful in many graph-based applications. However, they fail to generalize well under heterophilic setups.
  arXiv  Detail & Related papers  (2023-02-20T04:23:34Z)
• Refined Edge Usage of Graph Neural Networks for Edge Prediction [51.06557652109059]
  We propose a novel edge prediction paradigm named Edge-aware Message PassIng neuRal nEtworks (EMPIRE) We first introduce an edge splitting technique to specify use of each edge where each edge is solely used as either the topology or the supervision. In order to emphasize the differences between pairs connected by supervision edges and pairs unconnected, we further weight the messages to highlight the relative ones that can reflect the differences.
  arXiv  Detail & Related papers  (2022-12-25T23:19:56Z)
• ES-GNN: Generalizing Graph Neural Networks Beyond Homophily with Edge Splitting [32.69196871253339]
  We propose a novel Edge Splitting GNN (ES-GNN) framework to adaptively distinguish between graph edges either relevant or irrelevant to learning tasks. We show that our ES-GNN can be regarded as a solution to a disentangled graph denoising problem.
  arXiv  Detail & Related papers  (2022-05-27T01:29:03Z)
• Exploiting Neighbor Effect: Conv-Agnostic GNNs Framework for Graphs with Heterophily [58.76759997223951]
  We propose a new metric based on von Neumann entropy to re-examine the heterophily problem of GNNs. We also propose a Conv-Agnostic GNN framework (CAGNNs) to enhance the performance of most GNNs on heterophily datasets.
  arXiv  Detail & Related papers  (2022-03-19T14:26:43Z)
• Learnt Sparsification for Interpretable Graph Neural Networks [5.527927312898106]
  We propose a novel method called Kedge for explicitly sparsifying the underlying graph by removing unnecessary neighbors. Kedge learns edge masks in a modular fashion trained with any GNN allowing for gradient based optimization. We show that Kedge effectively counters the over-smoothing phenomena in deep GNNs by maintaining good task performance with increasing GNN layers.
  arXiv  Detail & Related papers  (2021-06-23T16:04:25Z)
• Training Robust Graph Neural Networks with Topology Adaptive Edge Dropping [116.26579152942162]
  Graph neural networks (GNNs) are processing architectures that exploit graph structural information to model representations from network data. Despite their success, GNNs suffer from sub-optimal generalization performance given limited training data. This paper proposes Topology Adaptive Edge Dropping to improve generalization performance and learn robust GNN models.
  arXiv  Detail & Related papers  (2021-06-05T13:20:36Z)
• Relation-aware Graph Attention Model With Adaptive Self-adversarial Training [29.240686573485718]
  This paper describes an end-to-end solution for the relationship prediction task in heterogeneous, multi-relational graphs. We particularly address two building blocks in the pipeline, namely heterogeneous graph representation learning and negative sampling. We introduce a parameter-free negative sampling technique -- adaptive self-adversarial (ASA) negative sampling.
  arXiv  Detail & Related papers  (2021-02-14T16:11:56Z)

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.