The Graph Lottery Ticket Hypothesis: Finding Sparse, Informative Graph
  Structure
Anton Tsitsulin Bryan Perozzi
Graph learning methods help utilize implicit relationships among data items,
thereby reducing training label requirements and improving task performance.
However, determining the optimal graph structure for a particular learning task
remains a challenging research problem.
  In this work, we introduce the Graph Lottery Ticket (GLT) Hypothesis - that
there is an extremely sparse backbone for every graph, and that graph learning
algorithms attain comparable performance when trained on that subgraph as on
the full graph. We identify and systematically study 8 key metrics of interest
that directly influence the performance of graph learning algorithms.
Subsequently, we define the notion of a "winning ticket" for graph structure -
an extremely sparse subset of edges that can deliver a robust approximation of
the entire graph's performance. We propose a straightforward and efficient
algorithm for finding these GLTs in arbitrary graphs. Empirically, we observe
that performance of different graph learning algorithms can be matched or even
exceeded on graphs with the average degree as low as 5.