Enhancing Robustness of Graph Neural Networks on Social Media with Explainable Inverse Reinforcement Learning

Q1: Could this approach be transferred to bit flips?

A1: Thank you for your constructive question. We believe that it is feasible theoretically.

(1) Bit flip attack: This attack disrupts neural network operations by flipping bits in parameters or intermediate results. For example, [1] degrades GNN performance by selectively flipping bits in quantized weights and biases, targeting those most impactful to the model's injectivity.

(2) To transfer our work to bit flips, the key is to model bit flip attacks as a MDP for RL. Suppose there are $T$ -times bit flips to achieve an effective attack, defining the attack trajectory with $T$ steps. The RL elements are:

• State: The current GNN parameters;
• Action: Flipping the specific bit in the parameters, which could be represented by a mask matrix;
• Reward: Estimated by the IRL module;
• Policy: Given the current state, output the next action. A deep RL policy, such as Actor-Critic (AC), might be effective for handling the state from the deep models.

For IRL, it is suggested to use a neural network as the reward function because it is difficult to design interpretable linear features for bit flip attacks when targeting the internals of an end-to-end deep model. Given the target GNN model and some expert bit flip attack trajectories, the learner policy produces the attack actions and updates with the reward from the IRL module to approximate the expert policy.

[1] Attacking Graph Neural Networks with Bit Flips: Weisfeiler and Lehman Go Indifferent

Q2: Did you analyze the impact of varying Rich-club coefficients in the datasets?

A2: Thank you for your vaulable suggestion. The rich-club coefficients of Weibo and Pheme are shown in Figure 1 in the PDF. The analysis reveals that:

(1) As the degree increases, the rich-club coefficient first rises and then falls, indicating that nodes with moderate influence in the social network have higher connectivity with each other.

(2) Pheme exhibits higher rich-club coefficients compared to Weibo, suggesting that the social network on Pheme is more densely connected overall. As a result, attacks on Pheme generate more pronounced cascading effects [1], thereby complicating the recovery of attack policies, which aligns with the experimental results presented in Table 2. The model's performance on Pheme, which has a higher rich-club coefficient, is lower compared to the performance on Weibo with smaller rich-club coefficients.

[1] Cascading failures in complex networks

Q3: The proposed method involves multiple components, which can increase the computational complexity and may not be easily scalable.

A3: Thank you for your valuable suggestion. Please see Q1 in the global rebuttal for further details.

Q4: It might limit the generalizability of the method to other types of graphs and applications.

A4: Thank you for your suggestion. To verify the generalizability, we have adapted and implemented our method for the recommendation system task.

• Dataset: Gowalla [1], includes 13,591 users, 14,322 items, and 227,193 interactions.
• Interpretable Features: The domain-specific features used for rumor detection in our work were modified to suit recommendation systems.
• Metric: ΔNDCG, which measures the reduction in NDCG@20 value after $T$-step attacks.
• Target Model: PinSage [2]. Without attacks, the NDCG value on the training set is 0.4139.
• Attack Method: We improved AdRumor-RL with the features in (2) and generated three expert trajectories, each with 5 steps. It conducts the global attack and updates with the reward ΔNDCG. The average attack performance (ΔNDCG) is 0.0325.
• Performance: Results of policy recovery are as follows. The learner policy achieved 90% of the performance of experts. Our method is effective in the recommendation system task.

[1] Friendship and mobility: User movement in location-based social networks

[2] Graph convolutional neural networks for web-scale recommender systems

Q5: The theoretical underpinnings of IRL and MoE could be more clearly explained.

A5: Thank you for your suggestion. We provide explanations for EntIRL and MoE as follows.

(1) EntIRL infers the reward function in the environment by maximizing the entropy of the path distribution. Thus, the EntIRL objective is defined as $\max\sum -P(τ) \log P(τ)$ with trajactory $τ$. It assumes that $P(τ|θ)∝\exp(R_θ(τ))$, where $R_θ(τ)$ is the reward function with parameter $θ$. The loss function for EntIRL is the likelihood $L(θ) = \sum \log P(τ|θ)$ because maximizing likelihood and maximizing entropy share the same goal [1].

In our work, we consider locally optimal examples, segmenting the trajectory as state-action pairs. The previous assumption becomes $p(a|s)∝\exp(Q^*(s, a))$ [1]. With a discount factor of 0, the action probability $p(a|s)$ is given by Eq. (2). The loss function then becomes $L(θ) = \sum \log P(a|s, θ)$.

(2) MoE consists of a gating network $α()$ and $K$ experts $p_1(),\ldots,p_k()$. It can be indicated as $p(y|x) = \sum_k α(x)p_k(y|x)$. We model the RL policy as an MoE as stated in Eq. (4), with each expert corresponding to an action probability function as shown in Eq. (5). The IRL loss function for each expert is $L(θ_k) = \sum \log p(a|s, θ_k)$, which aligns with the M-step goal in the EM algorithm as stated in Eq. (11). Thus, it optimizes the IRL policy using the EM algorithm.

[1] Maximum entropy inverse reinforcement learning

Q6: No code is provided.

A6: Thank you for your valuable suggestion. Please see Q2 in the global rebuttal.

Q7: Wrong description about “Threat model”.

A7: Thank you for your correction. "Threat model" should be replaced with "Target model".

Q1: What makes the policies on Pheme significantly harder to recover than the policies on Weibo in Table 2?

A1: Thank you for your insightful question. We posit that the difficulty in policy recovery is related to the complexity of the underlying graph structures. As indicated in Table II of the PDF, we have devised several metrics to assess the complexities of the Weibo and Pheme datasets [1-3]. The data reveals that the graph structure of Pheme is more complex than that of Weibo, characterized by a larger variance in node degree and a higher graph density.

Returning to the proposed model, the success of Inverse Reinforcement Learning (IRL) in recovering expert policies is influenced by several factors, including the quality and quantity of expert demonstrations, the complexity of the expert policies, and the variability of the environment. In our humble view, the attack sequences within complex social graphs exhibit significant cascading effects [4], complicating the recovery of these policies. The more intricate the graph structure, the more substantial the cascading effect due to edge-flipping attacks. Such an attack can propagate from a target node to multiple others, thereby impacting the overall system performance because of the high interdependence and connectivity among nodes. Complex graphs increase the likelihood of cascading reactions triggered by attack behaviors.

Furthermore, sequential attacks on these graphs intensify cascading reactions, potentially altering the characteristics of numerous nodes and causing environmental changes within the reinforcement learning process. Attackers may also optimize their strategies, adding more decision conditions and steps to navigate the complex social graph effectively. Together, these factors contribute to the increased difficulty of IRL in recovering expert policies.

As presented in Table II, all baseline methods, including Apprenticeship Learning and EntIRL, exhibit suboptimal performance in recovering policies due to the complexity of the social graph in Pheme. In contrast, our approach, which integrates a mixture of experts to accommodate the attack sequences generated by complex social graphs, consistently achieves state-of-the-art performance on these challenging datasets.

[1] Complex networks: Structure and dynamics. 2006.

[2] The structure and function of complex networks. 2003.

[3] Graph measures and network robustness. 2013.

[4] Cascading failures in complex networks. 2020.

Q2: The unclear description and significant GCN performance discrepancy with [1] in Table 3. (Weakness 2 in reviews)

A2: Thank you for your correction and constructive question.

(1) We apologize for not clearly describing the columns in Table 3. As you mentioned, the column under "w/o Att." reflects test accuracy (%), while results under other columns reflect accuracy decline in actual numbers.

(2) The reasons for this discrepancy in attack effectiveness are multifaceted:

• a) Dataset Differences: The weibo-all dataset referenced in [1] is sourced from the CED repository in Github, which includes the Rumdect dataset and the ChineseRumorDataset. However, the URL for Rumdect is no longer valid. Moreover, the weibo-all dataset in CED repository is pre-processed and lacks user IDs for message reposts, preventing the construction of the social following graph. Therefore, we utilized the original ChineseRumorDataset, which comprises 3,387 Weibo posts (1,538 rumors and 1,849 non-rumors), in contrast to the weibo-all dataset's 8,050 Weibo posts (3,581 rumors and 4,199 non-rumors).
• b) Preprocessing Differences: In previous work [1], all reposting and comment information was either retained or filtered with the early rate (ER). Our approach focuses on retaining early repost messages and comments published within the first 25% of the average time interval and selectively retaining those with high information entropy. To achieve this, we removed stop words and punctuation, segmented the text, calculated the word information entropy for each text, and retained only those texts with entropy values higher than 90% of the highest observed entropy.
• c) Model Differences: We used pre-trained word2vec embeddings and an embedding layer to encode the text content, whereas [1] used TF-IDF + NN as the encoder. We also supplemented the experimental results using TF-IDF encoding as shown in Table Ⅲ in the PDF. TF-IDF slightly outperforms word2vec embeddings. Pre-trained word2vec embeddings might suffer from poor representation of low-frequency words or differences between training corpora and the target task domain. Additionally, our proposal consistently outperforms the baselines with various text encoders, highlighting the effectiveness of the MoE framework.

[1] Ced: Credible early detection of social media rumors. 2018.

Q3: Computational Efficiency: Given the complexity of the model structure illustrated in Figure 2, it would be beneficial to benchmark the computational efficiency of the proposed approach against the baselines in Table 3.

A3: Thank you for your valuable suggestion. Please see Q1 in the global rebuttal for further details.

Dear Reviewer QAYk,

I hope this message finds you well.

I am writing to kindly inquire about the status of your review for our submission 14020 as the rebuttal deadline swiftly approaching (just one day remaining).

We understand that you may have a busy schedule, and we sincerely appreciate your time and effort in reviewing our work. If you have any additional comments or concerns, we would be grateful to discuss them as soon as possible.

Thank you for your understanding and support.

Best regards,

Submission 14020.

Q1: Scalability Analysis: Could you elaborate on how your method scales when applied to very large social media graphs? Any additional insights or preliminary results on this matter would be highly informative.

A1: Thank you for your valuable suggestion.

For the scalability in the large social media graphs, we analyze the time complexity of our method. Please refer to Table I in the attached PDF, where we detail the time complexity and runtime of the MoE-BiEntIRL, alongside two baseline models.

Based on Table I in the accompanying PDF, the time complexity of our proposal and the baseline methods primarily diverges during the reward acquisition phase of IRL. Our approach introduces $K$ experts to manage multi-source attack trajectories with diverse motivations, thereby increasing the time complexity. Notably, the complexity associated with IRL reward acquisition is independent of the input graph size and hinges solely on the predefined hyperparameter $K$, typically ranging from 1 to 10, rendering the increased complexity manageable. Moreover, the predominant computational effort across all models is concentrated in the attack stage, which further mitigates the impact of introducing multiple experts. Table I details the runtime of complete episodes and the IRL module. Despite the extended runtime of the MoE-BiEntIRL approach in the IRL module, it exerts negligible influence on the total runtime. Both the analysis of time complexity and experimental findings emphasize that the actual runtime is largely influenced by the attack stage.

Please see Q1 in the global rebuttal for further details about the time complexity analysis.

Based on the aforementioned time complexity analysis, the scalability of the IRL module easily scalable as it exhibits no direct correlation with the size of the graph. When applied to larger graphs, parameters such as $T$, $K$, $N$, and $S$ may indirectly increase due to the diverse nature of attacks within these larger contexts. As illustrated in Table I, the runtime of the IRL module shows minimal variation across datasets of varying sizes (e.g., Weibo with 10,280 nodes and Pheme with 2,708 nodes). As discussed in time complexity analysis, the predominant factor influencing runtime is the attack stage. Thus, in our humble opinion, the scalability of the proposed model is acceptable.

Furthermore, as for the hyperparameters affected by the large graph indirectly, various methods can mitigate the time complexity and the runtime of the Inverse Reinforcement Learning (IRL) module through careful control of hyperparameters: (1) $K$: Reduce the number of experts by phased experimentation, employing a coarse-to-fine division of experts. We design this method and conducts expriements, which details are shown in Q1 of the global rebuttal. (2) $T$: Segment lengthy expert trajectories using predefined rules or models to minimize state correlation before and after each segmentation. (3) $N$: Employ pre-classification or clustering of multiple expert samples to reduce the number of expert trajectories.

Q2: Could you provide more detailed information regarding your experimental setup? Additional details would aid in understanding how to replicate your study effectively.

A2: Thank you for your valuable suggestion. Please see Q2 in the global rebuttal for further details.

Q1: Could you provide a simple illustrative example or additional details to clarify how the precise sample guidance mechanism and the bidirectional update mechanism work in the MoE-BiEntIRL method?

A1: Thank you for your suggestion. We have provided code and algorithms in global rebuttal Q2, which illustrate when and how the precise sample guidance mechanism and the bidirectional update mechanism operate.

During the early stages of learning, precise sample guidance and inverse updates are performed periodically. In an inverse update episode, the steps for executing the RL policy are replaced with precise sample guidance steps, and attacks are carried out according to the given expert samples. As for the reward, it is assigned the maximum historical reward. Given the sample and reward, the gradient ascent update of the IRL is replaced with the inverse update after the responsibility calculation.

Q2: Can you provide a brief overview of the computational complexity of your proposed method, along with any potential optimizations that could be considered to enhance practical feasibility?

A2: Thank you for your valuable suggestion. Please see Q1 in the global rebuttal for further details.

Q3: A minor issue is that the sensitivity of the model to various parameters is not thoroughly explored. A brief analysis or guidance on parameter selection could aid in the practical application of the method.

A3: Thank you for your suggestions. Here, we provide guidelines for selecting some parameters:

• The sampling upper bound $μ$: This parameter controls the similarity between the negative sample and the expert sample. Considering the validity of hard negative samples, we tend to choose samples with higher similarity, setting $μ=0.8$.
• The learning rates of the learner policy, inverse update, and gate function: These are determined using grid search.

We have included a sensitivity analysis of parameters in Figure 2 in the PDF. Our findings are as follows:

• Sampling similar instances can be advantageous for policy reconstruction; however, selecting instances that are too similar can lead to the failure of Inverse Reinforcement Learning (IRL).

• The learning rates for both the learner policy and the inverse update process are more sensitive compared to that of the gate function.