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

# InductWave: Inductive Multi-Hop Logical Query Answering on Knowledge Graphs
Source: [https://arxiv.org/html/2607.07422](https://arxiv.org/html/2607.07422)
Mayank Kharbanda, Michael Cochez, Rajiv Ratn Shah, Raghava MutharajuM\. 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\.

###### 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\(∧\\wedge\), disjunction \(∨\\vee\), and negation \(¬\\neg\) 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, with75%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\-the\-art models\. The code and datasets for the model are available athttps://github\.com/kracr/inductwave/\.

###### Index Terms:

Knowledge Graphs, Logical Query Answering, Multi\-Hop Query Answering, Inductive Query Answering, Graph Wavelets\.

## IIntroduction

A Knowledge Graph \(KG\)\[[17](https://arxiv.org/html/2607.07422#bib.bib1)\]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\[[20](https://arxiv.org/html/2607.07422#bib.bib17)\]\.

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\[[38](https://arxiv.org/html/2607.07422#bib.bib23)\]and NodePiece\-QE, have been proposed to incorporate this idea, and they have outperformed*transductive*models\[[9](https://arxiv.org/html/2607.07422#bib.bib22),[10](https://arxiv.org/html/2607.07422#bib.bib20)\]\.

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\[[39](https://arxiv.org/html/2607.07422#bib.bib19)\]\. 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\[[8](https://arxiv.org/html/2607.07422#bib.bib30)\]with the Neural Bellman\-Ford Network \(NBF\-Net\)\[[39](https://arxiv.org/html/2607.07422#bib.bib19)\]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\.

![Refer to caption](https://arxiv.org/html/2607.07422v1/x1.png)Figure 1:Toy example for*inductive*query answering where the test graph \(Gt​e​s​tG\_\{test\}\) contains additional nodes \(represented by blue color\) than the train graph \(Gt​r​a​i​nG\_\{train\}\)\. Dotted circles represent the solution for the query,Q1\-*Name the university from which a French Field medalist graduated*, with FOL asQ=v\.∃u:win\(FieldMedal,u\)∧citizen\(France,u\)∧graduate\(u,v\)Q=v\.\\exists u:win\(FieldMedal,u\)\\wedge citizen\(France,u\)\\wedge graduate\(u,v\)Contribution II: Efficient execution of the message passing\.We extend the GE\-SpMM\[[19](https://arxiv.org/html/2607.07422#bib.bib36)\]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 fromO​\(2​b​\|ℰ\|​d\)O\(2b\|\\mathcal\{E\}\|d\)toO​\(b​\|𝒱\|​d\+\|ℰ\|​d\)O\(b\|\\mathcal\{V\}\|d\+\|\\mathcal\{E\}\|d\)\. Here,bbis the batch size,\|ℰ\|\|\\mathcal\{E\}\|and\|𝒱\|\|\\mathcal\{V\}\|are the triple and node counts, andddis 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\)\[[30](https://arxiv.org/html/2607.07422#bib.bib35)\]dataset\. We also test our model on the Wiki\-KG\[[18](https://arxiv.org/html/2607.07422#bib.bib34)\]dataset, which contains millions of nodes\. The results are supported by an ablation study of InductWave, along with its space and runtime analysis\.

## IIRelated Work

Multi\-Hop Query Answering\.In multi\-hop reasoning, one approach is to traverse a path in a KG to perform link prediction\[[33](https://arxiv.org/html/2607.07422#bib.bib2),[23](https://arxiv.org/html/2607.07422#bib.bib4),[5](https://arxiv.org/html/2607.07422#bib.bib5),[14](https://arxiv.org/html/2607.07422#bib.bib6),[13](https://arxiv.org/html/2607.07422#bib.bib7),[32](https://arxiv.org/html/2607.07422#bib.bib8)\]\. 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\)\[[15](https://arxiv.org/html/2607.07422#bib.bib9)\]and Query2Box\[[26](https://arxiv.org/html/2607.07422#bib.bib10)\]were the first to introduce methods to resolve queries containing disjunction \(∨\\vee\) and conjunction \(∧\\wedge\) operators\. Using the beta distributions for embedding, BetaE\[[27](https://arxiv.org/html/2607.07422#bib.bib11)\]incorporated the negation operator \(¬\\neg\) in the queries\. There are geometric embedding methods, such as ConE\[[37](https://arxiv.org/html/2607.07422#bib.bib33)\]and Query2Geom\[[28](https://arxiv.org/html/2607.07422#bib.bib37)\], which embed queries as geometric shapes in the latent space\. FuzzyQE\[[6](https://arxiv.org/html/2607.07422#bib.bib12)\]provides a fuzzy set of answers between the query traversal\. GNN\-QE\[[38](https://arxiv.org/html/2607.07422#bib.bib23)\]uses NBF\-Net\[[39](https://arxiv.org/html/2607.07422#bib.bib19)\]for the relation projection and fuzzy operators for other FOL operations\. CQD\[[2](https://arxiv.org/html/2607.07422#bib.bib26)\]employs a greedy approach of beam search for FOL operations, and ComplEx\[[31](https://arxiv.org/html/2607.07422#bib.bib32)\]for relational projection\. RConE\[[21](https://arxiv.org/html/2607.07422#bib.bib13)\]and STARQE\[[1](https://arxiv.org/html/2607.07422#bib.bib14)\]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\[[22](https://arxiv.org/html/2607.07422#bib.bib18)\]and\[[25](https://arxiv.org/html/2607.07422#bib.bib16)\], 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\[[38](https://arxiv.org/html/2607.07422#bib.bib23)\], initially proposed for*transductive*reasoning, can also be used for*inductive*query answering\[[9](https://arxiv.org/html/2607.07422#bib.bib22)\]\. 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\[[9](https://arxiv.org/html/2607.07422#bib.bib22),[10](https://arxiv.org/html/2607.07422#bib.bib20)\]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\[[2](https://arxiv.org/html/2607.07422#bib.bib26)\]for FOL operations\.

ULTRA\[[11](https://arxiv.org/html/2607.07422#bib.bib28),[12](https://arxiv.org/html/2607.07422#bib.bib21)\]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\[[8](https://arxiv.org/html/2607.07422#bib.bib30)\]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\[[34](https://arxiv.org/html/2607.07422#bib.bib29)\]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\[[24](https://arxiv.org/html/2607.07422#bib.bib38)\]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\.

## IIIPreliminaries

Inductive Reasoning on KG\.A Knowledge GraphG​\(𝒱,ℰ,ℛ\)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\}\.

ℰ=\{\(es,r,eo\)\|es,eo∈𝒱,r∈ℛ\}\\mathcal\{E\}=\\\{\(e\_\{s\},r,e\_\{o\}\)\|e\_\{s\},e\_\{o\}\\in\\mathcal\{V\},r\\in\\mathcal\{R\}\\\}\(1\)Given\|𝒱\|=N\|\\mathcal\{V\}\|=Nand\|ℛ\|=M\|\\mathcal\{R\}\|=M, we say the query answering is*inductive*if the training KG \(Gt​r​a​i​nG\_\{train\}\) containsα1\\alpha\_\{1\}nodes andβ1\\beta\_\{1\}relations, such that\|α1\|<N\|\\alpha\_\{1\}\|<Nand/or\|β1\|<M\|\\beta\_\{1\}\|<M, i\.e\., the training nodes/relations are a subset ofGG\. The test graph \(Gt​e​s​tG\_\{test\}\) containsα2\\alpha\_\{2\}nodes andβ2\\beta\_\{2\}relations, such thatα2∖α1≠ϕ\\alpha\_\{2\}\\setminus\\alpha\_\{1\}\\neq\\phiand/orβ2∖β1≠ϕ\\beta\_\{2\}\\setminus\\beta\_\{1\}\\neq\\phi\. For our work, we train on all relations \(\|β1\|=M,\|α1\|<N\|\\beta\_\{1\}\|=M,\\;\\;\|\\alpha\_\{1\}\|<N\)\.

Figure[1](https://arxiv.org/html/2607.07422#S1.F1)provides a toy example\. Given a query,Q1\-*Name the university from which a French Field medalist graduated\.*In the training graph \(Gt​r​a​i​nG\_\{train\}\), we get*École Normale Supérieure*as the answer\. While in the test graph \(Gt​e​s​tG\_\{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\) queryQQutilizes 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\[[27](https://arxiv.org/html/2607.07422#bib.bib11)\]\.

The queryQQhas a distinguished target variableV?V\_\{?\}\(answer to the query\), a finite set of existentially quantified bound variablesV1,…,VkV\_\{1\},\\ldots,V\_\{k\}, and a constant entity set𝒱a⊆𝒱\\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?\.∃V1,…,Vk:c1∨c2∨…∨cnQ\[V\_\{?\}\]=V\_\{?\}\.\\exists V\_\{1\},\\dots,V\_\{k\}:c\_\{1\}\\vee c\_\{2\}\\vee\.\.\.\\vee c\_\{n\}\(2\)Each clausecic\_\{i\}is a conjunction of one or more relational binary functions \(positive or negative\)r​\(x,y\)r\(x,y\),r∈ℛr\\in\\mathcal\{R\}, wherexxandyycan be a constant or a variable\. For queryQ1, the FOL would beQ=v\.∃u:win\(FieldMedal,u\)∧citizen\(France,u\)∧graduate\(u,v\)Q=v\.\\exists u:win\(FieldMedal,u\)\\wedge citizen\(France,u\)\\wedge graduate\(u,v\)\.

Fuzzy Set\.A Fuzzy set is a relaxed conventional set, defined asA=\{\(x,μ\)\|x∈U\}A=\\\{\(x,\\mu\)\|x\\in U\\\}\.μ∈\[0,1\]\\mu\\in\[0,1\]is the membership function of elementxxfor the setAA\.UUis 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\[[38](https://arxiv.org/html/2607.07422#bib.bib23)\]\.

## IVInductWave

This section describes the three components of InductWave that handle FOL queries, such asQ1in Figure[1](https://arxiv.org/html/2607.07422#S1.F1)\. The first component,Relation Projection, processes different relations specified in the query\. For example, inQ1, 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\[[38](https://arxiv.org/html/2607.07422#bib.bib23)\]\.

### IV\-ARelation Projection

Given a fuzzy set of head entities𝐟h​e\\mathbf\{f\}\_\{he\}and a query relationqq, the relation projection operation provides a fuzzy set of all the tail entities𝐟t​a\\mathbf\{f\}\_\{ta\}that can be reached from𝐟h​e\\mathbf\{f\}\_\{he\}usingqq\(Equation[3](https://arxiv.org/html/2607.07422#S4.E3)\)\. InQ1, for example, for the relation*win*,𝐟h​e\\mathbf\{f\}\_\{he\}is a one\-hot vector with the probability of Field\-Medal being11\. The relation projection𝒫q​\(𝐟h​e\)\\mathcal\{P\}\_\{q\}\(\\mathbf\{f\}\_\{he\}\)for*win*will produce𝐟t​a\\mathbf\{f\}\_\{ta\}, where the probability of all the individuals who*win*the Fields Medal \(in the graph\) approaching11\.

𝒫q​\(𝐟h​e\):\[0,1\]𝒱↦\[0,1\]𝒱\\mathcal\{P\}\_\{q\}\(\\mathbf\{f\}\_\{he\}\):\[0,1\]^\{\\mathcal\{V\}\}\\mapsto\[0,1\]^\{\\mathcal\{V\}\}\(3\)We present WAVBFNet for computing relation projections\. The approach consists of two components: graph wavelets and NBF\-Net\. First, we introduce theKnowledge Graph Laplacian, which serves as a foundation for constructing graph wavelets\. In the second part, we use the KG Laplacian to developGraph Wavelet Embedding\. Finally, in theWAVBFNetsection, we combine wavelet embeddings with NBF\-Net to create a relation projection function\.

#### IV\-A1Knowledge 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\[[36](https://arxiv.org/html/2607.07422#bib.bib24)\]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\[[36](https://arxiv.org/html/2607.07422#bib.bib24)\]is already defined for directed graphs\. We extend the method and define a KG Laplacian that accounts for both direction and relation\.

Let𝐀r\\mathbf\{A\}^\{r\}be an adjacency matrix containing all the edges for relationrr\(r∈ℛr\\in\\mathcal\{R\}\) of the KG,GXG\_\{X\}\(GX=Gt​r​a​i​n/Gv​a​l​i​d/Gt​e​s​tG\_\{X\}=G\_\{train\}/G\_\{valid\}/G\_\{test\}dataset\)\. Let𝐀sr\\mathbf\{A\}\_\{s\}^\{r\}be the symmetric matrix generated from𝐀r\\mathbf\{A\}^\{r\}, with a degree matrix𝐃sr​\(u,u\)\\mathbf\{D\}^\{r\}\_\{s\}\(u,u\), defined as

𝐀sr​\(u,v\)\\displaystyle\\mathbf\{A\}^\{r\}\_\{s\}\(u,v\)=12​\(𝐀r​\(u,v\)\+𝐀r​\(v,u\)\)\\displaystyle=\\frac\{1\}\{2\}\(\\mathbf\{A\}^\{r\}\(u,v\)\+\\mathbf\{A\}^\{r\}\(v,u\)\)\(4\)𝐃sr​\(u,u\)\\displaystyle\\mathbf\{D\}^\{r\}\_\{s\}\(u,u\)=∑v∈𝒱𝐀sr​\(u,v\)\\displaystyle=\\sum\_\{v\\in\\mathcal\{V\}\}\\mathbf\{A\}\_\{s\}^\{r\}\(u,v\)\(5\)𝐀sr​\(u,v\)\>0\\mathbf\{A\}^\{r\}\_\{s\}\(u,v\)\>0indicates that a relationrrexists between nodeuuandvv\. The direction of this edge is captured by

𝚯r\(g\)​\(u,v\)\\displaystyle\\mathbf\{\\Theta\}\_\{r\}^\{\(g\)\}\(u,v\)=2​π​g​\(𝐀r​\(u,v\)−𝐀r​\(v,u\)\)\\displaystyle=2\\pi g\(\\mathbf\{A\}^\{r\}\(u,v\)\-\\mathbf\{A\}^\{r\}\(v,u\)\)\(6\)whereggis a hyper\-parameter with values in the range\[0,0\.25\]\[0,0\.25\]\. If there is a direct edge𝐀r​\(u,v\)∈ℰ\\mathbf\{A\}^\{r\}\(u,v\)\\in\\mathcal\{E\}, but not the reverse edge𝐀r​\(v,u\)∉ℰ\\mathbf\{A\}^\{r\}\(v,u\)\\notin\\mathcal\{E\}, then𝚯r\(g\)​\(u,v\)\\mathbf\{\\Theta\}\_\{r\}^\{\(g\)\}\(u,v\)will be positive while𝚯r\(g\)​\(v,u\)\\mathbf\{\\Theta\}\_\{r\}^\{\(g\)\}\(v,u\)will be negative\. Conversely, if the relational edge is bi\-directional or does not exist, then𝚯r\(g\)​\(u,v\)=0\\mathbf\{\\Theta\}\_\{r\}^\{\(g\)\}\(u,v\)=0\. We define the original relational adjacency matrix𝐀r\\mathbf\{A\}^\{r\}, using a hermitian matrix as

𝐇r​\(g\)=𝐀sr⊙exp⁡\(ir​𝚯r\(g\)\)\\mathbf\{H\}^\{r\(g\)\}=\\mathbf\{A\}\_\{s\}^\{r\}\\odot\\exp\{\(i\_\{r\}\\mathbf\{\\Theta\}\_\{r\}^\{\(g\)\}\)\}\(7\)here,iri\_\{r\}is the imaginary dimension for relationrr, and⊙\\odotis element\-wise multiplication\.𝐀sr\\mathbf\{A\}\_\{s\}^\{r\}captures edge existence, whileexp⁡\(ir​𝚯r\(g\)\)\\exp\{\(i\_\{r\}\\mathbf\{\\Theta\}\_\{r\}^\{\(g\)\}\)\}accounts for the direction\. Inspired by\[[36](https://arxiv.org/html/2607.07422#bib.bib24)\], we propose the unnormalized Laplacian for relationrras

𝐋u​nr​\(g\)=𝐃sr−𝐇r​\(g\)=𝐃sr−𝐀sr⊙exp⁡\(ir​𝚯r\(g\)\)\\displaystyle\\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\)\}\)\}\(8\)We define KG Laplacian as a set of these relational Laplacians,𝐋u​n\(g\)=\{𝐋u​nr​\(g\)\|r∈ℛ\}\\mathbf\{L\}\_\{un\}^\{\(g\)\}=\\\{\\mathbf\{L\}\_\{un\}^\{r\(g\)\}\|r\\in\\mathcal\{R\}\\\}\. The proof of𝐋u​nr​\(g\)\\mathbf\{L\}\_\{un\}^\{r\(g\)\}being positive semi\-definite can be found in the Supplementary Material\.

In Equation[8](https://arxiv.org/html/2607.07422#S4.E8), thert​hr^\{th\}Laplacian contains information about that specific relationrr\. However, there is no information exchange between two distinct relational Laplacians𝐋u​nr​\(g\)\\mathbf\{L\}\_\{un\}^\{r\(g\)\},𝐋u​ns​\(g\)\\mathbf\{L\}\_\{un\}^\{s\(g\)\}\(r,s∈ℛ,r≠sr,s\\in\\mathcal\{R\},r\\neq 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,GXG\_\{X\}, rather than just based on relationrr\. The normalized magnet Laplacian for relationrris defined as

𝐋nr​\(g\)\\displaystyle\\mathbf\{L\}\_\{n\}^\{r\(g\)\}=𝐃z−1/2​𝐋u​nr​\(g\)​𝐃z−1/2\\displaystyle=\\mathbf\{D\}\_\{z\}^\{\-1/2\}\\mathbf\{L\}\_\{un\}^\{r\(g\)\}\\mathbf\{D\}\_\{z\}^\{\-1/2\}=𝐃z−1/2​\(𝐃sr−𝐀sr⊙e​x​p​\(ir​𝚯r\(g\)\)\)​𝐃z−1/2\\displaystyle=\\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\}\(9\)where𝐃z\\mathbf\{D\}\_\{z\}is the sum of all degree matrices𝐃sr\\mathbf\{D\}^\{r\}\_\{s\},∀r∈ℛ\\forall r\\in\\mathcal\{R\}, defined as

𝐃z​\(u,u\)=∑r∈ℛ∑v∈𝒱𝐀sr​\(u,v\)\\mathbf\{D\}\_\{z\}\(u,u\)=\\sum\_\{r\\in\\mathcal\{R\}\}\\sum\_\{v\\in\\mathcal\{V\}\}\\mathbf\{A\}^\{r\}\_\{s\}\(u,v\)\(10\)We use this normalized KG Laplacian \(Equation[9](https://arxiv.org/html/2607.07422#S4.E9)\) to generate graph wavelet embedding, which is subsequently used in WAVBFNet for relation projection\.

#### IV\-A2Graph Wavelet Embedding

In this section, we generate graph wavelet embeddings for WAVBFNet using the KG Laplacian \(Equation[9](https://arxiv.org/html/2607.07422#S4.E9)\)\. GraphWave\[[8](https://arxiv.org/html/2607.07422#bib.bib30)\]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[9](https://arxiv.org/html/2607.07422#S4.E9)\) 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 relationrris expressed as𝐋nr=𝐔r​Λr​𝐔r⁣†\\mathbf\{L\}\_\{n\}^\{r\}=\\mathbf\{U\}^\{r\}\\Lambda^\{r\}\\mathbf\{U\}^\{r\\dagger\}\(omittedggfrom𝐋nr​\(g\)\\mathbf\{L\}\_\{n\}^\{r\(g\)\}for simplicity\)\. Here,𝐔r\\mathbf\{U\}^\{r\}consists of eigenvectors \(𝐔r⁣†\\mathbf\{U\}^\{r\\dagger\}is the conjugate transpose of𝐔r\\mathbf\{U\}^\{r\}\), and𝚲r=D​i​a​g​\{λ1,…​λn\}\\mathbf\{\\Lambda\}^\{r\}=Diag\\\{\\lambda\_\{1\},\.\.\.\\lambda\_\{n\}\\\}is the diagonal matrix containing ordered eigenvalues\.

Let𝔤s\\mathfrak\{g\}\_\{s\}be a low\-pass heat filter,𝔤s​\(λ\)=e−λ​s\\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 relationrris defined as

𝚿r\\displaystyle\\mathbf\{\\Psi\}^\{r\}=𝐔r​𝔤s​\(𝚲r\)​𝐔r⁣†\\displaystyle=\\mathbf\{U\}^\{r\}\\mathfrak\{g\}\_\{s\}\(\\mathbf\{\\Lambda\}^\{r\}\)\\mathbf\{U\}^\{r\\dagger\}\(11\)The low\-pass filter \(𝔤s\\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𝚿r\\mathbf\{\\Psi\}^\{r\}\(Equation[11](https://arxiv.org/html/2607.07422#S4.E11)\) is an expensive operation\. Hence, to simplify this process, we use the Chebyshev polynomial approximation\[[29](https://arxiv.org/html/2607.07422#bib.bib31)\]\.

The graph wavelet embedding is obtained by sampling from the characteristic function of𝚿r\\mathbf\{\\Psi\}^\{r\}\. This embedding is used to measure the expected amount of information a nodeuureceives from all other nodes, in relationrr\. The characteristic function for nodeuuis defined as

ϕur​\(tj,tk\)\\displaystyle\\phi^\{r\}\_\{u\}\(t\_\{j\},t\_\{k\}\)=E​\[ei​\(tj​𝚿ur​\(r​e\)\+tk​𝚿ur​\(i​m\)\)\]\\displaystyle=E\[e^\{i\(t\_\{j\}\\mathbf\{\\Psi\}^\{r\}\_\{u\}\(re\)\+t\_\{k\}\\mathbf\{\\Psi\}^\{r\}\_\{u\}\(im\)\)\}\]=1\|𝒱\|​∑v∈𝒱ei​\(tj​𝚿v​ur​\(r​e\)\+tk​𝚿v​ur​\(i​m\)\)\\displaystyle=\\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\)\)\}\(12\)where𝚿ur​\(r​e\)\\mathbf\{\\Psi\}^\{r\}\_\{u\}\(re\)and𝚿ur​\(i​m\)\\mathbf\{\\Psi\}^\{r\}\_\{u\}\(im\)represent the real and imaginary parts of𝚿ur\\mathbf\{\\Psi\}^\{r\}\_\{u\}\.tj,tk∈ℝt\_\{j\},t\_\{k\}\\in\\mathbb\{R\}are the uniform random samples taken from the joint distribution\. The graph wavelet embeddings withd/2d/2samples is defined as

χur=\[R​e​\(ϕur​\(tj,tk\)\),I​m​\(ϕur​\(tj,tk\)\)\]\(t1​j,t1​k\),…,\(t\(d/2\)​j,t\(d/2\)​k\)\\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\}\)\}\(13\)The resulting graph wavelet embeddings,χur\\mathbf\{\\chi\}^\{r\}\_\{u\}, will bedd\-dimensional, withd/2d/2real andd/2d/2imaginary components\. We use this wavelet embedding \(Equation[13](https://arxiv.org/html/2607.07422#S4.E13)\) for the WAVBFNet in the following section\.

#### IV\-A3WAVBFNet

The relation projection method, WAVBFNet, is constructed using two components: the graph wavelet embeddings and the Neural Bellman Ford Network \(NBF\-Net\)\[[39](https://arxiv.org/html/2607.07422#bib.bib19)\]\.

GNN\-QE\[[38](https://arxiv.org/html/2607.07422#bib.bib23)\]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](https://arxiv.org/html/2607.07422#S4.E13)\) 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](https://arxiv.org/html/2607.07422#S4.E14)\)\.

𝐡v\(0\)←xv​𝐪\\mathbf\{h\}^\{\(0\)\}\_\{v\}\\leftarrow x\_\{v\}\\mathbf\{q\}\(14\)here,xvx\_\{v\}is the probability of nodevvin𝐟h​e\\mathbf\{f\}\_\{he\}\(fuzzy set of head nodes\)\. Since we are working with complex wavelet embedding, we split the vector \(Equation[14](https://arxiv.org/html/2607.07422#S4.E14)\) into real and imaginary parts and handle them separately\.𝐡vr​e\(0\)=𝐡v\[:i/2\]\(0\)\\mathbf\{h\}^\{\(0\)\}\_\{v\_\{re\}\}=\\mathbf\{h\}^\{\(0\)\}\_\{v\_\{\[:i/2\]\}\}being the real vector and𝐡vi​m\(0\)=𝐡v\[\(i/2\)\+1:\]\(0\)\\mathbf\{h\}^\{\(0\)\}\_\{v\_\{im\}\}=\\mathbf\{h\}^\{\(0\)\}\_\{v\_\{\[\(i/2\)\+1:\]\}\}the imaginary part\.

In the message passing method, we define theM​E​S​S​A​G​EMESSAGEfor a nodevvas a function of its neighbor’s embedding \(𝐡x\(t−1\)\\mathbf\{h\}^\{\(t\-1\)\}\_\{x\}\), the relation embedding \(wq​\(x,r,v\)\|\(x,r,v\)∈ℰw\_\{q\}\(x,r,v\)\\;\|\\;\(x,r,v\)\\in\\mathcal\{E\}\), and the wavelet embeddings of the neighbor \(χxr\\mathbf\{\\chi\}^\{r\}\_\{x\}from Equation[13](https://arxiv.org/html/2607.07422#S4.E13)\)\. The function for the real part is defined as

M​E​S\\displaystyle MESS​A​G​E​\(𝐡xr​e\(t−1\),wqr​e​\(x,r,v\),χxr​er\)\\displaystyle SAGE\(\\mathbf\{h\}^\{\(t\-1\)\}\_\{x\_\{re\}\},w\_\{q\_\{re\}\}\(x,r,v\),\\mathbf\{\\chi\}^\{r\}\_\{x\_\{re\}\}\)=𝐡xr​e\(t−1\)⊙\(𝐖r​𝐪\+𝐛r\)r​e⊙\(𝐰𝟏\+𝐰𝟐​χxr​er\)\\displaystyle=\\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\}\}\)\(15\)The term\(𝐖r​𝐪\+𝐛r\)r​e\(\\mathbf\{W\}\_\{r\}\\mathbf\{q\}\+\\mathbf\{b\}\_\{r\}\)\_\{re\}indicates that the relation embedding is dependent on the query relationqq\. The product of the first two terms in Equation[IV\-A3](https://arxiv.org/html/2607.07422#S4.Ex3)is analogous to the link prediction method DistMult\[[35](https://arxiv.org/html/2607.07422#bib.bib42)\]\. The expression\(𝐰1\+𝐰2​χxr​er\)\(\\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 \(χxr​er\\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\[[31](https://arxiv.org/html/2607.07422#bib.bib32)\]and TransE\[[4](https://arxiv.org/html/2607.07422#bib.bib40)\], but DistMult performed the best among the three\. The message passing for the WAVBFNet \(Figure[2](https://arxiv.org/html/2607.07422#S4.F2)\) is described as

𝐡vr​e\(t\)←\\displaystyle\\mathbf\{h\}^\{\(t\)\}\_\{v\_\{re\}\}\\leftarrowAGG\(\{MESSAGE\(𝐡xr​e\(t−1\),wqr​e\(x,r,v\),χxr​er\)∣\\displaystyle AGG\(\\\{MESSAGE\(\\mathbf\{h\}^\{\(t\-1\)\}\_\{x\_\{re\}\},w\_\{q\_\{re\}\}\(x,r,v\),\\mathbf\{\\chi\}^\{r\}\_\{x\_\{re\}\}\)\\mid\(x,r,v\)∈ℰ\(v\)\}∪\{𝐡vr​e\(0\)\}\)\\displaystyle\(x,r,v\)\\in\\mathcal\{E\}\(v\)\\\}\\cup\\\{\\mathbf\{h\}^\{\(0\)\}\_\{v\_\{re\}\}\\\}\)\(16\)𝐡vi​m\(t\)←\\displaystyle\\mathbf\{h\}^\{\(t\)\}\_\{v\_\{im\}\}\\leftarrowAGG\(\{MESSAGE\(𝐡xi​m\(t−1\),wqi​m\(x,r,v\),χxi​mr\)∣\\displaystyle AGG\(\\\{MESSAGE\(\\mathbf\{h\}^\{\(t\-1\)\}\_\{x\_\{im\}\},w\_\{q\_\{im\}\}\(x,r,v\),\\mathbf\{\\chi\}^\{r\}\_\{x\_\{im\}\}\)\\mid\(x,r,v\)∈ℰ\(v\)\}∪\{𝐡vi​m\(0\)\}\)\\displaystyle\(x,r,v\)\\in\\mathcal\{E\}\(v\)\\\}\\cup\\\{\\mathbf\{h\}^\{\(0\)\}\_\{v\_\{im\}\}\\\}\)\(17\)𝐡v\(t\)←\\displaystyle\\mathbf\{h\}^\{\(t\)\}\_\{v\}\\leftarrowC​O​N​C​A​T​\(𝐡vr​e\(t\),𝐡vi​m\(t\)\)\\displaystyle CONCAT\(\\mathbf\{h\}^\{\(t\)\}\_\{v\_\{re\}\},\\mathbf\{h\}^\{\(t\)\}\_\{v\_\{im\}\}\)\(18\)Note, we have concatenated the real and imaginary embeddings \(𝐡vr​e\(t\)\\mathbf\{h\}^\{\(t\)\}\_\{v\_\{re\}\}and𝐡vi​m\(t\)\\mathbf\{h\}^\{\(t\)\}\_\{v\_\{im\}\}\) at the end\. We use PNA \(Principal Neighborhood Aggregator\)\[[7](https://arxiv.org/html/2607.07422#bib.bib41)\]as the aggregator function \(A​G​GAGG\), unless specified otherwise\.

![Refer to caption](https://arxiv.org/html/2607.07422v1/x2.png)

Figure 2:WAVBFNet message passing\. Here⊙\\odotis element\-wise multiplication,⊕\\oplusis element\-wise addition,w1w\_\{1\}andw2w\_\{2\}are parameters\. The shadow under each vector and operator represents the real and imaginary parts working in parallel\.After the message passing phase, the embedding is fed into a two\-layer feed\-forward network to obtain the fuzzy set of tail nodes \(𝐟t​a\\mathbf\{f\}\_\{ta\}\)\. Thus, the relation projection described in the Equation[3](https://arxiv.org/html/2607.07422#S4.E3)can be expressed as the following function

𝒫q\(𝐟h​e\)=σ\(FF\(𝐡\(T\)\)\\mathcal\{P\}\_\{q\}\(\\mathbf\{f\}\_\{he\}\)=\\sigma\(FF\(\\mathbf\{h\}^\{\(T\)\}\)\(19\)whereσ\\sigmais the sigmoid activation function that maps all values to the range\[0,1\]\[0,1\]\.

### IV\-BFuzzy Operations

We employ fuzzy set operations to implement the other FOL operators, following a similar approach to\[[38](https://arxiv.org/html/2607.07422#bib.bib23)\]\. 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𝐲𝟏,𝐲𝟐∈\[0,1\]𝒱\\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\.

𝒞​\(𝐲𝟏,𝐲𝟐\)\\displaystyle\\mathcal\{C\}\(\\mathbf\{y\_\{1\}\},\\mathbf\{y\_\{2\}\}\)=𝐲𝟏⊙𝐲𝟐\\displaystyle=\\mathbf\{y\_\{1\}\}\\odot\\mathbf\{y\_\{2\}\}\(20\)𝒟​\(𝐲𝟏,𝐲𝟐\)\\displaystyle\\mathcal\{D\}\(\\mathbf\{y\_\{1\}\},\\mathbf\{y\_\{2\}\}\)=𝐲𝟏\+𝐲𝟐−𝐲𝟏⊙𝐲𝟐\\displaystyle=\\mathbf\{y\_\{1\}\}\+\\mathbf\{y\_\{2\}\}\-\\mathbf\{y\_\{1\}\}\\odot\\mathbf\{y\_\{2\}\}\(21\)𝒩​\(𝐲𝟏\)\\displaystyle\\mathcal\{N\}\(\\mathbf\{y\_\{1\}\}\)=𝟏−𝐲𝟏\\displaystyle=\\mathbf\{1\}\-\\mathbf\{y\_\{1\}\}\(22\)where⊙\\odotis the element\-wise multiplication and𝟏\\mathbf\{1\}is a vector of all ones\.

### IV\-CTraining Method

Traversal Dropout\.Direct query\-relation edges originating from the source nodes are randomly removed from the training graph with a probability ofpp\[[38](https://arxiv.org/html/2607.07422#bib.bib23)\]\. 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

L=\\displaystyle L=−1\|𝒜Q\|​∑u∈𝒜Ql​o​g​p​\(u\|Q\)\\displaystyle\-\\frac\{1\}\{\|\\mathcal\{A\}\_\{Q\}\|\}\\sum\_\{u\\in\\mathcal\{A\}\_\{Q\}\}log\\;p\(u\|Q\)−1\|𝒱∖𝒜Q\|​∑u′∈𝒱∖𝒜Ql​o​g​\(1−p​\(u′\|Q\)\)\\displaystyle\-\\frac\{1\}\{\|\\mathcal\{V\}\\setminus\\mathcal\{A\}\_\{Q\}\|\}\\sum\_\{u^\{\\prime\}\\in\\mathcal\{V\}\\setminus\\mathcal\{A\}\_\{Q\}\}log\\;\(1\-p\(u^\{\\prime\}\|Q\)\)\(23\)here,𝒜Q\\mathcal\{A\}\_\{Q\}is the set of all the answers to the complex queryQQ, andl​o​g​p​\(u\|Q\)log\\;p\(u\|Q\)denotes the probability of the answeruu, if queryQQis passed through InductWave\.

## VExperiments

### V\-AExperimental Setup

Datasets and Evaluation Metric\.We use FB15k\-\(237\)\[[30](https://arxiv.org/html/2607.07422#bib.bib35)\]and Wiki\-KG\[[18](https://arxiv.org/html/2607.07422#bib.bib34)\]datasets in our study\. The FB15k\-\(237\) dataset is derived from Freebase\[[3](https://arxiv.org/html/2607.07422#bib.bib44)\]\. It contains 237 relations and improves on the previous version by removing easy inverse relation leakage\[[4](https://arxiv.org/html/2607.07422#bib.bib40)\]\. 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 over2\.5​M2\.5Mnodes 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\.

![Refer to caption](https://arxiv.org/html/2607.07422v1/x3.png)Figure 3:Standard query structures used to generate First Order Logical \(FOL\) queries\. Here,ppis relation projection,iiis intersection,nnis negation, anduuis union operator\.Baselines\.We use GNN\-QE\[[9](https://arxiv.org/html/2607.07422#bib.bib22),[38](https://arxiv.org/html/2607.07422#bib.bib23)\]and NodePiece\-QE\[[9](https://arxiv.org/html/2607.07422#bib.bib22),[10](https://arxiv.org/html/2607.07422#bib.bib20)\]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\[[2](https://arxiv.org/html/2607.07422#bib.bib26)\]\. 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\[[9](https://arxiv.org/html/2607.07422#bib.bib22)\]\. We use a heuristic method\[[9](https://arxiv.org/html/2607.07422#bib.bib22)\]as a baseline to evaluate the performance of simpler models in inductive settings\.

We exclude ULTRA\[[11](https://arxiv.org/html/2607.07422#bib.bib28),[12](https://arxiv.org/html/2607.07422#bib.bib21)\]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:𝒱t​r​a​i​n\\mathcal\{V\}\_\{train\},𝒱v​a​l​i​d\\mathcal\{V\}\_\{valid\}, and𝒱t​e​s​t\\mathcal\{V\}\_\{test\}\. We create the training graph with𝒱t​r​a​i​n=τ∗𝒱\\mathcal\{V\}\_\{train\}=\\tau\*\\mathcal\{V\}nodes, whereτ=0\.4\\tau=0\.4\. This setup, including the value ofτ\\tau, is based on\[[9](https://arxiv.org/html/2607.07422#bib.bib22)\]\. The remaining nodes,\(1−τ\)∗𝒱\(1\-\\tau\)\*\\mathcal\{V\}, are split equally between𝒱v​a​l​i​d\\mathcal\{V\}\_\{valid\}and𝒱t​e​s​t\\mathcal\{V\}\_\{test\}\. The inference graphs for valid and test cases are constructed from𝒱i​n​f=𝒱v​a​l​i​d/t​e​s​t∪𝒱t​r​a​i​n\\mathcal\{V\}^\{inf\}=\\mathcal\{V\}\_\{valid/test\}\\cup\\mathcal\{V\}\_\{train\}, with the inference ratio𝒱i​n​f/𝒱t​r​a​i​n=175%\\mathcal\{V\}^\{inf\}/\\mathcal\{V\}\_\{train\}=175\\%\. This dataset is intended for testing in the same environment, where GNN\-QE was evaluated in\[[9](https://arxiv.org/html/2607.07422#bib.bib22)\]\.

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𝒱t​r​a​i​n\\mathcal\{V\}\_\{train\}\. We generate a train graph from a subset𝒱t​r​a​i​n0\\mathcal\{V\}\_\{train\_\{0\}\}\(𝒱t​r​a​i​n0⊊𝒱t​r​a​i​n\\mathcal\{V\}\_\{train\_\{0\}\}\\subsetneq\\mathcal\{V\}\_\{train\}\) consisting ofllnodes, selected randomly\. Additionally, we createkkrandom context graphs, each withllnodes, drawn from𝒱t​r​a​i​n\\mathcal\{V\}\_\{train\}, resulting in entity sets𝒱c​t​x​tk=\{𝒱c​t​x​t1,𝒱c​t​x​t2,…,𝒱c​t​x​tk\}\\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𝒱v​a​l​i​d/t​e​s​ti​n​f0=𝒱v​a​l​i​d/t​e​s​t∪𝒱t​r​a​i​n0\\mathcal\{V\}^\{inf\_\{0\}\}\_\{valid/test\}=\\mathcal\{V\}\_\{valid/test\}\\cup\\mathcal\{V\}\_\{train\_\{0\}\}, respectively\. We sample multiple sizes for𝒱t​r​a​i​n\\mathcal\{V\}\_\{train\}by varyingτ∈\{0\.2,0\.3,…,0\.9\}\\tau\\in\\\{0\.2,0\.3,\\allowbreak\\ldots,0\.9\\\}in𝒱t​r​a​i​n=τ∗𝒱\\mathcal\{V\}\_\{train\}=\\tau\*\\mathcal\{V\}\. This results in a diverse range of graphs with the ratio𝒱i​n​f/𝒱t​r​a​i​n\\mathcal\{V\}^\{inf\}/\\mathcal\{V\}\_\{train\}ranging from106%106\\%to300%300\\%\. Note that we omittedτ=0\.1\\tau=0\.1because the query generation module\[[27](https://arxiv.org/html/2607.07422#bib.bib11)\]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 approximately2\.52\.5million nodes and more than1616million triples\. It has512512unique relations\. Similar to FB15k\-\(237\), we create a training set that contains1\.51\.5million nodes\. From this set, we randomly generate a training graph andkkcontext graphs, each of sizell\. Both the valid and test sets include an additional500​k500knodes, containing55million known and600​k600kmissing edges\.

Query Generation\.Queries are generated using the query generation module described in\[[27](https://arxiv.org/html/2607.07422#bib.bib11)\]\. We utilize 14 different query structures, including*1p*,*2p*,*3p*,*2i*,*3i*,*pi*,*ip*,*2u*,*up*,*pni*,*pin*,*inp*,*2in*, and*3in*, whereppis relation projection,iiis intersection,nnis negation, anduuis union \(Figure[3](https://arxiv.org/html/2607.07422#S5.F3)\)\. Detailed statistics on the number of queries generated are available in the Supplementary Material\.

Hyper\-Parameters\.

TABLE I:Hyperparameters of InductWave on different datasets\.In earlier models\[[26](https://arxiv.org/html/2607.07422#bib.bib10),[27](https://arxiv.org/html/2607.07422#bib.bib11)\], 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,\[[38](https://arxiv.org/html/2607.07422#bib.bib23)\]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 setl=0\.5∗\|𝒱t​r​a​i​n\|l=0\.5\*\|\\mathcal\{V\}\_\{train\}\|\(0\.5 is used ensure less memory footprint\), and generate two context graphs \(k=2k=2\), for all ratios except106%106\\%\. We do the same for Wiki\-KG\. In the case𝒱i​n​f/𝒱t​r​a​i​n=106%\\mathcal\{V\}^\{inf\}/\\mathcal\{V\}\_\{train\}=106\\%, we takek=0k=0\. We train InductWave with𝒱t​r​a​i​n0\\mathcal\{V\}\_\{train\_\{0\}\}andkkcontext graphs in rotation among epochs\. The baseline models were trained on𝒱t​r​a​i​n0\\mathcal\{V\}\_\{train\_\{0\}\}\. The rationale behind generatingkkcontext 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\|𝒱t​r​a​i​n\|\|\\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𝒱t​r​a​i​n\\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\[[9](https://arxiv.org/html/2607.07422#bib.bib22)\]\. 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\[[9](https://arxiv.org/html/2607.07422#bib.bib22)\], 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\]=\[0\.1,1,10,50\],g=\[0\.1,0\.15,0\.2,0\.25\]g=\[0\.1,0\.15,0\.2,0\.25\], andt1,t2=\[2,3,4,5,10\]t\_\{1\},t\_\{2\}=\[2,3,4,5,10\]\. We used the chebyshev approximation parameter consistent with the original work\[[8](https://arxiv.org/html/2607.07422#bib.bib30)\]\. 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\]\[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](https://arxiv.org/html/2607.07422#S5.T1)presents the hyperparameters for InductWave\.

### V\-BResult Analysis

TABLE II:HITS@10 \(%\) score for*inductive*query answering, where all the nodes in𝒱t​r​a​i​n\\mathcal\{V\}\_\{train\}are used in a single training graph,𝒱i​n​f/𝒱t​r​a​i​n=175%\\mathcal\{V\}^\{inf\}/\\mathcal\{V\}\_\{train\}=175\\%\. avgpis the average of positive queries, and avg is the average of all the queries\.TABLE III:HITS@10 \(%\) score for*inductive*query answering for𝒱i​n​f/𝒱t​r​a​i​n=175%\\mathcal\{V\}^\{inf\}/\\mathcal\{V\}\_\{train\}=175\\%\. avgpis the average of positive queries, and avg is the average of all the queries\.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𝒱t​r​a​i​n\\mathcal\{V\}\_\{train\}, without any context graphs, with a ratio of𝒱i​n​f/𝒱t​r​a​i​n=175%\\mathcal\{V\}^\{inf\}/\\mathcal\{V\}\_\{train\}=175\\%\. The HITS@10 results for this configuration are in Table[II](https://arxiv.org/html/2607.07422#S5.T2)\. 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\.

Since InductWave performs better in the previous scenario\. We conduct additional experiments by generating small training graphs of sizell, 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[III](https://arxiv.org/html/2607.07422#S5.T3)presents the HITS@10 scores on FB15k\-\(237\), where𝒱i​n​f/𝒱t​r​a​i​n=175%\\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[II](https://arxiv.org/html/2607.07422#S5.T2)\.

TABLE IV:HITS@10 \(%\) score for*inductive*query answering for all𝒱i​n​f/𝒱t​r​a​i​n\\mathcal\{V\}^\{inf\}/\\mathcal\{V\}\_\{train\}ratios\. avgpis the average of positive queries, and avg is the average of all the queries\.TABLE V:HITS@3 \(%\) score for*inductive*query answering for all𝒱i​n​f/𝒱t​r​a​i​n\\mathcal\{V\}^\{inf\}/\\mathcal\{V\}\_\{train\}ratios\. avgpis the average of positive queries, and avg is the average of all the queries\.Table[IV](https://arxiv.org/html/2607.07422#S5.T4)presents HITS@10 results for all the𝒱i​n​f/𝒱t​r​a​i​n\\mathcal\{V\}^\{inf\}/\\mathcal\{V\}\_\{train\}ratios\. Starting from the middle of the table, for the ratio150%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 as175%175\\%,217%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 the300%300\\%ratio\.

Conversely, as we move to lower ratios,133%133\\%,121%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\) in121%121\\%\. NodePiece\-QE with GNN outperforms all for the positive queries in106%106\\%\.

Table[V](https://arxiv.org/html/2607.07422#S5.T5)consists HITS@3 score for all the𝒱i​n​f/𝒱t​r​a​i​n\\mathcal\{V\}^\{inf\}/\\mathcal\{V\}\_\{train\}ratios\. The results indicate similar trends as HITS@10 scores in Table[IV](https://arxiv.org/html/2607.07422#S5.T4)\.

All these results, in Table[IV](https://arxiv.org/html/2607.07422#S5.T4)and[V](https://arxiv.org/html/2607.07422#S5.T5), indicate that InductWave performs better as the ratio𝒱i​n​f/𝒱t​r​a​i​n\\mathcal\{V\}^\{inf\}/\\mathcal\{V\}\_\{train\}increases \(\|α1\|≪\|α2\|\|\\alpha\_\{1\}\|\\ll\|\\alpha\_\{2\}\|, Section[III](https://arxiv.org/html/2607.07422#S3)\)\. 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%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\.

TABLE VI:HITS@100 \(%\) score for*inductive*query answering for WikiKG dataset\. avgpis the average of the positive queries\.TABLE VII:HITS@10 \(%\) score for ablation study on*inductive*query answering for𝒱i​n​f/𝒱t​r​a​i​n=175%\\mathcal\{V\}^\{inf\}/\\mathcal\{V\}\_\{train\}=175\\%\. avgpis the average of positive queries, and avg is the average of all the queries\. Here \(w/o lc\) is without linear combination, and \(w cplx\) is with ComplEx link prediction algorithm\.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](https://arxiv.org/html/2607.07422#S5.T6)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\[[9](https://arxiv.org/html/2607.07422#bib.bib22)\]\. InductWave outperforms all baseline models across all query types\.

### V\-CComplexity Analysis

GE\-SpMM\.GE\-SpMM\[[19](https://arxiv.org/html/2607.07422#bib.bib36)\]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 fromO​\(b​\|ℰ\|​d\)O\(b\|\\mathcal\{E\}\|d\)toO​\(b​\|𝒱\|​d\)O\(b\|\\mathcal\{V\}\|d\)\. Here,bbis the batch size,\|ℰ\|\|\\mathcal\{E\}\|and\|𝒱\|\|\\mathcal\{V\}\|are the number of triples and nodes respectively, andddis 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[IV\-A3](https://arxiv.org/html/2607.07422#S4.Ex4)and[IV\-A3](https://arxiv.org/html/2607.07422#S4.Ex5), improving the combined space complexity fromO​\(2​b​\|ℰ\|​d\)O\(2b\|\\mathcal\{E\}\|d\)toO​\(b​\|𝒱\|​d\+\|ℰ\|​d\)O\(b\|\\mathcal\{V\}\|d\+\|\\mathcal\{E\}\|d\)\. In this enhanced version,\|ℰ\|​d\|\\mathcal\{E\}\|dspace is shared across the batch, since the wavelet embeddings remain the same\.

NBF\-Net contains four message passing layers\. Though, WAVBFNet requires an additionalO​\(\|ℰ\|​d\)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χur\\mathbf\{\\chi\}^\{r\}\_\{u\}for the triples present in the KG \(Equation[IV\-A3](https://arxiv.org/html/2607.07422#S4.Ex3)\)\. 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 of4×3×d4\\times 3\\times dfor each node\. Subsequently, this embedding is reduced todddimensions using a feed\-forward layer through matrix multiplication\. This includes matrices of dimensionsN×12​dN\\times 12dand12​d×d12d\\times d\.

WAVBFNet has separate real and imaginary messages\. This leads to matrix multiplications with dimensionsN×12​\(d/2\)N\\times 12\(d/2\)and12​\(d/2\)×\(d/2\)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\.

### V\-DAblation 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[IV\-A3](https://arxiv.org/html/2607.07422#S4.Ex3)is modified to the following relation\.

M​E​S\\displaystyle MESS​A​G​E​\(hxr​e\(t−1\),wqr​e​\(x,r,v\),χxr​er\)\\displaystyle SAGE\(h^\{\(t\-1\)\}\_\{x\_\{re\}\},w\_\{q\_\{re\}\}\(x,r,v\),\\chi^\{r\}\_\{x\_\{re\}\}\)=hxr​e\(t−1\)⊙\(Wr​q\+br\)r​e⊙χxr​er\\displaystyle=h^\{\(t\-1\)\}\_\{x\_\{re\}\}\\odot\(W\_\{r\}q\+b\_\{r\}\)\_\{re\}\\odot\\chi^\{r\}\_\{x\_\{re\}\}\(24\)
In the second configuration, we replaced the DistMult link prediction method in \(Equation[IV\-A3](https://arxiv.org/html/2607.07422#S4.Ex3)\) with the ComplEx\[[31](https://arxiv.org/html/2607.07422#bib.bib32)\]link prediction method\. Since graph wavelet embeddings are complex, this was intended to test our model in a complex\-plane environment\.

Table[VII](https://arxiv.org/html/2607.07422#S5.T7)presents results for InductWave \(3 layers\)without linear combination\(w/o lc\) andwith ComplEx\(w cplx\)\. The results consists of HITS@10 scores for𝒱i​n​f/𝒱t​r​a​i​n=175%\\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\.

### V\-ESpace and Run\-Time Usage

All the following details are for175%175\\%ratio of FB15k\-\(237\), where all the nodes in𝒱t​r​a​i​n\\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\.

## VIConclusion

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

ChatGPT and Gemini were used for basic text and code editing\.

## References

- \[1\]\(2021\)Query embedding on hyper\-relational knowledge graphs\.arXiv preprint arXiv:2106\.08166\.Cited by:[§II](https://arxiv.org/html/2607.07422#S2.p2.3)\.
- \[2\]E\. Arakelyan, D\. Daza, P\. Minervini, and M\. Cochez\(2020\)Complex query answering with neural link predictors\.arXiv preprint arXiv:2011\.03459\.Cited by:[§II](https://arxiv.org/html/2607.07422#S2.p2.3),[§II](https://arxiv.org/html/2607.07422#S2.p4.1),[§V\-A](https://arxiv.org/html/2607.07422#S5.SS1.p2.1)\.
- \[3\]K\. Bollacker, C\. Evans, P\. Paritosh, T\. Sturge, and J\. Taylor\(2008\)Freebase: a collaboratively created graph database for structuring human knowledge\.InProceedings of the 2008 ACM SIGMOD international conference on Management of data,pp\. 1247–1250\.Cited by:[§V\-A](https://arxiv.org/html/2607.07422#S5.SS1.p1.1)\.
- \[4\]A\. Bordes, N\. Usunier, A\. Garcia\-Duran, J\. Weston, and O\. Yakhnenko\(2013\)Translating embeddings for modeling multi\-relational data\.Advances in neural information processing systems26\.Cited by:[§IV\-A3](https://arxiv.org/html/2607.07422#S4.SS1.SSS3.p5.9),[§V\-A](https://arxiv.org/html/2607.07422#S5.SS1.p1.1)\.
- \[5\]X\. Chen, M\. Chen, W\. Shi, Y\. Sun, and C\. Zaniolo\(2019\)Embedding uncertain knowledge graphs\.InProceedings of the AAAI conference on artificial intelligence,Vol\.33,pp\. 3363–3370\.Cited by:[§II](https://arxiv.org/html/2607.07422#S2.p1.1)\.
- \[6\]X\. Chen, Z\. Hu, and Y\. Sun\(2022\)Fuzzy logic based logical query answering on knowledge graphs\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.36,pp\. 3939–3948\.Cited by:[§II](https://arxiv.org/html/2607.07422#S2.p2.3)\.
- \[7\]G\. Corso, L\. Cavalleri, D\. Beaini, P\. Liò, and P\. Veličković\(2020\)Principal neighbourhood aggregation for graph nets\.Advances in neural information processing systems33,pp\. 13260–13271\.Cited by:[§IV\-A3](https://arxiv.org/html/2607.07422#S4.SS1.SSS3.p5.12),[TABLE I](https://arxiv.org/html/2607.07422#S5.T1.2.2.2.2.8.6.3)\.
- \[8\]C\. Donnat, M\. Zitnik, D\. Hallac, and J\. Leskovec\(2018\)Learning structural node embeddings via diffusion wavelets\.InProceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining,pp\. 1320–1329\.Cited by:[§I](https://arxiv.org/html/2607.07422#S1.p8.1),[§II](https://arxiv.org/html/2607.07422#S2.p6.1),[§IV\-A2](https://arxiv.org/html/2607.07422#S4.SS1.SSS2.p1.1),[§V\-A](https://arxiv.org/html/2607.07422#S5.SS1.p13.4)\.
- \[9\]M\. Galkin, Z\. Zhu, H\. Ren, and J\. Tang\(2022\)Inductive logical query answering in knowledge graphs\.Advances in neural information processing systems35,pp\. 15230–15243\.Cited by:[§I](https://arxiv.org/html/2607.07422#S1.p5.1),[§II](https://arxiv.org/html/2607.07422#S2.p4.1),[§V\-A](https://arxiv.org/html/2607.07422#S5.SS1.p12.1),[§V\-A](https://arxiv.org/html/2607.07422#S5.SS1.p2.1),[§V\-A](https://arxiv.org/html/2607.07422#S5.SS1.p3.1),[§V\-A](https://arxiv.org/html/2607.07422#S5.SS1.p5.11),[§V\-B](https://arxiv.org/html/2607.07422#S5.SS2.p9.1)\.
- \[10\]M\. Galkin, E\. Denis, J\. Wu, and W\. L\. Hamilton\(2021\)Nodepiece: compositional and parameter\-efficient representations of large knowledge graphs\.arXiv preprint arXiv:2106\.12144\.Cited by:[§I](https://arxiv.org/html/2607.07422#S1.p5.1),[§II](https://arxiv.org/html/2607.07422#S2.p4.1),[§V\-A](https://arxiv.org/html/2607.07422#S5.SS1.p2.1)\.
- \[11\]M\. Galkin, X\. Yuan, H\. Mostafa, J\. Tang, and Z\. Zhu\(2023\)Towards foundation models for knowledge graph reasoning\.arXiv preprint arXiv:2310\.04562\.Cited by:[§II](https://arxiv.org/html/2607.07422#S2.p5.1),[§V\-A](https://arxiv.org/html/2607.07422#S5.SS1.p4.1)\.
- \[12\]M\. Galkin, J\. Zhou, B\. Ribeiro, J\. Tang, and Z\. Zhu\(2024\)Zero\-shot logical query reasoning on any knowledge graph\.arXiv preprint arXiv:2404\.07198\.Cited by:[§II](https://arxiv.org/html/2607.07422#S2.p5.1),[§V\-A](https://arxiv.org/html/2607.07422#S5.SS1.p4.1)\.
- \[13\]S\. Guo, Q\. Wang, L\. Wang, B\. Wang, and L\. Guo\(2016\)Jointly embedding knowledge graphs and logical rules\.InProceedings of the 2016 conference on empirical methods in natural language processing,pp\. 192–202\.Cited by:[§II](https://arxiv.org/html/2607.07422#S2.p1.1)\.
- \[14\]S\. Guo, Q\. Wang, L\. Wang, B\. Wang, and L\. Guo\(2018\)Knowledge graph embedding with iterative guidance from soft rules\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.32\.Cited by:[§II](https://arxiv.org/html/2607.07422#S2.p1.1)\.
- \[15\]W\. Hamilton, P\. Bajaj, M\. Zitnik, D\. Jurafsky, and J\. Leskovec\(2018\)Embedding logical queries on knowledge graphs\.Advances in neural information processing systems31\.Cited by:[§II](https://arxiv.org/html/2607.07422#S2.p2.3)\.
- \[16\]Y\. He, M\. Perlmutter, G\. Reinert, and M\. Cucuringu\(2022\)Msgnn: a spectral graph neural network based on a novel magnetic signed laplacian\.InLearning on Graphs Conference,pp\. 40–1\.Cited by:[§\-A](https://arxiv.org/html/2607.07422#A0.SS1.1.p1.6)\.
- \[17\]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\.\(2021\)Knowledge graphs\.ACM Computing Surveys \(Csur\)54\(4\),pp\. 1–37\.Cited by:[§I](https://arxiv.org/html/2607.07422#S1.p1.1)\.
- \[18\]W\. Hu, M\. Fey, M\. Zitnik, Y\. Dong, H\. Ren, B\. Liu, M\. Catasta, and J\. Leskovec\(2020\)Open graph benchmark: datasets for machine learning on graphs\.Advances in neural information processing systems33,pp\. 22118–22133\.Cited by:[§I](https://arxiv.org/html/2607.07422#S1.p10.1),[§V\-A](https://arxiv.org/html/2607.07422#S5.SS1.p1.1)\.
- \[19\]G\. Huang, G\. Dai, Y\. Wang, and H\. Yang\(2020\)Ge\-spmm: general\-purpose sparse matrix\-matrix multiplication on gpus for graph neural networks\.InSC20: International Conference for High Performance Computing, Networking, Storage and Analysis,pp\. 1–12\.Cited by:[§I](https://arxiv.org/html/2607.07422#S1.p9.6),[§V\-C](https://arxiv.org/html/2607.07422#S5.SS3.p1.6)\.
- \[20\]S\. Ji, S\. Pan, E\. Cambria, P\. Marttinen, and S\. Y\. Philip\(2021\)A survey on knowledge graphs: representation, acquisition, and applications\.IEEE transactions on neural networks and learning systems33\(2\),pp\. 494–514\.Cited by:[§I](https://arxiv.org/html/2607.07422#S1.p1.1)\.
- \[21\]M\. Kharbanda, R\. R\. Shah, and R\. Mutharaju\(2025\)RConE: rough cone embedding for multi\-hop logical query answering on multi\-modal knowledge graphs\.IEEE Transactions on Knowledge and Data Engineering\.Cited by:[§II](https://arxiv.org/html/2607.07422#S2.p2.3)\.
- \[22\]K\. Liang, L\. Meng, M\. Liu, Y\. Liu, W\. Tu, S\. Wang, S\. Zhou, X\. Liu, and F\. Sun\(2022\)A survey of knowledge graph reasoning on graph types: static, dynamic, and multimodal\.Cited by:[§II](https://arxiv.org/html/2607.07422#S2.p2.3)\.
- \[23\]X\. V\. Lin, C\. Xiong, and R\. Socher\(2023\-April 18\)Multi\-hop knowledge graph reasoning with reward shaping\.Google Patents\.Note:US Patent 11,631,009Cited by:[§II](https://arxiv.org/html/2607.07422#S2.p1.1)\.
- \[24\]R\. Liu, R\. Yin, Y\. Liu, and W\. Wang\(2024\)Aswt\-sgnn: adaptive spectral wavelet transform\-based self\-supervised graph neural network\.InProceedings of the AAAI conference on artificial intelligence,Vol\.38,pp\. 13990–13998\.Cited by:[§II](https://arxiv.org/html/2607.07422#S2.p6.1)\.
- \[25\]H\. Ren, M\. Galkin, M\. Cochez, Z\. Zhu, and J\. Leskovec\(2023\)Neural graph reasoning: complex logical query answering meets graph databases\.arXiv preprint arXiv:2303\.14617\.Cited by:[§II](https://arxiv.org/html/2607.07422#S2.p2.3)\.
- \[26\]H\. Ren, W\. Hu, and J\. Leskovec\(2020\)Query2box: reasoning over knowledge graphs in vector space using box embeddings\.arXiv preprint arXiv:2002\.05969\.Cited by:[§II](https://arxiv.org/html/2607.07422#S2.p2.3),[§V\-A](https://arxiv.org/html/2607.07422#S5.SS1.p10.1)\.
- \[27\]H\. Ren and J\. Leskovec\(2020\)Beta embeddings for multi\-hop logical reasoning in knowledge graphs\.Advances in Neural Information Processing Systems33,pp\. 19716–19726\.Cited by:[§II](https://arxiv.org/html/2607.07422#S2.p2.3),[§III](https://arxiv.org/html/2607.07422#S3.p3.6),[§V\-A](https://arxiv.org/html/2607.07422#S5.SS1.p10.1),[§V\-A](https://arxiv.org/html/2607.07422#S5.SS1.p6.16),[§V\-A](https://arxiv.org/html/2607.07422#S5.SS1.p8.4)\.
- \[28\]J\. Sardina, C\. Sardina, J\. D\. Kelleher, and D\. O’Sullivan\(2022\)Analysis of attention mechanisms in box\-embedding systems\.InIrish Conference on Artificial Intelligence and Cognitive Science,pp\. 68–80\.Cited by:[§II](https://arxiv.org/html/2607.07422#S2.p2.3)\.
- \[29\]D\. I\. Shuman, P\. Vandergheynst, and P\. Frossard\(2011\)Chebyshev polynomial approximation for distributed signal processing\.In2011 International Conference on Distributed Computing in Sensor Systems and Workshops \(DCOSS\),pp\. 1–8\.Cited by:[§IV\-A2](https://arxiv.org/html/2607.07422#S4.SS1.SSS2.p3.5)\.
- \[30\]K\. Toutanova and D\. Chen\(2015\)Observed versus latent features for knowledge base and text inference\.InProceedings of the 3rd workshop on continuous vector space models and their compositionality,pp\. 57–66\.Cited by:[§I](https://arxiv.org/html/2607.07422#S1.p10.1),[§V\-A](https://arxiv.org/html/2607.07422#S5.SS1.p1.1)\.
- \[31\]T\. Trouillon, J\. Welbl, S\. Riedel, É\. Gaussier, and G\. Bouchard\(2016\)Complex embeddings for simple link prediction\.InInternational conference on machine learning,pp\. 2071–2080\.Cited by:[§II](https://arxiv.org/html/2607.07422#S2.p2.3),[§IV\-A3](https://arxiv.org/html/2607.07422#S4.SS1.SSS3.p5.9),[§V\-D](https://arxiv.org/html/2607.07422#S5.SS4.p3.1)\.
- \[32\]H\. Wang, H\. Ren, and J\. Leskovec\(2020\)Entity context and relational paths for knowledge graph completion\.arXiv preprint arXiv:2002\.06757,pp\. 47\.Cited by:[§II](https://arxiv.org/html/2607.07422#S2.p1.1)\.
- \[33\]W\. Xiong, T\. Hoang, and W\. Y\. Wang\(2017\)Deeppath: a reinforcement learning method for knowledge graph reasoning\.arXiv preprint arXiv:1707\.06690\.Cited by:[§II](https://arxiv.org/html/2607.07422#S2.p1.1)\.
- \[34\]B\. Xu, H\. Shen, Q\. Cao, Y\. Qiu, and X\. Cheng\(2019\)Graph wavelet neural network\.arXiv preprint arXiv:1904\.07785\.Cited by:[§II](https://arxiv.org/html/2607.07422#S2.p6.1)\.
- \[35\]B\. Yang, W\. Yih, X\. He, J\. Gao, and L\. Deng\(2014\)Embedding entities and relations for learning and inference in knowledge bases\.arXiv preprint arXiv:1412\.6575\.Cited by:[§IV\-A3](https://arxiv.org/html/2607.07422#S4.SS1.SSS3.p5.9),[TABLE I](https://arxiv.org/html/2607.07422#S5.T1.2.2.2.2.7.5.2)\.
- \[36\]X\. Zhang, Y\. He, N\. Brugnone, M\. Perlmutter, and M\. Hirn\(2021\)Magnet: a neural network for directed graphs\.Advances in neural information processing systems34,pp\. 27003–27015\.Cited by:[§\-A](https://arxiv.org/html/2607.07422#A0.SS1.1.p1.6),[§\-A](https://arxiv.org/html/2607.07422#A0.SS1.p1.2),[§IV\-A1](https://arxiv.org/html/2607.07422#S4.SS1.SSS1.p2.1),[§IV\-A1](https://arxiv.org/html/2607.07422#S4.SS1.SSS1.p3.1),[§IV\-A1](https://arxiv.org/html/2607.07422#S4.SS1.SSS1.p4.26)\.
- \[37\]Z\. Zhang, J\. Wang, J\. Chen, S\. Ji, and F\. Wu\(2021\)Cone: cone embeddings for multi\-hop reasoning over knowledge graphs\.Advances in Neural Information Processing Systems34,pp\. 19172–19183\.Cited by:[§II](https://arxiv.org/html/2607.07422#S2.p2.3)\.
- \[38\]Z\. Zhu, M\. Galkin, Z\. Zhang, and J\. Tang\(2022\)Neural\-symbolic models for logical queries on knowledge graphs\.InInternational conference on machine learning,pp\. 27454–27478\.Cited by:[§I](https://arxiv.org/html/2607.07422#S1.p5.1),[§II](https://arxiv.org/html/2607.07422#S2.p2.3),[§II](https://arxiv.org/html/2607.07422#S2.p4.1),[§III](https://arxiv.org/html/2607.07422#S3.p5.5),[§IV\-A3](https://arxiv.org/html/2607.07422#S4.SS1.SSS3.p2.1),[§IV\-B](https://arxiv.org/html/2607.07422#S4.SS2.p1.1),[§IV\-C](https://arxiv.org/html/2607.07422#S4.SS3.p1.1),[§IV](https://arxiv.org/html/2607.07422#S4.p1.3),[§V\-A](https://arxiv.org/html/2607.07422#S5.SS1.p10.1),[§V\-A](https://arxiv.org/html/2607.07422#S5.SS1.p2.1)\.
- \[39\]Z\. Zhu, Z\. Zhang, L\. Xhonneux, and J\. Tang\(2021\)Neural bellman\-ford networks: a general graph neural network framework for link prediction\.Advances in Neural Information Processing Systems34,pp\. 29476–29490\.Cited by:[§I](https://arxiv.org/html/2607.07422#S1.p6.1),[§I](https://arxiv.org/html/2607.07422#S1.p8.1),[§II](https://arxiv.org/html/2607.07422#S2.p2.3),[§IV\-A3](https://arxiv.org/html/2607.07422#S4.SS1.SSS3.p1.1)\.

![[Uncaptioned image]](https://arxiv.org/html/2607.07422v1/profile/prof_pic.jpg)Mayank Kharbandareceived 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 athttps://mayankkharbanda\.github\.io/\.![[Uncaptioned image]](https://arxiv.org/html/2607.07422v1/profile/michael.jpg)Michael Cochezis Principal Investigator \(PS Fellow\) at the ELLIS Institute Finland and Professor at Å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 jyväskylä, Finland\. More information athttp://www\.cochez\.nl\.![[Uncaptioned image]](https://arxiv.org/html/2607.07422v1/profile/ratn.jpeg)Rajiv Ratn Shahis 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 human\-centered computing\. More information athttps://midas\.iiitd\.ac\.in/\.![[Uncaptioned image]](https://arxiv.org/html/2607.07422v1/x4.jpg)Raghava Mutharajuis 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 athttps://kracr\.github\.io/\.### \-AKG Laplacian

The theorems here are directly extended from MagNet\[[36](https://arxiv.org/html/2607.07422#bib.bib24)\], and mentioned here for completeness\. We first prove that the KG Laplacian for relationrris positive, semi\-definite for both the normalized and the un\-normalized Laplacian\. We then show that the normalized KG Laplacian lies in\[0,2\]\[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\[[36](https://arxiv.org/html/2607.07422#bib.bib24)\]\.

###### Theorem 1\.

LetG​\(𝒱,ℰ,ℛ\)G\(\\mathcal\{V\},\\mathcal\{E\},\\mathcal\{R\}\)is a KG with a set of nodes𝒱\\mathcal\{V\}, a set of relationsℛ\\mathcal\{R\}, and a triplet setℰ=\{\(es,r,eo\)\|es,eo∈𝒱,r∈ℛ\}\\mathcal\{E\}=\\\{\(e\_\{s\},r,e\_\{o\}\)\|e\_\{s\},e\_\{o\}\\in\\mathcal\{V\},r\\in\\mathcal\{R\}\\\}, and\|𝒱\|=N\|\\mathcal\{V\}\|=N\. Then, for allg≥0,g\\geq 0,andr∈ℛr\\in\\mathcal\{R\}𝐋u​nr​\(g\)\\boldsymbol\{L\}\_\{un\}^\{r\(g\)\}and their normalized counterpart𝐋nr​\(g\)\\boldsymbol\{L\}\_\{n\}^\{r\(g\)\}are positive semidefinite\.

###### Proof\.

Let𝐱∈ℂN\\mathbf\{x\}\\in\\mathbb\{C\}^\{N\}\. For a relationrrwe first note that since𝐋u​nr​\(g\)\\mathbf\{L\}^\{r\(g\)\}\_\{un\}is Hermitian we haveImag​\(𝐱†​𝐋u​n\(g\)​𝐱\)=0\\text\{Imag\}\(\\mathbf\{x\}^\{\\dagger\}\\mathbf\{L\}^\{\(g\)\}\_\{un\}\\mathbf\{x\}\)=0\. Next, we use the definition of𝐃sr\\mathbf\{D\}^\{r\}\_\{s\}and the fact that𝐀sr\\mathbf\{A\}^\{r\}\_\{s\}is symmetric to observe that\[[36](https://arxiv.org/html/2607.07422#bib.bib24),[16](https://arxiv.org/html/2607.07422#bib.bib3)\]\.

2​Real\\displaystyle 2\\text\{Real\}\(𝐱†​𝐋u​nr​\(g\)​𝐱\)=2​∑u,v=1N𝐃sr​\(u,v\)​𝐱​\(u\)​𝐱​\(v\)¯\\displaystyle\\left\(\\mathbf\{x\}^\{\\dagger\}\\mathbf\{L\}^\{r\(g\)\}\_\{un\}\\mathbf\{x\}\\right\)=2\\sum\_\{u,v=1\}^\{N\}\\mathbf\{D\}^\{r\}\_\{s\}\(u,v\)\\mathbf\{x\}\(u\)\\overline\{\\mathbf\{x\}\(v\)\}−2​∑u,v=1N𝐀sr​\(u,v\)​𝐱​\(u\)​𝐱​\(v\)¯​cos⁡\(𝚯r\(g\)​\(u,v\)\)\\displaystyle\-2\\sum\_\{u,v=1\}^\{N\}\\mathbf\{A\}^\{r\}\_\{s\}\(u,v\)\\mathbf\{x\}\(u\)\\overline\{\\mathbf\{x\}\(v\)\}\\cos\(\\boldsymbol\{\\Theta\}\_\{r\}^\{\(g\)\}\(u,v\)\)=2\\displaystyle=2∑u=1N𝐃sr​\(u,u\)​𝐱​\(u\)​𝐱​\(u\)¯\\displaystyle\\sum\_\{u=1\}^\{N\}\\mathbf\{D\}^\{r\}\_\{s\}\(u,u\)\\mathbf\{x\}\(u\)\\overline\{\\mathbf\{x\}\(u\)\}−2​∑u,v=1N𝐀sr​\(u,v\)​𝐱​\(u\)​𝐱​\(v\)¯​cos⁡\(𝚯r\(g\)​\(u,v\)\)\\displaystyle\-2\\sum\_\{u,v=1\}^\{N\}\\mathbf\{A\}^\{r\}\_\{s\}\(u,v\)\\mathbf\{x\}\(u\)\\overline\{\\mathbf\{x\}\(v\)\}\\cos\(\\boldsymbol\{\\Theta\}\_\{r\}^\{\(g\)\}\(u,v\)\)=2\\displaystyle=2∑u,v=1N𝐀sr​\(u,v\)​\|𝐱​\(u\)\|2\\displaystyle\\sum\_\{u,v=1\}^\{N\}\\mathbf\{A\}^\{r\}\_\{s\}\(u,v\)\|\\mathbf\{x\}\(u\)\|^\{2\}−2​∑u,v=1N𝐀sr​\(u,v\)​𝐱​\(u\)​𝐱​\(v\)¯​cos⁡\(𝚯r\(g\)​\(u,v\)\)\\displaystyle\-2\\sum\_\{u,v=1\}^\{N\}\\mathbf\{A\}^\{r\}\_\{s\}\(u,v\)\\mathbf\{x\}\(u\)\\overline\{\\mathbf\{x\}\(v\)\}\\cos\(\\boldsymbol\{\\Theta\}\_\{r\}^\{\(g\)\}\(u,v\)\)=\\displaystyle=∑u,v=1N𝐀sr​\(u,v\)​\|𝐱​\(u\)\|2\+∑u,v=1N𝐀sr​\(v,u\)​\|𝐱​\(v\)\|2\\displaystyle\\sum\_\{u,v=1\}^\{N\}\\mathbf\{A\}^\{r\}\_\{s\}\(u,v\)\|\\mathbf\{x\}\(u\)\|^\{2\}\+\\sum\_\{u,v=1\}^\{N\}\\mathbf\{A\}^\{r\}\_\{s\}\(v,u\)\|\\mathbf\{x\}\(v\)\|^\{2\}−2​∑u,v=1N𝐀sr​\(u,v\)​𝐱​\(u\)​𝐱​\(v\)¯​cos⁡\(𝚯r\(g\)​\(u,v\)\)\\displaystyle\-2\\sum\_\{u,v=1\}^\{N\}\\mathbf\{A\}^\{r\}\_\{s\}\(u,v\)\\mathbf\{x\}\(u\)\\overline\{\\mathbf\{x\}\(v\)\}\\cos\(\\boldsymbol\{\\Theta\}\_\{r\}^\{\(g\)\}\(u,v\)\)=\\displaystyle=∑u,v=1N𝐀sr​\(u,v\)​\|𝐱​\(u\)\|2\+∑u,v=1N𝐀sr​\(u,v\)​\|𝐱​\(v\)\|2\\displaystyle\\sum\_\{u,v=1\}^\{N\}\\mathbf\{A\}^\{r\}\_\{s\}\(u,v\)\|\\mathbf\{x\}\(u\)\|^\{2\}\+\\sum\_\{u,v=1\}^\{N\}\\mathbf\{A\}^\{r\}\_\{s\}\(u,v\)\|\\mathbf\{x\}\(v\)\|^\{2\}−2​∑u,v=1N𝐀sr​\(u,v\)​𝐱​\(u\)​𝐱​\(v\)¯​cos⁡\(𝚯r\(g\)​\(u,v\)\)\\displaystyle\-2\\sum\_\{u,v=1\}^\{N\}\\mathbf\{A\}^\{r\}\_\{s\}\(u,v\)\\mathbf\{x\}\(u\)\\overline\{\\mathbf\{x\}\(v\)\}\\cos\(\\boldsymbol\{\\Theta\}\_\{r\}^\{\(g\)\}\(u,v\)\)=\\displaystyle=∑u,v=1N𝐀sr​\(u,v\)\\displaystyle\\sum\_\{u,v=1\}^\{N\}\\mathbf\{A\}^\{r\}\_\{s\}\(u,v\)\(\|𝐱​\(u\)\|2\+\|𝐱​\(v\)\|2−2​𝐱​\(u\)​𝐱​\(v\)¯​cos⁡\(𝚯r\(g\)​\(u,v\)\)\)\\displaystyle\\left\(\|\\mathbf\{x\}\(u\)\|^\{2\}\+\|\\mathbf\{x\}\(v\)\|^\{2\}\-2\\mathbf\{x\}\(u\)\\overline\{\\mathbf\{x\}\(v\)\}\\cos\(\\boldsymbol\{\\Theta\}\_\{r\}^\{\(g\)\}\(u,v\)\)\\right\)\(25\)≥\\displaystyle\\geq∑u,v=1N𝐀sr​\(u,v\)​\(\|𝐱​\(u\)\|2\+\|𝐱​\(v\)\|2−2​\|𝐱​\(u\)\|​\|𝐱​\(v\)\|\)\\displaystyle\\sum\_\{u,v=1\}^\{N\}\\mathbf\{A\}^\{r\}\_\{s\}\(u,v\)\\left\(\|\\mathbf\{x\}\(u\)\|^\{2\}\+\|\\mathbf\{x\}\(v\)\|^\{2\}\-2\|\\mathbf\{x\}\(u\)\|\|\\mathbf\{x\}\(v\)\|\\right\)=\\displaystyle=∑u,v=1N𝐀sr​\(u,v\)​\(\|𝐱​\(u\)\|−\|𝐱​\(v\)\|\)2≥0\.\\displaystyle\\sum\_\{u,v=1\}^\{N\}\\mathbf\{A\}^\{r\}\_\{s\}\(u,v\)\(\|\\mathbf\{x\}\(u\)\|\-\|\\mathbf\{x\}\(v\)\|\)^\{2\}\\geq 0\.Thus, each𝐋u​nr​\(g\)\\mathbf\{L\}\_\{un\}^\{r\(g\)\}is positive semidefinite, forr∈Rr\\in R\. For the normalized magnetic Laplacian, we note that

𝐋nr​\(g\)=𝑫z−1/2​𝐋u​nr​\(g\)​𝑫z−1/2,𝐃z​\(u,u\)=∑r∈ℛ∑v∈𝒱𝐀sr​\(u,v\)\\mathbf\{L\}^\{r\(g\)\}\_\{n\}=\\boldsymbol\{D\}\_\{z\}^\{\-1/2\}\\mathbf\{L\}^\{r\(g\)\}\_\{un\}\\boldsymbol\{D\}\_\{z\}^\{\-1/2\},\\;\\;\\;\\mathbf\{D\}\_\{z\}\(u,u\)=\\sum\_\{r\\in\\mathcal\{R\}\}\\sum\_\{v\\in\\mathcal\{V\}\}\\mathbf\{A\}^\{r\}\_\{s\}\(u,v\)\(26\)We are usingDzD\_\{z\}for normalization in place ofDsrD\_\{s\}^\{r\}, to get normalized value influenced by the complete graph rather than a particular relation\. Thus, letting𝐲=𝐃z−1/2​𝐱,\\mathbf\{y\}=\\mathbf\{D\}\_\{z\}^\{\-1/2\}\\mathbf\{x\},the fact that𝐃z\\mathbf\{D\}\_\{z\}is diagonal implies

𝐱†​𝐋nr​\(g\)​𝐱=𝐱†​𝑫z−1/2​𝐋u​nr​\(g\)​𝑫z−1/2​𝐱=𝐲†​𝐋u​nr​\(g\)​𝐲≥0\.\\mathbf\{x\}^\{\\dagger\}\\mathbf\{L\}^\{r\(g\)\}\_\{n\}\\mathbf\{x\}=\\mathbf\{x\}^\{\\dagger\}\\boldsymbol\{D\}\_\{z\}^\{\-1/2\}\\mathbf\{L\}^\{r\(g\)\}\_\{un\}\\boldsymbol\{D\}\_\{z\}^\{\-1/2\}\\mathbf\{x\}=\\mathbf\{y\}^\{\\dagger\}\\mathbf\{L\}^\{r\(g\)\}\_\{un\}\\mathbf\{y\}\\geq 0\.∎

###### Theorem 2\.

LetG​\(𝒱,ℰ,ℛ\)G\(\\mathcal\{V\},\\mathcal\{E\},\\mathcal\{R\}\)is a KG with a set of nodes𝒱\\mathcal\{V\}, a set of relationsℛ\\mathcal\{R\}, and a triplet setℰ=\{\(es,r,eo\)\|es,eo∈𝒱,r∈ℛ\}\\mathcal\{E\}=\\\{\(e\_\{s\},r,e\_\{o\}\)\|e\_\{s\},e\_\{o\}\\in\\mathcal\{V\},r\\in\\mathcal\{R\}\\\}\. Then, for allg≥0g\\geq 0, andr∈ℛr\\in\\mathcal\{R\}the eigenvalues of the normalized magnetic Laplacian𝐋nr​\(g\)\\mathbf\{L\}\_\{n\}^\{r\(g\)\}are contained in the interval\[0,2\]\[0,2\]\.

###### Proof\.

By Theorem[1](https://arxiv.org/html/2607.07422#Thmtheorem1), we know that𝐋nr​\(g\)\\mathbf\{L\}^\{r\(g\)\}\_\{n\}has real, nonnegative eigenvalues\. Therefore, we need to show that the lead eigenvalue,λN,\\lambda\_\{N\},is less than or equal to 2\. The Courant\-Fischer theorem shows that

λN=max𝐱≠0⁡𝐱†​𝐋nr​\(g\)​𝐱𝐱†​𝐱\.\\lambda\_\{N\}=\\max\_\{\\mathbf\{x\}\\neq 0\}\\frac\{\\mathbf\{x\}^\{\\dagger\}\\mathbf\{L\}^\{r\(g\)\}\_\{n\}\\mathbf\{x\}\}\{\\mathbf\{x\}^\{\\dagger\}\\mathbf\{x\}\}\.Therefore, using \([26](https://arxiv.org/html/2607.07422#A0.E26)\) and setting𝐲=𝐃z−1/2​𝐱\\mathbf\{y\}=\\mathbf\{D\}\_\{z\}^\{\-1/2\}\\mathbf\{x\}, we have

λN=max𝐱≠0⁡𝐱†​𝐃z−1/2​𝐋u​nr​\(g\)​𝐃z−1/2​𝐱𝐱†​𝐱=max𝐲≠0⁡𝐲†​𝐋u​n\(g\)​𝐲𝐲†​𝐃z​𝐲\.\\lambda\_\{N\}=\\max\_\{\\mathbf\{x\}\\neq 0\}\\frac\{\\mathbf\{x\}^\{\\dagger\}\\mathbf\{D\}\_\{z\}^\{\-1/2\}\\mathbf\{L\}^\{r\(g\)\}\_\{un\}\\mathbf\{D\}\_\{z\}^\{\-1/2\}\\mathbf\{x\}\}\{\\mathbf\{x\}^\{\\dagger\}\\mathbf\{x\}\}=\\max\_\{\\mathbf\{y\}\\neq 0\}\\frac\{\\mathbf\{y\}^\{\\dagger\}\\mathbf\{L\}^\{\(g\)\}\_\{un\}\\mathbf\{y\}\}\{\\mathbf\{y\}^\{\\dagger\}\\mathbf\{D\}\_\{z\}\\mathbf\{y\}\}\.First, we observe that since𝐃z\\mathbf\{D\}\_\{z\}is diagonal, we have

𝐲†​𝐃z​𝐲=∑u,v=1N𝐃z​\(u,v\)​𝐲​\(u\)​𝐲​\(v\)¯=∑u=1N𝐃z​\(u,u\)​\|𝐲​\(u\)\|2\\mathbf\{y\}^\{\\dagger\}\\mathbf\{D\}\_\{z\}\\mathbf\{y\}=\\sum\_\{u,v=1\}^\{N\}\\mathbf\{D\}\_\{z\}\(u,v\)\\mathbf\{y\}\(u\)\\overline\{\\mathbf\{y\}\(v\)\}=\\sum\_\{u=1\}^\{N\}\\mathbf\{D\}\_\{z\}\(u,u\)\|\\mathbf\{y\}\(u\)\|^\{2\}Next, we note that by \([25](https://arxiv.org/html/2607.07422#A0.E25)\), we have

𝐲†\\displaystyle\\mathbf\{y\}^\{\\dagger\}𝐋u​nr​\(g\)𝐲=∑u,v=1N𝐀sr\(u,v\)\(\|𝐱\(u\)\|2\+\|𝐱\(v\)\|2\\displaystyle\\mathbf\{L\}^\{r\(g\)\}\_\{un\}\\mathbf\{y\}=\\sum\_\{u,v=1\}^\{N\}\\mathbf\{A\}^\{r\}\_\{s\}\(u,v\)\(\|\\mathbf\{x\}\(u\)\|^\{2\}\+\|\\mathbf\{x\}\(v\)\|^\{2\}−2𝐱\(u\)𝐱​\(v\)¯cos\(𝚯r\(g\)\(u,v\)\)\)\\displaystyle\-2\\mathbf\{x\}\(u\)\\overline\{\\mathbf\{x\}\(v\)\}\\cos\(\\boldsymbol\{\\Theta\}\_\{r\}^\{\(g\)\}\(u,v\)\)\)≤12​∑u,v=1N𝐀sr​\(u,v\)​\(\|𝐱​\(u\)\|\+\|𝐱​\(v\)\|\)2\\displaystyle\\leq\\frac\{1\}\{2\}\\sum\_\{u,v=1\}^\{N\}\\mathbf\{A\}^\{r\}\_\{s\}\(u,v\)\(\|\\mathbf\{x\}\(u\)\|\+\|\\mathbf\{x\}\(v\)\|\)^\{2\}≤∑u,v=1N𝐀sr​\(u,v\)​\(\|𝐱​\(u\)\|2\+\|𝐱​\(v\)\|2\)\.\\displaystyle\\leq\\sum\_\{u,v=1\}^\{N\}\\mathbf\{A\}^\{r\}\_\{s\}\(u,v\)\(\|\\mathbf\{x\}\(u\)\|^\{2\}\+\|\\mathbf\{x\}\(v\)\|^\{2\}\)\.Therefore, since𝐀𝐬𝐫\\mathbf\{A^\{r\}\_\{s\}\}is symmetric, we have

𝐲†​𝐋u​nr​\(g\)\\displaystyle\\mathbf\{y\}^\{\\dagger\}\\mathbf\{L\}^\{r\(g\)\}\_\{un\}𝐲≤2​∑u,v=1N𝐀sr​\(u,v\)​\|𝐱​\(u\)\|2=2​∑u=1N\|𝐱​\(u\)\|2​\(∑v=1N𝐀sr​\(u,v\)\)\\displaystyle\\mathbf\{y\}\\leq 2\\sum\_\{u,v=1\}^\{N\}\\mathbf\{A\}^\{r\}\_\{s\}\(u,v\)\|\\mathbf\{x\}\(u\)\|^\{2\}=2\\sum\_\{u=1\}^\{N\}\|\\mathbf\{x\}\(u\)\|^\{2\}\\left\(\\sum\_\{v=1\}^\{N\}\\mathbf\{A\}^\{r\}\_\{s\}\(u,v\)\\right\)=2​∑u=1N𝐃sr​\(u,u\)​\|𝐱​\(u\)\|2≤2​∑u=1N𝐃z​\(u,u\)​\|𝐱​\(u\)\|2=2​𝐲†​𝐃z​𝐲\.\\displaystyle=2\\sum\_\{u=1\}^\{N\}\\mathbf\{D\}^\{r\}\_\{s\}\(u,u\)\|\\mathbf\{x\}\(u\)\|^\{2\}\\leq 2\\sum\_\{u=1\}^\{N\}\\mathbf\{D\}\_\{z\}\(u,u\)\|\\mathbf\{x\}\(u\)\|^\{2\}=2\\mathbf\{y\}^\{\\dagger\}\\mathbf\{D\}\_\{z\}\\mathbf\{y\}\.∎

### \-BQuery Statistics and Results

TABLE I:Number of queries generated for each dataset ratio and query type\.The number of queries generated for each dataset are provided in Table[I](https://arxiv.org/html/2607.07422#A0.T1)\. The statistics mentioned as the train graph are for the graph𝒱t​r​a​i​n0\\mathcal\{V\}\_\{train\_\{0\}\}\.