InductWave: Inductive Multi-Hop Logical Query Answering on Knowledge Graphs

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

InductWave: Inductive Multi-Hop Logical Query Answering on Knowledge Graphs

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

artificialintelligence knowledgerepresentation reasoning

artificial intelligence, reasoning, knowledge representation

InductWave: Inductive Multi-Hop Logical Query Answering on Knowledge Graphs

arXiv:2607.07422v1 [cs.AI] 8 Jul 2026

Mayank Kharbanda, Michael Cochez, Rajiv Ratn Shah, Raghava Mutharaju

Abstract—Logical Multi-Hop Query Answering over Knowledge Graphs (KGs) can be formulated as querying, with an implicit completeness assumption. Current works mainly focus on Existential First Order Logic (EFO) queries. These EFO queries contain conjunction(∧), disjunction (∨), and negation (¬) operators. Most existing works employ transductive reasoning, meaning they are not capable of reasoning over entities unseen during training. In the real world, there is a resource scarcity, and we cannot train a model with all the nodes of a large KG. Hence, we propose InductWave, a wavelet-based inductive embedding method for logical query answering on large KGs. Here, the training graph consists of fewer nodes than the test graph. Our model performs on par with the baseline models while having half the number of message-passing layers. It outperforms all of them in most cases, with 75% of the layers. These fewer resource requirements enable us to evaluate InductWave on massive graphs, such as Wiki-KG. We test our model using extensive experiments across varying train-test graph proportions of the FB15k-(237) dataset, comparing it with the state-of-theart models. The code and datasets for the model are available at https://github.com/kracr/inductwave/. Index Terms—Knowledge Graphs, Logical Query Answering, Multi-Hop Query Answering, Inductive Query Answering, Graph Wavelets.

I. I NTRODUCTION 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 (∧), disjunction (∨), and negation (¬) 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

M. Kharbanda ([email protected]) is with IIIT-Delhi, India, and guest at Vrije Universiteit, Amsterdam, The Netherlands. M. Cochez ([email protected]) is with Ellis Institute Finland and Åbo Akademi University, Finland, prior with Vrije Universiteit, Amsterdam, The Netherlands. R. Shah ([email protected]) is with IIIT-Delhi, India and R. Mutharaju ([email protected]) is with IIT Palakkad, Kerala, India.

relations and can handle new nodes and/or relations at test time. Current State-Of-The-Art (SOTA). Traditional queryanswering 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 GNNQE [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 (NBFNet) [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

Field Medal

Laurent Schwatz

École Normale Supérieure

Field Medal

Laurent Schwatz

École Normale Supérieure

France

Jean Christophe Yoccoz

École Polytechnique

Solutions

France win

graduate

citizen

Fig. 1. Toy example for inductive query answering where the test graph (Gtest ) contains additional nodes (represented by blue color) than the train graph (Gtrain ). Dotted circles represent the solution for the query, Q1 - Name the university from which a French Field medalist graduated, with FOL as Q = v.∃u : win(F ieldM edal, u) ∧ citizen(F rance, u) ∧ graduate(u, v)

compatible with graph wavelet embedding. This enables efficient computation of WAVBFNet on GPU hardware. It reduces the memory complexity of WAVBFNet from O(2b|E|d) to O(b|V|d + |E|d). Here, b is the batch size, |E| and |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. II. R ELATED W ORK 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 multihop 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 (∨) and conjunction (∧) operators. Using the beta distributions for embedding, BetaE [19] incorporated the negation operator (¬) 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 queryanswering 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 subgraph 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. III. P RELIMINARIES Inductive Reasoning on KG. A Knowledge Graph G(V, E, R) is a directed graph with a set of nodes V, a set of relations R, and a triple set E. E = {(es , r, eo )|es , eo ∈ V, r ∈ R}

(1)

Given |V| = N and |R| = M , we say the query answering is inductive if the training KG (Gtrain ) contains α1 nodes and β1 relations, such that |α1 | < N and/or |β1 | < M , i.e., the training nodes/relations are a subset of G. The test graph (Gtest ) contains α2 nodes and β2 relations, such that α2 \α1 ̸= ϕ and/or β2 \ β1 ̸= ϕ. For our work, we train on all relations (|β1 | = M, |α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 (Gtrain ), we get École Normale Supérieure as the answer. While in the test graph (Gtest ), we have two new nodes: Jean Christophe Yoccoz and École Polytechnique. Hence, we obtain an additional answer for the same query as École Polytechnique. First Order Logic. First Order Logic (FOL) query Q utilizes conjunction (∧), disjunction (∨), existential quantification (∃), and negation (¬) as its logical operators. We exclude universal quantification (∀) 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 V1 , . . . , Vk , and a constant entity set Va ⊆ 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? .∃V1 , . . . , Vk : c1 ∨ c2 ∨ ... ∨ cn

(2)

Each clause ci is a conjunction of one or more relational binary functions (positive or negative) r(x, y), r ∈ R, where x and y can be a constant or a variable. For query Q1, the FOL would be Q = v.∃u : win(F ieldM edal, u) ∧ citizen(F rance, u) ∧ graduate(u, v). Fuzzy Set. A Fuzzy set is a relaxed conventional set, defined as A = {(x, µ)|x ∈ U }. µ ∈ [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]. IV. I NDUCT WAVE 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 (∧), disjunction (∨), and negation (¬). 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]. A. Relation Projection Given a fuzzy set of head entities fhe and a query relation q, the relation projection operation provides a fuzzy set of all the tail entities fta that can be reached from fhe using q

(Equation 3). In Q1, for example, for the relation win, fhe is a one-hot vector with the probability of Field-Medal being 1. The relation projection Pq (fhe ) for win will produce fta , where the probability of all the individuals who win the Fields Medal (in the graph) approaching 1. Pq (fhe ) : [0, 1]V 7→ [0, 1]V

(3)

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. 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 Ar be an adjacency matrix containing all the edges for relation r (r ∈ R) of the KG, GX (GX = Gtrain /Gvalid /Gtest dataset). Let Ars be the symmetric matrix generated from Ar , with a degree matrix Drs (u, u), defined as 1 r (A (u, v) + Ar (v, u)) 2 X Drs (u, u) = Ars (u, v) Ars (u, v) =

(4) (5)

v∈V

Ars (u, v) > 0 indicates that a relation r exists between node u and v. The direction of this edge is captured by r r Θ(g) r (u, v) = 2πg(A (u, v) − A (v, u))

(6)

where g is a hyper-parameter with values in the range [0, 0.25]. If there is a direct edge Ar (u, v) ∈ E, but not the reverse (g) edge Ar (v, u) ∈ / E, then Θr (u, v) will be positive while (g) Θr (v, u) will be negative. Conversely, if the relational edge (g) is bi-directional or does not exist, then Θr (u, v) = 0. We define the original relational adjacency matrix Ar , using a hermitian matrix as Hr(g) = Ars ⊙ exp (ir Θ(g) r )

(7)

here, ir is the imaginary dimension for relation r, and ⊙ is element-wise multiplication. Ars captures edge existence, (g) while exp (ir Θr ) accounts for the direction. Inspired by [33], we propose the unnormalized Laplacian for relation r as r r(g) Lr(g) = Drs − Ars ⊙ exp (ir Θ(g) un = Ds − H r )

(8)

−1/2 Lr(g) = D−1/2 Lr(g) n z un Dz

(9)

where Dz is the sum of all degree matrices Drs , ∀r ∈ R, defined as XX Dz (u, u) = Ars (u, v) (10) r∈R v∈V

We use this normalized KG Laplacian (Equation 9) to generate graph wavelet embedding, which is subsequently used in WAVBFNet for relation projection. 2) Graph Wavelet Embedding: In this section, we generate graph wavelet embeddings for WAVBFNet using the KG Laplacian (Equation 9). 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 R relations, i.e., a KG. The KG Laplacian (Equation 9) 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(g) r is expressed as Lrn = Ur Λr Ur† (omitted g from Ln r r† for simplicity). Here, U consists of eigenvectors (U is the conjugate transpose of Ur ), and Λr = Diag{λ1 , ...λn } is the diagonal matrix containing ordered eigenvalues. Let gs be a low-pass heat filter, gs (λ) = e−λ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 Ψr = Ur gs (Λr )Ur†

ϕru (tj , tk ) = E[ei(tj Ψu (re)+tk Ψu (im)) ] 1 X i(tj Ψrvu (re)+tk Ψrvu (im)) e = |V|

(12)

v∈V

We define KG Laplacian as a set of these relational Laplacians, (g) r(g) r(g) Lun = {Lun |r ∈ R}. The proof of Lun being positive semi-definite can be found in the Supplementary Material. In Equation 8, the rth Laplacian contains information about that specific relation r. However, there is no information r(g) exchange between two distinct relational Laplacians Lun , s(g) Lun (r, s ∈ R, r ̸= s). This may lead to loss of interrelational context within a KG. To address this information loss, we normalize the relational Laplacian using the degree of a node in the entire KG, GX , rather than just based on relation r. The normalized magnet Laplacian for relation r is defined as −1/2 = D−1/2 (Drs − Ars ⊙ exp(ir Θ(g) z r ))Dz

from all other nodes, in relation r. The characteristic function for node u is defined as

(11)

The low-pass filter (gs ) 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 Ψr (Equation 11) 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 Ψr . This embedding is used to measure the expected amount of information a node u receives

where Ψru (re) and Ψru (im) represent the real and imaginary parts of Ψru . tj , tk ∈ R are the uniform random samples taken from the joint distribution. The graph wavelet embeddings with d/2 samples is defined as χru = [Re(ϕru (tj , tk )), Im(ϕru (tj , tk ))](t1j ,t1k ),...,(t(d/2)j ,t(d/2)k ) (13) The resulting graph wavelet embeddings, χru , will be ddimensional, with d/2 real and d/2 imaginary components. We use this wavelet embedding (Equation 13) for the WAVBFNet in the following section. 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 13) 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 14). h(0) v ← xv q

(14)

here, xv is the probability of node v in fhe (fuzzy set of head nodes). Since we are working with complex wavelet embedding, we split the vector (Equation 14) into real and (0) (0) imaginary parts and handle them separately. hvre = hv[:i/2] (0) (0) being the real vector and hvim = hv[(i/2)+1:] the imaginary part. In the message passing method, we define the M ESSAGE for a node v as a function of its neighbor’s embedding (t−1) (hx ), the relation embedding (wq (x, r, v) | (x, r, v) ∈ E), and the wavelet embeddings of the neighbor (χrx from Equation 13). The function for the real part is defined as r M ESSAGE(h(t−1) xre , wqre (x, r, v), χxre )

= h(t−1) ⊙ (Wr q + br )re ⊙ (w1 + w2 χrxre ) (15) xre The term (Wr q + br )re indicates that the relation embedding is dependent on the query relation q. The product of the first

B. 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 y1 , y2 ∈ [0, 1]V . The conjunction (∧), disjunction (∨), and negation (¬) operations are represented by the following formulations, respectively.

C(y1 , y2 ) = y1 ⊙ y2

(20)

D(y1 , y2 ) = y1 + y2 − y1 ⊙ y2

(21)

N (y1 ) = 1 − y1 Wavelet Embedding

Node Embedding

where ⊙ is the element-wise multiplication and 1 is a vector of all ones. C. Training Method

Relation Embedding

Fig. 2. WAVBFNet message passing. Here ⊙ is element-wise multiplication, ⊕ is element-wise addition, w1 and w2 are parameters. The shadow under each vector and operator represents the real and imaginary parts working in parallel.

two terms in Equation 15 is analogous to the link prediction method DistMult [35]. The expression (w1 + w2 χrxre ) represents a linear combination of the former two terms, with and without the wavelet embedding (χrxre ). 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 (t−1) r h(t) vre ←AGG({M ESSAGE(hxre , wqre (x, r, v), χxre ) |

(x, r, v) ∈ E(v)} ∪ {h(0) vre })

(16)

(t−1) r h(t) vim ←AGG({M ESSAGE(hxim , wqim (x, r, v), χxim ) | (x, r, v) ∈ E(v)} ∪ {h(0) (17) vim }) (t) (t) (t) hv ←CON CAT (hvre , hvim ) (18)

Note, we have concatenated the real and imaginary embed(t) (t) dings (hvre and hvim ) 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 (fta ). Thus, the relation projection described in the Equation 3 can be expressed as the following function Pq (fhe ) = σ(F F (h(T ) )

(22)

(19)

where σ is the sigmoid activation function that maps all values to the range [0, 1].

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 crossentropy 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 1 X log p(u|Q) L=− |AQ | u∈AQ X 1 log (1 − p(u′ |Q)) (23) − |V \ AQ | ′ u ∈V\AQ

here, AQ 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. V. E XPERIMENTS A. 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 WikiKG 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

Start Node Projection

Intermediate Node Intersection

Union

Answer Node Negation

Fig. 3. Standard query structures used to generate First Order Logical (FOL) queries. Here, p is relation projection, i is intersection, n is negation, and u is union operator.

its directly connected relations and its distance from predefined anchor nodes. Its FOL operators are implemented using CQDBeam [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: Vtrain , Vvalid , and Vtest . We create the training graph with Vtrain = τ ∗ V nodes, where τ = 0.4. This setup, including the value of τ , is based on [4]. The remaining nodes, (1 − τ ) ∗ V, are split equally between Vvalid and Vtest . The inference graphs for valid and test cases are constructed from V inf = Vvalid/test ∪ Vtrain , with the inference ratio V inf /Vtrain = 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 Vtrain . We generate a train graph from a subset Vtrain0 (Vtrain0 ⊊ Vtrain ) consisting of l nodes, selected randomly. Additionally, we create k random context graphs, each with l nodes, drawn from Vtrain , k resulting in entity sets Vctxt = {Vctxt1 , Vctxt2 , . . . , Vctxtk }. We generate inference graphs for valid and test cases from inf0 Vvalid/test = Vvalid/test ∪ Vtrain0 , respectively. We sample multiple sizes for Vtrain by varying τ ∈ {0.2, 0.3, . . . , 0.9} in Vtrain = τ ∗ V. This results in a diverse range of graphs with the ratio V inf /Vtrain ranging from 106% to 300%. Note that we omitted τ = 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.

TABLE I H YPERPARAMETERS OF I NDUCT WAVE ON DIFFERENT DATASETS .

Hyperparameter

GNN

#layers hidden dim (real) hidden dim (imaginary) composition aggregation

FB15k-(237) InductWave (3 layers)

FB15k-(237) InductWave (2 layers)

Wiki-KG InductWave (2 layers)

3 16 16 DistMult [35] PNA [37]

2 16 16 DistMult PNA

2 8 8 DistMult mean

MLP

#layer hidden dim.

2 64

2 32

Traversal Dropout

probability

0.45

0.35

Learning

batch size sample weight loss # negatives optimizer learning rate iterations (#batch) adv. temperature

36 uniform across queries BCE 32 Adam 5e-3 30,000 0.1

36 uniform across queries BCE 32 Adam 5e-3 30,000 0.12

6 uniform across queries BCE 32 Adam 5e-3 20,000 0.12

Graph Wavelet

scaling factor chebyshev polynomial apprx KG laplacian (g) Step size for t1 Step size for t2

10 37 0.25 4 3

10 5 0.25 4 3

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 ∗ |Vtrain | (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 V inf /Vtrain = 106%, we take k = 0. We train InductWave with Vtrain0 and k context graphs in rotation among epochs. The baseline models were trained on Vtrain0 . 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 |Vtrain | (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 Vtrain only. We train WAVBFNet with two-layer and three-layer configurations. NBF-Net in GNN-QE is trained with four messagepassing 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 t1 , t2 = [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 I presents the hyperparameters for InductWave. B. Result Analysis 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 Vtrain , without any context graphs, with a ratio of V inf /Vtrain = 175%. The HITS@10 results for this configuration are in Table II. 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) (avgp ). As expected, the Edge-type heuristic model performs the worst among all, as it relies on simple heuristics for query answering without any training.

TABLE II HITS@10 (%) SCORE FOR inductive QUERY ANSWERING , WHERE ALL THE NODES IN Vtrain ARE USED IN A SINGLE TRAINING GRAPH , inf V /Vtrain = 175%. AVGp IS THE AVERAGE OF POSITIVE QUERIES , AND AVG IS THE AVERAGE OF ALL THE QUERIES .

Model

avg

avgp

2in

3in

inp

pni

Edge-type Heuristic NodePiece-QE NodePiece-QE w/ GNN GNN-QE InductWave (3 layers) InductWave (2 layers)

8.0 44.8 45.5 41.7

10.1 10.9 26.5 50.9 51.6 47.9

17.6 25.2 42.2 62.7 67.2 63.1

8.2 8.3 18.1 37.1 36.4 33.5

9.9 7.9 11.2 32.2 31.3 29.2

10.6 11.8 35.8 72.7 74.5 70.1

13.0 13.0 44.2 83.5 84.9 81.3

9.6 9.2 26.3 57.6 57.6 54.1

8.2 8.6 21.6 43.4 42.3 38.8

5.3 7.0 24.7 38.3 41.3 33.3

8.5 6.8 14.6 30.3 28.6 27.3

2.6 32.7 34.6 29.2

3.1 46.0 49.0 43.5

8.7 29.4 29.4 28.3

3.7 27.2 26.5 24.7

2.8 33.4 33.2 26.6

TABLE III HITS@10 (%) SCORE FOR inductive QUERY ANSWERING FOR V inf /Vtrain = 175%. AVGp IS THE AVERAGE OF POSITIVE QUERIES , AND AVG IS THE AVERAGE OF ALL THE QUERIES .

Model

avg

avgp

2in

3in

inp

pni

Edge-type Heuristic NodePiece-QE NodePiece-QE w/ GNN GNN-QE InductWave (3 layers) InductWave (2 layers)

8.4 41.4 43.5 41.5

10.5 10.9 28.4 48.1 50.5 48.6

18.8 24.6 46.3 61.4 65.7 64.2

9.9 9.9 19.6 37.1 39.5 38.8

10.7 8.3 12.6 29.2 32.2 31.0

10.4 11.5 36.3 70.5 72.4 71.0

13.0 12.5 43.1 81.4 82.7 81.5

9.5 9.5 25.5 55.5 57.0 56.1

8.3 8.5 23.7 39.2 43.2 39.5

5.0 6.0 30.2 33.7 34.5 30.4

8.8 7.4 18.3 24.8 27.8 24.9

2.5 28.4 29.2 25.2

2.9 40.2 41.6 40.7

10.8 28.8 30.9 30.8

4.1 23.4 26.4 24.8

2.7 25.6 26.6 22.8

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 τ ). This is to further reduce the memory overhead for training. Table III presents the HITS@10 scores on FB15k-(237), where V inf /Vtrain = 175%. Here, InductWave (3 layers) consistently outperforms other models across all query types. Meanwhile, InductWave (2 layers) performs on par with GNNQE. Both versions of NodePiece-QE and the heuristic model exhibit similar trends as in Table II. Table IV presents HITS@10 results for all the V inf /Vtrain 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 (avgp ) in 121%. NodePiece-QE with GNN outperforms all for the positive queries in 106%. Table V consists HITS@3 score for all the V inf /Vtrain ratios. The results indicate similar trends as HITS@10 scores in Table IV. All these results, in Table IV and V, indicate that InductWave performs better as the ratio V inf /Vtrain increases (|α1 | ≪ |α2 |, Section III). 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. 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 VI presents the results of models on the large WikiKG 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. C. 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|E|d) to O(b|V|d). Here, b is the

TABLE IV HITS@10 (%) SCORE FOR inductive QUERY ANSWERING FOR ALL V inf /Vtrain RATIOS . AVGp IS THE AVERAGE OF POSITIVE QUERIES , AND AVG IS THE AVERAGE OF ALL THE QUERIES . Ratio

Model

avg

avgp

2in

3in

inp

pni

300%

Edge-type Heuristic NodePiece-QE NodePiece-QE w/ GNN GNN-QE InductWave (3 layers) InductWave (2 layers)

9.5 36.4 38.0 38.2

11.8 9.2 17.8 43.8 45.3 45.6

19.3 19.8 35.6 53.2 54.4 54.5

11.3 7.5 14.6 33.6 36.2 35.6

11.6 5.0 8.8 26.0 27.9 28.2

12.2 11.3 22.7 66.6 68.0 69.1

15.2 12.5 20.2 80.9 81.5 82.2

11.5 9.2 16.4 53.9 54.7 55.3

9.5 7.1 13.7 36.1 37.1 38.5

6.0 5.9 16.1 23.3 25.1 25.4

9.5 4.9 11.9 20.6 22.4 21.6

3.3 19.0 20.9 20.4

3.7 36.3 38.3 39.7

11.4 24.7 26.7 26.5

4.9 19.7 21.3 21.3

3.8 15.6 17.8 16.5

217%

Edge-type Heuristic NodePiece-QE NodePiece-QE w/ GNN GNN-QE InductWave (3 layers) InductWave (2 layers)

9.1 37.8 39.2 39.2

11.5 11.1 22.6 44.7 46.8 46.7

19.2 22.6 42.1 53.3 60.3 58.7

11.0 10.3 15.4 35.5 37.0 38.4

11.5 9.1 9.2 28.3 29.6 30.2

11.7 11.6 28.9 67.4 69.4 68.6

14.6 12.8 33.8 81.3 82.1 81.4

10.9 9.9 19.9 54.1 55.2 53.5

9.2 9.0 17.9 35.7 37.5 39.2

5.7 6.4 21.3 24.0 26.9 26.6

9.5 7.9 14.4 22.9 23.6 23.6

2.9 22.3 22.8 21.3

3.3 39.0 38.1 38.3

10.9 28.1 28.3 29.2

4.4 19.8 20.0 21.9

3.1 17.5 18.4 17.7

175%

Edge-type Heuristic NodePiece-QE NodePiece-QE w/ GNN GNN-QE InductWave (3 layers) InductWave (2 layers)

8.4 41.4 43.5 41.5

10.5 10.9 28.4 48.1 50.5 48.6

18.8 24.6 46.3 61.4 65.7 64.2

9.9 9.9 19.6 37.1 39.5 38.8

10.7 8.3 12.6 29.2 32.2 31.0

10.4 11.5 36.3 70.5 72.4 71.0

13.0 12.5 43.1 81.4 82.7 81.5

9.5 9.5 25.5 55.5 57.0 56.1

8.3 8.5 23.7 39.2 43.2 39.5

5.0 6.0 30.2 33.7 34.5 30.4

8.8 7.4 18.3 24.8 27.8 24.9

2.5 28.4 29.2 25.2

2.9 40.2 41.6 40.7

10.8 28.8 30.9 30.8

4.1 23.4 26.4 24.8

2.7 25.6 26.6 22.8

150%

Edge-type Heuristic NodePiece-QE NodePiece-QE w/ GNN GNN-QE InductWave (3 layers) InductWave (2 layers)

7.9 40.5 42.2 40.6

10.0 10.6 36.8 48.6 49.7 47.8

18.9 23.5 55.3 66.8 66.2 63.2

8.9 9.2 25.8 36.2 38.3 37.1

9.4 7.3 12.2 28.0 30.5 30.2

10.4 11.5 49.7 72.4 73.8 70.8

13.2 13.1 59.8 83.5 84.6 82.7

8.8 9.7 37.3 55.5 56.0 53.7

8.2 8.6 32.6 39.5 40.1 40.0

4.6 5.8 35.8 31.6 32.8 28.4

7.7 6.8 22.4 23.5 25.2 24.5

2.3 23.3 25.2 23.8

3.0 39.8 42.1 40.1

9.3 27.8 29.7 29.8

3.5 18.2 21.1 21.7

2.1 20.9 24.8 22.1

133%

Edge-type Heuristic NodePiece-QE NodePiece-QE w/ GNN GNN-QE InductWave (3 layers) InductWave (2 layers)

7.4 44.0 45.2 40.7

9.3 10.8 42.1 50.7 51.6 47.5

16.7 23.1 60.7 68.9 69.1 65.2

8.7 10.0 30.2 38.4 39.8 37.1

8.7 8.3 13.4 30.7 31.8 30.5

9.9 11.1 56.0 75.1 75.6 70.7

12.6 13.0 66.9 86.1 86.6 82.6

8.5 9.7 43.8 55.0 56.6 51.3

7.1 8.8 39.7 38.8 40.3 35.9

4.5 5.8 42.0 36.8 36.8 30.6

7.3 7.0 26.3 26.2 27.5 24.0

2.4 29.4 32.0 25.2

2.8 45.3 47.5 41.3

8.3 29.3 30.2 27.9

3.9 25.3 28.6 23.5

2.3 30.5 30.7 24.0

121%

Edge-type Heuristic NodePiece-QE NodePiece-QE w/ GNN GNN-QE InductWave (3 layers) InductWave (2 layers)

7.0 41.9 42.2 38.9

8.9 9.6 42.3 49.0 48.7 45.4

19.8 24.9 61.7 70.4 71.5 66.2

7.4 8.1 28.4 34.7 33.8 33.7

8.5 7.7 11.7 29.0 27.1 27.7

9.0 9.8 58.7 73.2 73.9 67.7

11.3 11.2 68.1 81.7 82.1 77.1

7.4 7.4 40.0 52.4 52.6 49.9

5.9 6.5 38.9 37.2 35.5 33.6

3.7 4.5 46.4 36.8 37.8 31.6

6.9 6.1 26.4 25.7 23.4 20.8

2.3 30.1 31.6 27.4

2.7 39.1 41.7 38.0

7.1 26.0 28.0 25.9

3.3 21.7 20.7 20.2

2.1 28.9 31.0 25.6

113%

Edge-type Heuristic NodePiece-QE NodePiece-QE w/ GNN GNN-QE InductWave (3 layers) InductWave (2 layers)

6.0 40.7 44.2 38.2

7.7 8.7 45.1 46.9 50.7 44.2

18.5 23.0 61.9 70.9 69.0 66.6

6.2 7.0 28.4 31.9 38.8 31.5

6.4 5.9 12.1 26.1 30.5 26.2

7.2 8.1 60.7 66.4 75.8 61.7

9.8 10.4 68.8 76.3 86.4 72.3

6.5 7.5 44.1 50.6 55.7 47.6

5.3 6.4 44.9 36.7 39.2 34.6

3.3 4.4 56.0 40.0 35.8 34.6

6.0 5.3 28.8 23.4 25.1 22.8

1.9 31.0 30.9 27.3

1.9 38.3 46.1 36.4

5.8 24.7 29.5 24.7

3.2 20.4 24.8 21.0

1.8 33.4 31.0 27.3

106%

Edge-type Heuristic NodePiece-QE NodePiece-QE w/ GNN GNN-QE InductWave (3 layers) InductWave (2 layers)

5.8 40.5 41.7 37.6

7.2 8.8 49.8 46.5 47.4 43.1

16.5 24.2 66.8 69.6 69.3 63.3

6.3 7.2 33.9 35.3 35.5 33.7

4.9 4.1 12.6 27.8 29.4 27.6

8.0 9.1 67.1 66.1 67.1 60.9

10.9 13.3 73.1 71.8 72.4 69.2

5.6 5.9 46.1 45.1 45.7 41.5

4.8 6.7 54.2 34.9 37.1 32.5

3.1 3.9 62.7 40.9 41.9 32.8

5.0 4.7 31.8 27.0 27.9 26.1

1.7 32.3 34.4 25.2

1.9 34.6 35.4 33.0

5.7 23.0 24.3 21.9

3.1 22.2 22.8 28.0

3.3 36.5 40.4 30.1

batch size, |E| and |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 16 and 17, improving the combined space complexity from O(2b|E|d) to O(b|V|d + |E|d). In this enhanced version, |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(|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 R relations. This decreases the peak memory requirements at any given time. Furthermore, the Graph Wavelet Embedding can also be distributed over V, which further minimizes the peak memory requirements. Additionally, we only need to compute χru for the triples present in the KG (Equation 15). 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

TABLE V HITS@3 (%) SCORE FOR inductive QUERY ANSWERING FOR ALL V inf /Vtrain RATIOS . AVGp IS THE AVERAGE OF POSITIVE QUERIES , AND AVG IS THE AVERAGE OF ALL THE QUERIES . Ratio

Model

avg

avgp

2in

3in

inp

pni

300%

Edge-type Heuristic NodePiece-QE NodePiece-QE w/ GNN GNN-QE InductWave (3 layers) InductWave (2 layers)

4.3 26.6 27.6 27.8

5.3 4.8 9.9 33.3 34.3 34.5

9.5 12.8 21.5 43.2 43.0 44.1

5.1 3.8 7.8 22.6 24.8 24.0

5.2 2.2 4.4 16.1 17.9 17.8

5.2 5.4 12.6 52.3 53.6 54.0

6.7 5.9 11.7 68.9 69.5 70.1

4.7 4.2 8.8 41.5 42.2 42.3

4.4 3.7 7.7 26.3 27.1 28.6

2.5 3.1 8.6 16.0 16.8 16.8

4.4 2.3 6.0 12.4 13.7 12.8

1.5 12.7 13.1 13.4

1.6 24.1 24.7 26.2

4.9 14.8 16.3 16.1

2.4 11.6 13.0 12.5

1.6 9.9 11.0 10.6

217%

Edge-type Heuristic NodePiece-QE NodePiece-QE w/ GNN GNN-QE InductWave (3 layers) InductWave (2 layers)

4.2 27.7 28.7 28.6

5.2 5.4 12.6 34.4 35.8 35.6

9.6 14.3 26.1 44.1 47.9 47.5

5.0 4.8 8.2 24.4 25.6 26.3

5.2 4.3 4.7 18.4 19.6 19.7

5.1 5.0 16.0 54.2 55.7 54.9

6.2 5.5 19.5 70.4 71.0 70.2

4.5 4.2 10.2 41.7 42.3 40.9

4.4 4.3 10.0 26.5 28.0 29.1

2.4 2.9 11.7 15.6 17.4 17.3

4.6 3.7 7.6 14.3 14.9 14.7

1.4 13.2 13.4 13.4

1.5 26.0 25.1 25.4

4.9 17.3 17.3 17.5

2.2 12.1 12.3 13.0

1.3 10.3 10.9 10.9

175%

Edge-type Heuristic NodePiece-QE NodePiece-QE w/ GNN GNN-QE InductWave (3 layers) InductWave (2 layers)

3.8 30.2 31.6 30.4

4.8 5.6 16.5 36.9 38.6 37.2

9.8 16.6 30.9 50.2 53.1 51.9

4.6 4.9 10.7 25.5 27.1 26.7

4.9 3.9 6.5 18.9 21.3 20.5

4.4 5.1 21.2 56.5 58.5 56.7

5.6 5.5 25.9 70.2 71.7 70.1

3.9 4.1 14.0 42.8 43.9 43.0

3.9 4.2 13.4 29.5 31.6 30.0

2.1 2.6 16.4 23.0 22.2 20.1

4.3 3.5 9.6 15.4 17.7 16.2

1.1 17.8 17.2 15.7

1.3 27.0 28.1 27.6

4.7 17.8 19.0 18.8

2.0 14.0 16.2 15.3

1.2 14.8 15.1 13.2

150%

Edge-type Heuristic NodePiece-QE NodePiece-QE w/ GNN GNN-QE InductWave (3 layers) InductWave (2 layers)

3.6 29.6 30.6 29.6

4.6 5.4 24.1 37.1 38.0 36.7

10.2 14.2 38.3 54.6 53.8 52.0

4.1 4.7 16.2 24.3 25.7 25.1

4.2 3.4 6.5 18.0 19.8 19.6

4.3 5.1 32.2 58.0 59.2 56.3

5.5 5.6 40.9 72.4 73.4 71.5

3.8 4.4 23.3 42.3 42.7 40.9

4.2 4.8 21.9 28.9 29.9 30.0

1.9 2.8 22.8 20.3 21.7 19.0

3.6 3.3 14.3 15.0 15.8 15.5

1.0 13.6 15.4 15.2

1.3 25.4 27.6 26.1

3.7 16.7 17.8 18.0

1.7 11.1 12.5 13.0

0.9 12.9 13.5 12.4

133%

Edge-type Heuristic NodePiece-QE NodePiece-QE w/ GNN GNN-QE InductWave (3 layers) InductWave (2 layers)

3.3 32.3 33.1 29.3

4.3 5.1 29.2 38.8 39.4 35.9

8.7 12.3 43.5 55.3 56.7 51.5

4.1 5.0 20.1 26.1 26.4 25.3

3.8 4.0 7.7 20.2 20.9 19.8

4.1 4.9 38.0 60.3 61.0 55.5

5.3 5.6 48.3 74.6 75.2 70.6

3.5 4.1 29.5 41.6 42.6 38.2

3.5 4.6 28.8 28.8 29.3 26.3

1.8 2.7 28.8 25.9 25.3 20.2

3.4 3.2 18.2 16.8 17.4 15.6

1.0 18.9 21.4 15.3

1.2 31.1 33.2 28.2

3.3 17.7 18.8 16.6

1.9 15.9 16.2 13.9

1.0 19.4 18.8 13.0

121%

Edge-type Heuristic NodePiece-QE NodePiece-QE w/ GNN GNN-QE InductWave (3 layers) InductWave (2 layers)

3.2 31.0 30.6 28.1

4.2 4.3 30.5 37.6 36.8 34.0

11.3 11.6 46.7 58.4 58.9 54.4

3.4 3.7 19.2 23.1 21.8 21.8

4.1 3.4 7.0 18.8 17.2 17.6

3.8 4.3 41.7 58.1 58.7 52.9

4.9 4.8 50.7 69.6 70.1 65.1

3.0 3.1 26.1 39.8 39.3 37.4

2.8 3.1 29.0 27.6 25.1 23.5

1.5 2.1 34.6 26.5 26.2 21.1

3.3 2.7 19.2 16.3 14.3 12.6

1.0 20.7 20.7 17.5

1.1 26.7 28.2 25.8

2.8 16.1 17.0 15.7

1.5 13.8 12.4 11.7

0.7 18.6 19.1 15.6

113%

Edge-type Heuristic NodePiece-QE NodePiece-QE w/ GNN GNN-QE InductWave (3 layers) InductWave (2 layers)

2.7 29.6 32.1 27.6

3.6 3.9 32.9 35.6 38.6 33.1

10.4 10.7 46.8 58.3 55.2 54.6

2.9 3.4 20.2 21.4 25.8 20.6

2.9 2.8 7.8 16.6 19.6 16.4

2.8 3.2 44.7 51.8 60.8 47.0

3.8 4.0 52.0 63.5 75.2 59.3

2.7 3.0 31.2 37.3 41.9 35.1

2.4 3.2 33.1 26.8 28.8 24.9

1.3 2.1 41.0 29.4 24.4 25.0

2.9 2.5 19.9 14.9 15.6 14.7

0.7 20.7 19.6 18.7

0.8 24.9 32.3 23.8

2.3 14.8 18.1 14.6

1.4 13.0 14.7 13.5

0.7 21.6 17.6 18.4

106%

Edge-type Heuristic NodePiece-QE NodePiece-QE w/ GNN GNN-QE InductWave (3 layers) InductWave (2 layers)

2.6 29.6 30.3 26.7

3.3 4.7 38.1 35.2 35.8 31.8

10.0 17.3 52.7 57.3 56.8 50.8

2.9 3.2 24.7 23.8 23.7 21.3

2.0 1.7 8.5 17.7 17.5 15.7

3.1 4.5 52.2 51.3 52.9 46.9

4.2 6.6 58.1 59.8 60.6 57.1

2.1 2.2 33.0 34.0 34.6 30.8

2.0 3.2 41.0 24.7 27.2 23.2

1.3 1.4 48.8 31.2 32.7 25.4

2.2 1.9 23.7 17.2 16.6 15.0

0.5 23.6 23.7 19.0

0.8 21.6 21.7 20.8

1.9 14.3 14.5 13.1

1.5 12.1 13.8 13.5

1.2 25.7 27.5 21.2

TABLE VI HITS@100 (%) SCORE FOR inductive QUERY ANSWERING FOR W IKI KG DATASET. AVGp IS THE AVERAGE OF THE POSITIVE QUERIES . Model

avgp

Edge-type Heuristic NodePiece-QE NodePiece-QE w/ GNN InductWave (2 layers)

4.3 5.2 11.4 26.8

15.1 22.3 63.5 69.3

1.5 1.7 1.8 8.0

1.7 1.6 1.2 9.4

4.9 4.7 8.7 94.4

9.7 8.0 13.9 97.2

2.4 2.4 3.9 47.2

1.5 1.6 1.5 27.4

1.3 3.4 7.4 17.5

0.7 1.2 0.9 2.2

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×3×d for each node. Subsequently,

this embedding is reduced to d dimensions using a feedforward layer through matrix multiplication. This includes matrices of dimensions N × 12d and 12d × d. WAVBFNet has separate real and imaginary messages. This leads to matrix multiplications with dimensions N × 12(d/2)

TABLE VII HITS@10 (%) SCORE FOR ABLATION STUDY ON inductive QUERY ANSWERING FOR V inf /Vtrain = 175%. AVGp IS THE AVERAGE OF POSITIVE QUERIES , AND AVG IS THE AVERAGE OF ALL THE QUERIES . H ERE ( W / O LC ) IS WITHOUT LINEAR COMBINATION , AND ( W CPLX ) IS WITH C OMPL E X LINK PREDICTION ALGORITHM . Model

avg

avgp

2in

3in

inp

pni

InductWave (3 layers) InductWave (3 layers) (w/o lc) InductWave (3 layers) (w cplx)

43.5 42.7 42.3

50.5 49.8 49.5

65.7 64.1 64.1

39.5 38.4 38.7

32.2 30.8 31.5

72.4 73.0 71.9

82.7 83.0 82.3

57.0 56.8 55.8

43.2 41.5 39.9

34.5 34.4 35.0

27.8 25.9 26.2

29.2 28.3 27.4

41.6 41.8 40.3

30.9 30.2 30.2

26.4 24.8 24.2

26.6 24.7 25.0

and 12(d/2) × (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. D. 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 15 is modified to the following relation. r M ESSAGE(h(t−1) xre , wqre (x, r, v), χxre )

= h(t−1) ⊙ (Wr q + br )re ⊙ χrxre xre

VI. C ONCLUSION 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 WIKIKG 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

(24)

In the second configuration, we replaced the DistMult link prediction method in (Equation 15) with the ComplEx [24] link prediction method. Since graph wavelet embeddings are complex, this was intended to test our model in a complexplane environment. Table VII 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 V inf /Vtrain = 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. E. Space and Run-Time Usage All the following details are for 175% ratio of FB15k-(237), where all the nodes in Vtrain 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.

ChatGPT and Gemini were used for basic text and code editing. R EFERENCES [1] A. Hogan, E. Blomqvist, M. Cochez, C. d’Amato, G. D. Melo, C. Gutierrez, S. Kirrane, J. E. L. Gayo, R. Navigli, S. Neumaier et al., “Knowledge graphs,” ACM Computing Surveys (Csur), vol. 54, no. 4, pp. 1–37, 2021. [2] S. Ji, S. Pan, E. Cambria, P. Marttinen, and S. Y. Philip, “A survey on knowledge graphs: Representation, acquisition, and applications,” IEEE transactions on neural networks and learning systems, vol. 33, no. 2, pp. 494–514, 2021. [3] Z. Zhu, M. Galkin, Z. Zhang, and J. Tang, “Neural-symbolic models for logical queries on knowledge graphs,” in International conference on machine learning. PMLR, 2022, pp. 27 454–27 478. [4] M. Galkin, Z. Zhu, H. Ren, and J. Tang, “Inductive logical query answering in knowledge graphs,” Advances in neural information processing systems, vol. 35, pp. 15 230–15 243, 2022. [5] M. Galkin, E. Denis, J. Wu, and W. L. Hamilton, “Nodepiece: Compositional and parameter-efficient representations of large knowledge graphs,” arXiv preprint arXiv:2106.12144, 2021. [6] Z. Zhu, Z. Zhang, L.-P. Xhonneux, and J. Tang, “Neural bellman-ford networks: A general graph neural network framework for link prediction,” Advances in Neural Information Processing Systems, vol. 34, pp. 29 476–29 490, 2021. [7] C. Donnat, M. Zitnik, D. Hallac, and J. Leskovec, “Learning structural node embeddings via diffusion wavelets,” in Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, 2018, pp. 1320–1329. [8] G. Huang, G. Dai, Y. Wang, and H. Yang, “Ge-spmm: General-purpose sparse matrix-matrix multiplication on gpus for graph neural networks,” in SC20: International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE, 2020, pp. 1–12. [9] K. Toutanova and D. Chen, “Observed versus latent features for knowledge base and text inference,” in Proceedings of the 3rd workshop on continuous vector space models and their compositionality, 2015, pp. 57–66. [10] W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovec, “Open graph benchmark: Datasets for machine learning on graphs,” Advances in neural information processing systems, vol. 33, pp. 22 118–22 133, 2020.

[11] W. Xiong, T. Hoang, and W. Y. Wang, “Deeppath: A reinforcement learning method for knowledge graph reasoning,” arXiv preprint arXiv:1707.06690, 2017. [12] X. V. Lin, C. Xiong, and R. Socher, “Multi-hop knowledge graph reasoning with reward shaping,” Apr. 18 2023, uS Patent 11,631,009. [13] X. Chen, M. Chen, W. Shi, Y. Sun, and C. Zaniolo, “Embedding uncertain knowledge graphs,” in Proceedings of the AAAI conference on artificial intelligence, vol. 33, no. 01, 2019, pp. 3363–3370. [14] S. Guo, Q. Wang, L. Wang, B. Wang, and L. Guo, “Knowledge graph embedding with iterative guidance from soft rules,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 32, no. 1, 2018. [15] ——, “Jointly embedding knowledge graphs and logical rules,” in Proceedings of the 2016 conference on empirical methods in natural language processing, 2016, pp. 192–202. [16] H. Wang, H. Ren, and J. Leskovec, “Entity context and relational paths for knowledge graph completion,” arXiv preprint arXiv:2002.06757, p. 47, 2020. [17] W. Hamilton, P. Bajaj, M. Zitnik, D. Jurafsky, and J. Leskovec, “Embedding logical queries on knowledge graphs,” Advances in neural information processing systems, vol. 31, 2018. [18] H. Ren, W. Hu, and J. Leskovec, “Query2box: Reasoning over knowledge graphs in vector space using box embeddings,” arXiv preprint arXiv:2002.05969, 2020. [19] H. Ren and J. Leskovec, “Beta embeddings for multi-hop logical reasoning in knowledge graphs,” Advances in Neural Information Processing Systems, vol. 33, pp. 19 716–19 726, 2020. [20] Z. Zhang, J. Wang, J. Chen, S. Ji, and F. Wu, “Cone: Cone embeddings for multi-hop reasoning over knowledge graphs,” Advances in Neural Information Processing Systems, vol. 34, pp. 19 172–19 183, 2021. [21] J. Sardina, C. Sardina, J. D. Kelleher, and D. O’Sullivan, “Analysis of attention mechanisms in box-embedding systems,” in Irish Conference on Artificial Intelligence and Cognitive Science. Springer, 2022, pp. 68–80. [22] X. Chen, Z. Hu, and Y. Sun, “Fuzzy logic based logical query answering on knowledge graphs,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 36, no. 4, 2022, pp. 3939–3948. [23] E. Arakelyan, D. Daza, P. Minervini, and M. Cochez, “Complex query answering with neural link predictors,” arXiv preprint arXiv:2011.03459, 2020. [24] T. Trouillon, J. Welbl, S. Riedel, É. Gaussier, and G. Bouchard, “Complex embeddings for simple link prediction,” in International conference on machine learning. PMLR, 2016, pp. 2071–2080. [25] M. Kharbanda, R. R. Shah, and R. Mutharaju, “Rcone: Rough cone embedding for multi-hop logical query answering on multi-modal knowledge graphs,” IEEE Transactions on Knowledge and Data Engineering, 2025. [26] D. Alivanistos, M. Berrendorf, M. Cochez, and M. Galkin, “Query embedding on hyper-relational knowledge graphs,” arXiv preprint arXiv:2106.08166, 2021. [27] K. Liang, L. Meng, M. Liu, Y. Liu, W. Tu, S. Wang, S. Zhou, X. Liu, and F. Sun, “A survey of knowledge graph reasoning on graph types: Static, dynamic, and multimodal,” 2022. [28] H. Ren, M. Galkin, M. Cochez, Z. Zhu, and J. Leskovec, “Neural graph reasoning: Complex logical query answering meets graph databases,” arXiv preprint arXiv:2303.14617, 2023. [29] M. Galkin, X. Yuan, H. Mostafa, J. Tang, and Z. Zhu, “Towards foundation models for knowledge graph reasoning,” arXiv preprint arXiv:2310.04562, 2023. [30] M. Galkin, J. Zhou, B. Ribeiro, J. Tang, and Z. Zhu, “Zero-shot logical query reasoning on any knowledge graph,” arXiv preprint arXiv:2404.07198, 2024. [31] B. Xu, H. Shen, Q. Cao, Y. Qiu, and X. Cheng, “Graph wavelet neural network,” arXiv preprint arXiv:1904.07785, 2019. [32] R. Liu, R. Yin, Y. Liu, and W. Wang, “Aswt-sgnn: Adaptive spectral wavelet transform-based self-supervised graph neural network,” in Proceedings of the AAAI conference on artificial intelligence, vol. 38, no. 12, 2024, pp. 13 990–13 998. [33] X. Zhang, Y. He, N. Brugnone, M. Perlmutter, and M. Hirn, “Magnet: A neural network for directed graphs,” Advances in neural information processing systems, vol. 34, pp. 27 003–27 015, 2021. [34] D. I. Shuman, P. Vandergheynst, and P. Frossard, “Chebyshev polynomial approximation for distributed signal processing,” in 2011 International Conference on Distributed Computing in Sensor Systems and Workshops (DCOSS). IEEE, 2011, pp. 1–8. [35] B. Yang, W.-t. Yih, X. He, J. Gao, and L. Deng, “Embedding entities and relations for learning and inference in knowledge bases,” arXiv preprint arXiv:1412.6575, 2014.

[36] A. Bordes, N. Usunier, A. Garcia-Duran, J. Weston, and O. Yakhnenko, “Translating embeddings for modeling multi-relational data,” Advances in neural information processing systems, vol. 26, 2013. [37] G. Corso, L. Cavalleri, D. Beaini, P. Liò, and P. Veličković, “Principal neighbourhood aggregation for graph nets,” Advances in neural information processing systems, vol. 33, pp. 13 260–13 271, 2020. [38] K. Bollacker, C. Evans, P. Paritosh, T. Sturge, and J. Taylor, “Freebase: a collaboratively created graph database for structuring human knowledge,” in Proceedings of the 2008 ACM SIGMOD international conference on Management of data, 2008, pp. 1247–1250. [39] Y. He, M. Perlmutter, G. Reinert, and M. Cucuringu, “Msgnn: A spectral graph neural network based on a novel magnetic signed laplacian,” in Learning on Graphs Conference. PMLR, 2022, pp. 40–1.

Mayank Kharbanda received his bachelor’s and master’s degrees in computer science from the University of Delhi, India, in 2018 and 2020, respectively. He is currently working towards a PhD in the Department of Computer Science at IIIT Delhi. He is also a guest at Vrije Universiteit Amsterdam, the Netherlands. His research interests include Knowledge Graphs, Graph Representation Learning, and discrete mathematics. He is a UGC-JRF/SRF fellow. More information at https://mayankkharbanda.gith ub.io/.

Michael Cochez is Principal Investigator (PS Fellow) at the ELLIS Institute Finland and Professor at Åbo Akademi University, Turku, Finland. He is also part-time at Vrije Universiteit Amsterdam, the Netherlands. He was a postdoc at Fraunhofer FIT, Germany and obtained his PhD from the University of jyväskylä, Finland. More information at http: //www.cochez.nl.

Rajiv Ratn Shah is an Associate Professor in the Department of Computer Science and Engineering at IIIT-Delhi and Head of the MIDAS Research Lab. Prior to joining IIIT-Delhi, he was a Research Fellow at Singapore Management University and earned his Ph.D. from the National University of Singapore. His research interests include multimodal AI, natural language processing, computer vision, and humancentered computing. More information at https://mi das.iiitd.ac.in/.

Raghava Mutharaju is an Associate Professor in the Data Science department and is part of the Mehta Family School of Data Science and AI at IIT Palakkad, Kerala, India. He leads the Knowledgeable Computing and Reasoning (KRaCR) Lab. Earlier, we worked at IIIT-Delhi, GE Research, IBM Research, Bell Labs, and Xerox Research. His research interests include Knowledge Graphs, ontology modelling, and explainable AI. He has published at several venues, such as AAAI, IJCAI, ACL, and ISWC. More information at https://kracr.github.io/.

−1/2

a particular relation. Thus, letting y = Dz Dz is diagonal implies

A PPENDIX A. 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]. Theorem 1. Let G(V, E, R) is a KG with a set of nodes V, a set of relations R, and a triplet set E = {(es , r, eo )|es , eo ∈ V, r ∈ R}, and |V| = N . Then, for all g ≥ 0, and r ∈ r(g) R Lr(g) are positive un and their normalized counterpart Ln semidefinite.

† −1/2 r(g) −1/2 x† Lr(g) Lun D z x = y† Lr(g) n x = x Dz un y ≥ 0.

Theorem 2. Let G(V, E, R) is a KG with a set of nodes V, a set of relations R, and a triplet set E = {(es , r, eo )|es , eo ∈ V, r ∈ R}. Then, for all g ≥ 0, and r ∈ R the eigenvalues r(g) of the normalized magnetic Laplacian Ln are contained in the interval [0, 2]. r(g)

Proof. By Theorem 1, we know that Ln has real, nonnegative eigenvalues. Therefore, we need to show that the lead eigenvalue, λN , is less than or equal to 2. The Courant-Fischer theorem shows that r(g)

x† Ln x . x̸=0 x† x

Proof. Let x ∈ C . For a relation r we first note that since r(g) (g) Lun is Hermitian we have Imag(x† Lun x) = 0. Next, we r use the definition of Ds and the fact that Ars is symmetric to observe that [33], [39].

λN = max

−1/2

Therefore, using (26) and setting y = Dz

u,v=1

−2

First, we observe that since Dz is diagonal, we have

r (g) As (u, v)x(u)x(v) cos(Θr (u, v))

N X

u,v=1

N X

y† Dz y =

r Ds (u, u)x(u)x(u)

−2

u=1

†

(g)

As (u, v)x(u)x(v) cos(Θr (u, v))

≤

As (u, v)|x(u)| +

N X

As (v, u)|x(v)|

N X

(g)

N X

As (u, v)|x(v)|

†

N X

r(g)

y Lun y ≤ 2

N X

As (u, v)|x(u)| = 2

u,v=1

u,v=1 (g)

As (u, v)x(u)x(v) cos(Θr (u, v))

N X

N X u=1

Ds (u, u)|x(u)| ≤ 2

u=1

u,v=1

As (u, v)(|x(u)| + |x(v)| ).

Therefore, since Ars is symmetric, we have

As (u, v)x(u)x(v) cos(Θr (u, v))

As (u, v)|x(u)| + N X

N X

≤

u,v=1

−2

N 1 X r 2 A (u, v)(|x(u)| + |x(v)|) 2 u,v=1 s

u,v=1

− 2x(u)x(v) cos(Θr (u, v)))

u,v=1

−2

As (u, v)(|x(u)| + |x(v)| (g)

N X

N X u,v=1

u,v=1

r(g)

y Lun y =

r 2 As (u, v)|x(u)|

u,v=1

−2

Dz (u, u)|y(u)|2

Next, we note that by (25), we have

r (g) As (u, v)x(u)x(v) cos(Θr (u, v))

u,v=1 N X

N X

Dz (u, v)y(u)y(v) =

u,v=1

u=1 N X

x, we have

−1/2 r(g) −1/2 (g) x† Dz Lun Dz x y† Lun y λN = max = max . x̸=0 y̸=0 y† Dz y x† x

N X † r(g) r 2Real x Lun x = 2 Ds (u, v)x(u)x(v) N X

x, the fact that

N X

|x(u)|

N X

! r

As (u, v)

v=1 2

†

Dz (u, u)|x(u)| = 2y Dz y.

u=1

As (u, v)

u,v=1

(g) 2 2 |x(u)| + |x(v)| − 2x(u)x(v) cos(Θr (u, v)) ≥

N X

(25)

r 2 2 As (u, v) |x(u)| + |x(v)| − 2|x(u)||x(v)|

u,v=1

N X

As (u, v)(|x(u)| − |x(v)|) ≥ 0.

u,v=1

r(g)

Thus, each Lun is positive semidefinite, for r ∈ R. For the normalized magnetic Laplacian, we note that XX −1/2 Lr(g) = D −1/2 Lr(g) , Dz (u, u) = Ars (u, v) n z un D z r∈R v∈V

(26) We are using Dz for normalization in place of Dsr , to get normalized value influenced by the complete graph rather than

B. Query Statistics and Results The number of queries generated for each dataset are provided in Table I. The statistics mentioned as the train graph are for the graph Vtrain0 .

TABLE I N UMBER OF QUERIES GENERATED FOR EACH DATASET RATIO AND QUERY TYPE . Ratio

Graph

2in

3in

inp

pni

300%

training validation test

10,066 17,088 15,851

15,000 50,000 50,000

40,000 50,000 50,000

50,000 50,000 50,000

10,000 10,000 10,000

30,000 10,000 10,000

217%

training validation test

18,453 17,516 17,153

15,000 50,000 50,000

40,000 50,000 50,000

50,000 50,000 50,000

15,000 10,000 10,000

50,000 10,000 10,000

40,000 10,000 10,000

175%

training validation test

30,903 17,797 17,188

15,000 50,000 50,000

40,000 50,000 50,000

50,000 50,000 50,000

15,000 10,000 10,000

50,000 10,000 10,000

40,000 10,000 10,000

150%

training validation test

42,203 16,916 17,379

30,000 50,000 50,000

50,000 50,000 50,000

30,000 10,000 10,000

50,000 10,000 10,000

134%

training validation test

57,242 15,614 15,544

50,000 50,000 50,000

50,000 10,000 10,000

40,000 10,000 10,000

50,000 10,000 10,000

122%

training validation test

73,373 13,842 13,556

50,000 50,000 50,000

50,000 5,000 5,000

40,000 5,000 5,000

50,000 5,000 5,000

113%

training validation test

93,861 10,193 10,412

50,000 10,000 10,000

50,000 5,000 5,000

106%

training validation test

109,976 5,598 6,948

50,000 10,000 10,000

50,000 1,000 1,000

133%

training validation test

10,000 10,000 10,000

WikiKG 10,000 10,000 10,000

Record · ID 349675 · SHA-256 6bb6f68509a9f3cf
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.