  Link prediction is a fundamental problem for graph-structured data (e.g.,
social networks, drug side-effect networks, etc.). Graph neural networks have
offered robust solutions for this problem, specifically by learning the
representation of the subgraph enclosing the target link (i.e., pair of nodes).
However, these solutions do not scale well to large graphs as extraction and
operation on enclosing subgraphs are computationally expensive, especially for
large graphs. This paper presents a scalable link prediction solution, that we
call ScaLed, which utilizes sparse enclosing subgraphs to make predictions. To
extract sparse enclosing subgraphs, ScaLed takes multiple random walks from a
target pair of nodes, then operates on the sampled enclosing subgraph induced
by all visited nodes. By leveraging the smaller sampled enclosing subgraph,
ScaLed can scale to larger graphs with much less overhead while maintaining
high accuracy. ScaLed further provides the flexibility to control the trade-off
between computation overhead and accuracy. Through comprehensive experiments,
we have shown that ScaLed can produce comparable accuracy to those reported by
the existing subgraph representation learning frameworks while being less
computationally demanding.
