# TotalBotWar: A New Pseudo Real-time Multi-action Game Challenge and
Competition for AI

Alejandro Estaben, César Díaz, Raul Montoliu  Insitute of new imaging
Technologies
Jaume I University
Castellón, Spain
Email<EMAIL_ADDRESS>Diego Pérez-Liebana  Game AI group
Queen Mary Universtiy of London
London, UK
Email<EMAIL_ADDRESS>
###### Abstract

This paper presents TotalBotWar, a new pseudo real-time multi-action challenge
for game AI, as well as some initial experiments that benchmark the framework
with different agents. The game is based on the real-time battles of the
popular TotalWar games series where players manage an army to defeat the
opponent’s one. In the proposed game, a turn consists of a set of orders to
control the units. The number and specific orders that can be performed in a
turn vary during the progression of the game. One interesting feature of the
game is that if a particular unit does not receive an order in a turn, it will
continue performing the action specified in a previous turn. The turn-wise
branching factor becomes overwhelming for traditional algorithms and the
partial observability of the game state makes the proposed game an interesting
platform to test modern AI algorithms.

##  I Introduction

In recent years, games have proven to be important test-beds for Artificial
Intelligence (AI). For instance, deep reinforcement learning has enabled
computers to learn how to play games such as Chess [1], Go [1], Atari games
[2], and many other games [3]. Despite these important advances, there are
still games that pose important challenges for state-of-the-art AI agents.
Some examples are Blood Bowl [4], Legend of Code and Magic [5], MicroRTS [6],
FightingICE [7], Hanabi [8], Splendor [9], StarCraft [10], and the General
Video Game AI framework [11], among others.

In this paper, we propose TotalBotWar, a new pseudo real-time challenge for
game AI. The game is inspired by the real-time battles of the popular TotalWar
game series111Creative Assembly, https://www.totalwar.com/, where two players
control respective armies with the objective of defeating each other. On each
turn, the agent must decide where the unit must move to. When two opposite
units collide, they will start to fight. The result of the combat depends on
the type of units and their attributes. If during a turn a unit does not
receive any order, it will continue its movement following the previous one,
or it will stand still if none was given. This introduces unknown information
on the state: it is possible to know that an enemy unit is moving, but not its
destination. The game has a high number of possible actions in a turn
($\approx 6.7E7$) and also a huge number of possible states ($\approx
3.3E29$), which provides a significant challenge for AI agents. The game,
implemented using the CodinGame SDK222https://www.codingame.com/, has already
been made available online at this
platform333https://www.codingame.com/contribute/view/486222077fe22e3aa6bcdc0f729dd46223bb.

An initial set of experiments are also presented, where five different agents
are benchmarked to give a baseline to future researchers. Three of them are
primary agents where a) units never move (but can fight), b) always move
forward, or c) move to a random localisation. The two remaining are more
sophisticated. The first one applies human knowledge by using a heuristic
function. The last one implements the Online Evolutionary planning (OEP)
algorithm proposed by Justesen et al. [12]. Preliminary results show that the
heuristic-based and OEP overcome the three primary agents, being the OEP
preferable.

Summarising, this paper presents three main novelties:

  * •

We present TotalBotWar a new pseudo-real-time multi-action challenge for game
AI.

  * •

As far as we know, this is the first work implementing real-time TotalWar-
style battles as a game AI challenge.

  * •

We assess the performance of five agents, including the Online Evolutionary
Planning algorithm, in the proposed game AI challenge.

The rest of the paper has been organised as follows. Section II presents the
main characteristics of the game including how agents interact with the game
engine. A set of baseline agents and some preliminary experiments are showed
in Sections III and IV. Finally, the most important conclusions drawn from
this work are summarised in Section V.

##  II TotalBotWar

###  II-A Game Overview

_TotalBotWar_ is a 1 vs 1, pseudo real-time, multi-action game, partially
inspired in the real-time battles of the _Total War_ games series. In our
game, both players start with the same number of military units and their
objective is to defeat the other player. The winner is the player who first
destroys all the opponent’s units or the one with more units alive on the
battlefield when the maximum number of turns is reached, which is set to
$400$.

There are four different types of units: Swordsmen, Spearmen, Archers and
Knights (see Figure 1). The game uses a classical _rock-paper-scissors_ combat
scheme, where swordsmen are good against spearmen, spearmen are good versus
knights and finally, knights are good against swordsmen. Archers are an
exception: they can attack from distance but are very weak in a face to face
combat.

(a)

(b)

(c)

(d)

Figure 1: The four game units, from left to right: swordsmen, spearmen,
archers and knights.

Each unit has an attribute vector modelling its behaviour. The attributes are
Health Points, Attacking Strength, Defence, Charge Power, Charge Resistance,
Moving Speed and defence against Arrows. Besides, archers also have Throwing
Distance and Arrow Damage. Table I shows the values assigned to each attribute
for each unit type.

TABLE I: Values of the attributes of each unit type. Attribute | Swordsmen | spearmen | Knights | Archers
---|---|---|---|---
Health Points | 250 | 250 | 200 | 100
Attacking Strength | 20 | 15 | 12 | 10
Defence | 10 | 20 | 12 | 5
Charge Power | 5 | 10 | 100 | 5
Charge resistance | 25 | 125 | 15 | 0
Moving Speed | 15 | 10 | 40 | 15
Defence against Arrows | 10 | 30 | 30 | 10
Throwing Distance | - | - | - | 450
Arrow damage | - | - | - | 20

Units can move to any place of the battlefield. Two units from the same agent
can’t overlap, while they will fight if belonging to different armies. If an
unit reaches the limits of the battlefield, it stops. Archers always shoot
arrows to enemy troops into the attacking range. Troops suffer friendly-fire
if they are close to an opponent unit receiving arrows.

The game has three different leagues or levels. When using the CodinGame
platform, the player has to first implement a bot to defeat the system bot of
the first league. After, he/she must implement a new one to defeat the system
bot of the second league before passing to the third one. In the third league,
the CodingGame platform allows testing the player’s bot versus the bots
implemented by many other players. Alternatively, the three leagues can be
used isolated from CodingGame platform to test AI algorithms and to rule AI
competitions. We plan to use the third league as a future Game AI competition.

Figure 2: Screenshot of the first league of the game. The army has 4 units,
one of each type. Figure 3: Screenshot of the second league of the game during
the draft phase. In this league, the army is composed by 9 different units.
The composition of the army is defined at draft phase.  Figure 4: Screenshot
of the third league of the game during the battle phase. The army is composed
by 30 units and includes a General. The General is the unit with ID 1 and its
background colour is highlighted.

In the first league (see Figure 2), the army of each player consists of just
one unit of each type and units start in predefined initial locations on the
battlefield. The second league introduces the draft phase (see Figure 3)
where, in the first 9 turns of the game, the agents must select how many units
of each type will be part of their armies and their initial positions on the
battlefield. Therefore, the total number of units is 9. There is no
restriction on the number of units of each type, i.e. the army can be composed
by 9 archers if this is the decision of the agent. On each turn, players
select units simultaneously, knowing only the units selected by both players
in all previous turns.

In the third league (see Figure 4), the army is composed of 30 units,
therefore the draft lasts until the $30^{th}$ turn of the game. Additionally,
the third league introduces the General unit, which is a highly important unit
that can be crucial in the game. All units within a distance of $150$ pixels
to their general increase (multiplicatively) their attributes by $1.25$.
However, if the general is dead, all units decrease their attributes by
$0.75$. The general is always the first unit selected in the draft and can be
of any type.

The size of the battlefield is $1920\times 1080$ pixels. The size of the units
is $150\times 150$ pixels in leagues 1 and 2, and $75\times 75$ pixels in the
third league.

###  II-B Main characteristics

The main characteristics for game AI are as follows:

  * •

It is a 1 vs 1 game.

  * •

It is (pseudo) real-time. Although the game engine performs actions in the
order indicated in the turn, the effect of this order is practically
negligible. Similarly, the effect of which player performs first the actions
is minimal.

  * •

Not all information is known in the state. The state contains information
about the actual position of the enemy units and if they are moving or not,
but it does not provide information about the final target where they are
moving.

  * •

It is multi-action since in the same turn more than one action can be
performed for each different unit owned in the battlefield.

  * •

The agents have just $200$ms to decide the actions to be executed on each the
turn. This is a restriction of the core of CodingGame engine.

  * •

It has a very large number of possible actions in a turn ($\approx 6.7E7$) and
possible states ($\approx 3.3E29$).

###  II-C Motivation

This work has two principal motivations. On the one hand, the game has been
included in CodinGame platform to be used as a tool to learn programming
skills fascinatingly. CodinGame platform allows the use of many programming
languages, and it is possible to see the effect of the source code used for
the agent developed. That can help beginners to learn programming languages
faster than through a more traditional style of teaching. The first league of
the game is perfect for this purpose. On the other hand, the second and third
leagues are dedicated to the developing of new game AI agents due to their
complexity. The third league is the one selected to be a game AI competition
in the future.

The develop a new game AI challenge using the CodinGame SDK has three main
advantages with respect to completely develop it from zero:

  1. 1.

Developers can take advantage of the framework with contains useful code that
can make easier to develop a new game. 2

  2. 2.

Users can program their agents in their preferred programming language instead
of being restricted, as usually happens, to use just the one used to develop
the game.

  3. 3.

Sometimes to start with a new game AI challenge is hard since, for instance,
users not always have installed the correct libraries to run the game. The use
of CodinGame platform avoid this kind of problems.

However, some constraints must be accomplished as the maximum size of the
battlefield, the amount of thinking time per turn for the agents and the
maximum number of turns, among others.

The game is inspired in Total War games since they are very popular for the
general public. Similarly to other popular games AI challenges as StarCraft AI
competition, this can engage students to learn programming languages in
general and AI in particular since they can be highly motivated to develop
agents to play popular games.

###  II-D Action Space

On each turn, the current player can provide an action for each one of their
units. An action consists of moving a unit a particular number of pixels in
both $x$ and $y$ directions and the movement normally takes several turns to
be completed. If in a turn the player does not indicate an action for a
particular unit, it continues the movement following the previous action
performed on this unit.

An action has the following format: “ _ID_ $\delta_{x}$ $\delta_{y}$” where:

  * •

_ID_ is the unique ID of the unit.

  * •

$\delta_{x}$ is the number of pixels we want to move the troop on the X axis.

  * •

$\delta_{y}$ is the number of pixels we want to move the troop on the Y axis.

Note that $\delta_{x}$ and $\delta_{y}$ are not the global coordinates to move
the unit to, but how many pixels the unit must move with respect to its
current coordinates. The coordinates are relative to the unit location to be
independent to the position of the agent (up or down) in the battlefield.

For instance, some actions that can be played are:

  * •

“1 100 50”: Unit with ID $1$ will move $100$ pixels to its right (east in the
display if the agent plays in the bottom part of the battlefield or west,
otherwise) and $50$ to the front of the battlefield (upwards or north in the
display if the agent plays in the bottom part of the battlefield or downwards
or south, otherwise).

  * •

“3 -100 -10”: Unit with ID $3$ will move $100$ pixels to its left and $10$
pixels backward.

  * •

“5 0 0”: Unit with ID $5$ will stop.

On each turn, a player can perform more than one action and they are indicated
as a string separated by semicolons. For instance, to perform the three
previously described actions in the same turn, the player would provide the
following multi-action string: “1 100 50; 3 -100 -10; 5 0 0”.

###  II-E State representation

The system provides information about the player and opponent’s units. First,
the game indicates the total number of units for each player’s army. Then, the
system provides the following information for each one of the player and
opponent’s units:

  * •

ID: Unique id of the unit.

  * •

Location: $x$, $y$ coordinates indicating the actual position of the unit on
the battlefield.

  * •

Direction: a number indicating where the unit is looking for. It can be
Northwest ($0$), North ($1$), Northeast ($2$), East ($3$), Southeast ($4$),
South ($5$), Southwest ($6$) and West ($7$).

  * •

Life: amount of health points (See Table I). The unit is dead when its life
reaches 0.

  * •

Type: unit type for swordsmen ($0$), spearmen ($1$), cavalry ($2$) and archers
($3$).

  * •

Moving: Indicates if the unit is moving ($1$) or not ($0$).

  * •

Target: $x$, $y$ coordinates indicating where the unit is going to stop, only
for friendly units (for opponent units, no target information is provided).

Therefore, the state has $1+9n+7n$ elements, where $n$ is the number of units
for each player’s army.

###  II-F Game complexity

The number of possible actions that can be played on each turn is huge in both
the draft and battle phases, due to the large battlefield size ($1920\times
1080$). It also depends on the league, $1$ to $3$, selected. One possibility
to handle its complexity is to artificially reduce the places where the units
can be moved. According to the size of the units, we suggest defining two
grids, the first one of $13\times 7$ ($1920/150\approx 13$, $1080/150\approx
7$) and the second one of $26\times 14$ ($1920/75\approx 26$, $1080/75\approx
14$). Note that the units can be always be moved to any place of the
battlefield. The use of the grid is just for reducing the complexity of the
game. It is suggested to be used in the first stages of the implementation of
the agent, or for beginners.

TABLE II: Number of possible actions in the draft phase depending of the battlefield size. Battlefield size |  $\\#$ actions
---|---
$1920\times 1080$ | $8.3E6$
$26\times 14$ | $1.5E3$
$13\times 7$ | $3.6E2$
TABLE III: Number of possible actions in the battle phase depending of the league and the battlefield size. Battlefield size |  $1^{st}$ league |  $2^{nd}$ league |  $3^{rd}$ league
---|---|---|---
$1920\times 1080$ | $8.3E6$ | $1.9E7$ | $6.2E7$
$26\times 14$ | $1.5E3$ | $3.3E3$ | $1.1E4$
$13\times 7$ | $3.6E2$ | $8.2E2$ | $2.7E3$
TABLE IV: Number of different army combinations that can be obtained in the draft phase depending of the league and the battlefield size. Battlefield size |  $1^{st}$ league |  $2^{nd}$ league |  $3^{rd}$ league
---|---|---|---
$1920\times 1080$ | $1$ | $7.5E7$ | $2.5E8$
$26\times 14$ | $1$ | $1.3E4$ | $4.4E4$
$13\times 7$ | $1$ | $3.3E3$ | $1.1E4$
TABLE V: Number of possible states in the battle phase. Battlefield size |  $1^{st}$ league |  $2^{nd}$ league |  $3^{rd}$ league
---|---|---|---
$1920\times 1080$ | $5.8E27$ | $3.0E28$ | $3.3E29$
$26\times 14$ | $3.2E16$ | $7.1E16$ | $2.4E17$
$13\times 7$ | $4.9E14$ | $2.5E15$ | $2.8E16$

Tables II and III show the number of actions in both phases with respect to
the size of the battlefield in the three sizes proposed: $1920\times 1080$,
$26\times 14$ and $13\times 7$. The number of actions in the draft phase
depends on the size of the battlefield ($H$, $W$) and the existing number of
unit types ($t=4$). This number can be calculated as:

$H\times W\times t$ (1)

For instance, when the smallest grid is used ($H=13$, $W=7$), the number of
actions in the draft phase is $13*7*4=3.6E2$.

The number of actions in the battle phase depends on the size of the
battlefield ($H$, $W$) and the number of units on each league ($n$). $n$ is 4,
9 and 30 in leagues 1, 2 and 3, respectively. The number of actions can be
calculated as:

$H\times W\times n$ (2)

For instance, when the smallest grid is used ($H=13$, $W=7$) and for the third
league ($n=30$), the number of actions in the battle phase is $13*7*30=2.7E3$.

Table IV shows the number of existing army combinations that can be obtained
on each league. This number depends on the size of the battlefield ($H$, $W$),
the existing number of unit types ($t=4$), and the number of units on each
league ($n$). In this case, the formula is:

$H\times W\times t\times n$ (3)

For instance, when the complete battlefield is used ($H=1920$, $W=1080$) and
for the second league ($n=9$), the number of actions in the battle phase is
$1920*1080*4*9=7.5E7$. Note that in the first league there is just one
possible combination since there is not a draft phase and the initial
configuration of the army is always the same.

Table V shows the number of states for the three leagues and proposed
battlefield sizes. This number depends on the size of the battlefield ($H$,
$W$), the number of different directions ($d=8$), the number of health points
($l$) (for simplicity, we assume in these calculations that all units have the
same number of health points $l=100$, see Table I), the existing number of
unit types ($t=4$), if the unit is moving or not ($m=2$), and the number of
units on each league ($n$). The number of states can be calculated as:

$(H\times W\times d\times l\times t\times m\times H\times W)\times
n\times(H\times W\times d\times l\times t\times m)\times n$ (4)

Note that the second term, corresponding to the opponent units, do not have a
second element $H\times W$ since the final target of the opponent units is
unknown. For instance, when the complete battlefield is used ($H=1920$,
$W=1080$) and for the first league ($n=4$), the number of actions in the
battle phase is $(1920\times 1080\times 8\times 100\times 4\times 2\times
1920\times 1080)\times 4\times(1920\times 1080\times 8\times 100\times 4\times
2)\times 4=5.8E27$.

###  II-G Game Art

One of the more interesting features of CodinGame is that it is possible to
replay the game. Therefore, it is possible to study how some actions have
affected the game in a particular moment of the game.

A set of assets have been designed for a better representation of the game.
The units are based on the middle age and have a cartoon style (see Figure 1).

The game also includes animations for each state in which each unit can be
found. The states are: idle, running, attacking and dead. Furthermore, there
is an animation for when a unit is under arrows attack. As an example, Figure
5 shows the different sprites of some of the animations used in the game.

Figure 5: Some animations used in the game.

##  III Baseline Agents

Several AI agents have been developed as baselines for the proposed game. They
are briefly explained as follows:

####  III-1 StayStatic ($SS$)

All units stand still during the battle. A predefined army is always selected
in the draft. The knights are in the flanks, spearmen and swordsmen in the
middle and archers behind. The units never move but they can fight when
colliding with an opponent. Besides, the archers can shoot arrows to opponent
troops into the attacking range.

####  III-2 AlwaysForward ($AF$)

All units always move forward. The predefined army is the same as in $SS$.

####  III-3 Random ($RND$)

All units select random destinations. The predefined army is the same as in
$SS$.

####  III-4 Heuristic ($\Lambda$)

It uses human knowledge in both phases. In the draft, the agent tries to pick
the unit to have an advantage against the opponent. For instance, if the
opponent selected in the previous turn a Knight, it will pick a Spearman. The
agent has some rules to avoid to choose too many units of the same type. The
agent selects the position in front of the troop that can be defeated by the
selected one.

For the battle, for each unit, a heuristic function $\lambda$ is used to
estimate a value indicating how good is to attack each enemy unit. The enemy
unit with the biggest value is the one selected as the target. The heuristic
function $\lambda$ has been designed as the average of $5$ factors $\phi_{i}$
($\phi_{i}\in[0,\ldots,1],\forall{i}$ and $i\in[1,\ldots,5]$):

  * •

$\phi_{1}$ provides higher values if the player’s unit belongs to a type with
advantage with respect to the opponent one, taking into account the rock-
paper-scissor combat system. It can be $1.0$, $0.5$ or $0.0$ when the opponent
unit type is worse, the same or better, respectively.

  * •

$\phi_{2}$ is $1.0$ if the player’s unit avoids getting into the opponent
archers attacking range; $0.0$ otherwise.

  * •

$\phi_{3}$ benefits having more health points than the opponent unit. It can
be $1.0$, $0.5$ or $0.0$ when the opponent unit has less, the same or more
health points, respectively.

  * •

$\phi_{4}$ is $1.0$ in case of a flank attack, i.e. the attacking direction is
not frontal, and $0.0$ otherwise.

  * •

$\phi_{5}$ will be higher the closer the player’s unit is to the enemy’s.

In the third league, a new factor $\phi_{6}$ is added with a value of $1.0$ if
the opponent unit is a general and $0.0$ otherwise.

####  III-5 Online Evolutionary Planning (OEP)

This algorithm, proposed by Justesen et al. [12], evolves a vector of $N$
moves to be executed by agents in multi-action games. In the original
algorithm, an initial population of vectors (individuals) is generated at
random to then be evolved by the algorithm, executing actions consecutively in
the forward model. The state reached when all actions are executed is
evaluated to obtain a fitness for the individual.

The OEP agent implemented for TotalBotWar uses the method described for
Heuristic agent for the draft phase and for seeding the initial population in
the battle. Each individual contains $N$ genes, where each gene corresponds to
a unit owned by the agent and their values are the IDs of the opponent’s unit
to attack, i.e. the number of genes $N$ is the number of units $n$ of the army
in each league. For instance, in the first league ($n=4$), a genome
$[2,1,0,1]$ indicates that the first unit from the OEP agent will attack the
opponent unit with ID $2$, the second unit will attack unit with ID $1$, and
so on. A mutation rate $\rho=0.1$ is applied to each gene to change the target
to attack. The resultant states are evaluated using the same $\phi_{i}$
factors than in $\Lambda$, but adding a new one that rewards individuals who
target the same opponent unit more than once.

##  IV Experiments

Several games have been played using the agents developed and described in
Section III. Table VI shows the win-rate of the agents playing as the first
player. In all cases, results are reported using the third league, the
complete battlefield size (i.e. no grid is used) and $100$ games. As expected,
$\Lambda$ and OEP agents overcome the simplest baselines. Surprisingly there
is a tie between $\Lambda$ and OEP agents. This is likely due to the OEP agent
not having enough time (with the time limit constrain of CodingGame platform)
to evolve stronger action selections, being unable to find better
recommendations than the ones initially provided by the $\Lambda$ agent.

We have also tested both algorithms (OEP vs $\Lambda$) in leagues 2 and 1,
obtaining a win-rate for the OEP of $0.65$ and $0.90$, respectively. In these
cases, the game is less complex than in the case of the league 3. Therefore,
the OEP agent performs more iterations in the allowed budget time and it is
able to find better move recommendations.

TABLE VI: Win-rate of agents tested in League 3. | SS | AF | RND | $\Lambda$ | OEP
---|---|---|---|---|---
SS |  | 0.0 | 0.2 | 0.0 | 0.0
AF | 1.0 |  | 0.5 | 0.0 | 0.05
RND | 0.8 | 0.5 |  | 0.2 | 0.1
$\Lambda$ | 1.0 | 1.0 | 0.8 |  | 0.5
OEP | 1.0 | 0.95 | 0.90 | 0.5 |

##  V Conclusions

This paper presents a new game for game AI: TotalBotWar. The game introduces
interesting features and challenges for AI, as it presents a pseudo real-time
decision making problem in a large and continue state and action space. It
also provides an interesting challenge for drafting policies, army composition
and tactical planning. The paper suggests different possibilities for
discretizing the state space, and also benchmarks a state-of-the-art
algorithm, Online Evolutionary Planning (OEP), which shows good results in the
simpler scenarios but can’t outperform domain-knowledge rule-based agents in
the complex ones due to the time limitation constrain in CodingGame platform.

Future work can span in multiple directions. Regarding the game, more complex
units, rules and terrain features could be added. In terms of agents,
sophisticated agents and techniques can be object of research to outperform
the proposed baselines. Finally, we plan to propose this benchmark as a new
competition in the future for game playing AI research.

## References

  * [1] D. Silver, T. Hubert, J. Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran, T. Graepel, T. Lillicrap, K. Simonyan, and D. Hassabis, “A general reinforcement learning algorithm that masters chess, shogi, and go through self-play,” _Science_ , vol. 362, pp. 1140–1144, 12 2018.
  * [2] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, S. Petersen, C. Beattie, A. Sadik, I. Antonoglou, H. King, D. Kumaran, D. Wierstra, S. Legg, and D. Hassabis, “Human-level control through deep reinforcement learning,” _Nature_ , vol. 518, no. 7540, pp. 529–533, 2015.
  * [3] N. Justesen, P. Bontrager, J. Togelius, and S. Risi, “Deep learning for video game playing,” _IEEE Transactions on Games_ , vol. 12, no. 1, pp. 1–20, 2017\.
  * [4] N. Justesen, L. M. Uth, C. Jakobsen, P. D. Moore, J. Togelius, and S. Risi, “Blood bowl: A new board game challenge and competition for ai,” in _2019 IEEE Conference on Games (CoG)_ , 2019.
  * [5] J. Kowalski and R. Miernik, “Legends of code and magic,” https://jakubkowalski.tech/Projects/LOCM/, 2019, [Online; accessed 8-April-2020].
  * [6] S. Ontañón, N. A. Barriga, C. R. Silva, R. O. Moraes, and L. H. S. Lelis, “The first microrts artificial intelligence competition.” _AI Magazine_ , vol. 39, no. 1, pp. 75–83, 2018.
  * [7] R. Ishii, S. Ito, R. Thawonmas, and T. Harada, “A fighting game ai using highlight cues for generation of entertaining gameplay,” in _1st IEEE Conference on Games (CoG’19)_ , 2019.
  * [8] J. Walton-Rivers, P. R. Williams, and R. Bartle, “The 2018 hanabi competition,” in _2019 IEEE Conference on Games (CoG)_. IEEE, 2019, pp. 1–8.
  * [9] I. Bravi, D. Perez-Liebana, S. M. Lucas, and J. Liu, “Rinascimento: Optimising statistical forward planning agents for playing splendor,” in _2019 IEEE Conference on Games (CoG)_. IEEE, 2019, pp. 1–8.
  * [10] M. Čertický, D. Churchill, K. Kim, M. Čertický, and R. Kelly, “Starcraft ai competitions, bots, and tournament manager software,” _IEEE Transactions on Games_ , vol. 11, no. 3, pp. 227–237, 2019.
  * [11] D. Perez-Liebana, S. M. Lucas, R. D. Gaina, J. Togelius, A. Khalifa, and J. Liu, _General Video Game Artificial Intelligence_. Morgan & Claypool Publishers, 2019, https://gaigresearch.github.io/gvgaibook/.
  * [12] N. Justesen, T. Mahlmann, S. Risi, and J. Togelius, “Playing multi-action adversarial games: Online evolutionary planning versus tree search,” _IEEE Transactions on Games_ , vol. 10, no. 3, pp. 281–291, 2018.


# Conditional Graph Attention Networks for Distilling
and Refining Knowledge Graphs in Recommendation

Ke Tu  Ant Group<EMAIL_ADDRESS>,  Peng Cui  Tsinghua University
<EMAIL_ADDRESS>,  Daixin Wang  Ant Group<EMAIL_ADDRESS>,
Zhiqiang Zhang  Ant Group<EMAIL_ADDRESS>,  Jun Zhou  Ant Group
<EMAIL_ADDRESS>,  Yuan Qi  Ant Group<EMAIL_ADDRESS>and  Wenwu
Zhu  Tsinghua University<EMAIL_ADDRESS>
(2021)

###### Abstract.

Knowledge graph is generally incorporated into recommender systems to improve
overall performance. Due to the generalization and scale of the knowledge
graph, most knowledge relationships are not helpful for a target user-item
prediction. To exploit the knowledge graph to capture target-specific
knowledge relationships in recommender systems, we need to distill the
knowledge graph to reserve the useful information and refine the knowledge to
capture the users’ preferences. To address the issues, we propose _Knowledge-
aware Conditional Attention Networks_ (KCAN), which is an end-to-end model to
incorporate knowledge graph into a recommender system. Specifically, we use a
knowledge-aware attention propagation manner to obtain the node representation
first, which captures the global semantic similarity on the user-item network
and the knowledge graph. Then given a target, i.e., a user-item pair, we
automatically distill the knowledge graph into the target-specific subgraph
based on the knowledge-aware attention. Afterward, by applying a conditional
attention aggregation on the subgraph, we refine the knowledge graph to obtain
target-specific node representations. Therefore, we can gain both
representability and personalization to achieve overall performance.
Experimental results on real-world datasets demonstrate the effectiveness of
our framework over the state-of-the-art algorithms.

Network Representation Learning; Graph Convolutional Network; Knowledge Graph;
Conditional Attention

††journalyear: 2021††copyright: acmcopyright††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††doi: 10.1145/3459637.3482331††ccs: Information
systems Recommender systems

##  1\. Introduction

Nowadays, recommender systems (Wang et al., 2019c; He and Chua, 2017; Gao et
al., 2020) are widely used in various Internet applications, for example,
search engines (Baeza-Yates et al., 2004), video websites (Davidson et al.,
2010), and E-commerce (Schafer et al., 2001). The recommender system aims to
find proper items for target users to meet their personalized interests based
on the user-item historical network. However, the common critical problem of
recommender systems is data sparsity, i.e., the user behaviors or user-item
interactions are very limited comparing with the volume of items. Besides, it
is hard to recommend items for a new arrival user (Schein et al., 2002). To
address the limitations, the researchers have proposed to incorporate side
information into the recommender systems, such as attributes (Huang et al.,
2017), contexts (Kim et al., 2016), images (Niu et al., 2018).

Figure 1. Illustration of Knowledge-aware recommender system.

Among the various types of side information, knowledge graphs (Wang et al.,
2017; Dettmers et al., 2018) usually contain more abundant information about
the characteristics and connections of nodes. Different from the normal
network, the knowledge graph is composed of a set of triplets, i.e.,
$\textless$head entity, relations, tail entity$\textgreater$. It can describe
not only node attributes, such as $\textless\rm{Movie_{1}}$, $\rm{Genre}$,
$\rm{Actioner}$ $\textgreater$ in Figure 1, but also node relationships, such
as $\textless\rm{Actor_{1}}$, $\rm{Friend}$, $\rm{Director_{1}}\textgreater$
in Figure 1. Recently, numerous massive knowledge graphs, such as Wordnet
(Miller, 1995), Freebase (Bollacker et al., 2008) and DBpedia (Auer et al.,
2007), have been published. These knowledge graphs which describe the facts
and common sense can be partly aligned to the nodes of most network
applications and be regarded as their side information. They can benefit the
recommender systems by introducing relatedness among entities, enriching the
entity information, and producing the explainability. However, due to the
generalization and scale of the knowledge graph, most knowledge relationships
are not helpful for a user-item prediction. To exploit knowledge graph to
capture target-specific knowledge relationships in recommender systems (Qin et
al., 2020), we need to address the following new requirements:

  1. (1)

Knowledge Graph Distillation: Knowledge graphs are massive and comprehensive
for containing more information. For a specific item recommendation, most
knowledge relationships maybe not helpful. Thus learning semantic
relationships on the full knowledge graph for a given task is very time-
consuming and noisy. Distilling the knowledge graph which gives a small sub-
structure related to the target task from the full massive knowledge graph is
necessary. It is worth noting that the knowledge graph distillation describes
the process of transforming the full knowledge graph into a small concentrated
one to capture users’ preference accurately, rather than mimicking a pre-
trained, larger teacher model by a small student model like knowledge
distillation (Hinton et al., 2015).

  2. (2)

Knowledge Graph Refinement: Personalized recommendation mines user’s interests
from the past purchasing behaviors. In personalized recommendation with
knowledge graph, attention mechanisms are usually used to measure user’s
preference (Wang et al., 2019e, a). However, they give the same weights of
knowledge edges for different target users by edge attentions. For example, in
Figure 1, we aim to recommend for targets users $\rm{User_{1}}$ and
$\rm{User_{2}}$. The weights of edge
$\textless\rm{Movie_{2}},\rm{genre},\rm{Comedy}\textgreater$ are only based on
the nodes $\rm{Movie_{2}}$ and $\rm{Comedy}$, and are independent of
$\rm{User_{1}}$ and $\rm{User_{2}}$. But $\rm{User_{1}}$ and $\rm{User_{2}}$
may have different preferences on the genre of the movie. That is to say, the
weights of edge ¡Movie2,genre,Comedy¿ may be different for $\rm{User_{1}}$ and
$\rm{User_{2}}$. Thus, for a given target, we should refine the knowledge
graph to give different weights for all the knowledge relationships instead of
its neighbors.

Therefore, we believe that a good knowledge-aware network learning method
should distill and refine the knowledge graphs. Early knowledge graph-aware
algorithms are embedding-based models (Wang et al., 2019a; Cao et al., 2019).
They learn entity and relation representations first by knowledge graph
embedding algorithms (Wang et al., 2014; Dai et al., 2020) and then
incorporate the latent embeddings into the recommender system. The direct way
to exploit the knowledge graph in the embedding space fails to solve the
distillation and refinement issues and thus harm the performance. The path-
based methods (Hu et al., 2018; Wang et al., 2019c; Xian et al., 2019) explore
different meta-paths from knowledge graphs to build relationships of two
objects, such as $\rm{User}_{1}\stackrel{{\scriptstyle
watch}}{{\longrightarrow}}\rm{Movie}_{1}\stackrel{{\scriptstyle
genre}}{{\longrightarrow}}Actioner\stackrel{{\scriptstyle
include}}{{\longrightarrow}}\rm{Movie}_{5}$. They distill the knowledge graphs
into multiple meta-paths. However, these methods heavily depend on the hand-
crafted design of the meta-path. Besides, the multiple paths can not handle
the diversity of the users’ preference on the knowledge relationships.
Recently, some graph convolutional network-based methods (Wang et al., 2019a,
e) are proposed to propagate information on knowledge graphs. They usually use
an attention mechanism (Vaswani et al., 2017) to produce weights of different
neighbors for knowledge graph refinement. However, the attentions are only
based on the two nodes in the same edges and are independent with the target
nodes.

To overcome the Knowledge Graph Distillation and the Knowledge Graph
Refinement issue, we propose a novel model named _Knowledge-aware Conditional
Attention Networks_ (KCAN). First, we propose a knowledge-aware graph
convolutional network to propagate embedding on the knowledge graph by
knowledge-aware attention to capture the global similarity of entities like
KGAT (Wang et al., 2019a). After that, a subgraph sampling strategy is
designed to sample target-specific subgraphs based on the attention weights to
distill the knowledge graph. Also, the proposed Local Conditional Subgraph
Attention Network (LCSAN) propagates personalized information on the sampled
subgraph based on local conditional attention for refining the knowledge
graph. In conclusion, the proposed KCAN can effectively distill and refine the
knowledge graph at the same time.

It is worthwhile to highlight the following contributions of this paper:

  * •

We highlight the importance of distilling and refining knowledge graphs in
recommender systems and propose to use a conditional attention mechanism on
target-specific subgraphs to capture user preference.

  * •

We propose a novel framework named _Knowledge-aware Conditional Attention
Networks_ (KCAN) to incorporate the knowledge graph into the recommendation.
In particular, the _Knowledge-aware Graph Convolutional Network_ (KAGCN) layer
and target-specific subgraph sampling are designed with the Knowledge Graph
Distillation issue in mind. Moreover, the Knowledge Graph Refinement issue is
addressed by the _Local Conditional Subgraph Attention Network_ (LCSAN) layer.

  * •

Extensive experiments on real-world scenarios are conducted to demonstrate the
effectiveness of our framework over several state-of-the-art methods.

The rest of the paper is structured as follows. We first give a brief review
of the related works in section 2. Then we formally define the solved problems
and introduce the details of our proposed model in section 3. In section 4, we
report the experimental results. Finally, we give a conclusion in section 5.

Figure 2. The framework of the proposed KGAN. The framework is composed of
four modules: Knowledge Graph Embedding layer, Knowledge Graph Distillation
module (KAGCN layer and Target-sepcific Sampling), Knowledge Graph Refinement
module (LCSAN layer) and Multi-layer Perceptron (MLP) two-tower prediction
layer.

##  2\. Related Work

###  2.1. Knowledge Graph Embedding

Knowledge Graph Embedding (KGE) (Wang et al., 2017) aims to learn latent
representations for all components of the knowledge graph including entities
and relations. Then the low-rank embeddings which preserve the inherent
structure and knowledge graph can be used in the downstream tasks such as
knowledge graph completion and recommendation. The KGE methods can be roughly
divided into two classes: translation distance based models (Bordes et al.,
2013; Lin et al., 2015) and semantic matching based models (Nickel et al.,
2011; Yang et al., 2014; Trouillon et al., 2016). The translation distance
based models exploit distance-based scoring functions. The existing
relationships in the knowledge graph will have higher scores. The scoring
functions usually measure the distance of two entities under the space of the
relation. For example, TransE (Bordes et al., 2013) assumes
$head+relation=tail$ and use $||head+relation-tail||$ as scoring function on
the $(head,relation,tail)$ relationships. TransR (Lin et al., 2015) first
projects the entity representations $head$ and $tail$ into the space specific
to relation $r$ and measures the distance between entities $head$ and $tail$
under that space. The semantic matching models exploit similarity scoring
functions. For example, RESCAL (Nickel et al., 2011) uses a bilinear function
to learn the similarity of entities. For the recommendation task, the main
issue is how to introduce the representations of entities and relations into
the recommendation system for enriching the item information.

###  2.2. Graph Convolutional Network

The graph convolutional network (GCN) (Kipf and Welling, 2017; Zhang et al.,
2020) has been proposed to process network data in an end-to-end manner.
Earlier works define the graph convolutional operations in the spectral
domain. Bruna et al. (Defferrard et al., 2016) are inspired by the graph
signal process (Shuman et al., 2013) and define the convolution in the Fourier
spectral domain. Kipf et al. (Kipf and Welling, 2017) propose to use a first-
order approximation to deal with the complexity issue. Recently, lots of non-
spectral GCN, which directly define convolution on the graph, have been
proposed in the spatial domain. GraphSage (Hamilton et al., 2017) samples a
fixed-size neighborhood of each node and then aggregates over it. GAT
(Veličković et al., 2018) introduces a self-attention strategy to specify
different weights to different nodes in a neighborhood. However, these works
are designed for homogeneous graphs instead of knowledge graphs. Our method is
conceptually inspired by GCN. Similarly, Schlichtkrull et al. (Schlichtkrull
et al., 2018) and Wang et al. (Wang et al., 2019e) also propose to apply GCN
and GAT into the knowledge graph. They first applies knowledge graph embedding
(Wang et al., 2017) methods to obtain representation for entities. Then they
propagate the representation over the user-item bipartite graph and knowledge
graph to collect the high-order information. Besides, KGCN-LS (Wang et al.,
2019d) extends the previous knowledge based GCN method and adds a label
smoothness mechanism to propagates the user interaction labels on the
knowledge graph. However, the major difference between our work and these
methods is that our model consider the knowledge graph distillation and the
knowledge graph refinement whiling learning representations.

###  2.3. Knowledge-aware Recommendation

In general, existing knowledge graph-aware algorithms (Qin et al., 2020; Dai
et al., 2020) can be roughly categorized into two types:

(1) Embedding-based methods (Zhang et al., 2016; Xin et al., 2019). These
methods learn entity and relation representations first by knowledge graph
embedding algorithms and then incorporate the latent embeddings into the
original network. CKE (Zhang et al., 2016) combines collaborative filtering
with knowledge graph embedding. Cao et al. (Cao et al., 2019) use the
knowledge graph to augment the modeling of user-item interaction while
completing the missing facts in the knowledge graph based on the enhanced
user-item modeling at the same time. Nevertheless, these methods only use
knowledge graph embedding as regularization and lose the rich topology
structure of the knowledge graph. Additionally, Wang et al. (Wang et al.,
2019a) use graph convolutional network to explicitly model the high-order
relations by recursive propagation in the knowledge graph. But all these
methods usually have no constraint between the target users and entities and
thus hurt the modeling of user preferences.

(2) Path-based methods. These methods (Wang et al., 2019c, b; Hu et al., 2018)
regard the knowledge graph as a heterogeneous information network (Yu et al.,
2014) and explore different paths from knowledge graphs and measure node
relationships by meta-path-based similarity (Sun et al., 2011). Besides, some
methods leverage the meta-path based random walk to learn better entities
representation, such as HIN2Vec (Fu et al., 2017) and metapath2vec (Dong et
al., 2017). Defining effective meta-paths usually requires domain knowledge,
and it can not generalize to a new dataset. Recently, some works (Xian et al.,
2019; Song et al., 2019) propose to apply reinforcement learning to choose
meta-paths while training automatically. However, characterizing the user-item
similarity by separate paths may lead to information loss. Our works propose
to use target-specific subgraphs to distill the knowledge graph. Xiao et al.
(Sha et al., 2019) also use subgraphs to distill the knowledge graph. But it
pre-computes all user-item subgraphs by the knowledge graph and just learns on
these local subgraphs. In such a way, the semantic similarity between entities
on the whole knowledge graph is missing. Our model can not only preserve the
global semantic similarity but also dynamically generates target-specific
subgraphs to distill and refine knowledge graph for inferring local user
preference accurately.

##  3\. The Proposed Framework

In this section, we will introduce the proposed _Knowledge-aware Conditional
Attention Networks_ (KCAN). The framework is shown in Figure 2. The model is
composed of four modules: (1) Knowledge Graph Embedding layer. It learns
representations for each entity and relation by a traditional knowledge graph
embedding method TransH. (2) Knowledge Graph Distillation, which propagates
embedding with a knowledge-aware attention mechanism and uses a target-
sampling strategy to distill the knowledge graph. (3) Local Conditional
Subgraph Attention Network (LCSAN), which propagates personalized information
on the subgraph based on local conditional attention to refine the knowledge
graph. (4) Multi-layer Perceptron (MLP) two-tower prediction layer, which
combines the embeddings from the above two layers and predicts the final
results with a non-linear layer.

###  3.1. Notations and Definitions

Let $G=(V,E)$ denotes a network, where $V$ is the set of nodes and $E\subseteq
V\times V$ is the set of edges. For a node $v\in V$,
$\mathcal{N}(v)=\\{u|(v,u)\in E\\}$ is the set of its neighbors. In our
setting, we have an external knowledge graph
$\mathcal{G}=\\{(h,r,t)|h\in\mathcal{E},r\in\mathcal{R},t\in\mathcal{E}\\}$,
where $h$, $r$ and $t$ denotes the head entity, relation and tail entity of a
knowledge graph triple. $\mathcal{E}$ and $\mathcal{R}$ are the set of
entities and relations of knowledge graph $\mathcal{G}$. Actually, our model
can be used in any graph tasks with a side knowledge graph. The target sets
$\mathcal{T}$ rely on the goal of the graph task. For example, in node
classification, the target set is a single node $\mathcal{T}=\\{v\\}$. For
recommendation task, given a bipartite user-item graph, the goal is to predict
the existence or similarity $y_{uv}$ of a targeted user-item pair
$\mathcal{T}=\\{u,v\\}$. For drug reactions prediction task, the target set is
all the drugs which leads reaction together
$\mathcal{T}=\\{d_{1},..,d_{n}\\}$. In our paper, we only discuss
recommendation task with bipartite user-item graph $G$ and an external
knowledge graph $\mathcal{G}$. A node in network $G$ may also be an entity in
knowledge graph $\mathcal{G}$. In general, we use entity to refer all nodes in
both $G$ and $\mathcal{G}$. For an entity $v$, the neighborhood of $v$ in
knowledge graph is denoted as
$\mathcal{N}(v)=\\{(r,v^{\prime})|(v,r,v^{\prime})\in\mathcal{G}\\}$ and we
mark the K-hop neighborhood of entity $v$ as $S_{K}(v)$. We mark the embedding
of entity $h$ in $k$-th layer as $\mathbf{e}_{h}^{(k)}\in\mathbb{R}^{F_{k}}$
with $k=0,1,2,...,K$. For simplify, we mark $\mathbf{e}_{h}^{(0)}$ as
$\mathbf{e}_{h}$.

###  3.2. Knowledge Graph Distillation

To distill the whole knowledge graph, we must recognize the importance of the
knowledge relationships and eliminate the useless relationships. For this
purpose, we first vectorize the entities by knowledge graph embedding.

####  3.2.1. Knowledge Graph Embedding

Knowledge graph embedding (Wang et al., 2014; Ji et al., 2015; Dai et al.,
2020) is an effective way to learn entity and relation representations while
preserving the topology structure. Since we regard the click relation in the
recommendation as a type of knowledge relationships and a user may click many
items, so there are a lot of one-to-many mappings in the knowledge graph. Here
we use TransH (Wang et al., 2014) which can solve the one-to-many and many-to-
one issues. For a given triple $(h,r,t)$, its score or distance is defined as
follows:

(1)
$f_{r}(h,t)=\left\|\mathbf{e}_{h\perp}+\mathbf{d}_{r}-\mathbf{e}_{t\perp}\right\|_{1}^{2},$

where
$\mathbf{e}_{h\perp}=\mathbf{e}_{h}-\mathbf{w}_{r}^{\top}\mathbf{e}_{h}\mathbf{w}_{r}$
and
$\mathbf{e}_{t\perp}=\mathbf{e}_{t}-\mathbf{w}_{r}^{\top}\mathbf{e}_{t}\mathbf{w}_{r}$
are the projections of entities embedding $\mathbf{e}_{h}$ and
$\mathbf{e}_{t}$ on the relation-specific hyperplane $\mathbf{w}_{r}$, and
$\mathbf{d}_{r}$ is the relation-specific translation vector; $\|\cdot\|_{1}$
is the $L1$-norm. The lower score of $f_{r}(h,t)$ indicates the triplet is
more likely to be true and vice versa. By projecting to the relation-specific
hyperplane, TransH enables different roles of an entity in different triplets.

The loss of knowledge graph embedding is Bayesian personalized ranking loss
(Rendle et al., 2009), which aims to maximize the margin between the positive
samples and the negative samples:

(2)
$\mathcal{L}_{kg}=\sum_{(h,r,t)\in\mathcal{E}}\sum_{(h,r,t^{\prime})\notin\mathcal{E}}{-\ln\
\sigma(f_{r}(h,t^{\prime})-f_{r}(h,t))},$

where $\sigma$ is the sigmoid function, $t^{\prime}$ is uniformly sampled by
replacing $t$ with another entity randomly. To increase the representation
ability, we also train the model on both the knowledge graph $\mathcal{G}$ and
the user-item network $G$ with this loss function. For this purpose, we treat
all edges in network $G$ with the same type $r_{G}$. Then the network $G$ can
be also seen as a knowledge graph with one and the same relation type.

####  3.2.2. Knowledge-Aware Graph Covolutional Network

However, the knowledge graph embedding only focuses on the separate knowledge
triples, thus it fails to capture the high-order similarity between entities.
Inspired by KGAT (Wang et al., 2019a) and KGNN (Lin et al., 2020), we present
to capture the high-order similarity of entities by aggregating the knowledge
embedding with graph convolutional network. To distinguish the influence of
different types of relations in the knowledge graph, we propose to use a
knowledge-aware attention mechanism over the propagation:

(3)
$\mathbf{e}_{\mathcal{N}(v)}=\sum_{(r,t)\in\mathcal{N}(v)}\pi_{r}(v,t)\mathbf{e}_{t},$

where $\pi_{r}(v,t)$ is relation-specific attention coefficient. The attention
measures the importance of the entity $v$ to $t$ under the relation
$r$-specific space. When the entity $t$ is closer to entity $v$ under the
relation $r$-specific space, the more information should be propagated.
Motivated by this, we define knowledge-aware attention as follows:

(4) $\hat{\pi}_{r}(v,t)={\rm
softmax}(\cos(\mathbf{e}_{v\perp}+\mathbf{d}_{r},\mathbf{e}_{t\perp})),$

where
$\cos(\mathbf{x},\mathbf{y})=\frac{\mathbf{x}^{\mathrm{T}}\mathbf{y}}{\|\mathbf{x}\|_{2}\|\mathbf{y}\|_{2}}$
is the cosine similarity. In this way, it will propagate more information for
closer entities.

Finally, we combine the entity representation $\mathbf{e}_{v}$ and the
neighborhood representation $e_{\mathcal{N}(v)}$ and update the entities
representation as $\mathbf{e}_{v}^{(1)}$. For simplicity, we concatenate two
representations and add a nonlinear transformation like GraphSAGE aggregator
(Hamilton et al., 2017):

(5) $\displaystyle\mathbf{e}_{v}^{(1)}$ $\displaystyle={\rm
AGG}(\mathbf{e}_{v},\mathbf{e}_{\mathcal{N}}(v))$ (6) $\displaystyle={\rm
LeakyReLU}(\mathbf{W}^{(1)}(\mathbf{e}_{v}||\mathbf{e}_{\mathcal{N}}(v))+\mathbf{b}^{(1)}),$

where $||$ is the concatenation operation, and LeakyReLU is the activation
function. $\mathbf{W}^{(1)},\mathbf{b}^{(1)}$ are the trainable weights. By
this knowledge-aware propagation mechanism, we can preserve the global
similarity between entities after several iterations.

####  3.2.3. Target-specific Sampling

For a given user-item target $(u,v)$, the attentions of KAGCN rely on the
knowledge edges and do not concern with the targets. To capture the local
influence of the targets, we exploit subgraphs instead of the whole enormous
knowledge graph. Compared to the meta-path or random-walk based model which
uses path to capture the locality, the subgraph can contain diversity. A
target set is marked as $\mathcal{T}=\\{v_{1},...,v_{k}\\}$ which $k=2$ and
$\mathcal{T}$ is a user-item pair. Due to the locality of the users’
preference, we set the receptive field of each node $v$ as their K-hop
neighborhood $S_{K}(v)$. In a real-world knowledge graph, the number of
neighbors may vary significantly over all entities, and some entities may have
a huge number of neighbors. To distill the knowledge graph and reduce the
training time, we sample a fixed-size set of neighbors for each entity instead
of the full neighborhood. We set the sampled size as $M$. The traditional way
is to sample neighbors uniformly like GraphSAGE (Hamilton et al., 2017).
However, the knowledge graph is usually noisy and full of target-independent
information. Additionally, considering that we have obtained the global
attention $\pi_{r}(v,t)$, which measures the similarity of entities, we sample
neighbors with their attention score $\pi_{r}(v,t)$ as the sampled
probability. After getting the sampled $K$-hop neighborhood as
$\hat{S}_{K}(v)$ for each node $v$, we can obtain the receptive field of the
target set by merging them:

(7) $\hat{S}_{K}(\mathcal{T})=\cup_{v\in\mathcal{T}}\hat{S}_{K}(v).$

###  3.3. Knowledge Graph Refinement

The knowledge graph distillation module distills the knowledge graph to a
target-specific subgraph as the receptive field of the target set. In this
part, we re-weight the knowledge to refine the knowledge graph. For that, we
propagate entities’ information on the distilled target-specific subgraph. To
capture the preference of the target to the knowledge relationships, we
propose to use a conditional attention mechanism over propagation to refine
the subgraph as follows:

(8)
$\mathbf{e}^{(1)}_{\mathcal{N}^{\mathcal{T}}(v)}=\sum_{(r,t)\in\mathcal{N}^{\mathcal{T}}(v)}\alpha(v,r,t|\mathcal{T})\mathbf{e}^{(1)}_{t},$

where $\alpha(v,r,t|\mathcal{T})$ is the conditional attention which relies on
target $\mathcal{T}$, and $\mathcal{N}^{\mathcal{T}}(v)$ is the neighbors of
the entity $v$ in the receptive field of the target set
$\hat{S}_{k}(\mathcal{T})$.

To better refine the subgraph based on the target, the conditional attention
should contain two aspects: (1) the importance $\alpha_{1}(v,r,t)$ of the
knowledge relationship $(v,r,t)$. This part is independent of the target, and
it measures the importance of knowledge relationship itself upon the task. If
the knowledge relationship is a noise edge in the task, we should reduce its
influence. In the KAGCN part of the section 3.2.2, we had measured it by the
knowledge-aware attention $\hat{\pi}_{r}(v,t)$. So we can just set
$\alpha_{1}=\hat{\pi}_{r}(v,t)$ for simplicity. (2) the importance
$\alpha_{2}(t|\mathcal{T})$ of the entity to the target set. This term
measures the local preference of the target to the tail entity. The entities
which are more similar to the target should be more important for the target.
To make the target set and the entity comparable, we calculate the
representation of the target set as the concatenation of all contained
entities, i.e.,
$\mathbf{e}_{\mathcal{T}}=\|_{v\in\mathcal{T}}\mathbf{e}^{(1)}_{v}$.
Subsequently, we can measure the importance of the entity to the target set by
their representations:

(9)
$\alpha_{2}(t|\mathcal{T})=\mathbf{a}^{\mathrm{T}}[\mathbf{W}^{(1)}_{t}\mathbf{e}_{\mathcal{T}}\|\mathbf{W}^{(1)}_{e}\mathbf{e}^{(1)}_{t}],$

where $\mathbf{a}$ is a weight vector. $\mathbf{W}^{(1)}_{t}$ and
$\mathbf{W}^{(1)}_{e}$ are the linear transformation matrices of targets and
entities respectively.

Combining the two importance scores, we get the conditional attention:

(10) $\alpha(v,r,t|\mathcal{T})={\rm softmax}({\rm
LeakyReLU}(\alpha_{1}(v,r,t)*\alpha_{2}(t|\mathcal{T}))).$

The larger attention indicates the more important of the knowledge related to
the target. By the conditional attention, the local knowledge graph is refined
into a weighted graph varying with the target.

Finally, similar to KAGCN, the target-specific entities representations can be
obtained as follows:

(11) $\displaystyle\mathbf{e}_{v|\mathcal{T}}^{(2)}$ $\displaystyle={\rm
AGG}(\mathbf{e}_{v}^{(1)},\mathbf{e}^{(1)}_{\mathcal{N}^{\mathcal{T}}(v)})$
(12) $\displaystyle={\rm
LeakyReLU}(\mathbf{W}^{(2)}(\mathbf{e}_{v}^{(1)}\|\mathbf{e}^{(1)}_{\mathcal{N}^{\mathcal{T}}(v)})+\mathbf{b}^{(2)}).$

Furthermore, in order to capture high-order preference, we further stack more
LCSAN layers. Especially, since the subgraphs are composed of $K$-hop composed
neighborhoods, we stack the LCSAN with $K$ times to make sure that the
information of each node can be propagated over all the subgraph. In general,
the $i$-th LAGCN is as follows:

(13) $\mathbf{e}_{v|\mathcal{T}}^{(i+1)}={\rm
AGG}(\mathbf{e}_{v|\mathcal{T}}^{(i)},\mathbf{e}^{(i)}_{\mathcal{N}^{\mathcal{T}}(v)}),$

where $i=2,...K$. We set $K=2$ in all our experiments.

###  3.4. Multi-layer Perceptron Prediction

After conducting the LAGCN, we obtain the target-specific representations
$\mathbf{e}_{v|\mathcal{T}}^{(K+1)}$. To increase the representability of the
embeddings, we concatenate it with the output representations
$\mathbf{e}_{v}^{(1)}$ of KAGCN as
$\mathbf{e}_{v}^{c}=[\mathbf{e}_{v}^{(1)}\|\mathbf{e}_{v|\mathcal{T}}^{(K+1)}]$.
In such way, we can preserve both global similarity and local preference
effectively. To automatically balance the two parts, we feed the concatenated
representations $\mathbf{e}_{v|\mathcal{T}}^{o}$ into a multi-layer perceptron
(MLP) layers to obtain the final output representations:

(14)
$\mathbf{e}_{v|\mathcal{T}}^{o}=\mathbf{W}^{o}([\mathbf{e}_{v}^{(1)}\|\mathbf{e}_{v|\mathcal{T}}^{(K+1)}])+\mathbf{b}^{o},$

where $\mathbf{W}^{o}$ and $\mathbf{b}^{o}$ are learnable weights. For
recommendation with user-item $(u,i)$ prediction, the predicted score is their
inner product of user and item representations with the given target
$\mathcal{T}_{ui}=\\{u,i\\}$:

(15)
$p(u,i|\mathcal{T}_{ui})=\hat{y}_{ui}=\mathbf{e}_{u|\mathcal{T}}^{o\mathrm{T}}\mathbf{e}_{i|\mathcal{T}}^{o}.$

Since we only observe the positive interactions in the recommender systems, we
randomly sample some unobserved relations as the negative samples. To make the
learned similarities of the positive interactions are larger than the negative
samples, we optimize the model with the Bayesian personalized ranking loss
(Rendle et al., 2009):

(16) $\mathcal{L}_{T}=\sum_{(u,i)\in E^{+},(u,j)\notin
E^{-}}-\ln\sigma(p(u,j|\mathcal{T}_{uj})-p(u,i|\mathcal{T}_{ui})),$

where $E^{+}$ is the observed edges between user $u$ and item $i$ and $E^{-}$
is the uniformly sampled unobserved edges.

###  3.5. Optimization

#### Objective Function.

Combing the loss in Equation 2 and 16, we get the total objective function as
follows:

(17) $\mathcal{L}=\mathcal{L}_{kg}+\mathcal{L}_{T}+\lambda\|\Theta\|_{2}^{2},$

where $\Theta=\\{\
\mathbf{\hat{E}},\mathbf{W}^{(i)},\mathbf{b}^{(i)},\mathbf{W}_{t}^{(j)},\mathbf{W}_{e}^{(j)},\mathbf{W}^{o},\mathbf{b}^{o}|\forall
i\in\\{1,2,..,K+1\\},\forall j\in\\{1,2,...,K\\}\\}$ is the set of all
parameters, and $\mathbf{\hat{E}}$ is the embeddings of all entities and
relations. $\lambda$ is the weight of regularization. We optimize
$\mathcal{L}_{kg}$ and $\mathcal{L}_{T}$ alternatively and Adam (Kingma and
Ba, 2014) is used to optimize these parameters. The detailed training
algorithm is shown in Algorithm 1. The learning rate for Adam is initially set
to 0.025 at the beginning of the training, and the total epoch number is set
as 200.

Algorithm 1 Training Algorithm for _Knowledge-aware Conditional Attention
Networks_ (KCAN)

0: User-item network $G$; Knowledge graph $\mathcal{G}$. The configuration
$\Theta=\\{\
\mathbf{\hat{E}},\mathbf{W}^{(i)},\mathbf{b}^{(i)},\mathbf{W}_{t}^{(j)},\mathbf{W}_{e}^{(j)},\mathbf{W}^{o},\mathbf{b}^{o}|\forall
i\in\\{1,2,..,K+1\\},\forall j\in\\{1,2,...,K\\}\\}$.

1: Initialize all configurations

2: for epoch $\leftarrow 0,1,...,total\\_epoch\\_number$ do

3: /* Phase I Knowledge Graph Distillation*/

4: for each triple (h, r, t) in $\mathcal{G}$ do

5: Compute the loss of knowledge graph embedding in Equation 2 and update
knowledge graph embedding $e^{(0)}\in\Theta$ by Adam.

6: Compute the knowledge-aware attention $\hat{\pi}_{r}(v,t)$ in Equation 4.

7: end for

8: Based on Equation 5, propagate over the knowledge graph and the network by
the knowledge-aware attention $\hat{\pi}_{r}(v,t)$ to obtain embedding
$e^{(1)}$.

9: Based on $\hat{\pi}_{r}(v,t)$, sample target-specific subgraph.

10:

11: /* Phase II Knowledge Graph Refinement */

12: for each target $\mathcal{T}=\\{u,i\\}$ in $G$ do

13: for $k\leftarrow 1,...,K$ do

14: Based on Equation 10, compute the conditional attention
$\alpha(v,r,t|\mathcal{T})$.

15: Based on Equation 11 and 13, propagate over the target-specific subgraph
$\hat{S}_{K}(\mathcal{T})$ by the conditional attention
$\alpha(v,r,t|\mathcal{T})$ to obtain embedding
$e^{(k+1)}_{\cdot|\mathcal{T}}$.

16: end for

17: Based on $e^{(1)}$ and $e^{(K+1)}_{\cdot|\mathcal{T}}$, compute the
predicted score $p(u,i|\mathcal{T})$ by Equation 15.

18: Compute the target loss in Equation 16 and update the configuration
$\Theta$ by Adam.

19: end for

20: end for

#### Training Complexity.

The time cost of our proposed KCAN mainly comes from two part, KAGCN and
LCSAN. The time complexity of KCAN is $O((|E|+|E_{kg}|)*F_{1}^{2})$ where
$|E|$ is the number of edges in network $G$, $|E_{kg}|$ is the number of
triples in knowledge graph $\mathcal{G}$ and $F_{1}$ is the dimension of the
knowledge graph embedding. For LCSAN, the time complexity is
$O(|E_{kg}|*M*\sum_{i=1}^{K}F_{i}F_{i+1})$, where $M$ is the fixed-size number
of neighbors while sampling subgraphs, and $F_{i}$ is embedding size of $i$-th
layer. We usually set $S$ as 20. So the total complexity of KCAN is
$O((|E|+|E_{kg}|)*F_{1}^{2}+|E_{kg}|*S*\sum_{i=1}^{K}F_{i}F_{i+1})$. Note that
the $M$ and $F_{i}$ are small user-specified constants, the proposed KCAN is
linear to the scale of network and knowledge graph.

##  4\. Experiments

In this section, we evaluate our method on three real-world datasets to prove
its efficacy.

We aim to answer the following research questions:

  * •

RQ1: What do the knowledge attention and the conditional attention in the
proposed model learn?

  * •

RQ2: Does our proposed KCAN outperform the state-of-the-art knowledge-aware
methods?

  * •

RQ3: How do our proposed KAGCN, LCSAN layers affect the performance of KCAN
respectively?

  * •

RQ4: How do different choices of hyper-parameters affect the performance of
KCAN?

###  4.1. Datasets and Baselines

Table 1. Statistics of the datasets.

|  | MovieLens | Last-FM | Yelp
---|---|---|---|---
Network | #Users | 6,036 | 23, 566 | 45, 919
#Items | 2,445 | 48, 123 | 45, 538
#Interactions | 376,886 | 3, 034, 796 | 1, 185, 068
Knowledge Graph | #Entities | 182,011 | 58, 266 | 90, 961
#Relations | 12 | 9 | 42
#Triplets | 1,241,995 | 464, 567 | 1, 853, 704

In order to comprehensively evaluate the effectiveness of our proposed method
KCAN, we use three public benchmark datasets: MovieLens, Last-FM and Yelp.

  * •

MovieLens111https://grouplens.org/datasets/movielens/1m/ is a widely used
benchmark dataset in movie recommendations. It contains the explicit ratings
(ranging from 1-5) on the MovieLens website. We transform the rating into
implicit feedback where each entry is marked with 1 indicating that the user
has rated the item over a threshold score (4 for this dataset) and otherwise
0.

  * •

Last-FM222https://grouplens.org/datasets/hetrec-2011/ is a music listening
dataset collected from Last.fm online music systems. The timestamp of the
dataset is from Jan, 2015 to June, 2015. To ensure the quality of the dataset,
we use the 10-core setting like (Wang et al., 2019a), i.e., retaining users
and items with at least ten interactions.

  * •

Yelp333https://www.yelp.com/dataset/challenge is obtained from the 2018
edition of Yelp challenge. The items are local businesses like restaurants and
bars. Similarly, we also use 10-core setting on this dataset.

Besides, we also need to construct a corresponding knowledge graph from a
massive knowledge graph for each dataset. Actually, it is a rule-base rough
knowledge graph distill process. Microsoft
Satori444https://searchengineland.com/library/bing/bing-satori is used to
build a knowledge graph for MovieLens, we first select a subset of triplets
whose relation name contains ”movie” and the confidence level is greater than
0.9 from the whole knowledge graph. We match the entities with the items by
their title names. Similarly, the corresponding knowledge graph is built from
Freebase for Last-FM. For Yelp2018, we use the local business information
network, for example, category, location, and attribute, as the knowledge
graph.

The detailed statistics of the user-item networks and the knowledge graphs are
summarized in Table 1.

We compare our proposed KCAN with four representative types of baselines,
including regularization-based (CKE (Zhang et al., 2016)), factorization-based
(NMF (He and Chua, 2017)), path-based (RippleNet (Wang et al., 2018)) and GCN-
based (KGAT (Wang et al., 2019a)).

  * •

CKE (Zhang et al., 2016) combines collaborative filtering with the structural
knowledge content, the textual content and visual content in an unified
framework. In this paper, we implement CKE by combining collaborative
filtering and the structural knowledge content. It uses knowledge graph
information as regularization to fine tune the collaborative filtering.

  * •

NMF (He and Chua, 2017) is a novel factorization machine model for prediction
under sparse settings. It deepens factorization machine under the neural
network framework for learning higher-order and non-linear feature
interactions.

  * •

RippleNet (Wang et al., 2018) combines regularization-based and path-based
methods.It stimulates the propagation of user preferences over the set of
knowledge entities.

  * •

KGAT (Wang et al., 2019a) introduces graph attention into recommendation and
explicitly models the high-order connectivities in knowledge graph in an end-
to-end fashion.

We uniformly set the embedding size as 16 for all methods. The hidden size of
our method and KGAT is set as a tower structure with 16, 8, 8. For our model
and RippleNet, the number of hops is set as 2. The dropout rates of NFM, KGAT,
and our model are set as $0.1$. The fixed-size number of neighbors while
sampling subgraphs is set as 20 for our model. We do grid search from
$\\{0.01,0.025,0.05,0.1\\}$ to tune the learning rate parameter and from
$\\{10^{-1},10^{-2},10^{-3},10^{-4},10^{-5}\\}$ for the weights of the $L_{2}$
normalization. All the experiments are conducted on Intel(R) Xeon(R) CPU
E5-2699 v4 @ 2.20GHz with GeForce GTX Titan X GPU.

Figure 3. (a) Example from MovieLens dataset.The knowledge attention in the
whole knowledge graph and the user-item graph. (b) The conditional attention
on the target $(u_{0},i_{780})$-specific subgraph. (c) The conditional
attention on the target $(u_{0},i_{2466})$-specific subgraph. The red nodes
are the nodes which needs to be predicted.

###  4.2. Case Study (RQ1)

In this subsection, we show what the knowledge attention and the conditional
attention in the proposed model learn on the MovieLens dataset in Figure 3.

Figure 3 (a) shows the global knowledge attention in the Equation 4. The
attention is only related to knowledge relationships which is the same as the
KGAT. From this way, we can infer user preferences. The larger attention means
the more important edge. As we can see, the path $u_{0}\stackrel{{\scriptstyle
r_{12}}}{{\longrightarrow}}i_{1687}\stackrel{{\scriptstyle
r2}}{{\longrightarrow}}i_{2450}$ has the highest attention score between nodes
$u_{0}$ and $i_{2450}$. We can explain that the item $i_{2450}$ is recommend
to user $u_{0}$ because the user $u_{0}$ clicked item $i_{1687}$ which is
similar to item $i_{2450}$. Besides, the edge $u_{532}\stackrel{{\scriptstyle
r_{12}}}{{\longrightarrow}}i_{1687}$ with small weights $0.001$ has less
information. We can filter it out to distill the knowledge graph.

The Figure 3 (b), (c) show the local attention (Equation 10) with targets
$(u_{0},i_{780})$, $(u_{0},i_{2466})$ respectively. The red nodes are the
nodes which needs to be predicted. We refine the target-specific subgraph with
different weights by the local attention. We can see that there are different
attentions for the same edge $u_{0}\stackrel{{\scriptstyle
r_{12}}}{{\longrightarrow}}i_{1687}$ in the two subgraphs. The edge
$u_{0}\stackrel{{\scriptstyle r_{12}}}{{\longrightarrow}}i_{1687}$ is more
important for the prediction of $(u_{0},i_{2466})$ than the prediction of
$(u_{0},i_{780})$. All the baselines can not learn this information which is
important for predicting user-item pair.

###  4.3. Performance Comparison (RQ2)

We evaluate our method in two recommendation scenarios. (1) Top-K
recommendation. We use the leave-one-out strategy, which has been widely used
in previous works (He and Chua, 2017; Rendle et al., 2009) to evaluate the
recommendation performance. For a user, we randomly sample 100 items that are
not interacted by the user, ranking the test item among the 100 items. The
performance is judged by Hit Ratio@K (Hit@K) and Normalized Discounted
Cumulative Gain@K (NDCG@K) (He et al., 2015). If the true test item ranks in
the top $K$ lists, the Hit@K will be one otherwise zero. Compared with Hit@K,
NDCG@K pays more attention to the ranking order. The more front position of
the true item will have a larger NDCG@K. Then we compute the two metrics for
each user and obtain the average score at $K=10$. (2) Click-through rate (CTR)
prediction. We predict the score of each user-item pair, including positive
items and randomly sampled negative items, by the trained model. The
evaluation metric in CTR prediction is set as the area under the curve(AUC).
The AUC is equivalent to the probability of positive samples are ranked higher
than negative samples (Mason and Graham, 2002).

Table 2. Hit@10 and NDCG@10 in top-K recommendation.

Dataset | CKE | NFM | Ripple | KGAT | KCAN
---|---|---|---|---|---
MovieLens | Hit@10 | 0.293 | 0.384 | 0.607 | 0.467 | 0.668
NDCG@10 | 0.158 | 0.204 | 0.324 | 0.252 | 0.365
Last-FM | Hit@10 | 0.606 | 0.697 | 0.650 | 0.699 | 0.771
NDCG@10 | 0.383 | 0.421 | 0.367 | 0.437 | 0.506
Yelp | Hit@10 | 0.741 | 0.775 | 0.721 | 0.799 | 0.810
NDCG@10 | 0.480 | 0.491 | 0.410 | 0.502 | 0.527

Table 3. AUC value in CTR prediction. Dataset | CKE | NFM | Ripple | KGAT | KCAN
---|---|---|---|---|---
MovieLens | 0.530 | 0.809 | 0.903 | 0.841 | 0.907
Last-FM | 0.850 | 0.904 | 0.889 | 0.905 | 0.923
Yelp | 0.915 | 0.908 | 0.917 | 0.922 | 0.937
Figure 4. Left: AUC w.r.t. the log value of the weights of $L2$ normalization
$\log(\lambda)$. Right: AUC w.r.t. the fixed-size number of neighbors $M$ in
LCSAN.

The performance comparison results of the top-K recommendation and CTR
prediction are presented in Table 2 and 3, respectively. The observations are
illustrated as follows:

  * •

Our proposed KCAN achieves significant improvements over the baselines on all
the datasets in both top-K recommendation and CTR prediction. It demonstrates
the effectiveness of our proposed method KCAN. Moreover, KCAN outperforms the
KGAT in all experiments, and it indicates the effectiveness of conditional
attention for refining the knowledge graph to capture the local user
preference.

  * •

CKE is the worst one in most cases. It demonstrates that directly using the
knowledge graph as a regularization can not make full use of the knowledge
graph. Besides, the NFM outperforms CKE because it preserves the second-order
similarity implicitly by the input of the cross feature.

  * •

KGAT achieves better performance than CKE, NFM, Ripple in Last-FM and Yelp
datasets. It verifies the effectiveness of propagating information in the
knowledge graph to preserve global similarity.

  * •

In MovieLens dataset, CKE, NFM, KGAT have poorer performance than the
performance in the other two datasets. The reason is that MovieLens dataset
has very few users and items, and a large number of knowledge graphs, it is
more difficult to exploit knowledge graph effectively in this dataset.
However, Ripple achieves a good performance in this dataset. Ripple uses paths
from an item in a user’s history to a candidate item, and the path-based
methods can capture the local preference. It indicates the importance of
preserving local preference instead of the whole knowledge graph, especially
in a massive knowledge graph. Moreover, the improvements of our method KCAN
over Ripple may prove that the way we distill the knowledge graph is better
than than the way using multiple paths.

###  4.4. Study of KCAN (RQ3)

In this part, we evaluate how different parts of KCAN affect the performance.
To study their respective effects, we compare our KCAN with three variants:
(1) $\rm{KCAN_{w/o\ LC}}$. It removes the LCSAN layer from KCAN. (2)
$\rm{KCAN_{w/o\ GK}}$. It removes the KAGCN layers and uses the knowledge
graph embedding as the input of LCSAN. (3) $\rm{KCAN_{w/o\ both}}$. It removes
both the LCSAN and KAGCN. The result is shown in Table 4. The $\rm{KCAN_{w/o\
both}}$ performs the worst among the three variants, it demonstrates the two
layers, KAGCN and LCSAN, are beneficial for knowledge-aware recommendations.
This conclusion has been double verified since the three variants are worse
than the KCAN. Besides, the $\rm{KCAN_{w/o\ GK}}$ outperforms the
$\rm{KCAN_{w/o\ LC}}$, which demonstrates the necessity of distilling and
refining the knowledge graphs.

Table 4. Effects of KAGCN, LCSAN on top-K recommendation.

Dataset | $\rm{KCAN_{w/o\ LC}}$ | $\rm{KCAN_{w/o\ GK}}$ | $\rm{KCAN_{w/o\ both}}$ | KCAN
---|---|---|---|---
MovieLens | Hit@10 | 0.648 | 0.654 | 0.632 | 0.668
NDCG@10 | 0.355 | 0.364 | 0.348 | 0.365
Last-FM | Hit@10 | 0.712 | 0.750 | 0.698 | 0.771
NDCG@10 | 0.442 | 0.478 | 0.433 | 0.506
Yelp | Hit@10 | 0.772 | 0.785 | 0.735 | 0.810
NDCG@10 | 0.497 | 0.503 | 0.469 | 0.527

###  4.5. Parameter Sensitivity (RQ4)

Figure 5. The loss w.r.t the number of epoches.

In the section, we evaluate the scalability and how different settings of
hyper-parameters affect the performance of KCAN. Especially, we evaluate the
effect of the weights of $L2$ normalization $\lambda$ and the fixed-size
number of neighbors $M$ in LCSAN. Besides, we also measure the convergence of
the alternative optimization in this part. For brevity, we only report the AUC
results with Last-FM datasets, and similar trends can be observed on the other
datasets.

####  4.5.1. Weight of $L2$ normalization $\lambda$.

We show how the weights of $L2$ normalization $\lambda$ affect the performance
in Figure 4 Left. The $\lambda$ varies from
$\\{10^{-1},10^{-2},10^{-3},10^{-4},10^{-5}\\}$. When $\lambda$ increases from
$10^{-5}$ to $10^{-3}$, the performance is improved, demonstrating that the
$L2$ normalization can avoid overfitting to some extent. When $\lambda$
increases from $10^{-3}$ to $10^{-1}$, the performance becomes poorer. It
makes sense since the normalization is much larger than the losses which need
to be optimized in this situation.

####  4.5.2. The fixed-size number of neighbors $M$.

In the target-specific sampling step, we sample a fixed-size set of neighbors
to distill the knowledge graph and reduce the training time. We vary the
fixed-size number of neighbors $M$ from $\\{5,10,20,30\\}$. The result is
shown in Figure 4 Right. We can see that the performance raises firstly when
the fixed-size number of neighbors $M$ increases. This is reasonable because a
larger $M$ can embody more information in the subgraphs. After $M$ larger than
20, the curve is relatively stable. It demonstrates that our algorithm is not
very sensitive to $M$. Besides, we can find that a small $M$, such as 20, can
also achieve a relatively good result.

####  4.5.3. The convergence of the alternative optimization.

In the KCAN model, an alternative optimization is used to optimize the loss of
knowledge graph embedding $\mathcal{L}_{kg}$ and the loss of target prediction
$\mathcal{L}_{T}$, respectively. In this part, we measures the convergence
from the experiment by plotting the loss curve. The number of epoches varies
from 1 to 200. The result is shown in Figure 5. We can see that the two curves
descends very quickly, indicating the efficiency of the framework. About 100
epoches, the two loss are relatively stable, demonstrating our KCAN can
converge fast. Besides, we can find that the loss curve of $\mathcal{L}_{t}$
has very tiny shakes. It is reasonable because the process of sampling target-
specific subgraph will introduce sampling bias.

##  5\. Conclusion

In this paper, we investigate the problem of incorporating the knowledge graph
into the recommender system. To address the knowledge graph distillation issue
and knowledge graph refinement issue, we propose a novel knowledge-aware graph
convolutional network model named _Knowledge-aware Conditional Attention
Networks_ (KCAN). The framework consists of two main modules, the Knowledge
Graph Distillation module, and the Knowledge Graph Refinement module. We
propagates embedding with knowledge-aware attention in a recursive way to
capture the global similarity of entities. After that, a subgraph sampling
strategy is designed to distill the knowledge graph based on the attention
weight of the KAGCN. Also, the LCSAN propagates personalized information on
the sampled subgraph based on local conditional attention for refining the
knowledge graph. Benefitting from the two layers, the proposed KCAN can
effectively preserve topology similarity and distill and refine the knowledge
graph at the same time. Extensive experiments on three real-world scenarios
are conducted to demonstrate the effectiveness of our framework over several
state-of-the-art methods. In the future, we aim to further reduce the time
complexity of KCAN. Another interesting direction is to make the
recommendation more explainable.

##  6\. Acknowledgments

This work was supported in part by CCF-Ant Group Research Fund.

## References

  * (1)
  * Auer et al. (2007) Sören Auer, Christian Bizer, Georgi Kobilarov, Jens Lehmann, Richard Cyganiak, and Zachary Ives. 2007\.  Dbpedia: A nucleus for a web of open data.  In _The semantic web_. Springer, 722–735.
  * Baeza-Yates et al. (2004) Ricardo Baeza-Yates, Carlos Hurtado, and Marcelo Mendoza. 2004\.  Query recommendation using query logs in search engines. In _International conference on extending database technology_. Springer, 588–596.
  * Bollacker et al. (2008) Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. 2008.  Freebase: a collaboratively created graph database for structuring human knowledge. In _Proceedings of the 2008 ACM SIGMOD international conference on Management of data_. 1247–1250.
  * Bordes et al. (2013) Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. 2013\.  Translating embeddings for modeling multi-relational data. In _Neural Information Processing Systems (NIPS)_. 1–9.
  * Cao et al. (2019) Yixin Cao, Xiang Wang, Xiangnan He, Zikun Hu, and Tat-Seng Chua. 2019.  Unifying knowledge graph learning and recommendation: Towards a better understanding of user preferences. In _The world wide web conference_. 151–161.
  * Dai et al. (2020) Yuanfei Dai, Shiping Wang, Neal N Xiong, and Wenzhong Guo. 2020\.  A survey on knowledge graph embedding: Approaches, applications and benchmarks.  _Electronics_ 9, 5 (2020), 750.
  * Davidson et al. (2010) James Davidson, Benjamin Liebald, Junning Liu, Palash Nandy, Taylor Van Vleet, Ullas Gargi, Sujoy Gupta, Yu He, Mike Lambert, Blake Livingston, et al. 2010\.  The YouTube video recommendation system. In _Proceedings of the fourth ACM conference on Recommender systems_. 293–296.
  * Defferrard et al. (2016) Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. 2016.  Convolutional neural networks on graphs with fast localized spectral filtering. In _Advances in neural information processing systems_. 3844–3852.
  * Dettmers et al. (2018) Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. 2018.  Convolutional 2d knowledge graph embeddings. In _Thirty-Second AAAI Conference on Artificial Intelligence_.
  * Dong et al. (2017) Yuxiao Dong, Nitesh V Chawla, and Ananthram Swami. 2017\.  metapath2vec: Scalable representation learning for heterogeneous networks. In _Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining_. 135–144.
  * Fu et al. (2017) Tao-yang Fu, Wang-Chien Lee, and Zhen Lei. 2017.  Hin2vec: Explore meta-paths in heterogeneous information networks for representation learning. In _Proceedings of the 2017 ACM on Conference on Information and Knowledge Management_. 1797–1806.
  * Gao et al. (2020) Yang Gao, Yi-Fan Li, Yu Lin, Hang Gao, and Latifur Khan. 2020.  Deep Learning on Knowledge Graph for Recommender System: A Survey.  _arXiv preprint arXiv:2004.00387_ (2020).
  * Hamilton et al. (2017) William L. Hamilton, Rex Ying, and Jure Leskovec. 2017\.  Inductive Representation Learning on Large Graphs. In _NIPS_.
  * He et al. (2015) Xiangnan He, Tao Chen, Min-Yen Kan, and Xiao Chen. 2015\.  Trirank: Review-aware explainable recommendation by modeling aspects. In _Proceedings of the 24th ACM International on Conference on Information and Knowledge Management_. 1661–1670.
  * He and Chua (2017) Xiangnan He and Tat-Seng Chua. 2017.  Neural factorization machines for sparse predictive analytics. In _Proceedings of the 40th International ACM SIGIR conference on Research and Development in Information Retrieval_. 355–364.
  * Hinton et al. (2015) Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. 2015\.  Distilling the knowledge in a neural network.  _arXiv preprint arXiv:1503.02531_ (2015).
  * Hu et al. (2018) Binbin Hu, Chuan Shi, Wayne Xin Zhao, and Philip S Yu. 2018\.  Leveraging meta-path based context for top-n recommendation with a neural co-attention model. In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 1531–1540.
  * Huang et al. (2017) Xiao Huang, Jundong Li, and Xia Hu. 2017.  Label informed attributed network embedding. In _Proceedings of the Tenth ACM International Conference on Web Search and Data Mining_. 731–739.
  * 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)_. 687–696.
  * Kim et al. (2016) Donghyun Kim, Chanyoung Park, Jinoh Oh, Sungyoung Lee, and Hwanjo Yu. 2016.  Convolutional matrix factorization for document context-aware recommendation. In _Proceedings of the 10th ACM Conference on Recommender Systems_. 233–240.
  * Kingma and Ba (2014) Diederik P Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ (2014).
  * 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)_.
  * Lin et al. (2020) Xuan Lin, Zhe Quan, Zhi-Jie Wang, Tengfei Ma, and Xiangxiang Zeng. 2020.  Kgnn: Knowledge graph neural network for drug-drug interaction prediction. In _Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20 (International Joint Conferences on Artificial Intelligence Organization)_. 2739–2745.
  * 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 AAAI Conference on Artificial Intelligence_ , Vol. 29.
  * Mason and Graham (2002) Simon J Mason and Nicholas E Graham. 2002.  Areas beneath the relative operating characteristics (ROC) and relative operating levels (ROL) curves: Statistical significance and interpretation.  _Quarterly Journal of the Royal Meteorological Society: A journal of the atmospheric sciences, applied meteorology and physical oceanography_ 128, 584 (2002), 2145–2166.
  * Miller (1995) George A Miller. 1995\.  WordNet: a lexical database for English.  _Commun. ACM_ 38, 11 (1995), 39–41.
  * 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 _Icml_.
  * Niu et al. (2018) Wei Niu, James Caverlee, and Haokai Lu. 2018.  Neural personalized ranking for image recommendation. In _Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining_. 423–431.
  * Qin et al. (2020) Chuan Qin, Hengshu Zhu, Fuzhen Zhuang, Qingyu Guo, Qi Zhang, Le Zhang, Chao Wang, Enhong Chen, and Hui Xiong. 2020\.  A survey on knowledge graph-based recommender systems.  _SCIENTIA SINICA Informationis_ 50, 7 (2020), 937–956.
  * Rendle et al. (2009) Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, and Lars Schmidt-Thieme. 2009.  BPR: Bayesian personalized ranking from implicit feedback. In _Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence_. 452–461.
  * Schafer et al. (2001) J Ben Schafer, Joseph A Konstan, and John Riedl. 2001\.  E-commerce mendation applications.  _Data mining and knowledge discovery_ 5, 1-2 (2001), 115–153.
  * Schein et al. (2002) Andrew I Schein, Alexandrin Popescul, Lyle H Ungar, and David M Pennock. 2002.  Methods and metrics for cold-start recommendations. In _Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval_. 253–260.
  * 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.
  * Sha et al. (2019) Xiao Sha, Zhu Sun, and Jie Zhang. 2019.  Attentive Knowledge Graph Embedding for Personalized Recommendation.  _arXiv preprint arXiv:1910.08288_ (2019).
  * Shuman et al. (2013) David I Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. 2013\.  The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains.  _IEEE signal processing magazine_ 30, 3 (2013), 83–98.
  * Song et al. (2019) Weiping Song, Zhijian Duan, Ziqing Yang, Hao Zhu, Ming Zhang, and Jian Tang. 2019\.  Explainable Knowledge Graph-based Recommendation via Deep Reinforcement Learning.  _arXiv preprint arXiv:1906.09506_ (2019).
  * Sun et al. (2011) Yizhou Sun, Jiawei Han, Xifeng Yan, Philip S Yu, and Tianyi Wu. 2011.  Pathsim: Meta path-based top-k similarity search in heterogeneous information networks.  _Proceedings of the VLDB Endowment_ 4, 11 (2011), 992–1003.
  * Trouillon et al. (2016) Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. 2016.  Complex embeddings for simple link prediction. In _International Conference on Machine Learning_. PMLR, 2071–2080.
  * 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. (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. (2018) Hongwei Wang, Fuzheng Zhang, Jialin Wang, Miao Zhao, Wenjie Li, Xing Xie, and Minyi Guo. 2018.  Ripplenet: Propagating user preferences on the knowledge graph for recommender systems. In _Proceedings of the 27th ACM International Conference on Information and Knowledge Management_. 417–426.
  * Wang et al. (2019d) Hongwei Wang, Fuzheng Zhang, Mengdi Zhang, Jure Leskovec, Miao Zhao, Wenjie Li, and Zhongyuan Wang. 2019d.  Knowledge-aware graph neural networks with label smoothness regularization for recommender systems. In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 968–977.
  * Wang et al. (2019e) Hongwei Wang, Miao Zhao, Xing Xie, Wenjie Li, and Minyi Guo. 2019e.  Knowledge Graph Convolutional Networks for Recommender Systems. In _The World Wide Web Conference_. 3307–3313.
  * Wang et al. (2017) Quan Wang, Zhendong Mao, Bin Wang, and Li Guo. 2017\.  Knowledge graph embedding: A survey of approaches and applications.  _IEEE Transactions on Knowledge and Data Engineering_ 29, 12 (2017), 2724–2743.
  * 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 _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 950–958.
  * Wang et al. (2019b) Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip S Yu. 2019b.  Heterogeneous graph attention network. In _The World Wide Web Conference_. 2022–2032.
  * Wang et al. (2019c) Xiang Wang, Dingxian Wang, Canran Xu, Xiangnan He, Yixin Cao, and Tat-Seng Chua. 2019c.  Explainable reasoning over knowledge graphs for recommendation. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 33. 5329–5336.
  * Wang et al. (2014) Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. 2014\.  Knowledge graph embedding by translating on hyperplanes. In _Twenty-Eighth AAAI conference on artificial intelligence_.
  * Xian et al. (2019) Yikun Xian, Zuohui Fu, S Muthukrishnan, Gerard De Melo, and Yongfeng Zhang. 2019.  Reinforcement knowledge graph reasoning for explainable recommendation. In _Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval_. 285–294.
  * Xin et al. (2019) Xin Xin, Xiangnan He, Yongfeng Zhang, Yongdong Zhang, and Joemon Jose. 2019.  Relational collaborative filtering: Modeling multiple item relations for recommendation. In _Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval_. 125–134.
  * Yang et al. (2014) Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. 2014.  Embedding entities and relations for learning and inference in knowledge bases.  _arXiv preprint arXiv:1412.6575_ (2014).
  * Yu et al. (2014) Xiao Yu, Xiang Ren, Yizhou Sun, Quanquan Gu, Bradley Sturt, Urvashi Khandelwal, Brandon Norick, and Jiawei Han. 2014\.  Personalized entity recommendation: A heterogeneous information network approach. In _Proceedings of the 7th ACM international conference on Web search and data mining_. 283–292.
  * Zhang et al. (2016) Fuzheng Zhang, Nicholas Jing Yuan, Defu Lian, Xing Xie, and Wei-Ying Ma. 2016\.  Collaborative knowledge base embedding for recommender systems. In _Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining_. 353–362.
  * Zhang et al. (2020) Ziwei Zhang, Peng Cui, and Wenwu Zhu. 2020.  Deep learning on graphs: A survey.  _IEEE Transactions on Knowledge and Data Engineering_ (2020).