Residual Hyperbolic Graph Convolution Networks

This section is meant to theoretically explain the efficiency of our network architecture. Inspired by (Cai and Wang 2020), we first define a hyperbolic version of “Dirichlet energy" for tracking node embeddings as follows. The Dirichlet energy of a function measures the "smoothness" of a unit norm function. The indistinguishable parameters leading to the over-smoothing issue result in small Dirichlet energy. For details of formulas and proofs in this section, see the supplementary material.

Note that the defined Dirichlet energy always pulls back the node embedding in Lorentz space to its tangent space at the origin point.

If the hyperbolic graph convolution operator $hgc(\cdot)$ as in (10) has no original input, i.e. $\bar{H}=\tilde{P}\otimes H$ therein, then

$$E(H^{(l)})\leq(1-\lambda)^{2}\|(1-\beta_{l})I+\beta_{l}{\boldsymbol{W}}^{(l)}\|_{2}^{2}E(H^{(l-1)}),$$

(12)

where $0<\lambda<2$ is the smallest non-zero eigenvalue of $\tilde{\Delta}$ and $\|X\|_{2}$ denotes the maximal singular value of $X$. Note that $\|X\|_{2}=\max_{\|u\|_{2}=1}\|Xu\|_{2}$ for any matrix $X$. Hence by the triangle inequality,

$$\|((1-\beta_{l})I+\beta_{l}{\boldsymbol{W}}^{(l)})u\|_{2}\leq 1-\beta_{l}+\beta_{l}\|{\boldsymbol{W}}^{(l)}u\|_{2}.$$

(13)

Actually $\|Xu\|_{2}$ for any weight matrix $X$ may be estimated by

Hence combined with (12) and (13), we easily prove that in HGCNs without initial input, we have $E(H^{(l)})\leq d(1-\lambda)^{2}E(H^{(l-1)})$. Thus if the graph $G$ does not have enough expansion, say $(1-\lambda)<\frac{1}{\sqrt{d}}$, then HGCNs would be exponentially over-smoothing as the number of layers increases.

The above result suggests us add an initial input as in $hgc(\cdot)$,

$$\bar{H}=\left(\left((1-\alpha_{l})\odot(\tilde{P}\otimes H^{(l-1)})\right)\oplus\left(\alpha_{l}\odot H^{(0)}\right)\right),$$

seeking to interfere the decreasing of Dirichlet energy, which is the motivation of $\mathcal{R}$-HGCNs.

We investigate in details the interference of initial input. For simplicity we assume that the features in process all have positive entries so that ReLU does not affect the evaluation of Dirichlet energy. Thus utilizing the same argument as in the proof of (12) in the case with initial input, we have

$$\begin{split}&E(H^{(l)})=(y_{l}\log_{o}(z))^{T}\tilde{\Delta}(y_{l}\log_{o}(z)),\end{split}$$

(14)

with $y_{l}=(1-\beta_{l})I+\beta_{l}W^{(l)}$ and $z=\exp_{z_{1}}(\alpha_{l}P_{o\rightarrow z_{1}}(\log_{o}(H^{(0)})))$ the last equality of which is due to linearity of parallel transport, and $z_{1}=\exp_{o}((1-\alpha_{l})\log_{o}(\tilde{P}\otimes H^{(l-1)}))=\exp_{o}(z_{2})$.

By definition of parallel transport, we have

$$\begin{split}&P_{o\rightarrow z_{1}}(\log_{o}(H^{(0)}))\\ =&\log_{o}(H^{(0)})-\frac{\langle\log_{o}(z_{1}),\log_{o}(H^{(0)})\rangle_{\mathcal{L}}}{d_{\mathcal{L}}(o,z_{1})}(z_{2}+\log_{z_{1}}(o))\end{split}$$

(15)

Further by definition,

$$\begin{split}&z_{1}=\cosh((1-\alpha_{l})\|\tilde{P}\log_{o}(H^{(l-1)}))\|_{\mathcal{L}})o\\ &\quad+\frac{\sinh((1-\alpha_{l})\|\tilde{P}\log_{o}(H^{(l-1)})\|_{\mathcal{L}})}{\|\tilde{P}\log_{o}(H^{(l-1)})\|_{\mathcal{L}}}\tilde{P}\log_{o}(H^{(l-1)})\\ \end{split}$$

(16)

Also by definition, $\exp_{z_{1}}(x)=\cosh(\|x\|_{\mathcal{L}})z_{1}+\frac{\sinh(\|x\|_{\mathcal{L}})}{\|x\|_{\mathcal{L}}}x$. Then again by the property of parallel transport, we have

$$\begin{split}z=\theta_{l}\log_{o}(H^{(0)})+\phi_{l}\tilde{P}H^{(l-1)}+\psi_{l}o,\end{split}$$

(17)

where $\theta_{l},\phi_{l},\psi_{l}$ are coefficients depending on $\alpha_{l},\beta_{l}$ and the Lorentzian norm of the above 3 vectors. Noting that $\theta_{l}$ only depends on $\alpha_{l}$ and $H^{(0)}$, the effect of $\log_{o}(H^{(0)})$ is always not negligible. Also ($z=(z_{0},\dots)$)

$$\log_{o}(z)=\frac{arcosh(z_{0})}{\sqrt{z_{0}^{2}-1}}(z-z_{0}o),$$

which removes $z_{0}$ from $z$ and re-scale it by a large factor. Then altogether we have

$$\begin{split}E(H^{(l)})&=(\tilde{\theta}_{l}\log_{o}(H^{(0)})+\tilde{\phi}_{l}\tilde{P}H^{(l-1)}+\tilde{\psi}_{l}o)^{T}\tilde{\Delta}(\cdots)\\ &=\tilde{\theta}_{l}^{2}E(H^{(0)})+\cdots,\end{split}$$

(18)

where $\tilde{\theta}_{l}$ is negligible similarly. Thus we prove that in $\mathcal{R}$-HGCNs with initial input, the Dirichlet energy $E(H^{(l)})$ will be bounded away from zero even if the Dirichlet energy in the corresponding HGCNs without initial input decrease to zero.

We use the product manifold of the Lorentz models as embedding space. The Lorentz components of the product manifold are independent of each other.

The product manifold is the Cartesian product of a sequence of Riemannian manifolds, each of which is called a component. Given a sequence of the Lorentz models $\mathcal{L}^{d_{1}}_{1},\cdots,\mathcal{L}^{d_{j}}_{j},\cdots,\mathcal{L}^{d_{k}}_{k}$ where $d_{j}$ denotes the dimension of the $j$-th component, the product manifold is defined as $\mathbb{L}=\mathcal{L}^{d_{1}}_{1}\times\dots\times\mathcal{L}^{d_{j}}_{j}\times\cdots\times\mathcal{L}^{d_{k}}_{k}$. The coordinate of a point $\vec{x}$ on $\mathbb{L}$ is written as $\vec{x}=[\vec{x}_{1},\cdots,\vec{x}_{j},\cdots\vec{x}_{k}]$ where $\vec{x}_{j}\in\mathcal{L}^{d_{j}}_{j}$. Similarly, the coordinate of a tangent vector $\vec{v}\in\mathcal{T}_{\vec{x}}\mathbb{L}$ is written as $\vec{v}=[\vec{v}_{1},\cdots,\vec{v}_{j},\cdots,\vec{v}_{k}]$ where $\vec{v}_{j}\in\mathcal{T}_{\vec{x}_{j}}\mathcal{L}^{d_{j}}_{j}$. For $\vec{x},\vec{y}\in\mathbb{L}$ and $\vec{v}\in\mathcal{T}_{\vec{x}}\mathbb{L}$, the exponential and logarithmic maps on $\mathbb{L}$ are defined as

$\displaystyle\mathrm{exp}_{\vec{x}}(\vec{v})$

$\displaystyle=[\mathrm{exp}_{\vec{x}_{1}}(\vec{v}_{1}),\cdots,\mathrm{exp}_{\vec{x}_{j}}(\vec{v}_{j}),\cdots,\mathrm{exp}_{\vec{x}_{k}}(\vec{v}_{k})],$

(19)

$\displaystyle\mathrm{log}_{\vec{x}}(\vec{y})$

$\displaystyle=[\mathrm{log}_{\vec{x}_{1}}(\vec{y}_{1}),\cdots,\mathrm{log}_{\vec{x}_{j}}(\vec{y}_{j}),\cdots,\mathrm{log}_{\vec{x}_{k}}(\vec{y}_{k})].$

(20)

Different from ordinary product manifolds, we use $\mathbb{L}=(\mathcal{L}^{d})_{o_{1}}\times(\mathcal{L}^{d})_{o_{2}}\times\cdots\times(\mathcal{L}^{d})_{o_{k}}$, where $(\mathcal{L}^{d})_{o_{i}}$ are copies of $d$-dimensional Lorentz spaces with randomly prescribed origin points $o_{i}\in\mathcal{L}^{d}$. This gives $\mathcal{R}$-HGCNs the ability to extract node features from a wider range of different perspectives. Mathematically, such construction of product manifolds is inspired by the general construction of manifolds using Euclidean strata with different coordinates.

Hyperbolic Dropout(HyperDrop) adds multiplicative Gaussian noise on Lorentz components to regularize the HGCNs and alleviate the over-fitting issue. Concretely, let $\mathbb{L}=\mathcal{L}^{d_{1}}_{1}\times\cdots\times\mathcal{L}^{d_{j}}_{j}\times\cdots\times\mathcal{L}^{d_{k}}_{k}$ denote a product manifold of $k$ Lorentz models where $d_{j}$ denotes the dimension of the $j$-th Lorentz component. Given an input $\vec{l}=[\vec{l}_{1},\cdots,\vec{l}_{j},\cdots\vec{l}_{k}]\in\mathbb{L}$ on the product manifold where $\vec{l}_{j}\in\mathcal{L}_{j}^{d_{j}}$, HyperDrop is formulated as

	$\displaystyle\vec{y}{}$	$\displaystyle=[\vec{y}_{1},\cdots,\vec{y}_{j},\cdots,\vec{y}_{k}],$		(21)
		$\displaystyle\vec{y}_{j}=\xi_{j}\odot f_{\theta_{j}}(\vec{l}_{j}),$
		$\displaystyle\xi_{j}\sim\mathcal{N}(1,\sigma^{2}),$

where $\xi_{j}$ is the multiplicative Gaussian noise drawn from the Gaussian distribution $\mathcal{N}(1,\sigma^{2})$. Following (Srivastava et al. 2014), we set $\sigma^{2}={\eta}/{(1-\eta)}$ where $\eta$ denotes drop rate. $\odot$ denotes the Lorentz scalar multiplication that is the generalization of scalar multiplication to the Lorentz representations, defined in Definition  2. $f_{\theta_{j}}(\cdot)$ could be any realization of a desirable function, such as a neural network with parameters $\theta_{j}$.

It is noted that we sample $\xi_{j}$ from the Gaussian distribution instead of the Bernoulli distribution used in the standard dropout for the following reason. If $\xi_{j}$ is drawn from the Bernoulli distribution and happens to be $0$ (with a probability of $\eta$) at the $\ell$-th neural network layer, the information flow of the $j$-th Lorentz component will be interrupted, leading to the deactivation of the $j$-th Lorentz component after the $\ell$-th neural network layer. In contrast, $\xi_{j}$ drawn from a Gaussian distribution with mean value $1$ is exactly equal to $0$ is a small probability event. Thus, the $j$-th Lorentz component always works.

We may interpret HyperDrop from a Bayesian perspective. For convenience, we take a single Lorentz model and the Lorentz linear transformation as an example, i.e. $\vec{y}=\xi\odot f_{\theta}(\vec{l})$ and $f_{\theta}(\vec{l})=\vec{l}\otimes\theta$. We have

$\displaystyle\vec{y}=\xi\odot(\vec{l}\otimes\theta),~{}~{}\xi\sim\mathcal{N}(1,\sigma^{2})$

(22)

equal to

	$\displaystyle\vec{y}=\vec{l}\otimes$	$\displaystyle{\boldsymbol{{M}}},$		(23)
	$\displaystyle\mathrm{with}~{}~{}m_{r,c}=\xi\theta_{r,c}$	$\displaystyle,~{}\mathrm{and}~{}\xi\sim\mathcal{N}(1,\sigma^{2}),$

where $\otimes$ denotes the Lorentz matrix-vector multiplication as defined in Definition 1, ${\boldsymbol{M}}$ is the matrix with $m_{r,c}$ as entries, and $\theta$ is the matrix with $\theta_{r,c}$ as entries. Eq (23) can be interpreted as a Bayesian treatment that the posterior distribution of the weight is given by a Gaussian distribution i.e.  $q_{\phi}(m_{r,c})=\mathcal{N}(\theta_{r,c},\sigma^{2}\theta_{r,c}^{2})$. The HyperDrop sampling procedure Eq (22) can be interpreted as rising from a reparameterization of the posterior on the parameter ${\boldsymbol{M}}$ as shown in Eq (23).

We then investigate our architecture of $\mathcal{R}$-HGCN and its effect of preventing over-smoothing. In fact, we always combine $\mathcal{R}$-HGCN with initial input. Note that our model is of the form $\mathbb{L}=(\mathcal{L}^{d})_{o_{1}}\times(\mathcal{L}^{d})_{o_{2}}\times\cdots\times(\mathcal{L}^{d})_{o_{k}}$, where $(\mathcal{L}^{d})_{o_{i}}$ are copies of $d$-dimensional Lorentz spaces with random prescribed origin points $o_{i}\in\mathcal{L}^{d}$. Then for any $x=(x_{1},\dots,x_{k})\in\mathbb{L}$, its Dirichlet energy is defined as

$$E(x)=\max_{1\leq i\leq k}(\log_{o_{i}}(x_{i})^{T}\tilde{\Delta}\log_{o_{i}}(x_{i})):=\max_{1\leq i\leq k}E_{i}(x_{i}).$$

(24)

Then by the similar argument with the proof of (12), we can estimate $E_{i}(H_{i}^{(l)})$ separately and then opt for the maximal among them, which may be better behaved than any single component due to possible fluctuation.

We use four standard commonly-used citation network graph datasets : Pubmed, Citeseer, Cora and Airport (Sen et al. 2008). Dataset statistics are summarized in Table 1. Experiment details see in the supplementary material.

Here we demonstrate the effectiveness of the $\mathcal{R}$-HGCN and our regularization method under different model configurations. For $\mathcal{R}$-HGCN, increasing the number of hyperbolic graph convolution layers almost always brings improvements on three datasets.

The criterion for judging the effectiveness of HyperDrop is to test whether the performance of $\mathcal{R}$-HGCN is improved with the help of HyperDrop. In Table 2, we report the performance of HyperDrop with various graph convolution layers and structures of product manifolds on Pubmed, Citeseer Cora and Airport. We observe that in most experiment, HyperDrop improves the performance of $\mathcal{R}$-HGCN. For example, on Cora, $\mathcal{R}$-HGCN_[2×8] obtains $1.7\%$, $0.7\%$, $0.3\%$ and $0.2\%$ gains with $4$, $8$, $16$ and $32$ layers. The stable improvements demonstrate that HyperDrop can effectively improve the generalization ability of $\mathcal{R}$-HGCN.

We also compare $\mathcal{R}$-HGCN with a deep Euclidean method, GCNII. The hyperbolic residual connection and hyperbolic identity mapping in $\mathcal{R}$-HGCN are inspired by GCNII. The main difference between $\mathcal{R}$-HGCN and GCNII is, $\mathcal{R}$-HGCN performs graph representation learning in hyperbolic spaces while GCNII is in Euclidean spaces. As shown in Table 2, $\mathcal{R}$-HGCN shows superiority compared to GCNII. Actually, $\mathcal{R}$-HGCN is only baseline model we developed for evaluating the effectiveness of HyperDrop, and we give up extra training tricks for clear evaluations. For example, in Section Comparisons with DropConnect, $\mathcal{R}$-HGCN obtains the same mean accuracy $83.5\%$ as GCNII with $8$ layers on Cora while using HyperDrop and DropConnect(Wan et al. 2013) together. DropConnect is used in other hyperbolic graph convolutional networks, such HGCN (Chami et al. 2019) and LGCN (Zhang et al. 2021). We claim that the superior performance of $\mathcal{R}$-HGCN compared to GCNII benefits from the representing capabilities of hyperbolic spaces while dealing with hierarchical-structure data. It confirms the significance of hyperbolic representation learning.

We conducted ablation experiments on the Pubmed dataset to observe the effect of our proposed hyperbolic residual connection on $\mathcal{R}$-HGCN performance in different dimension selection approaches, respectively. As can be seen from Tabel 4, without the hyperbolic residual connection, the fortunate performance of the model shows a different degree of decrease respectively. Moreover, as the number of model layers increases, the decline in model performance is more pronounced. The experimental results prove that hyperbolic residual connection has a great helpful effect on the model performance.

The comparisons with several state-of-the-art Euclidean GCNs and HGCNs are shown in Table 3. We have three observations. First and most importantly, compared with other HGCNs that are typically shallow models, $\mathcal{R}$-HGCN shows better results on Pubmed and Citeseer. Through, on Pubmed, HGCN also achieves the best accuracy, $80.3\%$. Note that HGCN uses extra link prediction task as pre-training model while $\mathcal{R}$-HGCN does not use this training trick for a clear evaluation of HyperDrop; and the performance of HGCN decreases when the link prediction pre-training is not used. On Cora, LGCN achieves the highest mean accuracy $83.3\%$ among HGCNs. Note that both HGCN and LGCN utilize DropConnect (Wan et al. 2013) technique for training. As shown in Section Comparisons with DropConnect, $\mathcal{R}$-HGCN obtains $83.5\%$ mean accuracy on Cora while also using DropConnect, that is $0.2\%$ higher than that of LGCN. Second, both $\mathcal{R}$-HGCN_[16×1] and $\mathcal{R}$-HGCN_[2×8] benefit from HyperDrop on three datasets. It proves HyperDrop alleviates over-fitting issue in hyperbolic graph convolutional network and improves the generalization ability of $\mathcal{R}$-HGCN on the test set. Third, compared with Euclidean GCNs, $\mathcal{R}$-HGCN combined with HyperDrop achieves the best results on Pubmed and Citeseer. It confirms the superiority of hyperbolic representation learning while modeling graph data.