The Graph Lottery Ticket Hypothesis: Finding Sparse, Informative Graph Structure
This addresses the challenge of reducing computational costs and improving efficiency in graph-based machine learning, though it appears incremental as it builds on the lottery ticket hypothesis from neural networks.
The paper tackles the problem of finding optimal graph structures for learning tasks by proposing the Graph Lottery Ticket Hypothesis, which states that an extremely sparse subgraph can achieve comparable performance to the full graph, and they empirically show that graph learning algorithms can match or exceed performance with average degrees as low as 5.
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.