Optimal Exact Recovery in Semi-Supervised Learning: A Study of Spectral Methods and Graph Convolutional Networks

Hai-Xiao Wang, Zhichao Wang · 2024

Read Optimal Exact Recovery in Semi-Supervised Learning: A Study of Spectral Methods and Graph Convolutional Networks by Hai-Xiao Wang, Zhichao Wang (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-13754.txt.

Description

Hai-Xiao Wang and Zhichao Wang study label guessing on networks in a 2024 paper. In semi-supervised learning, only some nodes in a network carry labels. The task is to guess the rest. Their test world joins two clusters of nodes with trait vectors drawn from a mixed model. Each node's traits match its hidden cluster.

The authors find, for the first time, the exact data limit at which full recovery of all test labels is possible. They then build a spectral method that hits that limit. It blends the network links, the traits, and the known labels. Two other methods, graph ridge regression and graph neural networks, also hit the limit when tuned with the right self-loop weight. That hints feature learning helps such networks shine.

Catalog record

CREATORHai-Xiao Wang, Zhichao Wang
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE170 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-13754

Browse the full library · About the Tower of Babel