Heterogeneous Graph Information Bottleneck

1 Introduction

Heterogeneous Information Networks (HINs) possess the advantage of modeling rich relations in real work compared to homogeneous networks, which have been well studied by the researchers frommathematics, physics and computer science [Shi et al., 2017; Wang et al., 2020]. Thus, by effectively exploiting these multiple relations via meta-paths, HINs provide more clues for accurate network analysis, e.g. network embedding [Dong et al., 2017], and have been successfully applied to recommendation system [Shi et al., 2019], natural language processing [Hu et al., 2019] and knowledge graph.

∗Corresponding author.

Graph neural networks (GNNs) [Wu et al., 2021], especially graph convolutional neural networks (GCNNs) [Kipf and Welling, 2017; Bruna et al., 2014], have became a powerful tool for homogeneous attributed network embedding. And, their success can be attributed to the Laplacian smoothing [Li et al., 2018] from spatial perspective or the low-pass filtering [Wu et al., 2019] from spectral perspective.

Recent attempts extend GNNs to heterogeneous information networks [Wang et al., 2019; Fu et al., 2020; Yun et al., 2019; Hu et al., 2020]. Most of them follow the pipeline of transforming a heterogeneous attributed network with multiple relations into multiple attributed homogeneous networks via meta-paths and combining the embedding results of multiple homogeneous attributed networks obtained from GNNs. And, the supervision information is utilized to learn how to map from node feature to label and how to combine the multiple embedding results [Wang et al., 2019; Yun et al., 2019]. These semi-supervised methods implicitly take the direct assumption that the multiple homogeneous attributed networks induced by different meta-paths are complementary. That is, the information contained in each homogeneous attributed network is insufficient to represent nodes, thus, multiple homogeneous attributed networks are necessary to complete the information.

Here, the direct assumption of complementarity is investigated. The doubts about this hypothesis stem from both the characteristic of the homogeneous attributed networks and the nature of the adopted GNNs. First, the homogeneous attributed networks induced by meta-paths are not independent. In fact, they share the common node attributes (feature) and possess different network topologies. Second, the essence of GNNs, which are applied to each homogeneous attributed network, is the attributes smoothing according to the topology, i.e., discarding noises. Based on these two characteristics, the same attributes are smoothed according to the different topologies of multiple homogeneous networks. Thus, the smoothed node attributes in each homogeneous attributed network may not be significantly different.

Therefore, contrary to hypothesis of complementarity, another alternative assumption may be the consensus, where the aggregated node attributes shared by multiple homogeneous attributed networks are essential for node representations. In other words, to seek robust node representation, the aggregated node attributes, which are specific in each homogeneous attributed network, should be discarded. This assumption shares the common philosophy with consensus clustering. Note that this alternative assumption reduces the requirement for labels, thus is more suitable for unsupervised tasks.

In this paper, a novel Heterogeneous Graph Information Bottleneck (HGIB) is proposed to implement the consensus hypothesis in an unsupervised manner. To this end, information bottleneck (IB), which has been widely used in supervised tasks, is extended to unsupervised representation learning by leveraging self-supervision strategy. That is, each induced homogeneous attributed network is utilized as the selfsupervision information for the representation learning task on other induced homogeneous attributed networks. Specifically, HGIB simultaneously maximizes the mutual information between the representation learned from one homogeneous network and another homogeneous network, and minimizes the mutual information between the specific information contained in one homogeneous network and the representation learned from this homogeneous network. The model analysis reveals that HGIB degrades to the supervised heterogeneous GNN or the infomax on homogeneous graph, respectively, if the two adopted meta-paths are extremely similar or dissimilar.

The main contributions are summarized as follows.

• We investigate the widely-adopted complementary assumption in designing GNNs for HINs, and present an alternative one, i.e., consensus hypothesis, which is more suitable for unsupervised tasks.
• We propose a well-behavior Heterogeneous Graph Information Bottleneck (HGIB) by leveraging selfsupervised learning strategy, which facilitates the adoption of information bottleneck for unsupervised tasks.
• We reveal that the two extreme cases of HGIB correspond to the supervised heterogeneous GNN and the infomax on homogeneous graph, respectively.
• Extensive experiments demonstrate that the consensusbased unsupervised HGIB significantly outperforms most semi-supervised SOTA methods based on complementary assumption.

2 Preliminaries

2.1 Heterogeneous Information Network

A heterogeneous information network (HIN) [Sun and Han, 2012], denoted as G = (V, E, φ, ϕ), consists of a node set V and a link set E associating with a node type mapping function φ : V ↦→ T and link type mapping function ϕ : E ↦→ R, respectively. In the network, each object v ∈ V belongs to one specific object type φ(v) ∈ T and each link e ∈ E belongs to a specific relation ϕ(e) ∈ R, where |T | + |R| > 2. A meta-path P of length l is denoted in the form of T1 R1 --→ T2 R2 --→ ... Rl -→ Tl+1, which defines a composite relation R = R1 ◦ R2 ◦ ... ◦ Rl between types T1 and Tl+1 with ◦ standing for the composition operator on relations.

2.2 Information Bottleneck

To investigate the discriminative ability of the representation, the amount of label information that remains accessible after encoding the data, is known as sufficiency [Achille and Soatto, 2018]. A representation h of data x is sufficient for the label y if and only if I(x; y|h) = 0. That is, the amount of information regarding the task is unchanged by the encoding procedure, i.e.

where I(·; ·) stands for the mutual information. To make the representation robustness (generalization), Information Bottleneck principle (IB) [Tishby et al., 2000] attempts to discard all information from the input, which is not helpful for a given task. To this end, IB [Alemi et al., 2017] directly minimizes the mutual information between the data x and its representation h, I(x; h), while at the same time maximizes the mutual information between h and the label y, I(y; h). Its objective function can be formulated as follows

where θ denotes the parameters of the representation encoder pθ(h|x) and β controls the tradeoff. The second term I(x; h) can be subdivided into two components by using the chain rule of mutual information as

where the second term I(y; h) is independent of the representation h, since h is sufficient for y as shown in Eq. (1). The first term I(x; h|y) represents the information in h that is not predictive of y, i.e. superfluous information. Therefore, minimizing the mutual information I(x; h) is equivalent to minimizing the superfluous information I(x; h|y) [Federici et al., 2020], and the objective of IB in Eq. (4) can be reformulated as

Note that maximizing the IB can be done directly only in supervised settings, i.e. y is given.

3 Heterogeneous Graph Information Bottleneck

In this section, Heterogeneous Graph Information Bottleneck (HGIB) is proposed. First, the assumption and the overview are provided by transforming the unsupervised heterogeneous graph neural network as a self-supervised task. Then, the formula of the self-supervised information bottleneck is introduced based on the supervised one in Sec 2.2. Finally, the objective function and the optimization are elaborated.

3.1 Assumption and Overview

There may exist multiple relations between each pair of nodes, which are induced by different meta-paths, in heterogeneous. Taking ACM as an example, each pair of papers can be connected by the same author or same subject. Contrary to the complementary assumption taken by most existing GNNs for heterogeneous, another alternative assumption, i.e., consensus, is investigated here. Consensus assumption considers that the learned node representations shared by multiple subgraphs are essential for node representations. In other words, to seek robust node representation, the node representations, which are specific in each sub-graph, should be discarded.

To implement the consensus assumption, the Heterogeneous Graph Information Bottleneck (HGIB) is proposed. Its illustration is shown in Fig. 1. In the heterogeneous graph, circle, square and triangle denote three kinds of nodes, while solid, dashed and dotted lines stand for three kinds of edges. First, the heterogeneous graph G = (V, E, φ, ϕ) is decomposed into two sub-graphs G (1) = ( ¯ V, E (1) ) (upper graph) and G (2) = ( ¯ V, E (2) ) (lower graph) according to the metapaths "circle-square-circle" and "circle-triangle-circle", respectively, where ¯ V represents the set of nodes with the type of circle. The adjacency matrices of these two sub-graphs are denoted as A(1) and A(2) . The attributes of the nodes of circle type are collected in matrix X, and x is employed to represent the original attributes of one node.

Here, the widely-adopted GCN [Kipf and Welling, 2017] is adopted as the encoders to obtain the node representations on two sub-graphs, as shown in the four gray boxes in Fig. 1, where the light gray boxes and dark gray boxes represent the propagations without learnable parameter and trainable mapping functions, respectively. The formula is as follows

where ˜A = A+ I stands for the adjacency matrix with selfloop, ˜D denotes the degree matrix of ˜A with the diagonal elements as the degrees of the nodes, V = ˜D- 1 2 ˜A˜D- 12X stands for the representations after propagation but without learnable parameters, and Θ represents the learnable parameters (The matrices with superscripts ·(1) and ·(2) correspond to sub-graph G (1) and G (2) , respectively). Besides, v and h, which are the rows of V and H, respectively, are used to represent the attributes after propagation and final representation corresponding to one node, respectively. σ(·) denotes the nonlinear mapping function, such as ReLU or softmax.

According to the consensus assumption mentioned above, both v(1) (light orange box) and v(2) (light green box) share some common and inherent characteristics (yellow part) and possess specific characteristics (dark orange and dark green components), as shown in Fig. 1. Thus, we would like to learn the representation h(1) (or h(2) ) from v(1) (or v(2) ) that discards as much information as possible without losing any label information. In the next subsection, the IB for supervised task provided in Sec. 2.2 will be extended to selfsupervised one for discarding as much specific information as possible in the heterogeneous graph information bottleneck.

3.2 Self-supervised Information Bottleneck

In this section, the assumption and overview will be formulated by extending semi-supervised IB to self-supervised one. First, the consensus assumption can be formalized as the redundancy: v(1) is redundant with respect to v(2) for y if and only if I(y; v(1) |v(2) ) = 0. Whenever v(1) and v(2) are mutually redundant, any representation which contains all the information shared by both is as predictive as their joint observation.

Second, heterogeneous graph information bottleneck (HGIB) is formalized via self-supervised information bottleneck (SSIB). SSIB extends IB by considering the mutual redundancy assumption. Note that HGIB aims at exploring shared information by discarding as much specific information as possible. The IB formula in Eq. (4) can be extend to

where the first term I(v(2) ; h(1) ) maximizes the shared information between the learned representation h(1) from subgraph G (1) and v(2) from sub-graph G (2) , while the second term I(v(1) ; h(1) ) minimizes the information in h(1) ) from data v(1) . Similar to the decomposition in Eq. (3), by employing the redundancy assumption, the second term in SSIB (Eq. (5)) can be decomposed into

Since I(v(2) ; h(1) ) needs to be maximal to maximize RSSIB in Eq. (5), to minimize I(v(1) ; h(1) ), the first term in Eq. (6), i.e., I(v(1) ; h(1) |v(2) ), which represents the information in h(1) from the specific information of v(1) , should be minimized. Thus, the RSSIB in Eq. (5) can be rewritten as

where Θ(1) denotes the parameter of the GCN applied on sub-graph G (1) . Note that, in Fig. 1, the first term is illustrated as the oblique line between v(2) and h(1) , while the second term as the horizontal line between h(1) and the specific part in v(1) . Similarly, the counterpart of R(2) SSIB can be formulated as

Therefore, the self-supervised information bottleneck is formulated as jointly maximizing both R(1) SSIB (Θ(1) ) and R(2) SSIB (Θ(2) ), and the two representation encoders implemented via GCNs with parameters Θ(1) and Θ(2) can be obtained. Furthermore, the final node representation is obtained as h = h(1) + h(2) , where the + stands for the element-wise summation.

3.3 Objective Function and Optimization

Objective Function

As described in pervious subsection, the objective function of HGIB can be obtained by averaging Eqs. (7) and (8) as

On one hand, by considering h(1) and h(2) on the same domain, the term IΘ(1) (v(1) ; h(1) |v(2) ) can be expressed as

which provide an upper-bound. This bound is tight when pΘ(1)(h(1) |v(1) ) coincides with pΘ(2)(h(2) |v(2) ), i.e., the two GCNs provide a consistent representation encoder. The derivation is provided in supplementary. Similarly, the counterpart is

On the other hand, IΘ(1)(v(2) ; h(1) ) can be reformulated as follows

where the second equality sign is because h(2) is the representation of v(2) . This bound is tight when h(2) is sufficient for h(1) , i.e., h(2) contains all the information regarding h(1) . Analogously, it holds that

Therefore, the objective function in Eq. (14) can be lowerbounded as

where DSKL(pΘ(1)(h(1) |v(1) )||pΘ(2)(h(2) |v(2) )) stands for the symmetric KL divergence between pΘ(1)(h(1) |v(1) ) and pΘ(2)(h(2) |v(2) ). γ is employed to control the trade-off between sufficiency and robustness of the node representation. For clarity, this objective function is illustrated in Fig.1(b).

Optimization

First, the symmetric KL divergence DSKL(pΘ(1)(h(1) |v(1) )||pΘ(2)(h(2) |v(2) )) can be directly computed by setting both pΘ(1)(h(1) |v(1) ) and pΘ(2)(h(2) |v(2) ) as Gaussian distributions whose mean and diagonal covariance matrix are obtained by feeding v (v(1) and v(2) are for two probability distributions, respectively) into a fully-connected layer. Second, the mutual information IΘ(1)Θ(2)(h(1) ; h(2) ) between the node representations h(1) and h(2) can be maximized by using any sample-based differentiable mutual information lower bound, such as MINE [Belghazi et al., 2018] and inforNCE [Oord et al., 2018]. Here, MINE is employed to estimate the MI as

where Tψ = Tψ(h(1) , h(2) ) is a function parametrized by a deep neural network with parameters ψ, and a multi-layer perceptron (MLP) is employed in this paper. p(h(1) , h(2) ) is joint sampler, while p(h(1) ) and p(h(2) ) are marginal ones.

3.4 Model Analysis and Comparison

In this subsection, two extreme cases are considered to show the connections between our proposed heterogeneous graph information bottleneck (HGIB) and exiting methods.

Case 1. According to the decomposition in Eq. (6), the less the v(1) and v(2) in common, the more I(v(1) ; h(1) |v(2) ) can be reduced by seeking the representation h(1) . Then, the more I(v(1) ; h(1) ) can be used to discard specific information. Thus, the obtained node representation more robust. At the extreme, if v(1) and v(2) only share label information, the node representation h(1) is minimal for label y, and selfsupervised IB is equivalent to the supervised IB without accessing to the labels. Therefore, our proposed HGIB becomes the supervised heterogeneous graph neural network.

Case 2. In contrary, the more the v(1) and v(2) in common, the less I(v(1) ; h(1) |v(2) ) can be reduced by seeking the representation h(1) , then, the less I(v(1) ; h(1) ) can be reduced to discard specific information. Thus, the role of inducing multiple sub-graphs via different meta-paths is weakened. At the extreme, if v(1) and v(2) are identical, then the HGIB degenerates to the mutual information maximization principle in InfoMax [Hjelm et al., 2019] and mutual information maximization based on Noise-Contrastive Estimation [Oord et al., 2018] on homogeneous graph, i.e., maximizing I(x; h), such as in Graphical Mutual Informax (GMI) [Peng et al., 2020].

Information theory based GNNs. Since the MINE [Belghazi et al., 2018] and infoNCE [Oord et al., 2018] were proposed, mutual information and contrastive learning are employed for self-supervised representation learning, such as infomax [Hjelm et al., 2019]. Then, Deep Graph Informax (DGI) [Velickovic et al., 2019] and InfoGraph [Sun et al., 2020] are proposed for node and graph classification by applying MINE and infoNCE to graph data, respectively. HDGI [Park et al., 2020] extends DGI to multiplex network by individually applying DGI to each graph and combining them via consistency regularization. Graph Information Bottleneck (GIB) [Wu et al., 2020] is the first to incorporate IB [Tishby et al., 2000] principle to GNNs. It main focus is the adversarial attack instead of performance improvement. Beside, GIB can't be directly applied to HIN to effectively exploit the rich information containing in multiple meta-paths.

4 Experiments

In this part, we experimentally evaluate our proposed HGIB on node classification and clustering. HGIB firstly learn sets of node representations in unsupervised manner, then these representations are used for classification and clustering.

Datasets. Two citation network datasets ACM and DBLP, and a movie dataset IMDB, are employed for evaluation. The detailed descriptions of these heterogeneous graph data used in experiments are shown in Table 1.

Baselines. HGIB is comparedwith some state-of-the-art algorithms including traditional (heterogeneous) network embedding methods and graph neural networks, such as recent methods DeepWalk [Perozzi et al., 2014] [Dong et al., 2017] [Dong et al., 2017], GCN [Kipf and Welling, 2017], GAT [Velickovic et al., 2018], HAN [Wang et al., 2019], GTN [Yun et al., 2019], DGI [Velickovic et al., 2019] and HDGI [Park et al., 2020]. Note that, GCN, GAT, HAN and GTN are semi-supervised methods, while DGI, HDGI and our HGIB are unsupervised ones. Besides, the results obtained from HGIB with randomly initialization are provided to demonstrate the lifting power of information bottleneck.

Implementation details. The embedding dimension is set to 128 for all the above methods . Adam is employed as the optimizer. For IMDB and ACM, the learning rate is set to 10-3 , and the encoder consists of two layers GCN with the output dimensions of two GCN layers are 512 and 128 respectively. For DBLP, the learning rate is set as the same as

75

65

100

90

85

Figure 2: The visualization of the embeddings obtained from DGI, HAN (semi-supervised) and our proposed HGIB on ACM and DBLP. 55 75 80 90 95

95

85

65

20%

40%

100

60%

80%

85

75

PSP(random init)

PAP(random init)

PSP(SSH-GNN)

PAP(SSH-GNN)

APA(random init) APA(SSH-GNN)

APCPA(random init) APCPA(SSH-GNN)

Table 3: Comparison on node clustering in ARI and NMI.

above but the output dimensions of the GCN layer are 256 and 128 respectively. The early stopping with patience of 30 is utilized. The hyper-parameter γ is always fixed as 10-3 .

4.1 Classification and Clustering Results

For classification task, we randomly draw out 20%, 40% and 60% of nodes for training the linear regression classifier. This procedure is repeated for 20 times and report the averaged (Micro and Macro) F1-score. The results are shown in Table 2. It shows that HGIB achieves the best performance on almost all the datasets and various ratio of train set, especially for supervised methods such as GCN, GAT and HAN.

For clustering task, Kmeans is employed and the Normalized Mutual Information (NMI) and Adjusted Rand Index (ARI) are used to assess the quality of the clustering results. Similarly, the process is repeated for 20 times and the averaged results are reported in Table 3. HGIB significantly outperforms the baselines.

It can be observed that the performance improvements on clustering task are more remarkable compared to those on classification task. In fact, this phenomenon is not surprising due to the different focuses of clustering and classification tasks. Both of them are dependent on the comprehensiveness and importance of the representations. The classification task pays much attention on comprehensiveness, since the given labels play the role of feature selection, while the clustering pays much attention on the importance for the lack of supervision. Although HGIB enhances both comprehensiveness and importance of the representations, the importance improvement is more significant, because its intention is to discard the as much specific information as possible. Thus, its improvement on HGIB is more notable.

4.2 Case Study

Comparison with random parameters. To verify the improvements induced by the learned parameters via HGIB, the performances of learned parameters are compared with that of randomly initialized ones. The results are shown in Fig. 3. It shows that the performances are consistently and significantly improved, no matter the final representations are from one or two sub-graphs. This demonstrates the effectiveness of the proposed HGIB.

Impacts of pairs of meta-paths. The impacts of different pairs of meta-paths on performance are investigated. The results are shown in Fig. 4. It illustrates some interesting

20%

40%

60%

80%

APA(random init) APA(SSH-GNN)

APCPA(random init) APCPA(SSH-GNN)

Both(random init) Both(SSH-GNN)

(a) meta-paths pair

Figure 4: Impacts of meta-paths pair.

points. 1) The lowest performances are achieved when the two meta-paths are identical as shown on the diagonal. This corresponds to the Case 2 in Sec 3.4. 2) If the two meta-paths are very different, the higher performance is achieved. For example, the best performance is achieved when author and subject appear in two meta-path, respectively, e.g. PAP vs. PSP. This corresponds to the Case 1 in Sec 3.4.

Hyper-parameter γ analysis. The hyper-parameter γ varies in 1, 10-1 , 10-2 , 10-3 . The impacts on performance on DBLP network with different presents of labels are shown in Tab. 4. Since the best performance is achieved when γ = 10-3 , thus this value is adopted as the default.

5 Conclusions

This paper replaces the complementary hypothesis of the multiple homogeneous attributed networks induced by different meta-paths, which has been Heterogeneous Graph Neural Networks, with an alternative consensus one. The consensus assumption is implemented as Heterogeneous Graph Information Bottleneck (HGIB) by extending information bottleneck to unsupervised manner via self-supervised strategy. The proposed HGIB can be regard as the generalizations of both the semi-supervised heterogeneous GNNs and the infomax on homogeneous graph. Extensive experiments on real datasets demonstrate the correctness and the effectiveness of the consensus hypothesis by verifying the significant performance improvement of the unsupervised HGIB compared to the most semi-supervised state-of-the-art methods.

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China under Grant 61972442, Grant 61802391, Grant U2001202, Grant U1936208 and Grant 61802282, in part by the Key Research and Development Project of Hebei Province of China under Grant 20350802D and 20310802D; in part by the Natural Science Foundation of Hebei Province of China under Grant F2020202040, in part by the Hebei Province Innovation Capacity Enhancement Project under Grant 199676146H, in part by the Natural Science Foundation of Tianjin of China under Grant 20JCYBJC00650, in part by the Key Program of the Chinese Academy of Sciences under Grant QYZDB-SSW-JSC003, and in part by State Key Laboratory of Software Development Environment under Grant SKLSDE-2020ZX-18.

A Proof of Eq. (10)

B Proof of Eq. (12)