DNG: Taxonomy Expansion by Exploring the Intrinsic
Directed Structure on Non-gaussian Space

Taxonomy: A given taxonomy $\mathcal{T}=\{\mathcal{V},\mathcal{E}\}$ can be treated as a directed acyclic graph composed of a vertex set ($\mathcal{V}$) and an edge set ($\mathcal{E}$) (Shen et al. 2020; Jiang et al. 2022). An edge $(v_{i},v_{j})\in\mathcal{E}$ between nodes $v_{i}$ and $v_{j}$ represents the is-a relation between them (e.g., $v_{j}$ is-a $v_{i}$), where $v_{i}$ and $v_{j}$ are the hypernym (“parent”) and the hyponym (“child”), respectively.

Shannon entropy is the basic concept for measuring the degree of uncertainty of a random variable. It is defined for a discrete-valued random variable $X$ as:

According to Eq. 1, entropy for the linear transformation $\bm{y}=\bm{B}\bm{x}$, can be derived as follows (Hyvärinen, Karhunen, and Oja 2001):

where det denotes the determinant; $\bm{B}$ and $\ln$ are the mapping matrix and napierian logarithm, respectively.

In order to incorporate the taxonomic structure, each node (e.g., $v_{i}$) is explicitly represented by the combination of structural feature (inherited from its parents) and supplementary feature (could not be inherited from its parents):

where $\bm{v}_{i}\in\mathbb{R}^{d}$ and PA_i are the $d$-dimensional representation and the parent set of node $v_{i}$, respectively. $s_{ij}\bm{v}_{j}$ denotes the feature inherited from the parent node $v_{j}$, where the inherited feature is weighted by an inheritance factor $s_{ij}$. $\bm{u}_{i}$ is the supplementary feature of node $v_{i}$ which cannot be obtained from its parents. $\bm{V}$ indicates the feature matrix of seed’s node set ($\mathcal{V}^{0}$), and $\bm{s}_{i}$ is the inheritance vector of $v_{i}$ on $\mathcal{V}^{0}$.

Figure 3 illustrates the node representation in a taxonomy fragment with two is-a pairs (i.e., $v_{5}$ is-a $v_{2}$, and $v_{2}$ is-a $v_{1}$). For the node $v_{1}$, its feature $\bm{v}_{1}$ only contains the supplementary part (i.e., $\bm{v}_{1}=\bm{u}_{1}$) since it is the root and does not inherit any feature from any node. Node $v_{2}$ has the parent $v_{1}$, making its representation $\bm{v}_{2}$ the combination of $\bm{u}_{1}$ and $\bm{u}_{2}$ (i.e., $\bm{v}_{2}=s_{21}\bm{u}_{1}+\bm{u}_{2}$). It is observed that $\bm{u}_{2}$ is independent of $\bm{u}_{1}$ since neither $\bm{u}_{1}$ nor $\bm{u}_{2}$ contains any information about the other. Similarly, $\bm{v}_{5}$ can be represented by the inherited feature and its supplementary feature (i.e., $\bm{v}_{5}=s_{52}(s_{21}\bm{u}_{1}+\bm{u}_{2})+\bm{u}_{5}$), from which the independence among $\bm{u}_{1}$, $\bm{u}_{2}$, and $\bm{u}_{5}$ can be also inferred. Hence, based on Eq. 3, the hierarchical semantics in a taxonomy could be embodied: the inheritance and accumulation of features from one layer to the next layer. This example also shows that these supplementary features are independent of each other.

Additionally, the directionality is another crucial attribute of the is-a relation: “$v_{5}$ is-a $v_{2}$, but $v_{2}$ is-not-a $v_{5}$”. How to capture this structural information is an issue to be resolved. In this paper, we attempt to translate this directionality into the irreversible inheritance of features: “$v_{5}$ could inherit feature from $v_{2}$, but $v_{2}$ could not inherit feature from $v_{5}$”. Under this intuition, this attribute could be realized by the irreversible transformation between $\bm{v}_{2}$ and $\bm{v}_{5}$ in Eq. 3 (i.e., $\bm{v}_{2}\neq s_{25}\bm{v}_{5}+\bm{u}_{2}$ under $\bm{v}_{5}=s_{52}\bm{v}_{2}+\bm{u}_{5}$). Inspired by the Darmois-Skitovich Theorem, ensuring the non-Gaussianity of the supplementary feature is a feasible implementation, as proven in the next section.

Supposing the representation $\bm{v}_{i}=s_{ij}\bm{v}_{j}+\bm{u}_{i}$ admits the inverse version $\bm{v}_{j}=s_{ji}\bm{v}_{i}+\bm{u}_{j}$ under non-Gaussian $\bm{u}_{i}$, there will exist the following transformation:

As such, the simultaneous equation will be obtained:

Due to the non-Gaussian $\bm{u}_{i}$, it can be drawn from Eq.5 based on the corollary of Darmois-Skitovich Theorem¹¹1See appendix in the arXiv version. that $\bm{v}_{i}$ and $\bm{u}_{j}$ will be dependent (i.e., $\bm{v}_{i}\not\perp\!\!\!\perp\bm{u}_{j}$). However, the fundamental condition of the inverse transformation $\bm{v}_{j}=s_{ji}\bm{v}_{i}+\bm{u}_{j}$ is $\bm{v}_{i}\perp\!\!\!\perp\bm{u}_{j}$. This contradiction between the assumption and the deduction verifies that the non-Gaussian supplementary feature will make the reversal node representation given in Eq. 3 false, indicating that the directionality of is-a is captured. In order to ensure this required constraint, we employ a log-likelihood learning target, which will be elaborated in the next section.

Based on the recursive node representation in Eq. 3, the node set $\mathcal{V}$ can be represented as ²²2Derivation of Eq. 6: $\bm{V}=\bm{V}\bm{S}+\bm{U}\Rightarrow\bm{V}\bm{I}-\bm{V}\bm{S}=\bm{U}\Rightarrow\bm{V}(\bm{I}-\bm{S})=\bm{U}\Rightarrow\bm{V}=\bm{U}(\bm{I}-\bm{S})^{-1}$:

where $\bm{W}=\bm{I}-\bm{S}$ is dubbed the transition matrix. $\bm{I}$ and $\bm{S}$ are an identity matrix and the inheritance factor matrix, respectively, and both of them have the size $N\times N$. $\bm{U}$ denotes the supplementary feature matrix with the shape of $d\times N$ ($d$ is the dimension of this feature).

From Eq. 6, we can observe that the essential step is to estimate the supplementary feature set $\bm{U}$ and the inheritance factors $\bm{S}$ given the observational feature $\bm{V}$. For this inheritance factor matrix, the entry with position ($i^{th},j^{th}$) reflects the probability of node $v_{j}$ being the “parent” of node $v_{i}$.

In real-word datasets, the feature $\bm{V}$ could be easily obtained from the well-designed pre-trained models (Liu et al. 2019b; Devlin et al. 2019) by fusing sufficient context information³³3DNG focuses on parsing $\bm{U}$ and $\bm{S}$ under the given $\bm{V}$ which can be extracted by other structural approaches with the structural measure, e.g., Wu&P (K., Shet, and Acharya 2012).. However, how to learn $\bm{U}$ and $\bm{S}$ from $\bm{V}$ remains to be determined. To fulfill this goal, we will first analyze the supplementary features $U$ as:

where $p_{\bm{U}}(\bm{u}_{i})$ is the probability density of $\bm{u}_{i}$, implemented by $\mbox{tanh}(\bm{u}_{i})=(e^{\bm{u}_{i}}-e^{-\bm{u}_{i}})/(e^{\bm{u}_{i}}+e^{-\bm{u}_{i}})$ (Hyvärinen, Karhunen, and Oja 2001). Then, in order to build the relation between $p_{U}(\bm{U})$ and $p_{V}(\bm{V})$, the joint probability density of $\bm{V}$ could be derived from $p_{\bm{U}}(\bm{U})$ by their probability distribution functions (PDFs) ⁴⁴4 First, get the the relation between PDFs: $\mathcal{F}_{\bm{V}}(V)=P_{\bm{V}}(\bm{V}\leq V)=P_{\bm{V}}(\bm{U}\bm{W}^{-1}\leq V)=P_{\bm{U}}(\bm{U}\leq V\bm{W})=\mathcal{F}_{\bm{U}}(V\bm{W})$. Then, compute the first-order derivation of PDFs: $p_{\bm{V}}(\bm{V})=\mathcal{F}_{\bm{V}}^{{}^{\prime}}(\bm{V})=\mathcal{F}_{\bm{U}}^{{}^{\prime}}(\bm{V}\bm{W})=p_{\bm{U}}(\bm{V}\bm{W})~{}|\mbox{det}\bm{W}|$ :

where $\bm{W}=(\bm{w}_{i},...,\bm{w}_{n})^{\top}$ indicates how to analyze the supplementary features from the observational representations.

With the definition of $p_{\bm{V}}(\bm{V})$ in hand, the given taxonomy $\mathcal{T}$ could be treated as the joint distribution of the node set $\mathcal{V}$; hence, the learning target can be defined as maximizing the logarithm of the joint probability:

where $\jmath$ denotes the loss to be minimized, and $\Theta$ is the parameters. For the DNG model, it is essential to guarantee that the non-Gaussian constraint is satisfied under this optimization, which will be proven in the next section.

To demonstrate that the supplementary feature $\bm{U}$ is a non-Gaussian distribution under the learning objective, let us first derive the expectation of Eq. 9:

Additionally, in information theory, the entropy measures the uncertainty of a random variable; therefore, a variable with more randomness will have higher entropy. For all types of random variables with the same variance, the Gaussian variable has the highest entropy, leading us to borrow the Negentropy (Hyvärinen, Karhunen, and Oja 2001) as the measure of a variable’s non-Gaussianity. With the help of Eq. 10, the non-Gaussianity of feature $\bm{U}$ can be derived as:

where NG denotes the non-Gaussianity of a variable. $\bm{U}_{Gaussian}$ is the feature with Gaussian distribution, and $H(\bm{U}_{Gaussian})$ could be treated as a constant (Tong, Inouye, and Liu 1993; Hyvärinen, Karhunen, and Oja 2001). Additionally, the term $\ln|\mbox{det}\bm{W}|$ could be also considered as a constant since $\mathbb{E}(\bm{V}\bm{V}^{\top})=\bm{W}\mathbb{E}(\bm{U}\bm{U}^{\top})\bm{W}^{\top}=\bm{I}$ ⁵⁵5$\bm{V}$ is pre-processed to unit variance (Hyvärinen and Oja 2000). under the unit-variance $\bm{V}$ and $\mbox{det}\bm{I}=1=\mbox{det}\bm{W}\mathbb{E}(\bm{U}\bm{U}^{\top})\bm{W}^{\top}=(\mbox{det}\bm{W})(\mbox{det}\mathbb{E}(\bm{U}\bm{U}^{\top}))(\mbox{det}\bm{W}^{\top})$. In this transformation, it can draw that the term $\mbox{det}\mathbb{E}(\bm{U}\bm{U}^{\top})$ does not depend on $\bm{W}$, which implies $det\bm{W}$ is a constant (Hyvärinen and Oja 2000). Consequently, based on Eq. 11, it can be also drawn that maximizing the joint probability of $\bm{V}$ is also equivalent to maximizing the non-Gaussianity of $\bm{U}$. This corollary exactly accords with the non-Gaussian condition of the proposed DNG model.

In the DNG model, estimating the matrix $\bm{S}$ is the crucial step for the expansion task.To launch the learning procedure, the taxonomy with its vertex set, the feature matrix $\bm{V}$ and the edge set are taken as the inputs. Then, the proposed model DNG is used to analyze the supplementary features and estimate the inheritance factor matrix. Specially, the gradients of updating the parameters are:

where $\bm{G}=(2/sinh(2\bm{u}_{1}),...,2/sinh(2\bm{u}_{n}))^{\top}$, and $\alpha$ is the learning rate. During the inference stage, the inheritance vector $\bm{s}_{q_{i}}$ for the query $q_{i}$ is directly computed⁶⁶6For a more precise estimation, a new iteration is requisite on the whole node set. based on the query feature $\bm{v}_{q_{i}}$, the learned supplementary feature matrix and the inheritance matrix. With $\bm{s}_{q_{i}}$ in hand, its appropriate positions could be easily found⁷⁷7Code is available at https://github.com/SonglinZhai/DNG..

Similar to (Shen et al. 2020; Zhang et al. 2021; Jiang et al. 2022), we also split the original taxonomy into separate sub-taxonomies, with each sub-taxonomy containing all paths from a source node (e.g., the root node) to a destination node (e.g., one leaf node). During inference, candidate anchors are first initially produced from these distinct sub-taxonomies. Then these candidate anchors are recombined by combining the anchors from the nearest sub-taxonomies to generate better anchors. After several iterations, the ultimate predictions could be generated.

Table 2 summarizes the performance of all compared models on Precision, Recall, MR and MRR evaluation metrics. Generally, the DNG model outperforms all baseline approaches on most metrics and especially gains a large margin improvement in Recall across all datasets, indicating the actual anchors being ranked at high positions. Additionally, it has been shown that not all models are capable of producing comparatively superior results for all evolution metrics. Despite the findings demonstrating the excellent performance of TaxoEnrich, the proposed DNG model still surpasses this strong baseline on the majority of criteria. The advantage of the DNG model on MR and MRR reveals its superior ranking performance, validating the effectiveness of the designed node representation and the non-Gaussian constraint presented in this paper.

Section 4 presents a re-designed node representation to capture the hierarchical semantics reflected by the inheritance factor. By estimating $\bm{S}$, appropriate anchors could be determined by locating the nodes with high factors, which will be illustrated in this section.

Figure 4 gives two real cases of the MAG-CS dataset for validating DNG’s ability to capture taxonomic structure. In the top sub-figure, there are five nodes, each with a single parent in the taxonomy, where $v_{1}\to v_{2}\to v_{3}\to v_{4}$ and $v_{5}$ are the candidate nodes and the query node, respectively. Hence, the DNG model needs to estimate the inheritance vector $\bm{s}_{5}$ on these candidate nodes. After carrying out the inference, the estimated $\bm{s}_{5}$ is $[0,0,0.8519,0,0]$, indicating $v_{3}$ is its only “parent” with the inheritance factor $0.8519$ and it does not inherit any feature from any other nodes. Since the inheritance factor of $v_{3}$ is the largest and others are $0$, the appropriate anchor of query $v_{5}$ is $v_{3}$. Figure 4 (b) depicts a more complicated example in which the convoluted relationships could more convincingly demonstrate DNG’s ability. The matching process for the query node $v_{7}$ is to estimate $\bm{s}_{7}$ on other nodes, and the result is $[0,0,0.4116,0.6156,0,0,0]$, indicating $v_{7}$ inherits features from both of $v_{3}$ and $v_{4}$. Similarly, appropriate anchors are $v_{3}$ and $v_{4}$ since all other factors are equal to zero. Another notable finding is that $v_{7}$ (“campus network”) inherits more features from $v_{4}$ (“computer network”) than from $v_{3}$ (“computer security”), despite the fact that both $v_{3}$ and $v_{4}$ are the “parents”. This is consistent with their ground-truth relations in the MAG-CS dataset, which further validates the DNG’s superiority in identifying appropriate anchors for queries in taxonomic structures.

One fundamental contribution of this paper is capturing the directionality of the is-a relation under the non-Gaussian constraint; thereby, the structure of a taxonomy could be illustrated. Theoretically, to validate this, we need to solve the exact backward equation (i.e., $\bm{v}_{j}=f(\bm{v}_{i})$) under the non-Gaussian constraint to see if it obeys the reversed form of Eq. 3 (i.e., $\bm{v}_{j}=\sum_{v_{i}\in\mbox{PA}_{j}}s_{ji}\bm{v}_{i}+\bm{u}_{j}$). However, despite the fact that the forward equation (see Eq. 3) has been theoretically proven correct, it is still difficult to determine the exact backward equation due to the lack of its prior knowledge. Consequently, we devise an alternative synthetic experiment to serve a similar purpose. Specifically, on the one hand, the distance between the actual and predicted features is also a measure of model’s reliability, with a lower value indicating better performance. On the other hand, supposing the backward equation obeys the reversed Eq. 3, the difference between the distances computed by the forward and backward equations could reflect the “deviation degree” of the backward one. It is anticipated that this “deviation degree” will have a larger value for nodes with non-Gaussian supplementary features compared with that for Gaussian ones. We use a uniform distribution as a non-Gaussian distribution. Consequently, these distance differences of a uniformly-distributed and a Gaussianly-distributed supplementary features are computed to evaluate the reasonableness of the hypothetical backward equation in this section.

To conduct the experiment described above, two virtual taxonomies with four nodes and an identical structure (see Figure 5) are constructed using a uniform and a Gaussian distribution, respectively, where the edge set is $\{v_{1}\to v_{2}\to v_{4}\to v_{3}\}$ with inheritance factors $\{1.5,0.5,1.0\}$. The DNG model is then employed to estimate the matrix $\bm{S}$ and the supplementary feature $\bm{U}$ under these two distributions. For the uniform distribution, the distance between the actual and the predicted features with forward equation is: $\{0.51,0.58,0.50,0.59\}$, while the distance between the actual and the backward-predicted features is $\{0.58,1.25,1.63,1.13\}$. An analogous procedure is followed to obtain the distances for the Gaussian distribution: $\{0.79,0.84,0.83,0.83\}$ (forward) and $\{0.79,1.47,1.44,1.11\}$ (backward). As a result, the mean ratios of the “deviation degree” for the uniform and Gaussian distributions are 107.19% and 45.56%, respectively. The result implies that the hypothetical backward equation incurs a higher loss for the uniform distribution, demonstrating the irreversibility of Eq. 3 under the non-Gaussian constraint.

Apart from demonstrating DNG’s ability in capturing the directionality, we also conduct experiments to validate its ability in capturing the entire taxonomic structure. Figure 6 presents the estimated inheritance matrices $\bm{S}$ of the taxonomy (see Figure 5) under different distributions. As illustrated in the upper matrix, compared to the estimated $\bm{S}$ with Gaussian distribution, the one with non-Gaussian constraint (the top figure) more precisely capture the taxonomic structure, since the ground-truth “parents” have the larger inheritance factor, validating DNG’s ability in modeling taxonomic structure.