# Flashlight : Scalable Link Prediction with Effective Decoders

Yiwei Wang1 Bryan Hooi1 Yozen Liu2 Tong Zhao2
Zhichun Guo2 Neil Shah2
1 National University of Singapore
2 Snap Inc.
<EMAIL_ADDRESS>
###### Abstract

Link prediction (LP) has been recognized as an important task in graph
learning with its broad practical applications. A typical application of LP is
to retrieve the top scoring neighbors for a given source node, such as the
friend recommendation. These services desire the high inference scalability to
find the top scoring neighbors from many candidate nodes at low latencies.
There are two popular decoders that the recent LP models mainly use to compute
the edge scores from node embeddings: the HadamardMLP and Dot Product
decoders. After theoretical and empirical analysis, we find that the
HadamardMLP decoders are generally more effective for LP. However, HadamardMLP
lacks the scalability for retrieving top scoring neighbors on large graphs,
since to the best of our knowledge, there does not exist an algorithm to
retrieve the top scoring neighbors for HadamardMLP decoders in sublinear
complexity. To make HadamardMLP scalable, we propose the Flashlight algorithm
to accelerate the top scoring neighbor retrievals for HadamardMLP: a sublinear
algorithm that progressively applies approximate maximum inner product search
(MIPS) techniques with adaptively adjusted query embeddings. Empirical results
show that Flashlight improves the inference speed of LP by more than 100 times
on the large OGBL-CITATION2 dataset without sacrificing effectiveness. Our
work paves the way for large-scale LP applications with the effective
HadamardMLP decoders by greatly accelerating their inference.

##  1 Introduction

The goal of link prediction (LP) is to predict the missing links in a graph
[1]. LP is drawing increasing attention in the past decade due to its board
practical applications [2]. For instance, LP can be used to recommend new
friends on social media [3], and recommend attractive items to the costumers
on E-commerce sites [4], so as to improve the user experience. During
inference, these applications demand the LP methods to retrieve the top
scoring neighbors for a source node at low latencies. This is especially
challenging on large graphs because the LP methods need to search many
candidate nodes to find the top scoring neighbors.

There are two main kinds of architecture followed by the recent LP models. The
first uses an encoder, e.g., GCN [5], to obtain the node-level embeddings and
uses a decoder, e.g., Dot Product, to get the edge scores between the paired
nodes [6]. The second crops a subgraph for every edge and computes the edge
score from the subgraph directly [7]. The inference speed of the second is
much lower than the first, so we focus on the first kind of models to achieve
fast inference on large graphs. In the last years, extensive research focuses
on developing more expressive LP encoders [6, 8]. However, much less work pays
attention to the essential impacts of the choice of decoders on LP’s
performance. In this work, we theoretically and empirically analyze two
popular LP decoders: Dot Product and HadamardMLP (a MLP following the Hadamard
Product), and find that the latter is generally more effective than the
former.

In practical applications, we should not only consider the effectiveness of
LP, but also inference efficiency. Many LP applications generally require fast
retrieval of the top scoring neighbors for low-latency services [3, 9, 10].
For a Dot Product decoder, this retrieval can be approximated efficiently at
the sublinear time complexity [11]. However, to the best of our knowledge, no
such sublinear algorithms exist for the top scoring neighbor retrievals of the
HadamardMLP decoders. This means that for every source node, we have to
iterate over all the nodes in the graph to compute the scores so as to find
the top scoring neighbors for HadamardMLP, which is of linear complexity and
cannot scale to large graphs.

To allow LP applications to enjoy the high effectiveness of HadamardMLP
decoders while avoiding the poor inference scalability, we propose the
scalable top scoring neighbor search algorithm named Flashlight. Our
Flashlight progressively calls the well-developed approximate maximum inner
product search (MIPS) techniques for a few iterations. At every iteration, we
analyze the retrieved neighbors and adaptively adjust the query embedding for
Flashlight to find the missed high scoring neighbors. Our Flashlight algorithm
holds sublinear time complexity on finding top scoring neighbors for
HadamardMLP decoders, allowing for fast and scalable inference. Empirical
results show that Flashlight accelerates the inference of LP models by more
than 100 times on the large OGBL-CITATION2 dataset without sacrificing the
effectiveness. Overall, our work paves the way for the use of effective LP
decoders in practical settings by greatly accelerating their inference.

##  2 Revisiting Link Prediction Decoders

In this section, we formalize the link prediction (LP) problem and the LP
decoders. Typically, many LP models include an encoder that learns the node-
level embeddings $\mathbf{x}_{i},i\in\mathcal{V}$, where $\mathcal{V}$ is the
set of nodes, and an decoder
$\phi:\mathbb{R}^{d}\times\mathbb{R}^{d}\rightarrow\mathbb{R}$ that combines
the node-level embeddings of a pair of nodes: $\mathbf{x}_{i},\mathbf{x}_{j}$
into a single score: $s_{ij}$. If $s_{ij}$ is higher, the link between nodes
$i$ and $j$ is more likely to exist. The state-of-the-art models generally use
graph neural networks as the encoders [5, 12, 13, 6, 8]. From here on, we
mainly focus on the decoder $\phi$.

###  2.1 Dot Product Decoder

The most common decoder of link prediction is the Dot Product [6, 8, 10]:

$s_{ij}=\phi^{\mathrm{dot}}(\mathbf{x}_{i},\mathbf{x}_{j})\coloneqq\mathbf{x}_{i}\mathbin{\vbox{\hbox{{$\bullet$}}}}\mathbf{x}_{j},$
(1)

where $\mathbin{\vbox{\hbox{{$\bullet$}}}}$ denotes the dot product.

Training a link prediction model with the Dot Product decoder encourages the
embeddings of the connected nodes to be close to each other. Intuitively, the
score $s_{ij}$ can be thought as a measure of the squared Eulidean distance
between the node embeddings $\mathbf{x}_{i},\mathbf{x}_{j}$, as
$\|\mathbf{x}_{i}-\mathbf{x}_{j}\|^{2}=\|\mathbf{x}_{i}\|^{2}-2\mathbf{x}_{i}\mathbin{\vbox{\hbox{{$\bullet$}}}}\mathbf{x}_{j}+\|\mathbf{x}_{j}\|^{2}$,
if the $\|\mathbf{x}_{j}\|$ is constant over the neighbors $j\in\mathcal{N}$,
e.g., after normalization [14]. Because the node embeddings represent the
semantic information of nodes, Dot Product assumes the homophily of graph
topology, i.e., the semantically similar nodes are more likely to be
connected.

Figure 1: Two popular LP decoders: The Dot Product (left), equivalent to the
element-wise summation following the Hadamard product, and the HadamardMLP
decoder (right).

###  2.2 HadamardMLP (MLP following Hadamard Product) Decoder

Multi layer perceptrons (MLPs) are known to be universal approximators that
can approximate any continuous function on a compact set [15]. A MLP layer can
be defined as a function
$f:\mathbb{R}^{d_{\mathrm{in}}}\rightarrow\mathbb{R}^{d_{\mathrm{out}}}$:

$f_{\mathbf{W}}(\mathbf{x})=\mathrm{ReLU}(\mathbf{W}\mathbf{x})$ (2)

which is parameterized by the learnable weight
$\mathbf{W}\in\mathbb{R}^{d_{\mathrm{out}}\times d_{\mathrm{in}}}$ (the bias,
if exists, can be represented by an additional column in $\mathbf{W}$ and an
additional channel in the input $\mathbf{x}$ with the value as $1$).
$\mathrm{ReLU}$ is the activation function. In a MLP, several layers of $f$
are stacked, e.g., a 3-layer MLP can be formalized as
$f_{\mathbf{W}_{3}}(f_{\mathbf{W}_{2}}(f_{\mathbf{W}_{1}}(\mathbf{x})))$.

The state-of-the-art models widely use a MLP following the Hadamard Product
between the paired nodes as the decoder (short as the HadamardMLP decoders)
[6, 10, 8, 16]:

$s_{ij}=\phi^{\mathrm{MLP}}(\mathbf{x}_{i},\mathbf{x}_{j})\coloneqq\mathrm{MLP}(\mathbf{x}_{i}\odot\mathbf{x}_{j})=\mathbf{w}_{L}^{T}(f_{\mathbf{W}_{L-1}}(\dots
f_{\mathbf{W}_{1}}(\mathbf{x}_{i}\odot\mathbf{x}_{j})\dots)),$ (3)

where $\odot$ denotes the Hadamard Product. Fig. 1 illustrates these two
models the Dot Product and HadamardMLP decoders.

Figure 2: HadamardMLP achieves higher Mean Reciprocal Rank (MRR, higher is
better) than other decoders on the OGBL-CITATION2 [16] dataset with the
encoder as GraphSAGE [12] and GCN [5]. More empirical results and the detailed
settings are in Sec. 6.3.

###  2.3 Other Link Prediction Decoders

In principle, every function that takes two vectors as the input and outputs a
scalar can act as the decoder. For example, there are bilinear dot product
decoder (short as Bilinear decoder) [6]:

$s_{ij}=\mathbf{h}_{i}^{T}\mathbf{W}\mathbf{h}_{j},$ (4)

where $\mathbf{W}$ is the learnable weight, and the MLPs following the
concatenate decoder [10, 6] (short as ConcatMLP decoder):

$s_{ij}=\mathrm{MLP}(\mathbf{h}_{i}\|\mathbf{h}_{j})$ (5)

, etc. These two decoders are used much less than Dot Product and HadamardMLP
in the state-of-the-art LP models possibly due to their lower effectiveness
[6, 10, 8, 16].

###  2.4 HadamardMLP is Generally More Effective than Other Decoders

Dot Product demands the homophily of graph data to effectively infer the link
between nodes. In contrast, thanks to the universal approximation capability,
MLP can approximate any continuous function, and thus does not demand the
homophily of graph data for effective LP. This gap in the expressiveness
accounts for the performance difference of these two decoders on many datasets
(see Sec. 6.3). We additionally show in Appendix. A that using a HadamardMLP
is easy to learn Dot Product, which also partially accounts for the better
effectiveness of the HadamardMLP decoders over the Dot Product. Existing work
also finds that the effectiveness of Bilinear and ConcatMLP is generally worse
than the HardmardMLP or Dot Product decoder [6, 10, 8, 16]. We confirm these
findings more rigorously in the empirical results in Fig. 2 and more complete
in Sec. 6.3.

##  3 Scalability of Link Prediction Decoders

Most academic studies focus on training runtime when discussing scalability.
However, in industrial applications, the inference speed is often more
important. The inference of many LP applications needs to retrieve the top
scoring neighbors given a source node, e.g., recommending friends to a user
for friend recommendation. Given a source node, if there are $n$ nodes in the
graph, then the inference time complexity is $\mathcal{O}(n)$ if the decoder
needs to iterate over all the $n$ nodes to compute the edge scores. For large
scale applications, $n$ is typically in the range of millions, or even larger.
The empirical results show that the inference time of finding the top scoring
neighbors for a source node is longer than one second for HadamardMLP on the
OGBL-CITATION2 dataset of nearly three million nodes (see Sec. 6.5).

For a Dot Product decoder, the problem of finding the top scoring neighbors
can be approximated efficiently. This is a well-studied problem, known as
approximate maximum inner product search (MIPS) [17, 18] (see Sec. 5.2 for a
comprehensive literature review). MIPS techniques allow Dot Product’ inference
to be completed in a few milliseconds, even with millions of neighbors. There
exists some work that tries to extend MIPS to the ConcatMLP [19, 20]. These
methods hold strict assumptions on the models’ training and are not directly
applicable to the HadamardMLP. To the best of our knowledge, no such sublinear
techniques exist for the top scoring neighbor retrieval with the HadamardMLP
[10], which is a complex nonlinear function.

To summarize, the HadamardMLP decoder is not scalable for the real time LP
services on large graphs, while the Dot Product decoder allows fast retrieval
using the well established MIPS techniques.

##  4 Flashlight: Scalable Link Prediction with Effective Decoders

Sec. 2 has shown that the HadamardMLP decoder enjoys higher effectiveness than
the Dot Product decoder, which supports the superior performance of
HadamardMLP on many LP benchmarks. On the other hand, Sec. 3 has shown that
the HadamardMLP is not scalable for real time LP applications on large graphs,
while Dot Product supports the fast inference using the well-established MIPS
techniques. In this section, we aim to devise fast inference algorithms for
HadamardMLP to enable scalable LP with effective decoders.

We try to exploit the advances in the well-developed MIPS techniques to
accelerate the inference of HadamardMLP. Specifically, we divide the top
scoring retrievals for HadamardMLP predictors into a sequence of MIPS. Our
algorithm works in a progressive manner. The query embedding in every search
is adaptively adjusted to find the high scoring neighbors missed in the last
search.

The challenge of retrieving the neighbors of highest scores for HadamardMLP is
rooted in the unawareness of which neurons are activated, since if we know
which neurons are activated, the nonlinear HadamardMLP degrades to a linear
model. On the $l$th MLP layer, we define the mask matrix
$\mathbf{M}_{\mathcal{A},l}\in\mathbb{R}^{d_{l}\times d_{l}}$ to represent the
set of activated neurons $\mathcal{A}$ as

$M_{ij}=\begin{cases}1,&\text{if}\ i=j\ \text{and}\ i\in\mathcal{A}\\\
0,&\text{otherwise}\end{cases}$ (6)

With $\mathbf{M}_{\mathcal{A},l}$, we reformulate the HadamardMLP decoder as:

$\displaystyle s_{ij}=\phi^{\mathrm{MLP}}(\mathbf{x}_{i},\mathbf{x}_{j})$
$\displaystyle=\mathbf{w}_{L}^{T}\mathbf{M}_{\mathcal{A},L-1}\mathbf{W}_{L-1}\dots\mathbf{M}_{\mathcal{A},1}\mathbf{W}_{1}(\mathbf{x}_{i}\odot\mathbf{x}_{j})$
$\displaystyle=(\mathbf{W}_{1}^{T}\mathbf{M}_{\mathcal{A},1}\dots\mathbf{W}_{L-1}^{T}\mathbf{M}_{\mathcal{A},L-1}\mathbf{w}_{L}\odot\mathbf{x}_{i})\mathbin{\vbox{\hbox{{$\bullet$}}}}\mathbf{x}_{j}$
(7)

Because the vector
$\mathbf{W}_{1}^{T}\mathbf{M}_{\mathcal{A},1}\dots\mathbf{W}_{L-1}^{T}\mathbf{M}_{\mathcal{A},L-1}^{T}\mathbf{w}_{L}$
is determined by the weights of MLP and the activated neurons $\mathcal{A}$,
we term it as $\mathrm{MLP}_{\mathcal{A}}(\cdot)$:

$\mathrm{MLP}_{\mathcal{A}}(\cdot)\coloneqq\mathbf{W}_{1}^{T}\mathbf{M}_{\mathcal{A},1}\dots\mathbf{W}_{L-1}^{T}\mathbf{M}_{\mathcal{A},L-1}^{T}\mathbf{w}_{L}$
(8)

Given the source node $i$, because the score $s_{ij}$ is obtained by the dot
product between
$(\mathbf{W}_{1}^{T}\mathbf{M}_{\mathcal{A},1}\dots\mathbf{W}_{L-1}^{T}\mathbf{M}_{\mathcal{A},L-1}^{T}\mathbf{w}_{L}\odot\mathbf{x}_{i})$
and the neighbor embedding $\mathbf{x}_{j}$, we term the former vector as the
query embedding $\mathbf{q}$:

$\mathbf{q}\coloneqq\mathbf{W}_{1}^{T}\mathbf{M}_{\mathcal{A},1}\dots\mathbf{W}_{L-1}^{T}\mathbf{M}_{\mathcal{A},L-1}\mathbf{w}_{L}\odot\mathbf{x}_{i}=\mathrm{MLP}_{\mathcal{A}}(\cdot)\odot\mathbf{x}_{i}$
(9)

In this way, we can reformulate the output of decoder
$\phi^{MLP}(\mathbf{x}_{i},\mathbf{x_{j}})$ as

$s_{ij}=\phi^{\mathrm{MLP}}(\mathbf{x}_{i},\mathbf{x}_{j})=\mathbf{q}\mathbin{\vbox{\hbox{{$\bullet$}}}}\mathbf{x}_{j}.$
(10)

In practice, we can use the $\mathbf{q}$ as the query embedding in MIPS to
retrieve the neighbors of highest inner products, which correspond to the
highest scores. Here, how to get the activated neurons $\mathcal{A}$ so as to
obtain the query embedding $\mathbf{q}$ is an issue. Different node pairs
activate different neurons $\mathcal{A}$. Initially, without knowing which
neurons are activated, we first assume all the neurons are activated, i.e., we
have the initial query embedding as:

$\mathbf{q}[1]=(\prod_{i=1}^{L-1}\mathbf{W}_{i}^{T})\mathbf{w}_{L}\odot\mathbf{x}_{i}$
(11)

This initial design can reflect the general trends of increasing the edge
scores on LP, without restricting which neurons are activated. We use
$\mathbf{q}[1]$ as the query embedding to retrieve the highest inner product
neighbors as $\mathcal{N}[1]$ in the first iteration. Then, given the
retrieved neighbors in the $t$th iteration as $\mathcal{N}[t]$, we analyze the
$\mathcal{N}[t]$ and adaptively adjust the query embedding $\mathbf{q}[t+1]$
that we use in the next iteration to find more high scoring neighbors.
Specifically, we operate the feed-forward to MLP for $\mathcal{N}(t)$. We
define the function $A(\cdot,\cdot)$ that returns the set of activated neurons
for a MLP (the first input) with the input $\mathbf{x}_{i}\odot\mathbf{x}_{j}$
(the second input). Then we can use it to extract $\mathcal{A}$ as:

$\mathcal{A}=A(\mathrm{MLP}(\cdot),\mathbf{x}_{i}\odot\mathbf{x}_{j}).$ (12)

Then, we obtain the set of activated neurons of the highest scored neighbor at
the $t$th iteration as:

$\mathcal{A}[t]\leftarrow
A(\mathrm{MLP}(\cdot),\mathbf{x}_{i}\odot\mathbf{x}_{j^{\star}[t]}),\
\text{where}\
j^{\star}[t]=\arg\max_{j\in\mathcal{N}[t]}\mathrm{MLP}(\mathbf{x}_{i}\odot\mathbf{x}_{j}).$
(13)

This implies that the neighbors activating $\mathcal{A}[t]$ can obtain the
high edge scores. Then, if we take $\mathcal{A}[1]$ as the set of neurons that
we activate at the next query, we could find more high scoring neighbors. In
this way, we set the neurons that we assume to activate in the next iteration
as $\mathcal{A}[t]$. We repeat the above iterations until enough neighbors are
retrieved. The algorithm is summarized in Alg. 1.

We name our algorithm as Flashlight because it works like a flashlight to
progressively “illuminates” the semantic space to find the high scoring
neighbors. The query embeddings are like the lights sent from the flashlight.
And our process of adjusting the query embeddings is just like progressively
adjusting the “lights” from the “flashlight” by checking the “objects” found
in the last “illumination”.

In the experiments, we find that our Flashlight algorithm is effective to find
the top scoring neighbors from the massive candidate neighbors. For example,
in Fig. 3, our Flashlight is able to find the top 100 scoring neighbors from
nearly three million candidates by retrieving only 200 neighbors in the large
OGBL-CITATION2 graph dataset for the HadamardMLP decoders.

Algorithm 1 Flashlight : progressively “illuminates” the semantic space to
retrieve the high scoring neighbors for the LP HadamardMLP decoders.

Input: A trained HadamardMLP decoder $\phi^{\mathrm{MLP}}$ that outputs the
logit $s_{ij}$ for the input $\mathbf{x}_{i}\odot\mathbf{x}_{j}$. The set of
nodes $\mathcal{V}$. The node embedding set
$\mathcal{X}=\\{\mathbf{x}_{i}|i\in\mathcal{V}\\}$. A source node $i$. The
number of iterations $T$. The number of neighbors to retrieve at every
iteration: $\mathbf{N}=[N_{1},N_{2},\dots,N_{T}]$.

Output: The recommended neighbors $\mathcal{N}$ for the source node $i$.

1:Initialize the set of retrieved recommended neighbors
$\mathcal{N}\leftarrow\emptyset$

2:Initialize the set of activated neurons as $\mathcal{A}[0]$ as all the
neurons in $\mathrm{MLP}$.

3:for $t\leftarrow 1$ to $T$ do

4: Calculate the query embedding
$\mathbf{q}[t]\leftarrow\mathbf{x}_{i}\odot\mathrm{MLP}_{\mathcal{A}[t-1]}(\cdot)$.

5: $\mathcal{N}[t]$ $\leftarrow$ $N_{t}$ neighbors in $\mathcal{X}$ that
maximizes the inner product with $\mathbf{q}[t]$.

6:
$\mathcal{X}\leftarrow\mathcal{X}\setminus\\{\mathbf{x}_{j}|j\in\mathcal{N}[t]\\}$.

7:
$j^{\star}[t]=\arg\max_{j\in\mathcal{N}[t]}\mathrm{MLP}(\mathbf{x}_{i}\odot\mathbf{x}_{j})$

8: $\mathcal{A}[t]\leftarrow
A(\mathrm{MLP}(\cdot),\mathbf{x}_{i}\odot\mathbf{x}_{j^{\star}[t]})$.

9: $\mathcal{N}\leftarrow\mathcal{N}\cup\mathcal{N}[t]$.

10:return $\mathcal{N}$

Complexity Analysis. Using MLP decoders to compute the LP probabilities of all
the neighbors holds the complexity as $\mathcal{O}(N)$, where $N$ is the
number of nodes in the whole graph. Finding the top scoring neighbors from the
exact probabilities of all the neighbors also holds the linear complexity
$\mathcal{O}(N)$. Overall, using MLP decoders to find the top scoring
neighbors is of the time complexity $\mathcal{O}(N)$. In contrast, our
Flashlight progressively calls the MIPS techniques for a constant number of
times invariant to the graph data, which leads to the sublinear complexity as
same as MIPS. In conclusion, our Flashlight improves the scalability and
applicability of HadamardMLP decoders by reducing their inference time
complexity from linear to sublinear time.

##  5 Related Work

###  5.1 Link Prediction Models

There mainly exist three categories of existing LP models: heuristic feature
based [21, 22, 3, 9, 23], latent embedding based [24, 25, 26, 27, 12, 28], and
neural network based ones. The neural network-based link prediction models,
which use neural layers to explore non-linear deep structural feature, have
been primarily investigated in recent years. Variational graph auto-encoders
[13] predict links by encoding graph with graph convolutional layer [5]. Two
cutting-edge neural network based LP models WLNM [29] and SEAL [30] transfer
the union neighborhood of a pair of nodes as a meaningful matrix and encode
the graph structural features with DGCNN [31]. More recently, [6, 8]
summarized the architectures popular LP models, and formally define the
encoders and decoders as the important components in LP architectures.

Different from the previous work, we focus on analyzing the effectiveness of
different LP decoders and improving the scalability of the effective LP
decoders. In practice, we find that the Hadamard decoders exhibit superior
effectiveness but poor scalability for inference. Our work significantly
accelerates the inference of HadamardMLP decoders to make the effective LP
scalable.

###  5.2 Maximum Inner Product Search

Finding the top scoring neighbors for the Dot Product decoder at the sublinear
time complexity is a well studied research problem, known as the approximate
maximum inner product search (MIPS). There are several approaches to MIPS:
sampling based [32, 11, 33], LSH-based [34, 35, 36, 37], graph based [38, 39,
40], and quantization approaches [17, 18]. MIPS is a fundamental building
block in various application domains [41, 42, 43, 44, 45, 46], such as
information retrieval [47, 48], pattern recognition [49, 50], data mining [51,
52], machine learning [53, 54], and recommendation systems [55, 56].

With the explosive growth of datasets’ scale and the inevitable curse of
dimensionality, MIPS is essential to offer the scalable services. However, the
HadamardMLP decoders are nonlinear and there do not exist the well studied
sublinear complexity algorithms to find the top scoring neighbors for
HadamardMLP [10]. In this work, we utilize the well studied approximate MIPS
techniques with the adaptively adjusted query embeddings to find the top
scoring neighbors for the MLP decoders in a progressive manner. Our method
supports the plug-and-play use during inference and significantly acclerates
the LP inference with the effective MLP decoders.

##  6 Experiments

In this section, we first compare the effectiveness of different LP decoders.
We find that the HadamardMLP decoders generally perform better than other
decoders. Then, we implement our Flashlight algorithm with LP models to show
that Flashlight effectively retrieves the top scoring neighbors for the
HadamardMLP decoders. As a result, the inference efficiency and scalability of
HadamardMLP decoders are improved significantly by our work.

Table 1: Statistics of datasets. Dataset | OGBL-DDI | OGBL-COLLAB | OGBL-PPA | OGBL-CITATION2
---|---|---|---|---
$\\#$Nodes | 4,267 | 235,868 | 576,289 | 2,927,963
$\\#$Edges | 1,334,889 | 1,285,465 | 30,326,273 | 30,561,187

###  6.1 Datasets

We evaluate the link prediction on Open Graph Benchmark (OGB) data [57]. We
use four OGB datasets in experiments: OGBL-DDI, OGBL-COLLAB, OGBL-CITATION2,
and OGBL-PPA, which each has a different type of graph. OGBL-DDI collects the
drug-drug interactions as a homogeneous, unweighted, undirected graph, where
each node represents a drug. Drug interactions are represented by edges. OGBL-
COLLAB is an undirected graph, where all nodes come with 128-dimensional
features. In OGBL-COLLAB, each node represents an author and edges indicate
the collaboration between authors. OGBL-CITATION2 is a directed graph,
representing the citation network between papers. A paper with 128-dimensional
word2vec characteristics makes up each node. OGBL-PPA is an undirected and
unweighted graph, where every node represents a protein from 58 different
species. The edges in OGBL-PPA indicate biologically meaningful associations
between proteins. The statistics of these datasets is presented in Table. 1.

###  6.2 Hyper-parameter Settings

For all experiments in this section, we report the average and standard
deviation over ten runs with different random seeds. The results are reported
on the the best model selected using validation data. We set hyper-parameters
of the used techniques and considered baseline methods, e.g., the batch size,
the number of hidden units, the optimizer, and the learning rate as suggested
by their authors. We use the recent MIPS method ScaNN [18] in the
implementation of our Flashlight. For the hyper-parameters of our Flashlight,
we have found in the experiments that the performance of Flashlight is robust
to the change of hyper-parameters in a board range. Therefore, we simply set
the number of iterations of our Flashlight as $T=3$ and the number of
retrieved neighbors constant as 200 per iteration by default. We run all
experiments on a machine with 80 Intel(R) Xeon(R) E5-2698 v4 @ 2.20GHz CPUs,
and a single NVIDIA V100 GPU with 16GB RAM.

Table 2: The test effectiveness comparison of LP decoders on four OGB datasets
(DDI, COLLAB, PPA, and CITATION2) [16]. We report the results of the standard
metrics averaged over 10 runs following the existing work [16, 6]. HadamardMLP
is more effective than other decoders. Flashlight effectively retrieves the
top scoring neighbors for HadamardMLP and keep its exact outputs.

Decoder Dot Product Bilinear ConcatMLP HadamardMLP HadamardMLP w/ Flashlight
OGBL-DDI GCN [5] 13.8 $\pm$ 1.8 16.1 $\pm$ 1.2 12.9 $\pm$ 1.4 37.1 $\pm$ 5.1
37.1 $\pm$ 5.1 GraphSAGE [12] 36.5 $\pm$ 2.6 39.4 $\pm$ 1.7 34.2 $\pm$ 1.9
53.9 $\pm$ 4.7 53.9 $\pm$ 4.7 Node2Vec [27] 11.6 $\pm$ 1.9 13.8 $\pm$ 1.6 10.8
$\pm$ 1.7 23.3 $\pm$ 2.1 23.3 $\pm$ 2.1 OGBL-COLLAB GCN [5] 42.9 $\pm$ 0.7
43.2 $\pm$ 0.9 42.3 $\pm$ 1.0 44.8 $\pm$ 1.1 44.8 $\pm$ 1.1 GraphSAGE [12]
37.3 $\pm$ 0.9 41.5 $\pm$ 0.8 37.0 $\pm$ 0.7 48.1 $\pm$ 0.8 48.1 $\pm$ 0.8
Node2Vec [27] 27.7 $\pm$ 1.1 31.5 $\pm$ 1.0 27.2 $\pm$ 0.8 48.9 $\pm$ 0.5 48.9
$\pm$ 0.5 OGBL-PPA GCN [5] 5.1 $\pm$ 0.4 5.8 $\pm$ 0.5 6.2 $\pm$ 0.6 18.7
$\pm$ 1.3 18.7 $\pm$ 1.3 GraphSAGE [12] 3.2 $\pm$ 0.3 6.5 $\pm$ 0.7 5.8 $\pm$
0.4 16.6 $\pm$ 2.4 16.6 $\pm$ 2.4 Node2Vec [27] 4.2 $\pm$ 0.5 7.8 $\pm$ 0.6
8.3 $\pm$ 0.4 22.3 $\pm$ 0.8 22.3 $\pm$ 0.8 OGBL-CITATION2 GCN [5] 65.3 $\pm$
0.4 69.0 $\pm$ 0.8 62.7 $\pm$ 0.3 84.7 $\pm$ 0.2 84.7 $\pm$ 0.2 GraphSAGE [12]
62.2 $\pm$ 0.7 65.4 $\pm$ 0.9 60.8 $\pm$ 0.6 80.4 $\pm$ 0.1 80.4 $\pm$ 0.1
Node2Vec [27] 52.7 $\pm$ 0.8 54.1 $\pm$ 0.6 51.4 $\pm$ 0.5 61.4 $\pm$ 0.1 61.4
$\pm$ 0.1

###  6.3 Effectiveness of Link Prediction Decoders

We follow the standard benchmark settings of OGB datasets to evaluate the
effectiveness of LP with different decoders. The benchmark setting of OGBL-DDI
is to predict drug-drug interactions given information on already known drug-
drug interactions. The performance is evaluated by Hits@20: each true drug
interaction is ranked among a set of approximately 100,000 randomly-sampled
negative drug interactions, and count the ratio of positive edges that are
ranked at 20-place or above. The task of OGBL-COLLAB is to predict the future
author collaboration relationships given the past collaborations. Evaluation
metric is Hits50, where each true collaboration is ranked among a set of
100,000 randomly-sampled negative collaborations. The task of OGBL-PPA is to
predict new association edges given the training edges. Evaluation metric is
Hits@100, where each positive edge is ranked among 3,000,000 randomly-sampled
negative edges. The task of OGBL-CITATION2 is predict missing citation given
existing citations. The evaluation metric is Mean Reciprocal Rank (MRR), where
the reciprocal rank of the true reference among 1,000 sampled negative
candidates is calculated for each source nodes, and then the average is taken
over all source nodes.

We implement different decoders as introduced in Sec. 2, including the Dot
Product, Bilinear, ConcatMLP, and the HadamardMLP decoders, over the LP
encoders, including GCN [5], GraphSAGE [12], and Node2Vec [27], to compare the
effects of different decoders on the LP effectiveness. We present the results
on the OGBL-DDI, OGBL-COLLAB, OGBL-PPA, and OGBL-CITATION2 datasets in Table.
2. We observe that the HadamardMLP decoder outperforms other decoders on all
encoders and datasets. Our Flashlight algorithm can effectively retrieve the
top scoring neighbors for the HadamardMLP decoder and keep the exact LP
probabilities of HadamardMLPs’ output, which leads to the same results of the
HadamardMLP decoder with and without Flashlight.

Note that the benchmark settings of these datasets sample a small portion of
negative edges for the test evaluation, which is not challenging enough to
evaluate the scalability of LP decoders on retrieving the top scoring
neighbors from massive candidates in practice.

###  6.4 The Flashlight Algorithm Effectively Finds the Top Scoring Neighbors

To evaluate the effectiveness of our Flashlight on retrieving the top scoring
neighbors for the HadamardMLP decoder, we propose a more challenging test
setting for the OGB LP datasets. Given a source node, we takes its top 100
scoring neighbors of the HadamardMLP decoder as the ground-truth for
retrievals. We set the task as retrieving $k$ neighbors for a source node that
can match the ground-truth neighbors as much as possible. We formally define
the metric as Recall$@k$, which is the portion of the ground-truth neighbors
being in the top $k$ neighbors retrieved by different methods.

Figure 3: Recall$@k$ is the fraction of the 100 top scoring neighbors of
HadamardMLP ranked in the top $k$ neighbors retrieved by Flashlight. We report
Recall$@k$ averaged over all the source nodes on OGBL-CITATION2 and OGBL-DDI.

We sample $1000$ nodes as the source nodes from the OGBL-DDI and OGBL-
CITATION2 datasets respectively for evaluation. We evaluate the effectivness
of our Flashlight algorithm by checking whether it can find the top scoring
neighbors for every source node. We set the number of Flashlight iterations as
10 and the number of retrieved neighbors per iteration as 50. We present the
Recall$@k$ for $k$ from 1 to 500 averaged over all the source nodes in Fig. 3.
The “oracle” curve represents the performance of a optimum searcher, of which
the retrieved top $k$ neighbors are exactly the top $k$ scoring neighbors of
HadamardMLP.

When $k=100$, the 100 neighbors retrieved by our Flashlight can cover more
than 80% ground-truth neighbors. When $k\geq 200$, the recall reaches 100%. As
a comparison, if we randomly sample the candidate neighbors for retrievals,
the Recall$@k$ grows linearly with $k$ and is less than $1\times 10^{-4}$ for
$k=100$ on the OGBL-CITATION2 dataset. The curves of Flashlight is close the
optimum curve of the “oracle”. These results demonstrate the highly
effectiveness of our Flashlight on finding the top scoring neighbors.

Given the large OGBL-Citation2 dataset and smaller DDI dataset, our Flashlight
exhibits similar Recall$@k$ performance given different numbers $k$ of
retrieved neighbors. This implies that our Flashlight can accurately find the
top scoring neighbors for both small and large graphs.

###  6.5 Inference Efficiency of Link Prediction with Our Flashlight Algorithm

We use the throughputs to evaluate the inference speed of neighbor retrieval
of different methods. The throughput is defined as how many source nodes that
a method can serve to retrieve the top 100 scoring neighbors per second.
Except for the LP models that follow the encoder and decoder architectures,
e.g., GraphSAGE [12], GCN [5], and PLNLP [6], there are some subgraph based LP
models, e.g., SUREL [7] and SEAL [58]. The common issue of the subgraph based
models is the poor efficiency: they have to crop a seperate subgraph for every
node pair to calculate the LP probability on the node pair. In this sense, the
node embeddings cannot be shared on the LP calculation for different node
pairs. This leads to the much lower inference speed of the subgraph based LP
models than the encoder-decoder LP models. We compare the inference effeciency
of different methods on the OGBL-CITATION2 dataset in Fig. 4, where we present
the inference speed of different methods when achieving the 100% recall$@100$
for the top 100 scoring neighbors.

Figure 4: The inference speed of different LP methods on the OGBL-CITATION2
dataset. The y-axis (througputs) is in the logarithmic scale.

Figure 5: The tradeoff between the inference speed (y-axis) and the
effectiveness of finding the top scoring neighbors (x-axis) on the OGBL-
CITATION2 (left) and OGBL-PPA (right) datasets.

We observe that our Flashlight significantly accelerate the inference speed of
LP models GraphSAGE [12], GCN [5], and PLNLP [6] with the HadamardMLP decoders
by more than 100 times. This gap will be even larger for the datasets of
larger scales, because the inference with our Flashlight holds the logarithmic
time complexity while the HadamardMLP decoders holds the linear complexity.
Note that the y-axis is in logoratimic scale. The subgraph based methods SUREL
[7] and SEAL [58] hold the inference speed of throuputs lower than 1$\times
10^{-2}$ and 1$\times 10^{-3}$ respectively, which is not applicable to the
practical services that require the low latency of milliseconds.

Taking a further step, we comprehensively evaluate the tradeoff between the
inference speed and the effectiveness of finding the top scoring neighbors.
Taking GraphSAGE as the encoder, we present the tradeoff curves between the
throughputs and the Recall$@100$ on the OGBL-CITATION2 and OGBL-PPI datasets
in Fig. 5. In comparison with our Flashlight, we take the HadamardMLP decoder
with the Random Sampling as the baseline for comparison. For example, on the
OGBL-CITATION2 dataset, when achieving the Recall@100 as more than 80%, the
HadamardMLP with our Flashlight can serve more than 200 source nodes per
second, while the HadamardMLP with the random sampling can only serve less
than 1 node per second. Overall, our Flashlight achieves much better inference
speed and effectiveness tradeoff than the HadamardMLP with random sampling.

##  7 Conclusion

Our theoretical and empirical analysis suggests that the HadamardMLP decoders
are a better default choice than the Dot Product in terms of LP effectiveness.
Because there does not exist a well-developed sublinear complexity top scoring
neighbor searching algorithm for HadamardMLP, the HadamardMLP decoders are not
scalable and cannot support the fast inference on large graphs. To resolve
this issue, we propose the Flashlight algorithm to accelerate the inference of
LP models with HadamardMLP decoders. Flashlight progressively operates the
well-studied MIPS techniques for a few iterations. We adaptively adjust the
query embeddings at every iteration to find more high scoring neighbors.
Empirical results show that our Flashlight accelrates the inference of LP
models by more than 100 times on the large OGBL-CITATION2 graph. Overall, our
work paves the way for the use of strong LP decoders in practical settings by
greatly accelerating their inference.

## References

  * Lü and Zhou [2011] Linyuan Lü and Tao Zhou.  Link prediction in complex networks: A survey.  _Physica A: statistical mechanics and its applications_ , 390(6):1150–1170, 2011.
  * Martínez et al. [2016] Víctor Martínez, Fernando Berzal, and Juan-Carlos Cubero.  A survey of link prediction in complex networks.  _ACM computing surveys (CSUR)_ , 49(4):1–33, 2016\.
  * Adamic and Adar [2003] Lada A Adamic and Eytan Adar.  Friends and neighbors on the web.  _Social networks_ , 25(3):211–230, 2003.
  * Koren et al. [2009] Yehuda Koren, Robert Bell, and Chris Volinsky.  Matrix factorization techniques for recommender systems.  _Computer_ , 42(8):30–37, 2009.
  * Kipf and Welling [2016a] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_ , 2016a.
  * Wang et al. [2021] Zhitao Wang, Yong Zhou, Litao Hong, Yuanhang Zou, and Hanjing Su.  Pairwise learning for neural link prediction.  _arXiv preprint arXiv:2112.02936_ , 2021.
  * Yin et al. [2022] Haoteng Yin, Muhan Zhang, Yanbang Wang, Jianguo Wang, and Pan Li.  Algorithm and system co-design for efficient subgraph-based graph representation learning.  _arXiv preprint arXiv:2202.13538_ , 2022.
  * Sun and Wu [2020] Chuxiong Sun and Guoshi Wu.  Adaptive graph diffusion networks with hop-wise attention.  _arXiv preprint arXiv:2012.15024_ , 2020.
  * Zhou et al. [2009] Tao Zhou, Linyuan Lü, and Yi-Cheng Zhang.  Predicting missing links via local information.  _The European Physical Journal B_ , 71(4):623–630, 2009.
  * Rendle et al. [2020] Steffen Rendle, Walid Krichene, Li Zhang, and John Anderson.  Neural collaborative filtering vs. matrix factorization revisited.  In _Fourteenth ACM conference on recommender systems_ , pages 240–248, 2020.
  * Liu et al. [2019] Rui Liu, Tianyi Wu, and Barzan Mozafari.  A bandit approach to maximum inner product search.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pages 4376–4383, 2019.
  * Hamilton et al. [2017] Will Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  _Advances in neural information processing systems_ , 30, 2017.
  * Kipf and Welling [2016b] Thomas N Kipf and Max Welling.  Variational graph auto-encoders.  _arXiv preprint arXiv:1611.07308_ , 2016b.
  * Ying et al. [2018] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec.  Graph convolutional neural networks for web-scale recommender systems.  In _Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining_, pages 974–983, 2018.
  * Cybenko [1989] George Cybenko.  Approximation by superpositions of a sigmoidal function.  _Mathematics of control, signals and systems_ , 2(4):303–314, 1989.
  * Hu et al. [2021] Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec.  Ogb-lsc: A large-scale challenge for machine learning on graphs.  _arXiv preprint arXiv:2103.09430_ , 2021.
  * Dai et al. [2020] Xinyan Dai, Xiao Yan, Kelvin KW Ng, Jiu Liu, and James Cheng.  Norm-explicit quantization: Improving vector quantization for maximum inner product search.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 51–58, 2020.
  * Guo et al. [2020] Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar.  Accelerating large-scale inference with anisotropic vector quantization.  In _International Conference on Machine Learning_ , pages 3887–3896. PMLR, 2020.
  * Tan et al. [2020] Shulong Tan, Zhixin Zhou, Zhaozhuo Xu, and Ping Li.  Fast item ranking under neural network based measures.  In _Proceedings of the 13th International Conference on Web Search and Data Mining_ , pages 591–599, 2020.
  * Chen et al. [2022] Rihan Chen, Bin Liu, Han Zhu, Yaoxuan Wang, Qi Li, Buting Ma, Qingbo Hua, Jun Jiang, Yunlong Xu, Hongbo Deng, et al.  Approximate nearest neighbor search under neural similarity metric for large-scale recommendation.  _arXiv preprint arXiv:2202.10226_ , 2022.
  * Chowdhury [2010] Gobinda G Chowdhury.  _Introduction to modern information retrieval_.  Facet publishing, 2010.
  * Liben-Nowell and Kleinberg [2003] David Liben-Nowell and Jon Kleinberg.  The link prediction problem for social networks.  In _Proceedings of the twelfth international conference on Information and knowledge management_ , pages 556–559, 2003.
  * Jeh and Widom [2002] Glen Jeh and Jennifer Widom.  Simrank: a measure of structural-context similarity.  In _Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 538–543, 2002.
  * Menon and Elkan [2011] Aditya Krishna Menon and Charles Elkan.  Link prediction via matrix factorization.  In _Joint european conference on machine learning and knowledge discovery in databases_ , pages 437–452. Springer, 2011.
  * Perozzi et al. [2014] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena.  Deepwalk: Online learning of social representations.  In _Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 701–710, 2014.
  * Tang et al. [2015] Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei.  Line: Large-scale information network embedding.  In _Proceedings of the 24th international conference on world wide web_ , pages 1067–1077, 2015.
  * Grover and Leskovec [2016] Aditya Grover and Jure Leskovec.  node2vec: Scalable feature learning for networks.  In _Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 855–864, 2016.
  * Wang et al. [2017] Zhitao Wang, Chengyao Chen, and Wenjie Li.  Predictive network representation learning for link prediction.  In _Proceedings of the 40th international ACM SIGIR conference on research and development in information retrieval_ , pages 969–972, 2017.
  * Zhang and Chen [2017] Muhan Zhang and Yixin Chen.  Weisfeiler-lehman neural machine for link prediction.  In _Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining_ , pages 575–583, 2017.
  * Zhang and Chen [2018] Muhan Zhang and Yixin Chen.  Link prediction based on graph neural networks.  _Advances in neural information processing systems_ , 31, 2018.
  * Zhang et al. [2018] Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen.  An end-to-end deep learning architecture for graph classification.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 32, 2018.
  * Cohen and Lewis [1999] Edith Cohen and David D Lewis.  Approximating matrix multiplication for pattern recognition tasks.  _Journal of Algorithms_ , 30(2):211–252, 1999\.
  * Yu et al. [2017] Hsiang-Fu Yu, Cho-Jui Hsieh, Qi Lei, and Inderjit S Dhillon.  A greedy approach for budgeted maximum inner product search.  _Advances in neural information processing systems_ , 30, 2017.
  * Huang et al. [2018] Qiang Huang, Guihong Ma, Jianlin Feng, Qiong Fang, and Anthony KH Tung.  Accurate and fast asymmetric locality-sensitive hashing scheme for maximum inner product search.  In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pages 1561–1570, 2018.
  * Neyshabur and Srebro [2015] Behnam Neyshabur and Nathan Srebro.  On symmetric and asymmetric lshs for inner product search.  In _International Conference on Machine Learning_ , pages 1926–1934. PMLR, 2015.
  * Shrivastava and Li [2014] Anshumali Shrivastava and Ping Li.  Asymmetric lsh (alsh) for sublinear time maximum inner product search (mips).  _Advances in neural information processing systems_ , 27, 2014.
  * Yan et al. [2018] Xiao Yan, Jinfeng Li, Xinyan Dai, Hongzhi Chen, and James Cheng.  Norm-ranging lsh for maximum inner product search.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Liu et al. [2020] Jie Liu, Xiao Yan, Xinyan Dai, Zhirong Li, James Cheng, and Ming-Chang Yang.  Understanding and improving proximity graph based maximum inner product search.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 139–146, 2020.
  * Morozov and Babenko [2018] Stanislav Morozov and Artem Babenko.  Non-metric similarity graphs for maximum inner product search.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Zhou et al. [2019] Zhixin Zhou, Shulong Tan, Zhaozhuo Xu, and Ping Li.  Möbius transformation for fast inner product search on graph.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Aoyama et al. [2011] Kazuo Aoyama, Kazumi Saito, Hiroshi Sawada, and Naonori Ueda.  Fast approximate similarity search based on degree-reduced neighborhood graphs.  In _Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 1055–1063, 2011.
  * Arora et al. [2018] Akhil Arora, Sakshi Sinha, Piyush Kumar, and Arnab Bhattacharya.  Hd-index: Pushing the scalability-accuracy boundary for approximate knn search in high-dimensional spaces.  _arXiv preprint arXiv:1804.06829_ , 2018.
  * Fu et al. [2017] Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai.  Fast approximate nearest neighbor search with the navigating spreading-out graph.  _arXiv preprint arXiv:1707.00143_ , 2017.
  * Malkov and Yashunin [2018] Yu A Malkov and Dmitry A Yashunin.  Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs.  _IEEE transactions on pattern analysis and machine intelligence_ , 42(4):824–836, 2018.
  * Riegger [2010] Philipp M Riegger.  Literature survey on nearest neighbor search and search in graphs.  2010\.
  * Zhou et al. [2013] Wenhui Zhou, Chunfeng Yuan, Rong Gu, and Yihua Huang.  Large scale nearest neighbors search based on neighborhood graph.  In _2013 International Conference on Advanced Cloud and Big Data_ , pages 181–186. IEEE, 2013.
  * Flickner et al. [1995] Myron Flickner, Harpreet Sawhney, Wayne Niblack, Jonathan Ashley, Qian Huang, Byron Dom, Monika Gorkani, Jim Hafner, Denis Lee, Dragutin Petkovic, et al.  Query by image and video content: The qbic system.  _computer_ , 28(9):23–32, 1995.
  * Zhu et al. [2019] Chun Jiang Zhu, Tan Zhu, Haining Li, Jinbo Bi, and Minghu Song.  Accelerating large-scale molecular similarity search through exploiting high performance computing.  In _2019 IEEE International Conference on Bioinformatics and Biomedicine (BIBM)_ , pages 330–333. IEEE, 2019.
  * Cover and Hart [1967] Thomas Cover and Peter Hart.  Nearest neighbor pattern classification.  _IEEE transactions on information theory_ , 13(1):21–27, 1967.
  * Kosuge and Oshima [2019] Atsutake Kosuge and Takashi Oshima.  An object-pose estimation acceleration technique for picking robot applications by using graph-reusing k-nn search.  In _2019 First International Conference on Graph Computing (GC)_ , pages 68–74. IEEE, 2019.
  * Huang et al. [2017] Qiang Huang, Jianlin Feng, Qiong Fang, Wilfred Ng, and Wei Wang.  Query-aware locality-sensitive hashing scheme for $l\\_p$ norm.  _The VLDB Journal_ , 26(5):683–708, 2017.
  * Iwasaki [2016] Masajiro Iwasaki.  Pruned bi-directed k-nearest neighbor graph for proximity search.  In _International Conference on Similarity Search and Applications_ , pages 20–33. Springer, 2016.
  * Cao et al. [2017] Yuan Cao, Heng Qi, Wenrui Zhou, Jien Kato, Keqiu Li, Xiulong Liu, and Jie Gui.  Binary hashing for approximate nearest neighbor search on big data: A survey.  _IEEE Access_ , 6:2039–2054, 2017.
  * Cost and Salzberg [1993] Scott Cost and Steven Salzberg.  A weighted nearest neighbor algorithm for learning with symbolic features.  _Machine learning_ , 10(1):57–78, 1993.
  * Meng et al. [2020] Yitong Meng, Xinyan Dai, Xiao Yan, James Cheng, Weiwen Liu, Jun Guo, Benben Liao, and Guangyong Chen.  Pmd: An optimal transportation-based user distance for recommender systems.  In _European Conference on Information Retrieval_ , pages 272–280. Springer, 2020.
  * Sarwar et al. [2001] Badrul Sarwar, George Karypis, Joseph Konstan, and John Riedl.  Item-based collaborative filtering recommendation algorithms.  In _Proceedings of the 10th international conference on World Wide Web_ , pages 285–295, 2001.
  * Hu et al. [2020] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec.  Open graph benchmark: Datasets for machine learning on graphs.  _Advances in neural information processing systems_ , 33:22118–22133, 2020.
  * Zhang et al. [2021] Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin.  Labeling trick: A theory of using graph neural networks for multi-node representation learning.  _Advances in Neural Information Processing Systems_ , 34:9061–9073, 2021.
  * Allen-Zhu et al. [2019] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song.  A convergence theory for deep learning via over-parameterization.  In _International Conference on Machine Learning_ , pages 242–252. PMLR, 2019.
  * Andoni et al. [2014] Alexandr Andoni, Rina Panigrahy, Gregory Valiant, and Li Zhang.  Learning polynomials with neural networks.  In _International conference on machine learning_ , pages 1908–1916. PMLR, 2014.

##  Appendix A Learning a Dot Product decoder with a HadamardMLP decoder is
Easy

Before we have discussed the limitations of the Dot Product decoder. An
interesting questions is whether the HadamardMLP decoder can replace the Dot
Product decoder by approximating it. If the MLP decoder can learn a dot
product easily, it is safe to use MLP decoder instead of the dot product ones
in most cases. There are similar problems actively studied in machine
learning. Existing work imply that the difficulty scales polynomial with
dimensionality $d$ and $1/\epsilon$ in theory [59, 60, 10]. This motivates us
to investigate the question empirically.

Figure 6: A MLP decoder can learn a Dot Product decoder well with enough
training data. The left and right figures shows the MSE differences (y-axis)
per epoch (x-axis) between the outputs of dot product and the MLP decoders
given different training sizes with the input embedding dimenionality as
$d=64$ and $d=128$ respectively. The naive output denotes the outputs of
zeros.  Figure 7: Test inverse MSE differences between the outputs of Dot
Product and MLP decoders after convergence (y-axis) versus the training set
size (x-axis).

We set up a synthetic learning task where given two embeddings
$\mathbf{x}_{i},\mathbf{x}_{j}\in\mathbb{R}^{d}$ and a label
$\mathbf{x}_{i}\mathbin{\vbox{\hbox{{$\bullet$}}}}\mathbf{x}_{j}$, we want to
obtain a MLP function that approximates the
$\mathbf{x}_{i}\mathbin{\vbox{\hbox{{$\bullet$}}}}\mathbf{x}_{j}$ with the
inputs $\mathbf{x}_{i},\mathbf{x}_{j}\in\mathbb{R}^{d}$. For this experiment,
we create the datasets including the embedding matrix as
$\mathbf{E}\in\mathbb{R}^{10^{6}\times d}$. We draw every row in $\mathbf{E}$
from $\mathcal{N}(0,\mathbf{I})$ independently. Then, we uniformly sample
(without replacement) $10^{4}$ and $S$ embedding pair combinations from
$\mathbf{E}$ to form the test and training sets (no overlap) respectively.

We train the MLP on the training and evalute it on the test set. For the
architecture of the MLP, we keep it simple: we follow the existing work [6, 8]
to set the number of layers as 2 and the number of hidden units as same as the
input embeddings: $d$. For the optimizer, we also folow the existing work [6,
8] to choose the Adam optimizer.

As for evaluation metrics, we compute the MSE (Mean Squared Error) differences
between the predicted score of the MLP and the dot product decoders. We
measure the MSE of a naive model that predicts always 0 (the average rating).
Every experiment is repeated 5 times and we report the mean.

Fig. 6 shows the approximation errors on the MLP per epoch given different
number of training pairs and dimensions. The figure suggests that an MLP can
easily approximate the dot product with enough training data. Consistent with
the theory, the number of samples needed scales polynominally with the
increasing dimensions and reduced errors. Ancedotally, we observe the number
of needed training samples is about $\mathcal{O}(d^{\alpha}/\epsilon^{\beta})$
for $\alpha\approx 2,\beta\ll 1$ (see Fig. 7). In all cases, the MSE errors of
the MLP decoder are negligible compared with the naive output.

This experiment shows that an MLP can easily approximate the dot product with
enough training data. We hope this can explain, at least partially, why the
MLP decoder generally performs better than the dot product.

Our conclusion seems to be distinct to to the existing work [10], which claims
that the ConcatMLP is hard to learn a Dot Product. Actually, our conclusion is
not conflicted with that in [10]. This ConcatMLP decoder processes the
concatenation of the paired embeddings instead of the Hadamard product of the
paired embeddings as the HadamardMLP. The HadamardMLP holds the inductive bias
similar to the Dot Product, which makes the former easily learns the latter.
Actually, we show that a simple two-layer MLP with only two hidden units is
equivalent to the Dot Product with specific weights. We assign the first layer
weights for two hidden units as $\mathbf{1}$ and $-\mathbf{1}$ and the second
layer weights as ones. Then, we have its output as:

$s_{ij}=\phi^{\mathrm{MLP}}(\mathbf{x_{i}},\mathbf{x}_{j})=\mathrm{ReLU}(\mathbf{1}\mathbin{\vbox{\hbox{{$\bullet$}}}}(\mathbf{x}_{i}\odot\mathbf{x}_{j}))+\mathrm{ReLU}(-\mathbf{1}\mathbin{\vbox{\hbox{{$\bullet$}}}}(\mathbf{x}_{i}\odot\mathbf{x}_{j}))=\mathbf{1}\mathbin{\vbox{\hbox{{$\bullet$}}}}(\mathbf{x}_{i}\odot\mathbf{x}_{j})=\mathbf{x}_{i}\mathbin{\vbox{\hbox{{$\bullet$}}}}\mathbf{x}_{j},$
(14)

which is equivalent to the Dot Product decoder. From this result, we find that
any MLP decoder with the careful initialization is equivalent to the Dot
Product decoder and thus can learn the Dot Product easily.


11institutetext: Philippe Di Francesco 22institutetext: University of
Illinois, Mathematics MC-382 Urbana IL 61821 USA and IPhT CEA, Université
Paris-Saclay 91191 Gif-sur-Yvette France, 22email<EMAIL_ADDRESS>33institutetext: Rinat Kedem 44institutetext: University of Illinois,
Mathematics MC-382 Urbana IL 61821 USA, 44email<EMAIL_ADDRESS>
# Duality and Macdonald difference operators

Philippe Di Francesco and Rinat Kedem

###### Abstract

This note summarizes certain properties common to Macdonald, Koornwinder and
Arthamonov-Shakirov $q$-difference operators, relating to the duality or bi-
spectrality properties of their eigenfunctions. This results in Pieri
operators which, in the $q$-Whittaker limit, are relativistic difference Toda
type Hamiltonians which have a related quantum cluster algebra structure known
as the quantum Q-system. The genus-2 result explained here is new.

##  1 Introduction

This contribution puts together certain results associated with the duality or
bi-spectrality property which is common to the (genus 1) spherical double
affine Hecke algebras (sDAHAs) of classical types and the recently introduced
genus-2 DAHA AS (19). The functional representation of the spherical DAHA
contains a set of distinguished generators which are the (generalized)
Macdonald/Koornwinder $q$-difference operators. In genus 1, Macdonald
operators are naturally related to the affine root system of $A_{N}^{(1)}$,
while Koornwinder’s operators are related to $BC_{N}$ type affine root
systems. In genus-2, only the rank-1 DAHA is defined AS (19), and we propose a
candidate which takes the place of the affine root system in defining the
difference operators and duality. The duality relates the Macdonald or
Koornwinder $q$-difference operators with the Pieri rule operators, which are
difference operators in the “weight variables” $\lambda$.

In the $q$-Whittaker limit when $t\to\infty$, we have shown DFK (21) that in
the genus-1 case, the Dehn twists of the distinguished generators of the
sDAHAs are $A$-type cluster variables in the quantum Q-system cluster algebras
associated to each root system. The Pieri operators are interpreted as Toda-
type Hamiltonians, conserved quantities of the discrete evolution given by
appropriate mutation sequences. We show below that the genus-2 theory
degenerates in this limit into a product of three genus 1 $A_{1}^{(1)}$-type
quantum Toda theories.

We also discuss the role of the Universal solutions (c.f. basic Harish-Chandra
series Sto (14)), in terms of which the duality takes a particularly simple
form, both in the sDAHA setting and in the $q$-Whittaker limit.

Acknowledgments. We thank the organizers of the program “Geometric and
Representation-Theoretic Aspects of Quantum Integrability,” Simons Center for
Geometry and Physics in Stony Brook, and M. Shapiro for discussions about
genus-2 DAHA. RK thanks the Institut de Physique Théorique, Saclay for
hospitality. Research supported by NSF DMS grant 18-02044 and the Morris and
Gertrude Fine endowment.

##  2 Duality for type $A$ Macdonald theory

Macdonald theory is associated with $A_{N-1}^{(1)}$ or affine
$\mathfrak{sl}_{N}$. The finite-dimensional algebra $\mathfrak{sl}_{N}$ has
simple roots $\Pi=\\{\alpha_{i}=\epsilon_{i}-\epsilon_{i+1},i=1,...,N-1\\}$
and positive roots $R_{+}=\\{\epsilon_{i}-\epsilon_{j}:1\leq i<j\leq
N\\}=-R_{-}$. The fundamental weights are
$\omega_{i}=\epsilon_{1}+\cdots+\epsilon_{i}$. Let $Q_{+}$ denote the non-
negative integer cone generated by $\Pi$. The Weyl group $W=S_{N}$ acts by
permutation of the basis vectors $\epsilon_{i}$ of $\mathbb{C}^{N}$. With $q$
a generic complex number with $|q|<1$, the quantum torus or $q$-Weyl algebra
$\mathbb{T}_{X}$ is generated by $N$ commuting variables $x_{1},...,x_{N}$ and
and $N$ commuting momenta $\Gamma_{1},...,\Gamma_{N}$, subject to the
relations

$\Gamma_{i}\,x_{j}=q^{\delta_{i,j}}\,x_{j}\,\Gamma_{i}.$ (1)

In the functional representation, $x_{i}$ acts on functions of
$\mathbf{x}=(x_{1},...,x_{N})$ by multiplication and $\Gamma_{i}$ by shift of
$x_{i}$: $\Gamma_{i}f(\mathbf{x})=f(x_{1},...,qx_{i},...,x_{N})$, i.e.
$\Gamma_{i}=q^{x_{i}\partial_{x_{i}}}$.

###  2.1 Macdonald operators and eigenfunctions

Let $\vartheta(x)$ the Jacobi theta function

$\displaystyle\vartheta(x)=\frac{1}{2i}q^{1/8}x^{-\frac{1}{2}}(q;q)_{\infty}(x;q)_{\infty}(qx^{-1};q)_{\infty},$

so that

$\frac{\vartheta(x;q)}{\vartheta(tx;q)}=t^{\frac{1}{2}}\prod_{n\geq
0}\frac{1-q^{n}x}{1-tq^{n}x}\prod_{n>0}\frac{1-q^{n}x^{-1}}{1-t^{-1}q^{n}x^{-1}}.$

Define the function

$\Theta(\mathbf{x})=t^{-{N\choose 2}}\prod_{\alpha\in
R_{+}}\frac{\vartheta(\mathbf{x}^{\alpha})}{\vartheta(t\mathbf{x}^{\alpha})}=t^{-{N\choose
2}}\Delta_{+}(\mathbf{x})\Delta(\mathbf{x}),$

where $\mathbf{x}^{\epsilon_{i}}=x_{i}$, and

$\Delta_{+}(\mathbf{x})=\prod_{n\geq 0}\prod_{\alpha\in
R_{+}}\frac{1-q^{n}\mathbf{x}^{\alpha}}{1-tq^{n}\mathbf{x}^{\alpha}},\qquad\Delta(\mathbf{x})=\prod_{n>0}\prod_{\alpha\in
R_{-}}\frac{1-q^{n}\mathbf{x}^{\alpha}}{1-t^{-1}q^{n}\mathbf{x}^{\alpha}}.$

The modular property of the theta function $qx\vartheta(qx)=\vartheta(x)$
implies that

$\Theta(\mathbf{x})\Gamma_{\omega_{a}}\Theta(\mathbf{x})^{-1}=t^{-a(N-a)}\Gamma_{\omega_{a}},$

where $\Gamma_{\omega_{a}}=\Gamma_{1}\cdots\Gamma_{a}$. Therefore,

$\Delta_{+}(\mathbf{x})^{-1}\Gamma_{\omega_{a}}\Delta_{+}(\mathbf{x})=t^{a(n-a)}\Delta(\mathbf{x})\Gamma_{\omega_{a}}\Delta(\mathbf{x})^{-1}=\prod_{i=1}^{a}\prod_{j=r+1}^{N}\frac{tx_{i}-x_{j}}{x_{i}-x_{j}}\Gamma_{\omega_{a}}=A_{a}(\mathbf{x})\Gamma_{\omega_{a}}$

###### Remark 1

The product $\Delta_{+}(\mathbf{x})$ is the one introduced by Macdonald, see
e.g. Mac (01), and the discussion above shows that it can be interchanged with
$\Delta(\mathbf{x})$ up to a power of $t$. The choice of $\Delta(\mathbf{x})$
is adapted to taking the $t\to\infty$ $q$-Whittaker limit.

The Macdonald commuting difference operators are Mac (95):

$\mathcal{D}_{a}(\mathbf{x})={\rm
Sym}(A_{a}\Gamma_{\omega_{a}})=\sum_{I\subset[1,N]\atop|I|=a}\prod_{i\in
I,j\not\in I}\frac{tx_{i}-x_{j}}{x_{i}-x_{j}}\prod_{i\in I}\Gamma_{i}$ (2)

where $\rm Sym$ stands for symmetrization over the Weyl group $S_{N}$ acting
on $x_{i}$. The Macdonald polynomials $P_{\lambda}(\mathbf{x})$ are defined as
their common monic eigenfunctions:

$\mathcal{D}_{a}(\mathbf{x})\,P_{\lambda}(\mathbf{x})=t^{-{a\choose
2}}e_{a}(\mathbf{s})\,P_{\lambda}(\mathbf{x}),\qquad
P_{\lambda}(\mathbf{x})=\mathbf{x}^{\lambda}(1+O(\\{\mathbf{x}^{-\alpha}\\}_{\alpha\in
Q_{+}})),$ (3)

indexed by integer partitions
$\lambda=(\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{N}\geq 0)$. Here,
$\mathbf{s}=q^{\lambda}\,t^{\rho}=(s_{1},s_{2},...,s_{N})$,
$s_{i}=q^{\lambda_{i}}t^{N-i}$, with $\rho$ the Weyl vector, while
$e_{a}(\mathbf{s})$ is the $a$th elementary symmetric function in
$s_{1},...,s_{N}$.

###  2.2 Duality and Pieri rules

The Macdonald polynomials have a remarkable duality or bi-spectrality property
under the exchange of the variables $\mathbf{x}$ and $\mathbf{s}$. When the
variables are specialized as $\mathbf{x}=q^{\mu}\,t^{\rho}$ and
$\mathbf{s}=q^{\lambda}\,t^{\rho}$ where $\mu,\lambda$ are integer partitions,
the duality property is due to Macdonald Mac (95):

$\frac{P_{\lambda}(t^{\rho}q^{\mu})}{P_{\lambda}(t^{\rho})}=\frac{P_{\mu}(t^{\rho}q^{\lambda})}{P_{\mu}(t^{\rho})}.$
(4)

Moreover, the denominators $P_{\lambda}(t^{\rho})$ can be expressed in terms
of $\Delta(\mathbf{x})$ (c.f. Mac (95) (6.11)):

$P_{\lambda}(t^{\rho})=t^{(\rho,\lambda)}\frac{\Delta(t^{\rho})}{\Delta(t^{\rho}q^{\lambda})}$
(5)

The duality property can be generalized to the Universal solution NS (12) of
the Macdonald eigenvalue equations (3), also called asymptotically-free
Harish-Chandra series Sto (14). The polynomials $P_{\lambda}(\mathbf{x})$ are
replaced by formal series solutions
$P(\mathbf{x};\mathbf{s})=q^{(\lambda,\mu)}\sum_{\alpha\in
Q_{+}}c_{\alpha}(\mathbf{s})\mathbf{x}^{-\alpha}$ where $\lambda$ and $\mu$
are now generic complex $N$-tuples, with the normalization
$c_{0}(\mathbf{s})=1$. The series is convergent in the domain
$|\mathbf{x}^{-\alpha_{i}}=x_{i+1}/x_{i}|<1$ and truncates to a finite sum
when $\lambda$ is specialized to an integer partition, recovering

$P(\mathbf{x};\mathbf{s}=q^{\lambda}t^{\rho})\Big{|}_{\hbox{$\lambda$ integer
partition}}=t^{-(\rho,\lambda)}\,P_{\lambda}(\mathbf{x}),$ (6)

by using the relation
$\mathbf{x}^{\lambda}=q^{(\lambda,\mu)}\,t^{(\rho,\lambda)}$. The duality
relation (4) can be generalized to the universal solution with generic
$\mathbf{x},\mathbf{s}$ DFK (21):

$\Delta(\mathbf{s})\,P(\mathbf{x};\mathbf{s})=\Delta(\mathbf{x})\,P(\mathbf{s};\mathbf{x}).$
(7)

The Pieri rules for Macdonald polynomials follow from the duality property.
These express the result of multiplication of $P_{\lambda}(\mathbf{x})$ by the
elementary symmetric functions $e_{a}(\mathbf{x})$:

$e_{a}(\mathbf{x})\,P_{\lambda}(\mathbf{x})=\mathcal{H}_{a}(\mathbf{s})\,P_{\lambda}(\mathbf{x})$
(8)

Here $\mathcal{H}_{a}(\mathbf{s})$ is a difference operator acting on
functions of $\mathbf{s}=(s_{1},...,s_{N})$:

$\mathcal{H}_{a}(\mathbf{s})=t^{a\choose 2}{\rm
Ad}_{\Delta(\mathbf{s})^{-1}\,t^{(\rho,\lambda)}}\mathcal{D}_{a}(\mathbf{s}).$
(9)

This follows from the eigenvalue equations for the universal solutions and
(7):

$\Delta(\mathbf{x})^{-1}\mathcal{D}_{a}(\mathbf{x})\,\Delta(\mathbf{s})P(\mathbf{x};\mathbf{s})=\Delta(\mathbf{x})^{-1}\,\mathcal{D}_{a}(\mathbf{x})\,\Delta(\mathbf{x})\,P(\mathbf{s};\mathbf{x})=t^{-{a\choose
2}}e_{a}(\mathbf{s})\,P(\mathbf{s};\mathbf{x}),$

after interchanging the names of variables
$\mathbf{x}\leftrightarrow\mathbf{s}$, then specializing to integer partitions
$\lambda$ and using (6). Explicitly, Equation (9) is Mac (95)

$\mathcal{H}_{a}(\mathbf{s})=\sum_{I\subset[1,N]\atop|I|=a}\prod_{i\in I,\
j\not\in I\atop
j<i}\frac{t^{i-j-1}\Lambda_{j}-\Lambda_{i}}{t^{i-j}\Lambda_{j}-\Lambda_{i}}\
\frac{t^{i-j+1}\Lambda_{j}-q\Lambda_{i}}{t^{i-j}\Lambda_{j}-q\Lambda_{i}}\,\prod_{i\in
I}T_{i},$

in terms of the quantum torus $\mathbb{T}_{\Lambda}$ variables
$\Lambda=q^{\lambda}$ and $T_{i}=q^{\lambda_{i}\partial_{\lambda_{i}}}$, which
generate a second $q$-Weyl algebra with
$T_{i}\Lambda_{j}=q^{\delta_{ij}}\Lambda_{j}T_{i}$.

###  2.3 Dehn twist acting on sDAHA

The operators (2) are generators in the functional representation of the
sDAHA, i.e. the elementary symmetric functions of the generators $Y_{i}$ of
DAHA. This has a natural torus modular group
$\mathsf{SL}_{2}(\mathbb{Z})$-action generated by the two (a and b-cycle) Dehn
twists. The Dehn twist $\tau_{+}$, corresponding to $\begin{pmatrix}1&1\\\
0&1\end{pmatrix}$ in the defining representation, acts on the functional
representation via the adjoint action of Cherednik’s Gaussian
$\gamma(\mathbf{x})$ Che (05):

$\gamma(\mathbf{x})=\exp\left\\{\frac{\sum_{i=1}^{N}(\log x_{i})^{2}}{2\log
q}\right\\}.$ (10)

The action on Macdonald operators allows to define a discrete time evolution
for $n\in\mathbb{Z}$:

$\mathcal{D}_{a,n}(\mathbf{x})=q^{-na/2}\,{\rm
Ad}_{\gamma^{-n}}(\mathcal{D}_{a}(\mathbf{x}))=\sum_{I\subset[1,N]\atop|I|=a}\prod_{i\in
I,j\not\in I}\frac{tx_{i}-x_{j}}{x_{i}-x_{j}}\prod_{i\in
I}x_{i}^{n}\,\prod_{i\in I}\Gamma_{i}$ (11)

In the limit $N\to\infty$ these can be identified as elements in the quantum
toroidal algebra of ${\mathfrak{g}l}_{1}$ DFK (19).

##  3 Duality for Koornwinder theory

The root system underlying Koornwinder theory is the unreduced $BC_{N}$
system:

$R_{+}=\left\\{\epsilon_{i}\pm\epsilon_{j}(1\leq i\leq j\leq
N);\epsilon_{i},2\epsilon_{i}(1\leq i\leq N)\right\\}.$

We denote by $Q_{+}$ the non-negative integer cone generated by the finite
positive roots of type $C_{N}$. The Weyl group $W\simeq\mathbb{Z}_{2}^{\times
N}\rtimes S_{N}$ acts on the variables $\mathbf{x}=(x_{1},...,x_{N})$ by
permutations and inversion of variables. The Weyl-invariant elementary
symmetric functions are denoted by
$\hat{e}_{a}(\mathbf{x})=e_{a}(x_{1},x_{1}^{-1},...,x_{N},x_{N}^{-1})$.

###  3.1 Generalized Koornwinder operators

The theory is parameterized by six non-zero complex numbers $a,b,c,d,q,t$. Let

$\sigma=\sqrt{\frac{abcd}{q}},\quad t^{\rho}=(\sigma t^{N-i})_{i=1}^{N}.$ (12)

The following function takes the place of $\Delta$ in type $A$:

$\Delta^{(a,b,c,d)}(x)=\prod_{i=1}^{N}\prod_{\alpha\in\\{a,b,c,d\\}}\frac{(\frac{q}{x_{i}^{2}};q)_{\infty}}{(\frac{q}{\alpha
x_{i}};q)_{\infty}}\prod_{1\leq i<j\leq N}\prod_{\epsilon=\pm
1}\frac{(\frac{qx_{j}^{\epsilon}}{x_{i}};q)_{\infty}}{(\frac{qx_{j}^{\epsilon}}{tx_{i}};q)_{\infty}}.$
(13)

The Koornwinder difference operator111As in DFK (21), we add a constant to the
original definition of Koo (92), which suits our choice of eigenvalues. is
defined as

$\mathcal{D}_{1}^{(a,b,c,d)}(\mathbf{x})=\sigma^{2}\,{\rm
Sym}\left\\{\Delta^{(a,b,c,d)}(\mathbf{x})\Gamma_{1}\Delta^{(a,b,c,d)}(\mathbf{x})^{-1}\right\\}+\varphi^{(a,b,c,d)}(\mathbf{x})$
(14)

where the symmetrization is over the Weyl group $W$ and
$\varphi^{(a,b,c,d)}(\mathbf{x})$ is a Weyl-symmetric rational function such
that $\mathcal{D}_{1}^{(a,b,c,d)}(\mathbf{x})\cdot
1=\frac{1-t^{N}}{1-t}\left(1+\sigma^{2}t^{N-1}\right)$. Explicitly,

$\mathcal{D}_{1}^{(a,b,c,d)}(\mathbf{x})=\frac{1-t^{N}}{1-t}\left(1+\sigma^{2}t^{N-1}\right)+\sum_{i=1}^{N}\sum_{\epsilon=\pm
1}\Phi_{i,\epsilon}^{(a,b,c,d)}(x)\,\,(\Gamma_{i}^{\epsilon}-1)$ (15)

where

$\displaystyle\Phi_{i,\epsilon}^{(a,b,c,d)}(x)$ $\displaystyle=$
$\displaystyle\frac{(1-ax_{i}^{\epsilon})(1-bx_{i}^{\epsilon})(1-cx_{i}^{\epsilon})(1-dx_{i}^{\epsilon})}{(1-x_{i}^{2\epsilon})(1-qx_{i}^{2\epsilon})}\prod_{j\neq
i}\frac{tx_{i}^{\epsilon}-x_{j}}{x_{i}^{\epsilon}-x_{j}}\frac{tx_{i}^{\epsilon}x_{j}-1}{x_{i}^{\epsilon}x_{j}-1}.$

The difference operator (15) is the first of a commuting family of $N$
difference operators, where the higher order operators can be chosen DFK (21),
using vD (95); Rai (05), so that the eigenvalues of their common
eigenfunctions, the monic Koornwinder polynomials
$P_{\lambda}^{(a,b,c,d)}(\mathbf{x})$ indexed by integer partitions coding
their leading term, are

$\mathcal{D}_{m}^{(a,b,c,d)}(\mathbf{x})\,P_{\lambda}^{(a,b,c,d)}(\mathbf{x})=\sigma^{m}\,t^{m(N-\frac{m+1}{2})}\,{\hat{e}}_{m}(\mathbf{s})\,P_{\lambda}^{(a,b,c,d)}(\mathbf{x}),$
(16)

for $m=1,2,...,N$, where $\mathbf{s}=q^{\lambda}t^{\rho}$, with $\sigma,\rho$
as in (12).

Upon specialization of the parameters $a,b,c,d$ (see Table 1), the Koornwinder
theory reduces to the Macdonald theory Mac (01) for affine and twisted
classical types.

$\mathfrak{g}$ | $\mathfrak{g}^{*}$ | $a$ | $b$ | $c$ | $d$ | $R$ | S | $R^{*}$ | $\xi_{\mathfrak{g}}$
---|---|---|---|---|---|---|---|---|---
$D_{N}^{(1)}$ | $D_{N}^{(1)}$ | $1$ | $-1$ | $q^{\frac{1}{2}}$ | $-q^{\frac{1}{2}}$ | $D_{N}$ | $D_{N}$ | $D_{N}$ | 0
$B_{N}^{(1)}$ | $C_{N}^{(1)}$ | $t$ | $-1$ | $q^{\frac{1}{2}}$ | $-q^{\frac{1}{2}}$ | $B_{N}$ | $B_{N}$ | $C_{N}$ | $\frac{1}{2}$
$C_{N}^{(1)}$ | $B_{N}^{(1)}$ | $t^{\frac{1}{2}}$ | $-t^{\frac{1}{2}}$ | $t^{\frac{1}{2}}\,q^{\frac{1}{2}}$ | $-t^{\frac{1}{2}}\,q^{\frac{1}{2}}$ | $C_{N}$ | $C_{N}$ | $B_{N}$ | 1
$A_{2N-1}^{(2)}$ | $A_{2N-1}^{(2)}$ | $t^{\frac{1}{2}}$ | $-t^{\frac{1}{2}}$ | $q^{\frac{1}{2}}$ | $-q^{\frac{1}{2}}$ | $C_{N}$ | $B_{N}$ | $C_{N}$ | $\frac{1}{2}$
$D_{N+1}^{(2)}$ | $D_{N+1}^{(2)}$ | $t$ | $-1$ | $t\,q^{\frac{1}{2}}$ | $-q^{\frac{1}{2}}$ | $B_{N}$ | $C_{N}$ | $B_{N}$ | 1
$A_{2N}^{(2)}$ | $A_{2N}^{(2)}$ | $t$ | $-1$ | $t^{\frac{1}{2}}\,q^{\frac{1}{2}}$ | $-t^{\frac{1}{2}}\,q^{\frac{1}{2}}$ | $BC_{N}$ | – | $BC_{N}$ | 1

Table 1: Specialization of the Koornwinder parameters $a,b,c,d$ corresponding
to the affine algebra $\mathfrak{g}$. The pair $(R,S)$ refer to a pair of
classical root systems corresponding to Macdonald’s notation Mac (01), except
for $A_{2n}^{(2)}$.

###  3.2 Duality and Pieri rules

The Koornwinder polynomials obey a generalized version vD (96); Sah (99) of
the duality property for Macdonald polynomials (4). Let $*$ denote the
following involution on the parameters $(a,b,c,d)$:

$a^{*}=\Big{(}\frac{abcd}{q}\Big{)}^{1/2},\quad
b^{*}=-\Big{(}q\frac{ab}{cd}\Big{)}^{1/2},\quad
c^{*}=\Big{(}q\frac{ac}{bd}\Big{)}^{1/2},\quad
d^{*}=-\Big{(}q\frac{ad}{bc}\Big{)}^{1/2}.$ (17)

This implies that $\sigma^{*}=a$, and $(\sigma\,t^{\rho})^{*}=a\,t^{\rho}$.
The duality property for Koornwinder polynomials is

$\frac{P_{\lambda}^{(a,b,c,d)}(q^{\mu}t^{\rho^{*}})}{P^{(a,b,c,d)}_{\lambda}(t^{\rho^{*}})}=\frac{P_{\mu}^{(a^{*},b^{*},c^{*},d^{*})}(q^{\lambda}t^{\rho})}{P_{\mu}^{(a^{*},b^{*},c^{*},d^{*})}(t^{\rho})}.$
(18)

where $\mu,\lambda$ are both integer partitions.

###### Theorem 3.1

DFK (21) The denominators in (18) can be expressed in terms of
$\Delta^{(a,b,c,d)}(\mathbf{x})$ of (13) as:

$\displaystyle P_{\lambda}^{(a,b,c,d)}(t^{\rho^{*}})$ $\displaystyle=$
$\displaystyle
t^{(\rho^{*},\lambda)}\frac{\Delta^{(a^{*},b^{*},c^{*},d^{*})}(t^{\rho})}{\Delta^{(a^{*},b^{*},c^{*},d^{*})}(q^{\lambda}t^{\rho})},$
$\displaystyle P_{\mu}^{(a^{*},b^{*},c^{*},d^{*})}(t^{\rho})$ $\displaystyle=$
$\displaystyle
t^{(\rho,\mu)}\frac{\Delta^{(a,b,c,d)}(t^{\rho^{*}})}{\Delta^{(a,b,c,d)}(q^{\mu}t^{\rho^{*}})}.$

As in Macdonald theory, Equation (18) can be generalized to the Universal
solutions of the eigenvalue equations,
$P^{(a,b,c,d)}(\mathbf{x};\mathbf{s})=q^{(\lambda,\mu)}\sum_{\alpha\in
Q_{+}}c_{\alpha}^{(a,b,c,d)}(\mathbf{s})\,\mathbf{x}^{-\alpha}$ with generic
$\mathbf{x}=q^{\mu}t^{\rho^{*}}$ and $\mathbf{s}=q^{\lambda}t^{\rho}$ with
$c_{0}^{(a,b,c,d)}(\mathbf{s})=1$. The series
$P^{(a,b,c,d)}(\mathbf{x};\mathbf{s})$ reduces to a Koornwinder polynomial
upon specializing $\lambda$ to an integer partition222In the specialized cases
of Table 1, further truncations occur when $\lambda$ are taken to be integral
weights of the root system $R$, recovering the full generalized Macdonald
polynomial content. :

$P^{(a,b,c,d)}(\mathbf{x};\mathbf{s})\Big{|}_{\mathbf{s}=q^{\lambda}\,t^{\rho},\,\lambda\,{\rm
integer}}=t^{-(\rho,\lambda)}\,P_{\lambda}^{(a,b,c,d)}(\mathbf{x})$ (19)

###### Theorem 3.2

DFK (21) The universal solutions satisfy the duality relations

$\Delta^{(a^{*},b^{*},c^{*},d^{*})}(\mathbf{s})\,P^{(a,b,c,d)}(\mathbf{x};\mathbf{s})=\Delta^{(a,b,c,d)}(\mathbf{x})\,P^{(a^{*},b^{*},c^{*},d^{*})}(\mathbf{s};\mathbf{x}).$
(20)

Again, this implies the Pieri rules for Koornwinder polynomials:

$\hat{e}_{m}(\mathbf{x})\,P_{\lambda}^{(a,b,c,d)}(\mathbf{x})=\mathcal{H}_{m}^{(a,b,c,d)}(\mathbf{s})\,P_{\lambda}^{(a,b,c,d)}(\mathbf{x}).$
(21)

The Pieri operator is computed from the generalized Koornwinder polynomials
for the dual parameters:

$\mathcal{H}_{m}^{(a,b,c,d)}(\mathbf{s})=a^{-m}t^{m(\frac{m+1}{2}-N)}\,{\rm
Ad}_{\Delta^{(a^{*},b^{*},c^{*},d^{*})}(\mathbf{s})^{-1}\,t^{(\rho^{*},\lambda)}}\left\\{\mathcal{D}_{m}^{(a,b,c,d)}(\mathbf{s})\right\\}.$
(22)

##  4 Duality for genus two generalized Macdonald theory

The genus-2 DAHA of “rank-1” was introduced recently by Arthamonov and
Shakirov using refined Chern-Simons theory AS (20, 19). In the following, we
provide a formulation of duality analogous to the discussion above. Although
this case is not directly related to a particular root lattice, note that the
following vectors play an analogous role here. Define the three vectors in
$\mathbb{C}^{3}$:

$\alpha_{1}=(1,1,-1),\quad\alpha_{2}=(1,-1,1),\quad\alpha_{3}=(-1,1,1),$

and the root system-type sets $R_{\pm}^{(2)}$:

$R_{+}^{(2)}=\\{\alpha_{1},\alpha_{2},\alpha_{3},\alpha_{1}+\alpha_{2},\alpha_{1}+\alpha_{3},\alpha_{2}+\alpha_{3},\alpha_{1}+\alpha_{2}+\alpha_{3}\\}=-R_{-}^{(2)}$

together with the positive cone $Q_{+}^{(2)}=\oplus\mathbb{Z}_{\geq
0}\alpha_{i}$. The (un-normalized) dual basis is denoted by

$\omega_{1}=(1,1,0),\quad\omega_{2}=(1,0,1),\quad\omega_{3}=(0,1,1).$

The analog of the Weyl vector is taken as

$\rho=\alpha_{1}+\alpha_{2}+\alpha_{3}=(1,1,1).$

The analog of integer partitions are the elements in the set

$\mathcal{P}^{(2)}=\left\\{\lambda=(\lambda_{1},\lambda_{2},\lambda_{3})\in\mathbb{Z}^{3}|(\alpha_{i},\lambda)\in
2\mathbb{Z}_{\geq 0},i=1,2,3\right\\}.$

We use the notation $\mathbf{x}=(x_{1},x_{2},x_{3})$. The analog of the Weyl
group (generated by reflections by $\alpha_{i}+\alpha_{j}$) is the product
group $W\simeq S_{2}\times S_{2}\times S_{2}$, acting on the
$\mathbf{x}$-variables via inversions $x_{i}\mapsto x_{i}^{\pm 1}$.

###  4.1 Difference operators

Let $q,t$ be two nonzero complex parameters.333We use different conventions
from AS (19) to avoid fractional powers of $q,t$. The results of AS (19) are
recovered upon substituting $q\to q^{1/2}$ and $t\to t^{1/2}$. Introduce the
infinite product:

$\displaystyle\Delta^{(2)}(\mathbf{x})$ $\displaystyle=$
$\displaystyle\frac{\displaystyle\prod_{1\leq i<j\leq
3}(q^{2}\mathbf{x}^{-\alpha_{i}-\alpha_{j}};q^{2})_{\infty}}{\displaystyle({q^{2}}{t^{-1}}\mathbf{x}^{-\alpha_{1}-\alpha_{2}-\alpha_{3}};q^{2})_{\infty}\prod_{i=1}^{3}({q^{2}}{t^{-1}}\mathbf{x}^{-\alpha_{i}};q^{2})_{\infty}}$
$\displaystyle=$ $\displaystyle\prod_{n=1}^{\infty}\frac{1}{\displaystyle
1-\frac{q^{2n}}{t\,x_{1}x_{2}x_{3}}}\prod_{i=1}^{3}\frac{\displaystyle
1-\frac{q^{2n}}{x_{i}^{2}}}{\displaystyle
1-\frac{q^{2n}}{t}\frac{x_{i}^{2}}{x_{1}x_{2}x_{3}}}.$

The genus-2 commuting operators are defined for each pair $(i,j)$ such that
$1\leq i<j\leq 3$ by444This definition leads to the same difference operators
as those introduced in AS (19).

$\displaystyle\mathcal{D}_{i,j}^{(2)}$ $\displaystyle=$ $\displaystyle t\,{\rm
Sym}\left\\{\Delta^{(2)}(\mathbf{x})\,\Gamma_{i}\Gamma_{j}\,\Delta^{(2)}(\mathbf{x})^{-1}\right\\}$
(23) $\displaystyle=$
$\displaystyle\frac{1}{t}\sum_{\epsilon_{i},\epsilon_{j}=\pm
1}\frac{(tx_{i}^{\epsilon_{i}}x_{j}^{\epsilon_{j}}x_{k}-1)(tx_{i}^{\epsilon_{i}}x_{j}^{\epsilon_{j}}x_{k}^{-1}-1)}{(x_{i}^{2\epsilon_{i}}-1)(x_{j}^{2\epsilon_{j}}-1)}\Gamma_{i}^{\epsilon_{i}}\Gamma_{j}^{\epsilon_{j}},$

where $k$ is such that $\\{i,j,k\\}=\\{1,2,3\\}$. Here, the symmetrization is
with respect to $W$.

The genus 2 Macdonald polynomials $P_{\lambda}^{(2)}(\mathbf{x})$ are the
monic555A different normalization was used in the original definition AS (19)
where the polynomials are not monic, but inherit a particular normalization
from the refined Chern-Simons perspective. common eigenfunctions of the three
operators $\mathcal{D}_{i,j}^{(2)}$, indexed by genus-2 partitions
$\lambda\in\mathcal{P}^{(2)}$ coding their leading term in the sense that

$P_{\lambda}^{(2)}(\mathbf{x})=\prod_{i=1}^{3}x_{i}^{\frac{1}{2}(\alpha_{i},\lambda)}\Big{(}1+O(\mathbf{x}^{-\alpha})_{\alpha\in
Q_{+}}\Big{)}.$

The corresponding eigenvalue equations for $1\leq i<j\leq 3$ are

$\mathcal{D}_{i,j}^{(2)}(\mathbf{x})\,P_{\lambda}^{(2)}(\mathbf{x})=\hat{e}_{1}(s_{\ell})\,P_{\lambda}^{(2)}(\mathbf{x})$
(24)

where $\ell$ is such that $\alpha_{i}+\alpha_{j}=2\epsilon_{\ell}$,
$s_{\ell}=t\,q^{\frac{1}{2}(\alpha_{i}+\alpha_{j},\lambda)}=t\,q^{\lambda_{\ell}}$,
and $\hat{e}_{1}(x)=x+x^{-1}$. Note that we can still write
$\mathbf{s}=q^{\lambda}t^{\rho}$, with the relevant definitions above.

###  4.2 Duality and Pieri rules

In AS (19), the Macdonald polynomials of genus-2 are introduced as the unique
solution to Pieri rules, which automatically fixes their normalization. These
were inferred from the refined Chern-Simons approach. We now show that the
Pieri rules for the monic normalization of genus-2 Macdonald polynomials can
be derived as a consequence of duality relations. The resulting Pieri rules
agree with those of AS (19) up to a suitable change of normalization. We do
not present the proof here for lack of space, see DFK (23). The the method of
the proof is similar to that used by Macdonald for type $A$ Mac (95).

###### Theorem 4.1

The genus 2 Macdonald polynomials obey the following duality property,
obtained by specializing both $\mathbf{x}=q^{\mu}t^{\rho}$ and
$\mathbf{s}=q^{\lambda}t^{\rho}$ with $\lambda,\mu\in\mathcal{P}^{(2)}$:

$\frac{P_{\lambda}^{(2)}(q^{\mu}t^{\rho})}{P_{\lambda}^{(2)}(t^{\rho})}=\frac{P_{\mu}^{(2)}(q^{\lambda}t^{\rho})}{P_{\mu}^{(2)}(t^{\rho})}.$
(25)

###### Theorem 4.2

The normalization factors for genus 2 Macdonald polynomials are expressed in
terms of the product $\Delta^{(2)}(\mathbf{x})$ as follows:

$\displaystyle
P_{\lambda}^{(2)}(t^{\rho})=t^{\frac{1}{2}(\rho,\lambda)}\frac{\Delta^{(2)}(t^{\rho})}{\Delta^{(2)}(q^{\lambda}t^{\rho})}.$
(26)

As in genus-1, the duality extends to the universal solution of the eigenvalue
equations (24), defined for
$\mathbf{x}=q^{\mu}t^{\rho},\mathbf{s}=q^{\lambda}t^{\rho}$ with generic
comples $\lambda$, $\mu$ as the series

$P^{(2)}(\mathbf{x};\mathbf{s})=q^{\frac{1}{2}(\lambda,\Omega\mu)}\,\sum_{\alpha\in
Q^{(2)}_{+}}c_{\alpha}^{(2)}(\mathbf{s})\,\mathbf{x}^{-\alpha},\qquad\Omega=\begin{pmatrix}1&1&-1\\\
1&-1&1\\\ -1&1&1\end{pmatrix},$

with the normalization $c^{(2)}_{0}(\mathbf{s})=1$. As before, the series has
a finite truncation when we specialize $\lambda$ to a genus 2 integer
partition, recovering:

$P^{(2)}(\mathbf{x};\mathbf{s})\Big{|}_{\lambda\in\mathcal{P}^{(2)}}=t^{-\frac{1}{2}(\rho,\lambda)}\,P_{\lambda}^{(2)}(\mathbf{x}),$
(27)

where we used
$\prod_{i=1}^{3}x_{i}^{\frac{1}{2}(\alpha_{i},\lambda)}=t^{\frac{1}{2}(\rho,\lambda)}q^{\frac{1}{2}(\lambda,\Omega\mu)}$.

###### Theorem 4.3

The duality relation (25) extends to the universal solution with generic
$\lambda,\mu$ as

$\Delta^{(2)}(\mathbf{s})\,P^{(2)}(\mathbf{x};\mathbf{s})=\Delta^{(2)}(\mathbf{x})\,P^{(2)}(\mathbf{s};\mathbf{x}).$
(28)

As in genus-1, duality implies Pieri rules for genus-2 Macdonald polynomials.
The Pieri operators express the result of multiplying the polynomials by any
of the three elementary symmetric functions:

$\hat{e}_{1}(x_{\ell})\,P_{\lambda}^{(2)}(\mathbf{x})=\mathcal{H}_{\ell}^{(2)}(\mathbf{s})\,P_{\lambda}^{(2)}(\mathbf{x}),\qquad\ell=1,2,3.$
(29)

Duality implies that the Pieri operators
$\mathcal{H}_{\ell}^{(2)}(\mathbf{s})$ are

$\mathcal{H}_{\ell}^{(2)}(\mathbf{s})={\rm
Ad}_{\Delta^{(2)}(\mathbf{s})^{-1}\,t^{\frac{1}{2}(\rho,\lambda)}}\left\\{\mathcal{D}_{i,j}^{(2)}(\mathbf{s})\right\\},\qquad
i<j,\ \alpha_{i}+\alpha_{j}=2\epsilon_{\ell}.$ (30)

Explicitly, using the notation $\Lambda_{i}=q^{\lambda_{i}}$ and
$T_{i}=q^{\lambda_{i}\partial_{\lambda_{i}}}$,

$\displaystyle\mathcal{H}_{1}^{(2)}(\mathbf{s})$ $\displaystyle=$
$\displaystyle
T_{1}T_{2}+t\frac{\Lambda_{1}\Lambda_{2}}{\Lambda_{3}}\frac{(1-\frac{\Lambda_{2}\Lambda_{3}}{\Lambda_{1}})(1-q^{-2}t^{2}\frac{\Lambda_{2}\Lambda_{3}}{\Lambda_{1}})}{(1-t^{2}\Lambda_{2}^{2})(1-q^{-2}t^{2}\Lambda_{2}^{2})}\,T_{1}T_{2}^{-1}$
$\displaystyle+t\frac{\Lambda_{1}\Lambda_{2}}{\Lambda_{3}}\frac{(1-\frac{\Lambda_{1}\Lambda_{3}}{\Lambda_{2}})(1-q^{-2}t^{2}\frac{\Lambda_{1}\Lambda_{3}}{\Lambda_{2}})}{(1-t^{2}\Lambda_{1}^{2})(1-q^{-2}t^{2}\Lambda_{1}^{2})}\,T_{1}^{-1}T_{2}$
$\displaystyle+\frac{(1-\frac{\Lambda_{1}\Lambda_{2}}{\Lambda_{3}})(1-q^{-2}t^{2}\frac{\Lambda_{1}\Lambda_{2}}{\Lambda_{3}})(1-t^{2}\Lambda_{1}\Lambda_{2}\Lambda_{3})(1-q^{-2}t^{4}\Lambda_{1}\Lambda_{2}\Lambda_{3})}{(1-t^{2}\Lambda_{1}^{2})(1-t^{2}\Lambda_{2}^{2})(1-q^{-2}t^{2}\Lambda_{1}^{2})(1-q^{-2}t^{2}\Lambda_{2}^{2})}T_{1}^{-1}T_{2}^{-1},$

and $\mathcal{H}_{2}^{(2)}(\mathbf{s})$ and
$\mathcal{H}_{3}^{(2)}(\mathbf{s})$ are obtained by cyclic permutations of the
indices $1,2,3$.

These Pieri rules agree with those of AS (19) for the polynomials
$\psi_{\lambda}(\mathbf{x})$ with the normalization

$\psi_{\lambda}(\mathbf{x})=t^{-(\rho,\lambda)}\,\prod_{k=1}^{3}\prod_{i=0}^{\lambda_{k}-1}\frac{1-t^{4}q^{2i}}{1-t^{2}q^{2i}}\,\frac{P_{\lambda}(\mathbf{x})}{P_{\lambda}(t^{\rho})}.$

##  5 $q$-Whittaker limits and the quantum Q-systems

In genus-1, the motivation for the construction of the particular sets of
difference operators referred to above above and their Dehn-twisted analogues
is a set of recursion relations for characters of finite-dimensional
representations of quantum affine algebras known as the Q-system HKO+ (99) and
its quantization DFK (14). These appear in the $q$-Whittaker limit of the
sDAHAs.

###  5.1 Genus-1

The functions $\Delta$ for each setting above were chosen so that the limit
$t\to\infty$ is well-defined. We refer to this as the $q$-Whittaker limit.
Each of the $q$-difference operators in $\mathbf{x}$ has a well-defined limit
(after renormalization by a power of $t$). This limit can be taken directly in
Macdonald theory for type $A_{N}^{(1)}$. In Koornwinder theory, we take the
limit after the specialization of the parameters $(a,b,c,d)$ as in Table Table
1, since the specialization depends on $t$.

In this limit, the Dehn-twisted Macdonald-Koornwinder difference operators do
not simplify greatly, for example (11) become

$D_{a,n}(\mathbf{x})=\lim_{t\to\infty}t^{-a(N-a)}\mathcal{D}_{a,n}(\mathbf{x})=\sum_{I\subset[1,N]\atop|I|=a}\prod_{i\in
I,j\not\in I}\frac{x_{i}}{x_{i}-x_{j}}\,\prod_{i\in I}x_{i}^{n}\,\prod_{i\in
I}\Gamma_{i}.$

The eigenvalues of the Macdonald-Koornwinder operators, which are elementary
symmetric functions in $\mathbf{s}$, are replaced by their dominant monomial
in the limit, because $\mathbf{s}$ depends explicitly on $t$. For example in
type $A$, $e_{a}(\mathbf{s})$ is replaced by $\Lambda^{\omega_{a}}$, where
$\Lambda_{i}=q^{\lambda_{i}}$. The corresponding eigenfunctions are (class-1)
$q$-Whittaker functions, $\Pi_{\lambda}(\mathbf{x})$. In type $A$ they satisfy
the equations

$D_{a,0}(\mathbf{x})\,\Pi_{\lambda}(\mathbf{x})=\Lambda_{1}\Lambda_{2}\cdots\Lambda_{a}\,\Pi_{\lambda}(\mathbf{x}).$
(31)

The universal solutions of the eigenvalue equations also have well-defined
$q$-Whittaker limits as series solutions in $\mathbf{x}^{-\alpha_{i}}$,
$\Pi(\mathbf{x};\Lambda)$. Because $\mathbf{s}$ depends explicitly on $t$, the
the symmetry $\mathbf{x}\leftrightarrow\mathbf{s}$ in Equations (7), (20) and
(28) is broken in the limit, $\Delta(\mathbf{s})\to 1$ whereas
$\Delta(\mathbf{x})$ is an still an infinite product.

The Pieri rules have well-defined limits of the form
$e_{a}(\mathbf{x})\,\Pi_{\lambda}(x)=H_{a}(\Lambda)\,\Pi_{\lambda}(\mathbf{x})$
in type $A$. The limits of the Pieri operators are greatly simplified in the
limit and can be identified with the quantum relativistic Toda Hamiltonians
associated with each root system. They are all Laurent polynomials in
$\Lambda_{i},T_{i}$. For example in type A they are

$H_{1}(\Lambda)=T_{1}+\sum_{i=2}^{N}\Big{(}1-\frac{\Lambda_{i}}{\Lambda_{i-1}}\Big{)}T_{i}.$

These Hamiltonians are the conserved quantities of the discrete evolutions
called the quantum Q-systems corresponding to each affine algebra DFK (18,
21). These are non-commutative rational recursion relations in the discrete
time variables $n$. The limiting Dehn-twisted Macdonald-Koornwinder operators
are the solutions to these equations. In most cases, the Dehn twist is a
sequence of mutations in a quantum cluster algebra in which the elements
$D_{a,n}$ are the $\mathcal{A}$-type cluster variables. The proof of these
statements, found in DFK (21), relies on the duality property and the notion
of the “Fourier transform”, which allows us to trade $q$-difference operators
with their eigenvalues, when acting on the universal $q$-Whittaker function.

###  5.2 Genus-2 case

We use the same $t\to\infty$ limit for in genus-2. In this limit, the
operators (23) factorize into genus-1 $A_{1}^{(1)}$ type Macdonald operators:

$D_{i,j}^{(2)}(\mathbf{x})=\lim_{t\to\infty}t^{-1}\mathcal{D}_{i,j}^{(2)}(\mathbf{x})=\sum_{\epsilon_{i},\epsilon_{j}=\pm
1}\frac{x_{i}^{2\epsilon_{i}}}{x_{i}^{2\epsilon_{i}}-1}\,\Gamma_{i}^{\epsilon_{i}}\,\frac{x_{j}^{2\epsilon_{j}}}{x_{j}^{2\epsilon_{j}}-1}\Gamma_{j}^{\epsilon_{j}}=D_{1}(x_{i})\,D_{1}(x_{j})$
(32)

$D_{1}(x)$ is the ${\mathfrak{s}l}_{2}$ Macdonald operator in the
$q$-Whittaker limit

$D_{1}(x)=\frac{x^{2}}{x_{i}^{2}-1}\Gamma_{x}+\frac{x^{-2}}{x_{i}^{-2}-1}\Gamma_{x}^{-1}=D_{1}(x,x^{-1}).$

As a consequence, the $q$-Whittaker limit of the genus-2 Macdonald polynomials
factorize:

$\Pi^{(2)}_{\lambda}(\mathbf{x})=\Pi_{\frac{1}{2}(\alpha_{1},\lambda)}(x_{1})\,\Pi_{\frac{1}{2}(\alpha_{2},\lambda)}(x_{2})\,\Pi_{\frac{1}{2}(\alpha_{3},\lambda)}(x_{3}),$

where $\Pi_{m}(x)$ are expressed in terms of the $A_{1}$ Macdonald polynomials
as $\Pi_{\lambda_{1}-\lambda_{2}}(x)=\Pi_{\lambda_{1},\lambda_{2}}(x,x^{-1})$.

The Pieri operators have simple limits as well:

$H_{1}^{(2)}(\Lambda)=T_{1}T_{2}+\Big{(}1-\frac{\Lambda_{3}}{\Lambda_{1}\Lambda_{2}}\Big{)}T_{1}^{-1}T_{2}^{-1},$

while $H_{2}^{(2)},H_{3}^{(2)}$ are obtained by cyclic permutation of the
indices. The latter coincides with the Toda Hamiltonian
$H_{1}(\Lambda_{1},\Lambda_{2})$ for $A_{1}$ under the correspondence

$\Lambda_{1}\to\Big{(}\frac{\Lambda_{1}\Lambda_{2}}{\Lambda_{3}}\Big{)}^{1/2}=q^{\frac{1}{2}(\alpha_{1},\lambda)},\quad\Lambda_{2}\to\Big{(}\frac{\Lambda_{1}\Lambda_{2}}{\Lambda_{3}}\Big{)}^{-1/2}=q^{-\frac{1}{2}(\alpha_{1},\lambda)}.$

The quantum $Q$-system cluster algebra in this case is a factorized system of
three type $A_{1}^{(1)}$ systems, corresponding to three disconnected Jordan
quivers.

##  6 Conclusion

We have summarized the duality property in several versions of the spherical
double affine Hecke algebras. In each case the function $\Delta(\mathbf{x})$,
which is related to the normalization of the Macdonald polynomials under
duality, plays a pivotal role in determining the Pieri rules. This function is
related to the affine root system of an underlying affine Lie algebra in the
genus-1 case. We have argued that there is a structural similarity in the
genus-2 case, which does not correspond to a root system. The proofs of the
statements for genus-2 will appear in a forthcoming publication DFK (23).

## References

  * AS [19] S. Arthamonov and Sh. Shakirov.  Genus two generalization of $A_{1}$ spherical DAHA.  Selecta Math. (N.S.), 25(2):Paper No. 17, 29, 2019.
  * AS [20] S. Arthamonov and Sh. Shakirov.  Refined Chern-Simons theory in genus two.  J. Knot Theory Ramifications, 29(7):2050044, 24, 2020.
  * Che [05] Ivan Cherednik.  Double affine Hecke algebras, volume 319 of London Mathematical Society Lecture Note Series.  Cambridge University Press, Cambridge, 2005.
  * DFK [14] Philippe Di Francesco and Rinat Kedem.  Quantum cluster algebras and fusion products.  Int. Math. Res. Not. IMRN, (10):2593–2642, 2014.
  * DFK [18] P. Di Francesco and R. Kedem.  Difference equations for graded characters from quantum cluster algebra.  Transform. Groups, 23(2):391–424, 2018.
  * DFK [19] Philippe Di Francesco and Rinat Kedem.  ($q,t$)-Deformed Q-Systems, DAHA and Quantum Toroidal Algebras via Generalized Macdonald Operators.  Comm. Math. Phys., 369(3):867–928, 2019.
  * DFK [21] Philippe Di Francesco and Rinat Kedem.  Macdonald duality and the proof of the quantum q-system conjecture, 2021\.  preprint ArXiv 2112.09798.
  * DFK [23] Philippe Di Francesco and Rinat Kedem.  Manuscript in preparation, 2023.
  * HKO+ [99] G. Hatayama, A. Kuniba, M. Okado, T. Takagi, and Y. Yamada.  Remarks on fermionic formula.  In Recent developments in quantum affine algebras and related topics (Raleigh, NC, 1998), volume 248 of Contemp. Math., pages 243–291. Amer. Math. Soc., Providence, RI, 1999.
  * Koo [92] Tom H. Koornwinder.  Askey-Wilson polynomials for root systems of type $BC$.  In Hypergeometric functions on domains of positivity, Jack polynomials, and applications (Tampa, FL, 1991), volume 138 of Contemp. Math., pages 189–204. Amer. Math. Soc., Providence, RI, 1992.
  * Mac [01] I. G. Macdonald.  Orthogonal polynomials associated with root systems.  Sém. Lothar. Combin., 45:Art. B45a, 40, 2000/01.
  * Mac [95] I. G. Macdonald.  Symmetric functions and Hall polynomials.  Oxford Mathematical Monographs. The Clarendon Press, Oxford University Press, New York, second edition, 1995.  With contributions by A. Zelevinsky, Oxford Science Publications.
  * NS [12] Masatoshi Noumi and Jun’ichi Shiraishi.  A direct approach to the bispectral problem for the ruijsenaars-macdonald q-difference operators, 2012.  arXiv:1206.5364 [math.QA].
  * Rai [05] Eric M. Rains.  ${\rm BC}_{n}$-symmetric polynomials.  Transform. Groups, 10(1):63–132, 2005.
  * Sah [99] Siddhartha Sahi.  Nonsymmetric Koornwinder polynomials and duality.  Ann. of Math. (2), 150(1):267–282, 1999.
  * Sto [14] Jasper V. Stokman.  Connection coefficients for basic Harish-Chandra series.  Adv. Math., 250:351–386, 2014.
  * vD [95] J. F. van Diejen.  Commuting difference operators with polynomial eigenfunctions.  Compositio Math., 95(2):183–233, 1995.
  * vD [96] J. F. van Diejen.  Self-dual Koornwinder-Macdonald polynomials.  Invent. Math., 126(2):319–339, 1996.