Elastic Graph Neural Networks

Introduction

Graph neural networks (GNNs) generalize traditional deep neural networks (DNNs) from regular grids, such as image, video, and text, to irregular data such as social networks, transportation networks, and biological networks, which are typically denoted as graphs (Defferrard et al., 2016; Kipf & Welling, 2016). One popular such generalization is the neural message passing framework (Gilmer et al., 2017):

We derive a novel and general message passing scheme, i.e., Elastic Message Passing (EMP), and develop a family of GNN architectures, i.e., Elastic GNNs, by integrating the proposed message passing scheme into deep neural nets;

Preliminary

where the edge orientation can be arbitrary. Note that the incident matrix and unnormalized Laplacian matrix have the equivalence ${\mathbf{L}}=\Delta^{\top}\Delta$. Next, we briefly introduce some necessary background about the graph signal denoising perspective of GNNs and the graph trend filtering methods.

It is evident from recent work (Ma et al., 2020) that many popular GNNs can be uniformly understood as graph signal denoising with Laplacian smoothing regularization. Here we briefly describe several representative examples.

GCN. The message passing scheme in Graph Convolutional Networks (GCN) (Kipf & Welling, 2016),

PPNP & APPNP. The message passing scheme in PPNP and APPNP (Klicpera et al., 2018) follow the aggregation rules

They are shown to be the exact solution and one gradient descent step with stepsize $\alpha/2$ for the following problem

2 Graph Trend Filtering

In the univariate case, the $k$-th order graph trend filtering (GTF) estimator (Wang et al., 2016) is given by

where $\Delta^{(1)}$ is equivalent to the incident matrix $\Delta$. Generally, $k$-th order graph difference operators can be defined recursively:

Elastic Graph Neural Networks

In this section, we first propose a new graph signal denoising estimator. Then we develop an efficient optimization algorithm for solving the denoising problem and introduce a novel, general and efficient message passing scheme, i.e., Elastic Message Passing (EMP), for graph signal smoothing. Finally, the integration of the proposed message passing scheme and deep neural networks leads to Elastic GNNs.

Note that this normalized incident matrix maintains the relation with the normalized Laplacian matrix as in the unnormalized case

With the normalization, the estimator defined in (8) becomes:

2 Elastic Message Passing

Saddle point reformulation. For a general convex function $g(\cdot)$, its conjugate function is defined as

where $\mathbf{prox}_{\beta g^{*}}({\mathbf{X}})=\operatorname*{arg\,min}\limits_{{\mathbf{Y}}}\frac{1}{2}\|{\mathbf{Y}}-{\mathbf{X}}\|_{F}^{2}+\beta g^{*}({\mathbf{Y}})$. The stepsizes, $\gamma$ and $\beta$, will be specified later. The first step (13) obtains a prediction of ${\mathbf{F}}^{k+1}$, i.e., $\bar{\mathbf{F}}^{k+1}$, by a gradient descent step on primal variable ${\mathbf{F}}^{k}$. The second step (14) is a proximal dual ascent step on the dual variable ${\mathbf{Z}}^{k}$ based on the predicted $\bar{\mathbf{F}}^{k+1}$. Finally, another gradient descent step on the primal variable based on $({\mathbf{F}}^{k},{\mathbf{Z}}^{k+1})$ gives next iteration ${\mathbf{F}}^{k+1}$ (15). Algorithm (13)–(15) can be interpreted as a “predict-correct” algorithm for the saddle point problem (12). Next we demonstrate how to compute the proximal operator in Eq. (14).

Proximal operators. Using the Moreau’s decomposition principle (Bauschke & Combettes, 2011)

we can rewrite the step (14) using the proximal operator of $g(\cdot)$, that is,

We discuss the two options for the function $g(\cdot)$ corresponding to the objectives (10) and (11).

By definition, the proximal operator of $\frac{1}{\beta}g_{1}({\mathbf{X}})$ is

which is equivalent to the soft-thresholding operator (component-wise):

By definition, the proximal operator of $\frac{1}{\beta}g_{21}({\mathbf{X}})$ is

Similarly, using (16), we have the $i$-th row of $\mathbf{prox}_{\beta g_{21}^{*}}({\mathbf{X}})$ being

The Algorithm (13)–(15) and the proximal operators (17) and (• ‣ 3.2) enable us to derive the final message passing scheme. Note that the computation ${\mathbf{F}}^{k}-\gamma\nabla f({\mathbf{F}}^{k})$ in steps (13) and (15) can be shared to save computation. Therefore, we decompose the step (13) into two steps:

Substituting the proximal operators in (22) with (17) and (• ‣ 3.2), we obtain the complete elastic message passing scheme (EMP) as summarized in Figure 1.

If $\lambda_{2}=\frac{1}{\alpha}-1$, it recovers the message passing in APPNP:

If $\lambda_{2}=\infty$, it recovers the simple aggregation operation in many GNNs:

The convergence of EMP and the parameter settings are justified by Theorem 1, with a proof deferred to Appendix B.

3 Elastic GNNs

Incorporating the elastic message passing scheme from the elastic graph signal estimator (10) and (11) into deep neural networks, we introduce a family of GNNs, namely Elastic GNNs. In this work, we follow the decoupled way as proposed in APPNP (Klicpera et al., 2018), where we first make predictions from node features and aggregate the prediction through the proposed EMP:

In addition to the backbone neural network model, Elastic GNNs only require to set up three hyperparameters including two coefficients $\lambda_{1},\lambda_{2}$ and the propagation step $K$, but they do not introduce any learnable parameters. Therefore, it reduces the risk of overfitting.

The hyperparameters $\lambda_{1}$ and $\lambda_{2}$ provide better smoothness adaptivity to Elastic GNNs depending on the smoothness properties of the graph data.

The message passing scheme only entails simple and efficient operations, which makes it friendly to the efficient and end-to-end back-propagation training of the whole GNN model.

Experiment

Datasets. We conduct experiments on 8 real-world datasets including three citation graphs, i.e., Cora, Citeseer, Pubmed (Sen et al., 2008), two co-authorship graphs, i.e., Coauthor CS and Coauthor Physics (Shchur et al., 2018), two co-purchase graphs, i.e., Amazon Computers and Amazon Photo (Shchur et al., 2018), and one blog graph, i.e., Polblogs (Adamic & Glance, 2005). In Polblogs graph, node features are not available so we set the feature matrix to be a $n\times n$ identity matrix.

Baselines. We compare the proposed Elastic GNNs with representative GNNs including GCN (Kipf & Welling, 2016), GAT (Veličković et al., 2017), ChebNet (Defferrard et al., 2016), GraphSAGE (Hamilton et al., 2017), APPNP (Klicpera et al., 2018) and SGC (Wu et al., 2019). For all models, we use $2$ layer neural networks with $64$ hidden units.

Parameter settings. For each experiment, we report the average performance and the standard variance of 10 runs. For all methods, hyperparameters are tuned from the following search space: 1) learning rate: $\{0.05,0.01,0.005\}$; 2) weight decay: {5e-4, 5e-5, 5e-6}; 3) dropout rate: {0.5, 0.8}. For APPNP, the propagation step $K$ is tuned from $\{5,10\}$ and the parameter $\alpha$ is tuned from $\{0,0.1,0.2,0.3,0.5,0.8,1.0\}$. For Elastic GNNs, the propagation step $K$ is tuned from $\{5,10\}$ and parameters $\lambda_{1}$ and $\lambda_{2}$ are tuned from $\{0,3,6,9\}$. As suggested by Theorem 1, we set $\gamma=\frac{1}{1+\lambda_{2}}$ and $\beta=\frac{1}{2\gamma}$ in the proposed elastic message passing scheme. Adam optimizer (Kingma & Ba, 2014) is used in all experiments.

2 Performance on Benchmark Datasets

Elastic GNN outperforms GCN, GAT, ChebNet, GraphSAGE and SGC by significant margins on all datasets. For instance, Elastic GNN improves over GCN by $3.1\%$, $2.0\%$ and $1.8\%$ on Cora, CiteSeer and PubMed datasets. The improvement comes from the global and local smoothness adaptivity of Elastic GNN.

3 Robustness Under Adversarial Attack

Locally adaptive smoothness makes Elastic GNNs more robust to adversarial attack on graph structure. This is because the attack tends to connect nodes with different labels, which fuzzes the cluster structure in the graph. But EMP can tolerate large node differences along these wrong edges, and maintain the smoothness along correct edges.

4 Ablation Study

We provide ablation study to further investigate the adaptive smoothness, sparsity pattern, and convergence of EMP in Elastic GNN, based on three datasets including Cora, CiteSeer and PubMed. In this section, we fix $\lambda_{1}=3,\lambda_{2}=3$ for Elastic GNN, and $\alpha=0.1$ for APPNP. We fix learning rate as $0.01$, weight decay as $0.0005$ and dropout rate as $0.5$ since this setting works well for both methods.

Convergence of EMP. We provide two additional experiments to demonstrate the impact of propagation step $K$ on classification performance and the convergence of message passing scheme. Figure 2 shows that the increase of classification accuracy when the propagation step $K$ increases. It verifies the effectiveness of EMP in improving graph representation learning. It also shows that a small number of propagation step can achieve very good performance, and therefore the computation cost for EMP can be small. Figure 3 shows the decreasing of the objective value defined in Eq. (11) during the forward message passing process, and it verifies the convergence of the proposed EMP as suggested by Theorem 1.

Related Work

Conclusion

Acknowledgements

This research is supported by the National Science Foundation (NSF) under grant numbers CNS-1815636, IIS-1928278, IIS-1714741, IIS-1845081, IIS-1907704, IIS-1955285, and Army Research Office (ARO) under grant number W911NF-21-1-0198. Ming Yan is supported by NSF grant DMS-2012439 and Facebook Faculty Research Award (Systems for ML).

References

Appendix A Data Statistics

The data statistics for the benchmark datasets used in Section 4.2 are summarized in Table 5. The data statistics for the adversarially attacked graph used in Section 4.3 are summarized in Table 6.

Appendix B Convergence Guarantee

We provide Theorem 1 to show the convergence guarantee of the proposed elastic messsage passing scheme and the practical guidance for parameter settings in EMP.

where $f$ and $g$ are convex functions and ${\mathbf{B}}$ is a bounded linear operator. It is proved in (Loris & Verhoeven, 2011; Chen et al., 2013) that the iterations in (13)–(15) guarantee the convergence of ${\mathbf{F}}^{k}$ to the optimal solution of the minimization problem (25) if the parameters satisfy $\gamma<\frac{2}{L}$ and $\beta\leq\frac{1}{\gamma\lambda_{\max}({\mathbf{B}}{\mathbf{B}}^{\top})}$, where $L$ is the Lipschitz constant of $\nabla f({\mathbf{F}})$. These conditions are further relaxed to $\gamma<\frac{2}{L}$ and $\beta\leq\frac{4}{3\gamma\lambda_{\max}({\mathbf{B}}{\mathbf{B}}^{\top})}$ in (Li & Yan, 2017).

For the specific problems defined in (10) and (11), the two function components $f$ and $g$ are both convex, and the linear operator $\Delta$ is bounded. The Lipschitz constant of $\nabla f({\mathbf{F}})$ can be computed by the largest eigenvalue of the Hessian matrix of $f({\mathbf{F}})$: