Year: 2021

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.

heading: 1 INTRODUCTION
text: Recently, neural reasoning over knowledge graphs (KGs) has emerged as a popular paradigm in machine learning and natural language processing (NLP). KG-augmented models have improved performance on a 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., 2020; Lv et al., 2020; Talmor et al., 2018); for item recommendation, the KG mitigates data sparsity and cold start issues (Wang et al., 2018b; 2019a;b; 2018a). Furthermore, by using attention over the KG, such models aim to explain which KG information was most relevant for making a given prediction (Lin et al., 2019; Feng et al., 2020; Wang et al., 2018b; 2019b; Cao et al., 2019; Gao et al., 2019). Nonetheless, the process in which KG-augmented models reason about KG information is 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 et al., 2019; Feng et al., 2020; Gao et al., 2019; Song et al., 2019).
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 semantics and structure have been perturbed to hinder human comprehension. To perturb the KG, we propose four perturbation heuristics and a 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 to no effect on performance. This raises doubts about KG-augmented models’ use of KGs and the plausibility of their explanations.

heading: 2 PROBLEM SETTING
text: 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: //github.com/INK-USC/deceive-KG-models. †Equal contribution.
KG and perturbed KG. If original-perturbed KG similarity is low, then a human-like KG-augmented model should achieve worse performance with the perturbed KG than with the original KG. Furthermore, we evaluate the plausibility of KG-augmented models’ explanations when using original and perturbed KGs, by asking humans to rate these explanations’ readability and usability.
Notation Let Fθ be an KGaugmented model, and let (Xtrain, Xdev, Xtest) be a dataset for some downstream task. We denote a KG as G = (E ,R, T ), where E is the set of entities (nodes), R is the set of relation types, and T = {(e1, r, e2) | e1, e2 ∈ E , r ∈ R} is the set of facts (edges) composed from existing entities and relations (Zheng et al., 2018). Let G ′ = (E ,R′, T ′ ) be the KG obtained after perturbing G, where R ′ ⊆ R and T ′ 6= T . Let f(G,G ′ ) be a function that measures similarity between G and G ′ . Let g(G) be the downstream performance when evaluating Fθ on Xtest and G. Also, let ⊕ denote the concatenation operation, and let
NL(e) denote the set of L-hop neighbors for entity e ∈ E .
High-Level Procedure First, we train Fθ on Xtrain and G, then evaluate Fθ on Xtest and G to get the original performance g(G). Second, we freeze Fθ, then perturb G to obtain G ′ . Third, we evaluate Fθ on Xtest and G ′ to get the perturbed performance g(G ′ ). Finally, we measure g(G) − g(G′) and f(G,G ′ ) to assess how human-like Fθ’s reasoning process is. This procedure is illustrated in Fig. 1. In this paper, we consider two downstream tasks: commonsense QA and item recommendation.
Commonsense QA Given a question x and a set of k possible answers A = {y1, ..., yk}, the task is to predict a compatibility score for each (x, y) pair, such that the highest score is predicted for the correct answer. In commonsense QA, the questions are designed to require commonsense knowledge which is typically unstated in natural language, but more likely to be found in KGs (Talmor et al., 2018). Let F textφ be a text encoder (Devlin et al., 2018), F graph ψ be a graph encoder, and F cls ξ be an MLP classifier, where φ, ψ, ξ ⊂ θ. Let G(x,y) denote a subgraph of G consisting of entities mentioned in text sequence x ⊕ y, plus their corresponding edges. We start by computing a text embedding htext = F textφ (x⊕ y) and a graph embedding hgraph = F graph φ (G(x,y)). After that, we compute the score for (x, y) as S(x,y) = F clsξ (htext ⊕ hgraph). Finally, we select the highest scoring answer: ypred = argmaxy∈A S(x,y). KG-augmented commonsense QA models vary primarily in their design of Fgraphψ . In particular, path-based models compute the graph embedding by using attention to selectively aggregate paths in the subgraph. The attention scores can help explain which paths the model focused on most for a given prediction (Lin et al., 2019; Feng et al., 2020; Santoro et al., 2017).
Item Recommendation We consider a set of users U = {u1, u2, ..., um}, a set of items V = {v1, v2, ..., vn}, and a user-item interaction matrix Y ∈ Rm×n with entries yuv. If user u has been observed to engage with item v, then yuv = 1; otherwise, yuv = 0. Additionally, we consider a KG G, in which R is the set of relation types in G. In G, nodes are items v ∈ V, and edges are facts of the form (v, r, v′), where r ∈ R is a relation. For the zero entries in Y (i.e., yuv = 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 v. We represent each user u, item v, and relation r as embeddings u, v, 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 u 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).

heading: 3 KG SIMILARITY METRICS
text: To measure how much the perturbed KG has deviated from the original KG, we propose several metrics 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 sG(e1, r, e2) measures how likely edge (e1, r, e2) is to exist in G. Also, assume sG has been pre-trained on G for link prediction. Then, ATS is defined as fATS(G,G ′ ) = 1
|T ′ | ∑ (e1,r,e2)∈T
′ sG(e1, r, e2) ∈ [0, 1], which denotes the mean sG score across all edges in G′. Intuitively, if a high percentage of edges in G′ are also likely to exist in G (i.e., high ATS), then we say that G′ and G have high semantic similarity. sG is task-specific, as KGs from different tasks may differ greatly in semantics. For commonsense QA, we use the sG from Li et al. (2016); 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 fATS(G,G) may not equal 1, since sG may not perfectly generalize to KGs beyond those it was trained on.
Similarity in Clustering Coefficient Distribution (SC2D) SC2D measures structural similarity between two KGs and is derived from the local clustering coefficient (Saramäki et al., 2007; Onnela et al., 2005; Fagiolo, 2007). For a given entity in G (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 neighbors cluster around it). For entity ei ∈ E , the local clustering coefficient is defined as ci = 2Tri(ei)/(deg(ei)(deg(ei) − 1)), where Tri(ei) is the number of triangles through ei, and deg(ei) is the degree of ei. For each relation r ∈ R, let Gr be the subgraph of G consisting of all edges in T with r . That is, Gr = (E , r, T ′ ), where T ′ = {(e, r, e′) | e, e′ ∈E}. Let cr denote the |E|-dimensional clustering coefficient vector for Gr, where the ith element of cr is ci. Then, the mean clustering coefficient vectors for G and G′ are co = 1|R| ∑ r∈R c r and cp = 1|R′| ∑ r∈R′ c
r, respectively. SC2D is defined as fSC2D(G,G
′ ) = 1− ‖co−cp‖2‖co−cp‖2+1 ∈ [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 dr denote the |E|-dimensional degree vector for Gr, where the ith element of dr is deg(ei). Then, the mean degree vectors for G and G′ are do = 1|R| ∑ r∈R d r and dp = 1|R′| ∑ r∈R′ d
r, respectively. SD2 is defined as fSD2(G,G
′ ) = 1− ‖do−dp‖2‖do−dp‖2+1 ∈ [0, 1], with higher value indicating higher similarity.

heading: 4 METHODS FOR TARGETED KG PERTURBATION
text: 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 a KG’s semantics can be perturbed via its relation types, its structure can be perturbed via its edge connections. Therefore, we design five methods — four heuristic, one RL — for perturbing KG relation types, edge connections, or both (Fig. 2).

heading: 4.1 HEURISTIC-BASED KG PERTURBATION
text: 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 (e1, r1, e2) ∈ T , then replaces r1 with another relation r2 = argminr∈R sG(e1, r, e2). Edge Rewiring (ER) randomly chooses an edge (e1, r, e2) ∈ T , then replaces e2 with another entity e3 ∈ E \N1(e1). Edge Deletion (ED) randomly chooses an edge (e1, r, e2) ∈ T and deletes it. For ED, perturbing all edges means deleting all but 10 edges.

heading: 4.2 RL-BASED KG PERTURBATION
text: 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, fATS(G,G ′ ), is minimized, while downstream performance, g(G ′ ), is maximized. Specifically, the RL agent is trained to perturb G via relation replacement, so we call our algorithm RL-RR. Because the agent is limited to applying N = |T | perturbations to G, our RL problem is framed as a finite horizon Markov decision process. In the rest of this section, we define the actions, states, and reward in our RL problem, then explain how RL-RR is implemented.
Actions The action space consists of all possible relation replacements in G, i.e., replacing (e1, r, e2) ∈ T with (e1, r′, e2). Since having such a large action space poses computational issues, we decouple each action into a sequence of three subactions and operate instead in this smaller subaction space. Hence, a perturbation action at time step t would be at = (a(0)t , a (1) t , a (2) t ). Namely, a (0) t is sampling entity e1 ∈ E; a (1) t is selecting edge (e1, r, e2) ∈ T ; and a (2) t is selecting relation r′ ∈ R to replace r in (e1, r, e2). To make the policy choose low-ATS perturbations, we further restrict the a(2)t subaction space to be the K subactions resulting in the lowest ATS. Note that each a (i) t is represented by its corresponding pre-trained TransE (Bordes et al., 2013) entity, relation, or edge embedding in G. Since these TransE embeddings are not updated by the perturbation policy, we use a(i)t to refer to both the subaction and subaction embedding. Meanwhile, at 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 and state embedding. The state at t is the actual KG after t perturbation steps and is denoted as Gt. The state embedding at t is a vector representation of Gt and is denoted as st. To match at, we also decouple st into substate embeddings: st = (s(0)t , s (1) t , s (2) t ).
Reward The reward function pushes the policy to maximize downstream performance. For commonsense 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.

heading: 4.2.1 DQN ARCHITECTURE AND TRAINING
text: As described above, RL-RR is modeled as an action-subaction hierarchy. At the action (top) level, for t, the policy selects an action at given state st, then performs at on Gt to obtain Gt+1. At the subaction (bottom) level, for index i ∈ [0, 1, 2] within time step t, the policy selects a subaction a (i+1) t given s (i) t and, if any, previous subactions.
At t, the policy takes as input the substate embedding s(0)t . One approach for computing s (0) t would be to directly encode Gt with a graph encoder Fgraph, such that s(0)t = Fgraph(Gt) (Dai et al., 2018; Sun et al., 2020; Ma et al., 2019b). However, since we aim to assess graph encoders’ ability to capture KG information, it would not make sense to use a 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
this means s(i)t only implicitly captures KG state information via a (i−1) t , since the choice of each subaction is constrained precisely by which entities, relations, or edges are available in Gt.
To train RL-RR, we use the DQN algorithm (Mnih et al., 2015). Abstractly, the goal of DQN is to learn a Q-function Q(st, at), which outputs the expected reward for taking action at in state st. In our implementation, Q(st, at) is decomposed into a sequential pair of sub-Q-functions: Q1(a (1) t |s (0) t , a (0) t ) = 〈MLP(a (1) t ),MLP(h (0) t )〉 and Q2(a (2) t |s (1) t , a (0) t , a (1) t ) = 〈MLP(a (2) t ),MLP(h (1) t )〉. MLP denotes the vector representation computed by a multi-layer perceptron, while h(0)t and h (1) t denote the respective LSTM encodings of (s(0)t , a (0) t ) and (s (1) t , [a (0) t ⊕ a (1) t ]).
Figure 3: DQN Architecture for RL-RR
Fig. 3 depicts the perturbation procedure at t. First, we either initialize s(0)t with a trained embedding weight vector if t= 0, or set it to s(2)t−1 otherwise. Second, we uniformly sample a(0)t , which is encoded as h(0)t = LSTMCell1(s (0) t , a (0) t ). LSTMCell1 also updates s(0)t to s(1)t . Third, we compute Q1(a(1)t |s (0) t , a (0) t ), which takes h(0)t as input and outputs a (1) t . Fourth, we encode a (1) t as h (1) t = LSTMCell2(s (1) t , [a (0) t ⊕ a (1) t ]). LSTMCell2 also updates s (1) t to s (2) t . Fifth, we compute Q2(a (2) t |s (1) t , a
(0) t , a (1) t ), which takes h (1) t as input and outputs a (2) t . Note that a(1)t and a (2) t are selected -greedily during training and greedily during evaluation. Finally, using at = (a(0)t , a (1) t , a (2) t ), we perturb Gt to get Gt+1.
Ideally, for each t, we would evaluate Gt+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 to generalize well, state embeddings (st−T+1, ... , st−1, st) should not correlate with the order of actions (at−T+1, ... , at−1, at). 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.

heading: 5 EXPERIMENTS
text: In this section, we test KG-augmented models on their ability to maintain performance and explainability when the KG has been extensively perturbed. As explained in Sec. 2 and Fig. 1, the model is first trained on a given dataset using the 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 a subset of model-dataset-perturbation configurations, we also measure performance as a function of the number of edges perturbed. In addition, we conduct a user study where humans are asked to rate original and perturbed KGs, with respect to readability and usability for solving downstream tasks.

heading: 5.1 COMMONSENSE QA
text: 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 models (Devlin et al., 2018; Liu et al., 2019) and a number of KG-augmented models (Lin et al., 2019; Ma et al., 2019a; Wang et al., 2019c; Schlichtkrull et al., 2018) on this task. For both RN and MHGRN, we use a BERT-Base (Devlin et al., 2018) text encoder. We evaluate on the CommonsenseQA (CSQA) (Talmor et al., 2018) and OpenBookQA (OBQA) (Mihaylov et al., 2018) datasets, using ConceptNet (Speer et al., 2016) as the KG. Performance is measured using accuracy (Acc), which is the standard metric for commonsense QA (Lin et al., 2019; Feng et al., 2020).
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 2. 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 1-2 demonstrate that perturbing a KG does not necessarily imply decreased performance, nor does it 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 to 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 RLRR 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-test (three runs for both models) show that RL-RR achieves a 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 a human-like way, since RL-RR and RR can both achieve high performance despite extensively corrupting the original KG’s semantic and structural information.

heading: 5.2 ITEM RECOMMENDATION
text: The KG-augmented recommender systems we consider are KGCN (Wang et al., 2019b) and RippleNet (Wang et al., 2018b). We evaluate these models on the Last.FM (Rendle, 2012) and MovieLens-20M (Harper & Konstan, 2016) datasets, using the item KG from Wang et al. (2019a). As mentioned in Sec. 1, item KGs have been shown to benefit recommender systems in cold start scenarios (Wang et al., 2018b). Therefore, following Wang et al. (2018b), we simulate a cold start scenario by using only 20% and 40% of the train set for Last.FM 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.
Last.FM Results for Last.FM 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 Original 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-20M are displayed in Table 4. For both KGCN and RippleNet, we find that relation-based perturbation methods tend to perform on par with Original KG. Here, ER is the better of the two edge-based perturbation methods, performing about the same as Original KG for KGCN, but noticeably worse for RippleNet. Somehow, for both KGCN and RippleNet, 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-4 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 Last.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 manner, since RL-RR achieves high performance despite significantly perturbing the original KG’s semantic and structural information.

heading: 5.3 AUXILIARY EXPERIMENTS AND ANALYSIS
text: Varying Perturbation Level For a subset of model-dataset-perturbation 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. 4a shows that, across all levels of perturbation, RL-RR maintains higher accuracy than No KG. Meanwhile, RS’s accuracy reaches No KG’s accuracy at 100% perturbation, and RR’s does so at 60% perturbation. In Fig. 4b, we see that RL-RR’s and RR’s ATS drop significantly as the perturbation percentage increases, whereas RS’s ATS remains quite high even at 100% perturbation. For RippleNet on MovieLens-20M, Fig. 4c 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-
Method CSQA OBQA
RN MHGRN RN MHGRN
No KG 53.41 53.41 62.00 62.00 Orignal KG 56.87 57.21 66.80 68.00 Zero Subgraph Emb. 53.10 53.99 64.80 66.40 Rand. Subgraph Emb. 52.60 52.48 64.75 65.90 Rand. Ent./Rel. Emb. 53.02 54.03 64.45 64.85
Table 5: Noisy Baselines for Commonsense QA. Noisy baseline accuracy on CSQA and OBQA.
Method Last.FM MovieLens-20M
KGCN RippleNet KGCN RippleNet
No KG 50.75 50.75 91.30 91.30 Original KG 55.99 56.23 96.62 97.46 Rand. Ngbd. 55.91 51.04 96.21 92.11
Table 6: Noisy Baselines for Item Recommendation. Noisy baseline AUC on Last.FM and MovieLens-20M.
tics. Interestingly, for RippleNet on MovieLens-20M, 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 5 gives results for three noisy baselines on commonsense QA: (1) replace subgraph embedding with zero vector, (2) replace subgraph embedding 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 being on par with No KG (Table 1). 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 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-4). RippleNet may be more sensitive than KGCN to entity neighbor randomization because RippleNet considers directed edges. This is supported by RippleNet’s performance dropping when we perturb edge connections (Tables 3-4). 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 a [0, 1] scale. We obtain a Fleiss’ κ of 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 personal. What type of cards did he choose, instead?, the Original KG path is PRINT —[ANTONYM]→ HANDWRITTEN (Read=1.0; Use=2.0), and the RL-RR path is PRINT — [NOTDESIRES]→ HANDWRITTEN (Read=0.0; Use=0.0). Here, the Original KG path seems plausible, but the RL-RR path does not.
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-augmented 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 ability to corrupt the KG. CSQA’s lower sensitivity to perturbation can be explained by the fact that CSQA is con-
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 questionanswer than with an OBQA question-answer. Hence, a perturbed ConceptNet subgraph may also be more likely to overlap with a CSQA question-answer, which means perturbing the KG might have a 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 Metrics Using our human evaluation results, we validate our three proposed KG similarity metrics: ATS, SC2D and SD2. We find that the Pearson correlation coefficient between the human evaluation scores in Table 7 and the three KG similarity scores in Tables 1-2 are 0.845, 0.932 and 0.932, respectively. This indicates high correlation and that our metrics aptly capture a perturbed KG’s preservation of semantic/structural 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-RR) 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 Last.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/usability ratings than 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.

heading: 6 RELATED WORK
text: KG-Augmented Neural Models Although neural models may already capture some semantic knowledge (Petroni et al., 2019; Davison et al., 2019), augmenting them with external KGs has improved performance on various downstream tasks: commonsense QA (Lin et al., 2019; Shen et al., 2020; Lv et al., 2020; Musa et al., 2019), item recommendation (Wang et al., 2019b; 2020; Song et al., 2019; Cao et al., 2019), natural language inference (Chen et al., 2017; Wang et al., 2019c), and others (Chen et al., 2019; Kapanipathi et al.). KG-augmented models have also been designed to explain the model’s predictions via attention over the KG (Lin et al., 2019; Zhang et al., 2019; Song et al., 2019; Cao et al., 2019; Gao et al., 2019; Ai et al., 2018).
Adversarial Perturbation of Graphs Inspired by adversarial learning in computer vision (Bhambri et al., 2019) and NLP (Zhang et al., 2020), some recent works have addressed adversarial perturbation in graph learning (Chen et al., 2020). Multiple paradigms have been proposed for graph perturbation, including gradient-based methods (Chen et al., 2018; Bojchevski & Günnemann, 2019; Wu et al., 2019), RL-based methods (Ma et al., 2019b; Dai et al., 2018), and autoencoder-based methods (Chen et al., 2018). Whereas such works aim to minimally perturb the graph while maximally impacting the graph’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.

heading: 7 CONCLUSION
text: In this paper, we analyze the effects of strategically perturbed KGs on KG-augmented model predictions. Using four heuristics and a RL policy, we show that KGs can be perturbed in way that drastically changes their semantics and structure, while preserving the model’s downstream performance. Apparently, KG-augmented models can process KG information in a way that does not align with human priors about KGs, although the nature of this process still requires further investigation. Moreover, we conduct a user study to demonstrate that both perturbed and unperturbed KGs struggle to facilitate plausible explanations of the model’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 designing KG-augmented models that are better in these aspects. Additionally, our results suggest that KG-augmented models can 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.

heading: 8 ACKNOWLEDGMENTS
text: 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-19051600007, the DARPA MCS program under Contract No. N660011924033 with the United States Office Of 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.

Review summaries:
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.