Beyond Graph Convolutional Network: An Interpretable Regularizer-centered Optimization Framework

Owing to the powerful ability to aggregate neighborhood information, Graph Convolutional Network (GCN) has been successfully applied to diverse domains, such as computer vision [1, 2, 3], recommender systems [4, 5], privacy preserving [6], and traffic forecasting [7, 8]. Rooted in a series of theoretical foundations, GCN extends convolution operations to the non-Euclidean spaces and effectively propagates label signals, and therefore its variants have been extensively employed for a variety of graph-related tasks, including classification [9, 10], clustering [11, 12] and link prediction [13, 14]. In a nutshell, GCN generates the graph embedding with the well-established graph convolutional layers gathering semantics from neighbors according to the network topology, which are revealed to be the most critical component.

Although GCN has behaved well in many machine learning tasks, lots of studies have pointed out its certain drawbacks and made efforts for further improvements. Bo et al. [15] indicated that the propagation mechanism could be considered as a special form of low-pass filter, and presented a GCN with an adaptive frequency. Zhang et al. [16] argued that most GCN-based methods ignored the global information and proposed SHNE, which leveraged the structure and feature similarity to capture latent semantics. Wang et al. [17] revealed that the original GCN aggregated information from node neighbors inadequately, and then developed a multi-channel GCN by utilizing feature-based semantic graph. In spite of the performance boosts of these GCN variants, they didn’t establish a generalized framework, i.e., these approaches understood and enhanced GCN from certain and non-generalizable perspectives, thereby they are exceedingly difficult to be further developed, and with limited interpretability.

Consequently, it is expected to construct a unified framework for various GCNs with better interpretability; however, it is a pity that this kind of work is still in shortage. Zhao et al. [18] linked GCN and Graph-regularized PCA (GPCA), and then proposed a multi-layer network by stacking the GPCA layers. Zhu et al. [19] attempted to interpret existing GCN-based methods with a unified optimization framework, under which they devised an adjustable graph filter for a new GCN variant. Yang et al. [20] designed a family of graph convolutional layers inspired by the updating rules of two typical iterative algorithms. Although these efforts have contributed to better understanding of GCNs, they only explained GCNs in partial aspects, promoting the expectation of a more comprehensive analysis of GCNs.

To tackle the aforementioned issues, this paper induces an interpretable regularizer-centered optimization framework, which provides a novel perspective to digest various GCNs, i.e., this framework captures the common essential properties of existing state-of-the-art GCN variants and could defines them just by devising different regularizers. Moreover, in light of the analyses on current representative GCNs, we find that most of the existing approaches only consider capturing the topological regularization, while the feature-based semantic structure is underutilized, and hence this motivates us to design a dual-regularizer graph convolutional network (called tsGCN) within the regularizer-centered optimization framework for the fullest explorations of both structures and semantics from graph data. Due to the high computational complexity of performing infinite-order graph convolutions, the unified framework provides a straightforward way employing truncated polynomials to approximate the graph Laplacian, similar to the truncated Chebyshev polynomials by vanilla GCN, restricting the message passing of a single graph convolution to the first-order neighborhood.

The main contributions of this paper can be summarized as the following three aspects:

• •

  Propose a regularizer-centered constrained optimization framework, which interprets various existing GCNs with specific regularizers.

• •

  Establish a new dual-regularizer graph convolutional network (tsGCN), which exploits topological and semantic structures of the given data; and develop an efficient algorithm to reduce the computational complexity of solving infinite-order graph convolutions.

• •

  Conduct a series of experiments to show that tsGCN performs much better than many SOTA GCNs, and also consumes much less time than the newly GNN-HF/LF.

For the convenience of formal descriptions, derivations, and analyses, necessary notations are narrated as below. A graph is denoted as $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{A})$, where $\mathcal{V}$ marks the vertex set with $|\mathcal{V}|=N$ ($N$ is the total number of nodes in graph $\mathcal{G}$), $\mathcal{E}$ marks the edge set, and $\mathbf{A}=[\mathbf{A}_{ij}]_{N\times N}$ marks an affinity matrix of which $\mathbf{A}_{ij}$ measures the similarity between the $i$-th and the $j$-th node. In addition, $\mathbf{D}=[\mathbf{D}_{ij}]_{N\times N}$ represents the degree matrix of $\mathcal{G}$ with $\mathbf{D}_{ii}=\sum_{j=1}^{N}\mathbf{A}_{ij}$, and then the normalized symmetrical graph Laplacian of $\mathcal{G}$ is computed as $\widetilde{\mathbf{L}}=\mathbf{I}-\widetilde{\mathbf{A}}$ with $\widetilde{\mathbf{A}}=\mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D}^{-\frac{1}{2}}$.

For a graph $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{A})$, the svd of its graph Laplacian is $\mathbf{L}=\mathbf{U}\mathbf{\Lambda}\mathbf{U}^{\top}$, where $\mathbf{U}\in\mathbb{R}^{N\times N}$ is comprised of orthonormal eigenvectors and $\mathbf{\Lambda}=\mbox{diag}(\lambda_{1},\cdots,\lambda_{N})$ is a diagonal matrix with $\lambda_{i}$ denoting the $i$-th eigenvalue and $\lambda_{i}\geq\lambda_{j}$ ($i=1,\cdots,N$). Essentially, this decomposition induces a Fourier transform on the graph domain, where eigenvectors correspond to Fourier components and eigenvalues represent frequencies of the graph. For an input signal $\mathbf{x}\in\mathbb{R}^{N}$ defined on the graph $\mathcal{G}$, the corresponding graph Fourier transform of $\mathbf{x}$ is $\widehat{\mathbf{x}}=\mathbf{U}^{\top}\mathbf{x}$, and its inverse transform is derived as $\mathbf{x}=\mathbf{U}\widehat{\mathbf{x}}$. Consequently, the graph convolution between the signal $\mathbf{x}$ and the filter $\mathbf{g}\in\mathbb{R}^{N}$ is

where $\odot$ is the Hadamard product between two vectors. Particularly, denoting $\mathbf{g}_{\mathbf{\Theta}}=\mbox{diag}(\mathbf{\Theta}):=\mathbf{U}^{\top}\mathbf{g}$ parameterized by $\mathbf{\Theta}\in\mathbb{R}^{N}$, the graph convolution between $\mathbf{x}$ and $\mathbf{g}$ can be rewritten as

where $\mathbf{\Theta}$ is regarded as the filter coefficients to be optimized. Especially, $\mathbf{\Theta}$ is assumed to be the polynomials of the spectrums of the graph Laplacian [30], i.e.,

where $K$ is the order of Chebyshev polynomials. By fixing $K=2$, the graph convolutional network (GCN) [21] takes an effective form

where $\mathbf{\Theta}=[\theta]$ is a parameter to be optimized. When extending single channel signal $\mathbf{x}$ and filter $\theta$ to multi-channel $\mathbf{H}^{(l)}\in\mathbb{R}^{N\times d_{l}}$ and $\mathbf{\Theta}^{(l)}\in\mathbb{R}^{d_{l}\times f_{l}}$, the GCN is converted to

where $\widehat{\mathbf{A}}$ is a normalized version of $\mathbf{I}+\widetilde{\mathbf{A}}$, $\sigma(\cdot)$ is an activation function, and $\mathbf{H}^{(l)}\in\mathbb{R}^{N\times d_{l}}$ is the output of the $l$-th layer with $\mathbf{H}^{(0)}=\mathbf{X}$ being the input feature matrix.

Given the input $\mathbf{H}^{(l-1)}$ of the $(l)$-th layer, GCN can compute the output $\mathbf{H}^{(l)}$ by minimizing

where $\frac{1}{2}\text{Tr}({\mathbf{H}^{(l)}}^{\top}\widetilde{\mathbf{L}}\mathbf{H}^{(l)})=\frac{1}{4}\sum_{j=1}^{N}\sum_{i=1}^{N}\mathbf{A}_{ij}||\frac{\mathbf{h}^{(l)}_{i}}{\sqrt{\mathbf{D}_{ii}}}-\frac{\mathbf{h}^{(l)}_{j}}{\sqrt{\mathbf{D}_{jj}}}||_{2}^{2}$ with $\mathbf{H}^{(l)}=[\mathbf{h}_{1}^{(l)};\cdots;\mathbf{h}_{N}^{(l)}]$; it is a normalized regularizer to preserve the pairwise similarity of any two nodes in the given graph. Besides, the $-\text{Tr}({\mathbf{H}^{(l)}}^{\top}\mathbf{H}^{(l-1)}\mathbf{\Theta}^{(l)})$ is actually a fitting loss term bewteen $\mathbf{H}^{(l)}$ and $\mathbf{H}^{(l-1)}\mathbf{\Theta}^{(l)}$, i.e., $||\mathbf{H}^{(l)}-\mathbf{H}^{(l-1)}\mathbf{\Theta}^{(l)}||_{F}^{2}$ with $\mathbf{H}^{(l-1)}$ and $\mathbf{\Theta}^{(l)}$ fixed when optimizing $\mathbf{H}^{(l)}$. Note that the square term $||\mathbf{H}^{(l)}||_{F}^{2}$ is a L2-regularized smoother, which can be ignored or absorbed in the second graph regularizer $\text{Tr}({\mathbf{H}^{(l)}}^{\top}\widetilde{\mathbf{L}}\mathbf{H}^{(l)})$.

Taking derivative of $\mathcal{L}$ with respect to $\mathbf{H}^{(l)}$ and setting it to zero, we obtain $\mathbf{H}^{(l_{+})}$ as

and then there yields

when the nonnegative constraints $\mathbf{H}^{(l)}\geq\mathbf{0}$ are further considered. Notice that $\sigma(\cdot)$ is the $\mathrm{ReLU}(\cdot)$ activation function. Here, if the matix inverse $(\mathbf{I}-\tilde{\mathbf{A}})^{-1}=\sum_{i=0}^{\infty}\tilde{\mathbf{A}}^{i}$ is approximated by the first-order expansion, i.e., $(\mathbf{I}-\tilde{\mathbf{A}})^{-1}\approx\mathbf{I}+\tilde{\mathbf{A}}$, then Eq. (8) will lead to the updating rule (5) of GCN.

Usually, the activation functions in GCN are $\mathrm{ReLU}(\cdot)$ and $\mathrm{Softmax}(\cdot)$, which could be converted to different projection optimizations. Concretely, the $\mathrm{ReLU}(\cdot)$ activation function is equivalent to project a point $\mathbf{x}$ onto the non-negative plane $\mathcal{S}_{+}=\{\mathbf{s}\in\mathbb{R}^{d}|\mathbf{s}\geq\mathbf{0}\}$, i.e.,

By the way, we denote $\mathcal{S}=\{\mathbf{s}\in\mathbb{R}^{d}\}$, which corresponds to an identity activation function. In terms of the $\mathrm{Softmax}(\cdot)$ activation function, it can be regarded as projecting $\mathbf{x}$ onto the set $\mathcal{S}_{simplex}=\{\mathbf{s}\in\mathbb{R}^{d}|\mathbf{1}^{\top}\mathbf{s}=1,\mathbf{s}\geq\mathbf{0}\}$, i.e.,

where $\mathbf{y}^{\top}\log(\mathbf{y})=\sum_{i=1}^{d}\mathbf{y}_{i}\log(\mathbf{y}_{i})$ is the negative entropy of $\mathbf{y}$ [31]. In fact, with respect to other activation functions, they can also be equivalent to project a point onto some feasible set with some metric.

Up to present, we have actually utilized a constrained optimization problem to interpret GCN, including information propagations (i.e., Eq. (7)) and the nonlinear activation functions (i.e., $\mathrm{ReLU}(\cdot)$ and $\mathrm{Softmax}(\cdot)$).

The above analyses can not only explain the vanilla GCN, but also stimulate a regularizer-centered optimization framework that can further unify various GCNs. By extending the optimization (6), a more general framework is written as

Under this framework, different regularizers could derive different GCNs, for example,

• •

  If $\mathcal{L}(\mathbf{H}^{(l)};\mathcal{G})=Tr\left({\mathbf{H}^{(l)}}^{\top}(\mathbf{I}+\mu\widehat{\mathbf{L}})^{-1}(\mathbf{I}+\lambda\widehat{\mathbf{L}})\mathbf{H}^{(l)}\right)$ with $\lambda=\beta+\frac{1}{\alpha}-1$, $\mu=\beta$, and $\widehat{\mathbf{L}}=\mathbf{I}-\widehat{\mathbf{A}}$, then it induces the updating rule $\mathbf{H}^{(l)}=\sigma\left((\mathbf{I}+\alpha\widehat{\mathbf{A}})^{-1}(\mathbf{I}+\beta\widehat{\mathbf{A}})\mathbf{H}^{(l-1)}\mathbf{\Theta}^{(l)}\right)$, which corresponds to GNN-HF [19].

• •

  If $\mathcal{L}(\mathbf{H}^{(l)};\mathcal{G})=Tr\left({\mathbf{H}^{(l)}}^{\top}(\mathbf{I}+\mu\widehat{\mathbf{A}})^{-1}(\mathbf{I}+\lambda\widehat{\mathbf{A}})\mathbf{H}^{(l)}\right)$ with $\lambda=\frac{-\alpha\beta+2\alpha-1}{\alpha\beta-\alpha+1}$ and $\mu=\frac{1}{\beta}-1$, then it gives rise to the updating rule $\mathbf{H}^{(l)}=\sigma\left((\mathbf{I}+\alpha\widehat{\mathbf{A}})^{-1}(\mathbf{I}+\beta\widehat{\mathbf{A}})\mathbf{H}^{(l-1)}\mathbf{\Theta}^{(l)}\right)$, which corresponds to GNN-LF [19].

For more cases, their results are summarized in Table 4, and the derivation details can refer to those of the original GCN (from Eq. (7) to Eq. (10)) and the supplementary.

Remarks. The work [19] is most similar to our work with the same research idea: they both want to propose a unified framework to interpret the current GCNs and guide the design of new GCN variants; however, they are realized in different ways. To be specific, (1) Zhu et al. [19] develop an optimization framework to explain different GCNs’ propagation processes; whereas we propose a constrained optimization framework not only to interpret various GCNs’ propagation processes, but also explain the nonlinear activation layers; (2) [19] unifies various GCNs via devising various fitting items which are essentially constructed by limited graph filters; while our work derives different GCNs through designing different regularizers. To sum up, our work interprets the whole (not partial) GCNs with regularizer-centered constrained optimizations.

One finding from most existing GCNs is that they often ignored feature-based semantic structures, which can weaken the representation learning abilities of graph networks, then we focus on two regularizers, i.e.,

where $\widetilde{\mathbf{L}}_{\mathcal{G}}$ is a graph Laplacian from the given adjacency matrix (e.g., $\widetilde{\mathbf{L}}_{\mathcal{G}}=\widetilde{\mathbf{L}}$), and $\widetilde{\mathbf{L}}_{\mathcal{X}}$ is a graph Laplacian calculated from the pairwise similarity of any two graph nodes. Hence, we devise a dual-regularizer, i.e., $\mathcal{L}(\mathbf{H}^{(l)})=\mathcal{L}_{1}(\mathbf{H}^{(l)};\mathcal{G})+\mathcal{L}_{2}(\mathbf{H}^{(l)};\mathcal{X})$, and if it is under the optimization framework (19), then there yields the following updating rule

Since this method seeks to preserve both the topological and semantic structures for more accurate presentations, we call it tsGCN (i.e., Topological and Semantic regularized GCN).

Notably, the computational complexity of $(\mathbf{I}+\alpha\widetilde{\mathbf{L}}_{\mathcal{G}}+\beta\widetilde{\mathbf{L}}_{\mathcal{X}})^{-1}$ is $\mathcal{O}(N^{3})$, which tends to be unaffordable in practical applications. To this end, a low-rank approximation is operated, i.e., $\alpha\widetilde{\mathbf{L}}_{\mathcal{G}}+\beta\widetilde{\mathbf{L}}_{\mathcal{X}}\approx\mathbf{W}\mathbf{V}^{\top}$, where $\mathbf{W},\mathbf{V}\in\mathbb{R}^{N\times r}$ with $r\ll N$. This leads to the Woodbury matrix identity:

of which the computational complexity costs $\mathcal{O}(N^{2})$.

Given that the optimal $\mathbf{M}^{*}$ of the following problem

is attained at the $r$-truncated singular value decomposition of $\alpha\widetilde{\mathbf{L}}_{\mathcal{G}}+\beta\widetilde{\mathbf{L}}_{\mathcal{X}}$, i.e., $\mathbf{M}^{*}=\mathbf{U}\mathbf{\Sigma}\mathbf{U}^{\top}$, where $\mathbf{\Sigma}\in\mathbb{R}^{r\times r}$ is a diagonal matrix containing the $r$ largest singular values. An optimal $\{\mathbf{W}^{*},\mathbf{V}^{*}\}$ to $\alpha\widetilde{\mathbf{L}}_{\mathcal{G}}+\beta\widetilde{\mathbf{L}}_{\mathcal{X}}\approx\mathbf{W}\mathbf{V}^{\top}$ can be given by an analytic form of $\mathbf{W}^{*}=\mathbf{V}^{*}=\mathbf{U}\mathbf{\Sigma}^{\frac{1}{2}}$.

To obtain the optimum $\{\mathbf{W}^{*},\mathbf{V}^{*}\}$, the iterative algorithm [32] with $\mathcal{O}(N^{2})$ is leveraged as

where QR$(\cdot)$ denotes the QR-decomposition. Note that this algorithm can converge to the $r$ largest eigenvalues $\mathbf{R}^{(t+1)}$ and its corresponding eigenvectors $\mathbf{Z}^{(t+1)}$ when the iterative number $t$ is large enough. Finally, there will be $\mathbf{W}^{*}=\mathbf{V}^{*}=\mathbf{U}^{(t+1)}[\mathbf{R}^{(t+1)}]^{\frac{1}{2}}$.

Gathering all analyses mentioned above, the procedure for tsGCN is summarized in Algorithm 1.

This section will show tsGCN’s effectiveness and efficiency via comprehensive experiments.

By revisiting GCN, this paper puts forward an interpretable regularizer-centered optimization framework, in which the connections between existing GCNs and diverse regularizers are revealed. It’s worth mentioning that this framework provides a new perspective to interpret existing work and guide new GCNs just by designing new graph regularizers. Impressed by the significant effectiveness of the feature based semantic graph, we further combine it with nodes’ topological structures, and develop a novel dual-regularizer graph convolutional network, called tsGCN. Since the analytical updating rule of tsGCN contains a time-consuming matrix inverse, we devise an efficient algorithm with low-rank approximation tricks. Experiments on node classification tasks demonstrate that tsGCN performs much better than quite a few state-of-the-art competitors, and also exhibit that tsGCN runs much faster than the very recently proposed GCN variants, e.g., GNN-HF and GNN-LF.

This work is in part supported by the National Natural Science Foundation of China (Grant Nos. U21A20472 and 62276065), the Natural Science Foundation of Fujian Province (Grant No. 2020J01130193).

In this supplementary, we mainly present specific details to link various GCNs with various graph regularizers under the regularizer-centered optimization framework. Besides, more experimental settings and results are provided to further enrich the main paper.