# A Quest for Structure: Jointly Learning the Graph Structure and Semi-Supervised Classification

arXiv: https://arxiv.org/abs/1909.12385 · HTML: https://mlsanity.com/paper/1909.12385/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Sep 2019.

## Built on by (most cited first, 13 of 13)

- [NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification](https://mlsanity.com/paper/2306.08385/) (2023)
- [Is Homophily a Necessity for Graph Neural Networks?](https://mlsanity.com/paper/2106.06134/) (2021)
- [Data Augmentation for Deep Graph Learning: A Survey](https://mlsanity.com/paper/2202.08235/) (2022)
- [SLAPS: Self-Supervision Improves Structure Learning for Graph Neural Networks](https://mlsanity.com/paper/2102.05034/) (2021)
- [Evidence-aware Fake News Detection with Graph Neural Networks](https://mlsanity.com/paper/2201.06885/) (2022)
- [GraphFM: Graph Factorization Machines for Feature Interaction Modeling](https://mlsanity.com/paper/2105.11866/) (2021)
- [RobGC: Towards Robust Graph Condensation](https://mlsanity.com/paper/2406.13200/) (2024)
- [Adversarial Contrastive Learning for Evidence-aware Fake News Detection with Graph Neural Networks](https://mlsanity.com/paper/2210.05498/) (2022)
- [On the Detection of Reviewer-Author Collusion Rings From Paper Bidding](https://mlsanity.com/paper/2402.07860/) (2024)
- [GLAM: Graph Learning by Modeling Affinity to Labeled Nodes for Graph Neural Networks](https://mlsanity.com/paper/2102.10403/) (2021)
- [Robust Graph Structure Learning with the Alignment of Features and Adjacency Matrix](https://mlsanity.com/paper/2307.02126/) (2023)
- [Self-Attention Empowered Graph Convolutional Network for Structure Learning and Node Embedding](https://mlsanity.com/paper/2403.03465/) (2024)
- [Large-Scale Graph Building in Dynamic Environments: Low Latency and High Quality](https://mlsanity.com/paper/2507.10139/) (2025)

## Abstract (arXiv)

Semi-supervised learning (SSL) is effectively used for numerous classification problems, thanks to its ability to make use of abundant unlabeled data. The main assumption of various SSL algorithms is that the nearby points on the data manifold are likely to share a label. Graph-based SSL constructs a graph from point-cloud data as an approximation to the underlying manifold, followed by label inference. It is no surprise that the quality of the constructed graph in capturing the essential structure of the data is critical to the accuracy of the subsequent inference step [6]. How should one construct a graph from the input point-cloud data for graph-based SSL? In this work we introduce a new, parallel graph learning framework (called PG-learn) for the graph construction step of SSL. Our solution has two main ingredients: (1) a gradient-based optimization of the edge weights (more specifically, different kernel bandwidths in each dimension) based on a validation loss function, and (2) a parallel hyperparameter search algorithm with an adaptive resource allocation scheme. In essence, (1) allows us to search around a (random) initial hyperparameter configuration for a better one with lower validation loss. Since the search space of hyperparameters is huge for high-dimensional problems, (2) empowers our gradient-based search to go through as many different initial configurations as possible, where runs for relatively unpromising starting configurations are terminated early to allocate the time for others. As such, PG-learn is a carefully-designed hybrid of random and adaptive search. Through experiments on multi-class classification problems, we show that PG-learn significantly outperforms a variety of existing graph construction schemes in accuracy (per fixed time budget for hyperparameter tuning), and scales more effectively to high dimensional problems.