Edge Classification on Graphs: New Directions in Topological Imbalance

• URL: http://arxiv.org/abs/2406.11685v2
• Date: Tue, 18 Jun 2024 02:49:25 GMT
• Title: Edge Classification on Graphs: New Directions in Topological Imbalance
• Authors: Xueqi Cheng, Yu Wang, Yunchao Liu, Yuying Zhao, Charu C. Aggarwal, Tyler Derr,
• Abstract summary: We identify a novel Topological Imbalance Issue', which arises from the skewed distribution of edges across different classes. We introduce Topological Entropy (TE), a novel topological-based metric that measures the topological imbalance for each edge. We develop two strategies - Topological Reweighting and TE Wedge-based Mixup - to focus training on (synthetic) edges based on their TEs.
• Score: 53.42066415249078
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent years have witnessed the remarkable success of applying Graph machine learning (GML) to node/graph classification and link prediction. However, edge classification task that enjoys numerous real-world applications such as social network analysis and cybersecurity, has not seen significant advancement. To address this gap, our study pioneers a comprehensive approach to edge classification. We identify a novel `Topological Imbalance Issue', which arises from the skewed distribution of edges across different classes, affecting the local subgraph of each edge and harming the performance of edge classifications. Inspired by the recent studies in node classification that the performance discrepancy exists with varying local structural patterns, we aim to investigate if the performance discrepancy in topological imbalanced edge classification can also be mitigated by characterizing the local class distribution variance. To overcome this challenge, we introduce Topological Entropy (TE), a novel topological-based metric that measures the topological imbalance for each edge. Our empirical studies confirm that TE effectively measures local class distribution variance, and indicate that prioritizing edges with high TE values can help address the issue of topological imbalance. Based on this, we develop two strategies - Topological Reweighting and TE Wedge-based Mixup - to focus training on (synthetic) edges based on their TEs. While topological reweighting directly manipulates training edge weights according to TE, our wedge-based mixup interpolates synthetic edges between high TE wedges. Ultimately, we integrate these strategies into a novel topological imbalance strategy for edge classification: TopoEdge. Through extensive experiments, we demonstrate the efficacy of our proposed strategies on newly curated datasets and thus establish a new benchmark for (imbalanced) edge classification.

Related papers

• Topology-Aware 3D Gaussian Splatting: Leveraging Persistent Homology for Optimized Structural Integrity [3.792470553976718]
  This work introduces Topology-Aware 3D Gaussian Splatting (Topology-GS) Topology-GS addresses compromised pixel-level structural integrity due to incomplete initial geometric coverage. Experiments on three novel-view benchmarks demonstrate that Topology-GS outperforms existing methods in terms of PSNR, SSIM, and LPIPS metrics.
  arXiv  Detail & Related papers  (2024-12-21T13:25:03Z)
• Perturbation Ontology based Graph Attention Networks [26.95077612390953]
  Ontology-based Graph Attention Networks (POGAT) is a novel methodology that combines ontology subgraphs with an advanced self-supervised learning paradigm to achieve a deep contextual understanding. POGAT significantly outperforms state-of-the-art baselines, achieving a groundbreaking improvement of up to 10.78% in F1-score for the critical task of link prediction and 12.01% in Micro-F1 for the critical task of node classification.
  arXiv  Detail & Related papers  (2024-11-27T17:12:14Z)
• Enhancing the Resilience of Graph Neural Networks to Topological Perturbations in Sparse Graphs [9.437128738619563]
  We propose a novel label inference framework, TraTopo, which combines topology-driven label propagation, Bayesian label transitions, and link analysis via random walks. TraTopo significantly surpasses its predecessors on sparse graphs by utilizing random walk sampling, specifically targeting isolated nodes for link prediction. Empirical evaluations highlight TraTopo's superiority in node classification, significantly exceeding contemporary GCN models in accuracy.
  arXiv  Detail & Related papers  (2024-06-05T09:40:08Z)
• 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)
• Subsidiary Prototype Alignment for Universal Domain Adaptation [58.431124236254]
  A major problem in Universal Domain Adaptation (UniDA) is misalignment of "known" and "unknown" classes. We propose a novel word-histogram-related pretext task to enable closed-set SPA, operating in conjunction with goal task UniDA. We demonstrate the efficacy of our approach on top of existing UniDA techniques, yielding state-of-the-art performance across three standard UniDA and Open-Set DA object recognition benchmarks.
  arXiv  Detail & Related papers  (2022-10-28T05:32:14Z)
• Position-aware Structure Learning for Graph Topology-imbalance by Relieving Under-reaching and Over-squashing [67.83086131278904]
  Topology-imbalance is a graph-specific imbalance problem caused by the uneven topology positions of labeled nodes. We propose a novel position-aware graph structure learning framework named PASTEL. Our key insight is to enhance the connectivity of nodes within the same class for more supervision information.
  arXiv  Detail & Related papers  (2022-08-17T14:04:21Z)
• Interpolation-based Correlation Reduction Network for Semi-Supervised Graph Learning [49.94816548023729]
  We propose a novel graph contrastive learning method, termed Interpolation-based Correlation Reduction Network (ICRN) In our method, we improve the discriminative capability of the latent feature by enlarging the margin of decision boundaries. By combining the two settings, we extract rich supervision information from both the abundant unlabeled nodes and the rare yet valuable labeled nodes for discnative representation learning.
  arXiv  Detail & Related papers  (2022-06-06T14:26:34Z)
• Revisiting LSTM Networks for Semi-Supervised Text Classification via Mixed Objective Function [106.69643619725652]
  We develop a training strategy that allows even a simple BiLSTM model, when trained with cross-entropy loss, to achieve competitive results. We report state-of-the-art results for text classification task on several benchmark datasets.
  arXiv  Detail & Related papers  (2020-09-08T21:55:22Z)

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.