Graph-based Semi-Supervised Learning via Maximum Discrimination

• URL: http://arxiv.org/abs/2602.08042v1
• Date: Sun, 08 Feb 2026 16:18:49 GMT
• Title: Graph-based Semi-Supervised Learning via Maximum Discrimination
• Authors: Nadav Katz, Ariel Jaffe,
• Abstract summary: Semi-supervised learning (SSL) addresses the challenge of training accurate models when labeled data is scarce but unlabeled data is abundant.<n>We develop AUC-spec, a graph approach that computes a low-dimensional representation that maximizes class separation.<n>It demonstrates competitive results on synthetic and real-world datasets while maintaining computational efficiency comparable to the field's classic and state-of-the-art methods.
• Score: 0.8594140167290097
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Semi-supervised learning (SSL) addresses the critical challenge of training accurate models when labeled data is scarce but unlabeled data is abundant. Graph-based SSL (GSSL) has emerged as a popular framework that captures data structure through graph representations. Classic graph SSL methods, such as Label Propagation and Label Spreading, aim to compute low-dimensional representations where points with the same labels are close in representation space. Although often effective, these methods can be suboptimal on data with complex label distributions. In our work, we develop AUC-spec, a graph approach that computes a low-dimensional representation that maximizes class separation. We compute this representation by optimizing the Area Under the ROC Curve (AUC) as estimated via the labeled points. We provide a detailed analysis of our approach under a product-of-manifold model, and show that the required number of labeled points for AUC-spec is polynomial in the model parameters. Empirically, we show that AUC-spec balances class separation with graph smoothness. It demonstrates competitive results on synthetic and real-world datasets while maintaining computational efficiency comparable to the field's classic and state-of-the-art methods.

Related papers

• A Unified Framework for Fair Spectral Clustering With Effective Graph Learning [12.343382413705394]
  We consider the problem of spectral clustering under group fairness constraints. In practice, the graph is usually unknown, and we need to construct the underlying graph from potentially noisy data. We propose a novel graph construction method with a node-adaptive graph filter to learn graphs from noisy data.
  arXiv  Detail & Related papers  (2023-11-23T01:43:00Z)
• Graph Out-of-Distribution Generalization with Controllable Data Augmentation [51.17476258673232]
  Graph Neural Network (GNN) has demonstrated extraordinary performance in classifying graph properties. Due to the selection bias of training and testing data, distribution deviation is widespread. We propose OOD calibration to measure the distribution deviation of virtual samples.
  arXiv  Detail & Related papers  (2023-08-16T13:10:27Z)
• Evaluating Self-Supervised Learning for Molecular Graph Embeddings [38.65102126919387]
  Graph Self-Supervised Learning (GSSL) provides a robust pathway for acquiring embeddings without expert labelling. "MOLGRAPHEVAL" generates detailed profiles of molecular graph embeddings with interpretable and diversified attributes.
  arXiv  Detail & Related papers  (2022-06-16T09:01:53Z)
• Template based Graph Neural Network with Optimal Transport Distances [11.56532171513328]
  Current Graph Neural Networks (GNN) architectures rely on two important components: node features embedding through message passing, and aggregation with a specialized form of pooling. We propose in this work a novel point of view, which places distances to some learnable graph templates at the core of the graph representation. This distance embedding is constructed thanks to an optimal transport distance: the Fused Gromov-Wasserstein (FGW) distance.
  arXiv  Detail & Related papers  (2022-05-31T12:24:01Z)
• Effective and Efficient Graph Learning for Multi-view Clustering [173.8313827799077]
  We propose an effective and efficient graph learning model for multi-view clustering. Our method exploits the view-similar between graphs of different views by the minimization of tensor Schatten p-norm. Our proposed algorithm is time-economical and obtains the stable results and scales well with the data size.
  arXiv  Detail & Related papers  (2021-08-15T13:14:28Z)
• Semi-supervised Superpixel-based Multi-Feature Graph Learning for Hyperspectral Image Data [0.0]
  We present a novel framework for the classification of Hyperspectral Image (HSI) data in light of a very limited amount of labelled data. We propose a multi-stage edge-efficient semi-supervised graph learning framework for HSI data.
  arXiv  Detail & Related papers  (2021-04-27T15:36:26Z)
• Spatial-Spectral Clustering with Anchor Graph for Hyperspectral Image [88.60285937702304]
  This paper proposes a novel unsupervised approach called spatial-spectral clustering with anchor graph (SSCAG) for HSI data clustering. The proposed SSCAG is competitive against the state-of-the-art approaches.
  arXiv  Detail & Related papers  (2021-04-24T08:09:27Z)
• Spatial-spectral Hyperspectral Image Classification via Multiple Random Anchor Graphs Ensemble Learning [88.60285937702304]
  This paper proposes a novel spatial-spectral HSI classification method via multiple random anchor graphs ensemble learning (RAGE) Firstly, the local binary pattern is adopted to extract the more descriptive features on each selected band, which preserves local structures and subtle changes of a region. Secondly, the adaptive neighbors assignment is introduced in the construction of anchor graph, to reduce the computational complexity.
  arXiv  Detail & Related papers  (2021-03-25T09:31:41Z)
• Graph Networks with Spectral Message Passing [1.0742675209112622]
  We introduce the Spectral Graph Network, which applies message passing to both the spatial and spectral domains. Our results show that the Spectral GN promotes efficient training, reaching high performance with fewer training iterations despite having more parameters.
  arXiv  Detail & Related papers  (2020-12-31T21:33:17Z)
• Contrastive and Generative Graph Convolutional Networks for Graph-based Semi-Supervised Learning [64.98816284854067]
  Graph-based Semi-Supervised Learning (SSL) aims to transfer the labels of a handful of labeled data to the remaining massive unlabeled data via a graph. A novel GCN-based SSL algorithm is presented in this paper to enrich the supervision signals by utilizing both data similarities and graph structure.
  arXiv  Detail & Related papers  (2020-09-15T13:59:28Z)
• Structured Graph Learning for Clustering and Semi-supervised Classification [74.35376212789132]
  We propose a graph learning framework to preserve both the local and global structure of data. Our method uses the self-expressiveness of samples to capture the global structure and adaptive neighbor approach to respect the local structure. Our model is equivalent to a combination of kernel k-means and k-means methods under certain condition.
  arXiv  Detail & Related papers  (2020-08-31T08:41:20Z)
• Almost exact recovery in noisy semi-supervised learning [0.09208007322096533]
  Graph-based semi-supervised learning methods combine the graph structure and labeled data to classify unlabeled data. We propose an algorithm derived from a continuous relaxation of the MAP, and we establish its consistency. Numerical experiments show that our approach achieves promising performance on synthetic and real data sets, even in the case of very noisy labeled data.
  arXiv  Detail & Related papers  (2020-07-29T09:56:05Z)

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.