Generalized Taxonomy-Guided Graph Neural Networks

1 Introduction

Network systems are ubiquitous in real life. With the recent success of neural networks, many network embedding techniques have been proposed for network analysis by transforming node representations into a low-dimensional space. Among these methods are Graph Neural Networks (GNNs) [Kipf and Welling, 2017; Velickovic et al., 2018], which are best known for their ability to obtain node embeddings by propagating and aggregating network features across given networks. The GNN methods have been broadly adopted for diverse applications like natural language processing [Huang and Carley, 2019; Qu et al., 2020], traffic forecasting [Bai et al., 2021; Bui et al., 2022], recommendation systems [He et al., 2020; Wang et al., 2019a; Ying et al., 2018], cybersecurity [Liu et al., 2021; Lu and Li, 2020].

∗Corresponding author

The classical GNNs and their variants [Kipf and Welling, 2017; Hamilton et al., 2017; Velickovic et al., 2018] iteratively update node representations through passing messages among neighboring nodes. However, many real-world networks are inherently hierarchical, and the neighborhood structures of nodes are often arranged based on the underlying implicit taxonomies that dictate system organizational structures. Fig. 1 shows an example of a citation network based on a taxonomy of research topics. Categories in taxonomy can be viewed as groups of highly related entities, and subcategories prescribe a hierarchical structure. Correspondingly, nodes representing network entities tend to form implicit hierarchical communities within which they share varying degrees of similarity. For example, nodes a and c are first-order neighbors of node b, and node d is a second-order neighbor of node b. In computer science, a, b, c and d are all computer science-related papers, while by a detailed classification, papers a, b and c belong to a general category of AI, and papers b and c are categorized to the specialized computer vision field. Thus, for paper b, paper c is the most similar or closest neighbor, followed by a, and then d. In this toy example, paper b has different granularities of similarity with its neighbors, indicating an implicit hierarchical structure. Unfortunately, the existing GNN methods fail to capture the latent hierarchical structure in this example, resulting in distortions when embedding real-world networks with hierarchical structures.

Several algorithms and models have been designed to capture latent hierarchical structures within networks. For example, it has been attempted to infer network hierarchies and use estimated hierarchical structures to facilitate network representation learning [Chami et al., 2019; Ma et al., 2018; Lin et al., 2022]. However, the quality of inferred hierarchical structures depends on the network, and the results lack interpretability. Another line of attempt is to introduce network-specific taxonomy to graph neural networks to learn network hierarchical structures, thereby improving representation learning. For instance, TaxoGAN [Yang et al., 2020] co-embeds networks and taxonomies by computing network embedding using hierarchy labels to generate fine-grained label embedding. TaxoGNN [Xu et al., 2022] jointly learns the taxonomy and network representation by aligning taxonomy knowledge with the network structure through information distillation. However, these methods overlook the rich semantic and structural information in the given taxonomy. They are difficult to generalize and reuse, especially in scenarios where taxonomy is partially or completely missing.

To address these issues, we propose generalized Taxonomy-Guided Graph Neural Networks (TG-GNN) to incorporate network-specific taxonomies to integrate taxonomy guidance into network representation learning. TG-GNN comprises two key modules: taxonomy representation learning and network representation learning. The taxonomy representation module constructs a position-aware ego network for each category and introduces a positionenhanced graph neural network to capture taxonomical information. It generates pseudo-training data based on the given taxonomy. The network representation module incorporates a taxonomy-guided Markov mechanism to encapsulate taxonomy knowledge in pairwise potential functions to refine network embedding, ensuring effective guidance of the taxonomy knowledge space toward the network data space. Extensive experiments illustrate that our proposed TG-GNN significantly outperforms the state-ofthe-art methods on various real-world networks, including scenarios with incomplete taxonomy and inductive settings.

2 Preliminaries

2.1 Terms and Notations

Network. Consider a network G = {V, E, X}, with a set of nodes V = {v1, . . . , vn}, a set of edges E = {eij} ⊆ V ×V , and a node attribute matrix X. The topological structure of G is represented by an adjacency matrix A = [aij ] ∈ Rn×n , where aij = 1 if nodes vi and vj are connected, or aij = 0 otherwise.

Taxonomy. A taxonomy T = (C, L) organized in a tree-like form related to a network G can be formulated by a directed acyclic graph, where a node ci ∈ C represents a category and a directed edge <ci, cj> ∈ L indicates a category-category relation, expressing that ci serves as the "parent" of cj and cj as the "child" of ci in the taxonomy.

Network with Taxonomy. Each node vi in the network G can be attached to a category ci,di in the taxonomy T, and thus labeled with a category path (ci,1, ci,2, . . . , ci,di ) from root category ci,1 to category ci,di . D is the depth of the taxonomy. If ci,di is a leaf category, di = D, otherwise di < D. We may extend a path until its length becomes D.

2.2 Markov RandomFields

Markov Random Field (MRF) [Picka, 2006] is a probability distribution P over variables defined by an undirected graph. It is characterized by an energy function E consisting of unary potentials ϕ and pairwise potentials ψ:

where yi and yj are the labels of node vi and node vj , respectively. The unary term ϕ(yi) for node vi measures the cost for having label yi, and the pairwise term ψ(yi, yj) represents the cost that vi and vj have labels yi and yj, respectively. The MRF can be estimated by using the Gibbs distribution to compute the posterior probability of label Y given network topology A and node attributes X, defined as:

where Z is the partition function for normalization. The best label assignments ˆ Y can then be obtained:

3 Methodology

In the sequel, we first briefly discuss the new TG-GNN method, whose architecture is sketched in Fig. 2. We then present the two learning modules.

3.1 Overview of Taxonomy-Guided Graph Neural Networks

To effectively integrate taxonomy guidance into network representation learning, we propose generalized TaxonomyGuided Graph Neural Networks (TG-GNN, Fig. 2). TG-GNN comprises two key modules: 1) The taxonomy representation learning module that constructs a position-aware ego network to capture the semantic and structural information in the taxonomy. 2) The network representation learning module employs a graph attention mechanism to extract semantic and topological information from the network. It then passes this information to the taxonomy-guided Markov component to optimize the outcome of labeling.

3.2 Taxonomy Representation Learning

The taxonomy representation learning module captures the rich semantic and structural information in the taxonomy and provides the learned taxonomy knowledge to the network representation learning module. We first employ Word2Vec [Mikolov et al., 2013] to represent individual categories of the taxonomy tree as the taxonomy features. We then construct an ego network for each node within the taxonomy, enhancing the node embedding with the node position information. We model the taxonomy representation using a positionenhanced graph neural network.

Ego Network. It is a network constructed for each node to capture parent-child and hierarchical relationships. Since the edges in a taxonomy are unidirectional, information can only flow from the top to the bottom of the taxonomy tree, and parent nodes cannot learn information from their child nodes. However, as the surface names of parent and child nodes in the taxonomy might differ, there is no direct connection. For example, in the ACM computing classification, where "Natural Language Processing" serves as the parent category of "Machine Translation" without an explicit surface name connection, their initial embeddings reside far apart in the lowdimensional representation space. To address this issue, we consider each taxonomy category as an anchor concept and build an ego network that includes itself, its parent category, and subcategories so as to better model taxonomy categories.

Position-aware Embedding. In addition to modeling the semantic information in taxonomy, we introduce three position types to nodes: the anchor, parent and child nodes. Such positional information can be used to distinguish different ego networks and separate nodes with different identities (i.e., anchor vs. parent vs. child nodes) during information propagation and aggregation. Consider a graph neural network with K layers. We represent the attributes of taxonomy node ci in the k-th (k = 1, 2, . . . ,K) layer of GNN by h(k) i , and the position embedding of node ci in the k-th layer of the graph neural network is represented as p(k) i , then the position-aware embedding of node ci at layer k is

where ∥ represents the concatenation operation.

Position-Enhanced Graph Neural Network. Given an anchor node ci and its ego network, motivated by [Shen et al., 2020], we use a position-enhanced graph neural network to generate the final representation for the anchor node. Specifically, we use position-enhanced graph neural networks and a neighborhood aggregation strategy to iteratively update the representation of node ci by aggregating the representations of its own and its neighbors N(ci), i.e., N(ci)∪ci, short noted as ˜ N(ci). After K iterations, a node's representation captures structural information within its K-hop neighborhood. Formally, we define a position-enhanced graph neural network with K layers as follows:

where k ∈ {0, . . . ,K - 1}. Subsequently, we use a multihead graph attention network with M attention heads to instantiate the aggregation function:

where ∥ represents the concatenation operation, ρ is a nonlinear function, e.g.,ReLU, W (k) m is the m-th weight matrix in the m-th attention head, and α(k) ij is the importance of the characteristics of nodes cj to ci, which can be defined as:

where a(k) and W (k) are both learnable parameters, γ(·) is another nonlinear function (such as LeakyReLU), and ∥ represents the concatenation operation.

Readout Function. After obtaining the final representation h′i (K) of each node, we employ the readout function to generate the representation hG of the ego network G and use hG as the final embedding of the anchor node:

where the READOUT function is a weighted element-wise mean function, with weights related to node positions:

where αpi is a parameter indicating the importance of position pi.

3.3 Network Representation Learning

The network representation learning module first uses graph neural networks to extract the semantic and topological information of the network. Subsequently, inspired by [He et al., 2018], we design a taxonomy-guided network-specific Markov mechanism to encapsulate node-related taxonomy knowledge by the pairwise potential function to direct the learning process.

Taxonomy-guided Markov Mechanism. We employ the unary potential function ϕ(yi) as the interface between GNN and MRF, which allows the amalgamation of the network's learned semantics and topology into one MRF layer. Formally, the unary potential function can be defined as:

where p(yi) is the probability that node vi has label yi whose inital value comes from GNN's result. Then, inspired by [Dong et al., 2023], we employ the pairwise potential function of the MRF to encapsulate node-related taxonomy information. For each node vi, it is assumed to have an associated taxonomy path Ci = (ci,1, ci,2, . . . , ci,di ), and the taxonomy path representation Hi is the sequential concatenation of category representations in path Hi = hi,1∥hi,1∥ . . . ∥hi,di . We utilize the cosine similarity to quantify the taxonomy correlation between nodes:

where ⊙ represents the Hadamard product, wi,j is a learnable parameter matrix. Hi and Hj are the taxonomy path representations of node vi and node vj respectively, which are learned by the taxonomy representation learning module. From the above definition, it can be seen that Staxo i,j reflects the strength of the similarity between taxonomies associated with node vi and node vj. Therefore, the pairwise potential function can be defined as:

where Γ(yi, yj) is the label compatibility, which equals one if yi ̸= yj or 0 otherwise. By using the pairwise potential function, node pairs with similar taxonomy information but inconsistent labels will be penalized. The more similar the taxonomy information Hi and Hj of node vi and node vj is, the greater the value of Staxo i,j becomes. Correspondingly, the penalty increases when the value of ψ(yi, yj) grows. Therefore, we incorporate the guidance of the taxonomy knowledge space into the network data space via the pairwise potential function of the Markov random field.

Mean Field Approximate. As the distribution of P(Y |A,X) is difficult to compute precisely and efficiently, we employ the mean-field theory [Koller and Friedman, 2009] to approximate P(Y |A,X) by an approximate distribution Q(Y |A,X), which minimizes the KL-divergence D(Q∥P). Q(Y |A,X) is decomposable, which can be represented as:

where Zi is a partition function for normalization.

Then, we stack K MRF layers to obtain the matrix form of Eq. (14), which can be updated iteratively as:

where k represents the k-th MRF layer, the inputs to the MRF layer are the label prediction probabilities Q(0) = p(yi) ∈ Rn×dL from the GNN, and dLis the dimensionality of node labels. Staxo ∈ Rn×n represents the taxonomy correlation between nodes, and Γ(yi, yj) ∈ RdL×dL is the label compatibility matrix.

3.4 Learning and Inference

For the taxonomy representation learning, given a taxonomy T = (C,L), we generate self-supervised data and train the model using a self-supervised training method. Specifically, for each category cq in the taxonomy, we extract its parent node cp as a positive example (cq, cp) with the label of 1 and construct M negative pairs {(cq, c1r ), (cq, c2r ), . . . , (cq, cMr )} by randomly select M other nodes clr (l = 1, 2, . . . ,M) with the label of 0, which are neither the parents nor the descendants of cq. During the training process, cq serves as the query node and cp and clr as anchor nodes. Given the constructed self-supervised binary tuples, the model is tasked to predict the labels for these tuples.Given the constructed self-supervised binary tuples, the model is tasked to predict the labels for these tuples. We use InfoNCE loss [van den Oord et al., 2018] to predict the labels for these tuples in the self-supervised data Ds = {(cq, cp), (cq, c1r ), (cq, c2r ), . . . , (cq, cMr )} to train the model:

where f(·) is the matching module, functioning as a logbilinear model, j = 1, 2, . . . ,M + 1, and Ltaxo is the cross entropy of classifying the positive pair (cq, cp) correctly.

For the network representation learning, we design a crossentropy loss function for the node classification:

where VL denotes the node set with labels, yi is the groundtruth, and ˆ yi is the predicted label distribution of node vi from the last MRF layer.

4 Experiments

Here, we discuss the experiment setup, compare the proposed TG-GNN with the best existing methods for node classification and visualization, analyze different components of TGGNN by an ablation study, and present a cold start experiment and parameter analysis.

4.1 Experimental Setup

Datasets. We used four real-world networks with taxonomies (Table 1). Aminer 1 is a co-author network with the research topic taxonomy 2 , where node labels represent the types of conferences authors participate in. Patent 3 is a patent citation dataset with the patent taxonomy, where the range of the patent generality index determines the node labels. PubMed 4 is a protein network with the disease taxonomy 5 , where a clustering algorithm on the protein network determines the node label. Yelp 6 is a business network with the category taxonomy 7 , where node labels are determined by a clustering algorithm on the business network, which can be viewed as product themes. Notably, the PubMed and Yelp taxonomies are incomplete, with only about 20% and 66% of the network nodes containing taxonomy information, respectively.

Baseline Methods. We evaluate the performance of TGGNN by comparing it with seven state-of-art algorithms.

• GCN [Kipf and Welling, 2017] and GAT [Velickovic et al., 2018] iteratively update node representations through message passing among neighboring nodes.
• HGCN [Chami et al., 2019] and Poincar´e [Nickel and Kiela, 2017] extend GCNs into hyperbolic geometry to infer latent hierarchies from networks and use estimated hierarchies to facilitate network representation learning.
• Tag2Guass [Wang et al., 2019b] introduces flat labels to enhance network embedding, which ignores the hierarchical relationship between the labels.

1 https://www.aminer.cn/data/?nav=openDataAcademic-SocialNetwork

2 https://dl.acm.org/ccs

3 https://www.nber.org/research/data/us-patents

4 ftp://ftp.ncbi.nih.gov/pub/taxonomy

5 ftp://ftp.ncbi.nlm.nih.gov/

6 https://www.yelp.com/dataset

7 https://www.yelp.com/developers/documentation/v3/all category list

• TaxoGAN [Yang et al., 2020] and TaxoGNN [Xu et al., 2022] introduce taxonomy explicitly into GNNs and jointly learns the taxonomy and graph representations.

Implementation Details. We used the recommended parameter settings from the respective codes for all baseline methods. In taxonomy representation learning, we employed a self-supervised training approach to acquire representations for all taxonomy categories. Our approach uses a two-layer position-enhanced GAT, with the first layer comprising four attention heads and the second layer using one attention head. Both layers utilize 200-dimensional semantic embeddings and 50-dimensional position embeddings, with a dropout rate of 0.1 applied to the input feature vectors. Additionally, we utilized the Adam optimizer with an initial learning rate of 0.001. In network representation learning, we utilized two GAT layers along with three MRF layers and set the dropout ratio to 0.5 to prevent overfitting. Each dataset is divided into three distinct sets: training, validation, and testing, with allocation proportions of 60%, 20%, and 20%, respectively.

4.2 Application 1 - Node Classification

We compared the performance of these methods in a node classification task. We report the mean Accuracy and F1 Score along with the standard deviation of 10 independent trials with different random seeds.

As listed in Table 2, our model outperforms all compared baseline methods on all four datasets. Specifically, TG-GNN achieves up to 1.46%, 3.61%, 6.27% and 21.07% better accuracy than the best baseline method on Aminer, Patent, PubMed and Yelp datasets, respectively. TG-GNN also achieves up to 1.36%, 3.92%, 2.65% and 20.88% higher F1 Score than the best baseline method on these four datasets. TG-GNN improves more significantly than the existing methods when network taxonomies are incomplete, such as PubMed and Yelp. Surprisingly, when taxonomies are incomplete, taxonomy-guided methods TaxoGAN and TaxoGNN perform poorly, even underperforming traditional data-driven GNN models like GCN and GAT. These results suggest that the existing methods are not robust nor generalizable to networks with incomplete taxonomies. In contrast, our new TG-GNN is highly robust and generalizable to all types of networks we considered, particularly those with incomplete taxonomies. Moreover, our new method performs better than HGCN and Poincar´e that implicitly model network hierarchies. This result suggests that it is necessary to explicitly introduce taxonomy and fully exploit semantic and structural information of the taxonomy.

4.3 Application 2 - Visualization

To demonstrate the effectiveness of our new taxonomy representation learning method, we used t-SNE [van der Maaten and Hinton, 2008] to downscale the learned taxonomy representations to a two-dimensional space. Fig.3 shows the representation visualization of the research topic taxonomy related to Aminer. It can be observed that embeddings generated by Word2Vec rely solely on the textual names of the taxonomic categories and fail to capture the intricate hierarchical relationships among them. Taxonomic categories are scattered disorderly around the embedding space. In contrast, the embeddings generated by the position-aware taxonomy learning module result in closer representations for categories within the same branch and more distant representations for categories in separate branches. This demonstrates that our taxonomy representation learning module can effectively acquire hierarchical structural information within the taxonomy.

4.4 Ablation Study of TG-GNNComponents

We conducted an ablation study to appreciate the validity and contribution of each component of our new method. We considered three variants of TG-GNN: 1) TG-GNN-Snet removes the guidance of taxonomy knowledge. Specifically, it modifies the pairwise potential function ψ of the MRF layer by changing Staxo to Snet to calculate the similarity between network node attributes instead of the correlation of taxonomy information between nodes. 2) TG-GNN-P removes position embeddings when learning taxonomy representations. 3) TG-GNN-T removes the entire taxonomy representation learning module and uses the initial taxonomy representation learned by Word2Vec.

We report the results on node classification in Table 3. As shown, TG-GNN outperforms TG-GNN-Snet in all cases, suggesting that it is highly preferable to integrate taxonomy guidance in graph neural networks. Moreover, TG-GNN-P with no position information performs inferior to TG-GNN, indicating that position information helps learn the structure information of the taxonomy tree. Finally, TG-GNN-T does not perform as well as the complete TG-GNN, demonstrating the effectiveness of thoroughly mining the rich semantic and structural information in taxonomy.

4.5 Cold Start Analysis

To assess and demonstrate the generalizability of our new method in the presence of missing data in networks and taxonomies, we designed a cold-start experiment on Aminer and Yelp. We divided each network in Aminer and Yelp into two parts in a 1:1 ratio, i.e., an observed network A and a test network B. We trained the model on network A and tested it on network B, the nodes and edges in test network B are not used for training. For the Aminer networks, all nodes in networks AAminer and BAminer have relevant taxonomy. For the Yelp networks, all nodes in an observed network AY elp have a taxonomy, whereas in a test network BY elp, more than two-thirds (68%) of the nodes have no taxonomy information. Therefore, the model's performance on BY elp is suitable for evaluating the generalizability of our method on networks with network and taxonomy information missing. TG-GNN

outperforms the four baseline methods on these four networks of the two datasets (Fig. 4), showing that our method has better inductive capability on unseen networks.

4.6 Parameter Analysis

We analyzed the impact of the number of MRF layers on model performance. As shown in Fig. 5, as the number of MRF layers increases, the overall performance improves initially but then declines. Therefore, stacking an appropriate number of MRF layers is beneficial for enhancing the guidance of taxonomy knowledge. However, an excessive number of MRF layers may weaken the contribution of taxonomy knowledge. Therefore, considering the balance between model performance and efficiency, we chose to use three MRF layers in TG-GNN.

5 RelatedWork

Several prior works are related to our research, particularly classical GNNs and taxonomy-guided graph neural networks. Classical Graph Neural Networks. Graph Neural Networks apply deep neural networks to graph-structured data. GCN [Kipf and Welling, 2017] extends Convolutional Neural Networks to handle graph-structured data by message propagation through graph neighborhoods using graph convolution operations. GraphSAGE [Hamilton et al., 2017] learns node embeddings by sampling and aggregating features from a node's local neighborhood, especially for optimizing largescale networks. GAT [Velickovic et al., 2018] utilizes attention mechanisms to differentially weigh the importance of neighboring nodes, enabling selective attention to various parts of the neighborhood during message passing. However, these classical GNNs all fail to consider the implicit network hierarchical structure, inevitably resulting in information distortion on real-world graphs with hierarchical structures.

Taxonomy-Guided Graph Neural Networks. The concept of taxonomy has been recently introduced to graph neural networks. For example, HGCN [Chami et al., 2019] and Poincar´e [Nickel and Kiela, 2017] extend GCNs to incorporate hyperbolic geometry to represent latent hierarchical structures. NetHiex [Ma et al., 2018] divides node embeddings to capture multi-granularity node proximity. However, these approaches ignore network taxonomies, even when they are available, resulting in less interpretable node embeddings. In contrast, TaxoGAN [Yang et al., 2020] introduces taxonomy explicitly into GNNs, which co-embeds nodes and hierarchical labels via a hierarchical network generation process. TaxoGNN [Xu et al., 2022] jointly learns the taxonomy and graph representations, which aligns taxonomy knowledge with the graph through information distillation. Despite the above advancements, these methods neglect the rich semantic and structural information in taxonomy. Moreover, these methods are difficult to generalize and reuse, especially when taxonomy is incomplete.

6 Conclusion

We proposed generalized Taxonomy-Guided Graph Neural Networks (TG-GNN) that integrate taxonomy guidance into network representation learning. Specifically, we constructed position-aware ego networks and used a position-enhanced graph neural network to capture both the rich semantic and structural information in the given taxonomy. We then incorporated a taxonomy-guided Markov mechanism to encapsulate taxonomy knowledge to guide network representation learning. Extensive experimental results and interpretable case studies demonstrated the advantages of TG-GNN.

Acknowledgements

This work is supported by National Key Research and Development Program of China (2023YFC3304503, 2023YFB2603904), National Natural Science Foundation of China (92370111, 62276187, 62272340).