# Stronger 3SUM-Indexing Lower Bounds

Eldon Chung<EMAIL_ADDRESS>Center for Quantum Technologies, National
University of Singapore. Kasper Green Larsen<EMAIL_ADDRESS>Aarhus
University. Supported by Independent Research Fund Denmark (DFF) Sapere Aude
Research Leader grant No 9064-00068B.

###### Abstract

The $3$SUM-Indexing problem was introduced as a data structure version of the
$3$SUM problem, with the goal of proving strong conditional lower bounds for
static data structures via reductions. Ideally, the conjectured hardness of
$3$SUM-Indexing should be replaced by an unconditional lower bound.
Unfortunately, we are far from proving this, with the strongest current lower
bound being a logarithmic query time lower bound by Golovnev et al. from
STOC’20. Moreover, their lower bound holds only for non-adaptive data
structures and they explicitly asked for a lower bound for adaptive data
structures. Our main contribution is precisely such a lower bound against
adaptive data structures. As a secondary result, we also strengthen the non-
adaptive lower bound of Golovnev et al. and prove strong lower bounds for
$2$-bit-probe non-adaptive $3$SUM-Indexing data structures via a completely
new approach that we find interesting in its own right.

##  1 Introduction

In the $3$SUM Problem, we are given a set $S$ of $n$ group elements from an
abelian group $(G,+)$ and the goal is to determine whether there is a triple
$a,b,c\in S$ such that $a+b=c$. The $3$SUM Problem was originally introduced
by Gajentaan and Overmars [13] as a means of establishing hardness of
geometric problems. Concretely, it was conjectured that $3$SUM requires
$\Omega(n^{2})$ time when the underlying group is the set of reals and we use
the Real-RAM computational model. By reductions, this conjecture implies
similar lower bounds for a wealth of geometric problems, see e.g. [5, 27].

While originally being restricted mostly to geometric problems, the seminal
work by Pǎtraşcu [23] showed that a suitable integer version of $3$SUM (e.g.
$G$ is the integers modulo $n^{3}$), may be used to prove hardness of numerous
fundamental algorithmic problems (see e.g. [18, 4, 1, 23]) in the more
realistic word-RAM model. These lower bounds are based on the so-called $3$SUM
Conjecture, asserting that no $n^{2-\delta}$ time $3$SUM algorithm exists for
any constant $\delta>0$. To date, the fastest $3$SUM algorithm runs in time
$O(n^{2}(\lg\lg n)^{O(1)}/\lg^{2}n)$ [9], which is far from refuting the
conjecture. The $3$SUM Conjecture is now one of the pillars in fine-grained
complexity and much effort has gone into understanding its implications for
algorithm lower bounds.

Highly related to algorithm lower bounds is lower bounds for data structures.
While more progress has been made on proving unconditional lower bounds for
data structures compared to algorithms, current state-of-the-art lower bounds
are still only polylogarithmic [19, 22, 20]. This lack of progress motivates
fine-grained conditional lower bounds also for data structures. The first
approach in this direction, is via the Online Matrix-Vector Problem by
Henzinger et al. [17]. Their framework yields polynomial conditional lower
bounds for dynamic data structures via reductions from multiplication of a
boolean matrix and a boolean vector, with addition replaced by OR and
multiplication replaced by AND. However, their framework is inherently tied to
_dynamic_ data structure problems, where a data set is to be maintained under
update operations. As a means to addressing _static_ data structure problems,
Goldstein, Kopelowitz, Lewenstein, and Porat in [14] introduced the $3$SUM-
Indexing Problem.

####  $3$SUM-Indexing.

The $3$SUM-Indexing problem was first defined by Demaine and Vadhan in an
unpublished manuscript [10] and then by Goldstein, Kopelowitz, Lewenstein, and
Porat in [14] and is as follows:

######  Definition 1 ($3$SUM-Indexing).

Let $(G,+)$ be a finite abelian group. Preprocess two sets of group elements
$A_{1},A_{2}\subseteq G$ each of size $n$ into a data structure of $S$ memory
cells of $w$ bits so that given any query group element $z$, deciding whether
there exists $a_{1}\in A_{1}$ and $a_{2}\in A_{2}$ such that $a_{1}+a_{2}=z$
is done by accessing at most $T$ memory cells.

A number of hardness conjectures were provided together with the definition of
the $3$SUM-Indexing Problem. Combined with reductions, these conjectures allow
establishment of conditional lower bounds for static data structures. To be
consistent with the terminology used for unconditional data structure lower
bounds, which are typically proved in the cell probe model [29], we refer to
accessing a memory cell as _probing_ the cell. The following conjectures were
made regarding the hardness of $3$SUM-Indexing:

######  Conjecture 1 ([14]).

Any data structure for $3$SUM-Indexing with space $S$ and $T=O(1)$ probes must
have $S=\tilde{\Omega}(n^{2})$.

######  Conjecture 2 ([10]).

Any data structure for $3$SUM-Indexing with space $S$ and $T$ probes must have
$ST=\tilde{\Omega}(n^{2})$.

######  Conjecture 3 ([14]).

Any data structure for $3$SUM-Indexing with space $S$ and $T=O(n^{1-\delta})$
probes must have $S=\tilde{\Omega}(n^{2})$.

Clearly the last conjecture is the strongest, and in general, we have the
following implications:

$\textrm{Conjecture~{}\ref{cnj:c}}\Rightarrow\textrm{Conjecture~{}\ref{cnj:b}}\Rightarrow\textrm{Conjecture~{}\ref{cnj:a}}$

These conjectures have been successfully used to prove fine-grained hardness
of several natural static data structure problems ranging from Set
Disjointness, Set Intersection, Histogram Indexing to Forbidden Pattern
Document Retrieval [14].

Very surprisingly, Golovnev et al. [15] showed that the strongest of these
conjectures, Conjecture 3, is false. Concretely, they gave a data structure
for $3$SUM-Indexing with $T=\tilde{O}(n^{3\delta})$ and
$S=\tilde{O}(n^{2-\delta})$ for any constant $\delta>0$. This refutes
Conjecture 3, but not the remaining two conjectures. Their data structure is
based on an elegant use of Fiat and Naor’s [12] general time-space tradeoff
for function inversion.

The refutation of Conjecture 3 only makes it more urgent that we replace these
conjectured lower bounds by unconditional ones. However, depressingly little
is still known in terms of unconditional hardness of $3$SUM-Indexing. First,
[10] proved Conjecture 1 in the special case of $T=1$. Secondly, in the recent
work by Golovnev et al. [15], the following was proved for _non-adaptive_ data
structures:

######  Theorem 1 ([15]).

Any _non-adaptive_ cell probe data structure answering $3$SUM-Indexing queries
for input sets of size $n$ from an abelian group $G$ of size $O(n^{2})$ using
$S$ words of $w$ bits must have query time $T=\Omega(\lg n/\lg(Sw/n))$.

A non-adaptive data structure is one in which the cells to probe are chosen
beforehand as a function _only_ of the query element $z$. That is, the data
structure is not allowed to choose which memory cells to probe based on the
contents of previously probed cells. Proving lower bounds for non-adaptive
data structures is often easier than allowing adaptivity, see e.g. [8, 6, 25],
and Golovnev et al. remark: ” _It is crucial for our proof that the input is
chosen at random after the subset of data structure cells, yielding a lower
bound only for non-adaptive algorithms_.” [15]. Golovnev et al. explicitly
raised it as an interesting open problem (Open Question 3 in [15]) whether a
similar lower bound can be proved also for adaptive data structures.

###  1.1 Our Contributions

Our main contribution is a lower bound for $3$SUM-Indexing that holds also for
adaptive data structures:

######  Theorem 2.

Any cell probe data structure answering $3$SUM-Indexing queries for input sets
of size $n$ for abelian groups $([m],+\mod m)$ with $m=O(n^{2})$ and
$(\\{0,1\\}^{2\lg(n)+O(1)},\oplus)$ using $S$ words of $w=\Omega(\lg n)$ bits
must have query time $T=\Omega(\lg n/\lg(Sw/n))$.

Our lower bound matches the previous bound from [15], this time however
allowing adaptivity. Moreover, it (essentially) matches the strongest known
lower bounds for static data structures (the strongest lower bounds peak at
$T=\Omega(\lg n/\lg(Sw/n))$ [20]), thus ruling out further progress without a
major breakthrough (also in circuit complexity [28, 11]).

Our proof is based on a novel reduction from Pǎtraşcu’s Reachability Oracles
in the Butterfly graph problem [24]. This problem, while rather abstract, has
been shown to capture the hardness of a wealth of static data structure
problems such as 2D Range Counting, 2D Rectangle Stabbing, 2D Skyline Counting
and Range Mode Queries, see e.g. [26, 7, 16] as well as for dynamic data
structure problems, including Range Selection and Median [22] and recently
also all dynamic problems that the Marked Ancestor Problem reduces to [21, 3],
which includes 2d Range Emptiness, Partial Sums and Worst-Case Union-Find. Our
work adds $3$SUM-Indexing and all problems it reduces to, to the list.

#### Even Smaller Universes.

The reduction from Reachability Oracles in the Butterfly Graph problem gives
lower bounds for abelian groups of size $\Omega(n^{2})$, leaving open the
possibility of more efficient data structures for smaller groups. Indeed,
$\Omega(n^{2})$ cardinality of the groups seems like a natural requirement for
hardness, as there are $n^{2}$ pairs of elements $a_{1}\in A_{1}$ and
$a_{2}\in A_{2}$ and thus for smaller groups, one might start to exploit
structures in the sumset $A_{1}+A_{2}$ to obtain more efficient data
structures. We therefore investigate whether the lower bound in Theorem 2 can
be generalized to smaller groups. Quite surprisingly, we show that:

######  Theorem 3.

Any cell probe data structure answering $3$SUM-Indexing queries for input sets
of size $n$ for abelian groups $([m],+\mod m)$, with $m=O(n^{1+\delta})$ and
$(\\{0,1\\}^{(1+\delta)\lg(n)+O(1)},\oplus)$ for a constant $\delta>0$, using
$S$ words of $w=\Omega(\lg n)$ bits must have query time $T=\Omega(\lg
n/\lg(Sw/n))$.

Thus we get logarithmic lower bounds for linear space data structures, even
when the group has size only $n^{1+\delta}$.

To prove Theorem 3, we revisit Pǎtraşcu’s Lopsided Set Disjointness (LSD)
communication game, which he also used to prove his lower bound for
Reachability Oracles in the Butterfly graph problem. We give a careful
reduction from LSD to $3$SUM-Indexing on small universes, thereby establishing
Theorem 3.

#### Non-Adaptive Data Structures.

As another contribution, we revisit the non-adaptive setting considered by
Golovnev et al. [15]. Here we present a significantly shorter proof of their
lower bound and also improve it from $T=\Omega(\lg n/\lg(Sw/n))$ to
$T=\Omega(\lg|G|/\lg(Sw/n))$. Concretely, we prove the following theorem:

######  Theorem 4.

Any non-adaptive cell probe data structure answering $3$SUM-Indexing queries
for input sets of size $n$ for an abelian group $G$ of size $\omega(n^{2})$,
using $S$ words of $w=\Omega(\lg n)$ bits must have query time
$T=\Omega(\min\\{\lg|G|/\lg(Sw/n),n/w\\})$.

We remark that the proof of Golovnev et al. [15] cannot be extended to a
$\lg|G|$ (technically, they require $|G|/n$ queries to survive a cell
sampling, whereas we only require $n$ queries to survive).

Our improvement has a subtle, but interesting consequence. Concretely, if the
size of the group grows to sub-exponential in $n$, say $|G|=2^{\sqrt{n}}$,
then the lower bound becomes
$T=\Omega(\min\\{\sqrt{n}/\lg(\frac{Sw}{n}),n/w\\})$. Since it is most natural
to assume the cell size is large enough to store a group element, i.e.
$w=\Omega(\lg|G|)=\Omega(\sqrt{n})$, the lower bound is still at least
$T=\Omega(\sqrt{n}/\lg S)$. While such large groups are perhaps unrealistic,
one can also interpret the result as saying that if we are non-adaptive and
attempt to design a data structure that does not exploit the size of the
underlying group, then we are doomed to have a slow query time.

#### Non-Adaptive $2$-Bit-Probe Data Structures.

Finally, we consider non-adaptive data structures restricted to $T=2$ probes
in the _bit probe model_ , meaning that each memory cell has $w=1$ bits. The
lower bound from Theorem 1 by [15] in this case is $S=\tilde{\Omega}(n^{3/2})$
(see the paper [15] for the general formulation $S=\tilde{\Omega}(n^{1+1/T})$)
and our lower bound from Theorem 4 is
$S=\tilde{\Omega}(n(|G|/n)^{1/T})=\tilde{\Omega}(\sqrt{n|G|})$. We
significantly strengthen this result by proving an $S=\Omega(|G|)$ lower bound
for an abelian group $(G,+)$, completely ruling out any non-trivial data
structure with $2$ non-adaptive bit probes (with $|G|$ space, we can trivially
store a bit vector representing the sumset $A_{1}+A_{2}$ and have $T=1$ while
being non-adaptive):

######  Theorem 5.

Any non-adaptive data structure for $3$SUM-Indexing such that $T=2$ and $w=1$
requires $S=\Omega(|G|)$ for an abelian group $(G,+)$.

Our proof takes an interesting new approach to data structure lower bounds and
we find that the proof itself is a valuable contribution to data structure
lower bounds. The basic idea is to view the memory cells of the data structure
as a graph with one node per cell. The queries then become edges corresponding
to the $T=2$ memory cells probed. If the number of memory cells is $o(|G|)$,
then the graph has a super-linear number of edges. This implies that its girth
is at most logarithmic and hence we can find a short cycle in the graph. A
cycle is a set of $m$ queries being answered by $m$ memory cells. The standard
cell sampling lower bounds (often used in data structure lower bounds) cannot
derive a contradiction from this, as the $m$ memory bits intuitively are
sufficient to encode the $m$ query answers. However, our novel contribution is
to examine the different types of possible query algorithms (i.e. which
function of the two bits probed does it compute) and argue that in all cases,
such a short cycle is impossible. Directly examining the types of query
algorithms has not been done before in data structure lower bounds and we find
this a valuable contribution that we hope may prove useful in future work.

##  2 Reduction from Reachability Oracles in the Butterfly Graph

In this section, we give a reduction from the problem of _Reachability Oracles
in the Butterfly Graph_ to $3$SUM-Indexing with the cyclic group and the XOR
group, proving Theorem 2. In both cases, the size of the group is at most
quadratic with respect to the input set sizes.

######  Definition 2 (Butterfly Graphs).

A Butterfly graph of degree $B$ and depth $d$ is a directed graph with $d+1$
layers, each comprising of $B^{d}$ nodes. For each layer, the $i^{th}$ node
can be associated with a $d$-digit number in base $B$ which we will refer to
as its _label_ $v_{i}$ where $v_{i}[0]$ denotes the least significant digit.
Then there is an edge from node $i$ on the $k^{th}$ layer to node $j$ on the
$(k+1)^{th}$ layer if and only if $v_{i}[h]=v_{j}[h]$ for all $h\neq k$. That
is to say, that there is an edge if and only if $i$ and $j$ may differ only on
the $k^{th}$ digit of their labels. We will denote such an edge by
$e_{k}(i,j)$.

Nodes in the layer $0$ of the graph are called _source nodes_ , whereas nodes
in layer $d$ of the graph are called _sink nodes_.

######  Definition 3 (Reachability Oracles in the Butterfly Graph).

The problem of Reachability Oracles in the Butterfly Graph is that one has to
pre-process into a data structure a subset of the edges $E$ of the butterfly
graph of degree $B$ and depth $d$. Queries come in the form of $(s,t)$ and the
goal is decide if there exists a path from source node $s$ to sink node $t$
using the subset of edges $E$.

Pǎtraşcu proved the following lower bound for the problem in the cell probe
model:

######  Lemma 1 (Section 5 of [24]).

Any cell probe data structure answering reachability queries in subgraphs of
the butterfly graph with degree $B$ and depth $d$, using $S$ words of $w$ bits
must have query time $t=\Omega(d)$, assuming that $B=\Omega(w^{2})$ and
$\lg(B)=\Omega(\lg(Sd/N))$ where $N=dB^{d}$.

A few remarks about reachability in the Butterfly graph are in order. Firstly,
note that for any source-sink pair $(s,t)$, there exists a unique path from
source $s$ to sink $t$ in the Butterfly graph. Namely, the path uses exactly
edges of the form $e_{k}(i,j)$ such that for $k\in[d]$, $e_{k}(i,j)$ is the
edge from node $i$ on layer $k$ to node $j$ on layer $k+1$ such that:

  1. 1.

$v_{s}[h]=v_{i}[h]$ for all $h\geq k$. That is to say that the $d-k$ most
significant digits of the labels of nodes $s$ and $i$ are the same.

  2. 2.

$v_{t}[h]=v_{j}[h]$ for all $h\leq k$. That is to say that the $k+1$ least
significant digits of the labels of nodes $t$ and $j$ are the same.

Conversely, we can also say that the edge $e_{k}(i,j)$ connects all pairs of
nodes $s,t$ such that the label for $s$ shares the most significant $d-k$
digits with $i$ and the label for $t$ shares the least significant $k+1$
digits with $t$.

Intuitively, this is because the traversing from node $i$ in the $k^{th}$
layer to node $j$ in the $(k+1)^{th}$ layer can be seen as “setting” the
$k^{th}$ digit of the label for node $i$ into the $k^{th}$ digit of the label
for node $j$ while leaving the rest of the digits unaltered.

The general idea of the reduction to $3$SUM-Indexing is to test whether all
the required edges are present when querying for $s$ and $t$. This should be
done by asking one $3$SUM-Indexing query. We will design it such that a sum
$z=a_{1}+a_{2}$ exists for our query $z$ if and only if there is at least one
edge missing on the path from $s$ to $t$.

#### Constructing $A_{1}$.

Our basic idea is to take every edge $e_{k}(i,j)$ in the Butterfly graph and
encode it into a group element $g$ in $A_{1}$. We construct $g$ such that its
digits can be broken up into 5 blocks so that conceptually the:

  1. 1.

first block encodes the layer the edge is from;

  2. 2.

second block encodes the presence of edge $e_{k}(i,j)$ in $E$;

  3. 3.

third block encodes the $d-k$ most significant bits of $i$ followed by $k$
zeroes;

  4. 4.

fourth block holds $d-k-1$ zeroes followed by the $k+1$ least significant
digits of $j$;

  5. 5.

fifth block holds $2$ zeroes.

In short, for every edge $e_{k}(i,j)$, we add group element to $A_{1}$ whose
digits are in the following form:

$(k,\mathbbm{1}\\{{e_{k}(i,j)\in
E}\\},v_{i}[d-1],\ldots,v_{i}[k],\underbrace{0,\ldots,0}_{\text{d -
1}},v_{j}[k],\ldots,v_{j}[0],0,0)$

where $\mathbbm{1}\\{{e_{k}(i,j)\in E}\\}$ is $1$ if $e_{k}(i,j)\in E$ and $0$
otherwise. Note that the Butterfly graph has $dB^{d}$ nodes with degree $B$,
hence a total of $n=dB^{d+1}$ edges. Since $A_{1}$ has one element for each
such edge, we have $|A_{1}|=n$.

#### Constructing $A_{2}$.

Next, we construct the set $A_{2}$ of group elements such that for every $k$,
it “helps” any group element $g$ in $A_{1}$, originating from an edge
$e_{k}(i,j)$, to sum to any value where the third block shares the $d-k$ most
significant bits with $i$ and the fourth block shares the $k+1$ least
significant digits of $j$. This can be done by adding into set $A_{2}$ every
group element such that the:

  1. 1.

first block holds some value $-k$;

  2. 2.

second block is zero;

  3. 3.

third block is $d-k$ zeroes followed by any possible $k$ digit value;

  4. 4.

fourth block holds any possible $d-k-1$ digit value followed by $k+1$ zeroes;

  5. 5.

fifth block holds any possible digit value from $[0,B-1]$.

Thus for $k\in[0,d-1]$, we add any number of the following form into $A_{2}$:

$(-k,0,\underbrace{0,\ldots,0}_{d-k},\underbrace{\star,\ldots,\star}_{d-1},\underbrace{0,\ldots,0}_{k+1},\star,\star)$

where $\star$ denotes wildcard. Note that the least significant digits is not
strictly necessary but is included to enforce that the size of the sets
$A_{1}$ and $A_{2}$ are the same. Observe that $|A_{2}|=dB^{d+1}=n=|A_{1}|$.

#### Different Groups.

For the reduction to $3$SUM-indexing in the cyclic group, we will consider the
set of integers in $[(dB^{d+1})^{2}]$. To that end, the encoding works by
understanding the $2(d+2)$ digits as specifying a mixed-radix number, where
the most significant digit is in base $4d$, the second most significant digit
is in base $3$ and the remaining digits are in base $B$. In which case, we can
take $-k$ to be $4d-k$.

On the other hand, for the XOR group, assuming that $d$ and $B$ are powers of
$2$, we can then also naturally transform each digit into their binary
representation with the exception of the most significant digit whose bit
representation should be based on the number’s complement and the second most
significant digit may be in base $2$.

#### Translating a Query.

What remains is to explain how we answer a reachability query $(s,t)$. We will
first consider the reduction for the group
$([(dB^{d+1})^{2}],+\mod(dB^{d+1})^{2})$ and subsequently argue that the same
reduction basically holds for the XOR group assuming that $d$ and $B$ are
powers of $2$. We claim that there exists $a_{1}\in A_{1}$ and $a_{2}\in
A_{2}$ whose sum is

$z_{(s,t)}=(0,0,v_{s}[d-1],\ldots,v_{s}[0],v_{t}[d-1],\ldots,v_{t}[0],0,0)$

if and only if there does not exist a path from $s$ to $t$ in the Butterfly
graph.

To see this, we first argue that for a pair $a_{1}+a_{2}$ that could
potentially sum to $z_{(s,t)}$, we need not worry about carries amongst the
digits of the numbers. To see this, we start by observing that $a_{1}+a_{2}$
must have its most significant digit equal to $0$. We claim this is only
possible if $a_{1}$’s most significant digit is $k$ and $a_{2}$’s is
$4d-k=-k$. To see this, observe that the second most significant digit of
$a_{1}$ is at most $1$ and the second most significant of $a_{2}$ is always
$0$. Since the second most significant digit is in base $3$, this means that
we cannot get a carry from these digits. Now that we have established this, we
observe that for all remaining digits of any valid pair $a_{1}$ and $a_{2}$
(pairs where the most significant digit in the sum is $0$), there is at most
one of the elements that has a non-zero digit, hence we will not see any
carries.

Now assume there does not exists a path from some source node $s$ to some sink
node $t$. This must mean that there exists a $k\in[0,d-1]$ and an edge
$e_{k}(i,j)$ not in $E$ where:

$\displaystyle v_{i}$
$\displaystyle=(v_{s}[d-1],\ldots,v_{s}[k],v_{t}[k-1],\ldots,v_{t}[0])$
$\displaystyle v_{j}$
$\displaystyle=(v_{s}[d-1],\ldots,v_{s}[k+1],v_{t}[k],\ldots,v_{t}[0])$

By construction, this implies that the following group element exists in the
set $A_{1}$:

$(k,0,v_{s}[d-1],\ldots,v_{s}[k],\underbrace{0,\ldots,0}_{\text{d -
1}},v_{t}[k],\ldots,v_{t}[0],0,0)$

Furthermore, the following group element always exists in $A_{2}$:

$(-k,0,0,\ldots,0,v_{t}[k-1],\ldots,v_{t}[0],v_{s}[d-1],\ldots,v_{s}[k+1],0,\ldots,0,0)$

This means that the value
$(0,0,v_{s}[d-1],\ldots,v_{s}[0],v_{t}[d-1],\ldots,v_{t}[0],0)$ is obtainable
as a sum $a_{1}+a_{2}$. If on the other hand there is a path between $s$ and
$t$, then all elements in $A_{1}$ of the form

$(k,\star,v_{s}[d-1],\ldots,v_{s}[k],\underbrace{0,\ldots,0}_{\text{d -
1}},v_{t}[k],\ldots,v_{t}[0],0)$

must have $\star=1$ and thus it is not possible to write $z_{(s,t)}$ as
$a_{1}+a_{2}$.

#### The XOR Group.

For a reduction to the XOR group setting, we consider each element coordinate-
wise using their binary representations with the exception that in the first
coordinate the value is represented using the number’s complement
representation. Using the previous remark we also assert that for any pair
$a_{1}\in A_{1}$, $a_{2}\in A_{2}$, the only common digit that is both non-
zero is the most significant digit and thus the addition being done digit-
wise. For that reason, the sum behaves exactly the same way over the XOR group
as it does over the cyclic group that we have defined. Thus the size of the
universe and input sets $A_{1},A_{2}$ remain unchanged and the reduction holds
in the XOR group as well.

#### Analysis.

Now by setting $B=\frac{Sw^{2}}{n}$, note that $B=\Omega(w^{2})$ and:

$\displaystyle\lg(Sd/N)\leq\lg\left(\frac{SB\lg(n)}{n}\right)\leq\lg(SBw/n)\leq\lg(B^{2})=O(\lg
B)$

Furthermore, it holds that

$\displaystyle\lg(Sw/n)=\frac{1}{2}\lg((Sw/n)^{2})\geq\frac{1}{2}\lg(Sw^{2}/n)\geq\frac{1}{2}\lg
B$

Using Lemma 1, it then follows that for any cell-probe solution for $3$SUM-
Indexing for the cyclic group $([m],+\mod m)$ where $m=O(n^{2})$ and XOR group
$(\\{0,1\\}^{2\lg(n)+O(1)},\oplus)$ any static data structure that uses $S\geq
n$ cells of $w\geq\lg(n)$ bits has query time
$T=\Omega(d)=\Omega(\lg_{B}n)=\Omega(\lg n/\lg(Sw/n))$.

##  3 Reduction from Lopsided Set Disjointness

In this section, we prove Theorem 3, establishing hardness of $3$SUM-Indexing
also for abelian groups of size $\Delta=n^{1+\delta}$. For the proof, we focus
on the integers modulo $\Delta$, but remark that the proof readily adapts to
the XOR group as well.

For the proof, we use Pǎtraşcu’s Blocked Lopsided Set Disjointness (Blocked
LSD) problem. In this problem, there are two players, Alice and Bob. Bob
receives as input a set $Y$, which is an arbitrary subset of a universe
$[N]\times[B]$. Alice receives a set $X\subset[N]\times[B]$ with the
restriction that $X$ contains exactly one element $(i,b_{i})$ for every
$i=0,\dots,N-1$. The goal for Alice and Bob is to determine whether $X\cap
Y=\emptyset$ while minimizing communication. The following is known regarding
the communication complexity of Blocked LSD:

######  Lemma 2 (Theorem 4 of [24]).

Fix $\delta>0$. Any communication protocol for Blocked LSD requires either
Alice sending at least $\delta N\lg B$ bits, or Bob sending at least
$NB^{1-O(\delta)}$ bits.

The basic idea in the reduction, is to have Bob interpret his set $Y$ as two
input sets $A_{1},A_{2}$ of $n=NB$ group elements to $3$SUM-Indexing (we may
have $|A_{1}|$ and $|A_{2}|$ smaller than $NB$, but we can always pad with
dummy elements, so we assume $n=NB$). Given a data structure $D$ for $3$SUM-
Indexing, Bob then builds $D$ on this input. Alice on the other hand
interprets her set $X$ (which has cardinality $N$) as a set of $N/\ell$
queries to $3$SUM-Indexing, where $\ell$ is a parameter to be determined. The
key property of the reduction, is that the answers to all $N/\ell$ queries of
Alice on $D$, determines whether $X\cap Y=\emptyset$.

#### Communication Protocol.

Assume for now that we can give such a reduction. Alice and Bob then obtains a
communication protocol for Blocked LSD as follows: Let $T$ be the query time
of $D$. For $i=1,\dots,T$, Alice simulates the $i$’th step of the query
algorithm for each of her $N/\ell$ queries, _in parallel_. This is done by
asking Bob for the set of at most $N/\ell$ cells that they probe in the $i$’th
step. This costs $O(\lg\binom{S}{N/\ell})=O((N/\ell)\lg(S\ell/N))$ bits of
communication by specifying the required cells as a subset of the $S$ memory
cells of $D$. Bob replies with the contents of the cells, costing
$((N/\ell)w)$ bits. This is done for $T$ rounds, resulting in a communication
protocol where Alice sends $O((N/\ell)T\lg(S\ell/N))$ bits and Bob sends
$O((N/\ell)Tw)$ bits. If we fix $B=w^{4}$ and $\delta$ as a small enough
constant, then Lemma 2 says that either Alice sends $\Omega(N\lg w)$ bits or
Bob sends $\Omega(N\sqrt{B})=\Omega(Nw^{2})$ bits. In our protocol, Bob’s
communication is $O((N/\ell)Tw)=O(NTw)$ bits. We assume $w=\Omega(\lg n)$,
thus we conclude that either $NTw=\Omega(Nw^{2})\Rightarrow T=\Omega(\lg n)$,
or Alice’s communication must be $\Omega(N\lg B)=\Omega(N\lg w)$ bits. In the
first case, we are done with the proof, hence we examine the latter case.
Alice’s communication is $O((N/\ell)T\lg(S\ell/N))$ bits, which implies
$T=\Omega(\ell\lg w/\lg(S\ell/N))$. Thus to derive our lower bound, we have to
argue that it suffices for Alice to answer $N/\ell$ queries for a large enough
$\ell$.

#### Asking Few Queries.

We will show that it suffices for Alice to ask $N/\ell$ queries with
$\ell=\varepsilon\lg n/\lg w$. Here $\varepsilon>0$ is a small constant
depending on $\delta$ in the group size $\Delta=n^{1+\delta}$. Thus we get a
lower bound of $T=\Omega(\lg n/\lg((S\lg n)/(N\lg w)))$. Since
$N=n/B=n/w^{4}$, this simplifies to $T=\Omega(\lg n/\lg(Sw/n))$ as claimed in
Theorem 3.

Thus what remains is to show how Alice and Bob computes the input and queries.
For this, they conceptually partition the universe $[N]\times[B]$ into groups
$\\{i\ell,\dots,(i+1)\ell-1\\}\times[B]$ for $i=0,\dots,N/\ell$. Alice will
ask precisely one query for each such group. Denote by $Y_{i}$ the subset of
$Y$ that falls in the $i$’th group and denote by $X_{i}$ the subset of $X$
that falls in the $i$’th group. Clearly $X\cap Y=\emptyset$ if and only if
$X_{i}\cap Y_{i}=\emptyset$ for all $i$. Thus Alice will use her $i$’th query
to determine whether $X_{i}\cap Y_{i}=\emptyset$.

#### Constructing $A_{1}$ and $A_{2}$.

To support this, Bob first constructs the set $A_{1}$ based on his elements
$X$. He examines each group $X_{i}$, and for every $(j,b)\in X_{i}$, he adds
the integer $i(2B+1)^{\ell+1}+(b+1)(2B+1)^{j-i\ell}$ to $A_{1}$. Next, he
constructs the set $A_{2}$. For this, he considers all vectors
$Z=(b_{0},\dots,b_{\ell-1})$ for which the numbers are all between $0$ and $B$
and precisely one of them is $0$. He adds the integer
$\sum_{j\in[\ell]}b_{j}(2B+1)^{j}$ to $A_{2}$. This completes Bob’s
construction of the input sets $A_{1}$ and $A_{2}$. We have $|A_{1}|\leq NB=n$
and $|A_{2}|\leq(2B+1)^{\ell}$.

#### Asking the Queries.

We next describe how Alice translates her set $Y$ into queries. For each
$Y_{i}$, she needs to construct one query $z_{i}$ whose answer determines
whether $X_{i}\cap Y_{i}=\emptyset$. Recall that $Y_{i}$ is of the form
$\\{(i\ell,b_{0}),(i\ell+1,b_{1}),\dots,((i+1)\ell-1,b_{\ell-1})\\}$. She
starts by subtracting off $i\ell$ from the first index in each pair, obtaining
the set $\\{(0,b_{0}),(1,b_{1}),\dots,(\ell-1,b_{\ell-1})\\}$. Alice now asks
the query $z_{i}=i(2B+1)^{\ell+1}+\sum_{j=0}^{\ell-1}(b_{j}+1)(2B+1)^{j}$.

#### Correctness.

We claim that $z_{i}$ is part of a $3$SUM if and only if $X_{i}\cap
Y_{i}\neq\emptyset$. To see this, observe first that to write $z_{i}$ as
$a_{1}+a_{2}$, it must be the case that $a_{1}$ was constructed from $X_{i}$
as otherwise we cannot obtain the $i(2B+1)^{\ell+1}$ parts of $z_{i}$. Next,
observe that if we write the integers in base $2B+1$, then $A_{2}$ contains
precisely every integer of the form where there is a single digit $j\in[\ell]$
that is zero and all remaining are non-zero. Also, the numbers obtained from
$(j,b)\in X_{i}$ are of the form $i(2B+1)^{\ell+1}+(b+1)(2B+1)^{j-i\ell}$ and
thus have exactly one non-zero digit among the first $\ell$. Since $z_{i}$ has
exclusive non-zero digits in the first $\ell$, it follows that
$z_{i}=i(2B+1)^{\ell+1}+\sum_{j=0}^{\ell-1}(b_{j}+1)(2B+1)^{j}$ can be written
as $a_{1}+a_{2}$ if and only if $a_{1}$ was obtained from a $(j,b)\in X_{i}$
for which $b$ is equal to $b_{j-i\ell}$. This is the case if and only if
$X_{i}$ and $Y_{i}$ intersect in $(j,b)$.

#### Analysis.

We now determine $\ell$. Recall that $B=w^{4}$ and observe that all possible
integers are bounded by $N(2B+1)^{\ell+2}\leq n(2B+1)^{\ell+2}$. If we insist
on a group of size $\Delta=n^{1+\delta}$, this means we can set
$\ell=\delta\lg n/\lg(2B+1)-2\geq\varepsilon\lg n/\lg w$ for a sufficiently
small constant $\varepsilon>0$. This also implies that $|A_{2}|\leq
n^{\delta}\leq n$ and thus completes the proof of Theorem 3.

##  4 Lower Bound for Non-Adaptive Data Structures

In this section, we prove an $\Omega(\min\\{\lg|G|/\lg(Sw/n),n/w\\})$ lower
bound for non-adaptive $3$SUM-Indexing data structures when
$|G|=\omega(n^{2})$. Similarly to the previous approach by Golovnev et al.
[15], we use a cell sampling approach.

Consider a data structure using $S$ memory cells of $w$ bits and answering
queries non-adaptively in $T$ probes. Consider all subsets of $\Delta=n/(2w)$
memory cells. There are $\binom{S}{\Delta}$ such subsets. We say that a query
$z$ is answered by a set of cells $C$, if all the (non-adaptively chosen)
cells it probes are contained in $C$. Any query $z$ is answered by at least
$\binom{S-T}{\Delta-T}$ sets of $\Delta$ cells, namely all those containing
the $T$ cells probed on $z$. It follows by averaging over the $|G|$ queries
that there is a set of cells $C^{*}$ answering at least

$|G|\binom{S-T}{\Delta-T}/\binom{S}{\Delta}=|G|\frac{\Delta(\Delta-1)\cdots(\Delta-T+1)}{S(S-1)\cdots(S-T+1)}\geq|G|\left(\frac{\Delta-T+1}{S}\right)^{T}$

queries.

If $T\geq\Delta/2$, we are already done as we have proven $T=\Omega(n/w)$.
Otherwise, $T\leq\Delta/2$ and thus the above is at least
$|G|(\Delta/(2S))^{T}=|G|(n/(4Sw))^{T}$. If we assume for contradiction that
$T=o(\lg|G|/\lg(Sw/n))$, this is at least $|G|^{1-o(1)}>n$. Let $Q$ be the
group elements corresponding to an arbitrary subset of $n$ of those queries.
We argue that we can construct a distribution over inputs $A_{1},A_{2}$ such
that the queries $Q$ cannot be answered from few cells, contradicting that we
have answered them from $C^{*}$. More precisely, we show:

######  Lemma 3.

Let $(G,+)$ be an abelian group with $\omega(n^{2})$ elements. Given any
subset $Q\subseteq G$ of at most $n$ elements, there exists an input
distribution $D$ of $A_{1},A_{2}$ such that, all the events of the form
$q\in(A_{1}+A_{2})$ (defined as $\\{a_{1}+a_{2}:a_{1}\in A_{1},a_{2}\in
A_{2}\\}$) for all $q$ in $Q$ is fully independent. That is, for any subset
$S=\\{s_{1},s_{2}\ldots,s_{r}\\}$ of $Q$ of $r$ elements, and any sequence of
$r$ events $E_{1},E_{2},\ldots,E_{r}$ either of the form
$s_{i}\in(A_{1}+A_{2})$ or the form $s_{i}\notin(A_{1}+A_{2})$, it holds that
$\Pr[\bigwedge_{i=1}^{r}E_{i}]=\prod_{i=1}^{r}\Pr[E_{i}]$ . Furthermore, for
any $q\in Q$, it is the case that $\Pr_{(A_{1},A_{2})\sim
D}[q\in(A_{1}+A_{2})]=\frac{1}{2}$.

The proof is deferred to the end of the section.

We now use Lemma 3 to derive a contradiction to the assumption that
$T=o(\lg|G|/\lg(Sw/n))$. Concretely, we invoke the lemma with the $Q$ defined
above. This implies that the answers to the queries in $Q$ has entropy $n$
bits. However, they are being answered from a fixed set of $n/2w$ cells. These
cells together have $n/2$ bits. Since their addresses are fixed, their
contents must uniquely determine the $n$ query answers, yielding the
contradiction and hence $T=\Omega(\min\\{\lg|G|/\lg(Sw/n),n/w\\})$. This
completes the proof of Theorem 4. What remains is to prove Lemma 3:

#### Proof of Lemma 3.

We prove the lemma by first showing that given $Q\subseteq G$ of $n$ elements,
for any $P\subseteq Q$ there exists an input pair $A_{1}^{P}$ and $A_{2}^{P}$
such that $P\subseteq(A_{1}^{P}+A_{2}^{P})$ and $(Q\setminus
P)\cap(A_{1}^{P}+A_{2}^{P})=\emptyset$. That is to say that for every possible
subset $P$ of $Q$, there exists a pair of sets $(A_{1}^{P},A_{2}^{P})$ such
that $(A_{1}^{P}+A_{2}^{P})$ contains all the pair sums of $P$ and none of the
pair sums outside of $P$ and in $Q$. Then $D$ is the distribution that is
uniform over all possible pairs of sets $(A_{1}^{P},A_{2}^{P})$ with $P$
ranging over all subsets of $Q$. Another way to view $D$ is the distribution
that first randomly samples $P\subseteq Q$ before deterministically outputing
pairs of sets $(A_{1}^{P},A_{2}^{P})$.

Given any $P$, we build the sets $A_{1}^{P}$ and $A_{2}^{P}$ iteratively,
where they are both initially empty. Let $p_{1},p_{2},\ldots$ enumerate the
elements of $P$. At each iteration, let $p_{i}$ be the first value not in
$(A_{1}^{P}+A_{2}^{P})$. There are $\lvert G\rvert$ ordered pairs of elements
$(a_{1},a_{2})$ such that $a_{1}+a_{2}=p_{i}$. To see this, note that letting
$a_{1}=p_{i}+(-t)$ and $a_{2}=t$ for any $t\in G$ yields us a distinct pair of
elements for which the sum holds. We want to show that we can add $n$ pairs of
elements (thus enumerating all of the elements in $P$ and beyond) without ever
having any pair sum to an element in $(Q\setminus P)$. For each element
$q\in(Q\setminus P)$, and each element in $a\in A_{1}$, there is exactly one
element $b\in G$ such that $a+b=q$ (likewise for each element $a\in A_{2}$).
Therefore, for any given $q$, there are $\lvert A_{1}\rvert$ elements $b\in G$
that if added into set $A_{2}$, would imply that $q\in(A_{1}+A_{2})$ (likewise
for set $A_{2}$). Since $\lvert Q\setminus P\rvert\leq n$, and at every
iteration $\lvert A_{1}\rvert=\lvert A_{2}\rvert\leq n$, we have that there
are at most $2n^{2}$ elements that cannot be added into either set $A_{1}$ or
set $A_{2}$ (otherwise sets $(Q\setminus P)$ and $(A_{1}+A_{2})$ are no longer
disjoint).

Therefore there must still exist a pair $(a_{1},a_{2})$ such that
$a_{1}+a_{2}=p_{i}$ and $(\\{a_{1}\\}\cup A_{1}^{P}+\\{a_{2}\\}\cup
A_{2}^{P})\cap(Q\setminus P)=\emptyset$, assuming that $\lvert
G\rvert=\omega(n^{2})$. In the case that every element in $P$ is enumerated
before we have added $n$ pairs, we can still pad with more arbitrary pairs of
elements from $G$ whilst avoiding creating any element in $(Q\setminus P)$ for
the same reason as laid out above.

It remains to show that our distribution $D$ indeed witnesses full
independence and that each individual event occurs with probability
$\frac{1}{2}$. Let $S$ be an arbitrary subset of $Q$ of size $r\leq n$.
Further, let $E_{i}$ be either the event that $s_{i}\in(A_{1}+A_{2})$ or
$s_{i}\notin(A_{1}+A_{2})$, and let $S^{\prime}\subseteq S$ contain the
elements $s_{i}$ such that $E_{i}$ is the event that $s_{i}\in(A_{1}+A_{2})$
(so $S\setminus S^{\prime}$ is precisely the set of elements $s_{i}$ for which
there is the event $s_{i}\notin(A_{1}+A_{2})$). In the support of $D$, there
are exactly $2^{n}$ pairs of sets $(A_{1}^{P},A_{2}^{P})$, each realising a
distinct subset $P\subseteq Q$ of elements such that $P\subseteq(A_{1}+A_{2})$
and $(Q\setminus P)\cap(A_{1}+A_{2})=\emptyset$. Thus, given any set
$S^{\prime}\subseteq S\subseteq Q$, there are $2^{n-r}$ pairs of sets
$(A_{1}^{P},A_{2}^{P})$ each with for set $P$ such that $S^{\prime}\subseteq
P$ and $(S\setminus S^{\prime})\subseteq(Q\setminus P)$. Thus we argue that

$\Pr\left[\bigwedge_{i=1}^{r}E_{i}\right]=\frac{2^{n-r}}{2^{n}}=2^{-r}.$

Note that for individual events, we can take the subset $S$ to contain only a
single element $q$ from $Q$ and the above argument would imply that
$\Pr[q\in(A_{1},A_{2})]=\frac{1}{2}$ and that
$\Pr[q\notin(A_{1},A_{2})]=\frac{1}{2}$. Thus the conclusion readily follows
from the fact that

$\prod_{i=1}^{r}\Pr\left[E_{i}\right]=2^{-r}.$

##  5 Bit Probe Lower Bound for $3$SUM-Indexing

In this section we give the bit probe lower bound for $3$SUM-Indexing stated
in Theorem 5.

The proof idea is based on an incompressibility argument. We will inspect the
way the queries are structured and construct a specific input distribution
that the data structure algorithm end up using too few bits for and therefore
derive a contradiction. For this, we will again use Lemma 3 from the previous
section. The key difference between this proof and the proof in the previous
section, lies in how we find a set of queries answered by too few cells.
Moreover, in this proof, we will derive a contradiction even with $m$ queries
being answered by $m$ cells, and thus intuitively the cells actually have
enough information, but yet cannot answer the queries. We start by introducing
some graph theory that we need:

######  Lemma 4.

[Theorem 1 of [2]] Let $(V,E)$ be a graph with $n$ nodes, average degree $d>2$
and girth $r$. Then $n\geq 2(d-2)^{r/2-2}$.

From Lemma 4 we conclude that for a graph with $o(\lvert G\rvert)$ nodes and
$\lvert G\rvert$ edges, it is the case that the graph has a girth of
$O(\lg(n))$. To see this, note that the average degree $d$ of such a graph is
$\omega(1)$ and thus it follows that for some constant $c>1$:

$\displaystyle o(\lvert G\rvert)\geq 2(d-2)^{r/2-2}$
$\displaystyle\Rightarrow$ $\displaystyle o(\lvert G\rvert)\gg 2(c)^{r/2}$
$\displaystyle\Rightarrow$ $\displaystyle r\in O(\lg_{c}(n))$

Given any non-adaptive pre-processing algorithm with $T=2$, $S=o(\lvert
G\rvert)$, and $w=1$, define $V$ to be the set of $S$ nodes each representing
a memory cell and let $E$ be the set of edges such that an edge $e_{g}=(u,v)$
is in the edge set if and only there exists some group element $g\in G$ such
that the querying algorithm on input $g$ accesses both memory cell $u$ and
$v$. Furthermore, associate with each edge $e_{g}$ a function
$f_{g}:\\{0,1\\}^{2}\to\\{0,1\\}$ that defines the output behaviour of the
querying algorithm upon reading the bits at node $u$ and $v$. We broadly
categorise the possible functions $f_{g}$ into $4$ types:

  1. 1.

Copy type functions. The type of functions $f_{g}$ that depend only one of its
two inputs. There are $4$ of such functions.

  2. 2.

Constant type functions. The type of functions $f_{g}$ that are completely
independent of its two inputs. There are $2$ such functions.

  3. 3.

AND type functions. The type of functions $f_{g}$ whose truth table is such
that exactly $3$ of the $4$ possible inputs leads to the same output where the
last input differs. There are $8$ such functions.

  4. 4.

XOR type functions. The type of functions $f_{g}$ that are either the XOR of
its $2$ inputs or the negation of the XOR of its $2$ inputs. There are $2$
such functions.

Note that none of the edges can be the constant type, since this means that
the querying algorithm’s answer is independent of the input set. Also, by an
averaging argument there is at least one type of function that $\Omega(\lvert
G\rvert)$ edges are associated with. Furthermore, Lemma 3 asserts that there
can be at most $2$ edges that are parallel to each other, otherwise we can
construct an input distribution $D$ such that the data structure manages to
use $2$ bits to encode the outcome of a random variable that has Shannon
entropy at least $3$, which is a contradiction. Thus there are $\Omega(\lvert
G\rvert)$ many edges that are not parallel to each other and are all of the
same type. We analyse the different types separately. We start with the
simplest COPY type:

(COPY type) Assuming that there are $\Omega(\lvert G\rvert)$ edges that are
associated with the copy type function, there must exist at least one node $u$
such that $\omega(1)$ edges $e_{g}$ are such that the associated function
$f_{g}$ depend only on the bit at this node. Letting $Q$ contain two such
group elements, this yields a contradiction using Lemma 3 to construct a
distribution over $A_{1}$ and $A_{2}$ such that the entropy of the two query
answers in $Q$ is $2$ bits.

For the remaining types, we look for a short cycle. Using Lemma 4, we get that
there is a cycle of $O(\lg n)$ length using only edges associated with
functions of the same type. Denote by $Y$ the set of group elements $g$ such
that $e_{g}$ is in the cycle and $y_{1},\ldots,y_{t}$ enumerates the elements
of $Y$ based on a traversal of the cycle. That is, the edge corresponding to
$y_{i}$ shares endpoints with edges corresponding to $y_{i-1}$ and $y_{i+1}$,
where $y_{t+1}=y_{1}$ and $y_{0}=y_{t}$. We use Lemma 3 with $Q=Y$ to get a
distribution $D$ over $(A_{1},A_{2})$ such that the answers to queries in $Y$
are independent and they are all uniform random. We now handle the two
remaining types separately.

(AND type) Let $b$ be the output of $f_{y_{1}}$ that is only obtainable by
exactly $1$ of the $4$ possible inputs. Consider the distribution $D$
conditioned on the event that $\mathbbm{1}\\{{y_{1}\in(A_{1}+A_{2})}\\}=b$.
Since only $1$ of the $4$ inputs to $f_{y_{1}}$ is consistent with this
output, this fixes the two input bits to $f_{y_{1}}$. Therefore, there are
$t-2$ bits left to encode $t-1$ independent and fully random outputs (namely,
whether $y_{2},\ldots,y_{t}$ are in $A_{1}+A_{2}$), which yields us the
desired contradiction.

(XOR type) Let $(A_{1},A_{2})\sim D$ be drawn from the input distribution
constructed using Lemma 3 with $Q=Y$. Let the endpoints of $y_{i}$ be
$u_{i},v_{i}$, such that $v_{t}=u_{1}$. Note for all $i$, it is necessarily
the case that $\mathbbm{1}\\{{y_{i}\in(A_{1}+A_{2})}\\}=u_{i}\oplus v_{i}$ or
$\mathbbm{1}\\{{y_{i}\in(A_{1}+A_{2})}\\}=1\oplus u_{i}\oplus v_{i}$. Then
$\bigoplus_{2}^{t}\mathbbm{1}\\{{y_{i}\in(A_{1}+A_{2})}\\}$ is either
$u_{1}\oplus v_{1}$ or $1\oplus u_{1}\oplus v_{1}$ which means that
$\mathbbm{1}\\{{y_{1}\in(A_{1}+A_{2})}\\}$ is either
$\bigoplus_{2}^{t}\mathbbm{1}\\{{y_{i}\in(A_{1}+A_{2})}\\}$ or its negation.
Then Lemma 3 yields the desired contradiction.

##  6 Acknowledgments

The author Eldon Chung would like to thank Thomas Tan for the helpful
discussions with regards to the proof for theorem 5.

## References

  * [1] A. Abboud and K. Lewi.  Exact weight subgraphs and the k-sum conjecture.  In F. V. Fomin, R. Freivalds, M. Z. Kwiatkowska, and D. Peleg, editors, Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, volume 7965 of Lecture Notes in Computer Science, pages 1–12. Springer, 2013.
  * [2] N. Alon, S. Hoory, and N. Linial.  The moore bound for irregular graphs.  Graphs and Combinatorics, 18(1):53–57, 2002.
  * [3] S. Alstrup, T. Husfeldt, and T. Rauhe.  Marked ancestor problems.  In 39th Annual Symposium on Foundations of Computer Science, FOCS ’98, November 8-11, 1998, Palo Alto, California, USA, pages 534–544. IEEE Computer Society, 1998.
  * [4] A. Amir, T. M. Chan, M. Lewenstein, and N. Lewenstein.  On hardness of jumbled indexing.  In J. Esparza, P. Fraigniaud, T. Husfeldt, and E. Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, volume 8572 of Lecture Notes in Computer Science, pages 114–125. Springer, 2014.
  * [5] G. Barequet and S. Har-Peled.  Polygon containment and translational min-hausdorff-distance between segment sets are 3sum-hard.  Int. J. Comput. Geom. Appl., 11(4):465–474, 2001.
  * [6] J. Boninger, J. Brody, and O. Kephart.  Non-adaptive data structure bounds for dynamic predecessor.  In S. V. Lokam and R. Ramanujam, editors, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017, December 11-15, 2017, Kanpur, India, volume 93 of LIPIcs, pages 20:1–20:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
  * [7] G. S. Brodal and K. G. Larsen.  Optimal planar orthogonal skyline counting queries.  In R. Ravi and I. L. Gørtz, editors, Algorithm Theory - SWAT 2014 - 14th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2-4, 2014. Proceedings, volume 8503 of Lecture Notes in Computer Science, pages 110–121. Springer, 2014.
  * [8] J. Brody and K. G. Larsen.  Adapt or die: Polynomial lower bounds for non-adaptive dynamic data structures.  Theory Comput., 11:471–489, 2015.
  * [9] T. M. Chan.  More logarithmic-factor speedups for 3sum, (median, +)-convolution, and some geometric 3sum-hard problems.  In A. Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 881–897. SIAM, 2018.
  * [10] E. D. Demaine and S. P. Vadhan.  Some notes on 3sum.  Unpublished manuscript, December 2001.
  * [11] Z. Dvir, A. Golovnev, and O. Weinstein.  Static data structure lower bounds imply rigidity.  In M. Charikar and E. Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 967–978. ACM, 2019.
  * [12] A. Fiat and M. Naor.  Rigorous time/space tradeoffs for inverting functions.  In C. Koutsougeras and J. S. Vitter, editors, Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA, pages 534–541. ACM, 1991.
  * [13] A. Gajentaan and M. H. Overmars.  On a class of o(n${}^{\mbox{2}}$) problems in computational geometry.  Comput. Geom., 45(4):140–152, 2012.
  * [14] I. Goldstein, T. Kopelowitz, M. Lewenstein, and E. Porat.  Conditional lower bounds for space/time tradeoffs.  In F. Ellen, A. Kolokolova, and J. Sack, editors, Algorithms and Data Structures - 15th International Symposium, WADS 2017, St. John’s, NL, Canada, July 31 - August 2, 2017, Proceedings, volume 10389 of Lecture Notes in Computer Science, pages 421–436. Springer, 2017.
  * [15] A. Golovnev, S. Guo, T. Horel, S. Park, and V. Vaikuntanathan.  Data structures meet cryptography: 3sum with preprocessing.  In K. Makarychev, Y. Makarychev, M. Tulsiani, G. Kamath, and J. Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 294–307. ACM, 2020.
  * [16] M. Greve, A. G. Jørgensen, K. D. Larsen, and J. Truelsen.  Cell probe lower bounds and approximations for range mode.  In S. Abramsky, C. Gavoille, C. Kirchner, F. M. auf der Heide, and P. G. Spirakis, editors, Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I, volume 6198 of Lecture Notes in Computer Science, pages 605–616. Springer, 2010.
  * [17] M. Henzinger, S. Krinninger, D. Nanongkai, and T. Saranurak.  Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture.  In R. A. Servedio and R. Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 21–30. ACM, 2015.
  * [18] T. Kopelowitz, S. Pettie, and E. Porat.  Higher lower bounds from the 3sum conjecture.  In R. Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1272–1287. SIAM, 2016.
  * [19] K. G. Larsen.  The cell probe complexity of dynamic range counting.  In H. J. Karloff and T. Pitassi, editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 85–94. ACM, 2012.
  * [20] K. G. Larsen.  Higher cell probe lower bounds for evaluating polynomials.  In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 293–301. IEEE Computer Society, 2012.
  * [21] K. G. Larsen, J. L. Starup, and J. Steensgaard.  Further unifying the landscape of cell probe lower bounds.  In H. V. Le and V. King, editors, 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11-12, 2021, pages 224–231. SIAM, 2021.
  * [22] K. G. Larsen, O. Weinstein, and H. Yu.  Crossing the logarithmic barrier for dynamic boolean data structure lower bounds.  SIAM J. Comput., 49(5), 2020.
  * [23] M. Patrascu.  Towards polynomial lower bounds for dynamic problems.  In L. J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 603–610. ACM, 2010.
  * [24] M. Patrascu.  Unifying the landscape of cell-probe lower bounds.  SIAM J. Comput., 40(3):827–847, 2011.
  * [25] S. N. Ramamoorthy and A. Rao.  Lower Bounds on Non-Adaptive Data Structures Maintaining Sets of Numbers, from Sunflowers.  In R. A. Servedio, editor, 33rd Computational Complexity Conference (CCC 2018), volume 102 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1–27:16, Dagstuhl, Germany, 2018. Schloss Dagstuhl–Leibniz-Zentrum für Informatik.
  * [26] C. Sommer, E. Verbin, and W. Yu.  Distance oracles for sparse graphs.  In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 703–712. IEEE Computer Society, 2009.
  * [27] M. A. Soss, J. Erickson, and M. H. Overmars.  Preprocessing chains for fast dihedral rotations is hard or even impossible.  Comput. Geom., 26(3):235–246, 2003.
  * [28] E. Viola.  Lower bounds for data structures with space close to maximum imply circuit lower bounds.  Theory Comput., 15:1–9, 2019.
  * [29] A. C. Yao.  Should tables be sorted?  J. ACM, 28(3):615–628, 1981.


# Relation-aware Heterogeneous Graph for User Profiling

Qilong Yan1,2111Equal contribution., Yufeng Zhang1111Equal contribution.,
Qiang Liu1,2, Shu Wu1,2222Corresponding author. and Liang Wang1,2
1Center for Research on Intelligent Perception and Computing, Institute of
Automation, Chinese Academy of Sciences
2School of Artificial Intelligence, University of Chinese Academy of Sciences
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>

(2021)

###### Abstract.

User profiling has long been an important problem that investigates user
interests in many real applications. Some recent works regard users and their
interacted objects as entities of a graph and turn the problem into a node
classification task. However, they neglect the difference of distinct
interaction types, e.g. user clicks an item v.s. user purchases an item, and
thus cannot incorporate such information well. To solve these issues, we
propose to leverage the relation-aware heterogeneous graph method for user
profiling, which also allows capturing significant meta relations. We adopt
the query, key, and value mechanism in a transformer fashion for heterogeneous
message passing so that entities can effectively interact with each other. Via
such interactions on different relation types, our model can generate
representations with rich information for the user profile prediction. We
conduct experiments on two real-world e-commerce datasets and observe a
significant performance boost of our approach.

User Modeling, Deep Learning, Graph Neural Networks, Heterogeneous Information
Networks, Representation Learning

††copyright: acmcopyright††journalyear: 2021††doi:
10.1145/3459637.3482170††conference: Proceedings of the 30th ACM International
Conference on Information and Knowledge Management; November 1–5, 2021;
Virtual Event, Australia.††booktitle: Proceedings of the 30th ACM Int’l Conf.
on Information and Knowledge Management (CIKM ’21), November 1–5, 2021,
Virtual Event, Australia††price: 15.00††isbn: 978-1-4503-8446-9/21/11††ccs:
Computing methodologies Information extraction

##  1\. Introduction

Nowadays, users from all kinds of applications have been producing an ocean of
data as they browse the internet. Such data potentially contain valuable
information, such as user’s interest, trait, and behaviour pattern, for
providing them with personalised services. The scenario is typically named
user profiling. Taking (Rao et al., 2010) as an example, they first propose to
predict user’s gender, age, area, and political tendency by modelling their
twitters from social networks. Recent works expand the task purpose to a
broader scope, including occupation (Zhao et al., 2019), geolocation (Rahimi
et al., 2018), ideology (Xiao et al., 2020), and race (Preoţiuc-Pietro and
Ungar, 2018).

Figure 1. The heterogenerous graph with multiple types of entities and
relations for user profiling. Best view in colour.

In user profiling, an intuitive way is to model the user’s interaction
behaviour with graphs. Despite the success of traditional deep learning
approaches (Rao et al., 2010; Nguyen et al., 2013; Farnadi et al., 2018),
graph methods are highlighting their advantages on non-euclidean relations in
such tasks (Wu et al., 2019a; Yu et al., 2020; Zhang et al., 2020b, a; Li et
al., 2020; Zhang et al., 2021b, a). Rahimi et al. (2018); Chen et al. (2019);
Xiao et al. (2020) regard users with co-relation (like co-purchase in
e-commerce) as a graph with entities and hierarchically pump the heterogeneous
information up from the attribute with graph attention networks. In addition
to the interaction, the semantic of entities is also important. For example,
items usually possess the description of their category and brand, and
advertisements have that of their sponsor and campaign, which are unified as
side information (Liu et al., 2021). Chen et al. (2019) apply the words of the
title as entities to represent the side information.

Figure 2. The overall architecture of the relation-aware heterogeneous graph
network. Suppose an edge $e$ links a source node $s$ and a target node $t$,
denote its meta relation as $\langle\tau(s),\phi(e),\tau(t)\rangle$. The
representation $H_{t}$ of the user is obtained by collecting the neighbourhood
messages.

However, two problems remain untouched in existing works. First, previous
studies oversimplify the relations between entities and merely count on the
binary association (with and without interaction). In real-world scenarios,
users generally interact with other objects with multiple behaviours, e.g.
they can click, like, or purchase items on a typical shopping platform. We
argue that different behaviours may contribute to different intentions and the
degree of favour. A ‘click’ is naturally a less strong association than a
‘like’ or ‘purchase’. Second, the side information is insufficiently
considered so far. Only titles of the item are deemed as attributes, whereas
other types, such as categories and brands, are dismissed. Simply integrating
more types of side information into the graph may not be sound since they
expect different semantic space when doing attention operations. Actual
experiments have proved that they do not produce satisfactory results.

The core issue mentioned above is that most works are based on a single type
of entity and relation, but more information needs to be uncovered by
different types. To that end, we propose Relation-aware Heterogeneous Graph
Network for user profiling (RHGN) that can model multiple relations on the
heterogeneous graph. In contrast to the single relation graph by previous
approaches, we adopt a graph with various relations between different types of
entities, as illustrated in Figure 1. We also design a heterogeneous graph
propagation network that aggregates information from multiple sources. A
transformer-like multi-relation attention (Vaswani et al., 2017; Hu et al.,
2020) is employed to learn the importance between nodes and reveal the meta-
relation significance on the graph. We validate our model on two real-world
user profiling datasets. The experimental result shows that our approach
significantly advances the prediction for user profiles. The main
contributions of this paper are as follows:

  * •

We first propose the heterogeneous graph with multiple types of relations and
entities for user profiling.

  * •

We adopt a heterogeneous graph propagation network to acquire heterogeneous
information from multiple sources.

  * •

We use heterogeneous multi-relation attention to automatically reveal the
meta-relation significance on the graph.

##  2\. Relation-aware Heterogeneous Graph Networks

In this section, we formulate the user profiling problem and introduce our
approach to address the multi-source information extraction on the
heterogeneous graph. As illustrated in Figure 2, the model consists of three
segments: Neighbourhood Message Passing, Multi-Relation Attention, and Target
State Update.

###  2.1. Problem Statement

Given a collection of users’ behaviours and properties, user profiling aims to
predict their labels, such as age and gender. We present the entities and
relations as a directed heterogeneous graph
$\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{A},\mathcal{R})$, where nodes
$v\in\mathcal{V}$ and edges $e\in\mathcal{E}$ can be mapped into their types
by function $\tau(v):V\rightarrow\mathcal{A}$ and
$\phi(e):E\rightarrow\mathcal{R}$, respectively. In the case of e-commerce,
$\tau(v)$ typically has types ‘user’, ‘item’, ‘advertisement’, and
‘attribute’, and $\phi(e)$ has types ‘click’, ‘purchase’, and ‘has_attribute’,
as illustrated in Figure 1. Suppose an edge $e$ links a source node $s$ and a
target node $t$, denote its meta relation as
$\langle\tau(s),\phi(e),\tau(t)\rangle$. The meta relation generally reflects
different interaction intentions between entities.

Note that in real situations, labels for the user are usually limited. Semi-
supervised learning is thus required by using a large number of unlabelled
data.

###  2.2. Neighbourhood Message Passing

To obtain the representation $H$ of users, it is necessary to collect their
neighbourhood messages, that is, the items they have interacted with. They, to
a large extent, exhibit one’s interest and concern. Similarly, items should
learn from their neighbourhood users and attributes. Formally, for a triplet
of a target node $t$, its neighbour node $s\in N(t)$, and an edge relation
$e=(s,t)$, we calculate the message to pass in the $l$-th layer as:

(1) $M(s,e,t)=\mathop{\parallel}\limits_{i\in[1,h]}M\mathchar 45\relax
head^{i}(s,e,t)\\\ \vspace{-2mm}$ $M\mathchar 45\relax
head^{i}(s,e,t)=F^{i}_{M}\left(H^{l}[s]\right)W^{MSG}_{\phi(e)}\\\ $

where $\parallel$ denotes the concatenation operation, $F^{i}_{M}$ is the
$i$-th multi-head linear function, $h$ is the number of heads, and
$W^{MSG}_{\phi(e)}$ is a matrix that projects the message into a relation-
dependent space. By keeping a distinct $W^{MSG}_{\phi(e)}$ for each meta
relation $\langle\tau(s),\phi(e),\tau(t)\rangle$, our model can better
distinguish different intentions between the source and the target with
various types of interaction, e.g. click and purchase.

Table 1. The comparison between various models on the two datasets. Model | JD-dataset | Alibaba-dataset
---|---|---
Gender-Acc | Gender-F1 | Age-Acc | Age-F1 | Gender-Acc | Gender-F1 | Age-Acc | Age-F1
GCN | 40.60 | 28.88 | 51.83 | 17.80 | 78.81 | 45.48 | 32.14 | 14.34
GAT | 77.52 | 75.85 | 51.45 | 25.52 | 79.09 | 47.75 | 34.89 | 16.70
RGCN | 60.30 | 56.40 | 45.10 | 17.10 | 78.00 | 69.96 | 36.94 | 22.28
HGCN | 80.00 | 79.33 | 52.82 | 25.77 | 80.97 | 63.82 | 41.55 | 26.78
(+info) | 78.10 | 77.52 | 52.30 | 23.74 | 80.56 | 63.27 | 41.23 | 26.12
HGAT | 80.20 | 79.40 | 51.70 | 19.46 | 79.89 | 64.27 | 36.72 | 21.76
(+info) | 78.74 | 78.05 | 51.40 | 17.13 | 79.12 | 63.70 | 35.16 | 20.58
RHGN | 80.44 | 79.18 | 54.70 | 33.95 | 83.00 | 77.73 | 43.80 | 29.60

###  2.3. Multi-Relation Attention

Like many sorts of research demonstrated (Rahimi et al., 2018; Chen et al.,
2019), not all neighbourhood messages are necessarily essential for the target
node. For example, the model may need to pay more attention to which item the
user bought rather than which advertisement they viewed. We thus adopt an
attention weight to rescale the significance of each message. In formal, we
project the source node and the target node into a Key vector and a Query
vector, respectively, and measure their similarity as:

(2) $\vspace{-3mm}\alpha(s,e,t)=\mathop{\rm softmax}\limits_{\forall s\in
N(t)}\left(\mathop{\parallel}\limits_{i\in[1,h]}\alpha\mathchar 45\relax
head^{i}\left(s,e,t\right)\right)\\\ $ $\alpha\mathchar 45\relax
head^{i}(s,e,t)=\left(K^{i}(s)W^{ATT}_{\phi(e)}Q^{i}(t)^{T}\right)\cdot\frac{1}{\sqrt{d}}\\\
\vspace{-1mm}$ $K^{i}(s)=F^{i}_{K}(H^{l}[s])\vspace{-1mm}$
$Q^{i}(t)=F^{i}_{Q}(H^{l}[t])$

where $F^{i}_{K}$ and $F^{i}_{Q}$ are the $i$-th multi-head linear function
for the Key vector and the Query vector, respectively, $W^{ATT}_{\phi(e)}$ is
a projection matrix, and $d$ is the dimension of the vector. The architecture
resembles Transformer (Vaswani et al., 2017), and $\sqrt{d}$ is also used to
smooth the dot product of the Key vector and the Query vector. However, the
vanilla Transformer calculates the dot product with the same set of parameters
for all inputs, which does not consider the effect of multiple associations.
The additional weight $W^{ATT}_{\phi(e)}$ here can help the model reassign
attentions according to different meta relations.

###  2.4. Target State Update

After propagating the messages and their attentions to the target node, we
assemble them to update the target node embedding. We define the update
formulation as:

(3)
$H^{l+1}[t]=F_{map}\left(\sigma(\hat{H}^{l}[t])\right)+H^{l}[t]\vspace{-2mm}$
$\hat{H}^{l}[t]=\mathop{\oplus}\limits_{\forall s\in
N(t)}\left(\alpha\left(s,e,t\right)\cdot M\left(s,e,t\right)\right)$

where $F_{map}$ is a linear function that maps the message back to the target
feature distribution, and $\sigma$ denotes the activation function. As the
attention $\alpha(s,e,t)$ is normalised by the softmax procedure
($\sum_{\forall s\in N(t)}\alpha(s,e,t)=1_{h\times 1}$), it can be directly
applied to the message $M(s,e,t)$ without affecting its distribution. Through
stacking the graph layer and the residual connection, each node can reach
$L$-hop neighbours. For example, a user can receive messages from other users
who may share similar interest and behaviour, though they are not connected.

###  2.5. Training

The final step involves classifying the user representation in the last layer
into profile labels. Formally, we employ a single linear classifier and
optimize the model with cross-entropy as:

(4)
$\mathcal{L}=-\sum\limits_{t\in\mathcal{V}^{\prime}}\sum\limits^{P}_{p=1}Y_{tp}{\rm
log}(Z_{tp})\vspace{-2mm}$ $Z={\rm softmax}\left(F_{out}(H^{L}[t])\right)$

where $\mathcal{V}^{\prime}$ denotes the labelled user node set, $P$ denotes
the total number of profile labels, and $Y$ denotes the ground truth.

##  3\. EXPERIMENTS

In this section, we conduct experiments on two real-world datasets to evaluate
our proposed method.

###  3.1. Datasets

To examine the actual performance of our proposed method, we select two public
large-scale user profiling datasets in real scenes: JD-
dataset111https://github.com/guyulongcs/IJCAI2019_HGAT and Alibaba-
dataset222https://tianchi.aliyun.com/dataset/dataDetail?dataId=56, two of the
most popular e-commerce portals in China. For each dataset, the heterogeneous
graphs are extracted with multiple relations between users, items (or
advertisements), and attributes. In consistency with (Chen et al., 2019), we
use the user’s gender and age as the label of their profiles. In the JD-
dataset, users and items have ‘click’ and ‘purchase’ relations, and attributes
include four category descriptions of items. In the Alibaba-dataset, users and
items have four relations - ‘click’, ‘purchase’, ‘favorite’, and ‘shopping
cart’; users and advertisements have ‘view’ relations; items and
advertisements have ‘promotion’ relations; and attributes have three types of
basic information of advertisements, including category ID, campaign ID, and
sponsor ID.

###  3.2. Baselines

We consider both classical and state-of-the-art graph methods as baselines:
(1) GCN (Kipf and Welling, 2017) and GAT (Veličković et al., 2017) are two
representative and strong baselines on many tasks, that are based on
homogeneous graphs and do not take mutiple types of relations and entities
into account; (2) RGCN (Schlichtkrull et al., 2018) refers to Relational GCN.
It splits the graph into several sub-graphs according to different types of
relations and uses parallel GCN layers for each sub-graph; (3) HGCN and HGAT
(Chen et al., 2019) are two state-of-the-art methods. They regard the node as
heterogeneity. However, they lack the distinction between relation types. They
also dismiss some important side information; (4) We further extend HGCN and
HGAT with (+info) to investigate whether they gain benefit from more side
information. We add side information under the same attention distribution of
their model.

Table 2. Ablation study on the JD-dataset Model | Gender-Acc | Gender-F1 | Age-Acc | Age-F1
---|---|---|---|---
RHGN | 80.44 | 79.18 | 54.70 | 33.95
w/o U-I relations | 78.99 | 77.56 | 54.62 | 31.01
w/o I-A relations | 75.95 | 74.24 | 52.69 | 30.23

###  3.3. Experimental Setup

We implement our RHGN in the PyTorch framework for efficient GPU computation.
In the experiment, we randomly split labelled users into a training set, a
validation set, and a test set with the ratio 75 : 12.5 : 12.5 (Qiu et al.,
2018; Chen et al., 2019). The embedding for users and items is randomly
initialized, whereas that for attributes is initialized by their content via
Fasttext (Armand Joulin and Mikolov, 2017). We adopt the grid-search strategy
to find the optimal parameter combination for our model. The entity-level
aggregation network has two layers with the hidden dimension in {32, 64, 128,
256}. The number of heads in multi-head attention is searched in {1, 2, 4, 8,
16}. All models are optimized via the AdamW optimizer with the One Cycle
Learning Rate Scheduler. The learning rate, weight decay, and mini-batch size
are set to 0.001, 0.01, 512, respectively. We use GELU (Hendrycks and Gimpel,
2016) as our activation function. The implementation of all baselines follow
their original paper.

There are two node classification tasks: the gender prediction (binary
classification task) and the age prediction (multi-class classification task).
We evaluate the models with Accuracy and Macro-F1 (Wu et al., 2019b; Chen et
al., 2019), which are widely used in user profiling problems.

###  3.4. Results

Table 1 displays the experimental results of different methods on the two
datasets. We observe that our model significantly boost the performance of
most tasks. In particular, our model presents an averagely higher performance
gain on the Alibaba dataset than that on the JD dataset. It is reasonable
because the Alibaba dataset contains more diverse interaction behaviours,
which carries richer user intentions. By modelling distinct meta relations,
our model can intrinsically extract more information than the baselines.

The result also shows that HGCN and HGAT outperform vanilla GCN and GAT,
implying that the task benefits from the heterogeneous node types.
Nevertheless, they do not improve further by incorporating more side
information. It is probably because they project different types of side
information into the same distribution so that they cannot discriminate the
impact of each.

Overall, the experiment indicates that it is necessary to consider multiple
types of meta relations in user profiling, and our approach can leverage such
information to provide better services.

Figure 3. An example from the JD-dataset. Visualizing the significance of
distinct relation types with different items for opposite genders.

###  3.5. Ablation Study

To investigate the individual effectiveness of user-item multi-relation and
item-attribute (side information) multi-relation, we carry out ablation study
experiments on them. Specifically, we modify RHGN by consolidating user-item
attention (w/o U-I relations) and item-attribute relations (w/o I-A
relations), respectively. As demonstrated in Table 2, the result shows both
individuals can improve the performance compared with original model,
suggesting that either multi-relation can contribute to the task. In addition,
the item-attribute relation yields a higher performance influence than the
user-item relation. It is a plausible phenomenon since side information
contains category semantics that can reflect user intentions.

###  3.6. Case Study

To understand how the meta relation impacts the prediction for user profiles,
we visualize the attention score between two users (a male and a female) and
their interacted items, as illustrated in Figure 3. According to different
user genders, the attention score exhibits different significances in terms of
the item category and interactive relation. It is worth noting that the
‘click’ relation of some gender-oriented items are more biased than the
‘purchase’ relation of some neutral items.

##  4\. Conclusion

In this paper, we proposed a heterogeneous graph with multiple entities and
relations for user profiling. We also adopted a relation-aware heterogeneous
graph network to learn the meta relation significance on such a graph. Through
experiments on real large datasets, we found incorporating more types of
entities and relations is generally beneficial for capturing user’s intentions
and predicting their profile labels. Further studies demonstrate the
interpretability of RHGM with different meta relation attention weights.

## Acknowledgments

This work is supported by National Key Research and Development Program
(2019QY1601, 2019QY1600), National Natural Science Foundation of China
(61772528).

## References

  * (1)
  * Armand Joulin and Mikolov (2017) Edouard Grave Armand Joulin and Piotr Bojanowski Tomas Mikolov. 2017\.  Bag of tricks for efficient text classification. In _EACL_.
  * Chen et al. (2019) Weijian Chen, Yulong Gu, Zhaochun Ren, Xiangnan He, Hongtao Xie, Tong Guo, Dawei Yin, and Yongdong Zhang. 2019\.  Semi-supervised User Profiling with Heterogeneous Graph Attention Networks.. In _IJCAI_ , Vol. 19. 2116–2122.
  * Farnadi et al. (2018) Golnoosh Farnadi, Jie Tang, Martine De Cock, and Marie-Francine Moens. 2018.  User profiling through deep multimodal fusion. In _Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining_. 171–179.
  * Hendrycks and Gimpel (2016) Dan Hendrycks and Kevin Gimpel. 2016.  Gaussian error linear units (gelus).  _arXiv preprint arXiv:1606.08415_ (2016).
  * Hu et al. (2020) Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. 2020\.  Heterogeneous graph transformer. In _Proceedings of The Web Conference 2020_. 2704–2710.
  * Kipf and Welling (2017) Thomas N Kipf and Max Welling. 2017.  Semi-supervised classification with graph convolutional networks. In _ICLR_.
  * Li et al. (2020) Xiaohan Li, Mengqi Zhang, Shu Wu, Zheng Liu, Liang Wang, and S Yu Philip. 2020.  Dynamic graph collaborative filtering. In _2020 IEEE International Conference on Data Mining (ICDM)_. IEEE, 322–331.
  * Liu et al. (2021) Chang Liu, Xiaoguang Li, Guohao Cai, Zhenhua Dong, Hong Zhu, and Lifeng Shang. 2021\.  Non-invasive Self-attention for Side Information Fusion in Sequential Recommendation. In _AAAI_.
  * Nguyen et al. (2013) Dong Nguyen, Rilana Gravel, Dolf Trieschnigg, and Theo Meder. 2013.  ” How Old Do You Think I Am?” A Study of Language and Age in Twitter. In _Proceedings of the International AAAI Conference on Web and Social Media_ , Vol. 7.
  * Preoţiuc-Pietro and Ungar (2018) Daniel Preoţiuc-Pietro and Lyle Ungar. 2018.  User-level race and ethnicity predictors from twitter text. In _Proceedings of the 27th International Conference on Computational Linguistics_. 1534–1545.
  * Qiu et al. (2018) Jiezhong Qiu, Jian Tang, Hao Ma, Yuxiao Dong, Kuansan Wang, and Jie Tang. 2018\.  Deepinf: Social influence prediction with deep learning. In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 2110–2119.
  * Rahimi et al. (2018) Afshin Rahimi, Trevor Cohn, and Timothy Baldwin. 2018\.  Semi-supervised user geolocation via graph convolutional networks. In _ACL_.
  * Rao et al. (2010) Delip Rao, David Yarowsky, Abhishek Shreevats, and Manaswi Gupta. 2010.  Classifying latent user attributes in twitter. In _Proceedings of the 2nd international workshop on Search and mining user-generated contents_. 37–44.
  * Schlichtkrull et al. (2018) Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. 2018.  Modeling relational data with graph convolutional networks. In _European semantic web conference_. Springer, 593–607.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017\.  Attention is all you need. In _NIPS_.
  * Veličković et al. (2017) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2017.  Graph attention networks. In _ICLR_.
  * Wu et al. (2019b) Chuhan Wu, Fangzhao Wu, Junxin Liu, Shaojian He, Yongfeng Huang, and Xing Xie. 2019b.  Neural demographic prediction using search query. In _Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining_. 654–662.
  * Wu et al. (2019a) Shu Wu, Yuyuan Tang, Yanqiao Zhu, Liang Wang, Xing Xie, and Tieniu Tan. 2019a.  Session-based Recommendation with Graph Neural Networks. In _AAAI_. 346–353.
  * Xiao et al. (2020) Zhiping Xiao, Weiping Song, Haoyan Xu, Zhicheng Ren, and Yizhou Sun. 2020.  TIMME: Twitter Ideology-detection via Multi-task Multi-relational Embedding. In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 2258–2268.
  * Yu et al. (2020) Feng Yu, Yanqiao Zhu, Qiang Liu, Shu Wu, Liang Wang, and Tieniu Tan. 2020.  TAGNN: Target Attentive Graph Neural Networks for Session-based Recommendation. In _SIGIR_. 1921–1924.
  * Zhang et al. (2021b) Jinghao Zhang, Yanqiao Zhu, Qiang Liu, Shu Wu, Shuhui Wang, and Liang Wang. 2021b.  Mining Latent Structures for Multimedia Recommendation.  (2021).
  * Zhang et al. (2020a) Mengqi Zhang, Shu Wu, Meng Gao, Xin Jiang, Ke Xu, and Liang Wang. 2020a.  Personalized graph neural networks with attention mechanism for session-aware recommendation.  _IEEE Transactions on Knowledge and Data Engineering_ (2020).
  * Zhang et al. (2020b) Yufeng Zhang, Xueli Yu, Zeyu Cui, Shu Wu, Zhongzhen Wen, and Liang Wang. 2020b.  Every document owns its structure: Inductive text classification via graph neural networks. In _ACL_.
  * Zhang et al. (2021a) Yufeng Zhang, Jinghao Zhang, Zeyu Cui, Shu Wu, and Liang Wang. 2021a.  A Graph-based Relevance Matching Model for Ad-hoc Retrieval. In _AAAI_.
  * Zhao et al. (2019) Sha Zhao, Zhiling Luo, Ziwen Jiang, Haiyan Wang, Feng Xu, Shijian Li, Jianwei Yin, and Gang Pan. 2019\.  Appusage2vec: Modeling smartphone app usage for prediction. In _2019 IEEE 35th International Conference on Data Engineering (ICDE)_. IEEE, 1322–1333.