Interpreting and explaining pagerank through argumentation semantics

Abstract

In this paper we show how re-interpreting PageRank as an argumentation semantics for a bipolar argumentation framework empowers its explainability. After showing that PageRank, naively re-interpreted as an argumentation semantics for support frameworks, fails to satisfy some generally desirable properties, we propose a novel approach able to reconstruct PageRank as a gradual semantics of a suitably defined bipolar argumentation framework, while satisfying these properties. We then show how the theoretical advantages afforded by this approach also enjoy an enhanced explanatory power: we propose several types of argument-based explanations for PageRank, each of which focuses on different aspects of the algorithm and uncovers information useful for the comprehension of its results.

Keywords

PageRank explainability gradual argumentation semantics quantitative bipolar argumentation frameworks

1 Introduction

In the context of search engines, a user wants to find the (web) pages that are the most relevant to a search query, potentially among millions of them. The web has an essential feature: each piece of information (page) may link to other pieces of information (through hyperlinks), and therefore the web organisation can be regarded as a directed graph, where pages correspond to nodes and links to edges. This is the idea that in 1999 inspired the revolutionary PageRank (PR) algorithm [1]: a method for computing a ranking score for every page based on the graph structure of the web. Given its conceptual simplicity and general formalisation for any kind of directed graph, PR has been applied to many other domains where entities can be evaluated on the basis of their connections to other entities, including citation networks [2], recommendation systems [3], chemistry [4], biology [5] and neuroscience [6], and has been studied from several viewpoints including an axiomatic characterisation from a social choice theory perspective [7].

Graph-based representations are also pervasive in the field of computational argumentation. In particular Dung’s abstract argumentation frameworks [8] are essentially directed graphs whose nodes are arguments and edges represent attacks. Dung’s seminal proposal has been subsequently extended in several directions, e.g. bipolar argumentation frameworks [9] encompass also a notion of support, while in quantitative bipolar argumentation frameworks [10] a base score is assigned to each argument. In this context, the argument graph structure is the basis of the assessment of argument acceptability according to some argumentation semantics [11]: in Dung’s traditional approach the evaluation is qualitative, while in further developments numerical argument assessments based on gradual semantics have been investigated [10, 12]. Given the similarity between PR and gradual argumentation semantics as formal tools producing a numerical assessment of connected entities in a graph, it appears that exploring possible cross-fertilisation opportunities between the two areas represents on its own an interesting research direction.

But drawing bridges between the two areas possesses not only theoretical yields. In fact, reconstructing PR in an argumentative perspective opens the door to the use of such a re-interpretation to generate explanations, exploiting in particular the graphical representation of the reasoning behind the algorithm. Explanations are crucial for the users of an algorithm such as PR: they may allow them to understand why the algorithm gives a certain output (e.g. attribution methods such as LIME [13] or SHAP [14]), to assess which components of the input led to different outcomes (e.g. contrastive explanations such as those proposed in [15]) or to identify which changes in the input could change the output (e.g. counterfactual explanations such as those proposed in [16]); for an overview see [17]. In particular, argumentation-based explanation techniques have been proposed for many AI methods, e.g., neural networks [18, 19], scheduling [20], Bayesian networks [21] and classifiers [22], query answering [23] and recommender systems [24].

In this paper we first explore how PR [1] can be directly interpreted, from an argumentation perspective, as a gradual semantics for support argumentation frameworks [25] in which pages are arguments and links are supports. We then evidence some limitations of this simplistic correspondence and propose

In a broader perspective, the contribution of the paper is two-fold. On one hand we define a new gradual semantics for QBAFs based on PageRank. On the other hand, we support the idea of using argumentation frameworks, not only to model dialectical debates, but also to describe the mechanism underpinning graph algorithms in order to present them in a dialectical form, with the main aim of generating explanations but possibly also enabling other practical applications.

The paper is organized as follows. In Section 2 we recall some background concepts on PR. In Section 3 we detail how PR can be directly interpreted as a gradual semantics in support argumentation frameworks, showing however that, as such, it does not satisfy some desirable properties for argumentation. In Section 4 we reconstruct PR as a gradual semantics of suitable QBAFs, achieving in this way the satisfaction of the above mentioned desirable properties. In Section 5 we first show the practical limitations of explanations based on the support argumentation framework introduced in Section 3 and then introduce four types of explanations for PR based on the gradual semantics of Section 4. In Section 6, using several datasets crawled from English and Irish universities’ websites and the Wikipedia dataset, we evaluate the different notions of explanations we introduced along several dimensions including size and cognitive tractability. We conclude the paper and outline lines of future work in Section 7.

This article builds upon [26] and [27]. In particular, Sections 2, 3 and 4 are adapted and revised from [26] and 5 and 6 extensively expand the preliminary results presented in [27].

2 PageRank background

We firstly recall the PR definition from the original paper [1], using a different but equivalent notation when necessary for our purposes.

We assume a set of pages/nodes $P = {u_{1}, \dots, u_{N}}$ and a set of links between the pages $L \subseteq P \times P$ , where $(u, v) \in L$ indicates that there is a link from page u to page v and we call the directed graph $〈 P, L 〉$ the web graph. We say $N = | P | > 0$ is the total number of pages, $O_{u} = {v \in P : (u, v) \in L}$ is the set of pages u points to and $I_{u} = {v \in P : (v, u) \in L}$ is the set of pages that point to u. We assume that $\forall u \in P, \neg! \exists (u, u) \in L$ , i.e. self-loops are ignored to prevent the manipulation of PR. We also assume that $\forall u \in P, | O_{u} | > 0$ , i.e. there are no dangling pages, that is, no pages without outgoing links (in practice, if such a page is found it is treated as having links towards all other pages as in [28]).

A random surfer model is used, which is based on the assumption that a user can either reach a page from a link in another page with probability d ∈]0 ; 1 [, referred to as damping factor, or land on a page directly with probability 1 - d.

Unless otherwise specified, we assume the value suggested in [1] of d = 0.85 and a uniform probability of directly landing on a page (i.e. we focus on non-personalized PR). In Section 7 we discuss how in future works these assumptions could be changed.

Definition 1. [1] The PageRank (PR) of a set of pages is an assignment $R : P \to] 0, 1]$ to the pages which satisfies: $R (u) = (1 - d) \cdot \frac{1}{N} + d \cdot \sum_{v \in I_{u}} \frac{R (v)}{| O_{v} |} \forall u \in P .$

Note that R is the solution of a system of linear equations derived from Definition 1 (we refer to R as both the assignment and the vector resulting from it). Notice also that, as described in [28], R is unique and ||R||₁ = 1, i.e. the L₁ norm of R is 1.

The aim of PR is to assign to every page a score that describes how relevant it is: the higher the score, the more important the page, since the score is intended to approximate the amount of users visiting the page. The latter is calculated through a mathematical model aiming at probabilistically estimating the number of user visits. The assumption here is therefore that the higher the number of links to (from) a page, the more it (the less each page linked by it, respectively) will be visited. Hence, the higher (lower, respectively) its PR score should be.

3 PageRank as a Gradual Semantics

In this section we show how PR may be interpreted directly as a gradual argumentation semantics and examine its ability to satisfy some desirable properties. First, we recall in Definition 2 some necessary formal notions from [10, 29].

Definition 2. A Quantitative Bipolar Argumentation Framework (QBAF) is a 4-tuple $〈 χ, R^{-}, R^{+}, τ$ , comprising:

a finite set of arguments χ,

a binary attack relation between arguments $R^{-} \subseteq χ \times χ$ ,

a binary support relation between arguments $R^{+} \subseteq χ \times χ$ ,

a total function $τ : χ \to 𝕀$ , with τ (α) the base score of α, where $𝕀$ is a set equipped with a preorder ≤ where, as usual, a < b denotes a ≤ b and b ≰ a.

Given a QBAF, a total function $σ : χ \to 𝕀$ , called a gradual semantics, may be used to assign a strength to each argument.

We define an sQBAF as a QBAF such that $R^{-} = \emptyset$ . Finally, we let $R^{-} (α) = {β \in χ : (β, α) \in R^{-}}$ and $R^{+} (α) = {β \in χ : (β, α) \in R^{+}}$ , and similarly $R^{-} (α) = {β \in χ : (α, β) \in R^{-}}$ and $R^{+} (α) = {β \in χ : (α, β) \in R^{+}}$ . Intuitively, the function σ is meant to provide an assessment of the strength of the arguments taking into account their initial base score τ and their relations with other arguments. Different forms of the function σ are appropriate in different argumentation contexts. In particular, we are interested in modeling web graphs in argumentative terms as follows.

A web graph $〈 P, L 〉$ can be interpreted as an sQBAF where the pages (nodes) are arguments and the links between them (edges) are supports, as follows.

Definition 3. Given a set of pages $P$ and a set of links $L, a$ PageRank Argumentation Framework (PRAF) is an sQBAF defined as $PR = 〈 χ, \emptyset, R^{+}, τ 〉$ , where:

$χ = P$ is the set of arguments corresponding to the set of pages,

$R^{+} = L$ is the set of supports corresponding to the set of links between pages,

$τ : χ \mapsto 𝕀 = [τ d, 1]$ is the base score, defined as a constant function describing the probability of a user directly landing on a page at random: $τ (α) = τ d \forall α \in χ .$

Given Definition 1 and the notes on loops and dangling nodes in Section 2, Remark 1 can be trivially derived.

Remark 1. Given a PRAF it always holds that:

each argument has at least one outgoing link: $| R^{+} (α) | > 0, \forall α \in χ$ ;

there are no self-supports: $\neg! \exists (α, α) \in R^{+}, \forall α \in χ$ .

We then interpret PR as a gradual semantics for sQBAFs.

Definition 4. The PageRank semantics is a gradual semantics $σ : χ \mapsto 𝕀$ such that: $σ (α) = τ (α) + d \cdot \sum_{β \in R^{+} (α)} \frac{σ (β)}{| R^{+} (β) |} \forall α \in χ .$

The following remark is directly derived from Definition 4.

Remark 2. The codomain of σ is $𝕀 = [τ d, 1]$

In order to formally assess PR as an argumentation semantics, we now review some desirable properties for argument strength, called group properties (GPs) in [10, 29], as they imply groups of other properties. Some preliminary definitions need to be recalled first. Given a QBAF $〈 χ, R^{-}, R^{+}, τ$ and a gradual semantics σ, for any A ⊆ χ, we refer to the multiset {σ (β) : β ∈ A} as A_σ. Given A, B ⊆ χ, A is strength equivalent to B, denoted $A \overset{σ}{=} B$ , iff A_σ = B_σ; A is at least as strong as B, denoted $A \overset{σ}{\geq} B$ , iff there exists an injective mapping f from B to A such that ∀α ∈ B, σ ( f (α)) ≥ σ (α); and A is stronger than B, denoted $A \overset{σ}{>} B$ , iff $A \overset{σ}{\geq} B$ and $B \overset{σ}{≱} A$ .

GPs are then defined as follows (some being reformulated in more general or more specific ways wrt [10, 29], where useful for our present purposes):

GP1. If $R^{-} (α) = \emptyset$ and $R^{+} (α) = \emptyset$ then σ (α) = τ (α).

GP2. If $R^{-} (α) \neq \emptyset$ and $R^{+} (α) = \emptyset$ then σ (α) < τ (α).

GP3. If $R^{-} (α) = \emptyset$ and $R^{+} (α) \neq \emptyset$ then σ (α) > τ (α).

GP4. If σ (α) < τ (α) then $R^{-} (α) \neq \emptyset$ .

GP5. If σ (α) > τ (α) then $R^{+} (α) \neq \emptyset$ .

GP6. If $R^{-} (α) \overset{σ}{=} R^{-} (β)$ , $R^{+} (α) \overset{σ}{=} R^{+} (β)$ and τ (α) = τ (β) then σ (α) = σ (β).

GP7. If $R^{-} B (α) ⊊ R^{-} B (β)$ , $R^{+} (α) \overset{σ}{=} R^{+} (β)$ and τ (α) = τ (β) then σ (β) < σ (α).

GP8. If $R^{-} (α) \overset{σ}{=} R^{-} (β)$ , $R_{σ}^{+} (α) ⊊ R_{σ}^{+} (β)$ and τ (α) = τ (β) then σ (α) < σ (β).

GP9. If $R^{-} (α) \overset{σ}{=} R^{-} (β)$ , $R^{+} (α) \overset{σ}{=} R^{+} (β)$ and τ (α) < τ (β) then σ (α) < σ (β).

GP10. If $R^{-} (α) \overset{σ}{<} R^{-} (β)$ , $R^{+} (α) \overset{σ}{=} R^{+} (β)$ and τ (α) = τ (β) then σ (β) < σ (α).

GP11. If $R^{-} (α) \overset{σ}{=} R^{-} (β)$ , $R^{+} (α) \overset{σ}{>} R^{+} (β)$ and τ (α) = τ (β) then σ (β) < σ (α).

In [10, 29], two general principles (and their strict counterparts) were also identified as a more synthetic way of describing the desirable (group) properties of a gradual semantics.

The intuition for the first principle is that a difference in an argument’s strength and base score must correspond to an imbalance in its attackers’ and supporters’ strengths.

Principle 1. [10, 29] A gradual semantics σ is balanced iff for any α ∈ χ:

if $R^{-} (α) \overset{σ}{=} R^{+} (α)$ then σ (α) = τ (α);

if $R^{-} (α) \overset{σ}{>} R^{+} (α)$ then σ (α) < τ (α);

if $R^{-} (α) \overset{σ}{<} R^{+} (α)$ then σ (α) > τ (α).

A gradual semantics σ is strictly balanced iff σ is balanced and for any α ∈ χ:

if σ (α) < τ (α) then $R^{-} (α) \overset{σ}{>} R^{+} (α)$ ;

if σ (α) > τ (α) then $R^{-} (α) \overset{σ}{<} R^{+} (α)$ .

In [10, 29] it is shown that if σ is balanced then it satisfies GP1 to GP3 and if it is strictly balanced then it satisfies GP1 to GP5.

The second principle requires that the strength of an argument depends monotonically on its base score and on the strengths of its attackers and supporters. To introduce this principle formally, we first recall the notion of shaping triple of an argument [10, 29], where for any α ∈ χ, the shaping triple of α is ( $τ (α), R^{+} (α), R^{-} (α))$ , denoted $S T α$ . Given α, β ∈ χ, $S T β$ is said to be: as boosting as $S T α$ , denoted as $S T α ⋍ S T β$ , iff τ (α) = τ (β), $R^{+} (α) \overset{σ}{=} R^{+} (β)$ , and $R^{-} (β) \overset{σ}{=} R^{-} (α)$ ; at least as boosting as $S T α$ , denoted as $S T α ⪯ S T β$ , iff τ (α) ≤ τ (β), $R^{+} (α) \overset{σ}{\leq} R^{+} (β)$ , and $R^{-} (β) \overset{σ}{\leq} R^{-} (α)$ ; or strictly more boosting than $S T α$ , denoted as $S T α ≺ S T β$ , iff $S T α ⪯ S T β$ and $S T β ⋠ S T α$ . (See [10, 29] for intuitions and illustrations.)

Principle 2. [10, 29] A gradual semantics σ is monotonic iff:

for any α, β ∈ χ, if $S T α ⋍ S T β$ then σ (α) = σ (β);

if $S T α ⪯ S T β$ then σ (α) ≤ σ (β).

A gradual semantics σ is strictly monotonic iff σ is monotonic and:

for any α, β ∈ χ, if $S T α ≺ S T β$ then σ (α) < σ (β).

In [10, 29] it is shown that if σ is (strictly) monotonic then it satisfies GP6 to GP11.

We will now show that the PR semantics σ satisfies some, but not all, of these desirable properties for gradual semantics. We will consider whether or not the properties are satisfied by the semantics σ when applied to a generic QBAF, in Propositions 1 and 2, or when applied to a PRAF (denoted as 〈PR, σ〉), in Propositions 3 and 4 (see Table 1 for a compact summary). Note that in the first case, if attacks are present in the QBAF, they are simply ignored by the definition of the semantics, and some of the properties may not hold for this mere reason.

Proposition 1. σ satisfies GP1, GP3, GP4, GP5 but not GP2, and thus is not balanced.

Proof. GP1 holds as when $R^{+} (α) = \emptyset$ , σ (α) = τ (α). GP3 and GP5 hold as σ (α) > τ (α) is true iff $\sum_{β \in R^{+} (α)} \frac{σ (β)}{| R^{+} (β) |} > 0$ that in turn is true iff $R^{+} (α) \neq \emptyset$ because if $\exists β \in R^{+} (α)$ then, by Remark 1, $| R^{+} (β) | > 0$ and, by Remark 2, σ (β) >0. GP4 holds because its preconditions cannot be verified: by Remark 2, ∀α ∈ χ, σ (α) ≥ τ (α). GP2 does not hold as when $R^{+} (α) = \emptyset$ , σ (α) = τ (α) independently of $R^{-} (α)$ , which is ignored in the definition of σ.□

Proposition 2. σ satisfies GP8 and GP9 but not GP6, GP7, GP10 and GP11, and thus is not monotonic.

Proof. GP8 holds as if τ (α) = τ (β) and $R_{σ}^{+} (α) \subset R_{σ}^{+} (β)$ and we assume by contradiction that σ (α) ≥ σ (β), then $\sum_{⋎ \in R^{+} (α)} \frac{σ (⋎)}{| R^{+} (⋎) |} \geq \sum_{⋎ \in R^{+} (β)} \frac{σ (⋎)}{| R^{+} (⋎) |}$ , but this is not possible, by Remark 2 because ¬ ! ∃ ⋎ such that σ (⋎) ≤0. GP9 holds because its preconditions cannot be verified: by Definition 3 τ is a constant, thus ¬ ! ∃ α, β ∈ χ : τ (α) ≠ τ (β). GP6: in the framework in Fig. 1, we have $R^{+} (β) \overset{σ}{=} R^{+} (δ)$ but σ (β) ≠ σ (δ). GP7 and GP10 cannot hold as attackers do not affect σ. GP11: in the framework in Fig. 1, we have $R^{+} (ζ) \overset{σ}{>} R^{+} (η)$ but σ (ζ) < σ (η).□

Fig. 1

Counter-example to GP6 and GP11 for the PR semantics σ in Proposition 2.

Proposition 3. 〈PR, σ〉 is strictly balanced and thus satisfies GP1 to GP5.

Proof. For balance, Point 1 holds as, by Definition 4, if $R^{+} (α) = \emptyset$ then σ (α) = τ (α). Point 2 holds trivially because its preconditions cannot be satisfied by an sQBAF since ¬ ! ∃ α such that $R^{+} (α) \overset{σ}{<} \emptyset$ . Points 3 and 5 hold as if $R^{+} (α) \overset{σ}{>} \emptyset$ then $R^{+} (α) \neq \emptyset$ and we already proved in Proposition 1 for GP3 and GP5 that σ (α) > τ (α) iff $R^{+} (α) \neq \emptyset$ . For strict balance, Point 4 holds because, by Remark 2, ¬ ! ∃ α such that σ (α) < τ (α).□

Proposition 4. 〈PR, σ〉 satisfies GP7 to GP10 but not GP6 or GP11 and thus is not monotonic.

Proof. GP6 and GP11 can be shown not to hold with the same counterexamples given in Proposition 2. GP8 and GP9 hold as, by Proposition 2, they hold for σ in general. GP7 and GP10 hold because their preconditions cannot be verified: ∀α ∈ χ, $R^{-} (α) = \emptyset$ , thus trivially $R^{-} (α) \overset{σ}{=} \emptyset$ .□

We have thus shown that directly interpreting PR as a gradual semantics for an sQBAF does not give rise to a satisfactory outcome in terms of formal properties. Indeed, while using PR as a semantics is somehow straightforward, it does not appear fully appropriate from a modeling perspective, as it does not provide a suitable argumentative counterpart to some key aspects of PR. In particular, note that, as a consequence of the PR definition, the strength of each node depends not only on the strengths of its supportersbut also on the cardinality of their outgoing supports. This has quite counter-intuitive effects from an argumentation perspective which could also affect explanations generated from this sQBAF. For example, consider the situation where two nodes have the same strength σ (α) = σ (β), but α has one outgoing support, while β has ten: the latter’s support to each of its children is actually ten times ‘less powerful’ (i.e. it transfers 1/10 of the strength) than the former’s. It follows that a node ⋎ supported by α only and a node δ supported by β only would have different strengths even if their supporters appear to be equivalent (formally the shaping triples of ⋎ and δ are the same).

This is the main reason for the lack of several desirable properties and calls for an alternative approach, which we introduce next.

4 PageRank as a gradual semantics in a meta-argumentation framework

In this section, we introduce an alternative approach to capture PageRank as an argumentation semantics. To this purpose we transform the sQBAF corresponding to a set of linked pages into a QBAF including additional meta-arguments and attacks between them. The underlying intuition is that each additional meta-argument can be understood as a vehicle of support from one page to another and that supports from the same page are in mutual conflict as they ‘compete’ in drawing strength from the same source.

In particular, as shown in Fig. 2, we add a meta-argument on every support relationship in the original PRAF, and all the meta-arguments supported by the same page attack each other. While the ‘regular’ arguments still represent the pages, these new meta-arguments correspond to the links between them. This increases the expressivity of the representation, as it includes attacks between the meta-arguments corresponding to links from the same page in order to describe the fact that they ‘compete’ for conveying strength, as mentioned above. As a consequence, the more links originating from the same page, the lower the strength transferred through each of them.

Fig. 2

Example of a transformation from a PRAF to an MPRAF.

Definition 5. Given a PRAF $PR = 〈 χ, \emptyset, R^{+}, τ 〉$ , the PageRank Meta-Argumentation Framework (MPRAF) derived from PR is a QBAF $〈 χ \cup M, {\hat{R}}^{-}, {\hat{R}}^{+}, \hat{τ} 〉$ , where:

$M = {m_{α, β} : (α, β) \in R^{+}}$ is the set of meta-arguments,

${\hat{R}}^{+} = {(α, m_{α, β}), (m_{α, β}, β) : α, β \in χ, m_{α, β} \in M}$ is the set of supports,

${\hat{R}}^{-} = {(m_{α, β}, m_{α, ⋎}) \in M \times M : (α, β), (α, ⋎) \in R^{+}}$ is the set of attacks,

$\hat{τ} : χ \cup M \mapsto \hat{𝕀} = [0, 1 [$ is the base score defined as the function: $\hat{τ} (α) = {\begin{matrix} 0 & if α \in M \\ τ d & if α \in χ . \end{matrix}$

Figure 2 illustrates the transformation of a PRAF into an MPRAF: the supports go from a ‘regular’ argument to another through an intermediate meta-argument. The following remarks illustrate some of the properties of MPRAFs $〈 χ \cup M, {\hat{R}}^{-}, {\hat{R}}^{+}, \hat{τ} 〉$ .

Remark 3. For any α ∈ χ, ${\hat{R}}^{-} (α) = \emptyset$ .

Remark 4. For any $m_{α, β} \in M$ , $\exists! α \in {\hat{R}}^{+} (m_{α, β})$ , $\exists! β \in {\hat{R}}^{+} Inverse (m_{α, β})$ , α ∈ χ and β ∈ χ.

Remark 5. For any $m_{α, β} \in M$ , $| {\hat{R}}^{-} (m_{α, β}) | + 1 = | R^{+} (α) | = | {\hat{R}}^{+} Inverse (α) |$ .

Remark 6. For any α ∈ χ such that $\exists! m_{α, β} : (α, m_{α, β}) \in {\hat{R}}^{+}$ , ${\hat{R}}^{-} (m_{α, β}) = \emptyset$ .

With reference to MPRAFs, we now define a gradual semantics $\hat{σ}$ , whose outcomes on ‘regular’ arguments coincide with the score produced by PR, as proved in Theorem 1.

Definition 6. The Meta-PageRank semantics (M-PR) is a gradual semantics $\hat{σ} : χ \cup M \mapsto \hat{𝕀}$ such that: $\hat{σ} (α) = \hat{τ} (α) + \sqrt{d} \cdot \frac{\sum_{β \in {\hat{R}}^{+} (α)} \hat{σ} (β)}{| {\hat{R}}^{-} (α) | + 1} \forall α \in χ \cup M .$

We now prove that, given a PRAF and corresponding MPRAF, for any α ∈ χ, the strength $\hat{σ} (α)$ according to Definition 6 is the same as the strength σ (α) according to Definition 4, i.e. to the PR score.

Theorem 1. (Equivalence of σ- $\hat{σ}$ ). Given a PRAF $〈 χ, \emptyset, R^{+}, τ 〉$ , denoted as PR, and the corresponding MPRAF $〈 χ \cup M, {\hat{R}}^{-}, {\hat{R}}^{+}, \hat{τ} 〉$ , denoted as $\hat{PR}$ , with the semantics σ for PR and $\hat{σ}$ for $\hat{PR}$ , for any argument α ∈ χ it holds that: $σ (α) = \hat{σ} (α)$

Proof. $\hat{σ} (α) = τ d + \sqrt{d} \cdot \frac{\sum_{⋎ \in {\hat{R}}^{+} (α)} \hat{σ} (⋎)}{| {\hat{R}}^{-} (α) | + 1}$ by Definition 6. By hypothesis α ∈ χ, thus if $⋎ \in {\hat{R}}^{+} (α)$ then $⋎ \in M$ , so we can rewrite ⋎ as m_β,α where $β \in R^{+} (α)$ . By the same hypothesis, we can derive, by Remark 3, that $| {\hat{R}}^{-} (α) = 0$ . This means that $\hat{σ} (α)$ can be rewritten as $τ d + \sqrt{d} \cdot \sum_{m_{β, α} \in {\hat{R}}^{+} (α)} \hat{σ} (m_{β, α})$ . Expliciting $\hat{σ} (m_{β, α})$ by Definition 6 and recalling that, by Definition 5, τ (m_β,α) =0 because m_β,α is a meta-argument, $\hat{σ} (α) = τ d +$ $+ \sqrt{d} \cdot \sum_{m_{β, α} \in {\hat{R}}^{+} (α)} (\sqrt{d} \cdot \frac{\sum_{β \in {\hat{R}}^{+} (m_{β, α})} \hat{σ} (β)}{| {\hat{R}}^{-} (m_{β, α}) | + 1})$ .

We recall that, by Remark 4, $\exists! β : β \in {\hat{R}}^{+} (m_{β, α})$ because $m_{β, α} \in M$ . Furthermore, we know by Remark 5 that $| {\hat{R}}^{-} (m_{β, α}) | + 1 = | R^{+} (β) |$ . Thus, $\hat{σ} (α) = τ d + d \cdot \sum_{m_{β, α} \in {\hat{R}}^{+} (α)} \frac{\hat{σ} (β)}{| R^{+} (β) |}$ . This is equivalent to $\hat{σ} (α) = τ d + d \cdot \sum_{β \in R^{+} (α)} \frac{\hat{σ} (β)}{| R^{+} (β) |} = σ (α)$ .□

Proposition 5 proves that the codomain of $\hat{σ}$ is $\hat{𝕀}$ .

Proposition 5. The codomain of $\hat{σ}$ on an MPRAF $〈 χ \cup M, {\hat{R}}^{-}, {\hat{R}}^{+}, \hat{τ} 〉$ is $\hat{𝕀} =] 0, 1]$ . Moreover, for any $α \in χ \cup M$ , if α ∈ χ then $\hat{σ} (α) \geq τ d$ , otherwise $\hat{σ} (α) > 0$ .

Proof. By Definition 6, $\hat{σ} (α)$ is the sum of $\hat{τ} (α)$ and positive values. Hence if α ∈ χ then $\hat{σ} (α) \geq τ d > 0$ . Otherwise, if $α \in M$ then, by Definitions 5 and 6, $\hat{σ} (α) = \sqrt{d} \cdot \frac{\sum_{β \in {\hat{R}}^{+} (α)} \hat{σ} (β)}{| {\hat{R}}^{-} (α) | + 1} \geq \sqrt{d} \cdot \sum_{β \in {\hat{R}}^{+} (α)} \hat{σ} (β)$ , and since β ∈ χ then $\hat{σ} (β) > 0 \forall β$ , hence $\hat{σ} (α) > 0$ . By Theorem 1 and by Remark 2, we have that if α ∈ χ then $\hat{σ} (α) \leq 1$ . Otherwise, if $α \in M$ then, by Remark 4, ${\hat{R}}^{+} (α) = {β}$ and β ∈ χ, hence by Definition 6, $\hat{σ} (α) = \sqrt{d} \cdot \frac{\hat{σ} (β)}{| {\hat{R}}^{-} (α) | + 1} \leq 1$ .□

The next proposition sheds light on the intuition behind our MPRAFs, in that the support from non-meta-arguments is partitioned among the meta-arguments. Meta-arguments supported by the same ‘regular’ argument all have the same strength since according to the random surfer model the probability of clicking on links is uniform.

Proposition 6. In an MPRAF $〈 χ \cup M, {\hat{R}}^{-}, {\hat{R}}^{+}, \hat{τ} 〉$ , if a meta-argument $α \in M$ has attackers then $\hat{σ} (α) = \hat{σ} (⋎), \forall ⋎ \in {\hat{R}}^{-} (α)$ .

Proof. By Definition 5, $\forall ⋎ \in {\hat{R}}^{-} (α)$ $⋎ \in M$ and by Definition 5 and Remark 4 $\forall ⋎ \in {\hat{R}}^{-} (α)$ ${\hat{R}}^{+} (α) = {\hat{R}}^{+} (⋎) = {β}$ where β ∈ χ is the single supporter of α. By Definition 6, $\hat{σ} (α) = \hat{τ} (α) + \sqrt{d} \cdot \frac{\sum_{β \in {\hat{R}}^{+} (α)} \hat{σ} (β)}{| {\hat{R}}^{-} (α) | + 1}$ , and by Definition 5 and Remark 4, $\hat{σ} (α) = \sqrt{d} \cdot \frac{\hat{σ} (β)}{| {\hat{R}}^{-} (α) | + 1}$ , and the same is true for any $⋎ \in {\hat{R}}^{-} (α)$ : $\hat{σ} (⋎) = \sqrt{d} \cdot \frac{\hat{σ} (β)}{| {\hat{R}}^{-} (⋎) | + 1}$ . By construction α and the elements of ${\hat{R}}^{-} (α)$ all attack each other, thus $| {\hat{R}}^{-} (α) | = | {\hat{R}}^{-} (⋎) |$ $\forall ⋎ \in {\hat{R}}^{-} (α)$ , and the result follows.□

We now assess this framework and semantics with respect to the desirable properties.

Proposition 7. $\hat{σ}$ satisfies GP1, GP4, GP5, GP6, GP8, GP9 and GP11.

Proof. GP1: by Definition 6, if ${\hat{R}}^{+} (α) = \emptyset$ and ${\hat{R}}^{-} (α) = \emptyset$ then the second term of the sum is always 0, therefore σ (α) = τ (α). GP4 holds because the GP’s preconditions cannot be verified: by Proposition 5, ∀α ∈ χ $\hat{σ} (α) \geq \hat{τ} (α)$ . GP5: by Definition 6, $\hat{σ} (α) > \hat{τ} (α)$ iff $\sum_{β \in {\hat{R}}^{+} (α)} \hat{σ} (β) > 0$ . Thus, it must be the case that $\exists β \in {\hat{R}}^{+} (α) : \hat{σ} (β) > 0$ , therefore ${\hat{R}}^{+} (α) \neq \emptyset$ GP6 follows directly from Definition 6. GP8: if ${\hat{R}}^{-} (α) \overset{σ}{=} {\hat{R}}^{-} (β)$ then $| {\hat{R}}^{-} B (α) | = | {\hat{R}}^{-} B (β) |$ and if ${\hat{R}}^{+} B (α) ⊊ {\hat{R}}^{+} B (β)$ then $\sum_{⋎ \in {\hat{R}}^{+} (α)} \hat{σ} (⋎) < \sum_{⋎ \in {\hat{R}}^{+} (β)} \hat{σ} (⋎)$ . The result follows from Definition 6. GP9: if ${\hat{R}}^{-} (α) \overset{σ}{=} {\hat{R}}^{-} (β)$ then $| {\hat{R}}^{-} B (α) | = | {\hat{R}}^{-} B (β) |$ and if ${\hat{R}}^{+} (α) \overset{σ}{=} {\hat{R}}^{+} (β)$ then $\sum_{⋎ \in {\hat{R}}^{+} (α)} \hat{σ} (⋎) = \sum_{⋎ \in {\hat{R}}^{+} (β)} \hat{σ} (⋎)$ . The result follows from Definition 6. GP11: if ${\hat{R}}^{-} (α) \overset{σ}{=} {\hat{R}}^{-} (β)$ then $| {\hat{R}}^{-} B (α) | = | {\hat{R}}^{-} B (β) |$ and if ${\hat{R}}^{+} (α) \overset{σ}{>} {\hat{R}}^{+} (β)$ then $\sum_{⋎ \in {\hat{R}}^{+} (α)} \hat{σ} (⋎) > \sum_{⋎ \in {\hat{R}}^{+} (β)} \hat{σ} (⋎)$ . The result follows from Definition 6.□

Proposition 8. $〈 \hat{PR}, \hat{σ} 〉$ is balanced and thus satisfies GP1 to GP3. However, $〈 \hat{PR}, \hat{σ} 〉$ is not strictly balanced.

Proof. For balance, Point 1: (A) If ${\hat{R}}^{-} (α) \overset{σ}{=} {\hat{R}}^{+} (α) = \emptyset$ then the result follows by Definition 6. (B) Otherwise, if ${\hat{R}}^{-} (α) \neq \emptyset$ then $α \in M$ and thus it has a single supporter β. There are two possible scenarios, which turn out to be impossible, as they contradict the hypothesis. (B.i) $\exists! ⋎ \in M : (β, α), (β, ⋎) \in {\hat{R}}^{+}$ , then we get ${β} = {\hat{R}}^{+} (α) \overset{σ}{>} {\hat{R}}^{-} (α) = {⋎}$ (which contradicts the hypothesis) because by Definition 6 $\hat{σ} (α) = \hat{σ} (⋎) < \hat{σ} (β)$ (B.ii) $\exists_{> 1} ⋎_{1}, . . ., ⋎_{n} \in M : (β, α), (β, ⋎_{1}), . . ., (β, ⋎_{n}) \in {\hat{R}}^{+}$ , hence $| {\hat{R}}^{-} (α) | > 1$ , therefore it cannot hold that ${⋎_{1}, . . ., ⋎_{n}} = {\hat{R}}^{-} (α) \overset{σ}{=} {\hat{R}}^{+} (α) = {β}$ , since by Definition 6 it holds again $\hat{σ} (α) = \hat{σ} (⋎_{1}) = . . . = \hat{σ} (⋎_{n}) < \hat{σ} (β)$ , hence there cannot be any injective mapping $f : {\hat{R}}^{-} (α) \to {\hat{R}}^{+} (α) : \forall α \in {\hat{R}}^{-} (α), σ (f (α)) \geq σ (α)$ , and thus there is no strength-equivalence relationship between ${\hat{R}}^{-} (α)$ and ${\hat{R}}^{+} (α)$ , contradicting the hypothesis. Point 2. For ${\hat{R}}^{-} (α) \overset{σ}{>} {\hat{R}}^{+} (α)$ to hold ${\hat{R}}^{-} (α) \neq \emptyset$ , thus $α \in M$ . Hence, we are in the same situation of (B) in the proof of Point 1, and therefore the precondition cannot hold and the result follows. Point 3. By Proposition 5, $\hat{σ} (α) > 0$ and if ${\hat{R}}^{-} (α) \overset{σ}{<} {\hat{R}}^{+} (α)$ then ${\hat{R}}^{+} (α) \neq \emptyset$ . Hence by Definition 6, $\hat{σ} (α) > \hat{τ} (α)$ , thus $〈 \hat{PR}, \hat{σ} 〉$ is balanced. For strict balance, Point 4 holds because $\neg! \exists α : \hat{σ} (α) < \hat{τ} (α)$ . But, Point 5 does not hold. For example, consider the framework in Fig. 2.b and in particular $m_{α, ⋎} \in M$ that it is supported by α ∈ χ and attacked by $m_{α, β}, m_{α, δ} \in M$ . By Definition 5 and Proposition 5, we have that $\hat{σ} (m_{α, ⋎}) \leq \hat{σ} (α)$ and $\hat{σ} (m_{α, ⋎}) = \hat{σ} (m_{α, β}) = \hat{σ} (m_{α, δ}) > 0$ . Hence, $\hat{σ} (m_{α, ⋎}) > \hat{τ} (m_{α, ⋎})$ , but ${\hat{R}}^{+} (m_{α, ⋎}) \overset{σ}{≱} {\hat{R}}^{-} (m_{α, ⋎})$ because no injective mapping exists from ${\hat{R}}^{-} (m_{α, ⋎})$ to ${\hat{R}}^{+} (m_{α, ⋎})$ . Thus ${\hat{R}}^{+} (m_{α, ⋎}) \overset{σ}{≯} {\hat{R}}^{-} (m_{α, ⋎})$ and therefore $〈 \hat{PR}, \hat{σ} 〉$ is not strictly balanced.□

Proposition 9. $〈 \hat{PR}, \hat{σ} 〉$ is strictly monotonic and thus satisfies GP6 to GP11.

Proof. Point 1: if ${\hat{R}}^{-} (α) \overset{σ}{=} {\hat{R}}^{-} (β)$ then $| {\hat{R}}^{-} (α) | = | {\hat{R}}^{-} (β) |$ and if ${\hat{R}}^{+} (α) \overset{σ}{=} {\hat{R}}^{+} (β)$ then $\sum_{⋎ \in {\hat{R}}^{+} (α)} \hat{σ} (⋎) = \sum_{⋎ \in {\hat{R}}^{+} (β)} \hat{σ} (⋎)$ . The result follows from Definition 6. Point 3: if α, β ∈ χ then $\hat{τ} (α) = \hat{τ} (β)$ and ${\hat{R}}^{-} (β) \overset{σ}{=} {\hat{R}}^{-} (α) = \emptyset$ , hence $| {\hat{R}}^{-} (α) | = | {\hat{R}}^{-} (β) |$ . If ${\hat{R}}^{+} (α) \overset{σ}{<} {\hat{R}}^{+} (β)$ then $\sum_{⋎ \in {\hat{R}}^{+} (α)} \hat{σ} (⋎) < \sum_{⋎ \in {\hat{R}}^{+} (β)} \hat{σ} (⋎)$ . Thus, by Definition 6, $\hat{σ} (α) < \hat{σ} (β)$ . If $α \in M$ and β ∈ χ then $\hat{τ} (α) < \hat{τ} (β)$ and ${\hat{R}}^{-} (β) = \emptyset$ . If ${\hat{R}}^{-} (α) \overset{σ}{\geq} \emptyset$ then $| {\hat{R}}^{-} (α) | \geq | {\hat{R}}^{-} (β) | = 0$ . If ${\hat{R}}^{+} (α) \overset{σ}{\leq} {\hat{R}}^{+} (β)$ then $\sum_{⋎ \in {\hat{R}}^{+} (α)} \hat{σ} (⋎) \leq \sum_{⋎ \in {\hat{R}}^{+} (β)} \hat{σ} (⋎)$ . Thus, by Definition 6, $\hat{σ} (α) < \hat{σ} (β)$ . If $α, β \in M$ then $\hat{τ} (α) = \hat{τ} (β)$ . If ${\hat{R}}^{-} (β) \overset{σ}{\leq} {\hat{R}}^{-} (α)$ then $| {\hat{R}}^{-} (α) | \geq | {\hat{R}}^{-} (β) |$ . If ${\hat{R}}^{+} (α) \overset{σ}{\leq} {\hat{R}}^{+} (β)$ then $\sum_{⋎ \in {\hat{R}}^{+} (α)} \hat{σ} (⋎) \leq \sum_{⋎ \in {\hat{R}}^{+} (β)} \hat{σ} (⋎)$ . Hence, by Definition 6, $\hat{σ} (α) \leq \hat{σ} (β)$ . For $S T β ⋠ S T α$ to hold, either:

${\hat{R}}^{-} (β) \overset{σ}{<} {\hat{R}}^{-} (α)$ and ${\hat{R}}^{+} (α) \overset{σ}{=} {\hat{R}}^{+} (β)$ , or

${\hat{R}}^{-} (β) \overset{σ}{=} {\hat{R}}^{-} (α)$ and ${\hat{R}}^{+} (α) \overset{σ}{<} {\hat{R}}^{+} (β)$ , or

${\hat{R}}^{-} (β) \overset{σ}{<} {\hat{R}}^{-} (α)$ and ${\hat{R}}^{+} (α) \overset{σ}{<} {\hat{R}}^{+} (β)$ .

In the first case, by construction of the framework PR,

| {\hat{R}}^{-} (α) | < | {\hat{R}}^{-} (β) |

, thus

\hat{σ} (α) < \hat{σ} (β)

. In the second case,

\sum_{⋎ \in {\hat{R}}^{+} (α)} \hat{σ} (⋎) < \sum_{⋎ \in {\hat{R}}^{+} (β)} \hat{σ} (⋎)

, thus

\hat{σ} (α) < \hat{σ} (β)

. In the third case,

\sum_{⋎ \in {\hat{R}}^{+} (α)} \hat{σ} (⋎) < \sum_{⋎ \in {\hat{R}}^{+} (β)} \hat{σ} (⋎)

and

| {\hat{R}}^{-} (α) | \leq | {\hat{R}}^{-} (β) |

, thus

\hat{σ} (α) < \hat{σ} (β)

. Point 3 implies Point 2, thus the result follows.□

Table 1

Satisfaction (✓) or not (×) of GPs and principles (Balance, Strict Balance, Monotonicity, Strict Monotonicity) by σ, 〈PR, σ〉, $\hat{σ}$ and $〈 \hat{PR}, \hat{σ} 〉$

	GP1	GP2	GP3	GP4	GP5	GP6	GP7	GP8	GP9	GP10	GP11	B	SB	M	SM
σ	✓	×	✓	✓	✓	×	×	✓	✓	×	×	×	×	×	×
〈PR, σ〉	✓	✓	✓	✓	✓	×	✓	✓	✓	✓	×	✓	✓	×	×
$\hat{σ}$	✓	×	×	✓	✓	✓	×	✓	✓	×	✓	×	×	×	×
$〈 \hat{PR}, \hat{σ} 〉$	✓	✓	✓	✓	✓	✓	✓	✓	✓	✓	✓	✓	×	✓	✓

We have thus proven that, through MPRAF, in exchange for a little structural addition, it is possible to ensure equivalence with PR while at the same time satisfying more desirable properties from an argumentation semantics perspective.

Table 1 shows a summary of the properties that the M-PR semantics applied on MPRAFs satisfies, including in particular monotonicity. This means that, from a dialectical viewpoint, the strength of an argument depends exclusively on its intrinsic strength, the reasons supporting it and the reasons against it, and any strengthening/weakening of these will affect the argument’s strength in an intuitive way.

The satisfaction of monotonicity is achieved through the role ascribed to meta-arguments and is a key factor for exploiting MPRAFs for practical applications, such as the generation of intuitive explanations of the PR score of a page. In this scenario, monotonicity is clearly a crucial factor because it allows a user to identify direct dependencies between the strengths of arguments according to the attacks and supports linking them in the graph structure of the MPRAF.

5 Argumentation-based explanations for PageRank

In this section we first evidence the limits of argumentative explanations for PR based on PRAFs and propose several novel explanations utilising the QBAF with meta-arguments introduced in Section 4. In particular we will consider explanations allowing the user to understand the reasons for a given PR score, providing hints on changes that can improve the score, or giving warnings on strong dependencies of the score on other pages. Throughout this section we assume as given a PRAF $〈 χ, \emptyset, R^{+}, τ 〉$ and its MPRAF counterpart $〈 χ \cup M, {\hat{R}}^{-}, {\hat{R}}^{+}, \hat{τ} 〉$ . For ease of comprehension, we will also propose some examples generated from the Wikipedia web graph that we will introduce in more detail in Section 6.

5.1 Types of explanations: singular explanations and plural explanations

Explanations may have different scopes and levels of abstraction. In this paper, we focus on local explanations concerning the score of a page or a group of pages, rather than global explanations concerning the overall PR score assignment. In particular, we consider two families of explanations:

singular explanations concerning the score of a single page, and

plural explanations concerning the scores of a set of pages.

We understand a singular explanation as a set of (meta-)arguments in the PRAF or in the MPRAF, accompanied by a function describing their importance w.r.t. the page whose score is explained.

Definition 7. A singular explanation for a page α ∈ χ is a pair $E (α) = (E, i)$ where:

$E \subseteq χ \cup M$ is the set of explaining arguments, and

$i : E \mapsto ℝ$ is the importance function.

In the case of plural explanations, the explanation concerns the scores of a set of pages: for each of these pages a set of explaining arguments is given and a function describes the importance of all explaining arguments.

Definition 8. A plural explanation for a set of pages A ⊆ χ is a pair $E (A) = ({E_{α} : α \in A}, i)$ where:

$E_{α} \subseteq χ \cup M$ is the set of explaining arguments for any page α ∈ A, and

$i : ⋃_{α \in A} E_{α} \mapsto ℝ$ is the importance function.

We will consider several instances of singular explanations and plural explanations, obtained by specific choices of explaining arguments and importance functions, drawn from the underlying PRAF or MPRAF.

5.2 PRAF-based explanations

Consider the problem of identifying which pages have a major role in determining the score of a given page one is interested in. If we were to answer this query using only PRAFs we could return the set of supporters of the page of interest : we call this form of explanation a basic explanation, in that it is solely based on the PRAF.

Definition 9. A basic explanation for page α ∈ χ is a singular explanation $E_{\leftarrow} (α) = (R^{+} (α), σ)$ .

Basic explanations essentially provide a magnification of the original PRAF focused on an argument (page) and its supporters (pages linking to it, whose importance coincides with their score). The result is an explanation like the one presented in Fig. 3.i. Here, the score of the page Nguyen Dynasty is explained showing its supporters, with each page score being represented by the size of the relevant bubble. Notice how, looking at this basic explanation, a user might (erroneously) deduce that the score of Nguyen Dinasty is mostly determined by Official Residence, which is actually not the case (due to the high number of outgoing links from Official Residence). Thus, basic explanations have clear limitations. The extent to which basic explanations could be misleading can be quite large, as shown by the excerpt of the MPRAF in Fig. 3.ii, where we can see how the actual contributions of the supporters of Nguyen Dinasty (the opaque bubbles) compare with their strengths (transparent bubbles).

Fig. 3

Transition, for the Wikipedia article Nguyen Dynasty, from its basic explanation (i), to the excerpt of the QBAF including it and its supporters, to eventually its attribution explanation (iii). Each bubble represents an argument and its size is proportional to the strength of the argument. In (ii) the opaque bubbles highlight the actual contribution of an argument to the Nguyen Dynasty page. Labels - and + indicate, respectively, attacks and supports.

In fact, basic explanations of this kind answer the question ‘Which are the pages with the highest score with a link to a page p?’ but this is different from answering the question ‘Which are the pages with the highest contribution to the score of a page p?’ or, more concisely, ‘Why does page p have this score?’. To answer this question using the PRAF representation a user should both have a deeper understanding of how PR works and be shown a larger part of the PRAF, including all the pages linked by the supporters of the considered page. Only then might the user realise that Hue, instead of Official Residence, is the Wikipedia article providing most support to Nguyen Dynasty.

5.3 MPRAF-based explanations

Attribution explanation. The unsuitability of PRAFs as explanatory tools can be overcome by attribution explanations based on MPRAFs that focus the attention of the user only on the meta-arguments supporting the page of interest, thus truly answering the question ‘Why does page p have this score?’.

Definition 10. An attribution explanation for page α ∈ χ is a singular explanation $E_{\leftarrow} (α) = (R^{+} (α), \hat{σ})$ .

Figure 3.iii, shows an example of an attribution explanation for the Wikipedia article Nguyen Dynasty as an excerpt of the QBAF comprising the argument of Nguyen Dynasty and its supporting meta-arguments. Intuitively, the strength assigned to each meta-argument by our novel semantics corresponds to the support actually flowing from one page to another. In this representation it is clear that the contribution of Hue to the score of Nguyen Dynasty is bigger than that of Official Residence, despite the former’s lower PR score.

Besides better supporting explanations of the reasons behind the PR of a page, attribution explanations appear to enable answering other kinds of user queries, like counterfactual questions of the kind: ‘What would happen if a given link is suppressed?’. In this context, meta-arguments’ strengths directly show an approximation 1 of the portion of the score that a page would lose if a link were removed. For example, in the attribution explanation in Fig. 3.iii, if we remove from the supporters of Nguyen Dynasty the page Hue then its PR will reduce considerably since Hue is the supporter contributing the most to the strength of Nguyen Dynasty.

Although the full set of meta-arguments potentially included in attribution explanations of a page may be very large (in the order of hundreds) we will show in Section 6 that considering only a limited subset is enough to produce a satisfactory explanation. This means that our explanations fulfil the desideratum of simplicity, avoiding overwhelming the user with too much information when the number of supporters is large.

Contrastive attribution explanation. When two (or more) pages have many shared supporters, understanding why the pages have different scores through attribution explanations is not trivial. Contrastive attribution explanations tackle this issue: given a set of pages of interest they show for each of them the nodes contributing exclusively to its score, ignoring the ones they share. Thus, these explanations answer questions of the kind: ‘Which are the links that make pages p and q have different scores?. Explanations of this kind find their typical usage scenario in the assessment of the reasons behind a page having a higher (or lower) score than other pages, comparing their non-shared supporters sorted by their strengths.

Definition 11. A Contrastive attribution explanation for a set of pages A ⊆ χ is a plural explanation $E_{\leftrightarrow} (A) = ({{\hat{R}}_{\ A}^{+} (α) : α \in A}, \hat{σ})$ where ${\hat{R}}_{\ A}^{+} (α)$ is the set of exclusive supporters of α in A i.e., ${\hat{R}}_{\ A}^{+} (α) = {\hat{R}}^{+} (α) \ {m_{β, α} \in {\hat{R}}^{+} (α) : β \in ⋃_{⋎ \in A \ {α}} R^{+} (⋎)}$ .

Figure 4 shows an example of a Contrastive attribution explanation for the Wikipedia articles Calorimeter and Spectrophotometer. Using this explanation, users can focus on the differences in the supporters of two pages rather than on their common supporters, which in this example amount to 40 nodes. As we will show in Section 6, the number of shared supporters typically increases if one of the two pages supports the other, and even more so if they mutually support each other.

Fig. 4

Contrastive attribution explanation for the Wikipedia articles Calorimeter and Spectrophotometer from the Wikipedia dataset. The size of the bubbles is proportional to the arguments’ strengths. The bubble labeled SHARED encompasses the contributions from the 40 shared supporters.

Additive counterfactual explanations. This form of explanation extends our effort in answering counter-factual questions in that additive counterfactual explanations provide the user with information on links, not currently present, that if added would increase the score of a page of interest. These explanations answer the question ‘To which pages could a link to p be added to maximize the increment of its score?’. A typical usage scenario of this explanation is searching for pages that could be modified to increase the score of a specific page.

In order to formally define additive counter-factual explanation we will now introduce the definition of the MPRAF with a link addition or removal.

Definition 12. Given two arguments α, β ∈ χ, then: if $(α, β) \notin R^{+}$ , we define the PRAF with the addition of the support (α, β), denoted by PR_+(α,β), as $〈 χ, \emptyset, R_{+ (α β)}^{+}, τ 〉$ where $R_{+ (α β)}^{+} = R^{+} \cup {(α, β)}$ .

We denote with ${\hat{PR}}_{+ (α β)}$ , ${\hat{σ}}_{+ (α β)}$ the MPRAF corresponding to PR_+(α,β) and the semantics $\hat{σ}$ on ${\hat{PR}}_{+ (α β)}$ , respectively.

We now formally define additive counter-factual explanations.

Definition 13. An additive counter-factual explanation for page β is a singular explanation $E_{\leftrightarrow} (β) = ({\hat{R}}_{2}^{+} (β), {\hat{σ}}_{+ (α β)})$ where ${\hat{R}}_{2}^{+} (α)$ is the set of meta-arguments that are not supporters of α or supported by α with backward hop-distance of 2 from α, i.e., ${\hat{R}}_{2}^{+} (α) = {m_{x, α} : x \notin R^{+} (α) \land x \notin R^{+} (α) \land x \in ⋃_{β \in R^{+} (α)} R^{+} (β)}$ .

Note that, in principle, the set of pages from which one could draw an additional link is potentially very large, thus some restriction is needed, also to ensure that the considered additions are somehow meaningful. For this reason, for this form of explanation to be useful in practice, we opted to include only meta-arguments (links) from pages with backward hop-distance of 2 to the page of interest in the web graph. As we will show in Section 6 this allowed us to select a smaller but “more relevant” portion of meta-arguments.

Figure 5.i shows an example of this type of explanation for the Wikipedia article Aztec Empire, visualizing the 10 most (potentially) influential meta-arguments (selected from 515).

Fig. 5

Additive counter-factual explanation for the Wikipedia article Aztec Empire (i) and edit-sensibility counterfactual explanation for the Wikipedia article Rate (Mathematics) (ii). Sizes are proportional to the arguments’ strengths for blue bubbles, and to the importance of the meta-arguments according to the form of explanation for the red and purple bubbles.

Edit-sensibility counterfactual explanation. While an additional incoming link positively affects the newly linked page, this addition will negatively affect the score of all the other pages linked by the same source. Edit-sensibility counterfactual explanations aim to inform the user about this aspect, giving information on how sensitive the score of a page is to changes in the supporting pages. This type of explanation answers the question ‘If an outgoing link is added to page q (a supporter of page p), how much will the score of p change?’.

To formally define edit-sensibility counterfactual explanations we first define the concept of the sensitivity of an argument, describing the extent to which a page is susceptible to the change of its supporters.

Definition 14. Given α, β, δ ∈ χ, $(α, β) \notin R^{+}$ , and $(α, δ) \in R^{+}$ , the sensitivity to addition of node $m_{α, δ} \in M$ is defined as: $φ (m_{α, δ}) = \hat{σ} (m_{α, δ}) - {\hat{σ}}_{+ (α β)} (m_{α, δ})$

We can now define edit-sensibility counterfactual explanations.

Definition 15. An edit-sensibility counterfactual explanation for page α is a singular explanation $\underset{\leftarrow}{\underset{Φ ?}{E}} (α) = ({\hat{R}}^{+} (α), φ)$ .

Essentially, this form of explanation highlights how much a page score is “exposed” to endogenous changes in the “link structure” of other pages. Figure 5.ii shows an example of this explanation for the Wikipedia article Rate (Mathematics). Here, the sizes of the supporting meta-arguments (including that of the page Rate (Mathematics)) are proportional to the sensitivity to addition (φ), that is the score loss that they would experience if another outgoing link were to be added to their parent page. This means that, for instance, a single new link from the Wikipedia article Ratio to another page would significantly change the PageRank score of Rate (Mathematics), reducing it by almost 20%.

5.4 Computational approximations of explanations

The counterfactual explanations that we introduced require the values of ${\hat{σ}}_{+ (α β)}$ to be computed. In particular, to generate the explanations for a node, the PR scores of the supporters of the node have to be assessed on the web graph with a single link changed, a computationally expensive operation that should be avoided when not necessary. To this purpose, with Proposition 10 we show that, under certain assumptions, it is not necessary to re-run PR on the whole web graph to compute the values of ${\hat{σ}}_{+ (α β)}$ .

Figure 6 provides a graphical support to the proposition. It shows the relationships between the nodes α, β and δ_i used in the proposition itself and in its proof.

Fig. 6

Excerpt of an argumentation framework in support of the proof of Proposition 10. Red and blue arrows represent, respectively, attacks and supports; orange and violet represent, respectively, additional attacks and supports; grey arrows highlight forbidden paths. n_c is the number of children of α.

Proposition 10. For ${\hat{PR}}_{+ (α β)}$ and $\forall δ_{i} \in R^{+} (α)$ it holds that:

$| {\hat{R}}^{-} Plus (m_{α, δ_{i}}) | = | {\hat{R}}^{-} (m_{α, δ_{i}}) | + 1$ .

If there is no support path 2 from β to α it holds that ${\hat{σ}}_{+ (α β)} (m_{α, δ_{i}}) =$ $= \hat{σ} (m_{α, δ_{i}}) - \frac{\hat{σ} (m_{α, δ_{i}})}{| {\hat{R}}^{-} (m_{α, δ_{i}}) | + 2}$

If there is no support path also from β to δ then it holds that ${\hat{σ}}_{+ (α β)} (δ_{i}) =$ $= \hat{σ} (δ_{i}) - d \cdot \frac{\hat{σ} (α)}{| {\hat{R}}^{-} (m_{α, δ_{i}}) | \cdot (| {\hat{R}}^{-} (m_{α, δ_{i}}) | + 1)}$

Proof. Point 1. By Definition 5, it is immediate that $\forall δ_{i} \in R^{+} (α), | {\hat{R}}^{-} Plus (m_{α, δ_{i}}) | = | {\hat{R}}^{-} (m_{α, δ_{i}}) | + 1$ . Point 2. Given that, by Remark 3, α does not have any attacker and that there is no support path from β to α then the strength value $\hat{σ} (α)$ does not change when adding (α, β) to $R^{+}$ because by Definition 6 $\hat{σ} (α)$ depends only on the strengths of its supporters and attackers. Thus, given Definition 6 and Remark 4 (meta-arguments only have a single support), we can write $\hat{σ} (m_{α, δ_{i}}) = \sqrt{d} \cdot \frac{\hat{σ} (α)}{| {\hat{R}}^{-} (m_{α, δ_{i}}) | + 1}$ and ${\hat{σ}}_{+ (α β)} (m_{α, δ_{i}}) = \sqrt{d} \cdot \frac{\hat{σ} (α)}{| {\hat{R}}^{-} Plus (m_{α, δ_{i}}) | + 1}$ . Now isolating $\hat{σ} (α)$ from the former and substituting it back into the latter we get ${\hat{σ}}_{+ (α β)} (m_{α, δ_{i}}) = \hat{σ} (m_{α, δ_{i}}) \cdot \frac{| {\hat{R}}^{-} (m_{α, δ_{i}}) | + 1}{| {\hat{R}}^{-} Plus (m_{α, δ_{i}}) | + 1}$ . Using what we just proved in point 1 then ${\hat{σ}}_{+ (α β)} (m_{α, δ_{i}}) = \hat{σ} (m_{α, δ_{i}}) \cdot \frac{| {\hat{R}}^{-} (m_{α, δ_{i}}) | + 1}{| {\hat{R}}^{-} (m_{α, δ_{i}}) | + 2}$ that is also equivalent to ${\hat{σ}}_{+ (α β)} (m_{α, δ_{i}}) = \hat{σ} (m_{α, δ_{i}}) - \frac{\hat{σ} (m_{α, δ_{i}})}{| {\hat{R}}^{-} (m_{α, δ_{i}}) | + 2}$ . Point 3. Given Definition 6 and the hypothesis that ¬ !∃ path also from β to δ_i, we can write ${\hat{σ}}_{+ (α β)} (δ_{i}) = τ d +$ $+ \sqrt{d} \cdot \frac{\sum_{m_{ζ, δ_{i}} \in {\hat{R}}^{+} Plus (δ_{i})} {\hat{σ}}_{+ (α β)} (m_{ζ, δ_{i}})}{| {\hat{R}}^{-} (δ_{i}) | + 1}$ . Given Remark 3 (non-meta-arguments have no attacks), we can rewrite the previous as ${\hat{σ}}_{+ (α β)} (δ_{i}) = τ d +$ $+ \sqrt{d} \cdot \sum_{m_{ζ, δ_{i}} \in {\hat{R}}^{+} Plus (δ_{i})} {\hat{σ}}_{+ (α β)} (m_{ζ, δ_{i}})$ . Now, if we isolate α’s contribution to δ_i in the summation, we get ${\hat{σ}}_{+ (α β)} (δ_{i}) = τ d + \sqrt{d} \cdot [(\sum_{m_{ζ, δ_{i}} \in {\hat{R}}^{+} (δ_{i})} \hat{σ} (m_{ζ, δ_{i}})) -$ $- \hat{σ} (m_{α, δ_{i}}) + {\hat{σ}}_{+ (α β)} (m_{α, δ_{i}})]$ . And given that $\hat{σ} (δ_{i}) = τ d + \sqrt{d} \cdot \sum_{m_{ζ, δ_{i}} \in {\hat{R}}^{+} (δ_{i})} \hat{σ} (m_{ζ, δ_{i}})$ then it holds that ${\hat{σ}}_{+ (α β)} (δ_{i}) = \hat{σ} (δ_{i}) + \sqrt{d} \cdot [- \hat{σ} (m_{α, δ_{i}}) +$ $+ {\hat{σ}}_{+ (α β)} (m_{α, δ_{i}})]$ . Using what we proved in point 2, we can rewrite as ${\hat{σ}}_{+ (α β)} (δ_{i}) = \hat{σ} (δ_{i}) +$ $+ \sqrt{d} \cdot (- \hat{σ} (m_{α, δ_{i}}) + \hat{σ} (m_{α, δ_{i}}) \cdot \frac{| {\hat{R}}^{-} (m_{α, δ_{i}}) | + 1}{| {\hat{R}}^{-} (m_{α, δ_{i}}) | + 2})$ or equivalently as ${\hat{σ}}_{+ (α β)} (δ_{i}) = \hat{σ} (δ_{i}) -$ $- \hat{σ} (m_{α, δ_{i}}) \cdot \frac{\sqrt{d}}{| {\hat{R}}^{-} (m_{α, δ_{i}}) + 2}$ .□

In practice, this proposition has a twofold use. On the one hand, it provides a computationally efficient procedure to compute ${\hat{σ}}_{+ (α β)}$ under certain assumptions. On the other hand, the same procedure can possibly be used as an estimation method when those assumptions do not hold. We denote such estimator as ${\hat{σ}}_{+ (α β)}^{e}$ . ${\hat{σ}}_{+ (α β)}^{e} = \hat{σ} (δ) - d \cdot \frac{\hat{σ} (α)}{| {\hat{R}}^{-} (m_{α, δ}) | \cdot (| {\hat{R}}^{-} (m_{α, δ}) | + 1)}$ In Section 6 will use this procedure to generate additive counter-factual explanations and we will also show empirically that this is a good estimator for ${\hat{σ}}_{+ (α β)}$ in terms of approximation error.

6 Experiments

In this section we evaluate the proposed explanations on the Wikipedia web graph and several other web graphs crawled from some British and Irish universities, see Table 2 for information.

Table 2
Characteristics of the web graphs used in the experiments. (†) These web graphs result from a partial crawl, i.e. the crawling of these websites was stopped before it completed after running for more than 1 month

Web Graph Website Number of pages Number of links Average number of links per page

Leeds Trinity University www.leedstrinity.ac.uk 1,119 35,011 31.28

Homerton College www.homerton.cam.ac.uk 1,261 55,903 44.33

National University of Ireland www.nui.ie 1,295 11,632 8.98

University of East Anglia www.uea.ac.uk 2,871 120,735 42.05

Cardiff Metropolitan University www.cardiffmet.ac.uk 4,467 107,354 24.03

University of Leeds www.leeds.ac.uk 25,824 180,196 6.97

Queen’s University Belfast www.qub.ac.uk 64,659 451,882 6.98

University College Dublin www.ucd.ie 81,893 1,129,103 13.78

University of Exeter^† www.exeter.ac.uk 118,005 1,859,492 15.75

Imperial College London^† www.imperial.ac.uk 146,125 4,758,430 32.56

University of Reading www.reading.ac.uk 302,130 7,063,264 23.37

London School of Economics^† www.lse.ac.uk 426,434 2,622,280 6.14

University of Oxford^† www.ox.ac.uk 430,490 5,429,420 12.61

Wikipedia simple.wikipedia.org 965,748 7,388,700 7.65

Web Graph	Website	Number of pages	Number of links	Average number of links per page
Leeds Trinity University	www.leedstrinity.ac.uk	1,119	35,011	31.28
Homerton College	www.homerton.cam.ac.uk	1,261	55,903	44.33
National University of Ireland	www.nui.ie	1,295	11,632	8.98
University of East Anglia	www.uea.ac.uk	2,871	120,735	42.05
Cardiff Metropolitan University	www.cardiffmet.ac.uk	4,467	107,354	24.03
University of Leeds	www.leeds.ac.uk	25,824	180,196	6.97
Queen’s University Belfast	www.qub.ac.uk	64,659	451,882	6.98
University College Dublin	www.ucd.ie	81,893	1,129,103	13.78
University of Exeter^†	www.exeter.ac.uk	118,005	1,859,492	15.75
Imperial College London^†	www.imperial.ac.uk	146,125	4,758,430	32.56
University of Reading	www.reading.ac.uk	302,130	7,063,264	23.37
London School of Economics^†	www.lse.ac.uk	426,434	2,622,280	6.14
University of Oxford^†	www.ox.ac.uk	430,490	5,429,420	12.61
Wikipedia	simple.wikipedia.org	965,748	7,388,700	7.65

In particular, we aim to address the following research questions:

Misleading basic explanations: do basic explanation provide a misleading picture of the pages contributing the most to the PR score of a page?

Cognitive tractability of explanations: Are explanations cognitively tractable? In particular:

What is the size of explanations?

How many arguments must be included in explanations to best explain page scores?

Contrastive attribution explanations usefulness: which portion of supporters is shared between two pages?

Approximation: is the estimator ${\hat{σ}}_{+ (α β)}^{e}$ based on Proposition 10 a good approximation for ${\hat{σ}}_{+ (α β)}$ , i.e., for the M-PR semantics on the MPRAF with the addition of a support?

Note that, when conducting experiments on Contrastive attribution explanation and additive counterfactual explanations, we randomly sampled 500,000 and 200,000 pairs of pages, respectively, for performance reasons; in all other experiments we used all the pages instead.

Misleading basic explanations. To assess if and how often basic explanations provide a misleading picture of the pages contributing to the score of a page of interest, we checked the divergence ratio of the strengths of arguments in basic explanations and meta-arguments in attribution explanations for the same page. We denote with σ_% (β, α) and ${\hat{σ}}_{%} (β, α)$ the contribution to page α ∈ χ from a supporter $β \in R^{+} (α)$ according to, respectively, the basic explanation and the attribution explanation, formally we define σ_% (β, α) and ${\hat{σ}}_{%} (β, α)$ as follows. $σ_{%} (β, α) = \frac{σ (β)}{\sum_{⋎ \in E_{b}} σ (⋎)}$ ${\hat{σ}}_{%} (β, α) = \frac{\hat{σ} (m_{β, α})}{\sum_{⋎ \in E_{\leftarrow}} \hat{σ} (m_{⋎, α})}$ We then define the divergence ratio as follows. $r_{%} (β, α) = | \frac{σ_{%} (β, α)}{{\hat{σ}}_{%} (β, α)} - 1 |$ The divergence ratio describes how much the contribution of a supporter β is under or over-estimated in a basic explanation of α wrt to its actual contribution in the attribution explanation. Table 3 shows that the divergence ratio ranges between 35% and 1324% in our experiments. This means that the picture portrayed by basic explanation can be very misleading in some web graphs.

Table 3

Average divergence ratio of the strength of arguments (in the basic explanations) and meta-arguments (in attribution explanations)

	Leeds Trinity University	Homerton College	National University of Ireland	University of East Anglia	Cardiff Metropolitan University	University of Leeds	Queen’s University Belfast	University College Dublin	University of Exeter	Imperial College London	University of Reading	London School of Economics	University of Oxford	Wikipedia
r _%	35.2	41	99.2	40.2	17.2	25.6	701.4	51	523.7	1324.9	97.9	34.3	56.3	73.8

Cognitive tractability. In order to assess the cognitive tractability of the explanations we proposed, we checked the size of explanations, in terms of overall number of arguments and the percentage of a score explained by the top arguments according to their importance in the explanation. Tables 4 and 5 show the results on the sizes of the explanations and the percentage of score explained by the top arguments, respectively. We note that: (1) the average explanation size ranges from some hundreds of arguments for the smaller web graphs, to hundreds of thousands for the bigger ones, significantly increasing with the number of pages and links in the web graph; (2) selecting only arguments with backward hop distance of 2 in additive counter-factual explanation considerably reduces the number of arguments in the explanations to an amount similar to that of other types of explanations. This is a reasonable amount when compared to the number of nodes in the web graph that would have been otherwise included. (3) Although the full set of meta-arguments potentially included in the explanations of a page may be very large, considering only a limited subset is enough to produce a satisfactory explanation. In fact, 10 meta-arguments are enough to explain on average between 84.8% and 99.7% of the score of a page depending on the web graph and the type of explanation.

Table 4

Average size of attribution explanations (E_←), Contrastive attribution explanations (E_↔), additive counter-factual explanations ( $\underset{\leftarrow}{\underset{+ ?}{E}}$ ) and editsensibility counterfactual explanations ( $\underset{\leftarrow}{\underset{Φ ?}{E}}$ ). (†) Additive counterfactual explanations’ sizes are equal to those of attribution explanations

Explanation	E _←	E _↔	$\underset{\leftarrow}{\underset{+ ?}{E}}$	$\underset{\leftarrow}{\underset{Φ ?}{E}}$
Leeds Trinity University	177.1	166.1	259.3	†
Homerton College	228	223.9	347.8	†
National University of Ireland	229.8	228.5	245	†
University of East Anglia	456.4	448.8	531.1	†
Cardiff Metropolitan University	868	849.4	979.8	†
University of Leeds	3887	3884.8	3973.1	†
Queen’s University Belfast	8710.8	8704.2	9353.1	†
University College Dublin	12605.3	12605.9	12765.6	†
University of Exeter	18495.1	18493.5	19310.4	†
Imperial College London	21072.1	21070.6	22313.4	†
University of Reading	47246.9	47237.1	37557.4	†
London School of Economics	61911	61663.7	33907.1	†
University of Oxford	63804.7	63778.4	36124.3	†
Wikipedia	123495.6	59340	38594.3	†

Table 5

Percentages of PageRank score explained by the top meta-arguments in explanations according to their importances

Explanation	Supporters	Leeds Trinity University	Homerton College	National University of Ireland	University of East Anglia	Cardiff Metropolitan University	University of Leeds	Queen’s University Belfast	University College Dublin	University of Exeter	Imperial College London	University of Reading	London School of Economics	University of Oxford	Wikipedia
E _←	top-1	73.4	83.7	88.2	84.5	76.9	82.2	86	79.8	82.1	79.1	67.2	90.5	80.6	82.3
	top-3	81	87.4	97.1	92.1	90	94.6	94.1	90.4	91.3	88.9	85.6	97.7	92.6	92.9
	top-5	83.9	88	98	92.6	93	96.2	95.9	92.6	93.7	91	92.3	98.8	95.7	95
	top-10	84.8	89.1	98.9	93.1	96.2	97.8	97.5	95.2	96	93.1	96.3	99.4	97.8	96.9
$\underset{\leftarrow}{\underset{Φ ?}{E}}$	top-1	74.6	86.2	90.7	85.9	77	83.6	87.1	80.9	83.5	80.8	69.4	92.3	82.9	85.7
	top-3	81.4	89.7	97.2	92.6	89.9	94.9	94.5	90.8	91.9	89.2	87.3	98.2	93.8	94.4
	top-5	84	90.3	98.1	93.1	93.1	96.4	96.1	93	94.2	91.1	93.6	99	96.4	96.1
	top-10	84.9	91.2	99	93.6	96.3	98	97.7	95.4	96.3	93.1	96.9	99.4	98	97.5
E _↔	top-1	96.8	90	90.7	91.4	85.5	92.6	93.1	83.3	88.9	75.3	66.1	88.9	84.3	90.2
	top-3	97.9	91.1	98.9	94.7	95.9	97.7	97.5	94.4	96	86.8	83.5	96.7	96.1	98.5
	top-5	98.1	91.4	99.4	95.2	97.9	98.6	98.4	95.3	97.5	89	91	97.9	98.2	99.2
	top-10	98.2	91.9	99.5	95.4	99	99.7	99.1	96.4	98.3	91.6	95.2	98.6	99.4	99.7
$\underset{\leftarrow}{\underset{+ ?}{E}}$	top-1	73.4	83.7	88.2	84.5	76.9	82.2	86	79.8	82.1	79.1	67.2	90.5	80.6	82.3
	top-3	81	87.4	97.1	92.1	90	94.6	94.1	90.4	91.3	88.9	85.6	97.7	92.6	92.9
	top-5	83.9	88	98	92.6	93	96.2	95.9	92.6	93.7	91	92.3	98.8	95.7	95
	top-10	84.8	89.1	98.9	93.1	96.2	97.8	97.5	95.2	96	93.1	96.3	99.4	97.8	96.9

Contrastive attribution explanation usefulness. Contrastive attribution explanations are useful only when the amount of shared supporters is not negligible. We checked therefore the average number of shared supporters in different scenarios. Table 6 shows the results. We note that: (1) the average number of shared supporters of two random pages can be more than 45% in some (smaller) datasets; (2) despite the small average number of shared supporters for two random pages in some datasets, in other scenarios where one of the two pages supports the other or they support one another, the number of shared supporters increases up to 96.2%.

Table 6

Percentages of shared supporters in Contrastive attribution explanations of (1) two random pages, (2) a page and one of its supporters and (3) two pages mutually supporting each other

	Leeds Trinity University	Homerton College	National University of Ireland	University of East Anglia	Cardiff Metropolitan University	University of Leeds	Queen’s University Belfast	University College Dublin	University of Exeter	Imperial College London	University of Reading	London School of Economics	University of Oxford	Wikipedia
Random pages (%)	45.6	25.7	21.1	20.7	3.7	0.5	3.2	0.6	4.3	1.8	0.1	0.1	0.2	0
Supporting pages (%)	27.1	17.1	9.7	25.4	18.7	13.7	8.8	14.7	20.8	12.5	25.4	5.4	10.7	12.1
Mutually supporting pages (%)	96.2	63.4	50.3	70.3	59.1	47.4	49.4	62	55.5	38.7	67.3	37.7	55	42

Approximation of ${\hat{σ}}_{+ (α β)}$ . We checked whether ${\hat{σ}}_{+ (α β)}^{e}$ is a good estimator for ${\hat{σ}}_{+ (α β)}$ on 50 random pairs of pages in each dataset. As shown by Table 7, the average approximation error is at most 0.024% and the maximum error ranges between 0.009% and 1.255% depending on the dataset. These low values confirm that the approximation provided by ${\hat{σ}}_{+ (α β)}^{e}$ for ${\hat{σ}}_{+ (α β)}$ is satisfactory.

Table 7

Approximation error of ${\hat{σ}}_{+ (α β)}^{e}$ , i.e., $| \frac{{\hat{σ}}_{+ (α β)}^{e} - {\hat{σ}}_{+ (α β)}}{\hat{σ}} |$

	Leeds Trinity University	Homerton College	National University of Ireland	University of East Anglia	Cardiff Metropolitan University	University of Leeds	Queen’s University Belfast	University College Dublin	University of Exeter	Imperial College London	University of Reading	London School of Economics	University of Oxford	Wikipedia
Average (%)	0.006	0.002	0.006	0.005	0.014	0.008	0.012	0.024	0.007	0.019	0.006	0	0.002	0.005
Maximum (%)	0.415	0.009	0.066	0.242	0.906	0.25	0.633	1.255	0.091	0.566	0.126	0.009	0.06	0.105

7 Conclusions

In this paper we have investigated connections between PageRank (PR) and formal argumentation.

Firstly, we have introduced a novel approach capable of reconstructing PR as a gradual argumentation semantics of a suitably defined bipolar argumentation framework, while ensuring the satisfaction of a set of generally desirable properties. Secondly, we have shown how using this approach enables the generation of better explanations of PR scores to end-users, proposing four different types of explanation.

To the best of our knowledge, the investigation of the relationships between PR and argumentation semantics has not been previously considered in the literature. The work in [30] explores the application of PR to rank the relevance of arguments available on the web to support or attack a given stance. This is an interesting but different goal: in [30] PR is not related to any semantics notion and the links have a different meaning, relating the conclusion of an argument with the premises of another one. On a different but related line, some works, e.g. [31], have explored connections between argumentation semantics and matrix representations from network theory, whose relationships with our approach are worth future investigation. To the best of our knowledge, the generation of explanations based on argumentation for PR has not been previously considered in the literature. We have illustrated the promise of our method in helping users to better understand PR, a popular algorithm for ranking pages, but leave user evaluations to future work.

Our proposal can be extended mainly in two directions. The role of bipolar argumentation framework representation with meta-arguments in enhancing the explainability of graph-based algorithms could be further investigated. In this regard, understanding how other algorithms designed for directed graphs could be re-interpreted in an argumentative perspective and developing other types of explanations from their argumentative counterparts represent two interesting research possibilities. Another fruitful direction would be the investigation of the relation between PR and argumentation semantics could be expanded. In this respect, firstly, the investigation of PR-inspired gradual semantics for various kinds of argumentation frameworks could be pursued. For example, it would be interesting to consider weighted versions of PR where a node’s strength can be distributed unevenly to its children and, more generally, to the variants of PR considered in various domains [6]. Secondly, one can notice that PR is essentially a mechanism to produce a score based on a relation of support, but it could be considered that, in several domains where PR is applied, also other relations, in particular attack, could be relevant for a proper scoring. Also, in the web domain, one could argue that the absence of a link from one page to another (where this link could instead be expected according to some criterion) could be interpreted as an attack diminishing the relevance of the non-linked page. Given the strong tradition on attack-based and bipolar evaluations in argumentation semantics, this suggests that the study of argumentation-inspired variants of PR may also represent a fruitful research direction. Finally, from a wider perspective, it would be interesting to investigate the possible interpretation in terms of gradual argumentation semantics of other graph-based quantitative assessments, like trust evaluation in social networks [32].

Footnotes

If there are cycles in the MPRAF, the removal of a link could indirectly strengthen or weaken the other incoming links, e.g., because the page of interest is cyclically supporting one of its supporting pages. However, in most cases this gives rise to negligible changes due to PageRank’s design.

For any α, β ∈ χ there exists a support path from α to β iff ∃⋎₁, …, ⋎_l such that ⋎₁ = α, ⋎_l = β, l > 0 and $\forall i \in {1, \dots, l - 1}, (⋎_{i}, ⋎_{i + 1}) \in R^{+}$ . Note that, by construction of the MPRAF, this is equivalent to requiring $(⋎_{i}, ⋎_{i + 1}) \in {\hat{R}}^{+}$ .

References

Page

, Brin

, Motwani

and Winograd

, The PageRank Citation Ranking: Bringing Order to the Web, World Wide Web Internet And Web Information Systems 54(1999-66) (1998), 1–17.

, Guan

and Zhao

, Bringing PageRank to the citation analysis, Information Processing and Management 44(2) (2008 3), 800–810.

Gori

and Pucci

, ItemRank: A Random-Walk Based Scoring Algorithm for Recommender Engines, In: Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI); (2007), pp. 2766–2771.

Hudelson

, Mooney

B.L.

and Clark

A.E.

, Determining polyhedral arrangements of atoms using PageRank, Journal of Mathematical Chemistry 50(9) (2012 9), 2342–2350.

Morrison

J.L.

, Breitling

, Higham

D.J.

and Gilbert

D.R.

, GeneRank: Using search engine technology for the analysis of microarray experiments, BMC Bioinformatics 6(1) (2005), 233.

Gleich

D.F.

, PageRank beyond the web, SIAM Review 57(3) (2015), 321–363.

Altman

and Tennenholtz

, Ranking systems: the PageRank axioms, In: Proceedings of the 6th ACM Conference on Electronic Commerce (EC); (2005), pp. 1–8.

Dung

P.M.

, On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-Person Games, Artificial Intelligence 77(2) (1995), 321–358.

Cayrol

and Lagasquie-Schiex

M.C.

, On the Acceptability of Arguments in Bipolar Argumentation Frameworks, In: Proceedings of the 8th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU); (2005), pp. 378–389.

10.

Baroni

, Rago

and Toni

, From fine-grained properties to broad principles for gradual argumentation: A principled spectrum, International Journal of Approximate Reasoning 105 (2019), 252–286.

11.

Baroni

, Caminada

and Giacomin

, An introduction to argumentation semantics, Knowledge Engineering Review 26(4) (2011), 365–410.

12.

Cayrol

and Lagasquie-Schiex

M.C.

, Graduality in Argumentation, Journal of Artificial Intelligence Research 23 (2005), 245–297.

13.

Ribeiro

M.T.

, Singh

and Guestrin

, “Why Should I Trust You?”, In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD); (2016), pp. 1135–1144.

14.

Lundberg

S.M.

, Allen

P.G.

and Lee

S.I.

, A Unified Approach to Interpreting Model Predictions, In: Proceedings of the 31st International Conference on Neural Information Processing Systems (NeurIPS); (2017), pp. 4768–4777.

15.

Dhurandhar

, Chen

P.Y.

, Luss

, Tu

C.C.

, Ting

P.S.

, Shanmugam

, et al., Explanations based on the Missing: Towards Contrastive Explanations with Pertinent Negatives, In: Proceedings of the 31st Conference on Neural Information Processing Systems (NeurIPS); (2018), pp. 590–601.

16.

Wachter

, Mittelstadt

and Russell

, Counterfactual Explanations Without Opening the Black Box: Automated Decisions and the GDPR, SSRN Electronic Journal (2017), 1–52.

17.

Mittelstadt

B.D.

, Russell

and Wachter

, Explaining Explanations in AI, In: Proceedings of the 2nd Conference on Fairness, Accountability, and Transparency (FAT*); (2019), pp. 279–288.

18.

Albini

, Lertvittayakumjorn

, Rago

, Toni

, DAX: Deep Argumentative eXplanation for Neural Networks. ArVix; 2020. Available from: http://arxiv.org/abs/2012.05766.

19.

Dejl

, He

, Mangal

, Mohsin

, Surdu

, Voinea

, et al., Argflow: A Toolkit for Deep Argumentative Explanations for Neural Networks, In: Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS); (2021), pp. 1761–1763.

20.

Cyras

, Letsios

, Misener

and Toni

, Argumentation for Explainable Scheduling, In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI); (2019), pp. 2752–2759.

21.

Timmer

S.T.

, Meyer

J.C.

, Prakken

, Renooij

and Verheij

, Explaining Bayesian Networks Using Argumentation, In: Proceedings of the 13th European Conference on Symbolic and Quantitative Approaches Reasoning with Uncertainty (ECSQARU); (2015), pp. 83–92.

22.

Rago

, Albini

, Baroni

, Toni

, Influence-Driven Explanations for Bayesian Network Classifiers. ArVix; 2020. Available from: http://arxiv.org/abs/2012.05773.

23.

Arioua

, Tamani

, Croitoru

, Query Answering Explanation in Inconsistent Datalog +/- Knowledge Bases, in: Q. Chen, A. Hameurlain, F. Toumani, R. Wagner, H. Decker, editors. Proceedings of the 26th International Conference on Database and Expert Systems Applications (DEXA). vol. 9261 of Lecture Notes in Computer Science; (2015), pp. 203–219.

24.

Rago

, Cocarascu

, Bechlivanidis

and Toni

, Argumentation as a Framework for Interactive Explanations for Recommendations, In: Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning (KR); (2020), pp. 805–815.

25.

Amgoud

and Ben-Naim

, Evaluation of Arguments from Support Relations: Axioms and Semantics, In: Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI); (2016), pp. 900–906.

26.

Albini

, Baroni

, Rago

and Toni

, PageRank as an argumentation semantics, In: Proceedings of the 8th International Conference on Computational Models of Argument (COMMA); (2020), pp. 55–66.

27.

Albini

, Baroni

, Rago

, Toni

, Explaining PageRank through Argumentation, In: Workshop on Explainable Logic-Based Knowledge Representation (Co-located with the 17th International Conference on Principles of Knowledge Representation and Reasoning, KR); 2020, pp. #390. Available from: https://lat.inf.tu-dresden.de/XLoKR20/XLoKRpaper390.pdf.

28.

Langville

A.N.

and Meyer

C.D.

, Deeper inside PageRank. InternetMathematics, Internet Mathematics 1(3) (2004), 335–380.

29.

Baroni

, Rago

and Toni

, How many properties do we need forgradual argumentation? In: Proceedings of the 32nd AAAIConference on Artificial Intelligence (AAAI); (2018), pp. 1736–1743.

30.

Wachsmuth

, Stein

and Ajjour

, “PageRank” for Argument Relevance, In: Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics (EACL); (2017), pp. 1117–1127.

31.

Corea

and Thimm

, Using Matrix Exponentials for Abstract Argumentation, In: Proceedings of the 1st International Workshop on Systems and Algorithms for Formal Argumentation (SAFA); (2016), pp. 10–21.

32.

Jiang

, Wang

, Bhuiyan

M.Z.A.

and Wu

, Understanding Graph-Based Trust Evaluation in Online Social Networks: Methodologies and Challenges, ACM Comput Surv 49(1) (2016), 10:1–10:35.