Learning to Deceive Knowledge Graph Augmented Models via Targeted Perturbation
Authors: Mrigank Raman
Aaron Chan
Siddhant Agarwal
PeiFeng Wang
Hansen Wang
Sungchul Kim
Ryan Rossi
Handong Zhao
Nedim Lipka
Xiang Ren
Venue: ICLR 2021 Poster (2021)
Keywords: neural symbolic reasoning
interpretability
model explanation
faithfulness
knowledge graph
commonsense question answering
recommender system

Abstract: Knowledge graphs (KGs) have helped neural models improve performance on various knowledge-intensive tasks, like question answering and item recommendation. By using attention over the KG, such KG-augmented models can also "explain" which KG information was most relevant for making a given prediction. In this paper, we question whether these models are really behaving as we expect. We show that, through a reinforcement learning policy (or even simple heuristics), one can produce deceptively perturbed KGs, which maintain the downstream performance of the original KG while significantly deviating from the original KG's semantics and structure. Our findings raise doubts about KG-augmented models' ability to reason about KG information and give sensible explanations.

Published as a conference paper at ICLR 2021
LEARNING TO DECEIVE KNOWLEDGE GRAPH AUGMENTED MODELS VIA TARGETED PERTURBATION
Mrigank Raman's ' Aaron Chan?i, Siddhant Agarwal Peifeng Wang* Hansen Wang"', Sungchul Kim", Ryan Rossi', Handong Zhao', Nedim Lipka², Xiang Ren" Indian Institute of Technology, Delhi, Uniiversity of Southern California, 3 Indian Institute of Technology, Kharagpur, "Tsinghua University, *Adobe Research mt1170736@iitd ac in, {chanaaro, peifengw xi xiangrenj@usc. edu, agarwal wwwaantttiiikgiieeeeeaaaaaiatttt ac. in, wang-ha hss 1 remamlls s. tsinghua edu.cn, (sukim, ryrossi, hazhao, lipka @adobe.com com
ABSTRACT
Knowledge graphs (KGs) have helped neural models improve performance on various snowledge-intensive tasks, like question answering and item recommen- dation. By using attention over the KG, such KG-augmented models can also "explain" which KG information was most relevant for making given prediction. In this paper, we question whether these models are really behaving as we expect. We show that, through a reinforcement learning policy (or even simple heuristies), one can produce deceptively perturbed KGs, which maintain the downstream per- formance of the original KG while significantly deviating from the original KG's semantics and structure. Our findings raise doubts about KG-augmented models' ability to reason about KG information and give sensible explanations.
INTRODUCTION
Recently, neural reasoning over knowledge graphs (KGs) has emerged a popular paradigm in machine learning and natural language processing (NLP). KG-augmented models have improved performance on number of knowledge-intensive downstream tasks: for question answering (QA), the KG provides context about how a given answer choice is related to the question (Lin et al.) 2019 Feng et al.J 2020; Lv et al. 2020: [almor et al.) 2018); for item recommendation, the KG mitigates data sparsity and cold start issues (Wang et al. 201 8b; 2019a b 201 Sa). Furthermore, by using attention over the KG, such models aim to explain which KG information was most relevant for making given prediction (Lin et al.. 2019 Feng al., 2020 Wang al., 2018b 2019b Cao 2019: Gao et al. 2019). Nonetheless, the process in which KG-augmented models reason about KG information still not well understood. It is assumed that, like humans, KG-augmented models base their predictions on meaningful KG paths and that this process is responsible for their performance gains (Lin al. 2019 Feng et al. 2020 Gao et 2019 Song al. 2019).
ctt al.
In this paper, we question if existing KG-augmented models actually use KGs in this human-like manner. We study this question primarily by measuring model performance when the KG's mantics and structure have been perturbed to hinder human comprehension. To perturb the KG, we propose four perturbation heuristics and reinforcement learning (RL) based perturbation algorithm. Surprisingly, for KG-augmented models on both commonsense QA and item recommendation, we find that the KG can be extensively perturbed with little no effect on performance. This raises doubts about KG-augmented models' use of KGs and the plausibility of their explanations.
2 PROBLEM SETTING
Our goal is to investigate whether KG-augmented models and humans use KGs similarly. Since KGs are human-labeled, we assume that they are generally accurate and meaningful to humans. Thus, across different perturbation methods, we measure model performance when every edge in the KG has been perturbed to make less sense to humans. To quantify the extent to which the KG has been perturbed, we also measure both semantic and structural similarity between the original
Work done while MR, SA and HW interned remotely at USC. Code and data are available at https: //git thub. com/ INK-USC/deceive (G-models Equal contribution.

---

Published as a conference paper at ICLR 2021
KG and perturbed KG. If original-perturben KG similarity is low, then human- like KG- KG-augmented model should achieve worse performance with the perturbed KG than with the original KG. Further- more, evaluate the plausibility of -uggumeeeedd models' explanations when using original and perturbed KGs, by asking humans to rate these explanations" readability and usability.
Notation Let Fø be KG- augmented model, and let (Xmin, X Xws) be for some downstream task. We denote a KG as G = (. where & is the set of entities (nodes), R the set of relation types, and T e2) | 61,62 E E, e R. the set of facts (edges) com- posed from existing entities and relations (Zheng et al. 2018). Let
task input
dataset
original KG
Step 1: train model original KG, then freeze model
perturbed KG
Step 2: apply N perturbations to full KG
KG KG-augmented model (trained)
KG aug-mmmmana model (frozan)
Step compare
G' = (E, T) be the KG obtained after perturbing G, where R' _ R and T' * T. Let f(G.g') be a function that measures similarity between g and G Let 9(g) be the downstream performance when evaluating Fo on Xes and G. Also, let e denote the concatenation operation, and let (e) denote the set of L-hop neighbors for entity e E.
downstroam tast porformance (original KG)
downstream performance
downstroam performance (perturbed KG)
Proposed KG Perturbation Framework. Our pro- cedure consists of three main steps: (1) train the KG-augmented model on the original KG, then freeze the model; (2) obtain the perturbed KG by applying N = [T] perturbations to the full orig- inal KG; and (3) compare the perturbed KG's downstream perfor- mance to that of the original KG.
Figure 1:
High-Level Procedure First, we train Fa on Xpai and G, then evaluate To on Xus and G to get the original performance g(G). Second, we freeze Fe. then perturb G to obtain g'. Third, we evaluate Fo on Xus and to get the perturbed performance g(g'), ). Finally, we measure g(g) - -g(")) and f(G
g') ) to assess how human-like Fo's 's reasoning process is. This procedure is illustrated in Fig. I In this paper, we consider two downstream tasks: commonsense QA and item recommendation.
Commonsense QA Given a question x and a set of l possible answers A = (yr,.... }, the task is to predict compatibility score for each (z, y) pair, such that the highest score is predicted for the correct answer. In commonsense QA, the questions are designed to require commonsense knowl- edge which is typically unstated in natural language. but more likely to be found in KGs (Talmor et al. 2018). Let Fraa be a text encoder (Devlin et al. 2018). Frrrph be a graph encoder, and F. be an MLP classifier, where d, v C 0. "Let G(ew) denote subgraph of G consisting of entities mentioned in text sequence x @ plus their corresponding edges. We start by computing a text embedding his = F (x + y) and graph embedding hgnnas = F F (G(x.))) After that, we compute the score for (2. as S(x.a) = Fell (luee ① hgguph). Finally, we select the highest scoring answer: Ypred arg max S(z.u). augaeeeete commonsense QA models vary primarily in their design of ,= In particular, path-basch models compute the graph embedding by using attention to selec- tively aggregate paths in the subgraph. The attention scores can help explain which paths the model focused on most for given prediction (Lin et al. 2019 Feng al. 2020 Santoro al. 2017)-
s
Item Recommendation We consider a set of users 24 = [u), U2, u2,..., a set of items V = (vi, u2..... v, and user-item interaction matrix Y R=x*= with entries you. If user a has been observed to engage with item v, then Yue = 1; otherwise, Yue = 0. Additionally, we consider a KG G, in which R is the set of relation types in g. In nodes are items E V, and edges facts of the form (v, r, e'), where E R is a relation. For the zero entries in Y (i.c., Buo 0), our task is to predict a compatibility score for user-item pair (u, v), indicating how likely user u is to want to engage with item e. We represent each user item v, and relation as embeddings and r, respectively. Given a user-item pair (u,v), its compatibility score is computed as (u, v), the inner product between u and v. KG-augmented recommender systems differ mainly in how they use g to compute and v. Generally, these models do so by using attention to selectively aggregate items/relations in G. The attention scores can help explain which items/relations the model found most relevant for a given prediction (Wang et al. 2018b 2019b).
v,
2

---

Published as a conference paper at ICLR 2021
3 KG SIMILARITY METRICS
To measure how much the perturbed KG has deviated from the original KG, we propose several metries for capturing semantic (ATS) and structural (SC2D, SD2) similarity between KGs.
Aggregated Triple Score (ATS) ATS measures semantic similarity between two KGs. Let sg be an edge (triple) scoring function, such that sc(ei, r; ea) measures how likely edge r,,, r, e2) ) to exist in G. Also, assume 8g has been pre-trained on for link prediction. Then, ATS is defined as fATs(G, G.) = + Eees.n.e)eTT (g(e1, E [0, 1], which denotes the mean 8g score across all edges in g'. Intuitively, ATS), then we say that G' and have high semantic similarity. sg is task-specific, as KGs from different tasks may differ greatly in semantics. For commonsense QA, we use the ag from Li et al. (016); for item recommendation, we use the sg from Yang et al. (2015). While ATS captures semantic KG differences, it is not sensitive to KG connectivity structure. Note that fais 9) may not equal since 86 may not perfectly generalize KGs beyond those it was trained on.
high percentage of edges in g' are also likely to exist g (i.e., high
Similarity in Clustering Coefficient Distribution (SC2D) SC2D measures structural similarity between two KGs and is derived from the local clustering coefficient (Saramäki et al.] 2007 Onnela
et al. 2005 Fagiolo 2007). For a given entity in & (treated here as undirected), the local clustering coefficient is the fraction of possible triangles through the entity that exist (i.e., how tightly the entity's 's neighbors cluster around it). For entity E E, the local clustering coefficient is defined as a 2Trr(ee)///aiee (erriee)/((egg) (deg(e))
- 1)), where Tri(e.) is the number of triangles through e,, and deg(e,) is the degree of e,. For each relation E R. let G" be the subgraph of g consisting of all edges in T with That is, G" = (E.r,T), where T = ((e,r,e') e, EE}. Let e" denote the dil-nnmmall clustering coefficient vector for g", where the ith element of c* is e,. Then, the mean clustering coefficient vectors for G and g' are C. [ed Erer c" and cp क ΣreR c", respectively. SC2D
is defined as fscmn G') = 1 ||c. 12
1e--cp 2 [0, 1], with higher value indicating higher similarity.
Similarity in Degree Distribution (SD2) SD2 also measures structural similarity between two KGs, while addressing SC2D's ineffectiveness when the KGs' entities have tiny local clustering coefficients (e.g., the item KG used by recommender systems is roughly bipartite). In such cases, SC2D is always close to one regardless of perturbation method, thus rendering SC2D useless. Let d' denote the -El-dimensional degree vector for g", where the ith element of d' is deg(e:). Then, the mean degree vectors for G and g' are d,
[ Σrer d' and d = ार Ever d', respectively. SD2 dpl-211 [0, 1], with higher value indicating higher similarity.
is defined as fsoe =
1|d,-d,ll
METHODS FOR TARGETED KG PERTURBATION
We aim to study how a KG's semantics and structure impact KG-augmented models' downstream performance. To do so, we measure model performance in response to various forms of targeted KG perturbation. While KG's semantics can be perturbed via its relation types, its structure can be perturbed via its edge connections. Therefore, design five methods four heuristic, one RI. for perturbing KG relation types, edge connections, or both (Fig. 2
4.1 HBURISTIC-BASED KG PERTURBATION
Our four KG perturbation heuristics are as follows: Relation Swapping (RS) randomly chooses two edges from T and swaps their relations. Relation Replacement (RR) randomly chooses an edge (2)) E T, then replaces rı with another relation r2 argmin,,g sa(e1, (c1,,,,e2) Edge Rewiring (ER) randomly chooses an edge (e1, r, e2) E T, then replaces e2 with another entity es E E (e Edge Deletion (ED) randomly chooses an edge (e)) E T and deletes it. For ED, perturbing all edges means deleting all but 10 edges.
4.2 RL-BASED KG PERTURBATION
We introduce an RL-based approach for perturbing the KG. Given a KG, G, we train a policy to output a perturbed KG, g", such that ATS, fAss(G, g') g'), is minimized, while downstream performance, g(g") ). is maximized. Specifically, the RL agent is trained to perturb g via relation replacement, so call our algorithm RL-RR. Because the agent is limited to applying N [T] perturbations g, our RL problem is framed as a finite horizon Markov decision process. In the rest this section, we define the actions, states, and reward in our RL problem, then explain how RL-RR is implemented.
3

---

Published as a conference paper at ICLR 2021
Capusiec!
Sit
Capabrerh
Sit
Hawoffor
Child
Dask
Child
Alloocation
AlLocation
Desires
All Alsovatton
ALoocatonn
Desiitss
AlLecation
Original KG
Learn
Schoolroom
Learn
Schoolroom
UlidtFor
Synomim
GapecheCi
UsedFor
UredPiy
Syntmym
Classroom
Classroom
Relation Swapping (RS)
Child
Desk
Edge Rewiring (ER)
Destres
AlLocation
AlEocation
Allocation
Relation Replacement (RR, RL-RR)
Learn
Schoolroam
Edge Deletion (ED)
CapataeC
Sit
Lieetfur
UsedPor
Synonym
Capabaach
Sit
UseetPar
Child
Desk
Child
Al Aloeatien
Destnss
Canteo
MLocatton
Desine
AlLecation
Learn
Schoolroom
Schoolroom
UtidiFor
Synanam
UsedFia
Sproppp
Classroom
Classroom
Figure 2: Proposed KG Perturbation Methods. We propose four heuristie-based perturbation methods and RL-based perturbation method. In this diagram, we consider example edge (Child, Lolocatio on, Classroom within subgraph the original ConceptNet KG (shown in bluc). We illustrate how this edge (and possibly other edges) changes in response to different perturbation methods (shown in red). Unlike the heuristic-based methods (RS, RR, ER, ED), the RL-based method RL-RR) is trained to maximize downstream performance and minimize original-perturber KG semantic similarity.
Actions The action space consists of all possible relation replacements in G. i.e., replacing (e1, r,e) E with (e1,r',eg Since having such a large action space poses computational is- decouple each action into sequence of three subactions and operate instead in this smaller subaction space. Hence, a perturbation action at time step t would be (a, aa ( Namely, (0) is sampling entity е1 E E; (1) is selecting edge (e) T; and af is selecting relation E R. replace r in (e,, To make the policy choose low-ATS perturbations, we further restrict the (2 subaction space be the subactions resulting in the lowest ATS. Note that each at is represented by its corresponding pre-trained TransE (Bordes al. 2013) entity, relation, or edge embedding in G. Since these TransE embeddings are not updated by the perturbation policy, we use at") to refer to both the subaction and subaction embedding. Meanwhile, a does not have any representation besides its constituent subaction embeddings.
States The state space is the set of all g' with the same entities and connectivity structure as G. Here, we make a distinction between state state embedding. The state at is the actual KG after I perturbation steps and is denoted as G.. The state embedding at is a vector representation of G, and is denoted as To match or, we also decouple into substate embeddings:
(st ,.())) (²)).
Reward The reward funetion pushes the policy maximize downstream performance. For com- monsense QA. higher reward corresponds to lower KL divergence between the predicted and true answer distributions. For item recommendation, we use validation AUC as the reward function.
4.2.1 DQN ARCHITECTURE AND TRAINING
action-suhaction hierarchy. At the action (top) level, for f, the policy selects an action a, given state st. then performs on G. to obtain Ge+1- At the subaction (bottom) level, for index [0, 1,2] within time step t, the policy selects subaction (i+1) given (8) and, if any, previous subactions.
As described above, RL-RR is modeled
of
At t, the policy takes input the substate embedding (0), One approach for computing s, would be to directly encode G, with graph encoder Feruph, such that ( Fronph( DDi et al. 2018 Sun et al., 22200] Ma et al. 2019b). However, since we aim to assess graph encoders' ability to capture KG information, would not make sense
graph encoder for KG perturbation. Instead, we use an LSTM (Hochreiter & Schmidhuber, 1997) to update substate embeddings both within and across time steps, while jointly encoding substate and subaction embeddings. Observe that
4

---

Published as a conference paper at ICLR 2021
this means of only implicitly captures KG state information via af 1 since the choice of each subaction is constrained precisely by which entities, relations, or edges are available in G..
the DQN algorithm (Mnih al.) 2015). Abstractly, the goal of DQN is to learn Q-function ((s;,ar) oz), which outputs the expected reward for taking action or in state Se- In our implementation, Q(+,, a4) is decomposed into sequential pair of uub-Q-functions: Q Q1(a, (a a. ) (MLP(a, (a.) MLP(h,))) and 1=( di a.") (MLP(a, MLP(H"")) MLP denotes the vector representation computed by multi-layer perceptron, while h,0 and (,
To train RL-RR.
denote the respective LSTM encodings of (s, " and (s [a! e I)..
Fig. depicts the perturba- tion procedure at t. First, either initialize of with trained embedding weight vee- tor t= 0, or set it to 8:-1 oth- erwise. Second, we uniformly sample af", which is encoded as (n LSTMCelll (o()) )
KG
Downstreamn
Task
Reward
apply perturbation: = (a. a.",
DON Module
(1)
(2)
(a 11
s (9)
a
(01)
0,(a
(1)
a.9))
LSTMCell also updates (0) to s!" Third, we com- pute (2(al")s55) ), which takes 1, as input and outputs at) Fourth, we encode at as 1,a) = LSTMCell2(s!), [a[") ① af LSTMCell, also updates
[0]
(1)
S. (1)
LSTM Cell 1
LSTM Cell 2
5
S IH
(0)
Figure 3: DQN Architecture for RL-RR
(1) to sfa) Fifth, we compute 1x( (2) "a a, a. which takes 11) as input and outputs a,")
Note that a. and a, are selected e-greedily during training and greedily during evaluation. Fi- nally, using a: = (a, (0) "aa"), (a,,a)))) ). we perturb G. to get Gr+1.
.at"
Ideally, for each t, we would evaluate Gi+1 on the downstream task to obtain the reward. However, downstream evaluation is expensive, so we only compute reward every T time steps. Moreover, for the policy generalize well, state embeddings (st-T+1, ... 8t-1, st) should not correlate with the order actions (ae-T+1; a.)) Thus, for every T time steps during training, we shuffle the last T' actions after computing reward, then update the LSTM and sub- Q-functions with respect to the shuffled actions. Doing so encourages state embeddings to be invariant to action order.
5 EXPERIMENTS
In this section, we test KG-augmented models on their ability to maintain performance and explain- ability when the KG has been extensively perturbed. As explained in Sec. 2 and Fig. [I] the model first trained on given dataset using original KG, frozen throughout KG perturbation, then used to compare downstream performance between original KG and perturbed KG. For all models, datasets, and perturbation methods, we measure performance and KG similarity when all [T] KG edges have been perturbed, averaged over three runs. For subset of taseel--datas--etturbblee configurations, we also measure performance as function of the number of edges perturbed. In addition, conduct a user study where humans asked to rate original and perturbed KGs, with respect to readability and usability for solving downstream tasks.
5.1 COMMONSENSE QA
For commonsense QA, the KG-augmented models we experiment with are RN (with attentional path aggregation) (Lin et al., 2019 Santoro et al., 2017) and MHGRN Feng et al. 2020), which have been shown to outperform non-KG KG models (Devlin et al. [0188] Liu et al. (019) and a num- ber of KG-augmented models (Lin et al. 2019 Ma et al.) 2019 9a Wang et al. 2019c Schlichtkrull al. 2018) on this task. For both RN and MHGRN, we use BERT-Bas (Devlin al. 2018 text encoder. We evaluate on the CommonsenseeQ (CSQA) (Tlmorr et al. 2018 and OpenBookQA (OBQA) (Mihaylov et al.) 2018) datasets, using ConceptNet (Speer al. 2016) as the KG. Perfor- mance is measured using accuracy (Ace), which is the standard metric for commonsense QA (Lin
al. 2019 Feng et al. 2020).
5

---

Published as a conference paper at ICLR 2021
Table I:
Comparison of Perturbation Methods on CSQA. We follow the standard protocol reporting
CSQA test accuracy on the in-house data split from Lin et al. 20199 as official test labels are not available.
CSQA
RN
MHGRN
Method
Acc (t)
ATS (L)
SC2D (.)
SD2 (
Ace (1)
ATS (L)
SC2D
SD2 (J)
No KG
53,41
53.41
Original KG
56.87
0.940
1.000
1.000
57.21
0.940
1,000
1.000
Relation Swapping (RS)
53.42
0.831
0.144
6.16B-3
53.42
0.831
0.144
6.16B-3
Relation Replacement (RR)
53.42
0.329
0.091
1.70B-3
52.22
0.329
0.091
1.70E-3
Edge Rewiring (ER)
53.42
0,505
0.116
2.30F-3
52.22
0.505
0.116
2.30F-3
Edge Deletion (ED)
52.21
0.933
0.126
2.00F-3
51.00
0.933
0.126
2.00B-3
RL-RR
55.21
0.322
0.093
1.66E-3
55.52
0.314
0,092
1.78B-3
Table 2: Comparison Perturbation Methods on OBQA
OBQA
RN
MHGRN
Method
Acc (*)
ATS (1)
SC2D (L)
SD2 (L)
Acc (f)
ATS (U)
SC2D ())
SD2 (L)
No KG
62.00
62.00
Original KG
66.80
0,934
1.000
1,000
68.00
0.934
1.000
1,000
Relation Swapping (RS)
67.00
0.857
0,159
7.73E-3
67.30
0.857
0.159
7.73E-3
Relation Replacement (RR)
66.80
0.269
0.095
1.84F-3
67.60
0.269
0.095
1.84-3
Edge Rewining (ER)
66.60
0.620
0.146
7.26E-3
67.00
0.620
0.146
7.26E-3
Edge Deletion (ED)
66.80
0.923
0.134
2.19E-3
67.60
0,923
0.134
2.19E-3
RL-RR
67.30
0.255
0.097
1.79E-4
67.70
0,248
0.094
1.75E.4
CSQA Results for CSQA are given in Table 1 For RN and MHGRN, we see that RL-RR achieves slightly worse accuracy than Original KG, while RS, RR, and ER perform on par with No KG. For both models, ED performs noticeably worse than No KG.
OBQA Results for OBQA are shown in Table For RN, we see that RL-RR actually obtains better accuracy than Original KG. For MHGRN, RL-RR yields marginally worse accuracy than Original KG. Meanwhile, for both RN and MHGRN, all heuristics uniformly achieve similar accuracy as Original KG, which itself significantly outperforms No KG.
Analysis Tables 12 demonstrate that perturbing KG does not necessarily imply decreased perfor- mance, nor does guarantee the creation of invalid or novel facts. As shown by the KG similarity scores, some perturbation methods cause greater semantic or structural KG changes than others. Perturbed KGs produced by RS and ED have high ATS (i.e., semantic similarity original KG), while RR, ER, and RL-RR achieve relatively low ATS. Meanwhile, SC2D and SD2 are quite low for all perturbation methods, indicating consistently low structural similarity between original and perturbed KG. RL-RR and RR collectively have the lowest SC2D and SD2 for CSQA, while RL- RR has the lowest SC2D and SD2 for OBQA. Notably, across all perturbation methods and models, RL-RR attains the highest accuracy while also having the lowest KG similarity scores overall. The results of a T-esst (three runs for both models) show that RL-RR achieves statistically significant improvement over its heuristic counterpart, RR. Still, even RR has a fairly high accuracy to KG similarity ratio. This suggests that our KG-augmented models are not using the KG in human-like way, since RL-RR and RR can both achieve high performance despite extensively corrupting the original KG's semantic and structural information.
5.2 ITEM RECOMMENDATION
The KG-augmented recommender systems we consider are KGCN (Wang et 2019b) and Rip- pleNet (Wang et al.) 2018b). We evaluate these models on the Last.FM (Rendle) (012) and MoVieLens-20M (Harper & Konstan 2016) datasets, using the item KG from Wang al. (2019a) As mentioned in Sec. item KGs have been shown to benefit recommender systems in cold start scenarios (Wang et al. 2018b). Therefore, following Wang et al. (018b), we simulate a cold start scenario by using only 20% and 40% of the train set for M and Movie Lens-20M, respectively. Performance is measured using AUC, which is the standard metric for item recommendation (Wang et al. 2019b 2018b). Since the item KG is almost bipartite. the local clustering coefficient of each item in the KG is extremely small, and so SC2D is not meaningful here (Sec. 3). Thus, for item recommendation, we do not report SC2D.

---

Published as a conference paper at ICLR 2021
Table 3: Comparison Perturbation Methods on Last.FM
Last.FM
KGCN
Ripplenet
Method
AUC (1)
ATS ())
SD2 (U)
AUC (t)
ATS ())
SD2 (U)
No KG
50.75
50.75
Original KG
55.99
0.972
1,000
56.23
0.972
1,000
Relation Swapping (RS)
55.98
0.681
2.96E-2
56.23
0.681
2.96E-2
Relation Replacement (RR)
55.98
0.415
0.253
56,22
0.415
0.253
Edge Rewiring (ER)
55.98
0.437
1.85--2
53.74
0.437
1885--2
Edge Deletion (ED)
50.96
0.941
3.37E-3
45.98
0.941
3.37F-3
RL-RR
56.04
0.320
1.30F-3
56.28
0.310
1,20E-3
Table 4: Comparison of Perturbation Methods MoVIeLens-20M
MovieLens-20M
KGCN
Ripplenet
Method
AUC (1)
ATS ())
SD2 (U)
AUC (t)
ATS (L)
SD2 (1)
No KG
91.30
91.30
Original KG
96.62
0.960
1.000
97.46
0.960
1.000
Relation Swapping (RS)
96.62
0.678
6.14E.4
97.46
0.678
6.14E-4
Relation Replacement (RR)
96.50
0.413
7.74F-5
97.45
0.413
7.74F-5
Edge Rewiring (ER)
96.24
0.679
4.44E.4
93.42
0.679
4.44E-4
Edge Deletion (ED)
90.36
0.982
1.02E-4
90.22
0.982
1.02-4
RL-RR
96.53
0.401
2.23E-4
97.25
0.268
2.21E-4
Last.FM Results for Last. are shown in Table 3 For KGCN and RippleNet, we see that RS, RR, and RL-RR achieve about the same AUC as Original KG, with RL-RR slightly outperforming Orig- inal KG. ER performs similarly to Original KG for KGCN, but considerably worse for RippleNet. ED's AUC is on par with No KG's for KGCN and much lower than No KG's for RippleNet.
MovieLens-20M Results for MovieLens-200 are displayed Table 4 For both KGCN and Rip- pleNet, we find that relation- based perturbation methods tend to perform on par with Original KG. Here, ER is the better the two edge-bases perturbation methods, performing about the same as Original KG for KGCN, but noticeably worse for RippleNet. Somehow, for both KGCN and Rip- pleNet, ED achieves even worse AUC than No KG. On the other hand, we see that ED achieves very high ATS, while RS, RR, ER, and RL-RR achieve more modest ATS scores.
Analysis Like in commonsense QA, Tables 3 show that KG-augmented models can perform well even when the KG has been drastically perturbed. Using the T-test with three runs, for almost all perturbation methods, we find a statistically insignificant difference between the perturbed KG's AUC and the original KG's AUC. The perturbed KGs produced by ED have high ATS, while RS, RR, ER, and RL-RR achieve modest ATS scores. However, all perturbation methods have fairly low SD2 (except RR on FM). In particular, across both datasets and models, RL-RR has the highest AUC overall, while also having the lowest KG similarity scores overall. This serves as additional evidence that the model is not using the KG in a human-like like manner, since RL-RR achieves high performance despite significantly perturbing the original KG's semantic and structural information.
5.3 AUXILIARY EXPERIMENTS AND ANALYSIS
Varying Perturbation Level For subset of tet--ddattsee-eetuatttiiooo settings, we measure the performance and ATS of various perturbation methods as a function of the percentage of KG edges perturbed. For MHGRN on CSQA, Fig. La shows that, across all levels of perturbation, RL-RR maintains higher accuracy than No KG. Meanwhile, RS's accuracy reaches No KG's s accuracy at 100% perturbation, and RR's does so at 60% perturbation. In Fig. 4., we see that RL-RR's and RR's ATS drop significantly as the perturbation percentage increases, whereas RS's s ATS remains quite high even at 100% perturbation. For RippleNet on MovieLens-20M, Fig. 4e shows a flat performance curve for all perturbation methods. Meanwhile, for all perturbation methods in Fig. 4d. ATS decreases steadily as perturbation level increases, with RL-RR's ATS dropping most.
These findings support the hypothesis that KG perturbation does not imply performance decrease or KG corruption. Building on the results of previous experiments, in both model-dataset settings, RL-RR largely maintains the model's performance despite also heavily perturbing the KG's seman-
7

---

Published as a conference paper at ICLR 2021
1.2
1.2
310
122
Relaton Replocerenc
FL-13
300
0.50
0.22
0.25
0.5
20
42
50
25
300
0.20
0
25
00
50
30
100
20
03
50
233
0.02
0
23
10
60
30
100
(a) CSQA Acc
(b) CSQA ATS
(c) MovieLens-20MM AUC (d) MovieLens 20M ATS
Figure 4: Varying Perturbation Level. Performance and ATS with respect to perturbation level, for MHGRN
on CSQA and RippleNet MovieLens-20MM 20M. Horizontal axis denotes percentage of perturbed KG edges.
Method
CSQA
OBQA
Method
LM
MovieL.ems 20M
RN
MIIGRN
RN
MIIGRN
KGCN
RippleNet
KGCN
RippleNet
No KG
53.41
53.41
62.00
62,00
No KG
50.75
50.75
91.30
91.30
Orignal KG
56.87
57.21
66.80
68.00
Original KG
55.99
56.23
96.62
97.46
Zero Subgraph Emb.
53.10
53.99
64.80
66.40
Rand. Nghd.
55.91
51.04
96.21
92.11
Rand. Subgraph Embh
52.60
52.48
64.75
65,90
Rand. Ent 7Rel, Fimb.
53.02
54,03
64.45
64,85
Table 6:
Noisy Baselines for Item Recommen- dation. Noisy baseline AUC on Last.FM and Moviel.cns-20M.
Table 5: Noisy Baselines for Commonsense QA. Noisy baseline accuracy on CSQA and OBQA.
tics. Interestingly, for RippleNet on LovieLe performance is completely unaffected by KG perturbation, even though the KG's semantic information is apparently being corrupted.
Noisy Baselines To see if KGs yielded by our perturbation methods capture more than just random noise, we compare them to several noisy baselines. Table gives results for three noisy baselines on commonsense QA: (1) replace subgraph embedding with zero vector, (2) replace subgraph em- bedding with random vector, and (3) replace entity/relation embeddings with random vectors. For CSQA, the noisy baselines perform noticeably worse than both Original KG and RL-RR, while be- ing on par with No KG (Table D. For OBQA, the noisy baselines' perform slightly better than No KG, but considerably worse than Original KG and all of the perturbation methods (Table 2). Table 6 displays results for our noisy baseline in item recommendation, which entails randomizing each entity's 's neighborhood. We find that KGCN performs about the same for this noisy baseline as for Original KG and our best perturbation methods, whereas RippleNet performs much worse (Tables 3 RippleNet may be more sensitive than KGCN to entity neighbor randomization because Rip- pleNet considers directed edges. This is supported by RippleNet's performance dropping when we perturb edge connections (Tables 3 In both tasks, the noisy baselines show that our perturbation methods yield KGs that capture measurably useful information beyond just noise. For KGCN, the unexpected discovery that noisy baselines perform similarly to Original KG suggest that even noisy KGs can contain useful information for KG-augmented models.
Human Evaluation of KG Explanations We conduct a user study to measure the plausibility of KG-augmented models' path-based explanations. For both the original KG and RL-RR perturbed KG, we sample 30 questions from the CSQA and OBQA test sets which were correctly answered by MHGRN. For each question, we retrieve the top-scoring path for each answer choice via MHGRN's path decoder attention. We then ask three human subjects to rate each path for readability and usability, with ratings aggregated via majority voting. Readability (Read) is whether the path makes sense, usability (Use) is whether the path is relevant to the given question-answer pair, and both are measured on [0, 1] scale. We obtain Fleiss' к of O. 0.1891, indicating slight agreement between raters. To illustrate, we provide examples of explanation paths and their consensus ratings. Given the question James chose to not to print the cards, because he wanted to be more personul. What rype of cards did he choose, instead?, the Original KG path is PRINT - [[NNTONY]]+ HANDWRITTEN (Read=1.0; Use=2.0), and the RL-RR path is PRINT - [ESTIES + Usc=0.0). Here, the Original KG path seems plausible. but the RL-RR path does not.
CSQA
OBQA
Method
Read
Use
Read
Use
Orig. KG RL-RR
0.360
0.081
0.357
0.111 0.100
0.353
0.115
0.199
Table 7: Human Evaluation of KG Ex- planations. Human ratings for readability (Read) and usability (Use) of KG explana- tion paths, on a [0, 1] scale.
HANDWRITTEN (Read=0.0;
In Table 7 we see that Original KG and RL-RR got relatively low ratings for both readability and usability. Whereas MHGRN successfully utilizes all KG paths in this user study, humans largely struggle to read or use them. This suggests that KG-augmmented models and humans process KG information quite differently, thus challenging the role of KG paths as plausible explanations. Also, Original KG beats RL-RR in readability and usability overall, signaling RL-RR's 's ability to corrupt the KG. CSQA's lower sensitivity to perturbation can be explained by the fact that CSQA is con-
8

---

Published as a conference paper at ICLR 2021
structed from ConceptNet. Every CSQA question-answer is based on ConceptNet entities/relations,, so a random ConceptNet subgraph is more likely to have semantic overlap with a CSQA question- answer than with OBQA question-answer. Hence, a perturbed ConceptNet subgraph may also be more likely to overlap with CSQA question-answer, which means perturbing the KG might have smaller impact on human judgments of CSQA paths. Note that this result concerns explainability and does not say anything about the model's performance on CSQA and OBQA.
Validation of KG Similarity Metries Using our human evaluation results, we validate our three proposed KG similarity metrics: ATS, SC2D and SD2, We find that the Pearson correlation coeffi- cient between the human evaluation scores in Table 7 and the three KG similarity scores in Tables 12 are 0.845, 0.932 and 0.932, respectively. This indicates high correlation and that our metrics aptly capture perturbed KG's preservation of semantic/structuraal information from its original KG.
Why do perturbed KGs sometimes perform better than the original KG? In our experiments, relation- based perturbations (RS, RR, RL-RRR generally outperform edge-based perturbations (ER, ED). Also, we find that the original KG can contain noisy relation annotations which are sometimes "corrected" by relation-based perturbations. In certain cases, this may result in the perturbed KG achieving slightly higher performance than the original KG (RR and RL-RR for RN-CSQA; RL-RR for FM). Similarly, in our user study, despite all questions being correctly answered by the model, there were some RL-RR explanations that received higher readability/usabiii their original KG counterparts. Although the original KG achieved higher human ratings than the RL-RR KG did overall, both KGs still achieved relatively low ratings with respect to our scales. While our main argument centers on KG-augmented models' flaws, this counterintuitive finding suggests that KGs themselves are flawed too, but in a way that can be systematically corrected.
ratings than
6 RELATED WORK
KG-Augeented Neural Models Although neural models may already capture some semantic
knowledge (Petroni et al. improved performance on various downstream tasks: commonsense QA (Lin et al.
2019; Davison et al. 2019), augmenting them with external KGs has
2019 Shen et al. 2020 Lv et al.] 2020 Musa al. 2019), item recommendation ( (Wang et al. 2019b 2020 Song et al. 2019; Cao et al. (2019), natural language inference (Chen et al.) 2017]] WWang ct al,
2019c), and others (Chen et al. 2019 Kapanipathi et al.). KG-augmented models have also been
designed to explain the model's 's predictions via attention over the KG (Lin et al. 2019 Zhang et al.,
2019 Song et al. 2019: Cao et al. 2019 Gao al. 2019 Ai al. 2018).
Adversarial Perturbation of Graphs Inspired by adversarial learning in computer vision (Bham- al. 2019) and NLP (Zhang et al., 2020), some recent works have addressed adversarial pertur- bation in graph learning (Chen et 2020). Multiple paradigms have been proposed for graph per- turbation, including gradient-based methods (Chen et al. [2018] [Bojchevski & Günnemann [019] Wu et al. 2019). RL-based methods (Ma et al. 20199b Dai et al., (018), and autoencoder- based methods (Chen et al.] (211)). Whereas such works aim to minimally perturb the graph while max- imally impacting the graph's 's performance, our purpose for graph perturbation is to see whether
KG-augmented models' use KGs in a human-like way and provide plausible explanations.
7 CONCLUSION
In this paper, we analyze the effects of strategically perturbed KGs on KG-augmented model pre- dictions. Using four heuristics and RL policy, we show that KGs can be perturbed in way that drastically changes their semantics and structure, while preserving the model's downstream perfor- mance. Apparently, KG-augmmeted models can process KG information align with human priors about KGs, although the nature of this process still requires further investi- gation. Moreover, we conduct user study to demonstrate that both perturbed and unperturbed KGs struggle to facilitate plausible explanations of the model's 's predictions. Note that our proposed KG perturbation methods merely serve as analytical tools and are not intended to directly improve model performance or explainability. Nonetheless, we believe our findings can guide future work on de- signing KG-augmented models that are better in these aspects. Additionally, our results suggest that KG-augmented models be robust to noisy KG data. Even when the KG contains a fairly small amount of signal, these models are somehow able to leverage it. This could be useful in situations where it is impractical to obtain fully clean KG annotations.
a way that does not

---

Published as a conference paper at ICLR 2021
8 ACKNOWLEDGMENTS
This research is supported in part by the Office of the Director of National Intelligence (ODNI, Intelligence Advanced Research Projects Activity (IARPA), via Contract No. 2019-1905 the DARPA MCS program under Contract No. N660011924000 Naval Research, the Defense Advanced Research Projects Agency with award W911NF-19-20271 and NSF SMA 18-29268. We would like to thank all collaborators at the USC INK Research Lab for their constructive feedback on the work.
with the United States Office Of
REFERENCES
Qingyao Ai, Vahid Azizi, Xu Chen, and Yongfeng Zhang. Learning heterogeneous knowledge base embeddings for explainable recommendation. Algorithms,, 11(9):137, 2018.
Siddhant Bhambri, Sumanyu Muku, Avinash Tulasi, and Arun Balaji Buduru. A study of black box adversarial attacks computer vision. arXiv preprint arXiv: 2019.
Alcksandar Bojchevski and Stephan Günnemann. Adversarial attacks on node embeddings via graph poisoning. In International Conference Machine Learning, pp. 695-704. PMLR, 2019.
Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Advances in neural information processing systems, pp. 2787-2795. 2013.
Yixin Cao, Xiang Wang, Xiangnan He, Zikun Hu, and Tat-Seng Chua. Unifying knowledge graph learning and recommendation: Towards better understanding of user preferences. In The world wide web conference, pp. 151-161, 2019.
Daoyuan Chen, Yaliang Li, Min Yang, Hai-Tao Zheng, and Ying Shen. Knowledge- textual entailment with graph attention network. Proceedings of the 28th ACM International Conference on Information and Knowledge Management, 2019.
Jinyin Chen, Yangyang Wu, Xuanheng Xu, Yixian Chen, Haibin Zheng, and Qi Xuan. Fast gradient 2018
attack on network embedding. arXiv preprint arXiv:1809.082
Liang Chen, Jintang Li, Jiaying Peng, Tao Xie, Zengxu Cao, Kun Xu. Xiangnan He, and Zibin Zheng. A survey of adversarial learning on graphs. arXiv preprint arXiv:2003.05730, 2020.
Qian Chen, Xiaodan Zhu, Zhen-Hua Ling, Diana Inkpen, and Si Wei. Neural natural language inference models enhanced with external knowledge. arXiv preprint arXiv:
2017.
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. arXiv preprint arXiv: /00.0330 2018.
Joe Davison, Joshua Feldman, and Alexander M Rush. Commonsense knowledge mining from pretrained models. In Proceedings of the 2019 Conference on Empirical Methods in Natural Lan- guage Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 1173-1178, 2019.
Jacob Devlin, Ming- Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv.1810.04805 2018.
Giorgio Fagiolo. Clustering in complex directed networks. Physical Review E, 76(2):026107, 2007.
Yanlin Feng, Xinyue Chen, Bill Yuchen Lin, Peifeng Wang, Jun Yan, and Xiang Ren. Scal- able multi-hop relational reasoning for knowledgc-aware question answering. arXiv preprint arXiv:2005.00646, 2020.
Jingyue Gao, Xiting Wang, Yasha Wang, and Xing Xie. Explainable recommendation through attentive multi-view learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp. 3622-3629, 2019.
F. Maxwell Harper and Joseph A. Konstan. The movielens datasets: History and context. ACM Trans. Interact. Intell. Syst. 5(4): 2016.
10

---

Published as a conference paper at ICLR 2021
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
Pavan Kapanipathi, Veronika Thost, Siva Sankalp Patel, Spencer Whitehead, Ibrahim Abdelaziz, Avinash Balakrishnan, Maria Chang, Kshitij P Fadnis, R Chulaka Gunasekara, Bassem Makni, et al. Infusing knowledge into the textual entailment task using graph convolutional networks.
Xiang Li, Aynaz. Taheri, Lifu Tu, and Kevin Gimpel. Commonsense knowledge base completion. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1445-1455, Berlin, Germany, August 2016. Association for Computational Linguistics, doi: 10.18653/v I/P16- 1137. URL httph::///// /tt:://wwww... http://wwwwwwwwbb.././...cco wwwweb. org httpg//nthlogy//// P16-1137
Bill Yuchen Lin, Xinyue Chen, Jamin Chen, and Xiang Ren. Kagnet: Knowledge-aware graph networks for commonsense reasoning. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 2822-28322 2019.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint 19X7v:1907.1160 11692, 2019.
Shangwen Lv, Daya Guo, Jingjing Xu, Duyu Tang, Nan Duan, Ming Gong, Linjun Shou, Daxin Jiang, Guihong Cao, and Songlin Hu. Graph-based reasoning heterogeneous external knowl- edge for commonsense question answering. In AAAI, 2020.
Kaixin Ma, Jonathan Francis, Quanyang Lu, Eric Nyberg, and Alessandro Oltramari. Towards generalizable neuro-symbolic systems for commonsense question answering. arXiv preprint 1XXi::9110.10087. 2019a.
Yao Ma, Suhang Wang. Tyler Derr, Lingfei Wu, and Jiliang Tang. Attacking graph convolutional networks via rewiring. arXiv preprint arXiv:1906.037550 2019b.
Todor Mihaylov, Peter Clark, Tushar Khot, and Ashish Sabharwal. Can suit of armor con- duct electricity? a new dataset for open book question answering. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 2381-2391, Brussels, Belgium, October-Novemble 2018. Association for Computational Linguistics. doi: 10. 1/D188 1260. URL httpp:: www.acll...coooccoo..wwm..wc..cw web. web.org//rrthoooog/////
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 51 (777740))5595553 2015.
Ryan Musa, Xiaoyan Wang, Achille Fokoue. Nicholas Mattei, Maria Chang, Pavan Kapanipathi, Bassem Makni, Kartik Talamadupula, and Michael Witbrock. Answering science exam questions using query reformulation with background knowledge. In Automated Knowledge Base Construc- tion (AKBC), 2019. URL httt:tttt/::/:nnnnm htt.aaaeeeee..eettooooooooddaadd
Pekka Onnela, Jari Saramäki, János Kertész, and Kimmo Kaski. Intensity and coherence of motifs in weighted complex networks. Physical Review E, 71(6):05103,, 2005.
Fabio Petroni, Tim Rocktäschel, Patrick Lewis, Anton Bakhtin, Yuxiang Wu, Alexander Miller, and Sebastian Riedel. Language models as knowledge bases? arXiv preprint arXiv: 1et9:099900000 01066, 2019.
Steffen Rendle. Factorization machines with libfm. ACM Transactions on Intelligent Systems and Technology, 3(3):57:1-57:22) 2012.
Adam Santoro, David Raposo, David G Barrett, Mateusz Malinowski. Razvan Pascanu, Peter Battaglia, and Timothy Lillicrap. A simple neural network module for relational reasoning. In Advances in neural information processing systems, pp. 4967-4976, 2017.
11

---

Published as a conference paper at ICLR 2021
Jari Saramäki, Mikko Kivelä, Jukka-Pekka Onnela, Kimmo Kaski, and Janos Kertesz. General- izations of the clustering coefficient to weighted complex networks. Physical Review E, 75(2): 027105, 2007.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European Semantic Web Conference, pp. 593-607. Springer, 2018.
Tao Shen, Yi Mao, Pengcheng He, Guodong Long, Adam Trischler, and Weizhu Chen. Exploiting structured knowledge in text via graph-guide representation learning. ArXiv, abs/2004.14224, 2020.
Weiping Song, Zhijian Duan, Ziqing Yang, Hao Zhu, Ming Zhang, and Jian Tang. Ex- plainable knowledge graph-based recommendation via deep reinforcement learning. ArXiv, abs/1906.09506, 2019.
Robyn Speer, Joshua Chin, and Catherine Havasi. Conceptnet 5.5: An open multilingual graph of general knowledge. arXiv preprint arXiv: 111.1:161,.03375, 2016.
Yiwei Sun, Suhang Wang, Xianfeng Tang, Tsung- Yu Hsieh, and Vasant Honavar. Adversarial attacks on graph neural networks via node injections: A hierarchical reinforcement learning approach. In Proceedings of The Web Conference 2020, pp. 673-683, 2020.
Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. Commonsensega: A question answering challenge targeting commonsense knowledge. arXiv preprint 1rXiv:/811.0099: 2018.
Hongwei Wang, Fuzheng Zhang, Min Hou, Xing Xie, Minyi Guo, and Qi Liu. Shine: Signed heterogeneous information network embedding for sentiment link prediction. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, pp. 592-600, 2018a.
Hongwei Wang, Fuzheng Zhang, Jialin Wang, Miao Zhao, Wenjie Li, Xing Xie, and Minyi Guo. Ripplenet: Propagating preferences the knowledge graph for recommender systems. In Proceedings of the 27th ACM International Conference on Information and Knowledge Manage- ment, pp. 417-426, 2018b.
Hongwei Wang, Fuzheng Zhang, Mengdi Zhang, Jure Leskovee, Miao Zhao, Wenjie Li, and Zhongyuan Wang. Knowledge-awan graph neural networks with label smoothness regularization for recommender systems. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 968 977, 2019a.
Hongwei Wang. Miao Zhao, Xing Xie, Wenjie Li, and Minyi Guo. Knowledge graph convolutional networks for recommender systems. In The world wide web conference, pp. 3307-3313, 2019b.
Xiang Wang, Yao-Kun Xu, Xiangnan He, Yixin Cao, Meng Wang, and Tat-Seng Chua. Reinforced negative sampling over knowledge graph for recommendation. Proceedings of The Web Confer- ence 2020, 2020.
Xiaoyan Wang, Pavan Kapanipathi, Ryan Musa, Mo Yu, Kartik Talamadupula. Ibrahim Abdelaziz, Maria Chang, Achille Fokoue, Bassem Makni, Nicholas Mattei, et al. Improving natural language inference using external knowledge in the science questions domain. Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 720877087707 7215,725,,222 2019c.
Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. Adversarial examples on graph data: Deep insights into attack and defense. arXiv preprint arXiv: 1903.01610, 2019.
Bishan Yang. Wen tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases, 2015.
Wei Emma Zhang, Quan Z Sheng, Ahoud Alhazmi, and Chenliang Li. Adversarial attacks on deap-len models in natural language processing: A survey. ACM Transactions on Intelligent Systems and Technology (TIST), 11(3):1-41, 2020.
12

---

Published as a conference paper at ICLR 2021
Wen Zhang, Bibek Paudel, Wei Zhang, Abraham Bernstein, and Huajun Chen. Interaction em- beddings for prediction and explanation in knowledge graphs. Proceedings of the Twelfth ACM International Conference Web Search and Data Mining. 2019.
W. Zheng, J. Yu, L. Zou, and H. Cheng. Question answering over knowledge graphs: Question understanding via template decomposition. Proc. VLDB Endow, 11:1373-1386, 2018.
13


Reviews:
[{"review_id": "tF6wKc1gkld", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper shows that knowledge graph augmented question answering and recommendation system models are so graph structure/content change invariant that by using a simple heuristic or more sophisticated reinforcement learning-based approach, we can change the knowledge graphs without significant change in the model performance. This phenomenon leads to corrupt non-sense explanations for such models' decisions/outputs.\n\nStrengths:\n- The paper is very well-written and crystal clear.\n- The idea is very interesting and novel.\n- The evaluations are relatively strong.\n\nWeak points:\n- I suggest the authors make their arguments about the invalidity of model explanations more clear by providing some explanation samples.\n- I am wondering what is the source of a more significant gap in the VALIDITY of explanations for original kg vs RL-PR in OBQA compared to CSQA. I am suggesting the authors provide an explanation for this difference.\n\nOverall, a study on the behavior of knowledge graph augmented models when they encounter the perturbed graphs is an interesting idea. The paper is also very well-written. I'd like to see the revised manuscript being accepted by the conference. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "V2S7twGSoM", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper provides a number of adversarial attacks on hybrid neural-symbolic systems. The systems are recommender and QA systems which use an underlying knowledge-graph (KG) such as ConceptNet. Previous work has suggested that the KGs are important for good performance, and moreover that the use of KGs lends the system a degree of interpretability. The attacks are successful - maintaining performance whilst seriously degrading the KG - throwing doubt on these claims.\n\nTwo main approaches to attacking the systems are followed: a simple heuristic method in which labels in the KG are modified randomly, and a more sophisticated method in which deep reinforcement learning is used to learn an optimal policy to change the KG whilst maintaining good performance on the task.\n\nOverall I have a lot of sympathy for the motivation of this paper. There is increasing evidence that the attempted use of symbolic methods in hybrid systems, and in particular the use of symbolic methods to provide explanations, is just picking up on incidental properties of the data and exploiting the power of the deep network in ways unrelated to the symbolic representations. This paper provides further compelling evidence.\n\nHowever, the paper is currently an extremely frustrating read, and it took me a number of attempts to get through the paper to write this review. Part of the problem is that the authors have tried to cram in too much material. I would have preferred to have seen fewer experiments described, but in more detail, with the remainder briefly mentioned in a paragraph or two, or perhaps in an appendix (if that's allowed for ICLR).\n\nThe other problem is that the presentation in the paper is poor. Part of that is down to the non-native English in parts (which is not the fault of the authors), but part of it is also just down to sloppiness in the presentation.\n\nMore detailed comments\n--\n\nA KG is denoted as G = (E, R, T ), where E and R are the entity set\nand relation set respectively - this is a little confusing since T is\nalso the set of relations (tuples over E). R is the set of relation\n*labels*?\n\nFinally, both c and k are concatenated for calculating the\n plausibility score - [presuambly the concatenation is then put\n through an MLP?]\n\nIn both graph encoders, the subgraph G(q,a) together with the\naggregation weights - [neither of the descriptions mention aggregation\nweights]\n\nwhile the task is to predict the unobserved interaction (yuv = 0). -\n[does the zero here mean that the interaction is unobserved, or that\nthe user has not engaged with the item? (or both?)]\n\nwhere the aggregation weights are personalized for u - [you need to\ndefine how the aggregation works]\n\nWe randomly choose two triples (edges) in the KG and swap their\nrelations. - [it would be good to see some actual examples here from\none of the applications/KGs.]\n\nwhere sG(·) is a KG scoring function trained on G.  - [is this defined\nanywhere?]\n\nThe font in table 1 is really small. If you get more room in a final\nversion please turn this into two tables.\n\nin-house test accuracy - what's an \"in-house\" accuracy?\n\nWe then compute the relation\nspecific clustering coefficient vector c^r - do you define this anywhere?\n\nOpenBookQA (OBQA) - do you give a reference?\n\nWe randomly select 10 questions - this seems like a small sample on\nwhich to peform the human evaluation. This evaluation would be more\npersuasive with a larger sample (even 20 or 30).\n\nTypos etc. (not exhaustive)\n--\n\ndespite a deceptive symbolic structure - [I'm not sure that\n\"deceptive\" is the right word here (and lots of places elsewhere),\njust something like \"incorrect\" may be better.]\n\n that KG -> the KG\n\nThe preliminary results indicate that KG can be easily manipulated and\nlost its benefit -> lose\n\nIt brings more worrisome scenario - [rephrase]\n\nwithout noticeable performance drop -> without a noticeable\nperformance drop\n\nIn specific -> More specifically\n\ne.g., commonsense question answering (QA) and recommender system, ->\ni.e.\n\naggregating its neighbors’ embedding -> aggregating its neighbors’ embeddings\n\nThis heuristic changes the semantic -> semantics\n\nThis heuristic also does not perturb KG’s structure but its semantic\n-> This heuristic also does not perturb KG’s structure but its\nsemantics\n\non both of commonsense QA and recommendation system tasks -> on both\n commonsense QA and recommendation system tasks\n\nsince one\nof our goal -> goals\n\nhave captured the information of KG. -> the KG\n\nsequentially to LSTM -> sequentially to the LSTM\n\nEvaluating the KG on downstream task -> Evaluating the KG on a\ndownstream task\n\nRelation Swapping(RS) -> Relation Swapping (RS)\n\nbut keep the relation distribution -> keeps\n\nWe also leverage the validity scores given by human -> humans\n\nranging from gradient based(Chen - [space]\n\nAutoEncoder based(Chen - [space]\n\nwhich can lead to corrupt explanations -> which can lead to incorrect\nexplanations\n\nour RL-RR method always yield -> yields\n\nbetween entities instead of the semantic -> semantics\n\nthat investigate into the problem -> that investigate the problem\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "NNVVqZl35K7", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed to learn a RL model to modified the KG. They showed that their model can successfully deceive the KG-augmented models with most relations replaced, compared to heuristic-based strategies. \n\nI am not convinced by the motivation of this paper. The authors claimed that their model can learn to modified a KB so that a KG-augmented model can yield similar performance as before. This is under the assumption that similar performance in predicting the correct answer (e.g. accuracy) will lead to similar quality of explanation. This assumption does not always hold. If the authors really care about explanation, you should experiment with the explanation model that used KGs. \n\nThere's also a discrepancy between the authors' motivation and their evaluation. If the authors assume KG is really important in generating explanations and can be easily fooled by their framework, they should also evaluated on KG only tasks, e.g. KBQA, KBC etc, besides these KG-augmented models.\n\nSome detailed questions:\n1. Many of the downstream models that the authors evaluated on are based on GCN approaches. GCN is good at filtering irrelevant information from their neighbors. How did you make sure that embeddings from the replaced relations are not simply filtered out at the aggregation steps?\n2. I would like to argue the LSTM is not appropriate here. LSTM is designed for \"ordered\" input. Making tricks to adapt it to un-ordered inputs is not a very good option. In each update step, the LSTM basically learns a gate variable \\sigma on the input. Can you do something like: G += \\sum \\alpha \\dot g, where g is the embedding of your single updates?\n3. In some cases, with replaced relations, the model can have better performance as the original model w/ KG (e.g. OBQA RN Acc in Table 1). Do you have an intuition why that could happen?", "extra_scores": {}, "extra_text": {}}, {"review_id": "GTYGkGa3CNI", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents an interesting finding that some of the existing KG-augmented models, such as those for QA and item recommendation, may not actually capture or leverage the semantics in KGs, and their performance improvement cannot be attributed to the usage of additional knowledge. I think this finding is of some significance.\n\nPros: \n\n1) The paper presents four heuristic methods and an RL-based method for KG perturbation. It obtains some interesting and noteworthy findings based on the experimental results in terms of QA and recommender systems.\n\nCons:\n\n1) In my opinion, perturbing KGs by randomly or heuristically changing existing edges is not well-motivated. Although it supports the experimental study in this paper and reveals several interesting findings, it has very little practical significance, because the perturbed KG would inevitably contain many invalid and incorrect facts without positive effects for downstream applications. Hence, the technical contribution of the proposed heuristic strategies and RL model for KG perturbation is not significant.\n\n2) The analysis for experimental results is somewhat superficial. It fails to provide deep insights into why some models can still work with the perturbed KG. The authors should provide more analysis to explain the experimental results that are against common sense. For example, an experiment conclusion says that \"it is the (false) connection between entities instead of the semantic stored in the KG that leads to the improvement over non-KG baseline.\" Why? I think this is an interesting and noteworthy finding, but no in-depth analysis is given. Besides, I also have a minor question, i.e., how does the edge deletion method perturb all the triples (100%) in a KG? How many triples are left after edge deletion?\n\nSome typos: \n\n1) these false connection ->  these false connections\n2) Relation Swapping(RS) -> Relation Swapping (RS)\n\nAnyway, the paper presents a noteworthy finding, which calls for further investigation into what information from the KGs is actually captured to improve the neural-symbolic models. So, I would like to recommend a weak acceptance of this paper. \n\n--- after rebuttal ---\nThank the authors for their response which addressed my concerns. Based on the response, the revision, and other reviews, I would like to keep my score unchanged at 6.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper's main message is that some existing NLP techniques that claim to improve performance by the use of a knowledge graph may not achieve this improved performance because of the knowledge graph or at least the explanation given may be questionable.  This is thought provoking and it will incite the community to think more carefully about the real factors of improved performance.  The initial version of the paper was not well written, but the authors improved the writing significantly.  The paper includes a thorough empirical evaluation to support the main message.  I have read the paper and I believe that this work will be of interest to a diverse audience.
Decision: Accept (Poster)