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
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].
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
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.
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 = 1, i.e. the L1 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.
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].
a finite set of arguments χ, a binary attack relation between arguments a binary support relation between arguments a total function
Given a QBAF, a total function
We define an sQBAF as a QBAF such that
A web graph
Given Definition 1 and the notes on loops and dangling nodes in Section 2, Remark 1 can be trivially derived.
each argument has at least one outgoing link: there are no self-supports:
We then interpret PR as a gradual semantics for sQBAFs.
The following remark is directly derived from Definition 4.
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
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):
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.
if if if if σ (α) < τ (α) then if σ (α) > τ (α) then
A gradual semantics σ is strictly balanced iff σ is balanced and for any α ∈ χ:
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 (
for any α, β ∈ χ, if if for any α, β ∈ χ, if
A gradual semantics σ is strictly monotonic iff σ is monotonic and:
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.
Proof. GP1 holds as when
Proof. GP8 holds as if τ (α) = τ (β) and

Counter-example to GP6 and GP11 for the PR semantics σ in Proposition 2.
Proof. For balance, Point 1 holds as, by Definition 4, if
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: ∀α ∈ χ,
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.
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.

Example of a transformation from a PRAF to an MPRAF.
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
With reference to MPRAFs, we now define a gradual semantics
We now prove that, given a PRAF and corresponding MPRAF, for any α ∈ χ, the strength
Proof.
We recall that, by Remark 4,
Proposition 5 proves that the codomain of
Proof. By Definition 6,
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.
Proof. By Definition 5,
We now assess this framework and semantics with respect to the desirable properties.
Proof. GP1: by Definition 6, if
Proof. For balance, Point 1: (A) If
Proof. Point 1: if
In the first case, by construction of the framework PR,
Satisfaction (✓) or not (×) of GPs and principles (
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.
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
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.
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.
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.
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.
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).

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.
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.
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.

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.
In order to formally define additive counter-factual explanation we will now introduce the definition of the MPRAF with a link addition or removal.
We denote with
We now formally define additive counter-factual explanations.
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).

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.
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.
We can now define edit-sensibility counterfactual explanations.
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%.
The counterfactual explanations that we introduced require the values of
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.

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 α.
If there is no support path
2
from β to α it holds that If there is no support path also from β to δ then it holds that
Proof. Point 1. By Definition 5, it is immediate that
In practice, this proposition has a twofold use. On the one hand, it provides a computationally efficient procedure to compute
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.
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
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
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
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.
Average divergence ratio of the strength of arguments (in the basic explanations) and meta-arguments (in attribution explanations)
Average size of attribution explanations (E←), Contrastive attribution explanations (E↔), additive counter-factual explanations (
Percentages of PageRank score explained by the top meta-arguments in explanations according to their importances
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
Approximation error of
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 ∃⋎1, …, ⋎
l
such that ⋎1 = α, ⋎
l
= β, l > 0 and
