Abstract: Graph neural networks (GNNs) work well when the graph structure is provided.
However, this structure may not always be available in real-world applications.
One solution to this problem is to infer a task-specific latent structure and
then apply a GNN to the inferred graph. Unfortunately, the space of possible
graph structures grows super-exponentially with the number of nodes and so the
task-specific supervision may be insufficient for learning both the structure
and the GNN parameters. In this work, we propose the Simultaneous Learning of
Adjacency and GNN Parameters with Self-supervision, or SLAPS, a method that
provides more supervision for inferring a graph structure through
self-supervision. A comprehensive experimental study demonstrates that SLAPS
scales to large graphs with hundreds of thousands of nodes and outperforms
several models that have been proposed to learn a task-specific graph structure
on established benchmarks.