# Efficient Representation of Lattice Path Matroids

Carles Padró  Universitat Politècnica de Catalunya, Barcelona, Spain

###### Abstract

An efficient deterministic algorithm to construct representations of lattice
path matroids over finite fields is presented. Its running time is polynomial
in the size of the ground set.

##  1 Introduction

This paper deals with efficient deterministic constructions of representations
of matroids over finite fields. Specifically, given a family of representable
matroids, we search for _deterministic_ algorithms that provide, for each
matroid in the family, a representation over some finite field
$\mathbf{F}_{q}$. Both the running time and the size $\log q$ of the elements
in the finite field must be polynomial in the number of elements in the ground
set.

The existence of such algorithms is well known for uniform and graphic
matroids, and it has been proved for matroids with two clonal classes [1].
Operations on matroids like duality and direct sums provide constructions for
other families as, for example, co-graphic and partition matroids. Even though
efficient _randomized_ algorithms are known, the problem has not been solved
for transversal matroids. Some results on that question are found in [17, 20].

In this paper, we present an efficient deterministic algorithm for lattice
path matroids, a family of transversal matroids introduced in [7]. Even though
that result has not been explicitly stated before, it directly follows from
previous works in secret sharing. Namely, the constructions of ideal linear
hierarchical secret sharing schemes in [8, 12, 26] and a recent
characterization of the matroids determined by those schemes, which were
proved to coincide with lattice path matroids [21]. In addition to pointing
out and explaining that connection, the main contribution in this paper is a
simpler and more general description of the constructions in [8, 12].
Specifically, by adapting the application of isolating weight functions in
[17], a general method to find representations of transversal matroids is
presented. It is efficient if the values of the isolating weight functions are
polynomial in the size of the ground set. The existence of such functions is
proved for lattice path matroids. The application to other families of
transversal matroids remains an open question.

##  2 Preliminaries

###  2.1 Polymatroids, Matroids, and Matroid Ports

The reader that is unfamiliar with matroid theory is referred to [22]. Most of
the times we use here the terminology and notation from that textbook. More
information about polymatroids and matroid ports, and their application to
secret sharing, is found in [18].

A _set function_ $f\colon 2^{E}\to\mathbf{R}$ on a finite set $E$ is
_monotone_ if $f(X)\leq f(Y)$ whenever $X\subseteq Y\subseteq E$, and it is
_submodular_ if $f(X)+f(Y)-f(X\cup Y)-f(X\cap Y)\geq 0$ for all $X,Y\subseteq
E$. A _polymatroid_ is a pair $(E,f)$ formed by a _ground set_ $E$ and a _rank
function_ $f$. The former is a finite set and the latter is a monotone,
submodular set function on $E$ with $f(\emptyset)=0$. _Integer polymatroids_
are those with integer-valued rank functions. From now on, only integer
polymatroids are considered.

An integer polymatroid $M=(E,r)$ with $r(\\{x\\})\leq 1$ for each $x\in E$ is
a _matroid_. The _independent sets_ of the matroid $M$ are the subsets of the
ground set with $r(X)=|X|$. A _basis_ is a maximal independent set and a
_circuit_ is a minimal dependent set.

Given a matrix $A$ over a field $K$ with columns indexed by a set $E$, the
sets $X\subseteq E$ corresponding to linearly independent sets of columns of
$A$ form the collection of independent sets of a matroid $M$ with ground set
$E$. In that situation, the matroid $M$ is _representable_ over $K$, or
$K$-representable, and the matrix $A$ is a _representation_ of $M$ over $K$.

For an element $p_{o}$ in the ground set $E$, the _port of the matroid $M$ at
$p_{o}$_ is formed by the sets $X\subseteq E\smallsetminus\\{p_{o}\\}$ such
that $r(X\cup\\{p_{o}\\})=r(X)$. Observe that the minimal sets in the matroid
port are the ones such that $X\cup\\{p_{o}\\}$ is a circuit. As a consequence
of [22, Theorem 4.3.3], a _connected_ matroid is determined by any of its
ports.

While representations of matroids are collections of vectors (the columns of a
matrix) some polymatroids can be represented by collections of vector
subspaces. A polymatroid $(E,f)$ is _$K$ -representable_ if there exists a
collection $(V_{x})_{x\in E}$ of subspaces of a $K$-vector subspace $V$ such
that $f(X)=\dim\sum_{x\in X}V_{x}$ for every $X\subseteq E$.

###  2.2 Transversal Matroids and Boolean Polymatroids

We discuss next some basic facts about transversal matroids, Boolean
polymatroids, and lattice path matroids. The reader is referred to [4, 5, 6,
7, 19, 22] for additional information on those topics.

For an integer polymatroid $(S,f)$, consider the family formed by the subsets
$X\subseteq S$ such that $|Y|\leq f(Y)$ for every $Y\subseteq X$. By [22,
Corollary 11.1.2], that is the family of independent sets of a matroid, which
is called the _matroid induced by the polymatroid $(S,f)$_.

Let $G$ be a bipartite graph with vertices in the parts $J$ and $S$. For a set
$X$ of vertices, $N(X)$ denotes the set of neighbors of the vertices in $X$.
If $B\subseteq S$, we notate $G_{B}$ for the subgraph of $G$ induced by $J\cup
B$. The _biadjacency matrix_ of the bipartite graph $G$ is a $(0,1)$-matrix
whose rows and columns are indexed by the sets $J$ and $S$, respectively, and
the entries equal to $1$ mark the edges of $G$.

The graph $G$ determines two sequences of sets. Namely, $(C_{x}\,:\,x\in S)$
with $C_{x}=N(\\{x\\})\subseteq J$ and $(A_{j}\,:\,j\in J)$ with
$A_{j}=N(\\{j\\})\subseteq S$. Observe that the sets in those sequences may
not be distinct.

The _partial transversals_ of the sequence $(A_{j}\,:\,j\in J)$ are the
independent sets of a _transversal matroid_ $M$ with ground set $S$. Observe
that $X\subseteq S$ is an independent set of $M$ if and only if there is a
matching in $G$ covering all vertices in $X$. The sequence $(A_{j}\,:\,j\in
J)$ of subsets of $S$ or, equivalently, the graph $G$ provide a _presentation_
of the transversal matroid $M$. A transversal matroid may admit different
presentations, but there exist presentations such that the size of $J$ equals
the rank of the matroid [4, Theorem 2.6]. From now on, we always assume that
this is the case, that is, we assume that there is a matching in $G$ with
$|J|$ edges. Observe that $B\subseteq S$ is a basis of $M$ if and only if the
subgraph $G_{B}$ has a perfect matching.

The sequence $(C_{x}\,:\,x\in S)$ of subsets of $J$ determines a _Boolean
polymatroid_ with ground set $S$. Namely, the polymatroid $(S,f)$ with
$f(X)=|N(X)|=\left|\bigcup_{x\in X}C_{x}\right|$ for every $X\subseteq S$. By
Hall’s marriage theorem, $X\subseteq S$ is an independent set of the
transversal matroid $M$ determined by $G$ if and only if $|Y|\leq f(Y)$ for
every $Y\subseteq X$. Therefore, a matroid is transversal if and only if it is
induced by a Boolean polymatroid.

_Lattice path matroids_ , which were introduced in [7], are a special class of
transversal matroids. As a consequence of [4, Lemma 4.7] the following
definition is equivalent to the one in [7]. For positive integers $m,n$, with
$m\leq n$, we notate $[m,n]=\\{m,m+1,\ldots,n\\}$ and $[n]=[1,n]$.

######  Proposition 2.1.

Let $G$ be a bipartite graph with parts $J=[r]$ and $S=[n]$. Then the
following conditions are equivalent.

  1. 1.

There are sequences $(a_{1},\ldots,a_{r})$ and $(b_{1},\ldots,b_{r})$ in $S$
with $1=a_{1}\leq a_{2}\leq\cdots\leq a_{r}$ and $b_{1}\leq
b_{2}\leq\cdots\leq b_{r}=n$ such that $A_{j}=[a_{j},b_{j}]$ for every $j\in
J$.

  2. 2.

There are sequences $(c_{1},\ldots,c_{n})$ and $(d_{1},\ldots,d_{n})$ in $J$
with $1=c_{1}\leq c_{2}\leq\cdots\leq c_{n}$ and $d_{1}\leq
d_{2}\leq\cdots\leq d_{n}=r$ such that $C_{x}=[c_{x},d_{x}]$ for every $x\in
S$.

######  Definition 2.2.

A _lattice path matroid_ is a transversal matroid that admits a presentation
in the conditions of Proposition 2.1. It is a _nested matroid_ (also called
_generalized Catalan matroid_) in the particular case that it admits such a
presentation with $b_{1}=n$ or, equivalently, $c_{n}=1$.

###  2.3 Vector Secret Sharing Schemes

The reader is referred to [2] for a comprehensive survey on secret sharing. In
a _secret sharing scheme_ , a secret value is distributed into _shares_ among
some _players_ in such a way that only some _qualified_ sets of players are
able to recover the secret from their shares. The qualified sets form the
_access structure_ , which is a _monotone_ family of sets of players. That is,
every set containing a qualified set is qualified. A secret sharing scheme is
_perfect_ if the shares from an unqualified set do not provide any information
on the secret value, and it is _ideal_ if, in addition, each share has the
same size as the secret value, which is the optimal case. Brickell and
Davenport [9] proved that the access structure of every ideal secret sharing
scheme is a matroid port.

_Vector secret sharing schemes_ are ideal schemes determined by linear codes.
A _linear code_ of _length_ $n$ over a finite field $K$ is a vector subspace
$C\subseteq K^{n}$. The rows of a _generator matrix_ form a basis of $C$. Such
a linear code $C$ determines a _vector secret sharing scheme_ as follows.
Given a _secret value_ $s\in K$, choose uniformly at random a code word
$c=(c_{1},c_{2},\ldots,c_{n})\in C$ with $c_{1}=s$, and distribute the
_shares_ $c_{2},\ldots,c_{n}$ among the $n-1$ _players_ in the scheme. A set
is qualified if and only if the first column of the generator matrix is a
linear combination of the columns corresponding to the players in $X$. Let $M$
be the $K$-representable matroid associated to the linear code $C$, that is,
the matroid represented by the generator matrix. The access structure of the
secret sharing scheme is the port of $M$ at the element in the ground set
corresponding to the first column. Therefore, the access structures of vector
secret sharing schemes are the ports of representable matroids. Each
representation of a matroid over a finite field provides vector secret sharing
schemes for its ports and, conversely, a representation of a matroid over a
finite field is obtained from a vector secret sharing scheme for any of its
ports.

###  2.4 Matroids with Large Clonal Classes

Two elements in the ground set of a matroid are _clones_ if the map that
interchanges them and let all other elements fixed is an automorphism of the
matroid. The equivalence classes of that equivalence relation are the _clonal
classes_ of the matroid, For example, uniform matroids are those having only
one clonal class.

In a secret sharing scheme, players $x$ and $y$ are _clones_ if, for every set
$A$ of players with $x,y\notin A$, the set $A\cup\\{x\\}$ is qualified if and
only if so is $A\cup\\{y\\}$. That is, they play the same role in the scheme.
If the access structure is a matroid port, two players are clones if and only
if they are clones in the matroid.

Secret sharing schemes whose set of players is partitioned into large clonal
classes have been studied by several authors [3, 8, 10, 11, 12, 14, 15, 23,
25, 26, 27]. The main examples are _compartmented_ and _hierarchical_ secret
sharing schemes.

######  Definition 2.3.

A matroid $M$ is _$\Pi$ -uniform_ for some partition $\Pi=(S_{i}\,:\,i\in P)$
of the ground set $S$ if all elements in the same part are clones. That is,
each $S_{i}$ is a subset of a clonal class. If $|P|=m$ , we say that $M$ is
_$m$ -uniform_.

Let $M=(S,r)$ be a $\Pi$-uniform matroid with $\Pi=(S_{i}\,:\,i\in P)$.
Associated to $M$, consider the integer polymatroid $(P,g)$ with

$g(I)=r\left(\bigcup_{i\in I}S_{i}\right)$

for every $I\subseteq P$. The matroid $M$ is determined by the integer
polymatroid $(P,g)$. Indeed, consider the map $\pi\colon S\to P$ with
$\pi(x)=i$ if $x\in S_{i}$ and the polymatroid $(S,f)$ with $f(X)=g(\pi(X))$
for each $X\subseteq S$. Then $M$ is the matroid induced by the polymatroid
$(S,f)$. Alternative proofs are given in [14, Section 4] and [13, Section 2].
The following result was proved in [14, Theorem 6.1].

######  Proposition 2.4.

Consider a $\Pi$-uniform matroid $M=(S,r)$ with $\Pi=(S_{i}\,:\,i\in P)$ and
its associated polymatroid $(P,g)$. There exists an integer $q(M)$ such that
$M$ is $K$-representable if the field $K$ has at least $q(M)$ elements and
$(P,g)$ is $K$-representable.

Nevertheless, no efficient methods are known to find representations of
matroids with large clonal classes from representations of the associated
polymatroids. which lead to the open problem posed in [14, Open Problem 6.9]
and [16, Section VII]. Preliminary versions of that problem, and some
solutions, are found in [8, 26, 27].

###  2.5 Hierarchical Secret Sharing and Lattice Path Matroids

In an access structure, a player $x$ is _hierarchically inferior_ to a player
$y$ if, for every set $A$ of players with $x,y\notin A$, the set
$A\cup\\{y\\}$ is qualified if so is the set $A\cup\\{x\\}$. In that
situation, we write $x\preceq y$. Observe that $x,y$ are clones if and only if
$x\preceq y$ and $y\preceq x$. An access structure is _hierarchical_ if that
preorder in the set of players is total. _Hierarchical secret sharing schemes_
are those having a hierarchical access structure.

Efficient deterministic constructions of vector secret sharing schemes were
presented in [8, 26] for the so-called _hierarchical threshold access
structures_. The construction in [8] was generalized in [12] to all
hierarchical matroid ports, which had been previously characterized in [15] in
terms of multi-uniform matroids induced by Boolean polymatroids. An
alternative characterization has been recently found [21], which is summarized
in the following. Hierarchical matroid ports coincide with the ports of
lattice path matroids at one of the extreme elements in the ground set. In
particular, hierarchical threshold access structures are ports of nested
matroids. Moreover, the hierarchical order is compatible with the natural
order in the ground set. Specifically, if $M$ is a lattice path matroid with
ground set $S=[n]$, then in the port of $M$ at the element $1\in S$, a player
$x$ is hierarchically inferior to a player $y$ if $1<y\leq x\leq n$. The
hierarchical order is reversed in the port of $M$ at the element $n\in S$.

Proposition 2.1 clarifies the connection between those two characterizations
of hierarchical matroid ports. While the characterization in [15] uses the
Boolean polymatroid determined by the sets $C_{x}$, the one in [21] focuses on
the lattice path matroid determined by the sets $A_{j}$.

Therefore, the constructions from [8, 26] and the ones from [12] provide
efficient deterministic algorithms to find representations over finite fields
for nested matroids and, respectively, lattice path matroids. The method in
[8, 12] provides representations over algebraic field extensions of large
degree, while the one in [26], which applies only to nested matroids, it is
based on Birkhoff interpolation and yields representations over large prime
fields. Extending the second construction to all lattice path matroids is an
open problem. In the next section, we present an alternative description of
the first one.

##  3 Representations of Transversal Matroids

###  3.1 Isolating Weight Functions

Representations for a transversal matroid $M$ are obtained by modifying the
biadjacency matrix of a presentation $G$. Indeed, take an arbitrary field $K$,
replace each nonzero entry with a variable $\alpha_{j,x}$ and assume that the
entries of the matrix are polynomials over $K$ in the variables
$\alpha_{j,x}$. Clearly, the determinant of the square submatrix formed by the
columns corresponding to a set $B\subseteq S$ with $|B|=r$ is a nonzero
polynomial if $B$ is a basis of $M$ and it is zero otherwise. At this point,
representations for $M$ are obtained by assigning values to the variables
$\alpha_{j,x}$. One possibility is considering that $\alpha_{j,x}$ are
algebraically independent elements over $K$ in some extension field. In
addition, for every sufficiently large field $K$, it is possible to substitute
the variables $\alpha_{j,x}$ by elements in $K$ in such a way that the value
of every polynomial corresponding to a basis of $M$ is nonzero. Nevertheless,
it is not clear how to efficiently choose those elements. We describe next a
method to assign values to the variables $\alpha_{j,x}$ from a weight function
on the edges of the graph.

######  Definition 3.1.

A weight function with non-negative integer values on the edges of $G$ is
_isolating_ if, for every basis $B$ of the transversal matroid $M$, among the
perfect matchings of $G_{B}$ there is only one with minimum weight.

Every bipartite graph admits an isolating weight function. Indeed, enumerate
the edges $\\{e_{0},e_{1}.\ldots,e_{m-1}\\}$ and take $w(e_{k})=2^{k}$.
Nevertheless, the method that is described in the following provides efficient
representations of transversal matroids only if the values of the isolating
weight functions are polynomial in the size of the ground set.

Let $w$ be an isolating weight function for $G$. Take a variable $\alpha$ and
put $\alpha_{j,x}=\alpha^{w(j,x)}$ for every edge $(j,x)$ of $G$. Take a prime
$p$ and assume that the entries of the matrix are polynomials in the variable
$\alpha$ over the finite field $\mathbf{F}_{p}$. Then the determinant of the
submatrix corresponding to a basis $B$ is a nonzero polynomial in the variable
$\alpha$. Indeed, the coefficient of the minimum degree term is equal to $1$
because it corresponds to the unique perfect matching in $G_{B}$ with minimum
weight. For each basis, the degree of that polynomial is at most the maximum
weight of a perfect matching. Take an integer $s$ larger than that quantity
and $q=p^{s}$. Consider the finite field $\mathbf{F}_{q}$, an algebraic
extension of $\mathbf{F}_{p}$, and substitute $\alpha$ by an element in
$\mathbf{F}_{q}$ whose minimal polynomial over $\mathbf{F}_{p}$ is of degree
$s$. Finding such an element is equivalent to finding an irreducible
polynomial over $\mathbf{F}_{p}$ of degree $s$, which can be done in time
polynomial in $p$ and $s$ by the algorithm proposed in [24]. The resulting
matrix is a representation of the matroid $M$ over $\mathbf{F}_{q}$. That
method is efficient for every family of transversal matroids admitting
isolating weight functions whose values are polynomial in the size of the
ground set.

The most computationally expensive step is the algorithm to find an
irreducible polynomial over $\mathbf{F}_{p}$ of degree $s$, which runs in time
$O(p^{1/2}s^{4})$ ignoring the powers of $\log s$ and $\log p$ [24]. Since $p$
can be the same for all matroids in the family, the computation time depends
almost exclusively on the value of $s$, and hence on the maximum weight of the
perfect matchings in the subgraphs $G_{B}$. In addition, the value of $s$
determines the size of the representations, and hence the efficiency of their
applications as, for example, secret sharing schemes.

###  3.2 Efficient Representations of Lattice Path Matroids

In this section, we consider only transversal matroids with a representation
$G$ with $J=[r]$ and $S=[n]$. For a set $B\subseteq S$, we notate
$B=(x_{1},\ldots,x_{r})$ to indicate that its elements are arranged in
increasing order.

We present in Proposition 3.3 a sufficient condition for the existence of
isolating weight functions with polynomial weights. It provides efficient
representations for lattice path matroids. The following technical result is a
consequence of the _rearrangement inequality_.

######  Lemma 3.2.

Let $(p_{1},\ldots,p_{r})$ and $(q_{1},\ldots,q_{r})$ be sequences of real
numbers such that the first one is non-decreasing and the second one is non-
increasing. Then

$p_{1}q_{1}+\cdots+p_{r}q_{r}\leq p_{1}q_{\sigma 1}+\cdots+p_{r}q_{\sigma
r}\leq p_{1}q_{r}+\cdots+p_{r}q_{1}$

for every permutation $\sigma$. Moreover, each of those bounds is attained
only by one permutation if each sequence has distinct terms.

######  Proposition 3.3.

Let $M$ be a transversal matroid such that, for each basis
$B=(x_{1},\ldots,x_{r})$, all pairs $(j,x_{j})$ with $j\in J$ are edges of
$G$. Then $G$ admits an isolating weight function with maximum weight at most
$(r-1)(n-1)$. In addition, for each basis $B$, the maximum weight of the
perfect matchings in $G_{B}$ is less than $r(r-1)(n-1)/2$.

###### Proof.

For $j\in[r]$ and $x\in[n]$, take $p_{j}=j-1$ and $q_{x}=n-x$. For every edge
$(j,x)$, take the weight $w(j,x)=p_{j}q_{x}$. This is an isolating weight
function because, by Lemma 3.2, the perfect matching formed by the edges
$(j,x_{j})$ is the only one in $G_{B}$ with minimum weight. Finally, by Lemma
3.2 again, the weight of a perfect matching in $G_{B}$ is at most

$(r-1)(n-1)+(r-2)(n-2)+\cdots+1\cdot(n-r+1)$

and hence less than $r(r-1)(n-1)/2$. ∎

By the following two propositions, lattice path matroids are the only
transversal matroids satisfying the sufficient condition in Proposition 3.3.

######  Proposition 3.4.

Let $M$ be a lattice path matroid and let $G$ be a presentation of $M$ in the
conditions of Proposition 2.1. If $B=(x_{1},\ldots,x_{r})$ is a basis of $M$,
then $(j,x_{j})$ is an edge of $G$ for every $j\in J$.

###### Proof.

Suppose that there is a basis $B$ without that property. Let $P$ be a perfect
matching in $G_{B}$ with the maximum number of edges of the form $(j,x_{j})$
and take the minimum $k\in J$ such that $(k,x_{k})$ is not in $P$. Since $P$
is a perfect matching, $k\leq r-1$ and there exist
$\ell_{1},\ell_{2}\in[k+1,r]$ such that $(\ell_{1},x_{k})$ and
$(k,x_{\ell_{2}})$ are edges in $P$. Then

$a_{k}\leq a_{\ell_{1}}\leq x_{k}<x_{\ell_{2}}\leq b_{k}\leq b_{\ell_{1}}$

which implies that $(k,x_{k})$ and $(\ell_{1},x_{\ell_{2}})$ are edges of $G$.
Then

$P^{\prime}=(P\smallsetminus\\{(k,x_{\ell_{2}}),(\ell_{1},x_{k})\\})\cup\\{(k,x_{k}),(\ell_{1},x_{\ell_{2}})\\}$

is a perfect matching in $G_{B}$ having more edges of the form $(j,x_{j})$
than $P$. ∎

######  Proposition 3.5.

Let $M$ be a transversal matroid without loops that admits a presentation $G$
such that, for every basis $B=(x_{1},\ldots,x_{r})$ and for every $j\in J$,
the pair $(j,x_{j})$ is an edge. Then $M$ is a lattice path matroid.

###### Proof.

Let $B_{1}=(a_{1},\ldots,a_{r})$ and $B_{2}=(b_{1},\ldots,b_{r})$ be the first
and last bases of $M$ in the lexicographic order. We are going to prove that
the sequence of sets $([a_{j},b_{j}]\,:\,j\in J)$ is a presentation of $M$,
and hence it is a lattice path matroid. For two distinct bases $B,B^{\prime}$,
we notate $B\ll B^{\prime}$ if $B$ precedes $B^{\prime}$ in the lexicographic
order. We prove first that $x_{j}\in[a_{j},b_{j}]$ for each $j\in[r]$ if
$(x_{1},\ldots,x_{r})$ is a basis. Suppose that there is a basis with
$x_{j}<a_{j}$ for some $j\in[r]$. Take $B$ the first such basis in the
lexicographic order and the minimum $j\in[r]$ with $x_{j}<a_{j}$. Since
$B_{1}\ll B$, the minimum $k\in[r]$ with $x_{k}>a_{k}$ satisfies $k<j$. Then
$B^{\prime}=(B\smallsetminus\\{x_{k}\\})\cup\\{a_{k}\\}$ is another basis in
the same situation with $B^{\prime}\ll B$, a contradiction. Symmetrically,
$x_{j}\leq b_{j}$ for each $j\in[r]$. We prove next that $(j,x)$ is an edge if
$x\in[a_{j},b_{j}]$. Since $x$ is not a loop, there is an edge $(k,x)$. If
$k>j$ and $x\neq b_{j}$, consider the basis
$B=(a_{1},\ldots,a_{j-1},b_{j},\ldots,b_{r})$. Then
$(B\smallsetminus\\{b_{k}\\})\cup\\{x\\}$ is a basis and $x$ is its $j$-th
element, which implies that $(j,x)$ is an edge. Symmetrically, the same
happens if $k<j$ and $x\neq a_{j}$. ∎

The following result summarizes the discussion in this section and the
previous one.

######  Theorem 3.6.

There exists a deterministic algorithm that, given a presentation of a lattice
path matroid $M$ in the conditions of Proposition 2.1, provides a
representation of $M$ over a finite field with $q=p^{s}$ elements, where $p$
is an arbitrarily chosen prime number and $s=r(r-1)(n-1)/2$. The running time
of the algorithm is polynomial in $p$ and the size $n$ of the ground set.

###  3.3 Lattice Path Matroids with Large Clonal Classes

We present next an improvement to the algorithm in Theorem 3.6 that applies to
lattice path matroids with large clonal classes. It is very similar to the
constructions of hierarchical vector secret sharing schemes in [8, 12].

Take $J=[r]$, $S=[n]$, and integers $t_{i}$ with
$1=t_{1}<t_{2}<\cdots<t_{m}<t_{m+1}=n+1$. Consider the partition
$\Pi=(S_{i}\,:\,i\in[m])$ of $S$ with $S_{i}=[t_{i},t_{i+1}-1]$. For every
$x\in S$, put $\pi(x)=i$ if $x\in S_{i}$. Consider a bipartite graph $G$ in
the conditions of Proposition 2.1 such that, for each $i\in[m]$, all vertices
in $S_{i}$ have the same neighbors. Then $G$ is a presentation of a
$\Pi$-uniform lattice path matroid $M$. Observe that the port of $M$ at the
element $1\in S$ is a hierarchical access structure in which all players in
the same part are hierarchically equivalent.

As we did before, we replace the nonzero entries of the biadjacency matrix of
$G$ with polynomials in the variable $\alpha$ over some finite field. Take a
prime number $p$ such that $p>|S_{i}|=t_{i+1}-t_{i}$ for every $i\in[m]$. For
each $i\in[m]$, take $t_{i+1}-t_{i}$ distinct nonzero elements
$(\beta_{x}\,:\,x\in S_{i})$ in the finite field $\mathbf{F}_{p}$. For $j\in
J$ and $x\in S$, take $p_{j}=j-1$ and $q_{x}=m-\pi(x)$, and consider on the
edges of $G$ the weight function $w(j,x)=p_{j}q_{x}$. Finally, consider the
matrix $H$ that is obtained by replacing the entry in the biadjacency matrix
of $G$ corresponding to the edge $(j,x)$ with
$\beta_{x}^{j-1}\alpha^{w(j,x)}$.

We prove next that, for every basis $B$ of $M$, the determinant of the
submatrix $H_{B}$ formed by the corresponding columns is a nonzero polynomial.
Even though the chosen weight function is not isolating, we can check that the
coefficient of the minimum degree term is nonzero. Indeed, let
$B=(x_{1},\ldots,x_{r})$ be a basis of $M$. By Lemma 3.2, the perfect matching
$((j,x_{j})\,:\,j\in J)$ has minimum weight, but there are other perfect
matchings in $G_{B}$ with the same weight, namely the ones of the form
$((j,x_{\sigma j})\,:\,j\in J)$, where $\sigma$ is any permutation such that
$\pi(x_{\sigma j})=\pi(x_{j})$ for every $j\in J$. The entries corresponding
to the edges of $G_{B}$ involved in those perfect matchings lie on square
submatrices on the diagonal of $H_{B}$, one for each $i\in[m]$ with $B\cap
S_{i}\neq\emptyset$. The determinant of each of those submatrices is of the
form $\alpha^{\ell_{i}}\Delta_{i}$, where $\Delta_{i}$ is the determinant of a
Vandermonde-like matrix, and hence nonzero. Therefore, the coefficient of the
minimum degree term of $\det H_{B}$ is equal to $\prod_{i}\Delta_{i}\neq 0$.
Observe that the weight of a perfect matching in any subgraph $G_{B}$ is less
than $r(r-1)(m-1)/2$. At this point, the following result has been proved.

######  Proposition 3.7.

There exists a deterministic algorithm that, given a an $m$-uniform lattice
path matroid $M$ in the conditions above, provides a representation of $M$
over a finite field with $q=p^{s}$ elements, where $p$ is a prime larger than
the number of elements in each part and $s=r(r-1)(m-1)/2$. The running time of
the algorithm is polynomial in $p$ and the size $n$ of the ground set.

This algorithm improves on the one in Theorem 3.6 if the number of parts $m$
is small in relation to the size of the ground set. Even though the prime $p$
is larger, the degree $s$ of the extension can be much smaller and, as we
discussed before, this is the main parameter to be taken into account.

If we need representations over fields with small characteristic, we can
replace in Proposition 3.7 the prime number $p$ with a prime power, but in
this case the search of an irreducible polynomial is slightly more expensive
(see [24]).

Every bi-uniform matroid (that is, $m=2$) is a lattice path matroid. and hence
the algorithm in Proposition 3.7 provides representations with $s=r(r-1)/2$.
Nevertheless, the algorithm proposed in [1] is in general more efficient
because the degree of the extension is $s=d(d-1)/2$, where
$d=r(S_{1})+r(S_{2})-r$.

## Acknowledgment

Thanks to Anna de Mier for an enlightening discussion about transversal
matroids. The author’s work was supported by the Spanish Government under
projects PID2019-109379RB-I00 and PID2021-124928NB-I00.

## References

  * [1] Simeon Ball, Carles Padró, Zsuzsa Weiner, Chaoping Xing. On the representability of the bi-uniform matroid. SIAM J. Discrete Math. 27 1482–1491 (2013)
  * [2] Amos Beimel. Secret-Sharing Schemes: A Survey. IWCC 2011 Lecture Notes in Comput. Sci., 6639 11–46 (2011)
  * [3] Amos Beimel, Tamir Tassa, Enav Weinreb. Characterizing Ideal Weighted Threshold Secret Sharing. SIAM J. Discrete Math. 22 360–397 (2008)
  * [4] Joseph E. Bonin. An Introduction to Transversal Matroids. Lecture notes available at the author’s webpage (2010)
  * [5] Joseph Bonin, Carolyn Chun, Tara Fife. The excluded minors for lattice path polymatroids. Electron. J. Combin. 29 (2022)
  * [6] Joseph E. Bonin, Anna de Mier. Lattice path matroids: Structural properties. European J. Combin. 27 701–738 (2006)
  * [7] Joseph Bonin, Anna de Mier, Marc Noy. Lattice path matroids: enumerative aspects and Tutte polynomials. J. Combin. Theory Ser. A. 104 63–94 (2003)
  * [8] Ernest F. Brickell. Some ideal secret sharing schemes. J. Combin. Math. Combin. Comput. 9 105–113 (1989)
  * [9] Ernest F. Brickell, Daniel M. Davenport. On the classification of ideal secret sharing schemes. J. Cryptology, 4 123–134 (1991)
  * [10] Qi Chen, Chunming Tang, Zhiqiang Lin. Efficient explicit constructions of compartmented secret sharing schemes. Des. Codes Cryptogr. 87 913–2940 (2019)
  * [11] Qi Chen, Chunming Tang, Zhiqiang Lin. Compartmented Secret Sharing Schemes and Locally Repairable Codes. IEEE Trans. Commun. 68 5976–5987 (2020)
  * [12] Qi Chen, Chunming Tang, Zhiqiang Lin. Efficient Explicit Constructions of Multipartite Secret Sharing Schemes. IEEE Trans. Inf. Theory 68 601–631 (2022)
  * [13] László Csirmaz, Frantisek Matúš, Carles Padró. Bipartite secret sharing and staircases. arXiv, CoRR abs/2103.04904 (2021)
  * [14] Oriol Farràs, Jaume Martí-Farré, Carles Padró. Ideal Multipartite Secret Sharing Schemes. J. Cryptology 25 434–463 (2012)
  * [15] Oriol Farràs, Carles Padró. Ideal Hierarchical Secret Sharing Schemes. IEEE Trans. Inform. Theory 58 3273–3286 (2012)
  * [16] Oriol Farràs, Carles Padró, Chaoping Xing, An Yang: Natural Generalizations of Threshold Secret Sharing. IEEE Trans. Inf. Theory 60 1652–1664 (2014)
  * [17] Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, Saket Saurabh, Meirav Zehavi. Quasipolynomial Representation of Transversal Matroids with Applications in Parameterized Complexity. ITCS 2018: 32:1–32:13 (2018)
  * [18] Jaume Martí-Farré, Carles Padró. On Secret Sharing Schemes, Matroids and Polymatroids. J. Math. Cryptol. 4 95–120 (2010)
  * [19] František Matúš. Excluded minors for Boolean polymatroids. Discrete Math. 235 317–321 (2001)
  * [20] Pranabendu Misra, Fahad Panolan, M. S. Ramanujan, Saket Saurabh. Linear representation of transversal matroids and gammoids parameterized by rank. Theor. Comput. Sci. 818 51–59 (2020)
  * [21] Songbao Mo. Ideal hierarchical secret sharing and lattice path matroids. Des. Codes Cryptogr. 91 1335–1349 (2023)
  * [22] James Oxley. Matroid theory. Second edition. Oxford Science Publications, The Clarendon Press, Oxford University Press, New York (2011)
  * [23] Carles Padró, Germán Sáez. Secret sharing schemes with bipartite access structure. IEEE Trans. Inform. Theory 46 2596–2604 (2000)
  * [24] Victor Shoup. New algorithms for finding irreducible polynomials over finite fields. _Math. Coup._ 54 435–447 (1990)
  * [25] Gustavus J. Simmons. How to (Really) Share a Secret. _Advances in Cryptology – CRYPTO’88, Lecture Notes in Comput. Sci._ , 403 390–448 (1990)
  * [26] Tamir Tassa. Hierarchical Threshold Secret Sharing. J. Cryptology 20 237–264 (2007)
  * [27] Tamir Tassa, Nira Dyn. Multipartite Secret Sharing by Bivariate Interpolation. J. Cryptology 22 227–258 (2009)


# Multi-Layer Ranking with Large Language Models for News Source
Recommendation

Wenjia Zhang  0009-0004-5645-9926 Computer ScienceUniversity of
WarwickCoventryUK<EMAIL_ADDRESS>,  Lin Gui  0000-0002-8054-9524
InformaticsKing’s College LondonLondonUK<EMAIL_ADDRESS>,  Rob Procter
0000-0001-8059-5224 Computer ScienceUniversity of WarwickCoventryUK The Alan
Turing InstituteLondonUK<EMAIL_ADDRESS>and  Yulan He
0000-0003-3948-5845 InformaticsKing’s College LondonLondonUK The Alan Turing
InstituteLondonUK<EMAIL_ADDRESS>
(2024)

###### Abstract.

To seek reliable information sources for news events, we introduce a novel
task of expert recommendation, which aims to identify trustworthy sources
based on their previously quoted statements. To achieve this, we built a novel
dataset, called NewsQuote, consisting of 23,571 quote-speaker pairs sourced
from a collection of news articles. We formulate the recommendation task as
the retrieval of experts based on their likelihood of being associated with a
given query. We also propose a multi-layer ranking framework employing Large
Language Models to improve the recommendation performance. Our results show
that employing an in-context learning based LLM ranker and a multi-layer
ranking-based filter significantly improve both the predictive quality and
behavioural quality of the recommender system.

Recommender System, In-Context Learning, Large Language Model

††journalyear: 2024††copyright: rightsretained††conference: Proceedings of the
47th International ACM SIGIR Conference on Research and Development in
Information Retrieval; July 14–18, 2024; Washington, DC, USA††booktitle:
Proceedings of the 47th International ACM SIGIR Conference on Research and
Development in Information Retrieval (SIGIR ’24), July 14–18, 2024,
Washington, DC, USA††doi: 10.1145/3626772.3657966††isbn:
979-8-4007-0431-4/24/07††submissionid: sp7535††ccs: Information systems
Retrieval models and ranking

##  1\. Introduction

Identifying credible information sources plays a crucial role in ensuring the
integrity and accuracy of journalism. First, the reliability of the source of
a claim strengthens the groundwork for accurate assessments regarding the
authenticity of the claim (Chu et al., 2012; Mukherjee et al., 2013; Shu et
al., 2019; Al-Rakhami and Alamri, 2020; Qureshi et al., 2022). Second,
external information sources can provide additional evidence for verifying
claims’ veracity (Vladika and Matthes, 2023; Thorne et al., 2018; Schuster et
al., 2021; Augenstein et al., 2019; Hanselowski et al., 2019; Kotonya and
Toni, 2020; Wadden et al., 2020; Saakyan et al., 2021; Karadzhov et al.,
2017). Most fact-checking research assumes that the information provided by a
reputable platform is trustworthy. However, it is crucial to recognise that
these platforms can only be considered as secondary sources comparison to the
primary speakers quoted in articles. In practice, it is essential for fact-
checkers and journalists to seek out and consult credible primary sources
within the relevant field to gain insights (Procter et al., 2023).

Tailored software toolkits are designed to accommodate various strategies for
evaluating information sources, including the consideration of diversity
(Shang et al., 2022) and topic relevance (Cao et al., 2019). Moreover,
datasets have been curated to facilitate insights into the extraction and
attribution of quotes in news articles (Vaucher et al., 2021; Zhang and Liu,
2022). Quote Erat is the first interface designed for interactive exploration
of large-scale corpora of quotes from the news domain (Vukovic et al., 2022),
allowing users to retrieve relevant quotes and articles based on their
queries. These systems do not directly recommend potential information
sources, such as experts or organizations, in response to user queries.

In the booming of Large Language Models (LLMs) (Brown et al., 2020), content-
based recommendation methods have experienced a surge in effectiveness,
particularly due to the advancements in In-Context Learning(Li et al., 2023).
Various prompting techniques have been designed to enhance the capabilities of
recommender systems, serving diverse roles such as being a recommender (Dai et
al., 2023; Liu et al., 2023), a ranker (Hou et al., 2024), or a designer (Lyu
et al., 2023; Wang et al., 2023). In these approaches, LLMs function as a
substitute for a specific step within recommendation systems.

In this paper, we present an expert-based recommendation system for
identifying information sources by analyzing quote-speaker pairs within news
articles. Our contributions are: (1) We describe the construction of a novel
dataset, named NewsQuote111The dataset can be accessed at
https://zenodo.org/records/11032190, which contains quote-speaker pairs
extracted from a collection of news articles. (2) We implement a source
recommendation system that retrieves potential information sources for a given
query by leveraging historical quotations. (3) We enhance the expert retrieval
approach by integrating a multi-layer ranking-based filtering mechanism
consisting of LLM rankers. (4) Experimental results show that multi-layer LLM
ranking improves the predictive quality of the recommendation system while
mitigating popularity bias.

##  2\. Data Construction

We built our NewsQuote dataset from the AYLIEN coronavirus
dataset222https://aylien.com/resources/datasets/coronavirus-dataset, which
contains news articales published between November 2019 and August 2020. Apart
from text, each article is also accompanied with the meta data such as
authors, keywords, summary, source, publishing time, topical categories coded
by both the Interactive Advertising Bureau (IAB)
taxonomy333https://www.iab.com and the IPTC
NewsCodes444https://iptc.org/standards/newscodes/, as well as the recognized
entities and entity links from the DBpedia.

Data Deduplication As the same news story may be posted by multiple sources,
we removed news articles that are similar to what have already been published.
News articles were first sorted in chronological order. News duplicates were
then detected using a RoBERTa
classifier555https://huggingface.co/vslaykovsky/roberta-news-duplicates
trained with title-body pairs using semi-supervised learning (Rücklé et al.,
2019). For processing efficiency, the dataset was split into 16 equal-sized
subsets. For each subset, the titles and the first sentence of the news
summaries of the temporally-ordered news articles were sequentially fed as
input to the RoBERTa classifier. Any duplicates were removed. After data
deduplication, 158,325 news articles were kept.

| Test | Valid | Train
---|---|---|---
No. of samples | 2000 | 1961 | 19610
No. of articles | 1749 | 1741 | 13728
No. of speakers | 936 | 923 | 2843
Avg. quote length | 18.24 | 16.04 | 16.12
No. of domains | 184 | 185 | 258
No. of news categories | 441 | 428 | 634
No. of keywords | 21672 | 21769 | 70560

Table 1. The NewsQuote Dataset statistics. Speaker is the information source,
domain is the platform where article was published. Quote length is the No. of
words.

Quote Trigger Word Filtering For each of the selected articles, we segmented
the the main body into sentences, and then used a pre-trained BERT-based
semantic role labeling model (Shi and Lin, 2019) to extract verbs (or
predicates), subjects, and objects. We obtained a candidate verb list sorted
by their occurrence frequencies. After manually checking the most frequent
candidate verbs with occurrences over 100, we identified 352 quote trigger
words which are more likely indicative of direct or indirect quotes. Some of
the verbs are clearly indicative of quotes, such as ‘ _said_ ’, while others
may not be associated with quotes in a traditional sense, for example, ‘
_tweet_ ’. After identifying the quote trigger words, we only kept the
sentences with at least one trigger word, one subject, and one object. The
subject is regarded as a potential speaker and the object is considered as a
potential quotation. To ensure that the quotations are informative, we also
require that the length of the object should be more than three words.

Speaker and Quote Filtering We required that the subject of a candidate
sentence should be a person or an organisation, and therefore identified
potential speaker entities via the accompanied DBpedia ontology
labels666http://mappings.dbpedia.org/server/ontology/classes/ in the dataset.
As the same subject could have multiple mentions, we use the DBPedia entity
links for entity resolution and normalisation. In addition, we required a
named entity to appear at least twice in the dataset. Finally, to avoid the
sentence split error, we required the quotation marks to be paired in
sentences that contain direct quotes and mixed quotes.

Test Set Annotation Since in practice, given a topic, we can only identify
experts based on their previous quotes published in earlier news articles, we
divide the dataset into training, validation and test sets by the publishing
timestamps of news articles, ensuring speaker-quote pairs in the validation
and the test sets occurred later than those in the training set. To ensure
data quality, samples in the test set were manually screened by one annotator.

Dataset Statistics Our data covers three categories of quotes: direct quote,
indirect quote and mixed quote. In short, direct quotations are placed inside
quotation marks while indirect quotations are not, and a mix of direct and
indirect quotations have only part of the quotations placed inside quotation
marks. We roughly estimated the weight of each quotation type on the dataset
by the number and position of quotation marks: 81% for indirect quotes, 11%
for direct quotes, and 7% for mixed quotes. In the test set, there are 1,582
(79%) indirect quotes, 178 (9%) mixed quotes, and 240 direct quotes (12%).
Table 1 shows the statistics of our final NewsQuote dataset. In summary, we
have a total of 23,571 English speaker-quote pairs with 2,843 speakers from
263 global domains.

Figure 1. Illustration of the LLM Ranker and the Multi-layer Ranking-based
Filter

##  3\. Approaches

In our dataset, each sample $S_{i}$ consists of a context $d_{i}$, a quote-
speaker pair $(q,e)_{i}$ extracted from the context, and metadata $m_{i}$
inherited from the article where it originates. The context contains three
sentences, the primary sentence containing the speaker and quote, its
preceding sentence and the following sentence. The metadata are defined at the
document level and are sourced from the AYLIEN coronavirus dataset. We
formulate source recommendation as a retrieval problem, aiming at identifying
sources capable of commenting on the topic discussed in a given query, guided
by the historical quotes of the sources in news reports, and subsequently
ranking them by their relevance to the query. In our scenario, each context is
treated as a document, and a preprocessed news article title serves as the
query.

###  3.1. Expert Finding

We implemented both candidate-based and document-based expert retrieval
methods (Balog et al., 2009) for this source recommendation task.

The Candidate-based Expert Retrieval assumes that each term in the query is
sampled identically and independently, also that the document and the expert
source candidate are conditionally independent. The candidate-based approach
estimates $P(k|e)$ by:

$\displaystyle P(k|e)=\prod_{t\in k}\\{(1-\lambda)(\sum_{d\in
D}p(t|d)p(d|e))+\lambda p(t)\\}^{n(t,k)},$
$\displaystyle\lambda=\frac{\beta}{\beta+n(e)},\quad\beta=\frac{\sum_{E}|\\{d:n(e,d)>0\\}|\cdot|d|}{|E|},$

where $\lambda$ is the smoothing parameter, $p(t|d)$, $p(d|e)$ and $p(t)$ are
the conditional probability of a term $t$ in document $d$, the conditional
probability of a document $d$ given source $e$, and the probability of term
$t$, respectively. Both $p(t|d)$ and $p(t)$ are estimated by maximum
likelihood. $n(t,k)$ is the number of times a term $t$ appears in the query
$k$, $n(e,d)$ is the occurrence frequency of an source $e$ appeared in the
document $d$, $n(e)$ is the total number of tokens in all documents associated
with the source $e$, $|d|$ is the average document length, and $|E|$ is the
total number of sources.

The Document-based Expert Retrieval approach searches for sources via relevant
document collection by assuming the conditional independence between the query
and candidate, and estimates the probability of a term $t$ in each document.
The $P(k|e)$ is then calculated as:

$\displaystyle\small P(k|e)=\sum_{d\in D}\\{\prod_{t\in
k}((1-\lambda)p(t|d)+\lambda p(t))^{n(t,k)}\\}p(d|e),$
$\displaystyle\lambda=\frac{\beta}{\beta+n(d)},\quad\beta=|d|,$

where $n(d)$ is the length of document $d$.

In both expert finding approaches, the document-candidate associations
$p(d|e)$ is estimated by a simple Boolean model.

###  3.2. LLM-based Multi-Layer Ranking

Purely probability-based approaches face significant constraint due to the
limitation of the document corpus, making it challenging to efficiently
enhance models with additional knowledge in advance, especially when facing
unpredictable news topics. Instead, we take advantage of Large Language Models
to improve the performance of the recommender system.

LLM Ranker After obtaining a list of recommendations returned by the Expert
Finding methods, we employ LLMs to rerank the top recommended candidates. This
is achieved by devising a one-shot prompt template:

”You are a knowledgeable referrer. Given a query and the 10 potential
information sources (which may include both individuals and organizations)
retrieved based on the query, you need to rank the 10 potential sources in
order of relevance to the query, placing the source that is most likely to
provide information relevant to the query at the top of the list. Return the
new rank of sources only in the form of python list (exactly the same form of
the given list, just rerank it), please do not provide other words except for
the list. Here is an example: Query: ¡Example Query¿. 10 potential sources
are: ¡Candidate List for the Example Query¿, and then the output should be:
¡Reranked Candidate List¿. Now the query is: ¡Query¿. The source candidates
are: ¡Candidate List to Be Reranked¿”

Multi-layer Ranking-based Filter When using an LLM ranker to improve ranking
quality, the system’s predictive efficacy still depends on the probability-
based retrieval approach that provides the initial candidates. To expand the
pool of candidates considered for rankings, we propose a Multi-layer Ranking-
based Filter. This filter uses the one-shot LLM ranker as a component to
generate result from a wider range of candidates by sequentially sorting and
filtering through multiple layers. As shown in Fig. 1, in each layer, the
input candidate list is first randomly divided into several subgroups, and
then each subgroup is fed into an LLM ranker. The filter keeps only a subset
of the top-ranked candidates from each reranked subgroup candidate list, and
concatenates them into a new list of candidates for the subsequent layer.
Inspired by the Sequential Monte Carlo Steering (Lew et al., 2023), the LLM-
based filter operates N times to clone promising candidates and cull low-
likelihood ones.

Filter Strategy In our framework, the aforementioned filter undergoes multiple
iterations to generate confidence scores for the resulting candidates. We
employ two strategies to determine the final output based on the frequency of
retention by the filter. The Most Frequent Strategy only considers the output
from the last layer of the Multi-layer Ranking-based Filter. It selects
candidates with the highest frequency of occurrence across the repeated runs.
On the other hand, the Layer-Weighted Strategy considers the outputs of all
filter layers. It calculates the average repetition frequency of each layer
using a pre-defined set of weights, and then returns candidates with the
highest weighted occurrence score.

##  4\. Experiments

In this section, we describe how we set up experiments and evaluate the
results.

###  4.1. Setup

In experiments, we utilized context samples from the training set as the
document database and used article titles from the test set as queries. There
could be more than one source of information corresponding to an article title
query. We employed the GPT-3.5-Turbo and GPT4-Turbo as LLM rankers, and
GPT-3.5-Turbo as the Multi-layer Ranking-based Filter. The filter comprised a
2-layer structure: (1) In the first layer, we initialized with 100 candidates
returned by the document-centric approach, dividing them randomly into 10
groups. Each group then underwent reranking by an LLM ranker, with the top 5
candidates from each group being retained; (2) Subsequently, in the second
layer, the top 50 candidates from the first layer were shuffled, divided into
5 groups, and reranked by an LLM ranker. Only the top 2 candidates from each
group, as returned by the LLM ranker, were kept. Upon each run of the 2-layer
ranking-based filter, we obtained a list of 10 candidates. After repeating
this process 20 times, we determined the final output by adopting different
filter strategies mentioned in 3.2, resulting in the top 20 recommendations.

###  4.2. Metrics

Recall is the proportion of correctly identified information sources in the
top recommendations out of the total number of sources quoted in the article.

Mean Averaged Precision (MAP) is the mean of the precision at the points where
the relevant sources were retrieved.

Normalized Discounted Cumulative Gain at K first discounts the gain scale at
the $i$-th rank position by $\frac{1}{\log_{2}(i)}$, then adds up the
converted gain scales up to rank $k$, and finally normalizes the result by the
ideal ranking order.

Diversity is calculated as the average pairwise distance between items
appeared in the recommendation list. To encode entity features, we trained
Wikipedia2Vec embeddings (Yamada et al., 2020) on a Wikipedia database publish
in Jan 2024.

Coverage shows the percentage of information sources from the training dataset
being recommended on the test set.

Average Recommendation Popularity is the averaged popularity of the
recommended items on the training set. Here, we use the number of occurrences
in the training set as the popularity of the information source.

##  5\. Results

| CER | DER | ReDE4 | ReDE3.5
---|---|---|---|---
Recall | 0.2454 | 0.3241 | 0.3244 | 0.3249
MAP | 0.1342 | 0.2016 | 0.2257 | 0.1822
NDCG10 | 0.1619 | 0.2327 | 0.2512 | 0.2176

Table 2. Results of the Expert Retrieval baselines and LLM ranker. CER is the
Candidate-based Expert Retrieval, and DER is the Document-based Expert
Retrieval. ReDE3.5 used GPT-3.5 to rerank the top 10 candidates returned by
the DER, while ReDE4 used GPT-4.

As baselines, the Document-based Retrieval method performed much better than
the Candidate-based Retrieval method, scoring 7% to 8% higher in Recall, MAP,
and NDCG@10. This disparity is likely attributed to the fact that the training
set is organized by documents rather than by information source candidates.
When we applied the LLM ranker on the top 10 candidated returned by the
Document-based Retrieval approach, GPT-4 improved the MAP and NDCG@10 by 2%,
but GPT-3.5 did not yield improvement. This may be because GPT-4 possesses
more up-to-date knowledge compared to GPT-3.5. Interestingly, both the GPT-4
and GPT-3.5 rankers yielded a slight improvement in Recall, albeit negligible.
We attribute this phenomenon to the stochastic nature of LLM generation.

Although the single GPT-3.5 ranker did not perform well in reordering the top
10 candidates, integrating a multi-layer structural filter into the baseline
approach resulted in a modest improvement in Recall of the top 20 candidates
from the top 100 candidates by 0.5% to 2%. Given the task of recommending
sources for news stories, the diversity and comprehensiveness of sources are
also important alongside their reliability in providing accurate information.
Following the application of the Multi-layer Ranking-based Filter, the average
recommendation popularity decreased significantly from 71.68 to around 40.
This indicates that our approach has the capability to divert the baseline
from favoring popular sources. Moreover, allocating more weights from the last
layer to the first layer led to a slight decrease in recall, while increasing
MAP, NDCG@10, and popularity bias. Consequently, we conclude that the multi-
layer structure sacrifices ranking precision to increase recall and mitigate
popularity bias.

| DER | MRF | MRF0 | MRF1 | MRF2
---|---|---|---|---|---
Recall | 0.3909 | 0.4098 | 0.4080 | 0.4012 | 0.3940
MAP | 0.2056 | 0.1719 | 0.1808 | 0.1805 | 0.1795
NDCG10 | 0.2318 | 0.2059 | 0.2126 | 0.2127 | 0.2117
Diversity | 10.34 | 5.889 | 5.896 | 5.894 | 5.894
Coverage | 0.2085 | 0.2595 | 0.2562 | 0.2497 | 0.2497
ARP | 71.68 | 39.11 | 39.44 | 39.63 | 40.05

Table 3. Evaluations of the Multi-layer Ranking-based Filter on the top 20
candidates. DER denotes the Document-based Expert Retrieval. MRF represents
the DER results augmented by the multi-layer ranking-based filter using the
most frequent strategy. MRF0(MRF1, MRF2) denotes the DER results augmented by
the multi-layer ranking-based filter with the layer-weighted strategy and
layer weights [0.25,0.75]([0.5,0.5],[0.75,0.25]).

In evaluating the results, the golden answers refer to sources that were
actually cited in news reports, averaging only 1.052 golden answers per query.
These golden answers received a score of 1, while all other candidates
received a score of 0 when calculating Recall, MAP, and NDCG@10. As such, we
posit that the potential of the recommender system could be underestimated. In
reality, sources not cited in news articles may still hold value, and
therefore should be scored higher than zero.

##  6\. Conclusion and Future Work

This paper outlines the development of a novel dataset comprising quote-source
pairs extracted from news articles. It also presents a recommendation task,
aimed at identifying information sources for a given news topic query. Based
on the NewsQuote dataset, we explored the Expert Finding baselines for this
task, and proposed a Multi-layer Ranking-based Filter, which integrates LLM
rankers to enhance the capability of the recommender system. Results show that
the Multi-layer LLM Ranker improves predictive accuracy and mitigates
popularity bias, albeit at the expense of ranking precision. In future work,
we will engage with a more diverse document corpus and utilize human
evaluations to provide more practical ratings.

## Acknowledgements

This work was supported in part by the UK Engineering and Physical Sciences
Research Council (EP/V048597/1, EP/X019063/1) and a Turing AI Fellowship
(EP/V020579/1, EP/V020579/2).

## References

  * (1)
  * Al-Rakhami and Alamri (2020) Mabrook Al-Rakhami and Atif Alamri. 2020.  Lies Kill, Facts Save: Detecting COVID-19 Misinformation in Twitter.  _IEEE Access_ 8 (2020), 155961–155970.  https://doi.org/10.1109/ACCESS.2020.3019600
  * Augenstein et al. (2019) Isabelle Augenstein, Christina Lioma, Dongsheng Wang, Lucas Chaves Lima, Casper Hansen, Christian Hansen, and Jakob Grue Simonsen. 2019.  MultiFC: A Real-World Multi-Domain Dataset for Evidence-Based Fact Checking of Claims. In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNLP-IJCNLP 2019, Hong Kong, China, November 3-7, 2019_ , Kentaro Inui, Jing Jiang, Vincent Ng, and Xiaojun Wan (Eds.). Association for Computational Linguistics, 4684–4696.  https://doi.org/10.18653/V1/D19-1475
  * Balog et al. (2009) Krisztian Balog, Leif Azzopardi, and Maarten de Rijke. 2009.  A language modeling framework for expert finding.  _Inf. Process. Manag._ 45, 1 (2009), 1–19.  https://doi.org/10.1016/J.IPM.2008.06.003
  * Brown et al. (2020) Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language Models are Few-Shot Learners. In _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_ , Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.).  https://proceedings.neurips.cc/paper/2020/hash/1457c0d6bfcb4967418bfb8ac142f64a-Abstract.html
  * Cao et al. (2019) Tien Duc Cao, Ludivine Duroyon, François Goasdoué, Ioana Manolescu, and Xavier Tannier. 2019.  BeLink: Querying Networks of Facts, Statements and Beliefs. In _Proceedings of the 28th ACM International Conference on Information and Knowledge Management, CIKM 2019, Beijing, China, November 3-7, 2019_ , Wenwu Zhu, Dacheng Tao, Xueqi Cheng, Peng Cui, Elke A. Rundensteiner, David Carmel, Qi He, and Jeffrey Xu Yu (Eds.). ACM, 2941–2944.  https://doi.org/10.1145/3357384.3357851
  * Chu et al. (2012) Zi Chu, Steven Gianvecchio, Haining Wang, and Sushil Jajodia. 2012.  Detecting Automation of Twitter Accounts: Are You a Human, Bot, or Cyborg?  _IEEE Trans. Dependable Secur. Comput._ 9, 6 (2012), 811–824.  https://doi.org/10.1109/TDSC.2012.75
  * Dai et al. (2023) Sunhao Dai, Ninglu Shao, Haiyuan Zhao, Weijie Yu, Zihua Si, Chen Xu, Zhongxiang Sun, Xiao Zhang, and Jun Xu. 2023.  Uncovering ChatGPT’s Capabilities in Recommender Systems. In _Proceedings of the 17th ACM Conference on Recommender Systems, RecSys 2023, Singapore, Singapore, September 18-22, 2023_ , Jie Zhang, Li Chen, Shlomo Berkovsky, Min Zhang, Tommaso Di Noia, Justin Basilico, Luiz Pizzato, and Yang Song (Eds.). ACM, 1126–1132.  https://doi.org/10.1145/3604915.3610646
  * Hanselowski et al. (2019) Andreas Hanselowski, Christian Stab, Claudia Schulz, Zile Li, and Iryna Gurevych. 2019.  A Richly Annotated Corpus for Different Tasks in Automated Fact-Checking. In _Proceedings of the 23rd Conference on Computational Natural Language Learning, CoNLL 2019, Hong Kong, China, November 3-4, 2019_ , Mohit Bansal and Aline Villavicencio (Eds.). Association for Computational Linguistics, 493–503.  https://doi.org/10.18653/V1/K19-1046
  * Hou et al. (2024) Yupeng Hou, Junjie Zhang, Zihan Lin, Hongyu Lu, Ruobing Xie, Julian J. McAuley, and Wayne Xin Zhao. 2024.  Large Language Models are Zero-Shot Rankers for Recommender Systems. In _Advances in Information Retrieval - 46th European Conference on Information Retrieval, ECIR 2024, Glasgow, UK, March 24-28, 2024, Proceedings, Part II_ _(Lecture Notes in Computer Science, Vol. 14609)_ , Nazli Goharian, Nicola Tonellotto, Yulan He, Aldo Lipani, Graham McDonald, Craig Macdonald, and Iadh Ounis (Eds.). Springer, 364–381.  https://doi.org/10.1007/978-3-031-56060-6_24
  * Karadzhov et al. (2017) Georgi Karadzhov, Preslav Nakov, Lluís Màrquez, Alberto Barrón-Cedeño, and Ivan Koychev. 2017.  Fully Automated Fact Checking Using External Sources. In _Proceedings of the International Conference Recent Advances in Natural Language Processing, RANLP 2017, Varna, Bulgaria, September 2 - 8, 2017_ , Ruslan Mitkov and Galia Angelova (Eds.). INCOMA Ltd., 344–353.  https://doi.org/10.26615/978-954-452-049-6_046
  * Kotonya and Toni (2020) Neema Kotonya and Francesca Toni. 2020.  Explainable Automated Fact-Checking for Public Health Claims. In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020_ , Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (Eds.). Association for Computational Linguistics, 7740–7754.  https://doi.org/10.18653/V1/2020.EMNLP-MAIN.623
  * Lew et al. (2023) Alexander K Lew, Tan Zhi-Xuan, Gabriel Grand, and Vikash K Mansinghka. 2023.  Sequential Monte Carlo Steering of Large Language Models using Probabilistic Programs.  _arXiv preprint arXiv:2306.03081_ (2023).
  * Li et al. (2023) Jiazheng Li, Runcong Zhao, Yulan He, and Lin Gui. 2023.  OverPrompt: Enhancing ChatGPT Capabilities through an Efficient In-Context Learning Approach.  _CoRR_ abs/2305.14973 (2023).  https://doi.org/10.48550/ARXIV.2305.14973 arXiv:2305.14973
  * Liu et al. (2023) Junling Liu, Chao Liu, Renjie Lv, Kang Zhou, and Yan Zhang. 2023.  Is chatgpt a good recommender? a preliminary study.  _arXiv preprint arXiv:2304.10149_ (2023).
  * Lyu et al. (2023) Hanjia Lyu, Song Jiang, Hanqing Zeng, Yinglong Xia, and Jiebo Luo. 2023.  Llm-rec: Personalized recommendation via prompting large language models.  _arXiv preprint arXiv:2307.15780_ (2023).
  * Mukherjee et al. (2013) Arjun Mukherjee, Abhinav Kumar, Bing Liu, Junhui Wang, Meichun Hsu, Malú Castellanos, and Riddhiman Ghosh. 2013.  Spotting opinion spammers using behavioral footprints. In _The 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2013, Chicago, IL, USA, August 11-14, 2013_ , Inderjit S. Dhillon, Yehuda Koren, Rayid Ghani, Ted E. Senator, Paul Bradley, Rajesh Parekh, Jingrui He, Robert L. Grossman, and Ramasamy Uthurusamy (Eds.). ACM, 632–640.  https://doi.org/10.1145/2487575.2487580
  * Procter et al. (2023) Rob Procter, Miguel Arana Catania, Yulan He, Maria Liakata, Arkaitz Zubiaga, Elena Kochkina, and Runcong Zhao. 2023.  Some Observations on Fact-Checking Work with Implications for Computational Support.  _arXiv preprint arXiv:2305.02224_ (2023).
  * Qureshi et al. (2022) Khubaib Ahmed Qureshi, Rauf Ahmed Shams Malick, Muhammad Sabih, and Hocine Cherifi. 2022.  Deception detection on social media: A source-based perspective.  _Knowl. Based Syst._ 256 (2022), 109649.  https://doi.org/10.1016/J.KNOSYS.2022.109649
  * Rücklé et al. (2019) Andreas Rücklé, Nafise Sadat Moosavi, and Iryna Gurevych. 2019.  Neural Duplicate Question Detection without Labeled Training Data. In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNLP-IJCNLP 2019, Hong Kong, China, November 3-7, 2019_ , Kentaro Inui, Jing Jiang, Vincent Ng, and Xiaojun Wan (Eds.). Association for Computational Linguistics, 1607–1617.  https://doi.org/10.18653/V1/D19-1171
  * Saakyan et al. (2021) Arkadiy Saakyan, Tuhin Chakrabarty, and Smaranda Muresan. 2021.  COVID-Fact: Fact Extraction and Verification of Real-World Claims on COVID-19 Pandemic. In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing, ACL/IJCNLP 2021, (Volume 1: Long Papers), Virtual Event, August 1-6, 2021_ , Chengqing Zong, Fei Xia, Wenjie Li, and Roberto Navigli (Eds.). Association for Computational Linguistics, 2116–2129.  https://doi.org/10.18653/V1/2021.ACL-LONG.165
  * Schuster et al. (2021) Tal Schuster, Adam Fisch, and Regina Barzilay. 2021.  Get Your Vitamin C! Robust Fact Verification with Contrastive Evidence. In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2021, Online, June 6-11, 2021_ , Kristina Toutanova, Anna Rumshisky, Luke Zettlemoyer, Dilek Hakkani-Tür, Iz Beltagy, Steven Bethard, Ryan Cotterell, Tanmoy Chakraborty, and Yichao Zhou (Eds.). Association for Computational Linguistics, 624–643.  https://doi.org/10.18653/V1/2021.NAACL-MAIN.52
  * Shang et al. (2022) Xiaoxiao Shang, Zhiyuan Peng, Qiming Yuan, Sabiq Khan, Lauren Xie, Yi Fang, and Subramaniam Vincent. 2022.  DIANES: A DEI Audit Toolkit for News Sources. In _SIGIR ’22: The 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, Madrid, Spain, July 11 - 15, 2022_ , Enrique Amigó, Pablo Castells, Julio Gonzalo, Ben Carterette, J. Shane Culpepper, and Gabriella Kazai (Eds.). ACM, 3312–3317.  https://doi.org/10.1145/3477495.3531660
  * Shi and Lin (2019) Peng Shi and Jimmy Lin. 2019.  Simple bert models for relation extraction and semantic role labeling.  _arXiv preprint arXiv:1904.05255_ (2019).
  * Shu et al. (2019) Kai Shu, Xinyi Zhou, Suhang Wang, Reza Zafarani, and Huan Liu. 2019.  The role of user profiles for fake news detection. In _ASONAM ’19: International Conference on Advances in Social Networks Analysis and Mining, Vancouver, British Columbia, Canada, 27-30 August, 2019_ , Francesca Spezzano, Wei Chen, and Xiaokui Xiao (Eds.). ACM, 436–439.  https://doi.org/10.1145/3341161.3342927
  * Thorne et al. (2018) James Thorne, Andreas Vlachos, Oana Cocarascu, Christos Christodoulopoulos, and Arpit Mittal. 2018.  The Fact Extraction and VERification (FEVER) Shared Task. In _Proceedings of the First Workshop on Fact Extraction and VERification (FEVER)_. Association for Computational Linguistics, Brussels, Belgium, 1–9.  https://doi.org/10.18653/v1/W18-5501
  * Vaucher et al. (2021) Timoté Vaucher, Andreas Spitz, Michele Catasta, and Robert West. 2021.  Quotebank: A Corpus of Quotations from a Decade of News. In _WSDM ’21, The Fourteenth ACM International Conference on Web Search and Data Mining, Virtual Event, Israel, March 8-12, 2021_ , Liane Lewin-Eytan, David Carmel, Elad Yom-Tov, Eugene Agichtein, and Evgeniy Gabrilovich (Eds.). ACM, 328–336.  https://doi.org/10.1145/3437963.3441760
  * Vladika and Matthes (2023) Juraj Vladika and Florian Matthes. 2023.  Scientific Fact-Checking: A Survey of Resources and Approaches. In _Findings of the Association for Computational Linguistics: ACL 2023, Toronto, Canada, July 9-14, 2023_ , Anna Rogers, Jordan L. Boyd-Graber, and Naoaki Okazaki (Eds.). Association for Computational Linguistics, 6215–6230.  https://doi.org/10.18653/V1/2023.FINDINGS-ACL.387
  * Vukovic et al. (2022) Vuk Vukovic, Akhil Arora, Huan-Cheng Chang, Andreas Spitz, and Robert West. 2022.  Quote Erat Demonstrandum: A Web Interface for Exploring the Quotebank Corpus. In _SIGIR ’22: The 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, Madrid, Spain, July 11 - 15, 2022_ , Enrique Amigó, Pablo Castells, Julio Gonzalo, Ben Carterette, J. Shane Culpepper, and Gabriella Kazai (Eds.). ACM, 3350–3354.  https://doi.org/10.1145/3477495.3531696
  * Wadden et al. (2020) David Wadden, Shanchuan Lin, Kyle Lo, Lucy Lu Wang, Madeleine van Zuylen, Arman Cohan, and Hannaneh Hajishirzi. 2020.  Fact or Fiction: Verifying Scientific Claims. In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020_ , Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (Eds.). Association for Computational Linguistics, 7534–7550.  https://doi.org/10.18653/V1/2020.EMNLP-MAIN.609
  * Wang et al. (2023) Wenjie Wang, Xinyu Lin, Fuli Feng, Xiangnan He, and Tat-Seng Chua. 2023.  Generative recommendation: Towards next-generation recommender paradigm.  _arXiv preprint arXiv:2304.03516_ (2023).
  * Yamada et al. (2020) Ikuya Yamada, Akari Asai, Jin Sakuma, Hiroyuki Shindo, Hideaki Takeda, Yoshiyasu Takefuji, and Yuji Matsumoto. 2020.  Wikipedia2Vec: An Efficient Toolkit for Learning and Visualizing the Embeddings of Words and Entities from Wikipedia. In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, EMNLP 2020 - Demos, Online, November 16-20, 2020_ , Qun Liu and David Schlangen (Eds.). Association for Computational Linguistics, 23–30.  https://doi.org/10.18653/V1/2020.EMNLP-DEMOS.4
  * Zhang and Liu (2022) Yuanchi Zhang and Yang Liu. 2022.  DirectQuote: A Dataset for Direct Quotation Extraction and Attribution in News Articles. In _Proceedings of the Thirteenth Language Resources and Evaluation Conference, LREC 2022, Marseille, France, 20-25 June 2022_ , Nicoletta Calzolari, Frédéric Béchet, Philippe Blache, Khalid Choukri, Christopher Cieri, Thierry Declerck, Sara Goggi, Hitoshi Isahara, Bente Maegaard, Joseph Mariani, Hélène Mazo, Jan Odijk, and Stelios Piperidis (Eds.). European Language Resources Association, 6959–6966.  https://aclanthology.org/2022.lrec-1.752