GraphGLOW: Universal and Generalizable Structure Learning for Graph
  Neural Networks
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.
Wentao Zhao, Qitian Wu, Chenxiao Yang, Junchi Yan
# GraphGLOW: Universal and Generalizable Structure Learning for Graph Neural Networks

###### Abstract.

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 _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.

2018 acmcopyrightrightmargin=5pt plus 1pt minus 1pt
as a bi-level optimization target that jointly learns a single dataset-shared structure learner and multiple dataset-specific GNNs tailored for particular graph datasets, as shown in Fig. 1. Under such a framework, the well-trained structure learner can leverage the common transferrable knowledge across datasets for enhancing generalization and more critically, be readily utilized to yield adaptive message-passing topology for arbitrarily given target graphs.

With the guidance of the aforementioned general goal, we propose GraphGLOW (short for A Graph Structure Learning Model for Open-World Generalization) that aims at learning the generalizable patterns of optimal message-passing topology across source graphs. Specifically, we first take a bottom-up perspective and formulate the generative process for observed data in a probabilistic manner. On top of this, we derive a tractable and feasible learning objective through the lens of variational inference. The structure learner is specified as a multi-head weighted similarity function so as to guarantee enough expressivity for accommodating diverse structural information, and we further harness an approximation scheme to reduce the quadratic complexity overhead of learning potential edges from arbitrary node pairs.

To reasonably and comprehensively evaluate the model, we devise experiments with a diverse set of protocols that can measure the generalization ability under different difficulty levels (according to the intensity of distribution shifts between source graphs and target graphs). Concretely, we consider: 1) In-domain generalization, in which we generalize from some citation (social) networks to other citation (social) networks. 2) Cross-domain networks generalization between citation and social networks. The results, which are consistent across various combinations of source and target graph datasets, demonstrate that when evaluated on the target graphs, our approach i) consistently outperforms directly training the GNN counterpart on original non-optimized graph structures of the target datasets and ii) performs on par with state-of-the-art structure learning methods (Golovolovolovolov et al., 2012; Golovolovolov and LeCun, 2015; Golovolovolov and LeCun, 2015) trained on target graphs from scratch with up to 25\(\times\) less training time consumed. Our code is available at [https://github.com/WtaoZhao/GraphGLOW](https://github.com/WtaoZhao/GraphGLOW).

## 2. Preliminary and Problem Definition

**Node-Level Predictive Tasks.** Denote a graph with \(N\) nodes as \(\mathcal{G}=(\mathbf{A},\mathbf{X},\mathbf{Y})\) where \(\mathbf{A}=\{a_{up}\}_{N\times N}\) is an adjacency matrix (\(a_{up}=1\) means the edge between node \(u\) and \(o\) exists and \(0\) otherwise), \(\mathbf{X}=\{\mathbf{x}_{u}\}_{N\times D}\) is a feature matrix with \(\mathbf{x}_{u}\) a \(D\)-dimensional node feature vector of node \(u\), and \(\mathbf{Y}=\{y_{u}\}_{N\times C}\) with \(y_{u}\) the label vector of node \(u\) and \(C\) class number. The node labels are partially observed as training data, based on which the node-level prediction aims to predict the unobserved labels for testing nodes in the graph using node features and graph structures. The latter is often achieved via a GNN model, denoted as \(h_{w}\), that yields predicted node labels \(\hat{\mathbf{Y}}=h_{w}(\mathbf{A},\mathbf{X})\) and is optimized with the classification loss \(w^{*}=\arg\min_{w}=\mathcal{L}(\hat{\mathbf{Y}},\mathbf{Y})\) using observed labels from training nodes.

**Closed-World Graph Structure Learning (GLCW).** The standard graph structure learning for node-level predictive tasks trains a graph structure learner \(g_{\theta}\) to refine the given structure, i.e., \(\hat{\mathbf{A}}=g_{\theta}(\mathbf{A},\mathbf{X})\), over which the GNN classifier \(h_{w}\) conducts message passing for producing node representations and predictions. The \(g_{\theta}\) is expected to produce optimal graph structures that can give rise to satisfactory downstream classification performance of the GNN classifier. Formally speaking, the goal for training \(g_{\theta}\) along with \(h_{w}\) can be expressed as a nested optimization problem:

\[\theta^{*}=\arg\min_{w}\min_{\theta}\mathcal{L}\left(h_{w}(g_{\theta}(\mathbf{ A},\mathbf{X}),\mathbf{X}),\mathbf{Y}\right). \tag{1}\]

The above formulation of graph structure learning under closed-world assumptions constrains the training and testing nodes in the same graph, which requires \(g_{\theta}\) to be trained from scratch on each graph dataset. Since \(g_{\theta}\) is often much more complicated (e.g., with orders-of-magnitude more trainable parameters) and difficult for optimization (due to the bi-level optimization (1)) than the GNN \(h_{w}\), the GLCW would lead to undesired inefficiency and vulnerability for serious over-fitting (due to limited labeled information).

**Open-World Graph Structure Learning (GLOW).** In this work, we turn to a new learning paradigm that generalizes graph structure learning to open-world assumptions, borrowing the concepts of domain generalization (Sutskever et al., 2017) and out-of-distribution generalization (Sutskever et al., 2017), more broadly. Specifically, assume that we are given multiple source graphs, denoted as \(\{g_{m}^{s}\}_{m=1}^{M}=\{(\mathbf{A}_{m}^{s},\mathbf{X}_{m}^{s},\mathbf{Y}_{ m}^{s})\}_{m=1}^{M}\), and a target graph \(\mathcal{G}^{t}=(\mathbf{A}^{t},\mathbf{X}^{t},\mathbf{Y}^{t})\), whose distribution is often different from any source graph. The goal is to train a universal structure learner \(g_{\theta}\) on source graphs which can be directly used for inference on the target graph without any re-training or fine-tuning. The trained structure learner is expected to produce desired graph structures that can bring up better downstream classification of a GNN classifier optimized for the target graph.

More specifically, we consider a one-to-many framework that coordinates a shared graph structure learner \(g_{\theta}\) and multiple dataset-specific GNNs \(\{h_{w_{m}}\}_{m=1}^{M}\), where \(h_{w_{m}}\) with independent parameterization \(w_{m}\) is optimized for a given source graph \(\mathcal{G}_{m}^{s}\). With the aim of learning a universal \(g_{\theta}\) that can generalize to new unseen target graphs, our training goal can be formulated as the following bi-level optimization problem:

\[\theta^{*}=\arg\min_{\theta}\min_{w_{1},\cdots,w_{M}}\sum_{m=1}^{M}\mathcal{L} \left(h_{w_{m}}(g_{\theta}(\mathbf{A}_{m}^{s},\mathbf{X}_{m}^{s}),\mathbf{X}_{ m}^{s}),\mathbf{Y}_{m}^{s}\right), \tag{2}\]

Figure 1. Illustration of Open-World Graph Structure Learning. In a diverse set of source graphs, we train multiple dataset-specific GNNs and a shared structure learner. In the target graph, we directly utilize the learned structure learner and only need to train a new GNN.
where the inner optimization is a multi-task learning objective. Generally, (2) aims at finding an optimal \(g_{\theta}\) that can jointly minimize the classification loss induced by \(M\) GNN models, each trained for a particular source graph. After training, we can directly adapt \(g_{\theta^{*}}\) to the target graph for testing purpose, and only need to train a GNN \(h_{w}\) on the target graph:

\[w^{*}=\operatorname*{arg\,min}_{w}\mathcal{L}\left(h_{w}(g_{\theta^{*}}( \mathbf{A}^{t},\mathbf{X}^{t}),\mathbf{X}^{t}),\mathbf{Y}^{t}\right). \tag{3}\]

## 3. Proposed Model

To handle the above problem, we present an end-to-end learning framework GraphGLOW that guides the central graph structure learner to learn adaptive message-passing structures exploited by multiple GNNs. The overview of GraphGLOW is shown in Fig. 2.

The fundamental challenge of GLOW lies in how to model and capture the generalizable patterns among adaptive structures of different graphs. To this end, we first take a data-generative perspective that treats the inputs and inter-mediate results as random variables and investigate into their dependency, based on which we present the high-level model formulation in a probabilistic form (Sec. 3.1). Then we proceed to instantiate the model components (Sec. 3.2). Finally, we discuss differentiable training approaches for optimization (Sec. 3.3).

### Model Formulation

To commence, we characterize the data generation process by a latent variable model, based on which we derive the formulation of our method. We treat the latent graph \(\hat{\mathbf{A}}\) (given by \(g_{\theta}\)) as a latent variable whose prior distribution is given by \(p(\hat{\mathbf{A}}|\mathbf{A},\mathbf{X})\). The prior distribution reflects how one presumed on the latent structures before observed labels arrive. Then, the prediction is given by a predictive distribution \(p(\mathbf{Y}|\hat{\mathbf{A}},\mathbf{X})\). The learning objective aims at maximizing the log-likelihood of observed labels, which can be written as: \(\log p(\mathbf{Y}|\mathbf{A},\mathbf{X})=\log\int_{\hat{\mathbf{A}}}p(\mathbf{ Y}|\mathbf{A},\mathbf{X},\hat{\mathbf{A}})p(\hat{\mathbf{A}}|\mathbf{A}, \mathbf{X})d\hat{\mathbf{A}}\). To estimate latent graphs that could enhance message passing for downstream tasks, one plausible way is to sample from the posterior, i.e., \(p(\hat{\mathbf{A}}|\mathbf{Y},\mathbf{A},\mathbf{X})\), conditioned on the labels from downstream tasks. Using the Bayes' rule, we have

\[p(\hat{\mathbf{A}}|\mathbf{Y},\mathbf{A},\mathbf{X})=\frac{p(\mathbf{Y}| \mathbf{A},\mathbf{X},\hat{\mathbf{A}})p(\hat{\mathbf{A}}|\mathbf{A},\mathbf{X })}{\hat{\mathbf{J}}_{\hat{\mathbf{A}}}p(\mathbf{Y}|\mathbf{A},\mathbf{X}, \hat{\mathbf{A}})p(\hat{\mathbf{A}}|\mathbf{A},\mathbf{X})d\hat{\mathbf{A}}}. \tag{4}\]

However, the integration over \(\hat{\mathbf{A}}\) in the denominator is intractable for computation due to the exponentially large space of \(\hat{\mathbf{A}}\).

To circumvent the difficulty, we can introduce a variational distribution \(q(\hat{\mathbf{A}}|\mathbf{A},\mathbf{X})\) over \(\hat{\mathbf{A}}\) as an approximation to \(p(\hat{\mathbf{A}}|\mathbf{Y},\mathbf{A},\mathbf{X})\). We can sample latent graphs from \(q(\hat{\mathbf{A}}|\mathbf{A},\mathbf{X})\), i.e., instantiate it as the structure learner \(g_{\theta}\), and once \(q(\hat{\mathbf{A}}|\mathbf{A},\mathbf{X})=p(\hat{\mathbf{A}}|\mathbf{Y}, \mathbf{A},\mathbf{X})\), we could have samples from the posterior that ideally generates the optimal graph structures for downstream prediction. By this principle, we can start with minimizing the Kullback-Leibler divergence between \(q\) and \(p\) and derive the learning objective as follows:

\[\mathcal{D}_{KL}(q(\hat{\mathbf{A}}|\mathbf{A},\mathbf{X})||p( \hat{\mathbf{A}}|\mathbf{Y},\mathbf{A},\mathbf{X}))\] \[=-\underbrace{\mathbb{E}_{\hat{\mathbf{A}}-q(\hat{\mathbf{A}}| \mathbf{A},\mathbf{X})}}_{\text{Evidence Lower Bound}}+\log p(\mathbf{Y}| \mathbf{A},\mathbf{X}). \tag{5}\]

Based on this equation, we further have the inequality which bridges the relationship between the Evidence Lower Bound (ELBO)

Figure 2. Illustration of the proposed framework GraphGLOW targeting open-world graph structure learning. The middle part of the figure presents the training process for the structure learner together with multiple dataset-specific GNNs on source graphs. In (a)-(e) we illustrate the details of graph structure learner, backbone GNN, iterative training process, training procedure and transferring procedure. When the training is finished, the structure learner is fixed and we only need to train a dataset-specific GNN network on new target graph with latent structures inferred by the well-trained structure learner.
and observed data log-likelihood:

\[\log p(\mathrm{Y}|\mathbf{A},\mathbf{X})\geq\mathbb{E}_{\hat{\mathbf{A}}\sim q( \hat{\mathbf{A}}|\mathbf{A},\mathbf{X})}\left[\log\frac{p(\mathrm{Y}|\mathbf{A},\mathbf{X},\hat{\mathbf{A}})p(\hat{\mathbf{A}}|\mathbf{A},\mathbf{X})}{q( \hat{\mathbf{A}}|\mathbf{A},\mathbf{X})}\right]. \tag{6}\]

The equality holds if and only if \(\mathcal{D}_{KL}(q(\hat{\mathbf{A}}|\mathbf{A},\mathbf{X})\|p(\hat{\mathbf{A}} |\mathrm{Y},\mathbf{A},\mathbf{X}))=0\). The above fact suggests that we can optimize the ELBO as a surrogate for \(\log p(\mathrm{Y}|\mathbf{A},\mathbf{X})\) which involves the intractable integration. More importantly, when the ELBO is optimized w.r.t. \(q\) distribution, the variational bound is lifted to the original log-likelihood and one has \(q(\hat{\mathbf{A}}|\mathbf{A},\mathbf{X})=p(\hat{\mathbf{A}}|\mathrm{Y}, \mathbf{A},\mathbf{X})\), i.e., the variational distribution equals to the true posterior, which is what we expect.

Pushing further and incorporating source graphs \(\mathcal{G}_{m}\) (we omit the superscript for simplicity), we arrive at the following objective:

\[\mathbb{E}_{\mathcal{G}_{m}\sim p(\mathcal{G})}\left[\mathbb{E}_{ \hat{\mathbf{A}}\sim q_{\mathcal{G}}(\hat{\mathbf{A}}|\mathbf{A}=\mathbf{A}_{ m},\mathbf{X}=\mathbf{X}_{m})}\left[\log p_{\mathrm{w}_{m}}(\mathrm{Y}| \mathbf{A}=\mathbf{A}_{m},\mathbf{X}=\mathbf{X}_{m},\hat{\mathbf{A}})\right.\right.\] \[\left.\left.+\log p_{0}(\hat{\mathbf{A}}|\mathbf{A}=\mathbf{A}_{ m},\mathbf{X}=\mathbf{X}_{m})-\log q_{\mathcal{G}}(\hat{\mathbf{A}}|\mathbf{A}= \mathbf{A}_{m},\mathbf{X}=\mathbf{X}_{m})\right]\right].\]

Here we instantiate \(q(\hat{\mathbf{A}}|\mathbf{A},\mathbf{X})\) as the shared structure learner \(g_{\theta}\), \(p(\hat{\mathbf{A}}|\mathbf{A},\mathbf{X})\) as a (shared) non-parametric prior distribution \(p_{0}\) for latent structures, and \(p(\mathrm{Y}|\mathbf{A},\mathbf{X},\hat{\mathbf{A}})\) as the dataset-specific GNN model \(h_{\mathbf{w}_{m}}\), to suit the framework for our formulated problem in Section 2. The formulation of (7) shares the spritts with Bayesian meta learning (Hendle, 2017). We can treat the GNN training as a dataset-specific learning task and latent graph as a certain 'learning algorithm' or 'hyper-parameter', so (7) essentially aims at learning a structure learner that can yield desirable 'learning algorithm' for each specific learning task on graphs. Furthermore, the three terms in (7) have distinct effects: i) the predictive term \(\log p_{\mathrm{w}_{m}}\) acts as a supervised classification loss; ii) the prior term \(\log p_{0}\) serves for regularization on the generated structures; iii) the third term, which is essentially the entropy of \(q_{\theta}\), penalizes high confidence on certain structures.

To sum up, we can optimize (7) with joint learning of the structure learner \(g_{\theta}\) and GNN models \(\{h_{\mathbf{w}_{m}}\}_{m=1}^{M}\) on source graphs \(\{\mathcal{G}_{m}\}_{m=1}^{M}\) for training the structure learner. After that, we can generalize the well-trained \(g_{\theta^{*}}\) to estimate latent graph structures for a new target graph \(\mathcal{G}^{t}=(\mathbf{A}^{t},\mathbf{X}^{t})\) and only need to train the GNN model \(h_{\mathbf{w}}\) w.r.t. the predictive objective with fixed \(\theta^{*}\):

\[\mathbb{E}_{\hat{\mathbf{A}}\sim q_{\mathcal{G}^{t}}(\hat{\mathbf{A}}|\mathbf{ A}=\mathbf{A}^{t},\mathbf{X}=\mathbf{X}^{t})}\left[\log p_{\mathrm{w}}(\mathrm{Y}| \mathbf{A}=\mathbf{A}^{t},\mathbf{X}=\mathbf{X}^{t},\hat{\mathbf{A}})\right]. \tag{8}\]

We next discuss how to specify \(g_{\theta}\), \(h_{\mathbf{w}_{m}}\) and \(p_{0}\) with special focus on their expressiveness and efficiency in Section 3.2. Later, we present the details for loss computation and model training based on the formulation stated above in Section 3.3.

### Model Instantiations

#### 3.2.1. Instantiation for \(q_{\theta}(\hat{\mathbf{A}}|\mathbf{A},\mathbf{X})\)

The variational distribution aims at learning the conditional distribution that generates suitable latent structures for message passing based on input observations. A natural means is to assume each edge of the latent graph as a Bernoulli random variable and the distribution \(q\) is a product of \(N\times N\) independent Bernoulli random variables (Brandt, 2017; Goyal et al., 2017).

The graph structure learner \(g_{\theta}\) can be used for predicting the Bernoulli parameter matrix. To accommodate the information from node features and graph structure, we can use the node representation, denoted as \(\mathbf{z}_{u}\in\mathbb{R}^{d}\), where \(d\) is the embedding dimension, to compute the edge probability \(a_{uw}\) for edge \((u,v)\) as

\[a_{uw}=\delta\left(\frac{1}{H}\sum_{h=1}^{H}s(\mathbf{w}_{h}^{1}\odot\mathbf{z} _{u},\mathbf{w}_{h}^{2}\odot\mathbf{z}_{u})\right), \tag{9}\]

where \(s(\cdot,\cdot)\) is a similarity function for two vectors, \(\odot\) denotes Hadamard product, \(\delta\) is a function that converts the input into values within \([0,1]\) and \(\mathbf{w}_{h}^{1},\mathbf{w}_{h}^{2}\in\mathbb{R}^{d}\) are two weight vectors of the \(h\)-th head. Common choices for \(s(\cdot,\cdot)\) include simple dot-product, cosine distance (K
where \(\mathbf{W}^{(l)}\in\mathbb{R}^{d\times d}\) is a weight matrix, \(\sigma\) is non-linear activation, and \(\mathbf{D}\) denotes a diagonal degree matrix from input graph \(\mathbf{A}\) and \(\mathbf{Z}^{(l)}=\{\mathbf{z}_{u}^{(l)}\}_{N\times d}\) is a stack of node representations at the \(l\)-th layer.

With the estimated latent graph \(\hat{\mathbf{A}}=\hat{\mathbf{B}}_{1}\hat{\mathbf{B}}_{2}\), we perform message passing \(\mathrm{MP}_{2}(\cdot)\) in a two-step fashion to update node representations:

\[\text{i) node-to-pivot passing:}\;\mathbf{C}^{(l+\frac{1}{2})} =\mathrm{RowNorm}(\Gamma^{\top})\mathbf{Z}^{(l)}, \tag{12}\] \[\text{ii) pivot-to-node passing:}\;\mathbf{C}^{(l+1)} =\mathrm{RowNorm}(\Gamma)\mathbf{C}^{(l+\frac{1}{2})}, \tag{11}\]

where \(\mathbf{C}^{(l+\frac{1}{2})}\) is an intermediate node representation and \(\Gamma=\{\alpha_{uw}\}_{N\times P}\) is the node-pivot similarity matrix calculated by (9). Such a two-step procedure can be efficiently conducted within \(O(NP)\) time and space complexity.

Despite that the feature propagation on the estimated latent structure could presumably yield better node representations, the original input graph structures also contain useful information, such as effective inductive bias (Bang et al., 2017). Therefore, we integrate two message-passing functions to compute layer-wise updating for node representations:

\[\mathbf{Z}^{(l+1)}=\sigma\left(\lambda\mathrm{MP}_{1}(\mathbf{Z}^{(l)}, \mathbf{A})\mathbf{W}^{(l)}+(1-\lambda)\mathrm{MP}_{2}(\mathbf{Z}^{(l)},\hat{ \mathbf{A}})\mathbf{W}^{(l)}\right), \tag{13}\]

where \(\lambda\) is a trading hyper-parameter that controls the concentration weight on input structures. Such design could also improve the training stability by reducing the impact from large variation of latent structures through training procedure.

With \(L\) GNN layers, one can obtain the prediction \(\hat{\mathbf{Y}}\) by setting \(\hat{\mathbf{Y}}=\mathbf{Z}^{(L)}\) and \(\mathbf{W}^{(L-1)}\in\mathbb{R}^{d\times C}\) where \(C\) is the number of classes. Alg. 1 shows the feed-forward computation of message passing.

#### 3.2.3. Instantiation for \(p_{0}(\hat{\mathbf{A}}|\mathbf{A},\mathbf{X})\)

The prior distribution reflects how we presume on the latent graph structures without the information of observed labels. In other words, it characterizes how likely a given graph structure could provide enough potential for feature propagation by GNNs. The prior could be leveraged for regularization on the estimated latent graph \(\hat{\mathbf{A}}\). In this consideration, we choose the prior as an energy function that quantifies the smoothness of the graph:

\[p_{0}(\hat{\mathbf{A}}|\mathbf{X},\mathbf{A})\propto\exp\left(-\alpha\sum_{ \mathbf{z},\mathbf{z}}\hat{\mathbf{A}}_{uw}\|\mathbf{x}_{u}-\mathbf{x}_{v}\| _{2}^{2}-\rho\|\hat{\mathbf{A}}\|_{F}^{2}\right), \tag{14}\]

where \(\|\cdot\|_{F}\) is the Frobenius norm. The first term in (14) measures the smoothness of the latent graph (Bang et al., 2017), with the hypothesis that graphs with smoother feature has lower energy (i.e., higher probability). The second term helps avoiding too large node degrees (Gan et al., 2017). The hyperparameters \(\alpha\) and \(\rho\) control the strength for regularization effects.

While we can retrieve the latent graph via \(\hat{\mathbf{A}}=\hat{\mathbf{B}}_{1}\hat{\mathbf{B}}_{2}\), the computation of (14) still requires \(O(N^{2})\) cost. To reduce the overhead, we apply the regularization on the \(P\times P\) pivot-pivot adjacency matrix \(\tilde{\mathbf{E}}=\hat{\mathbf{B}}_{2}\hat{\mathbf{B}}_{1}\) as a proxy regularization:

\[\begin{split}\mathcal{R}(\hat{\mathbf{E}})&=\log p _{0}(\hat{\mathbf{A}}|\mathbf{X},\mathbf{A})\\ &\approx-\alpha\sum_{P,q}\hat{\mathbf{E}}_{pq}\|\mathbf{x}_{p}^{ \prime}-\mathbf{x}_{q}^{\prime}\|_{2}^{2}-\rho\|\hat{\mathbf{E}}\|_{F}^{2}, \end{split} \tag{15}\]

where \(\mathbf{x}_{p}^{\prime}\) denotes the input feature of the \(p\)-th pivot node.

### Model Training

For optimization with (7), we proceed to derive the loss functions and updating gradients for \(\theta\) and \(w_{m}\) based on the three terms \(\mathbb{E}_{qq}\left[\log p_{w_{m}}\right]\), \(\mathbb{E}_{qq}\left[\log p_{0}\right]\) and \(\mathbb{E}_{qq}\left[\log q_{\theta}\right]\).

#### 3.3.1. Optimization for \(\mathbb{E}_{qq}\left[\log p_{w_{m}}\right]\)

The optimization difficulty stems from the expectation over \(q_{\theta}\), where the sampling process is non-differentiable and hinders back-propagation. Common strategies for approximating the sampling for discrete random variables include Gumbel-Softmax trick (Gumbel and Softmax, 1998) and REINFORCE trick (Srivastava et al., 2017). However, both strategies yield a sparse graph structure each time of sampling, which could lead to high variance for the prediction result \(\log p_{w_{m}}(\mathbf{Y}|\mathbf{A},\mathbf{X},\hat{\mathbf{A}})\) produced by message passing over a sampled graph. To mitigate the issue, we alternatively adopt the Normalized Weighted Geometric Mean (NWGM) (Srivastava et al., 2017) to move the outer expectation into the feature-level. Specifically, we have (see Appendix A for detailed derivations)

\[\begin{split}&\nabla_{\theta}\mathbb{E}_{qq}(\hat{\mathbf{A}}| \mathbf{A},\mathbf{X})\left[\log p_{w_{m}}(\mathbf{Y}|\mathbf{A},\mathbf{X}, \hat{\mathbf{A}})\right]\\ &\approx\nabla_{\theta}\log p_{w_{m}}(\mathbf{Y}|\mathbf{A}, \mathbf{X},\hat{\mathbf{A}}=\mathbb{E}_{qq\left(\hat{\mathbf{A}}|\mathbf{X}, \mathbf{X}\right)}[\hat{\mathbf{A}}]).\end{split} \tag{16}\]

We denote the opposite of the above term as \(\nabla_{\theta}\mathcal{L}_{s}(\theta)\). The gradient w.r.t. \(w_{m}\) can be similarly derived. The above form is a biased estimation for the original objective, yet it can reduce the variance from sampling and also improve training efficiency (without the need of message passing over multiple sampled graphs).(16) induces the supervised cross-entropy loss.

#### 3.3.2. Optimization for \(\mathbb{E}_{qq}\left[\log p_{0}\right]\)

As for the second term in (7), we adopt the REINFORCE trick, i.e., policy gradient, to tackle the non-differentiability of sampling from \(q_{\theta}\). Specifically, for each feed-forward computation, we sample from the Bernoulli distribution for each edge given by the estimated node-pivot similarity matrix, i.e., \(Bernoulli(\alpha_{up})\), and obtain the sampled latent bipartite graph \(\hat{\mathbf{B}}_{1}\) and subsequently have \(\hat{\mathbf{E}}=\hat{\mathbf{B}}_{1}\hat{\mathbf{B}}_{2}=\hat{\mathbf{B}}_{1} \hat{\mathbf{B}}_{1}^{\top}\). The probability for the latent structure could be computed by

\[\pi_{\theta}(\hat{\mathbf{E}})=\prod_{u,p}\left(\hat{\mathbf{B}}_{1,up}\alpha_{up }+(1-\hat{\mathbf{B}}_{1,up})\cdot(1-\alpha_{up})\right). \tag{17}\]

Denote \(\hat{\mathbf{E}}_{k}\) as the sampled result at the \(k\)-th time, we can independently sample \(K\) times and obtain \(\{\hat{\mathbf{E}}_{k}\}_{k=1}^{K}\) and \(\{\pi_{\theta}(\hat{\mathbf{E}}_{k})\}_{k=1}^{K}\). Recall

Figure 3. Illustration for scalable structure learning message passing, which reduces algorithmic complexity from \(O(N^{2})\) to \(O(Np)\). We choose \(P\) nodes as pivots and convert the \(N\times N\) matrix to the product of two \(N\times P\) node-pivot matrices (where the message passing is executed with two steps, i.e., node-to-pivot and pivot-to-node.)
that the regularization reward from \(\log p_{0}\) has been given by (14). The policy gradient (Srivastava et al., 2017) yields the gradient of loss for \(\theta\) as

\[\begin{split}\nabla_{\theta}\mathcal{L}_{r}(\theta)&=- \nabla_{\theta}\mathbb{E}_{\hat{\mathbf{A}}-q(\hat{\mathbf{A}}|\mathbf{X}, \mathbf{A})}\left[\log p_{0}(\hat{\mathbf{A}}|\mathbf{X},\mathbf{A})\right]\\ &\approx-\nabla_{\theta}\frac{1}{K}\sum_{k=1}^{K}\log\pi_{\theta} (\hat{\mathbf{E}}_{k})\left(\mathcal{R}(\hat{\mathbf{E}}_{k})-\overline{ \mathcal{R}}\right),\end{split} \tag{17}\]

where \(\overline{\mathcal{R}}\) acts as a baseline function by averaging the regularization rewards \(\mathcal{R}(\hat{\mathbf{E}}_{k})\) in one feed-forward computation, which helps to reduce the variance during policy gradient training (Srivastava et al., 2017).

#### 3.3.3. Optimization with \(\mathbb{E}_{q_{0}}\left[\log q_{\theta}\right]\)

The last entropy term for \(q_{\theta}\) could be directly computed by

\[\begin{split}\mathcal{L}_{e}(\theta)&=\mathbb{E}_{ \hat{\mathbf{A}}-q(\hat{\mathbf{A}}|\mathbf{X},\mathbf{A})}\left[\log q(\hat{ \mathbf{A}}|\mathbf{X},\mathbf{A})\right]\\ &\approx\frac{1}{NP}\sum_{u=1}^{N}\sum_{p=1}^{P}\left[\alpha_{up }\log\alpha_{up}+(1-\alpha_{up})\log(1-\alpha_{up})\right],\end{split} \tag{18}\]

where we again adopt the node-pivot similarity matrix as a proxy for the estimated latent graph.

#### 3.3.4. Iterative Structure Learning for Acceleration

A straightforward way is to consider once structure inference and once GNN's message passing for prediction in each feed-forward computation. To enable structure learning and GNN learning mutually reinforce each other (Bengio et al., 2017), we consider multiple iterative updates of graph structures and node representations before once back-propagation. More specifically, in each epoch, we repeatedly update node representations \(\mathbf{Z}^{t}\) (where the superscript \(t\) denotes the \(t\)-th iteration) and latent graph \(\hat{\mathbf{A}}^{t}\) until a given maximum budget is achieved. To accelerate the training, we aggregate the losses \(\mathcal{L}^{t}\) in each iteration step for parameter updating. As different graphs have different feature space, we utilize the first layer of GNN as an encoder at the very beginning and then feed the encoded representations to structure learner. The training algorithm for structure learner \(g_{\theta}\) on source graphs is described in Alg. 2 (in the appendix) where we train structure learner for multiple episodes and in each episode, we train \(g_{\theta}\) on each source graph for several epochs. In testing, the well-trained \(g_{\theta}\) is fixed and we train a GNN \(h_{\mathbf{w}}\) on the target graph with latent structures inferred by \(g_{\theta}\), as described in Alg. 3.

## 4. Related Works

Graph Neural NetworksGraph neural networks (GNNs) (Garon et al., 2017; Ganin et al., 2017; Ganin et al., 2017; Ganin et al., 2017; Ganin et al., 2017; Ganin et al., 2017) have achieved impressive performances in modeling graph-structured data. Nonetheless, there is increasing evidence suggesting GNNs' deficiency for graph structures that are inconsistent with the principle of message passing. One typical situation lies in non-homophilous graphs (Srivastava et al., 2017), where adjacent nodes tend to have dissimilar features/labels. Recent studies devise adaptive feature propagation/aggregation to tackle the heterophily (Ganin et al., 2017; Ganin et al., 2017; Ganin et al., 2017; Ganin et al., 2017). Another situation stems from graphs with noisy or spurious links, for which several works propose to purify the observed structures for more robust node representations (Ganin et al., 2017; Ganin et al., 2017). Our work is related to these works by searching adaptive graph structures that is suitable for GNN's message passing. Yet, the key difference is that our method targets learning a new graph out of the scope of input one, while the above works focus on message passing within the input graph.

Graph Structure learningTo effectively address the limitations of GNNs' feature propagation within observed structures, many recent works attempt to jointly learn graph structures and the GNN model. For instance, (Ganin et al., 2017) models each edge as a Bernoulli random variable and optimizes graph structures along with the GCN. To exploit enough information from observed structure for structure learning, (Ganin et al., 2017) proposes a metric learning approach based on RBF kernel to compute edge probability with node representations, while (Ganin et al., 2017) adopts attention mechanism to achieve the similar goal. Furthermore, (Bengio et al., 2017) considers an iterative method that enables mutual reinforcement between learning graph structures and node embeddings. Also, (Ganin et al., 2017) presents a probabilistic framework that views the input graph as a random sample from a collection modeled by a parametric random graph model. (Ganin et al., 2017; Ganin et al., 2017) harnesses variational inference to estimate a posterior of graph structures and GNN parameters. While learning graph structures often requires \(O(N^{2})\) complexity, a recent work (Ganin et al., 2017) proposes an efficient Transformer that achieves latent structure learning in each layer with \(O(N)\) complexity. However, though these methods have shown promising results, they assume training nodes and testing nodes are from the same graph and consider only one graph. By contrast, we consider graph structure learning under the cross-graph setting and propose a general framework to learn a shared structure learner which can generalize to target graphs without any re-training.

Out-of-Distribution Generalization on GraphsDue to the demand for handling testing data in the wild, improving the capability of the neural networks for performing satisfactorily on out-of-distribution data has received increasing attention (Ganin et al., 2017; Ganin et al., 2017; Ganin et al., 2017; Ganin et al., 2017; Ganin et al., 2017). Recent studies, e.g., (Ganin et al., 2017; Ganin et al., 2017; Ganin et al., 2017) explore effective treatments for tackling general distribution shifts on graphs, and there are also works focusing on particular categories of distribution shifts like size generalization (Ganin et al., 2017), molecular scaffold generalization (Ganin et al., 2017), feature/attribute shifts (Ganin et al., 2017; Ganin et al., 2017), topological shifts (Ganin et al., 2017), etc. To the best of our knowledge, there is no prior works considering OOD generalization in the context of graph structure learning. In our case, the target graph, where the structure learner is expected to yield adaptive structures, can have disparate distributions than the source graphs. The distribution shifts could potentially stem from feature/label space, graph sizes or domains (e.g., from social networks to citation networks). As the first attempt along this path, our work can fill the research gap and enable the graph structure learning model to deal with new unseen graphs in an open world.

## 5. Experiments

We apply GraphGLOW to real-world datasets for node classification to test the efficacy of proposed structure learner for boosting performance of GNN learning on target graphs with distribution shifts from source graphs. We specify the backbone GNN network for GraphGLOW as a two-layer GCN (Ganin et al., 2017). We focus on the following research questions:

* **1)** How does GraphGLOW perform compared with directly training GNN models on input structure of target graphs?
\(\bullet\) 2) How does GraphGLOW perform compared to state-of-the-art structure learning models that are directly trained on target datasets in terms of both accuracy and training time?

\(\bullet\) 3) Are the proposed components of GraphGLOW effective and necessary for the achieved performance?

\(\bullet\) 4) What is the impact of hyper-parameter on performance and what is the impact of attack on observed edges?

\(\bullet\) 5) What is the property of inferred latent graphs and what generalizable pattern does the structure learner capture?

### Experimental Protocols

**Datasets.** Our experiments are conducted on several public graph datasets. First we consider three commonly used citation networks Cora, CiteSeer and PubMed. We use the same splits as in (Zhou et al., 2017). These three datasets have high homophily ratios (i.e., adjacent nodes tend to have similar labels) (Zhou et al., 2017). Apart from this, we also consider four social networks from Facebook-100 (Zhou et al., 2017), which have low homophily ratios. Readers may refer to Appendix B for more dataset information like splitting ratios.

**Competitors.** We mainly compare with GCN (Kipf and Welling, 2015), the GNN counterpart trained on input structure, for testing the efficacy of produced latent graphs by GraphGLOW. As further investigation, we also compare with other advanced GNN models: GraphSAGE (Kipf and Welling, 2015), GAT (Zhou et al., 2017), APPNP (Kipf and Welling, 2015), H\({}_{2}\)GCN (Zhou et al., 2017) and GPRGNN (Gupta et al., 2017). Here APPNP, H\({}_{2}\)GCN and GPRGNN are all strong GNN models equipped with adaptive feature propagation and high-order aggregation. For these pure GNN models, the training and testing are considered on (the same) target graphs. Furthermore, we compete GraphGLOW with state-of-the-art graph structure learning models, IDS (Kipf and Welling, 2015), IDGL (Chen et al., 2016) and VGCN (Chen et al., 2016). Since these models are all designed for training on one dataset from scratch, we directly train them on the target graph and they in principle could yield better performance than GraphGLOW.

We also consider variants of GraphGLOW as baselines. We replace the similarity function \(s\) with attention-based structure learner, denoted as GraphGLOW\({}_{\text{at}}\), which follows the same training scheme as GraphGLOW. Besides, we consider some non-parametric similarity functions like dot-product, KNN and cosine distance (denoted as GraphGLOW\({}_{\text{dp}}\), GraphGLOW\({}_{\text{kmn}}\) and GraphGLOW\({}_{\text{cos}}\), respectively). For these models, we only need to train the GNN network on target graphs with the non-parametric structure learners yielding latent structures. In addition, we introduce a variant GraphGLOW\({}^{*}\) that shares the same architecture as GraphGLOW and is directly trained on target graphs. Also, GraphGLOW\({}^{*}\) in principle could produce superior results than GraphGLOW. We report the test accuracy given by the model that produces the highest validation accuracy within 500 training epochs.

### In-domain Generalization

We first consider transferring within social networks or citation networks. The results are reported in Table 1 where for each social network (resp. citation network) as the target, we use the other social networks (resp. citation networks) as the source datasets. GraphGLOW performs consistently better than GCN, i.e., the counterpart using observed graph for message passing, which proves that GraphGLOW can capture generalizable patterns for desirable message-passing structure for unseen datasets that can indeed boost the GCN backbone's performance on downstream tasks. In particular, the improvement over GCN is over 5% on Cornell5 and Reed98, two datasets with low homophily ratios (as shown in Table 3). The reason is that for non-homophilous graphs where the message passing may propagate inconsistent signals (as mentioned in Section 1), the GNN learning could better benefits from structure learning than homophilous graphs. Furthermore, compared to other strong GNN models, GraphGLOW still achieves slight improvement than the best competitors though the backbone GCN network is less expressive. One could expect further performance gain by GraphGLOW if we specify the GNN backbone as other advanced architectures.

In contrast with non-parametric structure learning models and GraphGLOW\({}_{\text{at}}\), GraphGLOW outperforms them by a large margin throughout all cases, which verifies the superiority of our design of multi-head weighted similarity function that can accommodate multi-faceted diverse structural information. Compared with GraphGLOW\({}^{*}\), GraphGLOW performs on par with and even exceeds it on

\begin{table}
\begin{tabular}{|c|l c c c c c c c|} \hline
**Type** & **Method** & **Cornell5** & **Johns.55** & **Amherst41** & **Reed98** & **Cora** & **CiteSeer** & **PubMed** \\ \hline \multirow{8}{*}{**Pure**} & GCN & 68.6 \(\pm\) 0.5 & 70.8 \(\pm\) 1.0 & 65.8 \(\pm\) 1.6 & 60.8 \(\pm\) 1.6 & 81.6 \(\pm\) 0.4 & 71.6 \(\pm\) 0.3 & 78.8 \(\pm\) 0.6 \\  & SAGE & 68.7 \(\pm\) 0.8 & 67.5 \(\pm\) 0.9 & 66.3 \(\pm\) 1.8 & 63.9 \(\pm\) 1.9 & 81.4 \(\pm\) 0.6 & 71.6 \(\pm\) 0.5 & 78.6 \(\pm\) 0.7 \\  & GAT & 69.6 \(\pm\) 1.2 & 69.4 \(\pm\) 0.7 & 68.7 \(\pm\) 2.1 & 64.5 \(\pm\) 2.5 & 83.0 \(\pm\) 0.7 & 72.1 \(\pm\) 1.1 & 79.0 \(\pm\) 0.4 \\  & GPR & 68.8 \(\pm\) 0.7 & 69.6 \(\pm\) 1.3 & 66.2 \(\pm\) 1.5 & 62.7 \(\pm\) 2.0 & 83.1 \(\pm\) 0.7 & 72.4 \(\pm\) 0.8 & 79.6 \(\pm\) 0.5 \\  & APPNP & 68.5 \(\pm\) 0.8 & 69.1 \(\pm\) 1.4 & 65.9 \(\pm\) 1.3 & 62.3 \(\pm\) 1.5 & 82.7 \(\pm\) 0.5 & 71.9 \(\pm\) 0.5 & 79.2 \(\pm\) 0.3 \\  & H\({}_{2}\)GCN & 71.4 \(\pm\) 0.5 & 68.3 \(\pm\) 1.0 & 66.5 \(\pm\) 2.2 & 65.4 \(\pm\) 1.3 & 82.5 \(\pm\) 0.8 & 71.4 \(\pm\) 0.7 & 79.4 \(\pm\) 0.4 \\  & CPGNN & 71.1 \(\pm\) 0.5 & 68.7 \(\pm\) 1.3 & 66.7 \(\pm\) 0.8 & 63.6 \(\pm\) 1.8 & 80.8 \(\pm\) 0.4 & 71.6 \(\pm\) 0.4 & 78.5 \(\pm\) 0.7 \\ \hline \multirow{8}{*}{**Graph**} & GraphGLOW\({}_{\text{dp}}\) & 71.5 \(\pm\) 0.7 & 71.3 \(\pm\) 1.2 & 68.5 \(\pm\) 1.6 & 63.2 \(\pm\) 1.2 & 83.1 \(\pm\) 0.8 & 71.7 \(\pm\) 1.0 & 77.3 \(\pm\) 0.8 \\  & GraphGLOW\({}_{\text{kmn}}\) & 69.4 \(\pm\) 0.8 & 71.0 \(\pm\) 1.3 & 64.8 \(\pm\) 1.2 & 63.6 \(\pm\) 1.6 & 81.7 \(\pm\) 0.8 & 71.5 \(\pm\) 0.8 & 79.4 \(\pm\) 0.6 \\ \cline{1-1}  & GraphGLOW\({}_{\text{cos}}\) & 69.9 \(\pm\) 0.7 & 70.8 \(\pm\) 1.4 & 65.2 \(\pm\) 1.8 & 62.7 \(\pm\) 1.3 & 82.0 \(\pm\) 0.7 & 71.9 \(\pm\) 0.9 & 78.7 \(\pm\) 0.8 \\ \cline{1-1}  & GraphGLOW\({}_{\text{at}}\) & 69.3 \(\pm\) 0.8 & 70.9 \(\pm\) 1.3 & 65.0 \(\pm\) 1.3 & 65.0 \(\pm\) 1.7 & 81.9 \(\pm\) 0.9 & 71.3 \(\pm\) 0.7 & 78.8 \(\pm\) 0.6 \\ \cline{1-1}  & GraphGLOW & **71.8 \(\pm\) 0.9** & 71.5 \(\pm\) 0.8 & **70.6 \(\pm\) 1.4** & **66.8 \(\pm\) 1.1** & **83.5 \(\pm\) 0.6** & 73.6 \(\pm\) 0.6 & 79.8 \(\pm\) 0.8 \\ \cline{1-1}  & GraphGLOW\({}^{*}\) & 71.1 \(\pm\) 0.3 & **72.2 \(\pm\) 0.5** & 70.3 \(\pm\) 0.9 & **66.8 \(\pm\) 1.4** & **83.5 \(\pm\) 0.6** & **73.9 \(\pm\) 0.7** & **79.9 \(\pm\) 0.5** \\ \hline \end{tabular}
\end{table}
Table 1. Test accuracy (%) on target graphs for in-domain generalizations. For each social network (resp. citation network) as target dataset, we consider the other social networks (resp. citation networks) as source graphs. GraphGLOW\({}^{*}\) is an oracle model that shares the same architecture as our model GraphGLOW and is directly trained on target graphs.
Cornell5 and Amherst41. The possible reasons are two-fold. First, there exist sufficient shared patterns among citation networks (resp. social networks), which paves the way for successful generalization of GraphGLOW. Second, GraphGLOW\({}^{*}\) could sometimes overfit specific datasets, since the amount of free parameters are regularly orders-of-magnitude more than the number of labeled nodes in the dataset. The results also imply that our transfer learning approach can help to mitigate over-fitting on one dataset. Moreover, GraphGLOW can generalize structure learner to unseen graphs that is nearly three times larger than training graphs, i.e., Cornell5.

### Cross-domain Generalization

We next consider a more difficult task, transferring between social networks and citation networks. The difficulty stems from two aspects: 1) social networks and citations graphs are from distinct categories thus have larger underlying data-generating distribution gaps; 2) they have varied homophily ratios, which indicates that the observed edges play different roles in original graphs. In Table 2 we report the results. Despite the task difficulty, GraphGLOW manages to achieve superior results than GCN and also outperforms other non-parametric graph structure learning methods throughout all cases. This suggests GraphGLOW's ability for handling target graphs with distinct properties.

In Fig. 4 we further compare GraphGLOW with three state-of-the-art graph structure learning models that are directly trained on target graphs. Here we follow the setting in Table 2. The results show that even trained on source graphs that are different from the target one, GraphGLOW still performs on par with the competitors that are trained and tested on (the same) target graphs. Notably, GraphGLOW significantly reduces training time. For instance, in John Hopkins55, GraphGLOW is 6x, 9x and 40x faster than IDGL, LDS and VGCN, respectively. This shows one clear advantage of GraphGLOW in terms of training efficiency and also verifies that our model indeed helps to reduce the significant cost of training time for structure learning on target graphs.

### Ablation Studies

We conduct ablation studies to test the effectiveness of iterative learning scheme and regularization on graphs.

**Effect of Iterative Learning.** We replace the iterative learning process as a one-step prediction (i.e., once structure estimation and updating node representations in once feed-forward computation) and compare its test accuracy with GraphGLOW. The results are shown in Fig. 5(a) where we follow the setting of Table 1. The non-iterative version exhibits a considerable drop in accuracy (as large as 5.4% and 8.8% when tested on target graphs Cornell5

\begin{table}
\begin{tabular}{|c|l c c c c c c c|} \hline
**Type** & **Method** & **Cornell5** & **Johns.55** & **Amherst41** & **Reed98** & **Cora** & **CiteSeer** & **PubMed** \\ \hline \multirow{8}{*}{**GNN**} & GCN & 68.6 \(\pm\) 0.5 & 70.8 \(\pm\) 1.0 & 65.8 \(\pm\) 1.6 & 60.8 \(\pm\) 1.6 & 81.6 \(\pm\) 0.4 & 71.6 \(\pm\) 0.3 & 78.8 \(\pm\) 0.6 \\  & SAGE & 68.7 \(\pm\) 0.8 & 67.5 \(\pm\) 0.9 & 66.3 \(\pm\) 1.8 & 63.9 \(\pm\) 1.9 & 81.4 \(\pm\) 0.6 & 71.6 \(\pm\) 0.5 & 78.6 \(\pm\) 0.7 \\  & GAT & 69.6 \(\pm\) 1.2 & 69.4 \(\pm\) 0.7 & 68.7 \(\pm\) 2.1 & 64.5 \(\pm\) 2.5 & 83.0 \(\pm\) 0.7 & 72.1 \(\pm\) 1.1 & 79.0 \(\pm\) 0.4 \\  & GPR & 68.8 \(\pm\) 0.7 & 69.6 \(\pm\) 1.3 & 66.2 \(\pm\) 1.5 & 62.7 \(\pm\) 2.0 & 83.1 \(\pm\) 0.7 & 72.4 \(\pm\) 0.8 & 79.6 \(\pm\) 0.5 \\  & APPNP & 68.5 \(\pm\) 0.8 & 69.1 \(\pm\) 1.4 & 65.9 \(\pm\) 1.3 & 62.3 \(\pm\) 1.5 & 82.7 \(\pm\) 0.5 & 71.9 \(\pm\) 0.5 & 79.2 \(\pm\) 0.3 \\  & H\({}_{2}\)GCN & 71.4 \(\pm\) 0.5 & 68.3 \(\pm\) 1.0 & 66.5 \(\pm\) 2.2 & 65.4 \(\pm\) 1.3 & 82.5 \(\pm\) 0.8 & 71.4 \(\pm\) 0.7 & 79.4 \(\pm\) 0.4 \\  & CPGNN & 71.1 \(\pm\) 0.5 & 68.7 \(\pm\) 1.3 & 66.7 \(\pm\) 0.8 & 63.6 \(\pm\) 1.8 & 80.8 \(\pm\) 0.4 & 71.6 \(\pm\) 0.4 & 78.5 \(\pm\) 0.7 \\ \hline \multirow{4}{*}{**Graph Structure Learning**} & GraphGLOW\({}_{\text{dp}}\) & 71.5 \(\pm\) 0.7 & 71.3 \(\pm\) 1.2 & 68.5 \(\pm\) 1.6 & 63.2 \(\pm\) 1.2 & 83.1 \(\pm\) 0.8 & 71.7 \(\pm\) 1.0 & 77.3 \(\pm\) 0.8 \\  & GraphGLOW\({}_{\text{knn}}\) & 69.4 \(\pm\) 0.8 & 71.0 \(\pm\) 1.3 & 64.8 \(\pm\) 1.2 & 63.6 \(\pm\) 1.6 & 81.7 \(\pm\) 0.8 & 71.5 \(\pm\) 0.8 & 79.4 \(\pm\) 0.6 \\  & GraphGLOW\({}_{\text{cos}}\) & 69.9 \(\pm\) 0.7 & 70.8 \(\pm\) 1.4 & 65.2 \(\pm\) 1.8 & 62.7 \(\pm\) 1.3 & 82.0 \(\pm\) 0.7 & 71.9 \(\pm\) 0.9 & 78.7 \(\pm\) 0.8 \\  & GraphGLOW\({}_{\text{at}}\) & 69.9 \(\pm\) 1.0 & 70.4 \(\pm\) 1.5 & 64.4 \(\pm\) 1.2 & 65.0 \(\pm\) 1.7 & 82.5 \(\pm\) 0.9 & 71.8 \(\pm\) 0.8 & 78.5 \(\pm\) 0.7 \\  & GraphGLOW & **72.0 \(\pm\) 1.0** & 71.8 \(\pm\) 0.7 & 69.8 \(\pm\) 1.3 & **67.3 \(\pm\) 1.2** & 83.2 \(\pm\) 0.4 & 73.8 \(\pm\) 0.9 & 79.6 \(\pm\) 0.7 \\  & GraphGLOW\({}^{*}\) & 71.1 \(\pm\) 0.3 & **72.2 \(\pm\) 0.5** & **70.3 \(\pm\) 0.9** & 66.8 \(\pm\) 1.4 & **83.5 \(\pm\) 0.6** & **73.9 \(\pm\) 0.7** & **79.9 \(\pm\) 0.5** \\ \hline \end{tabular}
\end{table}
Table 2. Test accuracy (%) on target graphs for cross-domain generalizations. For each social network (resp. citation network) as target dataset, we consider citation networks (resp. social networks) as source graphs.

Figure 4. Comparison of test accuracy and training time with SOTA structure learning models (LDS (10), IDGL (6) and VGCN (8)). The radius of circle is proportional to standard deviation. The experiments are run on one Tesla V4 with 16 GPU memory. We adopt the same setting as Table 2 and report the results on target datasets. For Cornell5 and PubMed, the competitor models suffer out-of-memory.
and Amherst41, respectively). Therefore, the iterative updates indeed help to learn better graph structures and node embeddings, contributing to higher accuracy for downstream prediction.

**Effect of Regularization on structures.** We remove the regularization on structures (i.e., setting \(\alpha=\rho=0\)) and compare with GraphGLOW. As shown in Fig. 5(a), there is more or loss performance degradation. In fact, the regularization loss derived from the prior distribution for latent structures could help to provide some guidance for structure learning, especially when labeled information is limited.

### Hyper-parameter Sensitivity

In Fig. 7 (in the appendix), we study the variation of model's performance w.r.t. \(\lambda\) (the weight on input graphs) and \(P\) (the number of pivots) on target datasets Cora and CiteSer. Overall, the model is not sensitive to \(\lambda\)'s. For Cora, larger \(\lambda\) contributes to higher accuracy, while for CiteSer, smaller \(\lambda\) yields better performance. The possible reason is that the initial graph of Cora is more suitable for message passing (due to higher homophily ratio). For the impact of pivot number, as shown in Fig. 7(b), a moderate value of \(P\) could provide decent downstream performance.

### Robustness Analysis

In addition, we find that GraphGLOW is more immune to edge deletion attack than GCN. We randomly remove 10-50% edges of target graphs respectively, and then apply GraphGLOW and GCN. We present the results in Johns Hopkins55 in Fig. 5(b) and leave more results in Appendix D. When the drop ratio increases, the performance gap between two models becomes more significant. This is due to our structure learner's ability for learning new graph structures from node embeddings, making it less reliant on initial graph structures and more robust to attack on input edges.

### Case Study

We further probe into why our approach is effective for node classification by dissecting the learnt graph structures. Specifically, we measure the homophily ratios of learnt structures and their variance of neighborhood distributions of nodes with same labels. As nodes receive messages from neighbors in message passing, the more similar the neighborhood patterns of nodes within one class are, the easier it is for GNNs to correctly classify them (Zhu et al., 2017). We use homophily metric proposed in (Zhu et al., 2017) to measure homophily ratios. For calculation of variance of neighborhood distribution, we first calculate variance for each class, and then take weighted sum to get the final variance, where the weight is proportional to the number of nodes within corresponding class.

**Homophily Ratio.** We choose Amherst41, Johns Hopkins55 and Reed98 as target graphs, and record the homophily ratios of inferred latent structures every five epochs during training. As shown in Fig. 6(a), the homophily ratios of inferred latent graphs exhibit a clear increase as the training epochs become more and the final ratio is considerably larger than that of input graph. The results indicate that the trained structure learner incline to output more homophilous latent structures that are reckoned to be more suitable for message passing.

**Neighborhood Distribution Variance.** As shown in Fig. 6(b), the variance of neighborhood distribution of nodes with the same label is significantly smaller in our learnt structure, making it easier to classify nodes through message passing. The results also imply that high homophily ratio and similar intra-class neighborhood patterns could be two of the underlying transferable patterns of optimal message-passing structure, identified by GraphGLOW.

## 6. Conclusion

This paper proposes _Graph Structure Learning Under Cross-Graph Distribution Shift_, a new problem that requires structure learner to transfer to new target graphs without re-training and handles distribution shift. We develop a transfer learning framework that guides the structure learner to discover shared knowledge across source datasets with respect to optimal message-passing structure for boosting downstream performance. We also carefully design the model components and training approach in terms of expressiveness, scalability and stability. We devise experiments with various difficulties and demonstrate the efficacy and robustness of our approach. Although our framework is pretty general, we believe their are other potential methods that can lead to equally competitive results, which we leave as future work.

###### Acknowledgements.

 The work was supported in part by National Key Research and Development Program of China (2020AAA0107600), NSFC (62222607), Science and Technology Commission of Shanghai Municipality (22511105100), and Shanghai Municipal Science and Technology Major Project (2021SHZDZX0102).

Figure 5. (a) Ablation study for GraphGLOW. (b) Performance comparison of GraphGLOW and GCN w.r.t. randomly removing certain ratios of edges in Johns Hopkins55.

Figure 6. (a) The curves of homophily ratios for latent structures during the learning process. (b) The variance of neighborhood distribution of nodes with the same label in original graphs and learnt structure.