11institutetext: VERIMAG laboratory
University of Grenoble (UJF)
38610 Gières, France.
11email: {Dumitru.Ceara, Laurent.Mounier, Marie-Laure.Potet,
<EMAIL_ADDRESS>
# Combining Static and Dynamic Analysis for Vulnerability Detection

Sanjay Rawat  Dumitru Ceara  Laurent Mounier  Marie-Laure Potet

###### Abstract

In this paper, we present a hybrid approach for buffer overflow detection in C
code. The approach makes use of static and dynamic analysis of the application
under investigation. The static part consists in calculating _taint dependency
sequences_ (TDS) between user controlled inputs and vulnerable statements.
This process is akin to program slice of interest to calculate tainted data-
and control-flow path which exhibits the dependence between tainted program
inputs and vulnerable statements in the code. The dynamic part consists of
executing the program along TDSs to trigger the vulnerability by generating
suitable inputs. We use genetic algorithm to generate inputs. We propose a
fitness function that approximates the program behavior (control flow) based
on the frequencies of the statements along TDSs. This runtime aspect makes the
approach faster and accurate. We provide experimental results on the Verisec
benchmark to validate our approach.

##  1 Introduction

###  1.1 Context

In a recent report, published by Veracode [27], it is pointed out that a high
percentage of commercial and open source softwares is written in C/C++ and
thereby, making them highly susceptible to many dangerous attacks. Under this
category of C/C++, buffer overflow (BoF) tops the list with 32% of the total
vulnerabilities. In the present work, we focus on BoF vulnerability in C code.
There have been numerous studies in the literature to detect the presence of
BoF in applications [8][30]. These studies can broadly be categorized under
static and dynamic code analysis approaches. Both of the approaches have their
pros and cons.

Static code analysis is capable of analyzing all the possible paths from the
tainted source to potentially vulnerable statements. However, it may produce
false positives when dealing with complex language constructs or non trivial
sanitization functions. It is also sensitive to the artifacts introduced by
the compiler. For example, an _off-by-one_ error can be detected by a static
source code analyzer, but its actual exploitability will be known only after
the compilation.

On the contrary, Dynamic analysis can be very accurate in vulnerability
detection, but it faces a hard time in finding paths that activate the
vulnerability. The discipline of generating inputs that trigger a
vulnerability is termed as fuzzing [20]. Fuzzing can be completely random or
_intelligent_ [25][9]. In the later case, a possible approach is to use a
symbolic execution technique to produce a list of constraints that should be
satisfied in order to execute a given path (the so-called path-condition).
These path constraints are presented to a constraint solver to get some
possible inputs that satisfy them. However, the obtained results highly depend
on the solver’s efficiency. An alternative approach consists in re-phrasing
the input generation as a search problem, that can be solved using dedicated
techniques like genetic algorithms [19].

###  1.2 Our proposal

In this paper we propose a hybrid approach to detect BoF vulnerabilities.
First, a static code analysis is used to generate _Taint Dependency Sequences_
(TDS) representing a subset of tainted paths leading to a potential
vulnerability. Then, a dynamic analysis is used to generate concrete inputs
allowing to execute one of these paths. This dynamic part relies on a genetic
algorithm. The fitness function that we use associates a score to each current
input according to the runtime dynamics of the application: each obtained
execution trace is compared with the TDS that we target, and a next generation
of inputs is produced from the best individuals. This fitness function makes
use of the so-called _frequency spectrum_ of statements introduced in [3].

A high level diagram of our approach is depicted in Fig. 1.

Figure 1: A high level flow diagram representing various components of hybrid
approach

STAC is the static analysis component of the approach. It generates TDSs by
performing taint data-flow analysis. Based on this information, the source
code is instrumented in order to collect the execution traces produced by
running the program. The dynamic component, called TAGA (TDS Assisted Genetic
Algorithm, shown in dotted box), is then used to generate inputs as described
above. As we are targeting BoF vulnerability, TAGA keeps generating inputs
until we get a program crash, or until some threshold is reached in the number
of iterations performed by the genetic algorithm. When a crash is obtained, we
run the binary with a debugger to collect information about various internal
structures (e.g., the execution stack). This information will provide some
useful hints about the severity of the vulnerability: depending on the content
of the execution stack, we can infer how easy it is to write an exploit for
this vulnerability. Thus our approach shows not only the presence of the
vulnerability but also its feasibility of exploitation in real world.

The main contributions of the approach are:

  * •

Automated malicious input generation;

  * •

Robust taint data-flow based execution path generation, thereby reducing
search path. This point separates our approach from the ones based on code
coverage;

  * •

New runtime program behavior based fitness function;

  * •

Hints on the level of exploitability of a particular vulnerability.

The rest of the article is organized as follows. In section 2, we briefly
describe the static analysis component STAC. We elaborate on TAGA and its
various components including fitness function in section 3. Section 4 presents
the implementation details and some experiments performed on benchmark data.
Section 5 walks over the existing literature to report relevant work and
provides discussion in relation to our results. We conclude in section 6 by
providing summary and future extension of the approach.

##  2 Taint Dependency Sequence

As quoted in the introduction, one of the main difficulties when using search
based algorithms for vulnerability detection is to identify the part of the
program that needs to be covered during the search. In this section, we
describe the static analysis component that we use in our approach to automate
this task.

From a security point of view, a program execution sequence can be considered
as “dangerous” if it allows some user inputs to (directly or indirectly)
activate a (potentially) vulnerable statement, like an array access. Tracking
these dependencies between program inputs and vulnerable statements can be
obtained by means of a well-established technique called taint analysis.

Roughly speaking, taint analysis consists in assigning a taint information to
a variable $v$ at each program location $l$ if the value of $v$ at this
location may depend on an external input. Consider for instance the example
(taken from [28]) shown in Listing. 1 which serves as working example through
out the remaining article. This program takes two string arguments as input,
called gecos and login. It builds a result string (buf) by transforming the
gecos argument as follows: each occurrence of character “&” found before
either a “,”, “;”, “%” or “`\0`” character is substituted with the login
argument.

⬇

1void buildfname(char *gecos, char *login, char *buf)

2{

3 char *bp = buf;

4 char* p;

5 for (p = gecos; *p != ’\0’ && *p != ’,’ &&

6 *p != ’;’ && *p != ’%’; p++) {

7 if (*p == ’&’) {

8 (void) strcpy(bp, login); /* BAD */

9 *bp = toupper(*bp);

10 while (*bp != ’\0’)

11 bp++;

12 } else {

13 *bp++ = *p; /* BAD */

14 }

15 }

16 *bp = ’\0’; /* BAD */

17}

18int main(int argc, char **argv)

19{

20 char *gecos, *login, buf[512];

21 gecos=argv[1];

22 login=argv[2];

23 buildfname(gecos, login, buf);

24 return 0;

25}

Listing 1: buildfname simplified vulnerable function

In this program, parameters gecos and login are tainted at location 21 and 22
(since they depend on command line arguments). This taint information is
propagated to variables p and bp, both by data dependency (through explicit
assignments) and control dependency (since these variables are assigned within
an iteration controlled by an expression depending on gecos).

In [6], we proposed a static analysis approach which associates a taint
environment to each variable $v$, at each program location $l$. In addition to
taint information, this environment also associates to each pair ($l$, $v$) a
set of TDS explaining why the variable $v$ is tainted at location $l$. More
precisely, each TDS $t=<l_{1},l_{2},\dots,l_{n}>$ is a sequence of program
locations $l_{i}$ a program execution path should traverse in order to reach
$l$ with an input-dependent value assigned to $v$. Thus, when $l$ corresponds
to a vulnerable statement, this TDS set exactly characterizes the set of
“dangerous” execution paths.

In the buildfname example depicted in Listing. 1, 3 vulnerable statements can
be identified (lines 8, 13 and 16). Indeed, in each of these statements a
write access to a buffer buf is performed on a (potentially) tainted address
that might overflow the buffer. The TDS sets associated with these locations
corresponds to all the execution paths that may activate these vulnerabilities
(i.e., reach them with a tainted address)111Since these TDS are computed
statically some of these paths may be infeasible..

Let us consider, for instance, the vulnerability at line 8. At this location,
variable bp can be tainted in several ways, e.g.:

  * •

*bp is assigned p (at location 13), which was assigned the tainted value gecos (location 5). The corresponding TDS, therefore, is $<21,5,13,8>$.

  * •

bp is assigned within iteration loops controlled by a tainted value (location
5 and 10). Corresponding TDS are $<21,5,13,8>$ or $<22,8,10,11,8>$

##  3 Genetic Algorithm Based Input Generation

In this section, we briefly introduce the topic of genetic algorithm used in
the TAGA component. Genetic algorithm (GA, for short) is the member of family
of search-based algorithms known as _evolutionary algorithms_ [18]. GA is
based on the idea of human evolution i.e. _survival of the fittest_. Following
steps are involved in a typical GA based solution to a problem:

  1. 1.

Based on the problem, an _initial population_ of candidate solutions (inputs)
is generated randomly.

  2. 2.

A _fitness function_ is defined to evaluate each candidate solution (i.e. its
proximity to the target solution).

  3. 3.

_Crossover_ and _mutation_ are applied to parents (old generation) to create
children (new inputs).

  4. 4.

A _selection_ strategy is applied to generate new population based on fitness
score.

The pseudo-code of GA is given in listing: 2 (taken from [18]). In the
following sections, we describe GA components with respect to our
implementation. Genetic algorithm is used to generate inputs that cause
tainted path (i.e. TDS) to be executed. Indeed, the purpose of a TDS
$t=<l_{1},l_{2},\dots,l_{n}>$ is to “guide” the program execution towards a
vulnerability along a path traversing each $l_{i}$. The idea is to run the
vulnerable program with initial inputs and then by using GA generate new
inputs that not only traverse a given TDS but also cause the program to
misbehave, for example causing crash.

⬇

1popsize := desired population size

2P := []

3for popsize times do

4 P := P U <new random individuals>

5Best := []

6repeat

7 for each individual Pi in P do

8 AssessFitness(Pi)

9 if Best ==[] or Fitness(Pi) > Fitness(Best) then

10 Best := Pi

11 Q :=[]

12 for popsize/2 times do

13 Parent Pa := SelectwithReplacement(P)

14 Parent Pb := SelectwithReplacement(P)

15 Children Ca, Cb := Crossover(Copy(Pa), Copy(Pb))

16 Q := P U <Mutate(Ca), Mutate(Cb)>

17 P := Q

18until Best is the ideal solution OR we have run out of time

19return Best

Listing 2: Pseudo-code for Genetic Algorithm

###  3.1 Initial Population

As mentioned before, in order to execute a TDS a set of constraints
(corresponding to the IF and WHILE conditions associated to this TDS) has to
be satisfied. When these conditions are character comparisons, this implies
that the (string) inputs should pass these comparisons. Therefore, based on
static analysis of the source code, performed during TDS computation, we
collect information on program inputs and corresponding path conditions. For
the program, shown in Fig. 1, path conditions are in the form of comparisons
with particular characters belonging to the set
$C=(^{\prime}\&^{\prime},^{\prime},^{\prime},^{\prime};^{\prime})$. With this
information, we construct regular expression to represent the input and
thereupon, generate strings that satisfy that regular expression. In our
example, we use [a-z$%;,@#&$0-9A-Z]{16,32},which matches strings of length
between 16 and 32 characters including the ones belonging to $C$. The set of
such inputs constitutes our initial population222Currently, we are
experimenting with string type inputs only.. In each generation, we maintain
30 individuals.

###  3.2 Fitness Function

As aforementioned, our aim is to traverse a given TDS, which may contain nodes
responsible for path conditions. We should prefer inputs that traverse through
maximum number of such nodes. Based on this criteria, we assign weights to
each of the elements belonging to a selected TDS. Our fitness function $F_{i}$
of $i^{th}$ input ($i\in I$, set of inputs) is defined as follows:

$\centering F_{i}=\displaystyle\sum_{j=1}^{k}{w_{j}}\times
f_{ij}\@add@centering$ (1)

where $w_{j}\in W$ corresponds to the weight associated with $l_{j}\in t$ and
$f_{ij}$ is the frequency of $l_{j}$ for $i\in I$. $W$ is the set of weights
for each TDS $t$. Selection of appropriate values for $W$ is of paramount
importance for our fitness function to yield good results. For example, if we
choose to select equal weights for each $t_{j}$s, and there is a nested
structure in the program such that one (or more) $l_{j}$ is at inner most
nested statement, then it will be executed lesser times, as compared to
$l_{j}$ at outer most statements. As a result, inputs which are reaching till
outer statements only will have a high fitness values, thereby giving GA a
wrong fitness impression. Therefore, for such situation, we need to assign a
higher weight to the inner one as compared to the outer one. To tackle this
issue, we have following two approaches to work upon.

#### Static Approach

While calculating TDS, STAC also learns IsNested type of structure among
$l_{j}$s. For example, for any two $l_{1},l_{2}\in t$, we may learn that
$l_{1}$ and $l_{2}$ are in a same nested conditional statements structure and
$l_{1}$ lies at upper level than $l_{2}$ in the hierarchy. Therefore, if we
have this information from TDS, we can assign relative weights such that inner
$l_{j}$s have higher weights than outer ones.

#### Dynamic Approach

A careful runtime analysis reveals a lot about execution trace of the program
by means of frequencies corresponding to $l_{j}$s. In [3][2][22] the authors
discuss the dynamic analysis of program by means of _frequency spectrum
analysis_. In particular, by observing the frequencies of statements,
branching structure can be approximated to some extent. As discussed in above
section, it may be noted that rare execution statements will have low
frequencies as compared to easily executed ones. It may also be noted that
statements lie deep inside a nested structure belong to rare statements.
Therefore, frequency spectrum of $l_{j}$s captures IsNested type of structure
among $l_{j}$s. To calculate frequency spectrum, we start with a set of inputs
$I:=\langle i_{1},i_{2},...,i_{m}\rangle$ to get a frequency matrix
$freq=\left(\begin{smallmatrix}\cdots\\\ f_{ij}\\\
\cdots\end{smallmatrix}\right)$, where $f_{ij}$ is the frequency of $l_{j}$
for the input $i\in I$. As we are counting frequencies of each $l_{j}$, a
given tds $t$ is simplified further by removing duplicate $l_{j}$s, keeping
only the first occurrence of $l_{j}$. Based on the above assumption, we
calculate weights dynamically by counting global frequencies of $l_{j}$s and
inverting them i.e. for a set of inputs $I$ and the matrix $freq$, the weight
$w_{j}$ of $l_{j}$ is calculated as follows:

$\centering w_{j}=\frac{1}{\displaystyle\sum_{i=1}^{m}f_{ij}}\@add@centering$
(2)

We make another observation while calculating weights. Labels in TDS, which
are closer to vulnerable statement i.e. the last element of a TDS, should have
more weights than the ones which are relatively away from vulnerable
statement. This is because any input which is reaching nearer to vulnerable
statement has greater chance of reaching the vulnerable statement. Given this,
we multiply weights with a function whose value increases as we move from
beginning to end in a TDS. One example of such function may be the index of
the elements in the TDS i.e. for $l_{j}\in t$, the function value will be $j$.
We denote this function as $ProximVar$. Therefore, considering above
formulation in mind, we arrive at the following equation for calculating
weights.

$\centering w_{j}=\frac{1}{\displaystyle\sum_{i=1}^{m}f_{ij}}\times
ProximVar\@add@centering$ (3)

Substituting the values obtained by using eq. 3 into the eq. 1, we get the
fitness value of each input. These values are sorted in descending order to
select inputs to be used in next population generation.

In the present study, we use dynamic approach to calculate weights. The static
approach of calculating weights is incomplete in the sense that it only
provides the relation among various $l_{j}$s. Nevertheless, we need to use
another technique to calculate actual values of weights, for example linear
programming [12]. Dynamic approach, on the other hand, uses runtime statistics
to calculate weights, without requiring to use another technique.

###  3.3 Selection

We follow _elitism_ approach to select inputs. In this approach, we choose
best two inputs to be included in the next generation i.e. these two inputs
will be competing with their own children in the next generation.

###  3.4 Crossover and Mutation

We perform crossover by combining two inputs (parents) to form two new inputs
(children). Based on the problem, we may choose single- or two-point
crossover. As our inputs are strings, we concatenate substrings of both the
parents by interchanging them with each other. In experimentations, the rate
of crossover is set to 100%.

Mutation is performed by appending a random (smaller) string which is
generated by providing a regular expression of our choice. For our working
example, we use [ab$&%@12]{4} regular expression, which generate strings of
length 4. We deliberately use smaller character set with special character &
as the main purpose of mutation is to remove stagnation in population by
inserting characters (genes) of interest. The point of insertion of new string
to the existing string is decided by uniform probability distribution. We
choose following three positions to insert strings - beginning, middle and
end. This operation is also used to increase the length of the strings as we
are targeting BoF type of attack. The rate of mutation is set between 50 to
70%.

##  4 Implementation and Experimentation

This section details on implementation of our framework and provides a set of
experiments to validate the approach.

###  4.1 Implementation

From the implementation perspective, the present work is composed of two major
components- STAC and TAGA. STAC is implemented in Caml, using Frama-C
framework. Details of its implementation can be found in [6]. After the source
code is analyzed by STAC, we get all the information that we require to
perform dynamic analysis. For a given vulnerable statement, we get a set of
corresponding TDSs. We select a TDS which has maximum unique nodes to reach
vulnerable statement. The reason for doing so is that smaller TDS may be very
trivial or may provide less precise path.

Dynamic component TAGA is composed of instrumented binary of the program, GA
to generate inputs and an interface to communicate with a debugger to get
after-crash information. In this study, we choose to work with GDB as our
preferred debugger. As TDS includes control flow of the program, we get to
know which branch of a conditional statement is executed. This information is
used by our fitness function. Therefore, based on a particular TDS for a
particular vulnerability path, we instrument lines in source code
corresponding to the chosen TDS. For example, for the code given in listing 1,
one of the TDSs that we select is $\langle 21,5,7,8\rangle$ for the vulnerable
statement strcpy(bp, login). Therefore, we instrument statements after each of
these labels- 21, 5, 7, 8. In this way, at runtime, we get execution trace of
the program in terms of executed statement’s frequency.

GA is implemented as Python module. Inputs to GA module are instrumented
binary and regular expressions to generate inputs. Regular expressions are
constructed based on the static analysis of the program which extract
information on constraints e.g. character matching in IF statements. Such
characters, along with other ASCII characters, are included in regular
expression to help GA generating valid inputs faster. GA is run until we get
SIGSEGV signal or a predefined iteration threshold is reached (1000 iterations
in our experimental setup). We look for SIGSEGV signal because BoF will result
in invalid memory reference or segmentation fault. Once we get malicious
inputs corresponding to SIGSEGV signal, with the help of another Python
module, we run the binary with GDB to get more information which is useful for
understanding the impact of analysis on exploit generation (see section 4.3).
Using such information, we can infer as how easy (or difficult) it is to write
a real exploit for the vulnerability.

###  4.2 Experimentation

For empirical results, we experiment with Verisec benchmark suite [28]. The
suite consists of snippets of open source programs containing BoF
vulnerabilities of varied difficulties. For us the level of difficulty is
directly proportional to the manipulation done on the tainted input by the
program i.e. if there are checks on the input before it reaches the vulnerable
statement, it is more difficult to generate such input. From this perspective,
we find that Verisec suite has programs as simple as bind-> CVE-2001-001->
nslookupComplain-small_bad.c, gxine-> CVE-2007-0406-> main, Samba->
CVE-2007-0453 etc., wherein generating a larger _random_ string overflows the
buffer, to as hard as sendmail-> CVE-2003-0681-> buildfname, edbrowse->
CVE-2006-6909-> ftpls->
strchr_bad.c etc. wherein input should contain (or does not contain) specific
characters (at specific positions) in order to reach the vulnerable statement.

There are many programs which contain BoF vulnerability mainly due to _off-by-
one_ error. We could not experiment with such programs as gcc 4.4.1 compiles
the binaries such that vulnerable buffer does not appear just above the saved
frame pointer (ebp). This makes it impossible to overwrite last byte of saved
ebp which is the technique to exploit _off-by-one_ error [15]. Therefore in
practice, there is no _off-by-one_ error as such and without the dynamic
analysis, this would have been a false positive.

Table 1 shows the findings of our analysis on three programs which do string
(inputs) manipulations before letting it reach the vulnerable statement. In
order to evaluate the gain by including TDS with GA, we compare our results
with two other approaches- random fuzzing approach and code coverage based GA
approach, similar to [13]. However, even for random approach, we use the same
regular expression that we use in our proposed approach to generate the random
inputs i.e. random fuzzing is not completely random. For the second approach,
we use _gcov_ tool for calculating code-coverage. In this case, the fitness
function depends on percentage of code covered by an input and number of times
a vulnerable statement is executed (and therefore, reached). We do not use any
specific path (slicing) to reach vulnerable statement. The weights are
selected as per heuristics discussed in [13].

Table 1: List of the programs used in experimentation S.No. |  Application |  Name |  # LoC |  Constraints |  TDS + GA |  coverage + GA |  Random inputs
---|---|---|---|---|---|---|---
1 |  sendmail |  mime_fromqp |  65 |  ’=n’ |  20 |  26 |  243
2 |  sendmail |  buildfname |  52 |  ’&’ and not(,;%) |  6 |  10 |  34
3 |  edbrowse |  ftpls |  49 |  ’– ’ (in the beginning) |  35 |  * |  *

In the table, columns 2–3 denote the path of the vulnerable program in the
Verisec suite. _lines of code_ parameter is given in column 4. Column 5 shows
constraints that an input must satisfy in order to reach vulnerable statement.
Column 6 shows the number of iterations (generations) taken by TDS based GA to
generate inputs that crash the application. These numbers are average taken
over 20 different runs of GA. Column 7 shows the same for coverage based GA.
Last column shows the number of iteration taken by random fuzzing approach. A
noticeable difference (shown as asterisk) comes out in the case of _edbrowse_
program. In this case, out of 20 times, coverage based GA could generate
malicious inputs only 3 times and random fuzzing could generate malicious
inputs only 2 times. This comparison shows the effectiveness of GA enabled
inputs generation _viz-a-viz_ randomly generated inputs, specially in the
case, when we have knowledge about the precise path to reach the vulnerable
statement by means of TDS. The experiments also show that even for the small
programs, data- and control-flow assisted GA outperforms other similar
approaches333For larger programs, the cyclomatic complexity will be high which
will further widen the gap..

###  4.3 Vulnerability Exploitability

Next step in vulnerability analysis is to check if the vulnerability is
exploitable in real world by generating exploits. Generating exploits for a
stack BoF vulnerability involves getting information about the execution stack
when the buffer overflow occurs. When we get a SIGSEGV signal on a particular
input, another python module is used to run the program with GDB to collect
after-the-crash information which includes various stack register contents
e.g. _return pointer, stack pointer, frame pointer_ etc., offset of input that
caused overflowing _saved return address_. The purpose of getting this
information is to further validate the exploitability of the vulnerability
(explained below). Following we show a typical output of our tool for the
program at S. No. 3 in the table. In that program, there exists a BoF when
strcpy() is called with a fixed length buffer user[USERSZ] and user controlled
input. In order to reach the strcpy() statement, the input string must have
’\-- ’ as first three characters. For convenience, we denote <space> by S in
the output shown in figure 2.

1 Generation# 35 2 Malicious inputs: --S1--*a%*S--
l42f4*cS8SnSaaSaSS%*S1-*%%Sn%1S 3
n1%a-nn*1*nn1a-S%%1-*a1*a*a-a*a-%a-%*Sa1S%1a*nn1--%*l&c%al*cgf= 4 Lengths: 107
5 Calling GDB...Returned from GDB.. 6 .... 7 EIP is overwritten by: a*a- at
index: 68 8 EBP is overwritten by: *a1* at index: 64 9 ESP is pointing to:
a*a-%a-%*Sa1S%1a*nn1--%*l&c%al*cg at index:72

Figure 2: Output of the tool.

Line 2-3 shows the malicious input that caused the program to crash, followed
by its length 107. Line # 7 shows the status of eip which is overwritten by
a*a- at an offset 68 in the string and line 9 shows the contents pointed by
esp at offset 72. With this information, one can construct a real exploit with
the following skeleton:

<\--S...Ax67...><4 bytes address to ’jump esp’
instruction><...shellcode..(starting at 72th byte>Based on this information,
we can infer that it is easy to exploit edbrowse program. On the other hand,
in the case of  mime_fromqp, we find it difficult to exploit as values of eip,
esp were not always affected _meaningfully_ by the user controlled input which
makes it hard to construct an exploit.

##  5 Related Work

Application code analysis is gaining importance, as it can help in writing
safe code during the development phase by detecting bugs that may lead to
vulnerabilities. As a result, tremendous research on code analysis has been
carried out by industry and academia and there exist many commercial and open
source tools and approaches for this purpose.

#### Taint Analysis.

The notion of taint variable has been introduced within the Perl language,
with the use of a special execution mode called “taint mode”. This idea of
computing variable’s taintness at runtime has been generalized into several
tools, see [7] for a more complete survey. Input dependencies of program
variables can also be computed using static analysis techniques, as in [29,
23, 26]. The main advantage of the latter approach is to consider the whole
set of program executions, but, as usual, the price to pay is larger number of
false positives. Moreover, it is highly desirable to extend results on
variable taintness with information on the corresponding execution paths. This
point has been considered so far only in a few existing works [16, 21]. The
most dangerous paths are then used as “test objective” in order to check if
the corresponding vulnerability is effective or not. On similar lines, in
[10], Ganesh _et al._ proposed an automated white-box fuzzing techniques in
the form of a tool- _BuzzFuzz_. The technique is to identify vulnerable points
in the code and execute the instrumented binary with _valid_ input set; using
data taint analysis, identify inputs that affect those vulnerable points; fuzz
these inputs and run the binary with them. In this way, the _legal_ syntactic
structure of the program is maintained while executing it with new fuzzed
inputs. However, a domain expert knowledge is required to fuzz the relevant
inputs manually.

#### Concolic Approaches.

Concolic approach is a _portmanteau_ of concrete and symbolic execution based
approaches for analysis. A pure symbolic approach- EXE is proposed in [4],
wherein the program is run on symbolic inputs while recording input-constraint
pairs. When a particular path ends or a bug is found, EXE generate a real
input by solving the constraints by using a solver. The problem with such
approaches is the path explosion and imperfect symbolic execution [11].
Godefroid _et al._ [11] implement a tool- SAGE which incorporates techniques
from symbolic and dynamic execution. At algorithm level, the approach has
components similar to our approach, specially from GA implementation
standpoint. However, the functionality of these components is different. The
idea is to start with an initial input and capture constraints by executing
the program. These constraints are given to constraint solver. Based on this
solution and their _score_ in covering basic-blocks, new children are
generated to cover new paths. This process is continued until some interesting
event is captured. The analysis is performed on machine-code, which makes it
suitable for wide variety of compilers, compiling to x86 instructions.

#### GA Assisted Dynamic Approaches.

Dynamic analysis technique analyzes the application by executing it on real
inputs. Miller _et al._ coined the term _fuzzing_ to test UNIX utilities by
generating random inputs to discover malfunctioning [20]. The idea is to
generate random values as inputs that covers boundary cases. But as noted in
[4][10], vulnerabilities that are buried deep inside the code are hard to
discover using this technique. Genetic algorithms (GAs) have been used to
generate test cases for program testing [1][19]. Grosso _et al._ have used GA
to generate inputs automatically that trigger BoF vulnerability in the
application [12][14]. The fitness score of input is based on its ability to
cover code and reaching vulnerable statements and weights associated with each
of these factors. They have used linear programming to adjust weights
automatically which is an additional step in the whole process of input
generation. The authors mention to consider _nested_ statements, but have not
provided enough description of its detection in source code and usage in the
fitness calculation. In our approach, we have made use of readily available
statement frequencies to approximate nested statements and their weights.
Sidewinder is a tool for analyzing binaries to detect vulnerabilities using GA
assisted fuzzer [24]. In this approach, control flow is modeled as Markov
Process and fitness function is defined over Markov probabilities associated
with state transition on control flow graph. Inputs are generated using
_grammatical evolution_. Due to the dependency of fitness function on
transition probabilities, this approach should be able to reach _deeply
nested_ statements which is important if vulnerable statements are buried deep
inside. Our approach is closest to this approach with added feature of
simplifying the weight calculation and path to traverse to reach vulnerable
statements. On the similar lines, Liu _et al._ construct _control dependence
predicate path_ (CDPPath) from the binary of the application and apply GA to
construct inputs to reach vulnerable statements [17]. Their fitness function
depends on the number of predicates in CDPPath covered by inputs. However,
this study treats each predicate equal which may result in stagnation during
later stage of searching.

##  6 Conclusions and Future Work

In this article, we report our work of generating inputs to reach a vulnerable
statement and putting the program in an abnormal states. Static analysis based
taint data-flow approach has the advantage of producing all possible paths
from tainted inputs to vulnerable statements, but is generally blind towards
paths constraints that must be satisfied by an input to traverse a given path.
Symbolic execution tries to overcome this hurdle by solving path constraints
to generate inputs, but at the cost of high computational complexity. Random
fuzzing is surprisingly effective in generating inputs for corner cases in
lesser time. This approach, however, does not consider any conditions on the
inputs, thereby making it unsuitable for more complex programs. We, therefore,
propose a hybrid approach by combining static and dynamic analysis to extract
nicer properties of both the approaches. By doing a static analysis, we
extract TDS- a program slice from tainted input to vulnerable statements and
string constraints to be satisfied by the inputs. Rather than solving these
constraints, we use GA to generate inputs along a TDS. The fitness function
depends on the runtime behavior of the program in terms of execution
frequencies of statements. This amalgamation makes the approach faster and
accurate, which is further supported by empirical results that we obtain on a
benchmark dataset.

This paper reports preliminary results of our work. We envisage many
improvements that comprise our future work. We intend to provide more formal
makeup to _frequency spectrum analysis_. Another point of difficulty is that
when more conditions are checked in a single $IF$ statement, GA has no way to
knowing up to what percentage of predicates are being satisfied by an input.
This makes it difficult to select inputs for its next generation. Had it been
represented by multiple separate $IF$ statements, GA can observe the
respective frequencies of separate $IF$ statements to select inputs. It should
be noted that at binary level, this structure is available by default. Each
condition in a composite $IF$ statement is represented by a separate basic-
block. This give us incentive to shift our static analysis to binary code. We
intend to integrate it with a debugger to have better runtime control.
Finally, for a better coverage of all tainted paths to a vulnerability, we
plan to design a fitness function (similar to the one proposed in [5]) which
is based on more than one TDS corresponding to one particular vulnerable
statement.

## References

  * [1] Afzal, W., Torkar, R., Feldt, R.: A systematic review of search-based testing for non-functional system properties. Information and Software Technology 51(6), 957–976 (2009)
  * [2] Ball, T.: What’s in a region? or computing control dependence regions in near-linear time for reducible control flow. ACM Letters on Programming Languages and Systems 2(1-4), 1–16 (1993)
  * [3] Ball, T.: The concept of dynamic analysis. In: Proc. of 7th European Software Engineering Conference. Lecture Notes in Computer Science, vol. 1687, pp. 216–234. Springer (1999)
  * [4] Cadar, C., Ganesh, V., Pawlowski, P.M., Dill, D.L., Engler, D.R.: Exe: Automatically generating inputs of death. In: Proceedings of the 13th ACM CCS’06. pp. 322–335. ACM (2006)
  * [5] Cao, Y., Hu, C., Li, L.: Search-based multi-paths test data generation for structure-oriented testing. In: Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation. pp. 25–32. ACM (2009)
  * [6] Ceara, D., Mounier, L., Potet, M.L.: Taint dependency sequences: A characterization of insecure execution paths based on input-sensitive cause sequences. In: Proc. of the IEEE International workshop MDV’10. pp. 371–380. IEEE Computer Society (2010)
  * [7] Chang, W., Streiff, B., Lin, C.: Efficient and extensible security enforcement using dynamic data flow analysis. In: Proceedings of the 15th ACM conference CCS’08. pp. 39–50. ACM (2008)
  * [8] Cowan, C., Wagle, P., Pu, C., Beattie, S., Walpole, J.: Buffer overflows: Attacks and defenses for the vulnerability of the decade. In: Proceedings of DISCEX’00, vol 2. pp. 119–129. IEEE (2000)
  * [9] DeMott, J.: The evolving art of fuzzing. In: Proceedings of DEFCON’06. DEFCON CD (2006), http://www.vdalabs.com/tools/The_Evolving_Art_of_Fuzzing.pdf
  * [10] Ganesh, V., Leek, T., Rinard, M.: Taint-based directed whitebox fuzzing. In: Proceedings of the IEEE 31st International Conference on Software Engineering. pp. 474–484. IEEE Computer Society (2009)
  * [11] Godefroid, P., Levin, M.Y., Molnar, D.: Automated whitebox fuzz testing. In: Proc. of Network Distributed Security Symposium. Internet Society (2008)
  * [12] Grosso, C.D., Antoniol, G., Merlo, E., Galinier, P.: Detecting buffer overflow via automatic test input data generation. Computers & Operations Research 35(10), 3125–3143 (2008)
  * [13] Grosso, C.D., Antoniol, G., Penta, M.D.: An evolutionary testing approach to detect buffer overflow. In: Proceedings of the International Symposium of Software Reliability Engineering (ISSRE’04) (Student Paper). pp. 77–78. IEEE (2004)
  * [14] Grosso, C.D., Antoniol, G., Penta, M.D., Galinier, P., Merlo, E.: Improving network applications security: A new heuristic to generate stress testing data. In: Proceedings of the 2005 conference on Genetic and evolutionary computation. pp. 1037–1043. ACM (2005)
  * [15] klog: The frame pointer overwrite. Phrack Magazine 9(55) (1999), http://www.phrack.com/issues.html?issue=55&id=8#article
  * [16] Le, W., Soffa, M.L.: Refining buffer overflow detection via demand-driven path-sensitive analysis. In: Proceedings of the 7th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering. pp. 63–68. ACM (2007)
  * [17] Liu, G.H., Wu, G., Tao, Z., Shuai, J.M., Tang, Z.C.: Vulnerability analysis for x86 executables using genetic algorithm and fuzzing. In: Proceedings of the 3rd International Conference on Convergence and Hybrid Information Technology. pp. 491–497. IEEE Computer Society (2008)
  * [18] Luke, S.: Essentials of Metaheuristics (2009), available at http://cs.gmu.edu/$\sim$sean/book/metaheuristics/
  * [19] Mantere, T., Alander, J.T.: Evolutionary software engineering, a review. Applied Soft Computing 5(3), 315–331 (2005), application Reviews
  * [20] Miller, B.P., Fredriksen, L., So, B.: An empirical study of the reliability of unix utilities. Commun. ACM 33(12), 32–44 (1990)
  * [21] Nagy, C., Mancoridis, S.: Static security analysis based on input-related software faults. In: Conference on Software Maintenance and Reengineering. IEEE Computer Society (2009)
  * [22] Reps, T.W.: The use of program profiling for software testing. In: Informatik 97, GI Jahrestagung. pp. 4–16 (1997)
  * [23] Scholz, B., Zhang, C., Cifuentes, C.: User-input dependence analysis via graph reachability. In: Proc. of IEEE International Workshop on Source Code Analysis and Manipulation. pp. 25–34 (2008)
  * [24] Sparks, S., Embleton, S., Cunningham, R., Zou, C.: Automated vulnerability analysis: Leveraging control flow for evolutionary input crafting. In: Proceedings of the 23 Annual Computer Security Applications Conference. ACSAC (2007)
  * [25] Sutton, M., Greene, A., Amini, P.: Fuzzing: Brute Force Vulnerability Discovery. Addison-Wesley Professional, 1 edn. (July 2007)
  * [26] Tripp, O., Pistoia, M., Fink, S.J., Sridharan, M., Weisman, O.: Taj: effective taint analysis of web applications. In: Proceedings of the 2009 ACM SIGPLAN conference PLDI’09. pp. 87–97. ACM (2009)
  * [27] Veracode: State of software security report: The intractable problem of insecure software (March 2010), http://www.veracode.com/reports/index.html
  * [28] Verisec: Verisec benchmark dataset (October 2008), http://se.cs.toronto.edu/index.php/Verisec_Suite
  * [29] Wassermann, G., Su, Z.: Sound and precise analysis of web applications for injection vulnerabilities. In: Proceedings of the 2007 ACM SIGPLAN conference PLDI’07. pp. 32–41. ACM (2007)
  * [30] Wilander, J., Kamkar, M.: A comparison of publicly available tools for dynamic buffer overflow prevention. In: Proceedings of the 10th Network and Distributed System Security Symposium. pp. 149–162 (2003)


# KQGC: Knowledge Graph Embedding with Smoothing Effects of Graph Convolutions
for Recommendation

Daisuke Kikuta1∗, Toyotaro Suzumura1,3, Md Mostafizur Rahman1, Yu Hirate1,
Satyen Abrol2, Manoj Kondapaka2, Takuma Ebisu1, Pablo Loyola1 1Rakuten
Institute of Technology, Rakuten Group, Inc., Tokyo, Japan  2Rakuten Institute
of Technology, Rakuten Group, Inc., Bengaluru, India  3The University of
Tokyo, Tokyo, Japan<EMAIL_ADDRESS><EMAIL_ADDRESS>
{mdmostafizu.a.rahman, yu.hirate, satyen.abrol, kondapaka.manoj, takuma.ebisu,
<EMAIL_ADDRESS>
(2022)

###### Abstract.

Leveraging graphs on recommender systems has gained popularity with the
development of graph representation learning (GRL). In particular, knowledge
graph embedding (KGE) and graph neural networks (GNNs) are representative GRL
approaches, which have achieved the state-of-the-art performance on several
recommendation tasks. Furthermore, combination of KGE and GNNs (KG-GNNs) has
been explored and found effective in many academic literatures.

One of the main characteristics of GNNs is their ability to retain structural
properties among neighbors in the resulting dense representation, which is
usually coined as smoothing. The smoothing is specially desired in the
presence of homophilic graphs, such as the ones we find on recommender
systems. In this paper, we propose a new model for recommender systems named
Knowledge Query-based Graph Convolution (KQGC). In contrast to exisiting KG-
GNNs, KQGC focuses on the smoothing, and leverages a simple linear graph
convolution for smoothing KGE. A pre-trained KGE is fed into KQGC, and it is
smoothed by aggregating neighbor knowledge queries, which allow entity-
embeddings to be aligned on appropriate vector points for smoothing KGE
effectively. We apply the proposed KQGC to a recommendation task that aims
prospective users for specific products. Extensive experiments on a real
E-commerce dataset demonstrate the effectiveness of KQGC.

Recommendation, Graph representation learning, Knowledge graph, Graph neural
networks

∗The author was with Rakuten Institute of Technology when the work was done

††copyright: acmcopyright††journalyear: 2022††doi:
XXXXXXX.XXXXXXX††conference: the 31st ACM International Conference on
Information and Knowledge Management (CIKM ’22); October 17–22, 2022; Atlanta,
Georgia††price: 15.00††isbn: 978-1-4503-XXXX-X/18/06††ccs: Information systems
Recommender systems

##  1\. Introduction

Internet services, including e-commerce and streaming, have been growing up
rapidly in recent years. Recommender Systems (RecSys) are indispensable
technologies for enhancing user experience of these services. Therefore, how
to fully leverage rich sources of data and improve RecSys have been one of the
most critical challenges for companies in the field. RecSys have been widely
studied in both research and industry, and various approaches have been
proposed over the years. Most of them have relied on collaborative filtering
(CF), which infers user’s latent preferences based on the co-occurrence in
historical interactions. Traditional CF-based methods, such as user-based
model (Shardanand and Maes, 1995; Breese et al., 1998), item-based model
(Sarwar et al., 2000; Billsus and Pazzani, 1998; Sarwar et al., 2001) and
matrix factorization (Koren et al., 2009), generate user’s and item’s features
from an interaction matrix. However, they cannot incorporate side information,
resulting in poor performance in the cold start problem (Wang et al., 2019a,
d).

Graph representation learning-based approaches have gained popularity in
recent years due to the ability to handle with both high-order relations in
historical interactions and side information. In particular, Graph Neural
Networks (GNNs) have shown prominent performance in RecSys based on their
ability of modelling complex settings and scalability. User-item bipartite
graphs have been employed for GNNs traditionally (Ying et al., 2018; van den
Berg et al., 2017; Zheng et al., 2018; Wang et al., 2019b, 2020), while
utilization of knowledge graphs (KGs) have been also considered lately (Wang
et al., 2019d, a; Wang et al., 2021). Leveraging KGs has two main advantages.
Firstly, it can handle attributes relationships (e.g., hierarchical dependency
of product genres in e-commerce). Secondly, extracting attributes as entities
(nodes) in a KG allows two nodes having the same attributes to be connected
through the attribute entities. As a result, GNNs can capture high-order
relations by sharing attributes more efficiently (Wang et al., 2019a). The
representative models combining KG and GNNs (KG-GNNs) are KGCN (Wang et al.,
2019d) and KGAT (Wang et al., 2019a). KGCN is a meta-path based GNN, which
generates embeddings of entities and relations in the KG with knowledge-aware
attention-based GNN layers. KGAT consists of two layers: Knowledge Graph
Embedding (KGE) and GNN layers, and it generates node embeddings by applying
GNN layers to the KGE obtained from TransR (Lin et al., 2015). Here, the two
layers are trained simultaneously.

We argue that homophily holds in graphs that emerge in recommendation tasks,
and aggregation (smoothing) is the most effective function of GNNs there as
Simple Graph Convolution (Wu et al., 2019b) has shown. In this paper, we
propose Knowledge Query-based Graph Convolution (KQGC), which enhances KGE
with smoothing. KQGC relies on the simple principle of smoothing, and it is a
KG-GNN model that has different perspective to KGCN and KGAT. Therefore, there
are three distinctions between existing KG-GNNs and KQGC: 1) KQGC consists of
both KGE model and graph convolution model. KGE is pre-trained, and
subsequently the KGE is fed into graph convolution model. i.e., the two models
are trained separately in contrast to KGAT. 2) KGCN and KGAT aggregates only
neighbor entity embeddings, while KQGC aggregates knowledge queries, which are
sums of entity and relation embeddings. That can alleviate irrelevant
smoothing. 3) KGCN and KGAT apply nonlinear function when updating embeddings,
while KGCN does not. As a results, property of the pre-trained KGE is
preserved.

Rakuten group has one of the largest E-commerce platform in the world. In
particular, AIris Target Prospecting (AIris TP), which is a framework that
finds prospective users for Rakuten business clients, has been playing an
important role in this E-commerce platform. Companies like Facebook runs one
of the world’s most powerful advertising platforms, which is called ”Facbook
Lookalike Audience”. Rakuten AIris TP serves the same purpose to its clients.
Therefore, we aim to improve the performance of AIris TP in this paper. We
apply KQGC to the Airis TP, and evaluate the effectiveness.

The main contributions of our work are organized as follows:

  * •

We propose a new model combining KGE and graph convolution called KQGC, which
enhances KGE with smoothing effects of graph convolution. It provides a new
perspective of combining KGE and GNNs.

  * •

Experimentally, we show the effectiveness of KQGC and its smoothing effects on
real E-commerce dataset.

##  2\. Related Work

Graph representation learning (GRL) for RecSys is roughly categorized into
three approaches: knowledge graph embedding (KGE), graph neural networks
(GNNs) and combination of the two. In this section, we describe each of them
and clarify relation between them and the proposed model.

###  2.1. Knowledge Graph Embedding

Knowledge graph (KG) is a directed heterogeneous graph that represents a fact,
where nodes and edges represent entities and relations between two entities,
respectively. It is formulated as a set of triples
$\\{(h,r,t)|h,t\in\mathcal{E},r\in\mathcal{R}\\}$, where $h$, $t$, $r$ are
heads, tails and relations. For instance, the fact that shoes A is sold by
Shop B is represented as a triple $(ShoesA,isSoldBy,ShopB)$. The main goal of
KGE is to map enitities and relations in KGs to embeddings (vectors).

There are two representative categories of KGE models: bilinear (semantic
matching) model and translation-based model (Guo et al., 2020). Bilinear model
is a tensor factorization model, which generates embeddings of entities and
relation matrices that can reconstruct relational adjacency matrix of the KG.
RESCAL (Nickel et al., 2011), DistMult (Yang et al., 2015) and ComplEX
(Trouillon et al., 2016) are representative bilinear models. In translation-
based model, embeddings of entities and relations are initialized with random
values, then they are updated so that distance between embeddings of positive
triples (e.g., $||\bm{e}_{h}+\bm{e}_{r}-\bm{e}_{t}||_{1,2}$ in TransE) is
minimized. TransE (Bordes et al., 2013) is the first translation-based model,
and there are several variants of it such as TransR (Lin et al., 2015) and
TransD (Ji et al., 2015).

In the context of RecSys, recommended items or users are determined by
evaluating similarity score between user- and item-embeddings obtained by KGE
models. More specially, in the case that we recommend $k$ items to a user,
top-$k$ items that have high score (e.g., inner product between the user and
items with purchase relation $(\bm{e}_{u}+\bm{e}_{purchase})^{T}\bm{e}_{i}$)
are selected as the recommended items. Our model employs translation-based
models in the pre-training phase, and subsequently smooths the pre-trained KGE
with graph convolution. Consequently, our model strengthens the homophily of
KGE.

###  2.2. Graph Neural Networks

Graph Neural Networks (GNNs) are neural network models for graphs, which
encode node/edge embeddings by leveraging both node/edge features and graph
structure. There are three types of GNNs: recurrent GNNs, spectral-based
convolutional GNNs and spatial-based convolutional GNNs (spatial-based
ConvGNNs) (Wu et al., 2019a). In particular, many variants of spatial-based
ConvGNNs have been proposed actively in recent years (Kipf and Welling, 2017;
Hamilton et al., 2017; Veličković et al., 2018; Schlichtkrull et al., 2018; Hu
et al., 2020) due to the flexibility of modeling and scalability. Generally,
GNNs are formulated with the message passing (MP) framework (Gilmer et al.,
2017), which consists of two steps: aggregation and update steps. Firstly, the
aggregation function aggregates neighbor node features of destination nodes,
where we term updated nodes destination nodes. The update function then
updates the destination node features by combining the aggregated neighbor
node features with themselves. Here, neural networks are employed in both the
aggregation and update functions usually.

GNNs have shown their remarkable capabilities for RCs as well as
classification tasks over the years. User-item bipartite graphs, which are
constructed with user-item interactions, are utilized as the input graphs in
the literature. Furthermore, user demography features and item attributes are
utilized as node features in contrast to KGE which treats the features as
entities (nodes). Aggregating neighbor node features is regarded as collecting
collaborative signals. Hence GNN-based approaches for RecSys are the CF-based
models with side information, that possess various expansions for complicated
modeling and large scale applications.

On the other hand, a paper has argued that nonlinearity in GNNs is not
necessary needed for several tasks. The authors have proposed Simple Graph
Convolution (SGC) (Wu et al., 2019b), which is a graph convolution without
activation function, and shown its competitive performance compared to the
state of the art GNNs. The simplification improves interpretability of the
model and reduce computational complexity. We believe that the fact holds in
tasks related to homophily and recommendation tasks are involved in there. In
this paper, we employ a new graph convolution without activation function,
which allows the property of the traslation-based models to be preserved.

###  2.3. Combination of KGE and GNNs

Two different GRL approaches are described in the above, while combination of
the two has been also studied in recent years. In (Wang et al., 2019a), the
authors introduce collaborative knowledge graph (CKG), which merges a user-
item bipartite graph and a KG of items, and apply KGAT to it. KGAT is a model
that combines KGE and GNNs. Firstly, it generates KGE with TransR (Lin et al.,
2015), and subsequently the KGE is fed into knowledge-aware attention-based
GNN layers. TransR and GNN layers are trained simultaneously with the loss
function of TransR and a pair-wise loss function. KGCN (Wang et al., 2019d) is
a mata-path based GNN model, which consists of only GNN layers designed for
KGs. In KGCN, embeddings of entities and relations are initialized with random
values as with normal KGE models, then the embeddings are updated with
knowledge-aware attention-based GNN layers. Nodes that have the same
attributes are connected each other in KGs. That allows GNNs to capture high-
order relations explicitly, resulting in enhancing effectiveness of
aggregation of GNNs. In fact, they reaches the state of the art performance in
several recommendation tasks.

However, the two models aggregates only entity embeddings in GNN layers, and
that possibly incurs irrelevant smoothing (described in Section 3.2). To
alleviate this issue, the proposed model aggregates knowledge queries, which
consists of both entity and relation embeddings. The proposed framework has
two components: KGE and a linear graph convolution, and they are trained
separately in contrast to KGAT.

##  3\. Methodology

We now introduce the proposed Knowledge Query-based Graph Convolution (KQGC),
which improves pre-trained KGE with smoothing effect of graph convolution.
Figure 1 shows the overall framework, which consists of two models:
translation-based KGE model and KQGC. The whole procedure for applying KQGC to
downstream tasks is as follows: 1) a knowledge graph (KG) is fed to the
knowledge graph embedding (KGE) model, then KGE for all the entities and
relations are trained in unsupervised learning; 2) the pre-trained KGE is
input to KQGC as initial node/edge features, and the KQGC is trained with
downstream tasks. Note that the KGE is fixed when KQGC is trained, i.e., the
two models are trained separately. We hereafter describe the details of the
two models (Section 3.1 and 3.2), and then introduce a use case of KQGC in
Rakuten group (Section 3.3).

Figure 1. Framework of KQGC

###  3.1. Translation-based Knowledge Graph Embedding model

In this work, we employ TransE as the translation-based KGE model. In TransE,
the embeddings of all the entities and relations are initialized with random
values, then they are updated by the gradient descent method based on the max-
margin loss function $\mathcal{L}_{\textrm{KGE}}$.

(1) $\displaystyle\mathcal{L}_{\textrm{KGE}}$
$\displaystyle=\sum_{(h,r,t)\in\mathcal{E}}\sum_{(h^{\prime},r,t^{\prime})\in\mathcal{E}^{-1}}\left[\gamma+f(h,r,t)-f(h^{\prime},r^{\prime},t^{\prime})\right]_{+},$

where $(h,r,t)$ is positive triples, which actually exist in the KG,
$(h^{\prime},r,t^{\prime})$ is broken triples, $\gamma$ is the margin,
$f(h,r,t)$ is the score function, and $[\cdot]_{+}=max(0,\cdot)$. The broken
triples are generated by replacing either head- or tail-entity of the positive
triples with an entity randomly chosen. The score function of TransE is as
bellow.

(2) $f(h,r,t)=\|\bm{e}_{h}+\bm{e}_{r}-\bm{e}_{t}\|_{1,2},$

where $\bm{e}_{h}$, $\bm{e}_{r}$ and $\bm{e}_{t}$, are the embeddings of head
entities, relations and tail entities, respectively. In Eq. (2), either L1 or
L2 norm is usually used, we employ L1 norm. Minimizing Eq. (1) with this score
function (Eq.(2)) leads a relation between embeddings of positive triples
$\bm{e}_{h}+\bm{e}_{r}\approx\bm{e}_{t}$ in the same vector space (Figure 2).

From the other perspective, sum of a head and relation embeddings (the red
arrow in Figure 2) reaches a near point to the related tail embeddings,
therefore it can be regarded as a query to visit tail entities related to the
head entity with the relation. In this paper, we term it knowledge query.
KQGC, which is described in the next section, aggregates the knowledge queries
obtained by TransE for aligning neighbor node embeddings in the vector space.

Figure 2. A relation between embeddings of positive triples obtained by
TransE; For simplicity, a 2D case is depicted. As each embedding is
normalized, it is mapped on the unit circle.

###  3.2. Knowledge Query-based Graph Convolution

After training of KGE is completed, the trained KGE is fed into KQGC and
smoothed by it. KQGC follows the MP framework and consists of two steps:
aggregation and update.

In terms of aggregation, KQGC aggregates knowledge queries instead of neighbor
node features. Aggregation of knowledge queries is depicted in Figure 3. The
knowledge query from a source node to the destination node with a relation,
which is aggregated when updating the destination node feature, is defined as

(3) $\mathcal{Q}_{(src,r,dst)}=\bm{e}_{src}+\bm{e}_{r},$

where $\bm{e}_{src}$ and $\bm{e}_{r}$ are embeddings of the source node and
the relation, and the triple $(src,r,dst)$ exists in the KG. In the case that
the KG is a directed graph and we have only embedding of one direction
relation, we obtain that of the reversed relation by multiplying the embedding
by -1. One of the main efficacy of aggregating knowledge queries is alignment
of node embeddings in the vector space, which is shown in the right-hand side
of Figure 3. We think of the case that updates embeddings of user A and item A
as an example. For simplicity, let the aggregation be simple mean operation
here. Assuming that each of the entity and relation embeddings is mapped on
the unit circle as shown in Figure 3, the aggregated (averaged) neighbor node
features for both user A and item A end up being similar (Figure 3 (a)), even
though they do not have any nodes shared in common. On the other hand, the
aggregated knowledge queries are aligned to near points to the embeddings of
the destination nodes, resulting in preservation of similarity obtained from
KGE model (Figure 3 (b)).

In the update phase, KQGC combines the aggregated knowledge queries with the
target node embedding using linear transformation. We do not leverage non-
linear function in this phase in order to preserve the property of
translation-based model when multiple layers of KQGC are stacked. SGC has
shown adequate capability of graph convolution without nonlinear function for
several tasks related to homophilicity. Intuitively recommendation task is
included to the tasks, and we believe that absence of nonlinear function is
not critical. We provide formulations of aggregation and update in below.

Figure 3. Aggregation of knowledge queries in KQGC

####  3.2.1. Aggregator

Here we propose mean- and attention aggregators. We redefine notation of
knowledge queries for multiple KQGC layers, as follows.

(4) $\mathcal{Q}^{l-1}_{(u,r,v)}=\bm{h}^{l-1}_{u}+\bm{h}^{l-1}_{r},$

where $l$ indicates $l$-th layer, $\mathcal{Q}^{l}_{urv}$ is the $l$-th query
from source $u$ to the destination $v$ with relation $r$, $\bm{h}^{l}_{u}$ and
$\bm{h}^{l}_{r}$ are the $l$-th embeddings of the source and relation,
respectively. KGE obtained from TransE is utilized as initial embeddings of
all the nodes and relations, i.e., $\bm{h}^{0}_{u}=\bm{e}_{u}$,
$\bm{h}^{0}_{r}=\bm{e}_{r}$. For the second and subsequent ones, node and
relation embeddings outputted from the previous layer are input to the next
layer. The two types of aggregators are formulated as follows.

#### Mean aggregator

This aggregator simply takes the average of neighbor knowledge queries, which
is formulated as,

(5) $\displaystyle\bm{m}_{\mathcal{Q}}^{l}$
$\displaystyle=\textrm{MEAN}\left(\left\\{\mathcal{Q}^{l-1}_{(u,r,v)},u\in\mathcal{N}(v),r\in\mathcal{R}(u,v)\right\\}\right),$

where $\bm{m}_{\mathcal{Q}}^{l}$ is the $l$-th message of knowledge queries,
$\mathcal{N}(v)$ is the set of neighbor nodes of node $v$, $\mathcal{R}(u,v)$
is the set of relations between $u$ and $v$.

#### Attention aggregator

Rather than aggregating neighbor knowledge queries equally, attention
aggregator considers the importance of each knowledge queries and aggregates
them with different weights. In this paper, we provide two types of attention
aggregators, which are formulated as,

(6) $\displaystyle\bm{m}^{l}_{\mathcal{Q}}$
$\displaystyle=\sum_{u\in\mathcal{N}(v)}\alpha_{(u,r,v)}\mathcal{Q}^{l-1}_{(u,r,v)},$
(7) $\displaystyle\alpha_{(u,r,v)}$
$\displaystyle=\frac{e_{(u,r,v)}}{\sum_{k\in\mathcal{N}(v)}e_{(k,r,v)}},$ (8)
$\displaystyle(Attention1)\ \ \ e_{(u,r,v)}$
$\displaystyle=\left(\mathcal{Q}^{l-1}_{(u,r,v)}\right)^{T}\bm{h}_{v}^{l-1},$
(9) $\displaystyle(Attention2)\ \ \ e_{(u,r,v)}$
$\displaystyle=\textrm{LeakyReLU}\left(\bm{a}^{T}\left(\mathcal{Q}^{l-1}_{(u,r,v)}\parallel\bm{h}^{l-1}_{v}\right)\right),$

where $\alpha_{(u,r,v)}$ is normalized attention coefficient,
$\bm{a}\in\mathbb{R}^{2H}$ is the trainable parameter, $H$ is dimension of the
embeddings, and $\parallel$ denotes concatenation. The first one (Eq. (8))
employs inner product between the knowledge query and the destination node to
calculate attention coefficients, which is the same as the attention mechanism
of KGCN. Knowledge queries that are closer to the destination node in the
vector space are aggregated with higher weights in this attention mechanism.
The second one (Eq.(9)) has trainable parameters and they allow us to
automatically design how to aggregate knowledge queries with appropriate
attention coefficients, based on the loss function of the downstream tasks.
The formulation is inspired by the self-masked attention mechanism of GAT.

####  3.2.2. Update

After aggregating knowledge queries, new embeddings of all the nodes and
relations are obtained by combining the destination node embedding with the
aggregated knowledge queries. We employ the following update rule.

(10) $\displaystyle\bm{h}_{v}^{l}$
$\displaystyle=W^{l}(\bm{h}_{v}^{l-1}+\bm{m}^{l}_{\mathcal{Q}})+\bm{b}^{l},$
(11) $\displaystyle\bm{r}^{l}$ $\displaystyle=W^{l}\bm{r}^{l-1}+\bm{b}^{l},$

where $\bm{h}_{v}^{l}$ and $\bm{r}^{l}$ are the updated embeddings of the
target nodes $v$ and all the relations, which are inputs of the next layer,
$W^{l}$ and $\bm{b}^{l}$ are the $l$-th trainable weight parameters. This
update rule simply sums up the destination node embedding and the aggregated
knowledge queries, and then map them to new vector space with linear
transformation. The transformation is also applied to the relation embeddings
so that translation between entites and relations can be constructed in the
new vector space as well. Therefore we do not employ nonlinear function in
this formulation.

###  3.3. Applications of KQGC in Recommender Systems of Rakuten Group

Rakuten group has various services and each service employs different model,
therefore it is impossible to replace all the models with end-to-end fashion
of KQGC. Instead, we attempt to improve the services by generating general
user embeddings that can be used across various Rakuten services. A framework
for applying KQGC to various Rakuten services is depicted in Figure 4. In this
framework, KQGC and models in different services are completely separated for
the portability. User embeddings obtained from KQGC are utilized in common as
input features of each model with the baseline features. Types of the baseline
features depend on types of services, which include user demographic features
or user’s purchase history.

In this paper, we focus on a Rakuten service called Target Prospecting (TP),
and evaluate KQGC on the task of TP. The task of TP is to find prospective
customers for clients (e.g., shops or brands) and prepare a list of top k
active Rakuten users. The definition of active users is: the users who buy
from Rakuten Ichiba regularly within average buying period. Currently, we have
more than 40 millions active users. This paper employs XGBoost, which is a
binary classifiers, as the service-side model. i.e., user embeddings obtained
from KQGC and the AIris baseline features (refer to Section 4.2) are input to
the binary classifier, and it classifies prospective customers with
true/false. We hereafter describe how to construct a knowledge graph for KQGC
and how to train KQGC for our AIris TP task.

Figure 4. A framework for applying KQGC to several Rakuten services

####  3.3.1. How to construct knowledge graphs

Rakuten group has the largest E-commerce platform called Rakuten Ichiba, which
stores rich data of user behavior and item attributes in there. Purchase
behavior of users is intuitively informative for not only predicting
perspective users for clients but also capturing user preferences, which can
be generally used for other services. Hence we leverage the data on Rakuten
Ichiba111https://www.rakuten.co.jp/ for constructing KGs, and obtain the
general user embeddings based on the KGs. The procedure of constructing KGs is
as follows: 1) collect seed users, who are picked up based on purchase history
from Rakuten Ichiba users. 2) collect all the items purchased by them. 3)
extract demography features of the seed users and attributes of the items. 4)
construct a KG: connect users and items with purchase history; attributes are
extracted as entities and they are connected to users and items. After
creating the KG, we apply the framework of KQGC to it, then we finally obtain
the general user embedding for the seed users.

####  3.3.2. Training

As our goal here is to obtain user embeddings from the KQGC, there is no
decoder in the downstream task. Therefore, we employ the following
unsupervised loss function for training KQGC.

(12) $\displaystyle\mathcal{L}_{\textrm{CF}}$
$\displaystyle=\sum_{(\mathcal{U},\mathcal{I})\in\mathcal{P}}\sum_{(\mathcal{U},\mathcal{I}^{\prime})\in\mathcal{P}^{-1}}\left[\gamma+f(\bm{h}_{\mathcal{U}},\bm{h}_{\mathcal{I}})-f(\bm{h}_{\mathcal{U}},\bm{h}_{\mathcal{I}^{\prime}})\right]_{+},$
(13) $\displaystyle f(\bm{h}_{\mathcal{U}},\bm{h}_{\mathcal{I}})$
$\displaystyle=\|\bm{h}_{\mathcal{U}}+\bm{h}_{\textrm{purchase}}-\bm{h}_{\mathcal{I}}\|_{1,2},$

where $(\mathcal{U},\mathcal{I})\in\mathcal{P}$ is the positive pairs between
users and items with purchase relation,
$(\mathcal{U},\mathcal{I}^{\prime})\in\mathcal{P}^{-1}$ is the negative one,
$f(\bm{h}_{\mathcal{U}},\bm{h}_{\mathcal{I}})$ is the score function
especially for user-item interaction, $\bm{h}_{\mathcal{U}}$ and
$\bm{h}_{\mathcal{I}}$ are user and item embeddings,
$\bm{h}_{\textrm{purchase}}$ is purchase-relation embeddings.
$\mathcal{I}^{\prime}$ denotes negative items, which are generated by
replacing the positive item with an item randomly chosen in the positive
pairs. Here we employ L1 norm for Eq. (13).

##  4\. Experiments

In this section, we conduct experiments to evaluate the performance of our
model using the same metric (PR-AUC) which is being used in AIris TP for
evaluation. The KQGC model has been implemented to the Rakuten AIris TP to
provide effective target prospecting. We first explain the AIris TP system
overview and experimental settings. Then, we evaluate the effectiveness of our
model with five brand datasets (the name of the brands have been kept
anonymous ) by comparing it with the baseline model. Finally, we briefly
discuss the effectiveness of the model in the real target prospecting
scenario.

###  4.1. Overview of the Rakuten AIris TP

In this section, we briefly describe the Rakuten Airis TP framework. Figure 5
shows the dashboard of AIris TP for clients. A client/marketer can upload a
file of users (to find out similar users) or she can use “Seed ID Manager ” to
select appropriate seed users for the task or retrieve the previous purchasers
of a product/brand using “Purchaser ID Finder”. There are two more options for
travel (Travelers ID Finder) and books (Book Readers ID Finder) related
targeting. After uploading the seed users using one of the options mentioned
above, clients can start a job for finding lookalike customers for their
business purpose.

Figure 5. Rakuten AIris TP Framework for marketers and clients.

###  4.2. Experimental set-up

#### Datasets

In AIris TP, for a specific product/brand we pick up the users who already
bought that product/brand in previous months and then AIris TP extracts
potential customers for a product/brand who have high probability to buy the
product/brand in next month. We adopt five cosmetic brands as the AIris
clients in this experiment and evaluate models based on whether AIris can
extract accurate potential customers for each of the client from given users,
with the features obtained from the models.

To treat this problem as binary classification, we arrange both positive users
(label 1) and negative users (label 0) for each client, in the datasets of TP.
Positive users are those who purchased at least one item of the client in a
certain time-window, i.e., positive users correspond to the accurate potential
customers in this evaluation. On the other hand, negative users are those who
purchased no item in the same time-window as positive users. Ratio between
positive and negative users is set to around 1 : 3 for each client. In terms
of data split, we collect train/validation and test users in different time-
windows to remove possible data leakage. 20K users are collected in two months
from Jul. 1st, 2021 to Oct. 31st, 2021 as training and validation data sets of
each client, and they are randomly divided into 6 (training) : 4 (validation).
5K test users for each client are collected in Sep. 1st, 2021 - Sep. 31st,
2021 (one month). If the number of positive users for a client in the time-
window is less than 20K or 5K, the number is used instead of 20K or 5K.
Purchase behavior for constructing KG is collected in Feb. 1st, 2021 - Jul.
31st, 2021, following the way described in 3.3.1.Statics of the datasets of TP
and the KG used for training KQGC are shown in table 1 and table 2,
respectively.

Table 1. Statics of the AIrist datasets |  | Brand A | Brand B | Brand C | Brand D | Brand E
---|---|---|---|---|---|---
Training | # positive users | 3784 | 3768 | 3719 | 1668 | 3753
# negative users | 11216 | 11232 | 11281 | 5504 | 11247
# total users | 15000 | 15000 | 15000 | 6672 | 15000
Validation | # positive users | 1255 | 1241 | 1285 | 213 | 1206
# negative users | 3745 | 3759 | 3715 | 639 | 3794
# total users | 5000 | 5000 | 5000 | 852 | 5000
Test | # positive users | 1285 | 1238 | 1264 | 1100 | 1233
# negative users | 3715 | 3715 | 3736 | 3300 | 3767
# total users | 5000 | 5000 | 5000 | 4400 | 5000
Table 2. Statics of the KG for training KQGC # users | # items | # edges | # relations
---|---|---|---
85,402 | 1,302,877 | 2,360,012 | 1 (purchase)

#### Baselines

To demonstrate the effectiveness, we compare our proposed model with the
current model and on production and other KGE models.

  * •

Baseline (AIris TP): This is the current model on production (see Fig. 5). It
is based on XGBoost model. This model uses five different features (note that
customer true identity is totally hidden to the dataset and model):

Demographic Features: Demographic features such as age, gender, region.
Point Summary: Rakuten users can gain points while buying different
products/services. This feature exhibits point status such as current
available points.
Point Feature: Transaction of points such as acquired/used points from
online/offline shops/ merchants.
Genre level Purchase History: Like other E-commerce companies Rakuten group
maintains ”genre” hierarchy. In this feature we capture the shopping trends in
popular genres.

  * •

TransE: Only TransE generated vectors has been employed here for AIris TP user
prediction as baseline.

#### Evaluation

We evaluate PR-AUC of AIris with user embeddings (input features) obtained
from each model. Three types of input features are compared in this
experiment: baseline features, KGE of TransE and KQGC. The baseline features
are user attributes including demography, genre preference, whose dimension is
157. In terms of KGE of TransE and KQGC, we concatenate each KGE with the
baseline features, and then input it to AIris, i.e., the dimension of the
input features is 257 when that of KGE is 100.

#### Model settings

The models are implemented in PyTorch and Deep Graph Library (Wang et al.,
2019c). The training and inference run on a single GPU ’NVIDIA Tesla V100’.
Hyperparamters of TransE are as follows. The number of epochs is 10,000, batch
size is 10,000, learning rate is 0.001, dimension of embeddings is 100, ratio
between positive and negative triples is 1 : 1, and margin $\gamma$ is 1.0.
Hyperparameters of KQGC are as follows. The number of GNN layers is 1, hidden
and output layers is 100, KGE of TransE in 5000 epochs is used as input of
KQGC, ratio between positive and negative pairs is 1 : 3, graph sampling where
10 neighbor nodes are randomly sampled is used only in training phase, and
others are the same as TransE. Trainable parameters are initialized with
Xavier normalization.

###  4.3. Results

Our goal is to improve PR-AUC for various clients. Hence we hereafter
emphasize the average of the PR-AUCs for all the clients. Note that user
embeddings and baseline features are shared among all the clients, on the
other hand, AIris is optimized for each client independently. The best PR-AUCs
over 10000 epochs are shown in table 3. In table 3, the values in parentheses
are improvement rate (%) compared to the baseline and the other values are PR-
AUCs. The highest PR-AUC among different input features is marked in bold for
each column. Table 3 shows that KQGC outperforms both the baseline and the
original TransE except for Brand D, and KQGC(mean) reaches the best PR-AUC for
the average of all the clients. Fig. 6 shows evolution of PR-AUC of the
averaged improvement rate with epochs. From Fig. 6, we can observe that
KQGC(mean and attn1) achieves more stable performance than others. That mean
aggregator’s performance is the best and attn2 aggregator’s one is unstable
possibly because the embedding module and the prediction one are separated.
The attention mechanism of KQGC are automatically designed by the loss
function of pre-training (Eq.13), therefore it is difficult to construct an
attention mechanism that is suitable for TP.

Table 3. Improvement rate compared to the baseline model in PR-AUC  Input features | Brand A | Brand B | Brand C | Brand D | Brand E | AVG.
---|---|---|---|---|---|---
Baseline | 0.693 | 0.678 | 0.593 | 0.749 | 0.732 | 0.689
TransE | 0.706 (+1.83) | 0.699 (+3.13) | 0.604 (+1.90) |  0.786 (+4.95) | 0.737 (+0.97) | 0.706 (+2.50)
KQGC(mean) |  0.712 (+2.70) | 0.703 (+3.62) | 0.607 (+2.46) | 0.784 (+4.65) |  0.749 (+2.32) |  0.711 (+3.15)
KQGC(attn1) | 0.708 (+2.11) |  0.705 (+3.88) | 0.607 (+2.52) | 0.781 (+4.26) | 0.741 (+1.23) | 0.708 (+2.80)
KQGC(attn2) | 0.710 (+2.46) | 0.702 (+3.55) |  0.612 (+3.27) | 0.784 (+4.67) | 0.740 (+1.09) | 0.710 (+3.00)
Figure 6. Evolution of the average of PR-AUC improvement rate with epochs

###  4.4. Model Deployment

The AIris TP is a well-known Rakuten target prospecting framework. Rakuten
group has started this service from the year of 2018. Periodically we evaluate
the deployed model’s performance and improve the model. The proposed KQGC is
in the testing phase for deployment on our AIris TP framework. The major
advantage of AIris TP is: it allows the marketers/clients to perform the
target prospecting without training the entire model from scratch when we have
a new task (job), e.g., find the potential users with similar behavior
patterns to new brand’s existing users. The tentative customer conversion rate
(CVR) is expected to go much higher in comparison with the previous standard
solution.

##  5\. Conclusion

In this paper, we have introduced a novel model for recommender systems that
leverages both KGE and graph convolution. KQGC smooths knowledge graph
embedding (KGE) obtained from translation-based models with the aggregation of
neighbor knowledge queries, and helps adjacent entities have similar
embeddings. Empirical result on Rakuten group’s real data shows that KQGC
outperforms current AIris TP baseline models including TransE, which is the
original translation-based model, and we also observed smoothing KGE is
effective for improving performance on recommendation tasks.

In future work, we will explore the following three things. (1) Deeper
analysis of our model; In this work, our model employs one convolutional
layer, and it is evaluated on only our private dataset. To confirm the
effectiveness of our model more strongly, we will evaluate our model with more
than two layers, and compare it with several SoTA models on various public
datasets. (2) Incorporation of side information; continuous attributes such as
image- or text-embeddings are difficult to be extracted as entities on a KG.
Hence we need to investigate how we can effectively combine KGE with those
continuous attributes as inputs of KQGC. (3) Generality of our model; Our
ultimate goal is to apply user embeddings obtained from KQGC to various
services. As this paper focuses on prospect recommendation task, we will
evaluate the user embeddings on different services and investigate the
generality as our next research direction.

## References

  * (1)
  * Billsus and Pazzani (1998) Daniel Billsus and Michael J. Pazzani. 1998.  Learning Collaborative Information Filters. In _Proceedings of the Fifteenth International Conference on Machine Learning_ _(ICML ’98)_. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 46–54.
  * Bordes et al. (2013) Antoine Bordes, Nicolas Usunier, Alberto Garcia-Durán, Jason Weston, and Oksana Yakhnenko. 2013\.  Translating Embeddings for Modeling Multi-Relational Data. In _Proceedings of the 26th International Conference on Neural Information Processing Systems - Volume 2_ (Lake Tahoe, Nevada) _(NIPS’13)_. Curran Associates Inc., Red Hook, NY, USA, 2787–2795.
  * Breese et al. (1998) John S. Breese, David Heckerman, and Carl Kadie. 1998\.  Empirical Analysis of Predictive Algorithms for Collaborative Filtering. In _Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence_ (Madison, Wisconsin) _(UAI’98)_. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 43–52.
  * Gilmer et al. (2017) Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. 2017\.  Neural Message Passing for Quantum Chemistry. In _Proceedings of the 34th International Conference on Machine Learning - Volume 70_ (Sydney, NSW, Australia) _(ICML’17)_. JMLR.org, 1263–1272.
  * Guo et al. (2020) Qingyu Guo, Fuzhen Zhuang, Chuan Qin, Hengshu Zhu, Xing Xie, Hui Xiong, and Qing He. 2020.  A Survey on Knowledge Graph-Based Recommender Systems.  _IEEE Transactions on Knowledge and Data Engineering_ (2020), 1–1.  https://doi.org/10.1109/TKDE.2020.3028705
  * Hamilton et al. (2017) Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017\.  Inductive Representation Learning on Large Graphs. In _Advances in Neural Information Processing Systems_ , I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.), Vol. 30. Curran Associates, Inc.  https://proceedings.neurips.cc/paper/2017/file/5dd9db5e033da9c6fb5ba83c7a7ebea9-Paper.pdf
  * Hu et al. (2020) Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. 2020\.  _Heterogeneous Graph Transformer_.  Association for Computing Machinery, New York, NY, USA, 2704–2710.  https://doi.org/10.1145/3366423.3380027
  * Ji et al. (2015) Guoliang Ji, Shizhu He, Liheng Xu, Kang Liu, and Jun Zhao. 2015.  Knowledge Graph Embedding via Dynamic Mapping Matrix. In _Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_. Association for Computational Linguistics, Beijing, China, 687–696.  https://doi.org/10.3115/v1/P15-1067
  * Kipf and Welling (2017) Thomas N. Kipf and Max Welling. 2017.  Semi-Supervised Classification with Graph Convolutional Networks. In _International Conference on Learning Representations (ICLR)_.
  * Koren et al. (2009) Yehuda Koren, Robert Bell, and Chris Volinsky. 2009\.  Matrix Factorization Techniques for Recommender Systems.  _Computer_ 42, 8 (2009), 30–37.  https://doi.org/10.1109/MC.2009.263
  * Lin et al. (2015) Yankai Lin, Zhiyuan Liu, Maosong Sun, Yang Liu, and Xuan Zhu. 2015.  Learning Entity and Relation Embeddings for Knowledge Graph Completion. In _Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence_ (Austin, Texas) _(AAAI’15)_. AAAI Press, 2181–2187.
  * Nickel et al. (2011) Maximilian Nickel, Volker Tresp, and Hans-Peter Kriegel. 2011\.  A Three-Way Model for Collective Learning on Multi-Relational Data. In _Proceedings of the 28th International Conference on International Conference on Machine Learning_ (Bellevue, Washington, USA) _(ICML’11)_. Omnipress, Madison, WI, USA, 809–816.
  * Sarwar et al. (2000) Badrul Sarwar, George Karypis, Joseph Konstan, and John Riedl. 2000.  Analysis of Recommendation Algorithms for E-Commerce. In _Proceedings of the 2nd ACM Conference on Electronic Commerce_ (Minneapolis, Minnesota, USA) _(EC ’00)_. Association for Computing Machinery, New York, NY, USA, 158–167.  https://doi.org/10.1145/352871.352887
  * Sarwar et al. (2001) Badrul Sarwar, George Karypis, Joseph Konstan, and John Riedl. 2001.  Item-Based Collaborative Filtering Recommendation Algorithms. In _Proceedings of the 10th International Conference on World Wide Web_ (Hong Kong, Hong Kong) _(WWW ’01)_. Association for Computing Machinery, New York, NY, USA, 285–295.  https://doi.org/10.1145/371920.372071
  * 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 _The Semantic Web_ , Aldo Gangemi, Roberto Navigli, Maria-Esther Vidal, Pascal Hitzler, Raphaël Troncy, Laura Hollink, Anna Tordai, and Mehwish Alam (Eds.). Springer International Publishing, Cham, 593–607.
  * Shardanand and Maes (1995) Upendra Shardanand and Pattie Maes. 1995.  Social Information Filtering: Algorithms for Automating “Word of Mouth”. In _Proceedings of the SIGCHI Conference on Human Factors in Computing Systems_ (Denver, Colorado, USA) _(CHI ’95)_. ACM Press/Addison-Wesley Publishing Co., USA, 210–217.  https://doi.org/10.1145/223904.223931
  * Trouillon et al. (2016) Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. 2016.  Complex Embeddings for Simple Link Prediction. In _Proceedings of the 33rd International Conference on International Conference on Machine Learning - Volume 48_ (New York, NY, USA) _(ICML’16)_. JMLR.org, 2071–2080.
  * van den Berg et al. (2017) Rianne van den Berg, Thomas N. Kipf, and Max Welling. 2017\.  Graph Convolutional Matrix Completion.  arXiv:1706.02263 [stat.ML]
  * Veličković et al. (2018) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. 2018.  Graph Attention Networks.  _International Conference on Learning Representations_ (2018).  https://openreview.net/forum?id=rJXMpikCZ accepted as poster.
  * Wang et al. (2019d) Hongwei Wang, Miao Zhao, Xing Xie, Wenjie Li, and Minyi Guo. 2019d.  Knowledge Graph Convolutional Networks for Recommender Systems. In _The World Wide Web Conference_ (San Francisco, CA, USA) _(WWW ’19)_. Association for Computing Machinery, New York, NY, USA, 3307–3313.  https://doi.org/10.1145/3308558.3313417
  * Wang et al. (2019c) Minjie Wang, Lingfan Yu, Da Zheng, Quan Gan, Yu Gai, Zihao Ye, Mufei Li, Jinjing Zhou, Qi Huang, Chao Ma, Ziyue Huang, Qipeng Guo, Hao Zhang, Haibin Lin, Junbo Zhao, Jinyang Li, Alexander J. Smola, and Zheng Zhang. 2019c.  Deep Graph Library: Towards Efficient and Scalable Deep Learning on Graphs.  _CoRR_ abs/1909.01315 (2019).  arXiv:1909.01315 http://arxiv.org/abs/1909.01315
  * Wang et al. (2019a) Xiang Wang, Xiangnan He, Yixin Cao, Meng Liu, and Tat-Seng Chua. 2019a.  KGAT: Knowledge Graph Attention Network for Recommendation. In _KDD_. 950–958.
  * Wang et al. (2019b) Xiang Wang, Xiangnan He, Meng Wang, Fuli Feng, and Tat-Seng Chua. 2019b.  Neural Graph Collaborative Filtering. In _Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval_ (Paris, France) _(SIGIR’19)_. Association for Computing Machinery, New York, NY, USA, 165–174.  https://doi.org/10.1145/3331184.3331267
  * Wang et al. (2021) Xiang Wang, Tinglin Huang, Dingxian Wang, Yancheng Yuan, Zhenguang Liu, Xiangnan He, and Tat-Seng Chua. 2021.  Learning Intents behind Interactions with Knowledge Graph for Recommendation. In _Proceedings of the Web Conference 2021_ (Ljubljana, Slovenia) _(WWW ’21)_. Association for Computing Machinery, New York, NY, USA, 878–887.  https://doi.org/10.1145/3442381.3450133
  * Wang et al. (2020) Xiao Wang, Ruijia Wang, Chuan Shi, Guojie Song, and Qingyong Li. 2020.  Multi-component graph convolutional collaborative filtering. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 34. 6267–6274.
  * Wu et al. (2019b) Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. 2019b.  Simplifying Graph Convolutional Networks. In _Proceedings of the 36th International Conference on Machine Learning_. PMLR, 6861–6871.
  * Wu et al. (2019a) Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. 2019a.  A Comprehensive Survey on Graph Neural Networks.  _CoRR_ abs/1901.00596 (2019).  arXiv:1901.00596 http://arxiv.org/abs/1901.00596
  * Yang et al. (2015) Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. 2015.  Embedding Entities and Relations for Learning and Inference in Knowledge Bases. In _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_ , Yoshua Bengio and Yann LeCun (Eds.).  http://arxiv.org/abs/1412.6575
  * Ying et al. (2018) Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. 2018.  Graph Convolutional Neural Networks for Web-Scale Recommender Systems. In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ _(KDD ’18)_. Association for Computing Machinery, 974–983.  https://doi.org/10.1145/3219819.3219890
  * Zheng et al. (2018) Lei Zheng, Chun-Ta Lu, Fei Jiang, Jiawei Zhang, and Philip S. Yu. 2018.  Spectral Collaborative Filtering. In _Proceedings of the 12th ACM Conference on Recommender Systems_ (Vancouver, British Columbia, Canada) _(RecSys ’18)_. Association for Computing Machinery, New York, NY, USA, 311–319.  https://doi.org/10.1145/3240323.3240343