Adversarial attacks in network security are a growing concern, prompting the need for innovative strategies to enhance both attack and defense mechanisms. This paper explores ways to improve adversarial attacks on the fairness and goodness algorithm (FGA) and review to reviewer (REV2), focusing on predicting trust within signed graphs. Unlike traditional time-based models, FGA and REV2 rely on iterative processes for trust propagation. By analyzing network structures, we identify strong ties and weak ties within FGA and discover preferential paths in REV2 that significantly impact information spread during algorithm iterations. Based on these insights, we propose a new approach called the vicinage attack, which enhances adversarial attacks by strategically targeting edges along these critical pathways. Our work highlights adversarial perturbation patterns that affect trust prediction on signed graphs and emphasizes their wide-reaching impact. These findings not only advance adversarial attack techniques but also deepen our understanding of trust propagation patterns. By clarifying the propagation bias in FGA and REV2, this research provides valuable insights for improving network security and developing better adversarial mitigation techniques in trust prediction.
Notes
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
A signed graph is a widely used model to represent trust relationships among entities, where each edge is assigned a positive or negative sign to indicate the nature of interaction [1]. Positive edges typically denote positive interactions such as friendships or alliances, while negative edges signify conflicts or disagreements. This versatility finds applications across various domains, such as social networks [2, 3], sentiment analysis [4], and trust prediction [5].
For example, in a community where individuals engage in peer-to-peer transactions [6‐8], each transaction involves an exchange of goods or services, and participants provide positive or negative feedback based on their experiences. A signed network can be constructed where nodes represent individuals, and edges between nodes carry signs to indicate whether the transaction feedback was positive or negative. In cryptocurrency, signed networks can provide insights into transaction dynamics between wallet addresses. Positive edges represent transactions from one wallet to another, while negative edges symbolize double-spending or fraudulent transactions. Analyzing such a signed network helps detect suspicious behaviors, track the flow of cryptocurrencies, and enhance security measures against fraud.
Advertisement
Understanding mutual trust information within signed graphs is crucial, and predicting trust relies on trust systems [9‐11]. The fairness and goodness algorithm (FGA) is a popular trust system on signed directed networks for edge weight prediction [12]. FGA uses two metrics to characterize node behavior: goodness, which reflects how much other nodes trust a given node, and fairness, which assesses how impartially this node rates others. These concepts are defined in a mutually recursive manner that eventually converges to a unique solution. Kumar et al. demonstrated FGA’s effectiveness in forecasting edge weights, indicating the trustworthiness between nodes that are not directly connected. Additionally, review to reviewer (REV2) is a network-based behavioral fraud detection algorithm [13].
REV2 has been adapted for risk rating on Ethereum [14, 15], where it quantifies the de-anonymity score, life span suspiciousness, and wash suspiciousness metrics, each mapped to a standardized range of \([-1, 1]\). This transformation allows the representation of Ethereum transaction records as a weighted signed graph model. The REV2 algorithm can then assign trust scores to individual accounts and assess associated risks.
The reliability of trust prediction is critical due to the presence of adversarial attacks against trust prediction systems [16‐18]. Attackers aim to manipulate trust scores using techniques like Sybil attacks [19‐21], which involve tactics such as IP harvesting and deploying botnets [22]. Their primary goal is to manipulate target nodes’ trust scores to evade detection by trust systems and cause confusion among users. This involves artificially inflating or deflating trust scores, effectively reversing the trustworthiness status of nodes. Studying adversarial attacks against trust prediction is essential. In the context of FGA on signed graphs, Lizurej et al. proposed an indirect Sybil attack on FGA. The objective is to decrease target nodes’ trust by injecting edges into the original graph with a limited edge budget [17]. The problem involves a weighted signed network, attacker nodes S, target nodes T, an intermediary set I, a budget k, and a threshold value \(r \in [-1, 1]\). Figure 1 provides details. The goal is to determine whether no more than k additional edges can decrease the trust score of each node in T below the threshold r. Attacker nodes can only affect nodes through the intermediary set I. This problem is NP-hard [17]. However, while Lizurej et al. showed indirect attacks are not effective, we find that indirect attacks can be effective due to the existence of preferential paths.
Fig. 1
The problem of Decrease Node Rating, an indirect Sybil attack on FGA, is NP-hard [17]. \(a_1\), \(a_2\), and \(a_3\) are attacker nodes. \(m_1\), \(m_2\), and \(m_3\) and \(n_1\), \(n_2\), and \(n_3\) are intermediary nodes. \(t_1\), \(t_2\), \(t_3\), and \(t_4\) are target nodes
×
This paper explores adversarial attacks against trust prediction and introduces a new perspective on enhancing them. Our research focuses on the iterative propagation process within FGA and REV2. First, we aim to distinguish strong ties and weak ties in FGA from the intricate interplay of tie structures. Then, we extend these concepts as preferential paths within REV2. Our main contributions are:
We confirm that strong ties and preferential paths are recognizable topology patterns more likely to be vulnerabilities for trust systems.
We find a propagation bias within both FGA and REV2, where the trust metric is more likely to travel along strong ties or preferential paths.
We are the first to highlight the role of strong ties and preferential paths in shaping the effectiveness of adversarial attacks.
Through this exploration, we aim to establish a foundation for a new paradigm in adversarial attack strategies—one that leverages the hidden influence of strong ties and preferential paths to enhance the potency of manipulative actions within complex networked environments. The remainder of this paper is organized as follows: Sect. 2 reviews existing research on trust prediction on signed graphs, status theory on signed graphs, trust and distrust propagation, and adversarial attacks on graphs. Section 3 describes the FGA and REV2 models used in our study. Section 4 outlines the specific problem statements and challenges addressed by our research. Section 5 analyzes network structures to identify strong and weak ties within FGA and preferential paths within REV2. Section 6 introduces our vicinage-attack approach. Section 7 presents experimental results, comparing the effectiveness of our method against baselines. Section 8 explores practical applications and broader implications. Section 9 discusses the limitations of our approach and outlines future research directions. Finally, the conclusion summarizes our key findings and their significance.
Advertisement
2 Related work
2.1 Trust prediction on signed graph
Hyperlink-Induced Topic Search (HITS) is a link analysis algorithm originally used to rank web pages. In signed graphs, HITS has been adapted for trust prediction by calculating authority scores from the scaled values of hubs pointing to a node and hub scores from the scaled values of authorities linked from a node.
Several enhancements to the HITS algorithm have been made for various applications, including fraud detection, node ranking, and link prediction [23‐27]. FGA builds on the HITS algorithm by introducing goodness and fairness metrics to improve trust prediction in signed graphs.
In addition to HITS-based modifications, PageRank-based algorithms have been adapted for trust prediction on signed graphs [28, 29]. REV2 has been further developed to enable more extensive propagation in complex networked environments. These advancements in HITS and PageRank-based algorithms have significantly improved the accuracy and reliability of trust prediction in signed graphs.
2.2 Status theory on signed graph
Status theory suggests that individuals within a social network occupy different levels of status, which influences their interactions with others [30]. High-status individuals are generally more trusted, while low-status individuals may face distrust. This is especially relevant in signed directed graphs, where edges represent trust (+) or distrust (-) and their direction indicates the flow of influence or information.
In signed directed graphs, high-status nodes tend to have more incoming trust edges and fewer distrust edges. Conversely, low-status nodes may have more incoming distrust edges. This pattern shows how people align their trust relationships with the perceived status of others.
Several studies have integrated status theory into trust prediction models [31, 32]. These studies show that considering social hierarchies can significantly improve the accuracy of trust predictions. In this paper, we use status theory to refine the perturbation spaces, reducing computational burden.
2.3 Trust and distrust propagation
Propagation-based techniques derive a dense matrix \(\hat{A}\) from the original matrix A using specific propagation operators. These operators perform multiple stages of information diffusion, predicting link signs between nodes \(u_i\) and \(u_j\) as \(sign(\hat{A_{ij}})\), with likelihood represented by \(|\hat{A_{ij}}|\).
Guha et al. [33] conceptualize trust propagation as repetitive matrix operations with four atomic trust propagation types: direct propagation, trust coupling, co-citation, and transpose trust. Both Guha et al. and Lee et al. [34] use a matrix representation approach.
Other methods use alternative representations like subjective logic [35], intuitionistic fuzzy relations [36], and bi-lattice [37] to propagate both trust and distrust through defined operators.
In this paper, we refer to atomic trust and distrust propagation as tie structures, which we use to construct the perturbation space for adversarial attacks.
2.4 Adversarial attacks on graph
Adversarial attacks on graph structures aim to modify the adjacency matrix to cause significant classification errors [38, 39]. In a gray-box scenario, attackers use gradient-based strategies on the adjacency matrix to identify critical modifications. Various methods exist for selecting edge alterations based on gradients [40‐43].
These adversarial techniques challenge the robustness of graph-based anomaly detection systems by exploiting vulnerabilities in graph structures and classification models. Ongoing research aims to develop better defense mechanisms to mitigate these attacks.
In this paper, we focus on the perturbation spaces defined by tie structures, providing a new perspective on enhancing adversarial attacks.
3 Target model
The goal of the target model is to derive trust scores for each node based on graph-level information. To achieve this, the fairness and goodness algorithm (FGA) and review to reviewer (REV2) are proposed, using iterative definitions of fairness f(u) and goodness g(v). Fairness reflects how objectively node u rates others, while goodness indicates the level of trust placed in node v when rated by others. In REV2, reliability r(u, v) is introduced as an edge-level metric during iterative learning, where reliable ratings are provided by fairer users, closer to goodness scores.
Consider a directed, weighted signed graph \(G = (U, R, W)\), where user \(u \in U\) generates a rating \((u,v) \in R\) for user \(v \in U\). Here, U, R, and W represent the set of all users, ratings, and the scores of ratings, respectively. The rating score \(W(u,v) \in [-1, 1]\) signifies the trust of node u in rating node v. Define:
\(\mathrm{In(v)}\) as the set of ratings received by node v
\(\mathrm{Out(u)}\) as the set of ratings given by node u
\(|\mathrm{In(v)}|\) as the count of ratings received by node v
\(|\mathrm{Out(u)}|\) as the count of ratings given by node u
This framework helps in systematically calculating trust scores and understanding the dynamics of trust within the network.
3.1 FGA as target model
The recursive formula of FGA is described as follows:
Here, f(u) ranges in [0,1] while g(u) falls in \([-1,1]\). Both f(u) and g(u) are initialized as 1 and are recursively updated over all nodes until they converge to a small value \(\varepsilon \). The convergence condition is \(\left| g^{t+1}(u)-g^t(u)\right| <\varepsilon \) or \(\left| f^{t+1}(u)-f^t(u)\right| <\varepsilon \). Lizurej et al. consider the goodness metric as a manipulative trust score and have proved that an indirect attack targeting goodness on FGA is NP-hard [17].
3.2 REV2 as target model
The recursive formula of REV2 is expressed as follows:
In this context, f(u), g(v), and r(u, v) values fall within [0, 1]. \(\mu _f\) and \(\mu _g\) are set as the mean scores of all users’ fairness and goodness scores, respectively. f(u), g(v), and r(u, v) are initialized as 1 and are recursively updated until convergence is achieved. The convergence condition is \(\max \{|g^{t+1}(u)-g^t(u)|, |f^{t+1}(u)-f^t(u)|, |r^{t+1}(u,v)-r^t(u,v)| \} < \varepsilon \), where \(\varepsilon \) is a small value. According to [13], the rank of the fairness score can be used to detect fraudulent users. For this process, \(\alpha _1\), \(\gamma _1\), \(\gamma _2\), and \(\beta _1\) are set to 1.
4 Problem statements
4.1 Threat model
This study presents a detailed threat model for adversarial attacks, specifically targeting trust prediction within signed social networks and trust systems like FGA and REV2. Our threat model includes the following key aspects:
Attacker’s Objective: Malicious entities, referred to as attackers, aim to disrupt the trust prediction process. They seek to manipulate trust scores for various purposes, such as discrediting specific users, hiding their true intentions, or boosting their trust scores within the network. Attackers achieve these goals by carefully crafting adversarial perturbations.
Knowledge and Capabilities: Attackers know the trust prediction algorithm and the network structure. They can manipulate the network by adding or modifying edges and influencing trust scores. Attackers use techniques like edge addition, deletion, or weight modification, strategically targeting influential pathways in trust propagation. Our focus is on edge injection, as removing edges is technically and practically challenging. For an injected edge (i, j) from i to j, we refer to it as a positive attack from i or a passive attack toward j.
Attacker’s Stealthiness: In indirect attacks, stealthiness is crucial. Unlike direct attacks, indirect attacks blend with genuine trust propagation to avoid detection. Attackers use tactics to ensure their actions do not raise suspicion within the network. Indirect attacks involve the participation of target nodes, their neighbors, and attacker nodes, making stealth a priority.
In summary, our threat model examines how attackers exploit preferential paths and strong ties within signed graphs, using their knowledge of algorithms, network structures, and perturbation techniques. It emphasizes the importance of stealth in indirect attacks to achieve their goals.
4.2 Problem formulation
In this section, we formulate the indirect attack against trust prediction as a bi-level discrete optimization problem.
We represent the original graph as \({G_0}=\{U_0, R_0, W_0, Y_0\}\), where \(Y_0\) is the trust score or trust rank of the nodes. In adversarial attacks, attackers inject malicious edges, resulting in a manipulated graph \(G_{\varepsilon }=\{U_0, R, W, Y_{\varepsilon }\}\), which is observed by trust system administrators. The trust prediction function is denoted as \(p(\cdot )\).
The graph structure is modified by introducing additional edges with weight scores to manipulate trust prediction results. The attacker’s primary goal is to minimize or maximize the trust prediction results of all target nodes in T by introducing at most k additional edges. The influence of attacker nodes S should be mediated through intermediary nodes in set I(T). The perturbation space is constructed by connecting attacker nodes with intermediary nodes, denoted as \(\Phi _{S,T}(B)= \{S \times I(T)\}_{w \in \{-1,1\}}\). The binary variable B represents the set of newly introduced edges.
The top-k largest entries in \(B^{*}\) are selected for modification through the operation \(\sigma _{\Phi }^{k}(\cdot )\), denoted as \(\bigcup _{1}^{k}(i^{*}, j^{*}) = \sigma _{\Phi }^{k}(B^{*}) = \arg \mathop {\max _{k}}_{(i, j, w) \in {\Phi _{S,T}(B^*)}} B^{*}\). The indirect attack against the trust system can then be formulated as a bi-level optimization problem:
Here, \(c_i\) represents the cost associated with the injected edges. The perturbation space includes various categories of edges for injection. Specifically, in a directed graph, there are two types of 1-hop neighbors for target node T: Pred(T) and Succ(T). Similarly, there are four types of 2-hop neighbors: Succ(Pred(T)), Pred(Succ(T)), Succ(Succ(T)), and Pred(Pred(T)). \(Pred(\cdot )\) represents the predecessors of nodes, and \(Succ(\cdot )\) represents the successors of nodes. \(\Phi _{S,T}(B_i)\) denotes the different types of perturbation spaces \(\{S \times I_{type_i}(T)\}_{w \in \{-1,1\}}\). Each entry \(b^{*}_{i} \in B^{*}\) is a binary variable, taking values from the set \(\{0, 1\}\) to indicate the inclusion or exclusion of a specific edge.
5 Analysis of preferential path
To thoroughly understand trust propagation in the trust system, we focus on analyzing a specific pathway. This pathway includes the flow from the attacker node to the target node, covering the target node’s neighbor and the injected edge. This structural configuration is referred to as the tie structure.
In this section, we distinguish strong ties and weak ties on FGA from the intricate interplay of tie structures. Then, we extend these concepts to preferential paths within REV2. The strong ties on FGA can be considered a specific example of preferential paths because attackers prefer to attack via strong ties rather than weak ties (to be detailed later).
Fig. 2
Concept of weak tie, strong tie, and Poly-ST on FGA. The examples of weak tie and strong tie are classical. The examples on Poly-ST are non-classical because there are more examples that can be enumerated
×
5.1 Strong ties and weak ties on FGA
Strong ties and weak ties describe whether a tie structure allows an attacker to indirectly generate a perturbation on goodness. The goodness metric reflects how much trust is received by other nodes. We also use conductivity and resistance to describe the capability of generating perturbations on target nodes concerning FGA goodness. Below, we enumerate all tie structures involving either 1-hop or 2-hop neighbors of the target node. Then, we distinguish strong ties and weak ties among them.
Definition 1
(TIE STRUCTURE) For the graph structure consisting of a target node t, an attacker node, and intermediary node(s), we call them Tie Structures.
Definition 2
(WEAK TIE I to X) For the tie structure consisting of a target node t, an attacker node, and 1) Succ(t) (referred to as Weak Tie IX and Weak Tie X in Fig. 2); 2) Pred(t) and Pred(Pred(t)) (referred to as Weak Tie I and Weak Tie IV in Fig. 2); 3) Succ(t) and Succ(Succ(t)) (referred to as Weak Tie III and Weak Tie VI in Fig. 2); 4) Succ(t) and Pred(Succ(t)) (referred to as Weak Tie II and Weak Tie V in Fig. 2); 5) attacker positive attack toward Pred(t) (referred to as Weak Tie VIII in Fig. 2); and 6) attacker passive attack toward Succ(Pred(t)) (referred to as Weak Tie VII in Fig. 2), we call them Weak Ties.
Definition 3
(STRONG TIE I and II) For the tie structure consisting of a target node t, an attacker node, and 1) attacker positive attack toward Succ(Pred(t)) (referred to as Strong Tie I in Fig. 2) and 2) attacker passive attack toward Pred(t) (referred to as Strong Tie II in Fig. 2), we call them Strong Ties.
Definition 4
(POLYMORPHIC STRONG TIE) For the tie structure consisting of a target node t, an attacker node, and 1) if there simultaneously exist multiple Strong Tie I (referred to as Poly-ST I in Fig. 2); 2) if there simultaneously exist multiple Strong Tie II; and 3) if there simultaneously exist Strong Tie I and Strong Tie II (referred to as Poly-ST IV in Fig. 2), we call them Polymorphic Strong Ties.
The concept of polymorphic strong tie (Poly-ST) can be extended to more than 2-hop neighbors (referred to as Poly-ST II, Poly-ST III, Poly-ST V, and Poly-ST VI in Fig. 2). Table 1 summarizes all indirect attack cases within at most 2-hop neighbors, filtering out two cases as strong tie candidates according to rigging properties (to be detailed later). We will also quantitatively analyze strong ties and weak ties. More details will be presented and discussed in the experimental evaluation.
Table 1
Indirect attack tie structures on FGA
Categories
Positive attack
Passive attack
Pred(T)
Succ(T)
Succ(Pred(T))
Pred(Succ(T))
Succ(Succ(T))
Pred(Pred(T))
is the case capable to generate perturbation on target node’s goodness, which is more likely to be strong tie.
are the cases cannot influence target node’s goodness. The positive and passive attack is in the view of attackers
5.1.1 Ties rigging axioms
The mutual recursive learning process on FGA leads to a noticeable propagation bias. This bias, seen as trust propagation on tie structures, can be understood through properties of conductivity and resistance. Trust propagation tends to follow a preferential path. For more detailed proofs, refer to [12, 17].
Axiom 1
(DIRECTION-ORIENTED RIGGING). A perturbation on f(Pred(t)) will change g(t), and similarly, a perturbation on g(Succ(t)) will change f(t).
The incoming edge of t starts from Pred(t), and the outgoing edge of t ends with Succ(t). From Eq. (1), a perturbation on f(Pred(t)) changes g(t), and a perturbation on g(t) changes f(Pred(t)). Similarly, a perturbation on g(Succ(t)) changes f(t), and a perturbation on f(t) changes g(Succ(t)). Axiom 1 demonstrates the interdependence of metrics in mutual recursive learning. In [12], the goodness axiom and fairness axiom also highlight this dependence.
Axiom 2
(SMOOTH GOODNESS). An increase in f(Pred(t)) results in a proportional increase in g(t).
This is a simplified explanation of the citation axiom in [17] (Axiom 1).
Axiom 3
(OBVIOUS FAIRNESS METRIC). If node Pred(t) rates all its successor nodes with a rating bias \(\gamma = |g(u)-W(Pred(t),u)| = 0\), then \(f(Pred(t))=1\). If node Pred(t) rates all its successor nodes with a rating bias \(\gamma = |g(u)-W(Pred(t),u)| = 2\), then \(f(Pred(t))=0\).
This is a simplified explanation of the citation axiom in [17] (Axiom 9). This axiom indicates that the rating bias determines the fairness score of nodes.
5.1.2 Tie strength analysis
Trust propagation shows conductivity on strong ties and resistance on weak ties. Here, we explore the reasons behind this propagation bias using ideal topological models to analyze trust propagation on FGA quantitatively. We show that the effectiveness of strong ties depends on both the sign and weight of the injected edge.
To simplify the discussion, we assume the edge weights \(w_1\) and \(w_2\) in Fig. 3 are positive, as negative edges are relatively rare in signed graphs. For Strong Tie I, this involves reducing g(q), which then decreases f(p) and, consequently, g(t). For Strong Tie II, the rigging mechanism focuses on reducing f(q), which then lowers g(t).
Theorem 1
(RESISTANCE OF WEAK TIES) From Weak Tie I to Weak Tie X, g(t) remains unchanged.
Proof
If there is a perturbation on f(Pred(t)), then g(t) will change. This rigging property can be expressed as \(\Delta g(t) \Leftrightarrow \Delta f(Pred(t))\). Similarly, if there is a perturbation on g(Succ(t)), f(t) will change, expressed as \(\Delta f(t) \Leftrightarrow \Delta g(Succ(t))\). Only two ties can generate a perturbation on g(t): \(\Delta g(t) \Leftrightarrow \Delta f(Pred(t)) \Leftrightarrow \Delta g(Succ(Pred(t)))\) and \(\Delta g(t) \Leftrightarrow \Delta f(Pred(t))\). These correspond to Strong Tie I and Strong Tie II. Given the topological model of strong ties and weak ties, there is only one path from the attacker node to the target node. Therefore, weak ties do not influence g(t). \(\square \)
Fig. 3
Tie strength analysis on strong ties
×
Theorem 2
(CONDUCTIVITY OF STRONG TIE I) For Strong Tie I, if (s, q) is injected with weight \(w_0\) and \(f(s)w_0< g(q) < w_2\), then \(\Delta g(t) < 0\); or if \(g(q) > \max (w_2, f(s)w_0)\) and \(w_0 < \frac{2w_2-1}{f(s)}\), then \(\Delta g(t) < 0\).
Proof
As shown in Fig. 3, if there is an injected edge attack, then \(g'(q)=\frac{g(q)d_{in}(q)+f(s)w_0}{d_{in}(q)+1}\). Thus, \(\Delta g(q) = g'(q)-g(q) =\frac{f(s)w_0-g(q)}{d_{in}(q)+1}\). If \(g(q) > f(s)w_0\), g(q) decreases; otherwise, g(q) increases. The perturbation of \(\Delta f(p)\) is \(\Delta f(p)=\frac{1}{2d_{out}(p)}(|w_2-g(q)|-|w_2-g'(q)|)\). There are four cases:
We expect \(\Delta g(q) < 0 \) and \(\Delta f(p) < 0\), so that \(\Delta g(t) = \frac{\Delta f(p)w_1}{d_{in}(t)} < 0\) when \(w_1 > 0\). In (4c), if \(\Delta g(q) < 0\), then \(\Delta f(p) > 0\); in (4d), if \(g(q)< w_2 < g'(q)\), then \(\Delta g(q) > 0\). Thus, only two cases need to be discussed.
CASE I: If \(f(s)w_0< g(q) < w_2\), then \(\Delta g(q)< 0, \Delta f(p) < 0\), and \(\Delta g(t) < 0\).
CASE II: We have \(\Delta g(q) = \frac{f(s)w_0-g(q)}{d_{in}(q)+1} < 2w_2 - 2\,g(q)\), \(-1< g(q)< \frac{2(d_{in}(q)+1)w_2-f(s)w_0}{2d_{in}(q)+1} < 1\), \(\frac{2w_2-f(s)w_0-1}{2(1-w_2)}< d_{in}(q) < \frac{2w_2-f(s)w_0-g(q)}{2(g(q)-w_2)}\). So, if \(g(q) > \max (w_2, f(s)w_0)\) and \(w_0 < \frac{2w_2-1}{f(s)}\), then \(\Delta g(q) < 0 \), \(\Delta f(p) < 0\), and \(\Delta g(t) < 0\). \(\square \)
Theorem 3
(CONDUCTIVITY OF STRONG TIE II) For Strong Tie II, if (q, s) is injected with weight \(w_0\) and \(f(p)w_0< g(s) < w_0\), \(\Delta g(t) < 0\); or if \(g(q) > \max (w_0, f(s)w_0)\) and \(w_0 > \frac{1}{2-f(s)}\), then \(\Delta g(t) < 0 \).
Proof
As shown in Fig. 3, if there is an injected edge attack, then \(\Delta g(s) = g'(s)-g(s) =\frac{f(q)w_0-g(s)}{d_{in}(s)+1}\) and \(\Delta f(q)=\frac{1}{2d_{out}(q)}(|w_0-g(s)|-|w_0-g'(s)|)\). We expect \(\Delta f(q) < 0\), so that \(\Delta g(t) = \frac{\Delta f(q)w_1}{d_{in}(t)} < 0\) when \(w_1 > 0\).
CASE I: If \(f(p)w_0< g(s) < w_0\), then \(\Delta g(s)< 0, \Delta f(q) < 0\), and \(\Delta g(t) < 0\).
CASE II: We have \(\Delta g(s) = \frac{f(q)w_0-g(s)}{d_{in}(s)+1} < 2w_0 - 2\,g(q)\), \(-1< g(s)< \frac{2(d_{in}(s)+1)w_0-f(s)w_0)}{2d_{in}(s)+1} < 1\), \(\frac{2w_0-f(s)w_0-1}{2(1-w_0)}< d_{in}(s) < \frac{2w_0-f(s)w_0-g(q)}{2(g(q)-w_0)}\). So, if \(g(q) > \max (w_0, f(s)w_0)\) and \(w_0 > \frac{1}{2-f(s)}\), then \(\Delta g(s) < 0 \), \(\Delta f(q) < 0\), and \(\Delta g(t) < 0\). \(\square \)
5.2 Preferential path on REV2
We aim to identify which nodes are crucial in forming preferential paths on REV2. To assist in this analysis, we introduce status theory as outlined in Table 2. In a signed directed graph, a positive edge from A to B means A believes B’s status is higher than A’s, while a negative edge from C to D means C believes D’s status is lower than C’s. We use fairness score to represent status. Status theory helps narrow the scope of perturbation spaces, allowing us to focus on situations where drastic changes might occur in the trust system. Our main focus is on injected edges that violate the principles of status theory, as these are more likely to disrupt normal trust prediction. Violations include a positive edge from a high-fairness node to a low-fairness node and a negative edge from a low-fairness node to a high-fairness node.
Table 3 provides a comprehensive list of all possible preferential paths identified in our experiments. Unlike the theoretical definitions of strong ties and weak ties on FGA, the concept of preferential path in REV2 is defined empirically (see experiment results on REV2). The main difference between strong ties and preferential paths is that the latter are the preferred pathways among all conductive paths. To clarify, if a tie structure is a preferential path, it must also meet the criteria of a strong tie. However, a strong tie may not always be a preferential path.
Table 2
Status theory in trust propagation on REV2
Categories
Positive edge
Negative edge
(low fairness, high fairness)
(high fairness, low fairness)
is the case satisfies status theory while
is the case disobey status theory. In original datasets, for negative edges defy status theory, there are 3.725% in bitcoin-alpha and 5.727% in bitcoin-otc. For positive edges defy status theory, there are 47.168% in bitcoin-alpha and 46.084% in bitcoin-otc
Table 3
Indirect attack cases tie structures on REV2
Categories
Passive attack (+1)
Positive attack \((-1)\)
Pred(T)
\(\heartsuit \)
Succ(T)
\(\heartsuit \)
Succ(Pred(T))
\(\heartsuit \)
Pred(Succ(T))
\(\heartsuit \)
Succ(Succ(T))
\(\heartsuit \)
Pred(Pred(T))
\(\heartsuit \)
means the case is more likely to be preferential path. \(\heartsuit \) means the case cannot be a preferential path because of empirical test. The positive and passive attack is in the view of target nodes
6 Proposed method
The overall architecture of the proposed method is shown in Fig. 4. The processes of sensitivity analysis and universe analysis help distinguish preferential paths from other tie structures in FGA and REV2. It is important to note that the construction of the perturbation space allows for the reutilization of results from adversarial training, which may lead to adversarial retraining if necessary.
6.1 Perturbation space construction
The perturbation space is constructed by connecting attacker nodes to the neighbors of target nodes (intermediary nodes), denoted as \(\Phi _{S,T}(B)= \{S \times I(T)\}_{w\in \{-1,1\}}\). This pathway, consisting of an attacker node, injected edge, target node’s neighbor, and the target node, forms a new tie structure. Additionally, the injected edge should be weighted. We refer to these two processes as tie structure generation and edge weight generation.
The perturbation space \(\Phi _{S,T}(B_0)\) includes edges originating from attacker nodes and pointing to Succ(Pred(T)). Similarly, the perturbation spaces \(\Phi _{S,T}(B_1)\), \(\Phi _{S,T}(B_2)\), and \(\Phi _{S,T}(B_3)\) include edges connecting attacker nodes to Pred(Succ(T)), Succ(Succ(T)), and Pred(Pred(T)), respectively. Recognizing that there are shared nodes among the neighborhoods of these four types of 2-hop neighbors, we combine the entire perturbation space under the term \(\Phi _{S,T}(B)\). This is defined as \(\Phi _{S,T}(B):=\mathop {\bigcup }_i\Phi _{S,T}(B_i)\), representing a comprehensive universe of perturbations.
For simplification, we assume that each edge has a uniform cost of 1. The optimization problem can be simplified and expressed as the following formula:
The optimization task is challenging due to the inherently discrete nature of the binary variable B. To address this challenge, we present a novel approach involving the redefinition of B as \(\widetilde{B}\). Each element \(\widetilde{b}_{i} \in B^{*}\) denotes the probability of manipulation pertaining to the \(edge_{i}\). This redefinition effectively transforms the underlying graph structure from a discrete graph to a continuous one, creating a probability space derived from the original perturbation space. The corresponding perturbation space is \(\Phi _{S,T}(\widetilde{B})= \{S \times I(T)\}_{w\in \{-1,1\}}^{p=0.5}\), where \(p=0.5\) is the initialized probability. This continuous representation of the graph allows us to conduct optimization operations more efficiently. The continuous graph can be expressed as \(\widetilde{\mathcal {G}} = \Phi _{S,T}(\widetilde{B})\cup G_0\). The optimization problem can be rewritten as follows:
The introduction of the continuous graph necessitates the formulation of new indegree and outdegree operators because the degree operators on the continuous graph should be differentiable with respect to the variable \(\widetilde{B}\). We define degree operators using the hyperbolic tangent function, with a smoothness parameter \(\beta \). The newly defined indegree and outdegree operators can be expressed as follows:
In REV2, trust scores are arranged in ascending order to produce a deterministic trust rank, \(\mathcal {R}(p(G_0))\), where the top-ranked nodes are considered unfair or anomalous. Our goal is to avoid sorting and use gradient-based optimization techniques instead. Inspired by Softrank by Taylor et al. [44], we propose an approximate algorithm to generate rank distributions without explicit sorting. For a given node, \(node_i\), we aim to estimate the probability that \(node_i\) ranks higher than another node, \(node_j\). This probability, denoted as \(\pi _{ij}\), is given by:
This probability reflects how often \(node_i\) will achieve a higher trust rank than \(node_j\) in repeated pairwise comparisons. By aggregating these probabilities for a node being ranked higher than every other node, the expected trust rank of \(node_i\) is:
$$E[r_i] = \sum _{i \ne j, j=1}^{|U|} \pi _{ij}$$
We introduce an attacker’s deterministic function, \(\mathcal {F}_{atk}(\cdot )\), to model the impact of manipulation on trust rank. This function determines whether the manipulation aims to minimize or maximize the trust rank. Specifically, \(\mathcal {F}_{atk}(\cdot )\) is defined as 1 for minimizing the trust rank and \(-1\) for maximizing it. In REV2, the optimization problem is formulated as follows:
We use gradient descent for the optimization problem, as detailed in previous works [39‐43]. We start with \(\widetilde{B}\) initialized at 0.5 and update it using the rule: \(\widetilde{B} \leftarrow \Pi _{[0,1]}(\widetilde{B} - \alpha \nabla _{\widetilde{B}} \mathcal {F}_{atk}(\mathcal {C}_{\widetilde{B}}))\), where \(\alpha \) is the learning rate. Here, \(\mathcal {C}_{\widetilde{B}}\) represents the cumulative trust rank of target nodes from \(\Phi _{S,T}(\widetilde{B}) \cup G_0\). The gradient projection ensures that \(\widetilde{B}\) remains within the range [0, 1]. This projection is also applied during updates to fairness, goodness, and reliability. After several optimization steps, \(\widetilde{B}\) converges to values close to either 1 or 0, indicating a higher probability of edge injection. Finally, the gradient distribution (in descending order) is used to select candidate edges.
As a summary, the proposed vicinage-attack method is outlined in Algorithm 1. The algorithm includes an outer loop for optimization steps and an inner loop for iterative learning. Parameters n and l denote the number of iterations for the outer and inner loops, respectively. The core idea of our adversarial attack algorithm is to treat the constructed perturbation space as a hyperparameter and compute the gradient of the attacker’s objective with respect to it.
Algorithm 1
Gradient-based Indirect Attack
×
7 Evaluation
7.1 Dataset description
We evaluated our proposed attacks using two real-world signed networks from the Stanford Network Analysis Project (SNAP: http://snap.stanford.edu/index.html). The datasets used are:
- bitcoin-alpha: This dataset includes 3,783 nodes and 24,186 edges.
- bitcoin-otc: This dataset includes 5,881 nodes and 35,592 edges.
Both datasets represent web-of-trust networks from Bitcoin trading. In these networks, each node represents a user, and the interactions between users are private and voluntary. In particular, each node pair represents a completed transaction, and the edge weights indicate ratings given by customers to suppliers. These ratings are initially in the range of \([-10, 10]\), but for our analysis, they are standardized to the interval \([-1, 1]\).
7.2 Comparison methods
We evaluate our proposed attack method by comparing it with three baseline strategies:
Random Attack: This method involves randomly selecting edges from the perturbation space to manipulate trust.
Indirect Attack: This approach uses a brute-force method to examine all edges in the perturbation space. For each edge, we test its impact on the trust score or rank of target nodes. The edges are then ranked by their influence, and the top-k most influential edges are selected. This approach follows [17].
Modified Indirect Attack: This method improves upon the Indirect Attack by dividing the budget of k into n epochs. Within each epoch, the influence of all potential edges is ranked, and the top-\(\frac{k}{n}\) edges are chosen as candidates. This approach is also detailed in [17].
For the modified indirect attacks, the performance depends on the parameter n. We found that even with \(n=1\), the brute-force method is more time-consuming compared to our proposed vicinage-attack method. To optimize computational efficiency, we set a maximum of optimization steps for our proposed method:
For FGA: We use up to five steps.
For REV2: We use up to four steps.
For the modified indirect attack, we set n as follows:
For FGA: n is set to five.
For REV2: n is set to four.
7.3 Adversarial attack on FGA
7.3.1 Experiment results
Figure 5 shows that the vicinage-attack method outperforms the baseline strategies in terms of effectiveness. The Indirect-attack and Modified Indirect-attack methods do not adequately solve the combination optimization problem. We aim to ensure that \(\Phi _{S,T}(B_4)\) generates only weak ties. Specifically, \(\Phi _{S,T}(B_4)\) is defined as \(\Phi _{S,T}(B_1) \cup \Phi _{S,T}(B_2) \cup \Phi _{S,T}(B_3) - \Phi _{S,T}(B_0)\). Figure 6 compares the results from different perturbation spaces: \(\Phi _{S,T}(B_0)\), \(\Phi _{S,T}(B_1)\), \(\Phi _{S,T}(B_2)\), \(\Phi _{S,T}(B_3)\), and \(\Phi _{S,T}(B_4)\). The results indicate that perturbations from \(\Phi _{S,T}(B_4)\) are less effective, highlighting the importance of strong ties in making adversarial attacks more effective.
Fig. 5
Compare vicinage-attack with baselines. The experimental results are obtained by taking the average value of five independent experiments
Fig. 6
Compare strong tie with weak ties. The experimental results are obtained by taking the average value of five independent experiments
Fig. 7
Distribution of fairness and goodness on FGA, and distribution of edge weights
Fig. 8
Fairness distribution on REV2
×
×
×
×
7.3.2 Prerequisite of strong tie
We observed that Strong Tie II is ineffective when the weight of the injected edge is set to \(-1\). This section examines why this happens, using statistical analysis and the prerequisites for strong ties.
For Strong Tie II, Case I is defined as \(f(p)w_0< g(s) < w_0\). This condition cannot be satisfied if \(w_0 < 0\), where \(w_0\) is the weight of the injected edge. Case II is defined as \(g(q) > \max (w_0, f(s)w_0)\) and \(w_0 > \frac{1}{2 - f(s)}\). Figure 7 shows the distributions of fairness and goodness in FGA, as well as the distribution of edge weights. Most fairness values are in the range (0.9, 1), while most goodness values are in (0.5, 0.25). Most edge weights are also in (0.5, 0.25). Satisfying Case II is difficult because \(w_0 > \frac{1}{2 - f(s)}\) implies \(w_0\) should be close to 1, which conflicts with the assumption of \(w_0 = -1\).
For Strong Tie I, Case I is defined as \(f(s)w_0< g(q) < w_2\). Case II is defined as \(g(q) > \max (w_2, f(s)w_0)\) and \(w_0 < \frac{2w_2 - 1}{f(s)}\). Case II can be approximated as \(g(q) > w_2\) and \(w_0 < \frac{2w_2 - 1}{f(s)}\). Given the majority distribution, the requirement can be simplified to \(w_0 < \frac{2w_2 - 1}{f(s)}\). This condition is more easily met when \(w_0 = -1\).
7.4 Adversarial attack on REV2
7.4.1 Experiment setting
In the REV2 experiments, we evaluate the effectiveness of the vicinage-attack by observing how trust propagates through the network. We focus on nodes with low fairness as our target nodes, assuming they would be motivated to avoid being labeled as anomalies or unfair. Consequently, attackers may attempt to enhance the trustworthiness of these nodes. Figure 8 shows the cumulative distribution function (CDF) of fairness. There is a gradual increase in the range (0.8, 0.9) and a steep rise in the range (0.9, 1). This suggests an opportunity for attackers to manipulate trust ranks. Target nodes T have fairness \(f(t) < 0.88\), while high-fairness nodes S have \(f(s) > 0.96\) and \(d(s) > d_{\text {threshold}}\). Figure 9 shows that the degree values cluster around \(d_{\text {threshold}}\).
Fig. 9
a Joint distribution of fairness and degree on REV2 in bitcoin-otc. b Joint distribution of fairness and degree on REV2 in bitcoin-alpha
×
7.4.2 Experiment results on REV2
We aim to identify preferential paths in REV2. The perturbation space includes both positive attacks and passive attacks, with interactions involving 1-hop and 2-hop neighbors. Figures 10, 11, and 12 show that the vicinage-attack method outperforms the baseline methods in finding the best perturbation edges. The caveat line in these figures indicates that 10% of nodes, with the lowest fairness, are considered unfair or anomalies.
Fig. 10
Compare vicinage with baseline on bitcoin-otc. The experimental results are obtained by taking the average value of five independent experiments
Fig. 11
Compare vicinage with baseline on bitcoin-alpha. The experimental results are obtained by taking the average value of five independent experiments
Fig. 12
Compare vicinage with baselines on bitcoin-alpha and bitcoin-otc. The experimental results are obtained by taking the average value of five independent experiments
×
×
×
When \(n < 4\): The vicinage-attack is more effective than both the indirect attack and modified indirect attack methods, demonstrating its efficiency with fewer iterations.
When \(n = 4\): The performance of the modified indirect attack approaches that of the vicinage-attack, suggesting that with enough iterations, it can be competitive, though it is still more time-consuming.
When \(n > 4\): The modified indirect attack becomes increasingly time-consuming with little improvement in performance, highlighting the inefficiency of exhaustive methods compared to the vicinage-attack.
The gradient-based approach of the vicinage-attack enables more efficient exploration of the perturbation space, allowing for quicker identification of strong ties and preferential paths, which are crucial for effective adversarial attacks on trust prediction systems.
Figures 13, 14, 15, and 16 provide additional results. We define four perturbation spaces: \(\Phi _{S,T}(B_0)\), \(\Phi _{S,T}(B_1)\), \(\Phi _{S,T}(B_2)\), and \(\Phi _{S,T}(B_3)\). These spaces involve edges connecting high-fairness nodes S to Succ(Pred(T)), Pred(Succ(T)), Succ(Succ(T)), and Pred(Pred(T)). We also derive subsets from these perturbation spaces, denoted as \(\Phi _{S,T}(B_4)\), \(\Phi _{S,T}(B_5)\), \(\Phi _{S,T}(B_6)\), and \(\Phi _{S,T}(B_7)\), as follows:
We also define two perturbation spaces for 1-hop neighbors: \(\Phi _{S,T}(B_8)\) and \(\Phi _{S,T}(B_9)\), which include edges connecting high-fairness nodes S to Pred(T) and Succ(T). We then derive two subsets: \(\Phi _{S,T}(B_{10})\) and \(\Phi _{S,T}(B_{11})\), defined as:
Preferential path analysis over 2-hop cases on bitcoin-otc. The rank below the caveat is regarded as unfair or anomaly nodes. The experimental results are obtained by taking the average value of five independent experiments
Fig. 14
Preferential path analysis over 2-hop cases on bitcoin-alpha. The experimental results are obtained by taking the average value of five independent experiments
Fig. 15
Preferential path analysis over 1-hop cases on bitcoin-otc. The experimental results are obtained by taking the average value of five independent experiments
Fig. 16
Preferential path analysis over 1-hop cases on bitcoin-alpha. The experimental results are obtained by taking the average value of five independent experiments
Fig. 17
Supplementary preferential path analysis over 2-hop cases on bitcoin-alpha from subsets of universe on constructed perturbation spaces
×
×
×
×
×
8 Related realm and application
Our research highlights the presence of preferential paths within trust systems, which introduces a bias in how trust is propagated. This has important implications for improving trust systems, especially in fields such as e-commerce, online reviews, and peer-to-peer networks. Additionally, our findings emphasize the need for vulnerability detection to identify and prevent adversarial attacks that exploit these preferential paths. Furthermore, preferential paths can be leveraged in trust chain discovery to uncover implicit trust relationships.
8.1 Vulnerability testing on trust systems
The preferential paths in trust systems can be seen as potential vulnerabilities. Adversarial techniques have been used to explore such vulnerabilities in graph-related tasks, such as backdoor attacks in graph classification [45‐48]. In a trust system, target nodes can be carefully chosen and labeled by administrators, allowing adversarial techniques to find the most critical paths that could be exploited. Our proposed vicinage-attack serves as a method to test these vulnerabilities. Reference [49] identifies three key conditions for adversarial attacks: stealthiness, consistency, and inconsistency.
- Stealthiness, denoted as \(\mathcal {S}(S,T)\), means that attacker nodes S can be several hops away from the target nodes T while still being effective in their attack. Defenders cannot easily distinguish between suspicious nodes and target nodes due to the limited number of injected edges, which form only a small part of the original graph.
- Consistency, denoted as \(\mathcal {C}(G_{0}, G_{\varepsilon })\), means that trust prediction results for most nontarget nodes remain stable or change only slightly after an attack. The attack is designed to target specific nodes, so the behavior of attackers may seem random but is actually purposeful.
- Inconsistency, denoted as \(\mathcal {I}(G_{0}, G_{\varepsilon })\), indicates that the trust prediction results for target nodes change significantly after an attack.
8.2 Trust chain discovery in trust systems
In this context, the perturbation space \(\Phi _{T}(B) \in G_{0}\) should represent a modified version of the original graph, focusing on edges that are indirectly connected to the target nodes. This technique, sometimes called an adversarial example [49‐52], incorporates preferential paths into the trust chain discovery process. By leveraging these paths, we can uncover hidden trust relationships within the network [53‐55]. This approach can be particularly useful in cases where explicit trust endorsements are lacking or where indirect relationships need to be assessed.
Moreover, our findings suggest that trust chain discovery involving preferential paths may extend beyond a static evaluation of trustworthiness. It can involve monitoring dynamic changes in trust relationships over time. Analyzing the influence along preferential paths can reveal variations in trust levels, helping to identify anomalies or adversarial manipulations in the network.
9 Limitation and future work
9.1 Limitation on scalability and generalization
Although the vicinage-attack strategy represents a significant improvement in adversarial attacks on trust prediction systems, there are some limitations. First, the complexity of finding preferential paths and executing vicinage-attacks increases as the network size grows. This can make it challenging to apply the method to large-scale social networks or online platforms with millions of nodes and edges. Second, the vicinage-attack has been specifically designed for FGA and REV2, and its effectiveness in other trust prediction algorithms has not been extensively tested. This limits the generalizability of our results to other types of trust prediction systems.
9.2 Future work on explainable defense mechanism
To overcome these limitations and advance the field, future work will involve splitting large graphs into subgraphs based on their density and sparsity. This approach will not only address scalability issues but also help in developing an explainable defense mechanism, as different subgraphs may show unique characteristics and vulnerabilities. Additionally, exploring graph neural networks (GNNs) could be valuable for handling large-scale networks. GNNs may provide new insights into preferential behaviors in the context of adversarial attacks and help improve overall defense strategies.
10 Conclusion
In this paper, we have identified the presence of preferential paths within trust systems and their significant impact on how trust is spread. Based on these findings, we have developed a new approach called the vicinage-attack. This method specifically targets edges along preferential paths to strengthen adversarial attacks. Our research advances the field of adversarial attack techniques and provides a deeper understanding of trust propagation patterns.
By highlighting the propagation bias in both FGA and REV2, we offer valuable insights that can help build more robust trust systems and improve defense mechanisms. This work paves the way for better understanding of adversarial attacks on trust systems, ultimately contributing to the security and reliability of online platforms and social networks.
Acknowledgements
This research was partly supported by the National Science Foundation of China (No. 62106210) and the Hong Kong Research Grant Council (No. PolyU25210821).
Declarations
Competing interests
The authors declare no competing interests.
Open Access This article is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License, which permits any non-commercial use, sharing, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if you modified the licensed material. You do not have permission under this licence to share adapted material derived from this article or parts of it. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by-nc-nd/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
is the case capable to generate perturbation on target node’s goodness, which is more likely to be strong tie.
are the cases cannot influence target node’s goodness. The positive and passive attack is in the view of attackers
is the case satisfies status theory while
is the case disobey status theory. In original datasets, for negative edges defy status theory, there are 3.725% in bitcoin-alpha and 5.727% in bitcoin-otc. For positive edges defy status theory, there are 47.168% in bitcoin-alpha and 46.084% in bitcoin-otc
means the case is more likely to be preferential path. \(\heartsuit \) means the case cannot be a preferential path because of empirical test. The positive and passive attack is in the view of target nodes
