Exploring Latent Sparse Graph for Large-Scale Semi-supervised Learning

Zitong WANG, Li WANG*, Raymond CHAN, Tieyong ZENG

*Corresponding author for this work

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review


We focus on developing a novel scalable graph-based semi-supervised learning (SSL) method for input data consisting of a small amount of labeled data and a large amount of unlabeled data. Due to the lack of labeled data and the availability of large-scale unlabeled data, existing SSL methods usually either encounter suboptimal performance because of an improper graph constructed from input data or are impractical due to the high-computational complexity of solving large-scale optimization problems. In this paper, we propose to address both problems by constructing a novel graph of input data for graph-based SSL methods. A density-based approach is proposed to learn a latent graph from input data. Based on the latent graph, a novel graph construction approach is proposed to construct the graph of input data by an efficient formula. With this formula, two transductive graph-based SSL methods are devised with the computational complexity linear in the number of input data points. Extensive experiments on synthetic data and real datasets demonstrate that the proposed methods not only are scalable for large-scale data, but also achieve good classification performance, especially for an extremely small number of labeled data.

Original languageEnglish
Title of host publicationMachine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2022, Proceedings
EditorsMassih-Reza AMINI, Stéphane CANU, Asja FISCHER, Tias GUNS, Petra KRALJ NOVAK, Grigorios TSOUMAKAS
PublisherSpringer, Cham
Number of pages17
ISBN (Electronic)9783031264122
ISBN (Print)9783031264115
Publication statusPublished - 2023
Externally publishedYes
Event22nd Joint European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2022 - Grenoble, France
Duration: 19 Sept 202223 Sept 2022

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference22nd Joint European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2022

Bibliographical note

Publisher Copyright:
© 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.


  • Graph structure learning
  • Graph-based semi-supervised learning
  • Large-scale learning


Dive into the research topics of 'Exploring Latent Sparse Graph for Large-Scale Semi-supervised Learning'. Together they form a unique fingerprint.

Cite this