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

• When Witnesses Defend: A Witness Graph Topological Layer for Adversarial Graph Learning [19.566775406771757]
  We bridge adversarial graph learning with the emerging tools from computational topology, namely, persistent homology representations of graphs. We introduce the concept of witness complex to adversarial analysis on graphs, which allows us to focus only on the salient shape characteristics of graphs, with minimal loss of topological information on the whole graph. Armed with the witness mechanism, we design Witness Graph Topological Layer (WGTL), which systematically integrates both local and global topological graph feature representations, the impact of which is, in turn, automatically controlled by the robust regularized topological loss.
  arXiv  Detail & Related papers  (2024-09-21T14:53:32Z)
• 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)
• A Deep-Discrete Learning Framework for Spherical Surface Registration [4.7633236054762875]
  Cortical surface registration is a fundamental tool for neuroimaging analysis. We propose a novel unsupervised learning-based framework that converts registration to a multi-label classification problem. Experiments show that our proposed framework performs competitively, in terms of similarity and areal distortion, relative to the most popular classical surface registration algorithms.
  arXiv  Detail & Related papers  (2022-03-24T11:47:11Z)
• 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.