Mayank Kharbanda, Michael Cochez, Rajiv Ratn Shah, Raghava Mutharaju et al.: InductWave: Inductive Multi-Hop Logical Query Answering on Knowledge Graphs

1 Introduction↩︎

A Knowledge Graph (KG) [1] is a directed graph used to represent facts. It is a set of triples in the form of source, relation, and object. The KGs are used to extract non-trivial information from data by leveraging structural and logical features. These graphs encompass diverse domains, including healthcare, finance, e-commerce, and search. Tasks such as recommendation systems, link prediction, and knowledge retrieval are performed on KGs to extract novel information [2].

Multi-hop logical query answering over KGs involves answering First Order Logic (FOL) queries. It includes traversing more than one hop from a starting node in the KG. Current works mainly focus on Existential First Order Logic (EFO) queries consisting of conjunction (\(\wedge\)), disjunction (\(\vee\)), and negation (\(\neg\)) operators. For query answering, there are two primary ways to train a model. First is the transductive method, in which the nodes and relations in the training and test graphs are identical; only the number of triples (edges) in the test graph increases. The other is the inductive method, in which the model is trained on a subset of nodes and/or relations and can handle new nodes and/or relations at test time.

Current State-Of-The-Art (SOTA). Traditional query-answering languages, such as SPARQL, become inadequate while processing queries over incomplete or noisy data. To address this, neural logical query answering methods have been introduced. These models embed queries and the KG in a latent space and predict answers against noise and missing links.

There has been significant progress in recent years in neural methods for multi-hop logical query answering. At the same time, most of these methods are transductive. These models require training across all parts of the KG and often fail when encountering new nodes/relations at inference time. As knowledge and datasets expand in the real world, there is a need to process queries on massive KGs containing millions of nodes. However, due to resource constraints, it is often not feasible to train with all the nodes of these enormous KGs.

One way to address this issue is to train a model on a subgraph with fewer nodes and then extrapolate it to process queries on the larger graph. Inductive methods, such as GNN-QE [3] and NodePiece-QE, have been proposed to incorporate this idea, and they have outperformed transductive models [4], [5].

In an inductive setting, GNN-QE generally performs better than NodePieceQE for small or medium-sized graphs. However, GNN-QE employs a memory-intensive link-prediction method, NBF-Net [6]. NBF-Net makes training on large graphs challenging. In contrast, NodePiece-QE does not face such memory constraints, enabling it to handle larger graphs efficiently.

We introduce InductWave, a graph wavelet-based method for logical query answering. It leverages the structural information of nodes to strengthen link prediction. As a result, the model achieves capabilities similar to GNN-QE with fewer message-passing layers. Ultimately, this allows us to use a message-passing method to query large graphs with millions of nodes (Wiki-KG).

Contribution I: A novel method, WAVBFNet, for link prediction. We propose a novel message passing algorithm, WAVBFNet. The method combines Graph Wavelet embeddings [7] with the Neural Bellman-Ford Network (NBF-Net) [6] for link prediction. The former provides the structural context of a node to the latter message-passing method. WAVBFNet is used for the relation projection operation in the query answering process.

Contribution II: Efficient execution of the message passing. We extend the GE-SpMM [8] method to make it compatible with graph wavelet embedding. This enables efficient computation of WAVBFNet on GPU hardware. It reduces the memory complexity of WAVBFNet from \(O(2b|\mathcal{E}|d)\) to \(O(b|\mathcal{V}|d+|\mathcal{E}|d)\). Here, \(b\) is the batch size, \(|\mathcal{E}|\) and \(|\mathcal{V}|\) are the triple and node counts, and \(d\) is the embedding dimension.

Contribution III: Extensive Evaluation. We evaluate our model on a diverse proportion of training and inference nodes set from the FB15k-(237) [9] dataset. We also test our model on the Wiki-KG [10] dataset, which contains millions of nodes. The results are supported by an ablation study of InductWave, along with its space and runtime analysis.

2 Related Work↩︎

Multi-Hop Query Answering. In multi-hop reasoning, one approach is to traverse a path in a KG to perform link prediction [11]–[16]. These techniques improve the prediction for rare or complex relations. Another application of multi-hop reasoning is in answering complex logical queries. This involves processing FOL operators to obtain the answers. Our work aligns with this latter approach.

Graph Query Embedding (GQE) [17] and Query2Box [18] were the first to introduce methods to resolve queries containing disjunction (\(\vee\)) and conjunction (\(\wedge\)) operators. Using the beta distributions for embedding, BetaE [19] incorporated the negation operator (\(\neg\)) in the queries. There are geometric embedding methods, such as ConE [20] and Query2Geom [21], which embed queries as geometric shapes in the latent space. FuzzyQE [22] provides a fuzzy set of answers between the query traversal. GNN-QE [3] uses NBF-Net [6] for the relation projection and fuzzy operators for other FOL operations. CQD [23] employs a greedy approach of beam search for FOL operations, and ComplEx [24] for relational projection. RConE [25] and STARQE [26] handle the query answering in multi-modal and hyper-relational graphs, respectively. The detailed studies about the KG reasoning and logical query answering are in [27] and [28], respectively.

Inductive Logical Query Answering. Most logical query-answering methods discussed so far are transductive. These require training queries for each entity in the KG. To generalize the training process, inductive methods have been proposed.

GNN-QE [3], initially proposed for transductive reasoning, can also be used for inductive query answering [4]. Since, for each relation projection, the node and relation embeddings are initialized based on the query. The model is trained on a sub-graph of the KG. NodePiece-QE [4], [5] is another inductive method. It represents each node by its incoming (outgoing) relations. It captures high-level structural information through the node’s distance from a few predetermined anchor nodes. The model utilizes CQD [23] for FOL operations.

ULTRA [29], [30] learns generalized embeddings across multiple KGs. It trains on the relational structures of a few KGs and tests on an entirely new KG by comparing these structures. The model effectively caters to a new set of relations at test time.

Wavelets in Graphs. GraphWave [7] generates diffusion wavelets on an undirected graph for node embeddings. It captures the structural information of a node’s neighborhood via heat-kernel-based information flow. GWNN [31] proposes a Graph Wavelet Neural Network for node classification on an undirected graph. The model learns a diagonal filter to tune information from a neighbor’s wavelet transformation. While previous models focused on low-pass filters, ASWT [32] uses both band-pass and low-pass filters for graph wavelets. It combines GCN and Graph wavelets for node classification.

InductWave is an inductive, logical query-answering method based on message passing, similar to GNN-QE. However, it requires less memory, making it suitable for large graphs. The method uses graph wavelets in its framework. It trains on a sample of the KG and evaluates on the entire KG; thus, we use GNN-QE and NodePiece-QE as baselines. We exclude ULTRA from our comparison, because the method has fundamentally different goal. It generalizes query answering across multiple KGs, by training on a set of KGs.

3 Preliminaries↩︎

Inductive Reasoning on KG. A Knowledge Graph \(G(\mathcal{V},\mathcal{E},\mathcal{R})\) is a directed graph with a set of nodes \(\mathcal{V}\), a set of relations \(\mathcal{R}\), and a triple set \(\mathcal{E}\). \[\mathcal{E} = \{(e_s, r, e_o) | e_s, e_o \in \mathcal{V}, r \in \mathcal{R}\}\] Given \(|\mathcal{V}|=N\) and \(|\mathcal{R}|=M\), we say the query answering is inductive if the training KG (\(G_{train}\)) contains \(\alpha_1\) nodes and \(\beta_1\) relations, such that \(|\alpha_1| < N\) and/or \(|\beta_1| < M\), i.e., the training nodes/relations are a subset of \(G\). The test graph (\(G_{test}\)) contains \(\alpha_2\) nodes and \(\beta_2\) relations, such that \(\alpha_2 \setminus \alpha_1 \neq \phi\) and/or \(\beta_2 \setminus \beta_1 \neq \phi\). For our work, we train on all relations (\(|\beta_1|=M,\;\; |\alpha_1|<N\)).

Figure 1 provides a toy example. Given a query, Q1 - Name the university from which a French Field medalist graduated. In the training graph (\(G_{train}\)), we get École Normale Supérieure as the answer. While in the test graph (\(G_{test}\)), we have two new nodes: Jean Christophe Yoccoz and École Polytechnique. Hence, we obtain an additional answer for the same query as École Polytechnique.

First Order Logic. First Order Logic (FOL) query \(Q\) utilizes conjunction (\(\wedge\)), disjunction (\(\vee\)), existential quantification (\(\exists\)), and negation (\(\neg\)) as its logical operators. We exclude universal quantification (\(\forall\)) because it is rarely employed in real-world KGs, as noted in [19].

The query \(Q\) has a distinguished target variable \(V_?\) (answer to the query), a finite set of existentially quantified bound variables \(V_1, \ldots, V_k\), and a constant entity set \(\mathcal{V}_a\subseteq \mathcal{V}\). The queries are structured in Disjunctive Normal Form (DNF) to accommodate the union operator at the conclusion, thereby ensuring scalability for more complex queries. \[Q[V_?]=V_?.\exists V_1, \dots, V_k : c_1 \vee c_2 \vee ... \vee c_n\] Each clause \(c_i\) is a conjunction of one or more relational binary functions (positive or negative) \(r(x,y)\), \(r \in \mathcal{R}\), where \(x\) and \(y\) can be a constant or a variable. For query Q1, the FOL would be \(Q=v.\exists u: win(Field Medal, u) \wedge citizen(France,u) \wedge graduate(u,v)\).

Fuzzy Set. A Fuzzy set is a relaxed conventional set, defined as \(A = \{(x,\mu)| x \in U\}\). \(\mu \in [0,1]\) is the membership function of element \(x\) for the set \(A\). \(U\) is the universal set. Applying FOL operators on a fuzzy set of nodes relaxes the membership of intermediate answers of a sub-query and enhances interpretability [3].

4 InductWave↩︎

This section describes the three components of InductWave that handle FOL queries, such as Q1 in Figure 1. The first component, Relation Projection, processes different relations specified in the query. For example, in Q1, it executes the relations win, graduate, and citizen. The second component, Fuzzy Operations, provides details about how InductWave handles other FOL operators, including conjunction (\(\wedge\)), disjunction (\(\vee\)), and negation (\(\neg\)). The third component, Training Method, consists of additional information about the model, including traversal dropout and the loss function. All FOL operators are executed on a fuzzy set of entities to improve interpretability inbetween query execution [3].

4.1 Relation Projection↩︎

Given a fuzzy set of head entities \(\mathbf{f}_{he}\) and a query relation \(q\), the relation projection operation provides a fuzzy set of all the tail entities \(\mathbf{f}_{ta}\) that can be reached from \(\mathbf{f}_{he}\) using \(q\) (Equation 1 ). In Q1, for example, for the relation win, \(\mathbf{f}_{he}\) is a one-hot vector with the probability of Field-Medal being \(1\). The relation projection \(\mathcal{P}_q (\mathbf{f}_{he})\) for win will produce \(\mathbf{f}_{ta}\), where the probability of all the individuals who win the Fields Medal (in the graph) approaching \(1\). \[\label{eqn:relproj95gen} \mathcal{P}_q (\mathbf{f}_{he}) : [0,1]^{\mathcal{V}} \mapsto [0,1]^{\mathcal{V}}\tag{1}\] We present WAVBFNet for computing relation projections. The approach consists of two components: graph wavelets and NBF-Net. First, we introduce the Knowledge Graph Laplacian, which serves as a foundation for constructing graph wavelets. In the second part, we use the KG Laplacian to develop Graph Wavelet Embedding. Finally, in the WAVBFNet section, we combine wavelet embeddings with NBF-Net to create a relation projection function.

4.1.1 Knowledge Graph Laplacian↩︎

To generate the graph wavelet embeddings for WAVBFNet, we first need to calculate the KG Laplacian. A graph Laplacian measures the information flow through edges over time. The Laplacian is defined for a simple undirected graph, as its adjacency matrix is symmetric.

Directed graphs are asymmetric and, therefore, do not have a standard Laplacian. To address this, MagNet [33] introduced a magnet Laplacian for directed graphs. It represents the asymmetric adjacency matrix as a hermitian matrix, that preserves the directional information of each edge. Similar to the standard Laplacian, the Laplacian derived from this hermition matrix is positive-semidefinite. Hence, the magnet Laplacian has an orthonormal basis of eigenvectors associated with non-negative eigenvalues.

In a KG, each edge has a direction and a specific relation associated with it. The magnet Laplacian [33] is already defined for directed graphs. We extend the method and define a KG Laplacian that accounts for both direction and relation.

Let \(\mathbf{A}^r\) be an adjacency matrix containing all the edges for relation \(r\) (\(r \in\mathcal{R}\)) of the KG, \(G_{X}\) (\(G_{X}=G_{train}/G_{valid}/G_{test}\) dataset). Let \(\mathbf{A}_s^r\) be the symmetric matrix generated from \(\mathbf{A}^r\), with a degree matrix \(\mathbf{D}^r_s(u,u)\), defined as \[\begin{align} \mathbf{A}^r_s(u,v) &= \frac{1}{2} (\mathbf{A}^r(u, v) + \mathbf{A}^r(v, u))\\ \mathbf{D}^r_s(u,u) &= \sum_{v \in \mathcal{V}} \mathbf{A}_s^r(u, v) \end{align}\] \(\mathbf{A}^r_s(u,v)>0\) indicates that a relation \(r\) exists between node \(u\) and \(v\). The direction of this edge is captured by \[\begin{align} \mathbf{\Theta}_{r}^{(g)} (u, v) &= 2\pi g (\mathbf{A}^r(u, v) - \mathbf{A}^r(v, u)) \label{eqn:thetaf} \end{align}\tag{2}\] where \(g\) is a hyper-parameter with values in the range \([0, 0.25]\). If there is a direct edge \(\mathbf{A}^r(u, v)\in \mathcal{E}\), but not the reverse edge \(\mathbf{A}^r(v, u) \notin \mathcal{E}\), then \(\mathbf{\Theta}_{r}^{(g)}(u,v)\) will be positive while \(\mathbf{\Theta}_{r}^{(g)}(v,u)\) will be negative. Conversely, if the relational edge is bi-directional or does not exist, then \(\mathbf{\Theta}_{r}^{(g)} (u, v) =0\). We define the original relational adjacency matrix \(\mathbf{A}^r\), using a hermitian matrix as \[\mathbf{H}^{r(g)} = \mathbf{A}_s^r \odot \exp{(i_r\mathbf{\Theta}_r^{(g)})}\] here, \(i_r\) is the imaginary dimension for relation \(r\), and \(\odot\) is element-wise multiplication. \(\mathbf{A}_s^r\) captures edge existence, while \(\exp{(i_r\mathbf{\Theta}_r^{(g)})}\) accounts for the direction. Inspired by [33], we propose the unnormalized Laplacian for relation \(r\) as \[\begin{align} \label{eqn:un95laplacian} \mathbf{L}_{un}^{r(g)} = \mathbf{D}_s^r - \mathbf{H}^{r(g)} = \mathbf{D}_s^r - \mathbf{A}_s^r \odot \exp{(i_r\mathbf{\Theta}_r^{(g)})} \end{align}\tag{3}\] We define KG Laplacian as a set of these relational Laplacians, \(\mathbf{L}_{un}^{(g)}=\{\mathbf{L}_{un}^{r(g)}|r\in \mathcal{R}\}\). The proof of \(\mathbf{L}_{un}^{r(g)}\) being positive semi-definite can be found in the Supplementary Material.

In Equation 3 , the \(r^{th}\) Laplacian contains information about that specific relation \(r\). However, there is no information exchange between two distinct relational Laplacians \(\mathbf{L}_{un}^{r(g)}\), \(\mathbf{L}_{un}^{s(g)}\) (\(r,s \in \mathcal{R}, r \ne s\)). This may lead to loss of inter-relational context within a KG. To address this information loss, we normalize the relational Laplacian using the degree of a node in the entire KG, \(G_X\), rather than just based on relation \(r\). The normalized magnet Laplacian for relation \(r\) is defined as \[\begin{align} \mathbf{L}_{n}^{r(g)} &= \mathbf{D}_z^{-1/2}\mathbf{L}_{un}^{r(g)}\mathbf{D}_z^{-1/2} \nonumber\\ &= \mathbf{D}_z^{-1/2}(\mathbf{D}^r_s - \mathbf{A}^r_s \odot exp(i_r\mathbf{\Theta}_r^{(g)}))\mathbf{D}_z^{-1/2}\label{eqn:n95laplacian} \end{align}\tag{4}\] where \(\mathbf{D}_z\) is the sum of all degree matrices \(\mathbf{D}^r_s\), \(\forall r\in \mathcal{R}\), defined as \[\label{eqn:dz} \mathbf{D}_z(u,u) = \sum_{r\in\mathcal{R}}\sum_{v \in \mathcal{V}} \mathbf{A}^r_s(u, v)\tag{5}\] We use this normalized KG Laplacian (Equation 4 ) to generate graph wavelet embedding, which is subsequently used in WAVBFNet for relation projection.

4.1.2 Graph Wavelet Embedding↩︎

In this section, we generate graph wavelet embeddings for WAVBFNet using the KG Laplacian (Equation 4 ). GraphWave [7] proposed a diffusion wavelet embedding method for extracting structural information around a node in an undirected graph. We adapt this concept for a directed graph with \(\mathcal{R}\) relations, i.e., a KG.

The KG Laplacian (Equation 4 ) is different from the conventional undirected Laplacian, since it involves complex numbers rather than just the real numbers. The spectral decomposition of the normalized KG Laplacian for a relation \(r\) is expressed as \(\mathbf{L}_{n}^r = \mathbf{U}^r \Lambda^r \mathbf{U}^{r\dagger}\) (omitted \(g\) from \(\mathbf{L}_{n}^{r(g)}\) for simplicity). Here, \(\mathbf{U}^r\) consists of eigenvectors (\(\mathbf{U}^{r\dagger}\) is the conjugate transpose of \(\mathbf{U}^r\)), and \(\mathbf{\Lambda}^r = Diag\{\lambda_1,...\lambda_n\}\) is the diagonal matrix containing ordered eigenvalues.

Let \(\mathfrak{g}_s\) be a low-pass heat filter, \(\mathfrak{g}_s(\lambda) = e^{-\lambda s}\). Here, the scaling factor s is used to adjust the extent to which a distant neighbor of a node affects its embedding. The graph spectral wavelet for a relation \(r\) is defined as \[\begin{align} \label{eqn:graph95wavelet} \mathbf{\Psi}^r &= \mathbf{U}^r \mathfrak{g}_s (\mathbf{\Lambda}^r)\mathbf{U}^{r\dagger} \end{align}\tag{6}\] The low-pass filter (\(\mathfrak{g}_s\)) incorporates only the lower eigenvalue of a Laplacian, favoring smoothness in the signal. This smoothness leads to neighboring nodes having similar embeddings (graph homophily). However, computing \(\mathbf{\Psi}^r\) (Equation 6 ) is an expensive operation. Hence, to simplify this process, we use the Chebyshev polynomial approximation [34].

The graph wavelet embedding is obtained by sampling from the characteristic function of \(\mathbf{\Psi}^r\). This embedding is used to measure the expected amount of information a node \(u\) receives from all other nodes, in relation \(r\). The characteristic function for node \(u\) is defined as \[\begin{align} \phi^r_u (t_j,t_k) &= E[e^{i(t_j\mathbf{\Psi}^r_{u}(re)+t_k\mathbf{\Psi}^r_{u}(im))}]\nonumber\\ &=\frac{1}{\mathcal{|V|}}\sum_{v\in \mathcal{V}}e^{i(t_j\mathbf{\Psi}^r_{vu}(re)+t_k\mathbf{\Psi}^r_{vu}(im))} \end{align}\] where \(\mathbf{\Psi}^r_{u}(re)\) and \(\mathbf{\Psi}^r_{u}(im)\) represent the real and imaginary parts of \(\mathbf{\Psi}^r_{u}\). \(t_j, t_k \in \mathbb{R}\) are the uniform random samples taken from the joint distribution. The graph wavelet embeddings with \(d/2\) samples is defined as \[\label{eqn:wave95emb} \mathbf{\chi}^r_u=[Re(\phi^r_u (t_j, t_k)), Im(\phi^r_u (t_j,t_k))]_{(t_{1j}, t_{1k}),\ldots,(t_{(d/2)j}, t_{(d/2)k})}\tag{7}\] The resulting graph wavelet embeddings, \(\mathbf{\chi}^r_u\), will be \(d\)-dimensional, with \(d/2\) real and \(d/2\) imaginary components. We use this wavelet embedding (Equation 7 ) for the WAVBFNet in the following section.

4.1.3 WAVBFNet↩︎

The relation projection method, WAVBFNet, is constructed using two components: the graph wavelet embeddings and the Neural Bellman Ford Network (NBF-Net) [6].

GNN-QE [3] uses NBF-Net for the relational projection. NBF-Net initializes the embeddings for the source node and the query relation. It then performs message passing to obtain the embeddings of all the nodes. These embeddings are subsequently used to compute the probability of each node being the tail (for the given source node and relation) in the link prediction task. GNN-QE modifies NBF-Net to operate with a fuzzy set of source nodes instead of a single source node for the projection operation.

Our model, WAVBFNet, integrates graph wavelet embeddings (Equation 7 ) with NBF-Net, rather than relying solely on the latter. This addition of graph wavelet embedding provides extra structural information. We will see in the results section that combining the two helps in early convergence for our model, reducing the number of message-passing layers required.

In WAVBFNet, we begin by initializing the source nodes’ embeddings (Equation 8 ). \[\label{eqn:mp95init} \mathbf{h}^{(0)}_v \leftarrow x_v \mathbf{q}\tag{8}\] here, \(x_v\) is the probability of node \(v\) in \(\mathbf{f}_{he}\) (fuzzy set of head nodes). Since we are working with complex wavelet embedding, we split the vector (Equation 8 ) into real and imaginary parts and handle them separately. \(\mathbf{h}^{(0)}_{v_{re}} = \mathbf{h}^{(0)}_{v_{[:i/2]}}\) being the real vector and \(\mathbf{h}^{(0)}_{v_{im}} = \mathbf{h}^{(0)}_{v_{[(i/2)+1:]}}\) the imaginary part.

In the message passing method, we define the \(MESSAGE\) for a node \(v\) as a function of its neighbor’s embedding (\(\mathbf{h}^{(t-1)}_{x}\)), the relation embedding (\(w_{q}(x, r, v)\; | \; (x,r,v) \in \mathcal{E}\)), and the wavelet embeddings of the neighbor (\(\mathbf{\chi}^r_{x}\) from Equation 7 ). The function for the real part is defined as \[\begin{align} \label{eqn:mp95message} MES&SAGE (\mathbf{h}^{(t-1)}_{x_{re}}, w_{q_{re}}(x, r, v),\mathbf{\chi}^r_{x_{re}}) \nonumber\\ &= \mathbf{h}^{ (t-1)}_{x_{re}} \odot (\mathbf{W}_r\mathbf{q} + \mathbf{b}_r)_{re} \odot (\mathbf{w_1}+\mathbf{w_2}\mathbf{\chi}^r_{x_{re}}) \end{align}\tag{9}\] The term \((\mathbf{W}_r\mathbf{q} + \mathbf{b}_r)_{re}\) indicates that the relation embedding is dependent on the query relation \(q\). The product of the first two terms in Equation 9 is analogous to the link prediction method DistMult [35]. The expression \((\mathbf{w}_1+\mathbf{w}_2\mathbf{\chi}^r_{x_{re}})\) represents a linear combination of the former two terms, with and without the wavelet embedding (\(\mathbf{\chi}^r_{x_{re}}\)). A corresponding function can be deduced for the imaginary part as well. Note that we tested other link prediction methods, including ComplEx [24] and TransE [36], but DistMult performed the best among the three. The message passing for the WAVBFNet (Figure 2) is described as \[\begin{align} \mathbf{h}^{(t)}_{v_{re}} \leftarrow &AGG (\{ MESSAGE (\mathbf{h}^{(t-1)}_{x_{re}}, w_{q_{re}}(x, r, v), \mathbf{\chi}^r_{x_{re}}) \mid \nonumber\tag{10}\\ &(x, r, v) \in \mathcal{E}(v)\} \cup \{\mathbf{h}^{(0)}_{v_{re}}\})\\ \mathbf{h}^{(t)}_{v_{im}} \leftarrow &AGG (\{ MESSAGE (\mathbf{h}^{(t-1)}_{x_{im}}, w_{q_{im}}(x, r, v), \mathbf{\chi}^r_{x_{im}}) \mid \nonumber\tag{11}\\ &(x, r, v) \in \mathcal{E}(v)\} \cup \{\mathbf{h}^{(0)}_{v_{im}}\})\\ \mathbf{h}^{(t)}_{v} \leftarrow &CONCAT(\mathbf{h}^{(t)}_{v_{re}}, \mathbf{h}^{(t)}_{v_{im}}) \end{align}\] Note, we have concatenated the real and imaginary embeddings (\(\mathbf{h}^{(t)}_{v_{re}}\) and \(\mathbf{h}^{(t)}_{v_{im}}\)) at the end. We use PNA (Principal Neighborhood Aggregator) [37] as the aggregator function (\(AGG\)), unless specified otherwise.

After the message passing phase, the embedding is fed into a two-layer feed-forward network to obtain the fuzzy set of tail nodes (\(\mathbf{f}_{ta}\)). Thus, the relation projection described in the Equation 1 can be expressed as the following function \[\mathcal{P}_q(\mathbf{f}_{he}) = \sigma (FF(\mathbf{h}^{(T)})\] where \(\sigma\) is the sigmoid activation function that maps all values to the range \([0, 1]\).

4.2 Fuzzy Operations↩︎

We employ fuzzy set operations to implement the other FOL operators, following a similar approach to [3]. Since, these operators should ideally adhere to the laws of logic, such as commutativity, associativity, and closure.

Given the fuzzy sets of nodes from the relation projection as \(\mathbf{y_1},\mathbf{y_2} \in [0,1]^{\mathcal{V}}\). The conjunction (\(\wedge\)), disjunction (\(\vee\)), and negation (\(\neg\)) operations are represented by the following formulations, respectively. \[\begin{align} \mathcal{C}(\mathbf{y_1}, \mathbf{y_2}) &= \mathbf{y_1} \odot \mathbf{y_2}\\ \mathcal{D}(\mathbf{y_1}, \mathbf{y_2}) &= \mathbf{y_1} + \mathbf{y_2} - \mathbf{y_1} \odot \mathbf{y_2}\\ \mathcal{N} (\mathbf{y_1}) &= \mathbf{1} - \mathbf{y_1} \end{align}\] where \(\odot\) is the element-wise multiplication and \(\mathbf{1}\) is a vector of all ones. \[\boldsymbol{Z}_i^{(t)} = \sigma \left( \sum_{j \in \mathcal{N}^m(i)}\left(\sum_{l=1}^J(\boldsymbol{\phi}_{l})_{i,j}\boldsymbol{X}_j^{(t-1)}\Theta w_q(x,r,v)\right)\right)\]

4.3 Training Method↩︎

Traversal Dropout. Direct query-relation edges originating from the source nodes are randomly removed from the training graph with a probability of \(p\) [3]. This prevents the model from overfitting by limiting direct access to the trivial tail entities. Randomly dropping edges from the KG makes the model resilient to the incomplete nature of real-world graphs.

Loss Function. The model is trained using the binary cross-entropy loss. Since InductWave generates probability estimates for each node in the graph, negative sampling is not required. Instead, the probabilities for both positive and negative answers are directly included in the loss calculation. The loss is given as \[\begin{align} \label{eqn:loss1} L=& -\frac{1}{|\mathcal{A}_Q|}\sum_{u\in \mathcal{A}_Q} log\;p(u|Q)\nonumber\\ &-\frac{1}{|\mathcal{V}\setminus \mathcal{A}_Q|} \sum_{u'\in \mathcal{V}\setminus \mathcal{A}_Q} log\;(1 - p(u'|Q)) \end{align}\tag{12}\] here, \(\mathcal{A}_Q\) is the set of all the answers to the complex query \(Q\), and \(log\;p(u|Q)\) denotes the probability of the answer \(u\), if query \(Q\) is passed through InductWave.

5 Experiments↩︎

5.1 Experimental Setup↩︎

Datasets and Evaluation Metric. We use FB15k-(237) [9] and Wiki-KG [10] datasets in our study. The FB15k-(237) dataset is derived from Freebase [38]. It contains 237 relations and improves on the previous version by removing easy inverse relation leakage [36]. The dataset is used to assess the models with varying train-test graph proportions. The Wiki-KG dataset is part of the Open Graph Benchmark suite, which consists of realistic, large-scale datasets. The dataset features over \(2.5M\) nodes in its complete graph. This makes it an ideal choice for testing the models on a large graph. We evaluate all the models using the HITS scores.

Baselines. We use GNN-QE [3], [4] and NodePiece-QE [4], [5] as the baselines. GNN-QE uses NBF-Net for relation projection and employs fuzzy set operations for other FOL operators. In NodePiece-QE, a node’s embedding depends on its directly connected relations and its distance from predefined anchor nodes. Its FOL operators are implemented using CQD-Beam [23]. In another variant of NodePiece-QE, the node embeddings are processed through a relational GNN encoder before being passed to CQD-Beam. However, NodePiece-QE cannot handle the negation operator. So we compare it with non-negative queries only.

We are not including any transductive model for comparison, as they perform poorly for inductive reasoning, as studied in [4]. We use a heuristic method [4] as a baseline to evaluate the performance of simpler models in inductive settings.

We exclude ULTRA [29], [30] from our comparison because it addresses a different problem. It is a Foundation Model designed for zero-shot transfer across multiple KGs, while our work optimizes efficiency for a single graph. ULTRA employs dual training, which involves message passing for both relational and entity graphs (effectively training two GNN-QE encoders). This design incurs significant computational overhead, contradicting our primary goal of scalable inference. Additionally, we are already comparing InductWave against GNN-QE, which serves as the backbone of ULTRA’s reasoning module.

Training Graphs. In the first dataset, we divide the entities of the FB15k-(237) dataset into three disjoint subsets: \(\mathcal{V}_{train}\), \(\mathcal{V}_{valid}\), and \(\mathcal{V}_{test}\). We create the training graph with \(\mathcal{V}_{train} = \tau*\mathcal{V}\) nodes, where \(\tau=0.4\). This setup, including the value of \(\tau\), is based on [4]. The remaining nodes, \((1-\tau)*\mathcal{V}\), are split equally between \(\mathcal{V}_{valid}\) and \(\mathcal{V}_{test}\). The inference graphs for valid and test cases are constructed from \(\mathcal{V}^{inf}=\mathcal{V}_{valid/test} \cup \mathcal{V}_{train}\), with the inference ratio \(\mathcal{V}^{inf}/\mathcal{V}_{train}=175\%\). This dataset is intended for testing in the same environment, where GNN-QE was evaluated in [4].

To further reduce the memory footprint, we create a second set of datasets. In this case, instead of using a train graph consisting all the nodes from \(\mathcal{V}_{train}\). We generate a train graph from a subset \(\mathcal{V}_{train_0}\) (\(\mathcal{V}_{train_0}\subsetneq\mathcal{V}_{train}\)) consisting of \(l\) nodes, selected randomly. Additionally, we create \(k\) random context graphs, each with \(l\) nodes, drawn from \(\mathcal{V}_{train}\), resulting in entity sets \(\mathcal{V}^k_{ctxt} = \{\mathcal{V}_{ctxt_1}, \mathcal{V}_{ctxt_2}, \ldots, \mathcal{V}_{ctxt_{k}}\}\). We generate inference graphs for valid and test cases from \(\mathcal{V}^{inf_0}_{valid/test} = \mathcal{V}_{valid/test} \cup \mathcal{V}_{train_0}\), respectively. We sample multiple sizes for \(\mathcal{V}_{train}\) by varying \(\tau\in\{0.2, 0.3, \ldots, 0.9\}\) in \(\mathcal{V}_{train} = \tau*\mathcal{V}\). This results in a diverse range of graphs with the ratio \(\mathcal{V}^{inf}/\mathcal{V}_{train}\) ranging from \(106\%\) to \(300\%\). Note that we omitted \(\tau = 0.1\) because the query generation module [19] was unable to create queries due to the small graph size.

We use Wiki-KG to evaluate the scalability of our model. The KG consists of approximately \(2.5\) million nodes and more than \(16\) million triples. It has \(512\) unique relations. Similar to FB15k-(237), we create a training set that contains \(1.5\) million nodes. From this set, we randomly generate a training graph and \(k\) context graphs, each of size \(l\). Both the valid and test sets include an additional \(500k\) nodes, containing \(5\) million known and \(600k\) missing edges.

Query Generation. Queries are generated using the query generation module described in [19]. We utilize 14 different query structures, including 1p, 2p, 3p, 2i, 3i, pi, ip, 2u, up, pni, pin, inp, 2in, and 3in, where \(p\) is relation projection, \(i\) is intersection, \(n\) is negation, and \(u\) is union (Figure 3). Detailed statistics on the number of queries generated are available in the Supplementary Material.

Hyper-Parameters.

width=

In earlier models[18], [19], queries were processed in batches, with each batch containing a single type of query. The inability to merge different query types due to varying lengths hindered scalability as the number of query types increased. To address this issue,  [3] proposed a non-recursive approach to query execution, in which the queries are converted into postfix notation. This allows the use of stacks for query execution. Similarly, we also convert the queries to postfix notation for InductWave.

For FB15k-(237), we set \(l=0.5*|\mathcal{V}_{train}|\) (0.5 is used ensure less memory footprint), and generate two context graphs (\(k = 2\)), for all ratios except \(106\%\). We do the same for Wiki-KG. In the case \(\mathcal{V}^{inf}/\mathcal{V}_{train}=106\%\), we take \(k=0\). We train InductWave with \(\mathcal{V}_{train_0}\) and \(k\) context graphs in rotation among epochs. The baseline models were trained on \(\mathcal{V}_{train_0}\). The rationale behind generating \(k\) context graphs is that, at any given time, only one graph (amongst train and context graphs) will be in the memory. This graph would be smaller than \(|\mathcal{V}_{train}|\) (saving memory), while still providing additional context. Concurrently, we experimented with the dataset containing no context graphs (first dataset), where both InductWave and baselines are trained on \(\mathcal{V}_{train}\) only.

We train WAVBFNet with two-layer and three-layer configurations. NBF-Net in GNN-QE is trained with four message-passing layers, as in [4]. We do not train our models for negative query structures in Wiki-KG because generating negative queries requires adding reverse relations to the KG. This would effectively double the number of triples in the graph, which are already numerous. As in the baseline [4], we are not conducting experiments for GNN-QE on the Wiki-KG dataset due to GPU memory constraints.

For the Graph Wavelet parameters, an ablation study was deemed unsuitable, so we performed a grid search to determine the optimal values. The parameters explored included the scaling factor \(= [0.1, 1, 10, 50]\), \(g = [0.1, 0.15, 0.2, 0.25]\), and \(t_1, t_2 = [2, 3, 4, 5, 10]\). We used the chebyshev approximation parameter consistent with the original work [7]. For WikiKG, this parameter of chebyshev approximation was chosen specifically to reduce computational costs due to its large size. For traversal dropout, we tested values in \([0.2, 0.25, 0.3, 0.35, 0.4, 0.45, 0.5]\). All experiments for InductWave were conducted on 40GB Nvidia A100 GPUs. Table ¿tbl:tab:hyperparameter? presents the hyperparameters for InductWave.

5.2 Result Analysis↩︎

width=

width=

Initially, we test our model on the first dataset generated from FB15k-(237). This dataset consists of one training graph induced from all the nodes in \(\mathcal{V}_{train}\), without any context graphs, with a ratio of \(\mathcal{V}^{inf}/\mathcal{V}_{train} = 175\%\). The HITS@10 results for this configuration are in Table ¿tbl:tab:hits175worandtrain?. The average results indicate that InductWave, with a 3-layer WAVBFNet, outperforms GNN-QE, while the 2-layer model performs slightly worse. We believe that integrating wavelet embeddings enables WAVBFNet to more effectively capture the graph structure, which facilitates convergence with fewer message passing layers. Notably, the 2-layer version performs marginally inferior than GNN-QE, despite having half the layers. This makes it a suitable choice in scenarios with resource constraints. NodePiece-QE with GNN performs better than without GNN. However, it is still worse than GNN-QE and InductWave for positive queries (queries without a negation operator) (avg\(_p\)). As expected, the Edge-type heuristic model performs the worst among all, as it relies on simple heuristics for query answering without any training.

Since InductWave performs better in the previous scenario. We conduct additional experiments by generating small training graphs of size \(l\), along with context graphs (the second set of datasets, generated from FB15k-(237) by varying \(\tau\)). This is to further reduce the memory overhead for training. Table ¿tbl:tab:hits175? presents the HITS@10 scores on FB15k-(237), where \(\mathcal{V}^{inf}/\mathcal{V}_{train} = 175\%\). Here, InductWave (3 layers) consistently outperforms other models across all query types. Meanwhile, InductWave (2 layers) performs on par with GNN-QE. Both versions of NodePiece-QE and the heuristic model exhibit similar trends as in Table ¿tbl:tab:hits175worandtrain?.

width=

width=

Table ¿tbl:tab:hits1095all? presents HITS@10 results for all the \(\mathcal{V}^{inf}/\mathcal{V}_{train}\) ratios. Starting from the middle of the table, for the ratio \(150\%\), InductWave (3-layer) performs better than other models in all query types except 1p. InductWave (2-layer) performs on par with the GNN-QE model. As we examine higher ratios from here, such as \(175\%\), \(217\%\), and so on. We observe that our models, on average, outperform all the baselines. At these higher ratios, the performance of both variations (3-layer and 2-layer) converge, with the 2-layer version outperforming the 3-layer in the \(300\%\) ratio.

Conversely, as we move to lower ratios, \(133\%\), \(121\%\), and so on, the 2-layered version performs worse than GNN-QE. The average results of the baselines are converging to InductWave (3-layer), with GNN-QE surpassing it for the positive queries (avg\(_p\)) in \(121\%\). NodePiece-QE with GNN outperforms all for the positive queries in \(106\%\).

Table ¿tbl:tab:hits395all? consists HITS@3 score for all the \(\mathcal{V}^{inf}/\mathcal{V}_{train}\) ratios. The results indicate similar trends as HITS@10 scores in Table ¿tbl:tab:hits1095all?.

All these results, in Table ¿tbl:tab:hits1095all? and ¿tbl:tab:hits395all?, indicate that InductWave performs better as the ratio \(\mathcal{V}^{inf}/\mathcal{V}_{train}\) increases (\(|\alpha_1| \ll |\alpha_2|\), Section 3). This improvement may be attributed to the additional structural information InductWave receives through graph wavelets, particularly when there is limited information due to a small training graph. In extreme cases, when the training graph is significantly smaller than the complete graph (\(300\%\) ratio), there is very little information available for training. As a result, our model converges faster, and adding a third layer leads to overfitting on the small training graph, making it inferior to the 2-layered model.

width=

At low ratios, most of the necessary information from the complete graph is already present in the training graph. In such cases, additional message-passing layers tend to be more beneficial than merging wavelet embeddings. This is evident, as the 4-layered GNN-QE either shows similar results or outperforms InductWave for lower ratios. However, when the ratio is high, InductWave performs better because any additional information becomes crucial; in this scenario, we obtain that information through graph wavelets.

Therefore, InductWave is a suitable choice while working with massive graphs, especially when the training graph is much smaller compared to the complete graph. Although InductWave (2 layers) performs inferior in most cases, it remains a good option when the ratio is high or when there are resource constraints since it requires half as many layers as GNN-QE.

Table 1 presents the results of models on the large Wiki-KG dataset. We chose the two-layered InductWave due to its lower memory requirements. We were able to train the model on a GPU, which was previously not possible for GNN-QE due to its high memory footprint [4]. InductWave outperforms all baseline models across all query types.

5.3 Complexity Analysis↩︎

GE-SpMM. GE-SpMM [8] proposed an efficient approach for performing message passing through generalized sparse matrix multiplication. It performs in-place operations on GPU threads, resulting in lower memory requirements than traditional methods. NBF-Net used this approach, reducing its space complexity from \(O(b|\mathcal{E}|d)\) to \(O(b|\mathcal{V}|d)\). Here, \(b\) is the batch size, \(|\mathcal{E}|\) and \(|\mathcal{V}|\) are the number of triples and nodes respectively, and \(d\) is the embedding dimension.

We extend the GE-SpMM method to include in-place operations for graph wavelet embeddings, ensuring the method’s compatibility with WAVBFNet. We used this method for Equations 10 and 11 , improving the combined space complexity from \(O(2b|\mathcal{E}|d)\) to \(O(b|\mathcal{V}|d+|\mathcal{E}|d)\). In this enhanced version, \(|\mathcal{E}|d\) space is shared across the batch, since the wavelet embeddings remain the same.

NBF-Net contains four message passing layers. Though, WAVBFNet requires an additional \(O(|\mathcal{E}|d)\) space per batch at each layer. It saves space of 2 layers in InductWave (2 layers) and 1 layer in InductWave (3 layers).

Laplacian and Wavelet Embeddings. InductWave needs to compute an additional KG Laplacian and Graph Wavelet Embedding compared to GNN-QE. We can intelligently distribute the computation for both across \(\mathcal{R}\) relations. This decreases the peak memory requirements at any given time. Furthermore, the Graph Wavelet Embedding can also be distributed over \(\mathcal{V}\), which further minimizes the peak memory requirements. Additionally, we only need to compute \(\mathbf{\chi}^r_u\) for the triples present in the KG (Equation 9 ). Lastly, we can always tune the Chebyshev approximation hyperparameter according to the available resources. Thus, these computations can be efficiently managed according to the resources at hand.

Message Aggregation. Both WAVBFNet and NBF-Net use PNA for message aggregation. PNA (Principal Neighborhood Aggregator) aggregates along four types: mean, max, min, and std; and it scales them along three metrics: node degree, 1, and 1/node degree. For NBF-Net, this results in an intermediate embedding dimension of \(4 \times 3 \times d\) for each node. Subsequently, this embedding is reduced to \(d\) dimensions using a feed-forward layer through matrix multiplication. This includes matrices of dimensions \(N\times 12d\) and \(12d\times d\).

WAVBFNet has separate real and imaginary messages. This leads to matrix multiplications with dimensions \(N\times 12(d/2)\) and \(12(d/2)\times (d/2)\) for each of the real and imaginary parts. By dividing the message into two smaller matrix multiplications instead of one larger one, WAVBFNet saves both space and time.

5.4 Ablation Study↩︎

In this study, we compare InductWave against two configurations as part of an ablation analysis.

In the first test, instead of using a linear combination and introducing additional parameters, we directly multiply the wavelet embedding with the node and relation embeddings. So, Equation 9 is modified to the following relation. \[\begin{align} \label{eqn:mp95message95abl} MES&SAGE (h^{(t-1)}_{x_{re}}, w_{q_{re}}(x, r, v),\chi^r_{x_{re}}) \nonumber\\ &= h^{ (t-1)}_{x_{re}} \odot (W_rq + b_r)_{re} \odot \chi^r_{x_{re}} \end{align}\tag{13}\]

In the second configuration, we replaced the DistMult link prediction method in (Equation 9 ) with the ComplEx [24] link prediction method. Since graph wavelet embeddings are complex, this was intended to test our model in a complex-plane environment.

Table ¿tbl:tab:abl? presents results for InductWave (3 layers) without linear combination (w/o lc) and with ComplEx (w cplx). The results consists of HITS@10 scores for \(\mathcal{V}^{inf}/\mathcal{V}_{train} = 175\%\), Fb15k-(237) dataset. We can see from the table that the original InductWave performs better, on average and across most query structures, from both the configurations.

5.5 Space and Run-Time Usage↩︎

All the following details are for \(175\%\) ratio of FB15k-(237), where all the nodes in \(\mathcal{V}_{train}\) are used in a single training graph (the first dataset).

For the GNN-QE, the runtime for one training epoch was 7 minutes and 39 seconds, and GPU memory usage was 20.16 GB. In comparison, the InductWave (3 layers) model took 7 minutes and 9 seconds and used 7.57 GB of memory. Further, for the InductWave (2 layers) model, the runtime was 5 minutes 31 seconds and required 5.63GB of GPU memory.

Additionally, the one-time preprocessing time to generate the graph wavelet embedding (including the KG Laplacian) was 10 minutes and 50 seconds. This preprocessing time was common for both InductWave (2 layers) and InductWave (3 layers), as the hyperparameters for graph wavelet embeddings were identical for both versions.

From this information, we can conclude that our model is more memory and time efficient than GNN-QE, aside from the one-time preprocessing step for graph wavelet embeddings.

6 Conclusion↩︎

In this work, we present a scalable method for inductive logical query answering over KGs. The model is particularly well-suited for scenarios where the training graph is much smaller than the complete graph. It can effectively handle large graphs containing millions of nodes (Wiki-KG). Although the average query score for InductWave is the highest for WIKI-KG dataset, there is still scope for improvement, which could be considered for future work. A future direction could be to explore distributed training for large KGs. Another direction is to develop models that can handle other operators used in query answering.

Acknowledgments↩︎

This work is partly supported by the University Grant Commission of India, Snellius: the National Supercomputer, Netherlands; Overseas Research Fellowship, the Infosys Center for AI, the Center of Design and New Media, and the Center of Excellence in Healthcare at IIIT-Delhi. ChatGPT and Gemini were used for basic text and code editing.

6.1 KG Laplacian↩︎

The theorems here are directly extended from MagNet [33], and mentioned here for completeness. We first prove that the KG Laplacian for relation \(r\) is positive, semi-definite for both the normalized and the un-normalized Laplacian. We then show that the normalized KG Laplacian lies in \([0, 2]\), as for the Laplacian of undirected graphs. Other properties of the KG Laplacian can be extended from these proofs with the context of [33].

6.2 Hyperparameters↩︎

Table ¿tbl:tab:hyperparameter? presents the hyperparameters for InductWave. All experiments for InductWave were conducted on 40GB Nvidia A100 GPUs.

For the Graph Wavelet parameters, an ablation study was deemed unsuitable, so we performed a grid search to determine the optimal values. The parameters explored included the scaling factor \(= [0.1, 1, 10, 50]\), \(g = [0.1, 0.15, 0.2, 0.25]\), and \(t_1, t_2 = [2, 3, 4, 5, 10]\). We used the chebyshev approximation parameter consistent with the original work [7]. For WikiKG, this parameter of chebyshev approximation was chosen specifically to reduce computational costs due to its large size. For traversal dropout, we tested values in \([0.2, 0.25, 0.3, 0.35, 0.4, 0.45, 0.5]\).

6.3 Query Statistics and Results↩︎

width=

The number of queries generated for each dataset are provided in Table ¿tbl:tab:all95queries?. The statistics mentioned as the train graph are for the graph \(\mathcal{V}_{train_0}\).

References↩︎

---

1. M. Kharbanda (mayankk@iiitd.ac.in) is with IIIT-Delhi, India, and guest at Vrije Universiteit, Amsterdam, The Netherlands. M. Cochez (michael.cochez@abo.fi) is with Ellis Institute Finland and Åbo Akademi University, Finland, prior with Vrije Universiteit, Amsterdam, The Netherlands. R. Shah (rajivratn@iiitd.ac.in) is with IIIT-Delhi, India and R. Mutharaju (raghava@iitpkd.ac.in) is with IIT Palakkad, Kerala, India.↩︎