  Graph structure learning is a well-established problem that aims at
optimizing graph structures adaptive to specific graph datasets to help message
passing neural networks (i.e., GNNs) to yield effective and robust node
embeddings. However, the common limitation of existing models lies in the
underlying \textit{closed-world assumption}: the testing graph is the same as
the training graph. This premise requires independently training the structure
learning model from scratch for each graph dataset, which leads to prohibitive
computation costs and potential risks for serious over-fitting. To mitigate
these issues, this paper explores a new direction that moves forward to learn a
universal structure learning model that can generalize across graph datasets in
an open world. We first introduce the mathematical definition of this novel
problem setting, and describe the model formulation from a probabilistic
data-generative aspect. Then we devise a general framework that coordinates a
single graph-shared structure learner and multiple graph-specific GNNs to
capture the generalizable patterns of optimal message-passing topology across
datasets. The well-trained structure learner can directly produce adaptive
structures for unseen target graphs without any fine-tuning. Across diverse
datasets and various challenging cross-graph generalization protocols, our
experiments show that even without training on target graphs, the proposed
model i) significantly outperforms expressive GNNs trained on input
(non-optimized) topology, and ii) surprisingly performs on par with
state-of-the-art models that independently optimize adaptive structures for
specific target graphs, with notably orders-of-magnitude acceleration for
training on the target graph.
