Latent graph inference (LGI) aims to jointly learn the underlying graph
structure and node representations from data features. However, existing LGI
methods commonly suffer from the issue of supervision starvation, where massive
edge weights are learned without semantic supervision and do not contribute to
the training loss. Consequently, these supervision-starved weights, which may
determine the predictions of testing samples, cannot be semantically optimal,
resulting in poor generalization. In this paper, we observe that this issue is
actually caused by the graph sparsification operation, which severely destroys
the important connections established between pivotal nodes and labeled ones.
To address this, we propose to restore the corrupted affinities and replenish
the missed supervision for better LGI. The key challenge then lies in
identifying the critical nodes and recovering the corrupted affinities. We
begin by defining the pivotal nodes as $k$-hop starved nodes, which can be
identified based on a given adjacency matrix. Considering the high
computational burden, we further present a more efficient alternative inspired
by CUR matrix decomposition. Subsequently, we eliminate the starved nodes by
reconstructing the destroyed connections. Extensive experiments on
representative benchmarks demonstrate that reducing the starved nodes
consistently improves the performance of state-of-the-art LGI methods,
especially under extremely limited supervision (6.12% improvement on Pubmed
with a labeling rate of only 0.3%).

通过恢复破坏的联系并提供缺失的监督，以改善潜在图推断方法的性能。