# The orthogonal Shmaliy polynomials are Hahn polynomials.

Enno Diekema 111email adress<EMAIL_ADDRESS>
###### Abstract

Morales-Mendoza et al. present in 2013 a new class of discrete orthogonal
polynomials. They use these polynomials to design an unbiased FIR filter. In
their paper they make the statement that a representation of the polynomials
via hypergeometric functions is unknown. However Shakibaei Asli et al. found
in 2017 a ${}_{3}F_{2}$ hypergeometric function representation. In this paper
it is shown that the ”new” orthogonal polynomials belong to the class of the
Hahn polynomials. The transfer function of the unbiased FIR filter has been
determined. In the second part, an orthogonal unbiased FIR filter is designed
following the method of the orthogonal derivative described in the thesis of
the author. In the Appendix a table with a number of possible transformations
of the Hahn polynomials is given.

##  1 Introduction

The author during his work at an hospital had to calculate the derivative of a
given function concerning the pressure in the eye. The signal was seriously
disturbed by noise so an averaging routine had to be used. He used the well-
known least square procedure. The result was a formula for a discrete low pass
filter based on a summation with discrete orthogonal polynomials. In this way
the orthogonal difference arose. He then expands the theory to the continuous
case and so he found a formula for the orthogonal derivative based on an
integral with continuous orthogonal polynomials [4], [5].

The formula found for the $n-$th orthogonal derivative and $n-$th orthogonal
difference are both dependent of the order of the used orthogonal polynomials.
When the order is set to zero the filter becomes a low pass filter based on
orthogonal polynomials. In this paper we consider only the discrete filter.

In [5, section 4] an discrete orthogonal filter is treated and in [5, section
5] the theory is applied using the Hahn polynomials. The filter is a finite
impulse response (FIR) filter. The author was unaware of the papers of Shmaliy
in which Shmaliy et al. developed a theory for an unbiased FIR filter (UFIR)
with an orthogonal polynomial [13]. In [9] the authors claim that the
orthogonal polynomials found are new orthogonal polynomials. In [12] the
authors found that the ”new” orthogonal polynomials can be described as a
hypergeometric function.

In section 2 it is shown that the UFIR functions derived by Shmaliy are Hahn
polynomials. In section 3 the transfer function of the UFIR is derived. In
section 4 the orthogonal UFIR filter based on the theory of the orthogonal
derivative is treated.

##  2 The UFIR function as a Hahn polynomial

The $n-$th degree discrete Shmaliy polynomials are defined as

$h_{m}(n,N)=\sum_{i=0}^{m}a_{im}(N)n^{i}$

with $0\leq n\leq N-1$. The coefficients $a_{im}$ are defined as

$a_{im}(N)=(-1)^{i}\dfrac{M^{(m)}_{(i+1),1}(N)}{|H_{m}(N)|}$

where $H_{m}(N)|$ is the determinant and $M^{(m)}_{(i+1),1}(N)$ is the minor
of the Hankel matrix $H_{m}(N)$

$H_{m}(N)=\left(\begin{array}[]{cccc}c_{0}&c_{1}&\dots&c_{m}\\\
c_{1}&c_{2}&\dots&c_{m+1}\\\ \dots&\dots&\dots&\dots\\\
c_{m}&c_{m+1}&\dots&c_{2m}\end{array}\right)$

The elements of the Hankel matrix are given by the power series

$c_{k}(N)=\sum_{i=0}^{N-1}i^{k}=\dfrac{1}{k+1}\left(B_{k+1}(N)-B_{k+1}\right)$

where $B_{k}(x)$ is the Bernoulli polynomial and $B_{k}=B_{k}(0)$ is the
Bernoulli number. For the Shmaliy polynomial we get

$h_{m}(n,N)=\sum_{i=0}^{m}(-1)^{i}\dfrac{M^{(m)}_{(i+1),1}(N)}{|H_{m}(N)|}$

In [9] the following properties of the discrete polynomials are proved

$\displaystyle\sum_{n=0}^{N-1}h_{m}(n,N)=1$
$\displaystyle\sum_{n=0}^{N-1}x^{q}h_{m}(n,N)=0\qquad 1\leq q\leq n$
$\displaystyle\sum_{n=0}^{N-1}h_{m}^{2}(n,N)<\infty$

The orthogonality property is

$\sum_{n=0}^{N-1}\rho(n,N)h_{m}(n,N)h_{q}(n,N)=(d_{m})^{2}\delta_{mq}$

with weight function

$\rho(n,N)=\dfrac{2n}{N(N-1)}$

and

$(d_{m})^{2}=\dfrac{(m+1)(N-m-1)}{N(N)_{m+1}}=\dfrac{(m+1)\Gamma(N-1)\Gamma(N)}{\Gamma(N-m-1)N\Gamma(N+m+1)}$

They found the recurrence relation

$h_{m}(n,N)=2\dfrac{m^{2}(2N-1)-(4m^{2}-1)n}{m(2m-1)(N+m)}h_{m-1}(n,N)-\dfrac{(2m+1)(N-m)}{(2m-1)(N+m)}h_{m-1}(n,N)$

with $m\geq 1,\ h_{-1}(n,N)=0$ and $h_{0}(n,N)=\dfrac{1}{N}$. The first four
functions are

$\displaystyle h_{0}(n,N)=\dfrac{1}{N}$ $\displaystyle
h_{1}(n,N)=\dfrac{2(2N-1)-6n}{N(N+1)}$ $\displaystyle
h_{2}(n,N)=\dfrac{3(3N^{2}-3N+2)-18(2N-1)n+30n^{2}}{N(N+1)(N+2)}$
$\displaystyle
h_{3}(n,N)=\dfrac{120(2N-1)n^{2}-140n^{3}}{N(N+1)(N+2)(N+3)}-\dfrac{8(2N^{3}-3N^{2}+7N-3)+20(6N^{2}-6N+5)n}{N(N+1)(N+2)(N+3)}$

In [12] the authors prove that $h_{m}(n,N)$ can be written as a hypergeometric
function

$h_{m}(n,N)=(-1)^{m}\dfrac{(m+1)(n-m)_{m}(N-n)_{m}}{m!(N)_{m+1}}\,\mbox{}_{3}F_{2}\\!\left(\genfrac{}{}{0.0pt}{}{-m,n+1,1-N+n}{n-m,1-N-m+n};1\right)$
(2.1)

We found by trial and error the following much simpler hypergeometric function

$h_{m}(n,N)=\dfrac{(m+1)^{2}}{N}\,\mbox{}_{3}F_{2}\\!\left(\genfrac{}{}{0.0pt}{}{-m,n+1,m+2}{2,1+N};1\right)$
(2.2)

To prove that (2.1) is equal (2.2) we use the following properties of the
Pochhammer symbols and the Gamma functions

$(-1-m)_{m}=\frac{\Gamma(-1)}{\Gamma(-1-m)}=(-1)^{m}\Gamma(m+2)$
$\dfrac{\Gamma(N-n+m)\Gamma(1-N-m+n)}{\Gamma(N-n)\Gamma(1-N+n)}=\dfrac{\sin(N-n)\pi}{\sin(N-n+m)\pi}=\dfrac{1}{\cos
m\pi}=(-1)^{m}$
$\dfrac{\Gamma(N+1)\Gamma(-N)}{\Gamma(1+N+m)\Gamma(-N-m)}=(-1)^{m}$

Application of (A.1) to (2.1) gives

$\displaystyle h_{m}(n,N)$
$\displaystyle=(-1)^{m}\dfrac{(m+1)(n-m)_{m}(N-n)_{m}}{m!(N)_{m+1}}\dfrac{(-1-m)_{m}(N-m)_{m}}{(n-m)_{m}(1-N-m+n)_{m}}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\,\mbox{}_{3}F_{2}\\!\left(\genfrac{}{}{0.0pt}{}{-m,n+1,m+2}{2,1+N};1\right)$
$\displaystyle=\dfrac{(-1)^{m}(m+1)}{\Gamma(m+1)}(-1-m)_{m}\dfrac{(N-n)_{m}}{(1-N-m+n)_{m}}\dfrac{(-N-m)_{m}}{(N)_{m+1}}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\,\mbox{}_{3}F_{2}\\!\left(\genfrac{}{}{0.0pt}{}{-m,n+1,m+2}{2,1+N};1\right)$
$\displaystyle=\left[\dfrac{(-1)^{m}(m+1)}{\Gamma(m+1)}(-1-m)_{m}\right]\left[\dfrac{\Gamma(N-n+m)\Gamma(1-N-m+n)}{\Gamma(N-n)\Gamma(1-N+n)}\right]\left[\dfrac{\Gamma(N)}{\Gamma(N+1)}\right]$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\ \
\left[\dfrac{\Gamma(N+1)\Gamma(-N)}{\Gamma(1+N+m)\Gamma(-N-m)}\right]\,\mbox{}_{3}F_{2}\\!\left(\genfrac{}{}{0.0pt}{}{-m,n+1,m+2}{2,1+N};1\right)$
$\displaystyle=\Big{[}(m+1)^{2}\Big{]}\Big{[}(-1)^{m}\Big{]}\Big{[}\dfrac{1}{N}\Big{]}\Big{[}(-1)^{m}\Big{]}\,\mbox{}_{3}F_{2}\\!\left(\genfrac{}{}{0.0pt}{}{-m,n+1,m+2}{2,1+N};1\right)$
$\displaystyle=\dfrac{(m+1)^{2}}{N}\,\mbox{}_{3}F_{2}\\!\left(\genfrac{}{}{0.0pt}{}{-m,n+1,m+2}{2,1+N};1\right)$

and this is (2.2). This is one of the Thomae transformations for the
${}_{3}F_{2}$ hypergeometric function with unit argument. In Appendix A the
standard transformations are given.

Both hypergeometric functions can be written as Hahn polynomials. [8, (9.5.1)]
gives as definition

$Q_{m}(y;\alpha,\beta,M)=\,\mbox{}_{3}F_{2}\\!\left(\genfrac{}{}{0.0pt}{}{-m.m+\alpha+\beta+1,-y}{\alpha+1,-M};1\right)\qquad
m=0,1,2,\dots,M$

which are orthogonal as $\alpha>-1$ and $\beta>-1$, or $\alpha<-M$ and
$\beta<-M$. These are polynomials of $m$-th degree.

Setting $\alpha=1$, $\beta=0$, $M=-1-N$ and $y=-n-1$ gives

$h_{m}(n,N)=\dfrac{(m+1)^{2}}{N}Q_{m}(-1-n;1,0,-1-N)$

With the transformations of the ${}_{3}F_{2}$ hypergeometric function there
are 31 transformations of the Hahn polynomials. See Appendix B. We choose

$Q_{m}(y;\alpha,\beta,N)=\dfrac{(-m-\beta)_{m}(-N-m-\alpha-\beta-1)_{m}}{(\alpha+1)_{m}(-N)_{m}}Q_{m}(y-N-\beta;\beta,\alpha,-N-\alpha-\beta-2)$

Application gives

$h_{m}(n,N)=\dfrac{(m+1)^{2}}{N}\dfrac{(-m)_{m}(N-1-m)_{m}}{(2)_{m}(N+1)_{m}}Q_{m}(N-n;0,1,N-2)$

Simplifying with $(-m)_{m}=(-1)^{m}\Gamma(m+1)$ gives at last

$h_{m}(n,N)=\dfrac{(m+1)(N+m+1)}{N(N+1)}Q_{m}(N-n;0,1,N-2)$

The conclusion is that the function $h_{m}(n,N)$ is a well known orthogonal
Hahn polynomial.

##  3 The general transfer function of the UFIR Shmaliy function

In [14] Shmialy et al. compute the transfer functions of the Unbiased FIR
function $h_{m}(N,N)$ for the values $m=1,\ 2$ and $3$. In this section a
general formula for the transfer function is derived. We start with (2.2)

$h_{m}(n,N)=\dfrac{(m+1)^{2}}{N}\,\mbox{}_{3}F_{2}\\!\left(\genfrac{}{}{0.0pt}{}{-m,n+1,m+2}{2,N+1};1\right)$

and write the hypergeometric function as a summation

$h_{m}(n,N)=\dfrac{(m+1)^{2}}{N}\sum_{k=0}^{m}\dfrac{(-m)_{k}(n+1)_{k}(m+2)_{k}}{(2)_{k}(N+1)_{k}}\dfrac{1}{k!}$

For computing the transfer function we use the $z$-transform with
$z=\exp(j\omega T)$

$\displaystyle H_{m}(z,N)$ $\displaystyle=\sum_{n=0}^{N-1}h_{m}(n,N)z^{-n}$
$\displaystyle=\sum_{n=0}^{N-1}\dfrac{(m+1)^{2}}{N}\sum_{k=0}^{m}\dfrac{(-m)_{k}(n+1)_{k}(m+2)_{k}}{(2)_{k}(N+1)_{k}}\dfrac{1}{k!}z^{-n}$

After using $(1+n)_{k}=(1+k)_{n}(1)_{k}/(1)_{n}$ and interchanging the
summations we get

$H_{m}(z,N)=\dfrac{(m+1)^{2}}{N}\sum_{k=0}^{m}\dfrac{(-m)_{k}(m+2)_{k}(1)_{k}}{(2)_{k}(N+1)_{k}}\dfrac{1}{k!}\sum_{n=0}^{N-1}\dfrac{(1+k)_{n}}{(1)_{n}}z^{-n}$

The last summation is known.

$H_{m}(z,N)=\dfrac{(m+1)^{2}}{N}\left(\dfrac{z}{z-1}\right)\sum_{k=0}^{m}\dfrac{(-m)_{k}(m+2)_{k}(1)_{k}}{(2)_{k}(N+1)_{k}}\dfrac{1}{k!}\left(\dfrac{z}{z-1}\right)^{k}\\\
\left[1-z^{-N}(N+1)_{k}\dfrac{1}{k!}\,\mbox{}_{2}F_{1}\\!\left(\genfrac{}{}{0.0pt}{}{-k,N}{N+1};\dfrac{1}{z}\right)\right]$

Applying a Gauss transformation to the hypergeometric function gives

$H_{m}(z,N)=\dfrac{(m+1)^{2}}{N}\left(\dfrac{z}{z-1}\right)\sum_{k=0}^{m}\dfrac{(-m)_{k}(m+2)_{k}(1)_{k}}{(2)_{k}(N+1)_{k}}\dfrac{1}{k!}\left(\dfrac{z}{z-1}\right)^{k}-\\\
-z^{-N}\dfrac{(m+1)^{2}}{N}\sum_{k=0}^{m}\dfrac{(-m)_{k}(m+2)_{k}}{(2)_{k}}\dfrac{1}{k!}\sum_{i=0}^{\infty}\dfrac{(N+1+k)_{i}(1)_{i}}{(N+1)_{i}}\dfrac{1}{i!}\left(\dfrac{1}{z}\right)^{i}$

After using $(N+1+k)_{i}=(N+1+i)_{k}(N+1)_{i}/(N+1)_{k}$, interchanging the
summations and writing the summation over $k$ as a hypergeometric function we
get

$H_{m}(z,N)=\dfrac{(m+1)^{2}}{N}\left(\dfrac{z}{z-1}\right)\sum_{k=0}^{m}\dfrac{(-m)_{k}(m+2)_{k}(1)_{k}}{(2)_{k}(N+1)_{k}}\dfrac{1}{k!}\left(\dfrac{z}{z-1}\right)^{k}-\\\
-z^{-N}\dfrac{(m+1)^{2}}{N}\sum_{i=0}^{\infty}\left(\dfrac{1}{z}\right)^{i}\,\mbox{}_{3}F_{2}\\!\left(\genfrac{}{}{0.0pt}{}{-m,m+2,N+1+i}{2,N+1};1\right)$
(3.1)

For the hypergeometric function we use (A.6).

$\,\mbox{}_{3}F_{2}\\!\left(\genfrac{}{}{0.0pt}{}{-m,m+2,N+1+i}{2,N+1};1\right)=\dfrac{(-m)_{m}}{(2)_{m}}\,\mbox{}_{3}F_{2}\\!\left(\genfrac{}{}{0.0pt}{}{-i,m,m+2}{1,N+1};1\right)=\\\
=\dfrac{(-1)^{m}}{(m+1)}\,\mbox{}_{3}F_{2}\\!\left(\genfrac{}{}{0.0pt}{}{-i,m,m+2}{1,N+1};1\right)=\dfrac{(-1)^{i}}{(m+1)}\sum_{k=0}^{\infty}\dfrac{(-i)_{k}(-m)_{k}(m+2)_{k}}{(1)_{k}(N+1)_{k}}\dfrac{1}{k!}$

Using $(-i)_{k}=(-1)^{k}\dfrac{(1)_{i}}{\Gamma(1-k)(1-k)_{i}}$ gives

$\,\mbox{}_{3}F_{2}\\!\left(\genfrac{}{}{0.0pt}{}{-m,m+2,N+1+i}{2,N+1};1\right)=\dfrac{(-1)^{m}(-1)_{i}}{(m+1)}\sum_{k=0}^{\infty}\dfrac{(-m)_{k}(m+2)_{k}}{(1)_{k}(N+1)_{k}\Gamma(1-k)(1-k)_{i}}\dfrac{1}{k!}(-1)^{k}$

Substitution in (3.1) and interchanging the summation in the last
hypergeometric function gives

$H_{m}(z,N)=\dfrac{(m+1)^{2}}{N}\left(\dfrac{z}{z-1}\right)\sum_{k=0}^{m}\dfrac{(-m)_{k}(m+2)_{k}(1)_{k}}{(2)_{k}(N+1)_{k}}\dfrac{1}{k!}\left(\dfrac{z}{z-1}\right)^{k}-\\\
-z^{-N}\dfrac{(m+1)^{2}}{N}\sum_{k=0}^{m}\dfrac{(-m)_{k}(m+2)_{k}}{(1)_{k}(N+1)_{k}}\dfrac{1}{k!}\dfrac{(-1)^{k}}{\Gamma(1-k)}\sum_{i=0}^{\infty}\dfrac{(1)_{i}(1)_{i}}{(1-k)_{i}}\left(\dfrac{1}{z}\right)^{i}$
(3.2)

For the last summation we can use the following property of the hypergeometric
function

$\dfrac{1}{\Gamma(-M)}\
_{p+1}F_{p}\left(\begin{array}[]{l}a_{0},\dots,a_{p}\\\
-M,b_{2},\dots,b_{p}\end{array};x\right)=\\\
=\dfrac{x^{M+1}(a_{0})_{M+1}\dots(a_{p})_{M+1}}{\Gamma(M+2)(b_{2})_{M+1}\dots(b_{p})_{M+1}}\
_{p+1}F_{p}\left(\begin{array}[]{l}a_{0}+M+1,\dots,a_{p}+M+1\\\
M+2,b_{2}+M+1,\dots,b_{p}+M+1\end{array};x\right)$

with $M$ a positive integer. For the proof of this formula see [6, Lemma 2].
The result is

$\dfrac{(-1)^{k}}{\Gamma(1-k)}\sum_{i=0}^{\infty}\dfrac{(1)_{i}(1)_{i}}{(1-k)_{i}}\left(\dfrac{1}{z}\right)^{i}=(-1)^{k}\left(\dfrac{1}{z}\right)^{k}(1)_{k}\sum_{i=0}^{\infty}(1+k)_{i}\dfrac{1}{i!}\left(\dfrac{1}{z}\right)^{i}=\\\
=(-1)^{k}\left(\dfrac{1}{z}\right)^{k}(1)_{k}\left(\dfrac{z}{z-1}\right)^{k+1}=\left(\dfrac{z}{z-1}\right)(1)_{k}\left(\dfrac{1}{1-z}\right)^{k}$

Substitution in (3.2) gives

$H_{m}(z,N)=\dfrac{(m+1)^{2}}{N}\left(\dfrac{z}{z-1}\right)\sum_{k=0}^{m}\dfrac{(-m)_{k}(m+2)_{k}(1)_{k}}{(2)_{k}(N+1)_{k}}\dfrac{1}{k!}\left(\dfrac{z}{z-1}\right)^{k}-\\\
-z^{-N}\dfrac{(m+1)}{N}(-1)^{m}\left(\dfrac{z}{z-1}\right)\sum_{k=0}^{m}\dfrac{(-m)_{k}(m+2)_{k}}{(N+1)_{k}}\dfrac{1}{k!}\left(\dfrac{1}{1-z}\right)^{k}$

The first summation is known.

$\sum_{k=0}^{m}\dfrac{(-m)_{k}(m+2)_{k}(1)_{k}}{(2)_{k}(N+1)_{k}}\dfrac{1}{k!}\left(\dfrac{z}{z-1}\right)^{k}=\dfrac{N}{(1+m)^{2}}\left(\dfrac{z-1}{z}\right)\left[1-\,\mbox{}_{2}F_{1}\\!\left(\genfrac{}{}{0.0pt}{}{-1-m,1+m}{N};\dfrac{z}{z-1}\right)\right]$

Substitution gives for the transfer function

$H_{m}(z,N)=1-\,\mbox{}_{2}F_{1}\\!\left(\genfrac{}{}{0.0pt}{}{-1-m,1+m}{N};\dfrac{z}{z-1}\right)-(-1)^{m}\dfrac{(m+1)}{N}\dfrac{z^{1-N}}{z-1}\,\mbox{}_{2}F_{1}\\!\left(\genfrac{}{}{0.0pt}{}{-m,m+2}{N+1};\dfrac{1}{1-z}\right)$

Application of Gauss transformations to both hypergeometric functions results
in

$H_{m}(z,N)=1-\left(\dfrac{1}{1-z}\right)^{m+1}\,\mbox{}_{2}F_{1}\\!\left(\genfrac{}{}{0.0pt}{}{-1-m,N-m-1}{N};z\right)+\\\
+\dfrac{(m+1)}{N}z^{-N}\left(\dfrac{z}{1-z}\right)^{m+1}\,\mbox{}_{2}F_{1}\\!\left(\genfrac{}{}{0.0pt}{}{-m,N-m-1}{N+1};\dfrac{1}{z}\right)$

Because $|z|\leq 1$ we use for the second hypergeometric function the
transformation

$\,\mbox{}_{2}F_{1}\\!\left(\genfrac{}{}{0.0pt}{}{-m,N-m-1}{N+1};\dfrac{1}{z}\right)=\dfrac{\Gamma(N+1)\Gamma(N-1)}{\Gamma(N-m-1)\Gamma(N+m+1)}\left(-\dfrac{1}{z}\right)^{m}\,\mbox{}_{2}F_{1}\\!\left(\genfrac{}{}{0.0pt}{}{-m,-N-m}{2-N};z\right)$

Substitution gives

$H_{m}(z,N)=1-\left(\dfrac{1}{1-z}\right)^{m+1}\,\mbox{}_{2}F_{1}\\!\left(\genfrac{}{}{0.0pt}{}{-1-m,N-m-1}{N};z\right)+\\\
+z^{1-N}\left(\dfrac{1}{1-z}\right)^{m+1}\dfrac{(m+1)\Gamma(N)\Gamma(N-1)}{\Gamma(N-m-1)\Gamma(N+m+1)}(-1)^{m}\,\mbox{}_{2}F_{1}\\!\left(\genfrac{}{}{0.0pt}{}{-m,-N-m}{2-N};z\right)$

Both hypergeometric functions can be written as Jacobi polynomials. There are
a lot of possibilities. We take the following transformations

$\displaystyle\,\mbox{}_{2}F_{1}\\!\left(\genfrac{}{}{0.0pt}{}{-1-m,N-m-1}{N};z\right)=\dfrac{\Gamma(N)\Gamma(m+2)}{\Gamma(N+m+1)}P_{m+1}^{(N-1,-2-2m)}(1-2z)$
$\displaystyle\,\mbox{}_{2}F_{1}\\!\left(\genfrac{}{}{0.0pt}{}{-m,-N-m}{2-N};z\right)=(-1)^{m}\dfrac{\Gamma(N-m-1)\Gamma(m+1)}{\Gamma(N-1)}P_{m}^{(1-N,-2-2m)}(1-2z)$

Substitution gives at last

$H_{m}(z,N)=1-\left(\dfrac{1}{1-z}\right)^{m+1}\dfrac{\Gamma(N)\Gamma(m+2)}{\Gamma(N+m+1)}\\\
\left[P_{m+1}^{(N-1,-2-2m)}(1-2z)-z^{1-N}P_{m}^{(1-N,-2-2m)}(1-2z)\right]$

If we replace $z$ with $e^{j\omega T}$ we get the transfer function of the
UFIR function.

$H_{m}(\omega\,T,N)=1-\left(\dfrac{1}{1-e^{j\omega
T}}\right)^{m+1}\dfrac{\Gamma(N)\Gamma(m+2)}{\Gamma(N+m+1)}\\\
\left[P_{m+1}^{(N-1,-2-2m)}(1-2e^{j\omega T})-e^{j(1-N)\omega
T}P_{m}^{(1-N,-2-2m)}(1-2e^{j\omega T})\right]$

The following figure shows the modulus of the transfer function for the values
of $m=1,\,2,\,3$. See also [1, Fig. 4].

Figure 1: Absolute value of the transfer function for $N=500$ and for
different values for $m$ as a function of $\omega\,T$.

It turns out that for small $\omega\,T$ a problem arises because both Jacobi
polynomials between the square brackets approach about the same value. Then
there is a great loss of decimals for the difference of these terms. The
result is unpredictable. See the left picture in Figure 2.

Figure 2: Absolute value of the transfer functions for $N=500$ and $m=3$. The
horizontal axis begins at $\omega\,T=10^{-4}$. Left picture: 9 decimals are
used. Right picture: 50 decimals are used.

Therefore, the calculation accuracy should be increased. The result is shown
in Figure 2. In the left picture the standard accuracy of 9 decimal places is
used. In the right picture the accuracy has been increased to 20 decimal
places. This means that for signals with a low frequency content ($\omega\,T$
small), a greater number of decimals should be used for the filter to function
properly.

##  4 The orthogonal unbiased FIR filter

In [4] and in his thesis [5], the author describes the theory of the
orthogonal derivative. The theory is developed for both the continuous case
and the discrete case. It is not discussed what happens when the order is set
equal to zero. It will appear that a low-pass filter is then created. Since a
UFIR involving Hahn polynomials has been discussed in the previous sections,
we also use the Hahn polynomials to investigate the properties of the low-pass
filter. See also [11].

For the definition of the orthogonal derivative we use [5, Theorem 2.3.1].

######  Theorem 4.1.

For some $n$ let $p_{n}$ be an orthogonal polynomial of degree $n$ with
respect to the orthogonality measure $\mu$. Let $x\in\mathbb{R}$. Let $I$ be a
closed interval such that, for some $\varepsilon>0,$ $\ x+\delta v\in I$ if
$0\leq\delta\leq\varepsilon$ and $v\in$ supp$(\mu)$. Let $f$ be a continuous
function on $I$ such that its derivatives of order $1,2,\dots,n$ at $x$ exist.
In addition, if $I$ is unbounded, assume that $f$ is of at most polynomial
growth on $I$. Then

$f^{(n)}(x)=\lim\limits_{\delta\downarrow 0}D_{\delta}^{n}[f](x)$

where

$D_{\delta}^{n}[f](x)=\dfrac{k_{n}n!}{h_{n}}\dfrac{1}{\delta^{n}}\int_{\mathbb{R}}f(x+\delta\xi)p_{n}(\xi)d\mu(\xi)$

where the integral converges absolutely.

In the rest of the paper the limit will be omitted. We set $\delta=1$. In that
case the orthogonal derivative becomes an approximate orthogonal derivative.
The theory for the discrete case using the Hahn polynomials is used with $\mu$
has a finite support ${x_{0},x_{1},x_{2},\dots,x_{N}}$ with corresponding
weights $w_{0},w_{1},w_{2},\dots,w_{N}$. Then the definition becomes

$f^{(n)}(x)=\dfrac{k_{n}n!}{h_{n}}\sum_{k=0}^{N-1}f(x+k)Q_{n}(x;\alpha,\beta,N)w(x;\alpha,\beta,N)$

For the Hahn polynomials we use the definition in [8, (9.5.1)]

$Q_{n}(x;\alpha,\beta,N):=\,\mbox{}_{3}F_{2}\\!\left(\genfrac{}{}{0.0pt}{}{-x,-n,n+\alpha+\beta+1}{\alpha+1,-N};1\right)\qquad
n=0,1,2,\dots,N$

Here the hypergeometric series is assumed to be a sum from $k=0$ to $n$, by
which the bottom parameter $-N$ will not cause a singularity. For
$\alpha,\beta>-1$ or $\alpha,\beta<-N$ they are orthogonal on $0,1,2.\dots,N$
with respect to the weights

$w(x;\alpha,\beta,N)=\dfrac{(\alpha+1)_{x}(\beta+1)_{N-x}}{x!(N-x)!}$

and

$\dfrac{k_{n}}{h_{n}}=(-1)^{n}\dfrac{(2n+\alpha+\beta+1)}{(\beta+1)_{n}}\dfrac{(n+\alpha+\beta+1)_{n}}{(n+\alpha+\beta+1)_{N+1}}\dfrac{N!}{n!}$

For all formula in this section we have $x=0,1,\dots,N$. So $x$ is an integer.
Then we have $1/x!=0$ for $x=-1,-2,\dots,-n$ and $1/(N-n-x)!=0$ for
$x=N,N-1,\dots,N-n+1$.

Setting $n=0$ gives

$y(x,N)=\dfrac{\Gamma(N+1)}{(\alpha+2)_{N}}\sum_{m=0}^{N-1}f(x+m)\dfrac{(\alpha+1)_{m}(\beta+1)_{N-m}}{(N-m)!m!}$
(4.1)

We need this equation for the $z$ transform. For simplicity we set $\beta=0$.
The result is

$y(x,N)=\dfrac{\Gamma(N+1)}{(\alpha+2)_{N}}\sum_{m=0}^{N-1}f(x+m)\dfrac{(\alpha+1)_{m}}{m!}$

If $\alpha$ is an integer, the impulse response is a polynomial of order
$\alpha$. This means that the behaviour of this function can be compared with
the function of Shmaliy.

For $\alpha=0$ the filter gives a simple average.

$y(x,N)=\dfrac{1}{N+1}\sum_{m=0}^{N-1}f(x+m)$

For $\alpha=1$ the filter becomes

$y(x,N)=\dfrac{2}{(N+1)(N+2)}\sum_{m=0}^{N-1}(m+1)f(x+m)$

For computing the transfer function we use the $z$-transform of (4.1).

$H(z,N)=\dfrac{\Gamma(N+1)}{(\alpha+2)_{N}}\sum_{m=0}^{N-1}\dfrac{(\alpha+1)_{m}(\beta+1)_{N-m}}{(N-m)!m!}z^{-m}$
(4.2)

The summation is well known.

$H(z,N)=\dfrac{(\beta+1)_{N}}{(\alpha+2)_{N}}\,\mbox{}_{2}F_{1}\\!\left(\genfrac{}{}{0.0pt}{}{-N,\alpha+1}{-\beta-N};\dfrac{1}{z}\right)-\dfrac{(\alpha+1)_{N}}{(\alpha+2)_{N}}z^{-N}$
(4.3)

For simplicity we want $\beta=0$. But for $\beta=0$ this formula is not valid.
Setting $\beta=0$ in (4.2) gives

$H(z,N,\alpha)=\left(\dfrac{z}{z-1}\right)^{\alpha+1}\dfrac{\Gamma(N+1)}{(\alpha+2)_{N}}-\dfrac{\alpha+1}{N+\alpha+1}z^{-N}\left(\dfrac{z}{z-1}\right)^{\alpha+1}\,\mbox{}_{2}F_{1}\\!\left(\genfrac{}{}{0.0pt}{}{-\alpha,N}{N+1};\dfrac{1}{z}\right)$
(4.4)

Using [7, 2.10.(4)] we get for the hypergeometric function

$\,\mbox{}_{2}F_{1}\\!\left(\genfrac{}{}{0.0pt}{}{-\alpha,N}{N+1};\dfrac{1}{z}\right)=\dfrac{\Gamma(N+1)\Gamma(\alpha+1)}{\Gamma(N+\alpha+1)}z^{N}-\\\
-\dfrac{N}{(\alpha+1)}z^{N}(z-1)^{\alpha+1}\,\mbox{}_{2}F_{1}\\!\left(\genfrac{}{}{0.0pt}{}{N+\alpha+1,\alpha+1}{\alpha+2};1-z\right)$

Substitution in (4.4)gives

$H(z,N,\alpha)=\dfrac{N}{N+\alpha+1}z^{\alpha+1}\,\mbox{}_{2}F_{1}\\!\left(\genfrac{}{}{0.0pt}{}{N+\alpha+1,\alpha+1}{\alpha+2};1-z\right)$

Application of a Gauss transformation results in a bounded hypergeoetric
function

$H(z,N,\alpha)=\dfrac{N}{N+\alpha+1}z^{1-N}\,\mbox{}_{2}F_{1}\\!\left(\genfrac{}{}{0.0pt}{}{1-N,1}{\alpha+2};1-z\right)$
(4.5)

The hypergeometric function can also be written as a Jacobi polynomial

$H(z,N,\alpha)=\dfrac{\Gamma(N+1)}{(\alpha+2)_{N}}z^{1-N}P_{N-1}^{(\alpha+1,-\alpha-N)}(2z-1)$

If we replace $z$ with $e^{j\omega\,T}$ we get the transfer function of the
filter.

$H(z,N,\alpha)=\dfrac{N}{N+\alpha+1}e^{j(1-N)\omega\,T}\,\mbox{}_{2}F_{1}\\!\left(\genfrac{}{}{0.0pt}{}{1-N,1}{\alpha+2};1-e^{j\omega\,T}\right)$

Taking the limit for $\omega\rightarrow 0$ and for $\omega\rightarrow 2\pi$ we
get

$\lim_{\omega\rightarrow 0,2\pi}H(\omega,N)=\dfrac{N}{N+\alpha+1}$ (4.6)

For large $N$ this limit goes to $1$. This means that the filter is a LP
filter with parameter $\alpha$. In the Figure 3 we show this transfer function
with $N=200$ and different values for $\alpha$. For high frequencies the
filter behaves like a first order LP filter.

Figure 3: Absolute value of the transfer functions for the orthogonal Hahn
filter with $N=200$ and $\alpha=0$, $\alpha=1$, $\alpha=2$ and $\alpha=4$.

Taking $\alpha=0$, $\alpha=1$ and $\alpha=2$ we get the following
$z$-transform functions from (4.5)

$\displaystyle\alpha=0\qquad
H(z,N,0)=\dfrac{z^{1-N}\big{(}z^{N}-1\big{)}}{(N+1)(z-1)}$
$\displaystyle\alpha=1\qquad
H(z,N,1)=\dfrac{2z^{1-N}\big{(}z^{N+1}-(N+1)z+N)\big{)}}{(N+1)(N+2)(z-1)^{2}}$
$\displaystyle\alpha=2\qquad
H(z,N,2)=\dfrac{3z^{1-N}\big{(}2z^{N+2}-(N+1)(N+2)z^{2}+2N(N+2)z-N(N+1)\big{)}}{(N+1)(N+2)(N+3)(z-1)^{3}}$

The effect of the number $N$ for the transfer function is given in Figure 4.
It is seen that the bandwidth is inversely proportional to the number $N$. The
first peak for all functions lies by $\omega\,T=2\pi$. The absolute values of
the moduli of the transfer function for $\omega\,T=2\pi$ is the same as the
absolute value for $\omega=0$ and is given by (4.6). So for the operation of
this filter it must hold that $\omega\,T<1$ provided that the number of points
$N$ is greater than about $50$.

Figure 4: Absolute value of the transfer functions for the orthogonal Hahn
filter with $\alpha=4$ and $N=50$, $N=100$ and $N=200$.

Now we have to show that the filter is unbiased. When using the criterion
given by [14, (27)]

$\int_{0}^{2\pi}H(e^{j\omega T})d(\omega T)=\int_{0}^{2\pi}|H(e^{j\omega
T})|^{2}d(\omega T)$

both integrals are zero. This can be proved by the substitution of
$z=e^{j\omega\,T}$. Integrating to $z$ gives a result containing only powers
of $z$. Back transformation gives the value of $e^{j\omega\,T}$ for the
boundaries $\omega=0$ and $\omega=2\pi$ being equal. Then the integrals in the
endpoints has the same values. So both integrals are equal to zero.

Acknowledgments

I thank Prof. Y.S. Shmaliy for his comments on the concept of this paper.

Appendices

##  Appendix A Transformations of the bounded ${}_{3}F_{2}$ hypergeometric
functions with unit argument

There are seven standard transformations of the bounded ${}_{3}F_{2}$
hypergeometric functions with unit argument [10, 7.4.4. (81-87)]. They are

$\displaystyle\,\mbox{}_{3}F_{2}\\!\left(\genfrac{}{}{0.0pt}{}{-n,a,b}{c,d};1\right)$
$\displaystyle=\dfrac{(c-a)_{n}(d-a)_{n}}{(c)_{n}(d)_{n}}\,\mbox{}_{3}F_{2}\\!\left(\genfrac{}{}{0.0pt}{}{-n,a,a+b-c-
d-n+1}{a-c-n+1,a-d-n+1};1\right)$ (A.1)
$\displaystyle=\dfrac{(a)_{n}(c+d-a-b)_{n}}{(c)_{n}}(d)_{n}\,\mbox{}_{3}F_{2}\\!\left(\genfrac{}{}{0.0pt}{}{-n,c-a,d-a}{1-a-n,c+d-a-b};1\right)$
(A.2)
$\displaystyle=\dfrac{(c+d-a-b)_{n}}{(c)_{n}}\,\mbox{}_{3}F_{2}\\!\left(\genfrac{}{}{0.0pt}{}{-n,d-a,d-b}{d,c+d-a-b};1\right)$
(A.3)
$\displaystyle=(-1)^{n}\dfrac{(a)_{n}(b)_{n}}{(c)_{n}(d)_{n}}\,\mbox{}_{3}F_{2}\\!\left(\genfrac{}{}{0.0pt}{}{-n,1-c-n,1-d-n}{1-a-n,1-b-n};1\right)$
(A.4)
$\displaystyle=(-1)^{n}\dfrac{(d-a)_{n}(d-b)_{n}}{(c)_{n}(d)_{n}}\,\mbox{}_{3}F_{2}\\!\left(\genfrac{}{}{0.0pt}{}{-n,1-d-n,a+b-c-
d-n}{a-d-n+1,b-d-n+1};1\right)$ (A.5)
$\displaystyle=\dfrac{(c-a)_{n}}{(c)_{n}}\,\mbox{}_{3}F_{2}\\!\left(\genfrac{}{}{0.0pt}{}{-n,a,d-b}{d,a-c-n+1};1\right)$
(A.6)
$\displaystyle=\dfrac{(c-a)_{n}(b)_{n}}{(c)_{n}(d)_{n}}\,\mbox{}_{3}F_{2}\\!\left(\genfrac{}{}{0.0pt}{}{-n,d-b,1-c-n}{1-b-n,a-c-n+1};1\right)$
(A.7)

##  Appendix B Transformations of the Hahn polynomials

Application of the transformations of the ${}_{3}F_{2}$ hypergeometric
functions in Appendix A gives a total of 32 forms of the Hahn polynomials with
a lot of conditions. These are

$\displaystyle Q_{n}(x;\alpha,\beta,N)$
$\displaystyle=Q_{n}(-n-\alpha-\beta-1;\alpha,-x-\alpha-1-n,N)$
$\displaystyle=Q_{n}(x;-N-1,n+\alpha+\beta+1+N-n,-\alpha-1)$
$\displaystyle=Q_{n}(-n-\alpha-\beta-1;-N-1,-x+N-n,-\alpha-1)$
$\displaystyle=\dfrac{(-n-\beta)_{n}(-N-n-\alpha-\beta-1)_{n}}{(\alpha+1)_{n}(-N)_{n}}$
$\displaystyle\qquad\qquad
Q_{n}(x-N-\beta;\beta,\alpha,-N-\alpha-\beta-2)\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad$
$\displaystyle Q_{n}(x;\alpha,\beta,N)$
$\displaystyle=\dfrac{(-n-\beta)_{n}(-N-n-\alpha-\beta-1)_{n}}{(\alpha+1)_{n}(-N)_{n}}$
$\displaystyle\qquad\qquad
Q_{n}(-n-\alpha-\beta-1;\beta,N-x-1-n,-N-\alpha-\beta-2)$
$\displaystyle=\dfrac{(-n-\beta)_{n}(-N-n-\alpha-\beta-1)_{n}}{(\alpha+1)_{n}(-N)_{n}}$
$\displaystyle\qquad\qquad Q_{n}(-N+x-\beta;N+\alpha+\beta+1,-N-1,-\beta-1)$
$\displaystyle=\dfrac{(-n-\beta)_{n}(-N-n-\alpha-\beta-1)_{n}}{(\alpha+1)_{n}(-N)_{n}}$
$\displaystyle\qquad\qquad Q_{n}(-N+x-\beta;N+\alpha+\beta+1,-N-1,-\beta-1)$
$\displaystyle=\dfrac{(-n-\beta)_{n}(-N-n-\alpha-\beta-1)_{n}}{(\alpha+1)_{n}(-N)_{n}}$
$\displaystyle\qquad\qquad
Q_{n}(-n-\alpha-\beta-1;N+\alpha+\beta+1,-n-x-\alpha-2,-\beta-1)$
$\displaystyle=\dfrac{(n+\alpha+\beta+1)_{n}(x-n-N-\beta)_{n}}{(\alpha+1)_{n}(-N)_{n}}$
$\displaystyle\qquad\qquad
Q_{n}(N+n+\alpha+\beta+1;-2n-\alpha-\beta-1,\alpha,N+n-x+\beta)$
$\displaystyle=\dfrac{(n+\alpha+\beta+1)_{n}(x-n-N-\beta)_{n}}{(\alpha+1)_{n}(-N)_{n}}$
$\displaystyle\qquad\qquad Q_{n}(n+\beta;-2n-\alpha-\beta-1,-N-1,N+n-x+\beta)$
$\displaystyle=\dfrac{(n+\alpha+\beta+1)_{n}(x-n-N-\beta)_{n}}{(\alpha+1)_{n}(-N)_{n}}$
$\displaystyle\qquad\qquad
Q_{n}(N+n+\alpha+\beta+1;x-n-N-\beta-1,N-n-x,2n+\alpha+\beta)$
$\displaystyle=\dfrac{(n+\alpha+\beta+1)_{n}(x-n-N-\beta)_{n}}{(\alpha+1)_{n}(-N)_{n}}$
$\displaystyle\qquad\qquad
Q_{n}(n+\beta;x-n-N-\beta-1,-n-x-\alpha-1,2n+\alpha+\beta)$
$\displaystyle=\dfrac{(x-n-N-\beta)_{n}}{(\alpha+1)_{n}}Q_{n}(N-x;-N-1,-2n-\alpha-\beta-1,N+n-x+\beta)$
$\displaystyle=\dfrac{(x-n-N-\beta)_{n}}{(\alpha+1)_{n}}Q_{n}(N+n+\alpha+\beta+1;-N-1,x-n,N+n-x+\beta)$
$\displaystyle=\dfrac{(x-n-N-\beta)_{n}}{(\alpha+1)_{n}}Q_{n}(N-x;-N-n+x-\beta-1,-n-x-\alpha-1,N)$
$\displaystyle=\dfrac{(x-n-N-\beta)_{n}}{(\alpha+1)_{n}}Q_{n}(N+n+\alpha+\beta+1;-N-n+x-\beta-1,\beta,N)$
$\displaystyle=(-1)^{n}\dfrac{(n+\alpha+\beta+1)_{n}(-x)_{n}}{(\alpha+1)_{n}(-N)_{n}}Q_{n}(n-N-1;-2n-\alpha-\beta-1,\beta,n-x-1)$
$\displaystyle=(-1)^{n}\dfrac{(n+\alpha+\beta+1)_{n}(-x)_{n}}{(\alpha+1)_{n}(-N)_{n}}Q_{n}(n+\alpha;-2n-\alpha-\beta-1,N+\alpha+\beta+1,n-x-1)$
$\displaystyle=(-1)^{n}\dfrac{(n+\alpha+\beta+1)_{n}(-x)_{n}}{(\alpha+1)_{n}(-N)_{n}}Q_{n}(-N+n-1;x-n,-n-x-\alpha-1,2n+\alpha+\beta)$
$\displaystyle=(-1)^{n}\dfrac{(n+\alpha+\beta+1)_{n}(-x)_{n}}{(\alpha+1)_{n}(-N)_{n}}Q_{n}(n+\alpha;x-n,N-n-x,2n+\alpha+\beta)$
$\displaystyle Q_{n}(x;\alpha,\beta,N)$
$\displaystyle=(-1)^{n}\dfrac{(-N-n-\alpha-\beta-1)_{n}(x-N)_{n}}{(\alpha+1)_{n}(-N)_{n}}$
$\displaystyle\qquad\qquad
Q_{n}(x-N-\beta;N+\alpha+\beta+1,-2n-\alpha-\beta-1,n-N+x-1)$
$\displaystyle=(-1)^{n}\dfrac{(-N-n-\alpha-\beta-1)_{n}(x-N)_{n}}{(\alpha+1)_{n}(-N)_{n}}$
$\displaystyle\qquad\qquad
Q_{n}(-N+n-1;N+\alpha+\beta+1,-n-x-\alpha-2,n-N+x-1)$
$\displaystyle=(-1)^{n}\dfrac{(-N-n-\alpha-\beta-1)_{n}(x-N)_{n}}{(\alpha+1)_{n}(-N)_{n}}$
$\displaystyle\qquad\qquad Q_{n}(-N+x-\beta;N-n-x,x-n,-N-\alpha-\beta-2)$
$\displaystyle=(-1)^{n}\dfrac{(-N-n-\alpha-\beta-1)_{n}(x-N)_{n}}{(\alpha+1)_{n}(-N)_{n}}$
$\displaystyle\qquad\qquad Q_{n}(-N+n-1;N-n-x,\beta-1,-N-\alpha-\beta-2)$
$\displaystyle=\dfrac{(-n-\beta)_{n}}{(\alpha+1)_{n}}Q_{n}(N-x;-N-1,\alpha+\beta+1+N,-\beta-1)$
$\displaystyle=\dfrac{(-n-\beta)_{n}}{(\alpha+1)_{n}}Q_{n}(-n-\alpha-\beta-1;-N-1,x-n,-\beta-1)$
$\displaystyle=\dfrac{(-n-\beta)_{n}}{(\alpha+1)_{n}}Q_{n}(N-x;\beta,\alpha,N)$
$\displaystyle=\dfrac{(-n-\beta)_{n}}{(\alpha+1)_{n}}Q_{n}(-n-\alpha-\beta-1;\beta,x-n-N-\beta-1,N)$
$\displaystyle=\dfrac{(-n-\beta)_{n}(-x)_{n}}{(\alpha+1)_{n}(-N)_{n}}Q_{n}(n+\alpha;x-n,-N-1,-\beta-1)$
$\displaystyle=\dfrac{(-n-\beta)_{n}(-x)_{n}}{(\alpha+1)_{n}(-N)_{n}}Q_{n}(N-x;x-n,-n-x-\alpha-1,-\beta-1)$
$\displaystyle=\dfrac{(-n-\beta)_{n}(-x)_{n}}{(\alpha+1)_{n}(-N)_{n}}Q_{n}(n+\alpha;\beta,x-n-N-\beta-1,n-x-1)$
$\displaystyle=\dfrac{(-n-\beta)_{n}(-x)_{n}}{(\alpha+1)_{n}(-N)_{n}}Q_{n}(N-x;\beta,-2n-\alpha-\beta-1,n-x-1)\qquad\qquad\qquad\qquad$

## References

  * [1] Castro-Tinttori, P. Ibarra-Manzano, O. Shmaliy Y.S. Implementation of digital unbiased FIR filters with polynomial impulse responses. Circuits Systems Signal processing 31 (2012) 611–626.
  * [2] Diekema, E. The fractional orthogonal derivative. Mathematics 3 (2015), 273–298.
  * [3] Diekema, E. The fractional orthogonal difference with applications. Mathematics 3 (2015), 487–509.
  * [4] Diekema, E. and Koornwinder, T.H. Differentiation by integration using orthogonal polynomials, a survey. J. Approx. Theory 164 (2012), 637–667.
  * [5] Diekema, E. The fractional orthogonal derivative for functions of one and two variables. Thesis, University of Amsterdam (2018). https://pure.uva.nl/ws/files/29401750/Thesis.pdf
  * [6] Diekema, E. A correlation function for the classical orthogonal polynomials. arXiv:2011.07498, 2020.
  * [7] Erdélyi, A. Higher transcendental functions, Vol. I. McGraw-Hill, 1953.
  * [8] Koekoek, R. Lesky, P.A. Swarttouw, R.F. Hypergeometric orthogonal polynomials and their q-analoques. Springer, 2010.
  * [9] Morales-Mendoza, L.J. Gamboa-Rosales, H. Shmaliy, Y.S. A new class of discrete orthogonal polynomials for blind fitting of finite data. Signal Processing 93 (2013) 1785–1793.
  * [10] Prudnikov, A.P. Brychkov, Y.A. Marichev, O.I. Integrals and Series Vol.3. Gordon and Breach Science Publishers 1986.
  * [11] Samadi, S. Nishihara, A. Explicit formula for predictive FIR filters and differentiators using Hahn orthogonal polynomials. IEICE Trans. Fundamentals, Vol.E90-A, 8 (2007) 1511–1518.
  * [12] Shakibaei Asli, B.H. Flusser, J. New discrete orthogonal moments for signal analysis. Signal Processing 141 (2017) 57–73.
  * [13] Shmaliy, Y.S. An unbiased FIR filter for TIE model of a local clock in applications to GPS-based timekeeping. IEEE Trans. Ultrasonics, Ferroelectrics and Frequency Control 53 (5) (2006) 862–870.
  * [14] Shmaliy, Y.S. Neuvo, Y. Khan, S. Review of unbiased FIR filters, smoothers and predictors for polynomial signals. Frontiers in Signal Processing 2 (2018) 1–29.


# Explainability-based Backdoor Attacks
Against Graph Neural Networks

Jing Xu<EMAIL_ADDRESS>Delft University of TechnologyNetherlands ,  Minhui
(Jason) Xue<EMAIL_ADDRESS>The University of AdelaideAustralia and
Stjepan Picek<EMAIL_ADDRESS>Delft University of TechnologyNetherlands

(2021)

###### Abstract.

Backdoor attacks represent a serious threat to neural network models. A
backdoored model will misclassify the trigger-embedded inputs into an
attacker-chosen target label while performing normally on other benign inputs.
There are already numerous works on backdoor attacks on neural networks, but
only a few works consider graph neural networks (GNNs). As such, there is no
intensive research on explaining the impact of trigger injecting position on
the performance of backdoor attacks on GNNs.

To bridge this gap, we conduct an experimental investigation on the
performance of backdoor attacks on GNNs. We apply two powerful GNN
explainability approaches to select the optimal trigger injecting position to
achieve two attacker objectives – high attack success rate and low clean
accuracy drop. Our empirical results on benchmark datasets and state-of-the-
art neural network models demonstrate the proposed method’s effectiveness in
selecting trigger injecting position for backdoor attacks on GNNs. For
instance, on the node classification task, the backdoor attack with trigger
injecting position selected by GraphLIME reaches over $84\%$ attack success
rate with less than $2.5\%$ accuracy drop.

††copyright: none††copyright: acmcopyright††journalyear: 2021††doi:
10.1145/xxxxxxx.xxxxxxx

##  1\. Introduction

Many real-world data can be modeled as graphs, such as social relations or
protein structures. Graph Neural Networks (GNNs) have emerged as state-of-the-
art for machine learning on graphs due to their superior ability to
incorporate information from neighboring nodes in the graph recursively by
capturing both graph structure and node features (Wu2021, ). However, similar
to Convolutional Neural Networks (CNNs), GNNs are also vulnerable to
adversarial attacks, one of which is the backdoor attack. Since GNNs are used
increasingly more for security applications, it is important to study the
backdoor attack on GNNs. Otherwise, there will remain security concerns. For
instance, in a Bitcoin transaction ego network
(DBLP:journals/corr/abs-1908-02591, ), where the nodes are the transactions,
and the edge between two nodes indicates the flow of Bitcoin from one
transaction to another, the attacker can attack the GNNs to classify an
illegal transaction as a legal one.

In the backdoor attacks on GNNs, the trigger injecting position impacts the
attack’s performance in terms of the attack success rate and clean accuracy
drop. Recently, some works are exploiting the vulnerabilities of GNNs to
backdoor attacks with different trigger injecting position selecting
strategies (zhang2020backdoor, ; xi2021graph, ). However, these works either
select trigger injecting position randomly, in which situation the attack may
be easily detected by the defender (zhang2020backdoor, ), or use a
computationally intensive algorithm to get the trigger injecting position, as
shown in (xi2021graph, ). If we know how to quickly select the optimal (or
close to optimal) trigger injecting position in backdoor attacks on GNNs, we
can achieve high attack performance and good evasion of the defender’s
detection mechanisms. Further, we can develop more robust GNN models.
Unfortunately, since graph data have characteristics of complex relationships
and interdependencies between objects, common explainability approaches for
CNNs, such as Shapley value (pmlr-v97-ancona19a, ), are not suitable to
explain the predictions of GNNs to select the optimal trigger injecting
position.

Deep Neural Networks (DNNs) are vulnerable to backdoor attacks
(DBLP:conf/ndss/LiuMALZW018, ; 9186317, ). Specifically, a backdoored neural
network classifier produces attacker-desired behaviors when a trigger is
injected into a testing example. Several studies showed that GNNs are also
vulnerable to backdoor attacks. Zhang et al. proposed a subgraph-based
backdoor attack to GNNs for graph classification task (zhang2020backdoor, ).
Xi et al. presented a subgraph-based backdoor attack to GNNs, but this attack
can be instantiated for both node classification and graph classification
tasks (xi2021graph, ).

Interpretability methods for non-graph neural networks can be grouped into two
main categories. Methods in the first group construct simple proxy models of
the original neural networks by learning a locally faithful approximation
around the prediction (DBLP:conf/kdd/Ribeiro0G16, ). Methods in the second
group identify important aspects of the computation (DBLP:conf/eccv/ZeilerF14,
; DBLP:conf/icml/SundararajanTY17, ). Since these approaches are not suitable
for explaining predictions made by GNNs, recently, some works try to interpret
GNNs. Ying et al. proposed to utilize mutual information to find a subgraph
with associated features for interpreting the predicted label of a node or
graph being explained (DBLP:conf/nips/YingBYZL19, ). Huang et al. presented a
method utilizing predicted labels from both the node being explained and its
neighbors, which enables to capture more local information around the node and
give a finite number of features as explanations in an intuitive way
(DBLP:journals/corr/abs-2001-06216, ).

In this paper, we propose utilizing powerful neural network approaches that
explain predictions made by GNNs to understand the performance of backdoor
attacks on GNNs. Indeed, backdoor attacks on GNNs have been presented
(zhang2020backdoor, ; xi2021graph, ) but how to quickly select the optimal
trigger injecting position and what is the impact of different trigger
injecting position on the attack performance have not been explored. In this
paper, we seek to bridge this gap. To the best of our knowledge, this work
represents the first study on the explainability of triggers for backdoor
attacks on GNNs. Our contributions can be summarized as follows:

  * •

We utilize GNNExplainer, an approach for explaining predictions made by GNNs,
to analyze the impact of trigger injecting position for the backdoor attacks
on GNNs for the graph classification task.

  * •

We propose a new backdoor attack on GNNs for the node classification task,
which uses a subset of node features as a trigger pattern. Additionally, we
explore GraphLIME, a local interpretable model explanation for graphs, to
explore the proposed backdoor attack on the node classification task through
modifying a different subset of node features.

We conduct an empirical study of the explainability of backdoor attack
triggers on GNNs using various state-of-the-art GNNs and four benchmark
datasets.

##  2\. Background

###  2.1. Preliminaries

Graph Neural Networks (GNNs). GNNs take a graph $G$ as an input, including its
structure information and node features, and learn a representation vector
(embedding) for each node $v\in G$, $z_{v}$, or the entire graph, $z_{G}$.
Modern GNNs follow a neighborhood aggregation strategy, where one iteratively
updates the representation of a node by aggregating representations of its
neighbors. After $k$ iterations of aggregation, a node’s representation
captures both structure and feature information within its $k$-hop network
neighborhood. Formally, the $k$-th layer of a GNN is (e.g., GCN (kipf2017semi,
), GraphSAGE (DBLP:conf/nips/HamiltonYL17, ), and GAT (velickovic2018graph,
)):

(1) $Z^{(k)}=AGGREGATE(A,Z^{(k-1)};\theta^{(k)}),$

where $Z^{(k)}$ are the node embeddings in the matrix form computed after the
$k$-th iteration and the $AGGREGATE$ function depends on the adjacency matrix
$A$, the trainable parameters $\theta^{(k)}$, and the previous node embeddings
$Z^{(k-1)}$. $Z^{(0)}$ is initialized as $G$’s node features.

For the node classification task, the node representation $Z^{(k)}$ of the
final iteration is used for prediction. And for the graph classification task,
the READOUT function pools the node embeddings from the final iteration $K$:

(2) $z_{G}=READOUT(Z^{(K)}).$

READOUT can be a simple permutation invariant function such as summation or a
more sophisticated graph-level pooling function (DBLP:conf/nips/YingY0RHL18, ;
DBLP:conf/aaai/ZhangCNC18, ).

Graph-Level classification. Graph-level classification aims to predict the
class label(s) for an entire graph (DBLP:conf/aaai/ZhangCNC18, ). The end-to-
end learning for this task can be realized using graph convolutional layers
and readout layers. While graph convolutional layers are responsible for
extracting high-level node representations, the readout layer collapses node
representations of each graph into a graph representation. By applying a
multilayer perceptron and a Softmax layer to graph representations, one can
build an end-to-end framework for graph classification.

Node-Level classification. Given a single graph with partial nodes being
labeled and others remaining unlabeled, GNNs can learn a robust model that
effectively identifies the class labels for the unlabeled nodes (kipf2017semi,
). In a node-level classification task, there are two types of training
settings - inductive and transductive. In an inductive setting, the unlabeled
nodes are not seen during training, while in a transductive setting, the test
nodes (but not their labels) are also observed during the training process. In
this paper, we focus on the transductive node-level classification task.

Explainability tools for GNNs. GNNExplainer is a model-agnostic approach for
providing explanations on predictions of any GNN-based model. Given a trained
GNN model and its prediction(s), GNNExplainer returns an explanation in the
form of a small subgraph of the input graph together with a small subset of
node features that are most influential for the prediction(s)
(DBLP:conf/nips/YingBYZL19, ). GraphLIME is a local interpretable model
explainability method for graphs. More specifically, to explain a node,
GraphLIME generates a nonlinear interpretable model from its $N$-hop
neighborhood and then computes the most $n$ representative features as the
explanations of its prediction using HSIC Lasso
(DBLP:journals/corr/abs-2001-06216, ).

###  2.2. Threat Model

We assume our threat model similar to the existing backdoor attacks, see,
e.g., (DBLP:conf/ndss/LiuMALZW018, ). Given a pre-trained GNN model
$\Phi_{o}$, the adversary forges a backdoored GNN $\Phi$ by perturbing its
model parameters without modifying the neural network architecture. We assume
the attacker has access to a dataset $D$ sampled from the training dataset.
Specifically, in the graph classification dataset, the attacker can inject a
trigger (graph) to each intended poisoned training graph and change the label
to an attacker-chosen target label. In the node classification dataset, the
attacker can inject a feature trigger (feature vector) to each intended
poisoned training node and relabel the label to the target label.
Consequently, our attack is a gray-box attack that does not modify the GNN’s
model architecture but perturbs the model parameters. This represents a
realistic model occurring in real-world settings. For instance, if the
training dataset is collected from public users, the malicious users under an
attacker’s control can provide trigger-embedded training data. Note that even
without direct access to such data, it is often possible for the attacker to
synthesize data to implement backdoor attacks (DBLP:conf/ndss/LiuMALZW018, ).

##  3\. Explainable Backdoor Attacks

###  3.1. Backdoor Attacks on Graph Classification

Since most graph classification tasks are implemented by utilizing GNNs to
learn the network structure, we focus on subgraph-based backdoor attacks on
the graph classification task. Figure 1 illustrates the pipeline of subgraph-
based backdoor attack on GNNs for the graph classification task. Formally, in
the training phase, the attacker injects a trigger (graph) $g_{t}$ to a subset
of the original training dataset and changes their labels to the attacker-
chosen target label to obtain the backdoored training dataset. A GNN model
trained using the backdoored training dataset is called backdoored GNN $\Phi$.
Then in the testing phase, the adversary injects the same trigger to a given
graph $G$. If we define such trigger-embedded graph as $G_{g_{t}}$, the
adversary’s objective can be defined as:

(3) $\left\\{\begin{matrix}\Phi(G_{g_{t}})=y_{t}\\\
\Phi(G)=\Phi_{o}(G)\end{matrix}\right.$

The first objective in Eq. (3) means that all the trigger-embedded graphs are
required to be misclassified to the target class $y_{t}$, i.e., attack
effectiveness. In contrast, the second objective ensures that the backdoored
GNN performs indistinguishably on normal graphs compared to the original GNN,
i.e., attack evasiveness.

It is challenging to find the optimal trigger injecting position so that the
adversary can reach several goals: 1) high attack success rate, 2) high
accuracy in normal graphs, and 3) difficult to detect by the defender. More
precisely,

  * •

if we sample $t$ nodes from the graph uniformly at random as the trigger nodes
in the trigger graph, the trigger will likely be injected into a subgraph that
is important for the GNN’s final prediction. As a result, the defender can
detect the trigger-embedded graphs easily;

  * •

to achieve the second objective, we can select a subgraph similar to $g_{t}$
in the graph as the trigger injecting position. However, the computation of
the similarity between graphs is a complex task as subgraph isomorphism is
known to be NP-complete. The graph matching algorithms require an exponential
time for computation (DBLP:journals/pami/CordellaFSV04, ).

To overcome the above challenges, we utilize GNNExplainer to optimize the
trigger injecting position to ensure the attack effectiveness and attack
evasiveness at the same time.

  * •

We first apply GNNExplainer to analyze the prediction of GNNs to understand
the impact of each structure in the graph on the classification result from
GNNs.

  * •

Instead of selecting $t$ nodes from the graph uniformly at random as the
trigger nodes, we select the $t$ least important nodes in the graph as the
trigger injecting position, which results in difficult-to-detect trigger-
embedded graphs.

The overall framework of backdoor attack on graph classification task based on
GNNExplainer is shown in Figure 2. Given a pre-trained GNN and its
predictions, through GNNExplainer, the importance value of nodes for each
graph can be computed. Based on the node importance matrix, we select the
optimal trigger injecting position for each intended poisoned graph and then
train the backdoored GNN.

Figure 1. Illustration of subgraph based backdoor attack on GNNs for graph
classification task. Figure 2. The framework of the backdoor attack on graph
classification task based on GNNExplainer.

###  3.2. Backdoor Attacks on Node Classification

The currently proposed backdoor attack on GNNs for the node classification
task defines triggers as specific subgraphs, i.e., given an arbitrary subgraph
$g$ in $G$, by replacing $g$ with the trigger (graph) $g_{t}$, the adversary
attempts to force the unlabeled nodes within $K$ hops to $g$ to be
misclassified into the target label $y_{t}$.

Here, we propose a new method to implement backdoor attacks on GNNs for the
node classification task. We assume that the adversary has access to $G$,
including the graph structure information $A$ and the node feature information
$X$. Each node $v$ in the graph $G$ has its feature vector $x$. Given an
arbitrary node in the graph, by changing the value of a subset of its features
as a feature trigger, the attacker aims to force the node to be classified to
the target class $y_{t}$ and simultaneously perform normally in other
unmodified nodes. Formally, the adversary’s objective can be defined as:

(4) $\left\\{\begin{matrix}\Phi(\emph{v},x_{t};G)=y_{t}\\\
\Phi(\emph{v},x;G)=\Phi_{o}(\emph{v},x;G)\end{matrix}\right.$

Here, $x_{t}$ represents the feature vector with trigger, obtained by changing
the features’ values in specific dimensions.

Similar to the graph classification task, these two objectives ensure the
attack effectiveness and attack evasiveness. The key point is how to select
specific dimensions of a feature vector as a trigger injecting position.
Intuitively, we can select $n$ features from the total features uniformly at
random and change their values to a fixed value as the feature trigger. We can
also use a GNN explainability method - GraphLIME to select the specific
feature dimensions:

  * •

We first apply GraphLIME to analyze the output of GNNs on the node
classification task to compute the $n$ most/least representative features.

  * •

We change the value of the $n$ most/least representative features to a fixed
value as the feature trigger and retrain the GNN to get the backdoored GNN.

The overall framework of the proposed backdoor attack on node classification
task based on GraphLIME is shown in Figure 3.

Figure 3. The framework of backdoor attack on node classification task based
on GraphLIME.

##  4\. Experimental Analysis

We conduct an empirical study of how to utilize the explainability approaches
to implement backdoor attacks on state-of-the-art GNN models and benchmark
datasets.

###  4.1. Experimental Setting

Our experiments were run on an Intel Core i7-8650U CPU processor with $1.90$
GHz frequency and $15.5$ GiB memory. For all the experiments, we use the
PyTorch framework.

Dataset. For the graph classification task, we use two publicly available
real-world graph datasets. (i) Mutagenicity (Morris2020, ) \- molecular
structure graphs of mutagen and nonmutagen; (ii) facebook_ct1 (Morris2020, )
\- a subset of the activity of the New Orleans Facebook community over three
months, used to implement the classification task of distinguishing temporal
graphs with vertex labels corresponding to observations of a dissemination
process and temporal graphs in which the labeling is not a result of a
dissemination process. We also use two real-world datasets for node
classification task: Cora (DBLP:journals/aim/SenNBGGE08, ) and CiteSeer
(DBLP:journals/aim/SenNBGGE08, ). Table 1 shows the statistics of these
datasets.

Table 1. Dataset statistics. Datasets |  # Graphs |  Avg. # nodes |  Avg. # edges |  Classes |  Graphs [Class] |  Target class
---|---|---|---|---|---|---
Mutagenicity |  $4,337$ |  $30.32$ |  $30.77$ |  $2$ |  $2,401[0],1,936[1]$ |  $1$
facebook_ct1 |  $995$ |  $95.72$ |  $269.01$ |  $2$ |  $498[0],497[1]$ |  $0$
Cora |  $1$ |  $2,708$ |  $5,429$ |  $7$ |  $351[0],217[1],418[2],818[3],$ |  $6$
|  |  |  |  |  $426[4],298[5],180[6]$ |
CiteSeer |  $1$ |  $3,327$ |  $4,608$ |  $6$ |  $264[0],590[1],668[2],$ |  $5$
|  |  |  |  |  $701[3],596[4],508[5]$ |

Dataset splits and parameter setting. For each graph classification dataset,
we sample 2/3 of the graphs as the original training dataset and treat the
remaining graphs as the original testing dataset. Among the original training
dataset, we randomly sample $\eta$ fraction of graphs to inject the trigger
and relabel them with the target label, called the backdoored training
dataset. We also inject our trigger to each original testing graph whose label
is not the target label to generate the backdoored testing dataset, which is
used to evaluate the attack effectiveness. There are several parameters in the
attack’s implementation: trigger size $s$, trigger density $\rho$, and
poisoning intensity $\eta$. We set the trigger size $s$ to be the $\gamma$
fraction of the graph dataset’s average number of nodes. Since the trigger
size affects the attack effectiveness dramatically, we explore the impact of
trigger size on the attack results. At the same time, we set other parameters
as: $\rho=0.8$ and $\eta=5\%$ following the parameter setting in
(zhang2020backdoor, ). We use Erdős-Rényi (ER) model (Gilbert1959, ) to
generate the trigger with graph density $\rho=0.8$.

In the node classification task, we split $20\%$ of the total nodes as the
original training dataset (labeled) for each dataset. To generate the
backdoored training dataset, we sample $15\%$ of the original training dataset
to inject the feature trigger and relabel these nodes with the target label.
The trigger size is set to $10\%$ of the total number of node feature
dimensions. We set these parameters as they provided the best results after
conducting a tuning phase. In the node classification task, each node feature
has a value of 0 or 1, and here we set the value of the modified node features
to 1 (note, the values could also be set to 0).

Models. In our experiment, we use the popular GIN (DBLP:conf/iclr/XuHLJ19, )
and GraphSAGE (DBLP:conf/nips/HamiltonYL17, ) models for the graph
classification task as these two methods are the state-of-the-art GNN models.
For node classification, we use GAT (velickovic2018graph, ) model as the pre-
trained GNN model.

Attack evaluation metrics. We use the attack success rate (ASR) to evaluate
the attack effectiveness. Specifically, in the graph classification task, the
ASR measures the proportion of trigger-embedded inputs (the original label is
not the target label) that are misclassified by the backdoored GNN into the
target class $y_{t}$ chosen by the adversary. The trigger-embedded inputs are

$D_{g_{t}}=\left\\{(G_{g_{t1}},y_{1}),(G_{g_{t2}},y_{2}),\ldots,(G_{g_{tn}},y_{n})\right\\}$

and

$D_{v_{t}}=\left\\{(v_{x_{t1}},y_{1}),(v_{x_{t2}},y_{2}),\ldots,(v_{x_{tn}},y_{n})\right\\}$

for graph classification and node classification task, respectively. Formally,
the ASR can be defined as:

$\displaystyle Attack\>Success\>Rate$
$\displaystyle=\frac{\sum_{i=1}^{n}\mathbb{I}(\Phi(G_{g_{ti}})=y_{t})}{n}$
$\displaystyle or=\frac{\sum_{i=1}^{n}\mathbb{I}(\Phi(v_{x_{ti}})=y_{t})}{n},$

where $\mathbb{I}$ is an indicator function.

To evaluate the attack evasiveness, we use clean testing dataset accuracy drop
(CAD), which is the classification accuracy difference of the original GNN
$\Phi_{o}$ and the backdoored GNN $\Phi$ over the clean testing dataset.

###  4.2. Results for Graph Classification

This set of experiments evaluate the backdoor attack on GNNs for the graph
classification task with the explainability results obtained from
GNNExplainer. Based on the node importance matrix from GNNExplainer, we
conduct three attacks with different trigger nodes selecting strategies, two
among which are proposed here as new strategies: 1) Random selecting attack
(RSA) \- As in (zhang2020backdoor, ), in this strategy, we sample $t$ nodes
from the graph uniformly at random and replace their connection with that in
the trigger graph. 2) Most important nodes selecting attack (MIA) \- We choose
the $t$ most important nodes based on the node importance matrix and replace
their connection as that of the trigger graph. 3) Least important nodes
selecting attack (LIA) \- Instead of selecting the most important $t$ nodes,
we select the least important nodes as the trigger nodes.

Table 2 presents the experimental results of the backdoor attack on the graph
classification task based on three attacks. For each result in the table, the
first value is ASR, and the second value is CAD. The results are conducted for
the trigger size $\gamma=0.2$. Finally, we include the performance of two
different GNN models - GIN and GraphSAGE. We can observe that overall, all
three backdoor attacks on GIN achieve high attack effectiveness (each with an
attack success rate over $93\%$) and low clean accuracy drop (each with
accuracy drop below $4\%$), while performances in GraphSAGE degrade with
attack success rate up to $82\%$. This may be explained by GIN having a more
powerful graph representation capability so the trigger graph can be learned
better. The rank between these three attacks, except for the result of the
facebook_ct1 dataset on GraphSAGE, is $LIA\approx RSA>MIA$ in terms of attack
effectiveness. The ASR of MIA is lower than the other two attacks probably
because after replacing the most important subgraph with the trigger graph, it
is more difficult for the GNN to distinguish the graphs of the target class
and non-target class. More precisely, GNN needs to dedicate more network
capacity to learn specific patterns for each class sample, which negatively
influences recognizing the trigger patterns. The result that ASR of RSA and
LIA is close means the attacker can inject the trigger to the least important
structure of the graph to achieve its goal of being less likely to be detected
by the defender.

We also evaluate the impact of trigger size - $\gamma$ fraction of the average
number of nodes on the backdoor attack’s performance. Figure 4 shows the
attack performance under different trigger sizes varying from $5\%$ to $20\%$.
Obviously, the attack effectiveness of all attacks monotonically increases
with the trigger size. This can be easily explained as with larger triggers,
backdoored GNNs can better learn the difference between trigger-embedded and
normal graphs. Additionally, the clean accuracy drop of all strategies
slightly increases as well when the trigger size grows. This may be explained
as the trigger size increases, more graph structure information has been
modified, and the border between samples from different classes becomes less
distinctive, so the performance of the backdoored GNNs on clean dataset drops.

This set of experiments takes on average $13.49$min and $16.72$min to
implement backdoor attacks on the GIN model on Mutagenicity and facebook_ct1
dataset, respectively. The GraphSAGE model takes around $13.37$min and
$16.35$min on Mutagenicity and facebook_ct1 dataset, respectively. Clearly,
the process of selecting the optimal trigger injecting position takes a short
time on both GNN models on two datasets, e.g., $0.65$s per graph on the GIN
model on the Mutagenicity dataset. Consequently, utilizing the GNNExplainer
method to select the optimal trigger injecting position for a backdoor attack
on GNNs for graph classification task is practical and feasible. What is more,
we can select the least important structure of the graph to evade the
detection from a defender.

Figure 4. Impact of trigger size $\gamma$ on the attack success rate (ASR) and clean accuracy drop (CAD) of backdoor attack on the graph classification task. Table 2. Backdoor attack results on graph classification task based on different trigger nodes selecting strategies. ASR(%) — CAD(%) | GIN | GraphSAGE
---|---|---
|  RSA |  MIA |  LIA |  RSA |  MIA |  LIA
Mutagenicity |  $98.24\;\ 2.80$ |  $93.66\;\ 1.66$ |  $97.69\;\ 2.65$ |  $79.73\;\ 1.03$ |  $73.55\;\ 0.58$ |  $82.24\;\ 0.65$
facebook ct1 |  $100\;\ 3.93$ |  $95.35\;\ 3.32$ |  $100\;\ 0.52$ |  $64.23\;\ 2.27$ |  $67.22\;\ 2.64$ |  $69.57\;\ 2.85$

###  4.3. Results for Node Classification

Next, we evaluate the backdoor attack on GNNs for the node classification task
under the explainability results of GraphLIME. Based on the feature importance
results of GraphLIME, we propose three attacks with different trigger feature
dimension selecting strategies: 1) Random selecting attack (RSA) \- select $n$
features from the node feature vector uniformly at random. 2) Most important
features selecting attack (MIA) \- select the most $n$ representative features
and change their values. 3) Least important features selecting attack (LIA) \-
select the least $n$ representative features and change their values.

Table 3 summarizes the attack performance under different trigger feature
dimension selecting strategies (the first value is the ASR, and the second
value is the CAD). Observe that these three backdoor attacks on GAT obtain
high attack success rate, i.e., over $84\%$ and $95\%$ for Cora and CiteSeer,
respectively, and low clean accuracy drop at the same time. This is similar to
the graph classification task results: the ASR of LIA is close to RSA, while
MIA has slightly degraded performance compared to the other two attacks.
Therefore, the attacker can select the least representative features of a node
to inject the feature trigger to achieve a high attack success rate, and the
trigger-embedded node has a lower probability of being detected by the
defender.

Table 3. Backdoor attack results on node classification task based on different trigger features selecting strategies. ASR(%) — CAD(%) | GAT
---|---
|  RSA |  MIA |  LIA
Cora |  $86.01\;\ 2.23$ |  $84.11\;\ 0.66$ |  $84.22\;\ 1.95$
CiteSeer |  $96.35\;\ 1.72$ |  $95.28\;\ 1.39$ |  $96.26\;\ 1.72$

The running time for backdoor attack implementation on the GAT model on two-
node classification datasets is on average $27.30$s and $59.02$s,
respectively. In the process of selecting the optimal trigger injecting
position, it only takes $0.06$s and $0.09$s per node for Cora and CiteSeer
dataset, respectively. Similar to the conclusion of graph classification
experiments, it is feasible to apply the explainability approach - GraphLIME
to select trigger injecting position for a backdoor attack on the node
classification task. We emphasize that we do not compare our attack results
with the state-of-the-art (zhang2020backdoor, ; xi2021graph, ) because the
implementation code for those works is not publicly available.

##  5\. Conclusion and Future Work

This work represents a first step toward the explainability of the impact of
trigger injecting position on the performance of backdoor attacks on GNNs. We
conduct research on two graph tasks - graph classification and node
classification. For the graph classification task, we apply GNNExplainer to
select the optimal subgraph in a graph to be replaced by the trigger graph.
For the node classification task, we propose a new backdoor attack using a
subset of node features as a trigger pattern, and then we apply GraphLIME to
choose the optimal subset of node features to change their values to a fixed
value as the feature trigger. Through empirical evaluation using benchmark
datasets and state-of-the-art models, we verify that our approach can quickly
select the optimal trigger injecting position to implement a powerful backdoor
attack on GNNs. Furthermore, we see that the attacker can select the least
important parts of the graph to inject the trigger, thus reducing the chances
of easy detection by the defender. Interesting future work includes: 1)
exploring defenses against the backdoor attacks by using the explainability
approach, and 2) designing “clean label” backdoor poisoning attacks against
GNNs where the attacker does not control the sample labeling process.

## References

  * [1] M. Ancona, C. Oztireli, and M. Gross.  Explaining deep neural networks with a polynomial time algorithm for shapley value approximation.  In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 272–281. PMLR, 09–15 Jun 2019\.
  * [2] L. P. Cordella, P. Foggia, C. Sansone, and M. Vento.  A (sub)graph isomorphism algorithm for matching large graphs.  IEEE Trans. Pattern Anal. Mach. Intell., 26(10):1367–1372, 2004\.
  * [3] E. N. Gilbert.  Random graphs.  The Annals of Mathematical Statistics, 30(4):1141–1144, Dec. 1959\.
  * [4] W. L. Hamilton, Z. Ying, and J. Leskovec.  Inductive representation learning on large graphs.  In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 1024–1034, 2017.
  * [5] Q. Huang, M. Yamada, Y. Tian, D. Singh, D. Yin, and Y. Chang.  Graphlime: Local interpretable model explanations for graph neural networks.  CoRR, abs/2001.06216, 2020.
  * [6] T. N. Kipf and M. Welling.  Semi-supervised classification with graph convolutional networks.  In International Conference on Learning Representations (ICLR), 2017\.
  * [7] S. Li, M. Xue, B. Zhao, H. Zhu, and X. Zhang.  Invisible backdoor attacks on deep neural networks via steganography and regularization.  IEEE Transactions on Dependable and Secure Computing, pages 1–1, 2020.
  * [8] Y. Liu, S. Ma, Y. Aafer, W. Lee, J. Zhai, W. Wang, and X. Zhang.  Trojaning attack on neural networks.  In 25th Annual Network and Distributed System Security Symposium, NDSS 2018, San Diego, California, USA, February 18-21, 2018. The Internet Society, 2018.
  * [9] C. Morris, N. M. Kriege, F. Bause, K. Kersting, P. Mutzel, and M. Neumann.  Tudataset: A collection of benchmark datasets for learning with graphs.  In ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020.
  * [10] M. T. Ribeiro, S. Singh, and C. Guestrin.  ”why should I trust you?”: Explaining the predictions of any classifier.  In B. Krishnapuram, M. Shah, A. J. Smola, C. C. Aggarwal, D. Shen, and R. Rastogi, editors, Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016, pages 1135–1144. ACM, 2016.
  * [11] P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Gallagher, and T. Eliassi-Rad.  Collective classification in network data.  AI Mag., 29(3):93–106, 2008.
  * [12] M. Sundararajan, A. Taly, and Q. Yan.  Axiomatic attribution for deep networks.  In D. Precup and Y. W. Teh, editors, Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 3319–3328. PMLR, 2017.
  * [13] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio.  Graph Attention Networks.  International Conference on Learning Representations, 2018.  accepted as poster.
  * [14] M. Weber, G. Domeniconi, J. Chen, D. K. I. Weidele, C. Bellei, T. Robinson, and C. E. Leiserson.  Anti-money laundering in bitcoin: Experimenting with graph convolutional networks for financial forensics.  CoRR, abs/1908.02591, 2019.
  * [15] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu.  A comprehensive survey on graph neural networks.  IEEE Transactions on Neural Networks and Learning Systems, 32(1):4–24, Jan. 2021.
  * [16] Z. Xi, R. Pang, S. Ji, and T. Wang.  Graph backdoor, 2021.
  * [17] K. Xu, W. Hu, J. Leskovec, and S. Jegelka.  How powerful are graph neural networks?  In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
  * [18] Z. Ying, D. Bourgeois, J. You, M. Zitnik, and J. Leskovec.  Gnnexplainer: Generating explanations for graph neural networks.  In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 9240–9251, 2019.
  * [19] Z. Ying, J. You, C. Morris, X. Ren, W. L. Hamilton, and J. Leskovec.  Hierarchical graph representation learning with differentiable pooling.  In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 4805–4815, 2018.
  * [20] M. D. Zeiler and R. Fergus.  Visualizing and understanding convolutional networks.  In D. J. Fleet, T. Pajdla, B. Schiele, and T. Tuytelaars, editors, Computer Vision - ECCV 2014 - 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part I, volume 8689 of Lecture Notes in Computer Science, pages 818–833. Springer, 2014.
  * [21] M. Zhang, Z. Cui, M. Neumann, and Y. Chen.  An end-to-end deep learning architecture for graph classification.  In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pages 4438–4445. AAAI Press, 2018.
  * [22] Z. Zhang, J. Jia, B. Wang, and N. Z. Gong.  Backdoor attacks to graph neural networks, 2020.


mode = titleDenResCov-19: A deep transfer learning network for classification
of CXRs

[orcid=0000-0002-4276-4119] [1] url]https://www.sheffield.ac.uk/dcs,
https://insigneo.org/

[orcid=0000-0001-5881-2341]

[orcid=0000-0001-8198-5128] URL]http://users.ox.ac.uk/ card0439/ [1]

[cor1]Corresponding author

# DenResCov-19: A deep transfer learning network for robust automatic
classification of COVID-19, pneumonia, and tuberculosis from X-rays

Michail Mamalakis<EMAIL_ADDRESS>Department of Computer Science,
University of Sheffield, Sheffield, UK  Insigneo Institute for in-silico
Medicine, Sheffield, UK  Andrew J. Swift  Bart Vorselaars  Surajit Ray
Simonne Weeks  Weiping Ding  Richard H. Clayton  Louise S. Mackenzie  Abhirup
Banerjee<EMAIL_ADDRESS>Division of Cardiovascular
Medicine, Radcliffe Department of Medicine, University of Oxford, Oxford OX3
9DU, UK  Institute of Biomedical Engineering, Department of Engineering
Science, University of Oxford, Oxford OX3 7DQ, UK  Department of Infection,
Immunity & Cardiovascular Disease, University of Sheffield, Sheffield, UK
School of Mathematics and Physics, University of Lincoln, Brayford Pool,
Lincoln LN6 7TS, UK  School of Mathematics and Statistics, University of
Glasgow, Glasgow G12 8QW, UK  School of Pharmacy and Biomedical Sciences,
University of Brighton, Brighton BN2 4GJ, UK  School of Information Science
and Technology, Nantong University, Nantong 226019, China

###### keywords:

COVID-19 Pneumonia Chest X-Rays Deep Transfer Learning Network Automatic
Classification