# Functionals with extrema at reproducing kernels

Aleksei Kulikov  Department of Mathematical Sciences, Norwegian University of
Science and Technology, NO-7491 Trondheim, Norway
<EMAIL_ADDRESS>
###### Abstract.

We show that certain monotone functionals on the Hardy spaces and convex
functionals on the Bergman spaces are maximized at the normalized reproducing
kernels among the functions of norm $1$, thus proving the contractivity
conjecture of Pavlović and of Brevig, Ortega-Cerdà, Seip and Zhao and the
Wehrl-type entropy conjecture for the $SU(1,1)$ group of Lieb and Solovej,
respectively.

This work was supported by Grant 275113 of the Research Council of Norway

##  1\. Introduction

In this paper we will be working with several analytic function spaces in the
unit disk $\mathbb{D}=\\{z\in\mathbb{C}:|z|<1\\}$. We begin by defining the
appropriate Hardy and Bergman spaces.

######  Definition 1.

For $0<p<\infty$ we say that a function $f$ analytic in $\mathbb{D}$ belongs
to the Hardy space $H^{p}$ if

$||f||_{H^{p}}^{p}=\sup_{0<r<1}\frac{1}{2\pi}\int\limits_{0}^{2\pi}|f(re^{i\theta})|^{p}d\theta<\infty.$

To define the Bergman space we first introduce the Möbius invariant hyperbolic
measure on the unit disk, which corresponds to the metric of constant negative
curvature $-4\pi$. For $z=x+iy\in\mathbb{D}$ we define it as

$dm(z)=\frac{1}{(1-|z|^{2})^{2}}\frac{dxdy}{\pi}.$

We will also sometimes denote hyperbolic measure of the set $A$ by
$|A|_{H}=m(A)$.

######  Definition 2.

For $0<p<\infty$ and $\alpha>1$ we say that a function $f$ analytic in
$\mathbb{D}$ belongs to the Bergman space $A^{p}_{\alpha}$ if

$||f||_{A^{p}_{\alpha}}^{p}=\int\limits_{\mathbb{D}}(\alpha-1)|f(z)|^{p}(1-|z|^{2})^{\alpha}dm(z)<\infty.$

Note that for the function $f(z)\equiv 1$ we have
$||f||_{H^{p}}=||f||_{A^{q}_{\alpha}}=1$ for all admissible values of $p,q$
and $\alpha$.

An important property of these spaces is that point evaluations are continuous
in them. Specifically, for all analytic functions $f$ we have

(1.1) $|f(z)|^{p}(1-|z|^{2})^{\alpha}\leq||f||_{A^{p}_{\alpha}}^{p}$

and

(1.2) $|f(z)|^{r}(1-|z|^{2})\leq||f||_{H^{r}}^{r}.$

Moreover, since polynomials are dense in all of these spaces, for each fixed
function $f$ the quantities on the left-hand sides of (1.1) and (1.2) tend
uniformly to $0$ as $|z|\to 1$.

One of the first questions about such spaces that one could ask is when one of
them is contained in another one. It turns out that the most interesting case
to consider is when $\frac{p}{\alpha}$ is held constant, in which case we have

$A^{p}_{\alpha}\subset
A^{q}_{\beta},\quad\frac{p}{\alpha}=\frac{q}{\beta}=r,\quad p<q$

and $H^{r}$ is contained in all these spaces. Moreover, the $H^{r}$ norm can
be evaluated as the limit of these Bergman norms in the sense that for $f\in
H^{r}$ we have

$||f||_{H^{r}}=\lim_{\alpha\to 1}||f||_{A^{r\alpha}_{\alpha}}.$

Thus it is sometimes reasonable to denote $H^{r}$ by $A^{r}_{1}$.

Recently, however, it was asked whether these embeddings are actually
contractions, that is whether the norm $||f||_{A^{r\alpha}_{\alpha}}$ is
decreasing in $\alpha$. In the case of Bergman spaces this question was asked
by Lieb and Solovej [9]. They showed that such contractivity implies their
Wehrl-type entropy conjecture for the $SU(1,1)$ group. In the case of
contractions from the Hardy space to the Bergman spaces it was asked by
Pavlović in [13] and by Brevig, Ortega-Cerdà, Seip and Zhao [3] in relation to
coefficient estimates for analytic functions. In this paper we confirm these
conjectures and moreover we prove more general results where we replace the
function $t^{r}$ with a general convex or monotone function, respectively.

######  Theorem 1.1.

Let $G:[0,\infty)\to\mathbb{R}$ be an increasing function. Then the maximum
value of

(1.3) $\int\limits_{\mathbb{D}}G(|f(z)|^{p}(1-|z|^{2}))dm(z)$

is attained for $f(z)\equiv 1$, subject to the condition that $f\in H^{p}$ and
$||f||_{H^{p}}=1$.

######  Theorem 1.2.

Let $G:[0,\infty)\to\mathbb{R}$ be a convex function. Then the maximum value
of

(1.4) $\int\limits_{\mathbb{D}}G(|f(z)|^{p}(1-|z|^{2})^{\alpha})dm(z)$

is attained for $f(z)\equiv 1$, subject to the condition that $f\in
A^{p}_{\alpha}$ and $||f||_{A^{p}_{\alpha}}=1$.

Applying these theorems to the convex and increasing function $G(t)=t^{s},s>1$
we get that all the embeddings above between Hardy and Bergman spaces are
contractions, that is we get the following corollary

######  Corollary 1.3.

For all $0<p<q<\infty$ and $1<\alpha<\beta<\infty$ with
$\frac{p}{\alpha}=\frac{q}{\beta}=r$ for all functions $f$ analytic in
$\mathbb{D}$ we have

$||f||_{A^{q}_{\beta}}\leq||f||_{A^{p}_{\alpha}}\leq||f||_{H^{r}}$

with equality for $f(z)\equiv c$ for $c\in\mathbb{C}$.

In fact, we are able to prove more general results than Theorems 1.1 and 1.2.
Specifically, in the case of Hardy spaces we are able to prove a sharp bound
for the hyperbolic measure of the superlevel sets of the function
$|f(z)|^{p}(1-|z|^{2})$, thus verifying also Conjecture $2$ from [3], while in
the case of Bergman spaces our proof allows us to consider some not
necessarily convex functions, see Theorem 3.1 and Remark 4.2 respectively.

It is important to mention that the Möbius group acts not only on the measure
$m$ but on the spaces $A^{p}_{\alpha}$ as well. Specifically, given a function
$f\in A^{p}_{\alpha}$ and $w\in\mathbb{D}$, the function

$g(z)=f\left(\frac{z-\bar{w}}{1-zw}\right)\frac{(1-|w|^{2})^{\alpha/p}}{(1-zw)^{2\alpha/p}}$

also belongs to the space $A^{p}_{\alpha}$ and moreover it has the same norm
as $f$ and the same distribution of the function
$|f(z)|^{p}(1-|z|^{2})^{\alpha}$ with respect to the measure $m$. In
particular, when $f(z)\equiv 1$ in this way we get
$g(z)=\frac{(1-|w|^{2})^{\alpha/p}}{(1-zw)^{2\alpha/p}}$ and these functions
also necessarily give us the maximal value in (1.3) and (1.4). Note that when
$p=2$, the spaces $A^{p}_{\alpha}$ are Hilbert spaces and these functions turn
out to be (normalized) reproducing kernels at the point $\bar{w}$. By analogy,
we will call them reproducing kernels even if $p\neq 2$ (they are in fact
reproducing kernels for the dual space).

Lastly, let us also mention that all our results also hold true for the Hardy
and Bergman spaces in the upper half-plane, either by using a conformal
mapping from the unit disk or by directly translating our methods. We chose to
work in the unit disk, however, since it allows us to simplify some
calculations in the proof.

The structure of the paper is as follows. In Section 2 we prove a general
monotonicity theorem for the hyperbolic measure of the superlevel sets of
analytic functions, which is an adaptation of the ingenious method from [11]
to the hyperbolic setting. This will also be the only Section where we use
analyticity and hyperbolic geometry in an essential way. Then, in Sections 3
and 4 we deduce from it Theorems 1.1 and 1.2, respectively. Finally, in
Section 5 we briefly discuss an application of Theorem 1.1 to coefficient
estimates for analytic functions.

##  2\. monotonicity for the superlevel sets

Let $f$ be a function analytic in $\mathbb{D}$ such that
$u(z)=|f(z)|^{a}(1-|z|^{2})^{b}$ is bounded and goes to $0$ uniformly as
$|z|\to 1$. Then the superlevel sets $A_{t}=\\{z:u(z)>t\\}$ for $t>0$ are
compactly embedded into $\mathbb{D}$ and thus have finite hyperbolic measure
$\mu(t)=m(A_{t})$. The goal of this section is to prove the following theorem
which says that a certain quantity related to this measure is decreasing.

######  Theorem 2.1.

Let $f:\mathbb{D}\to\mathbb{C}$ be an analytic function such that the function
$u(z)=|f(z)|^{a}(1-|z|^{2})^{b}$ is bounded and $u(z)$ tends to $0$ uniformly
as $|z|\to 1$. Then the function $g(t)=t^{1/b}(\mu(t)+1)$ is decreasing on the
interval $(0,t_{0})$, where $t_{0}=\max_{z\in\mathbb{D}}u(z)$.

The reason we consider this specific function $g$ is that for $f(z)\equiv 1$
the function $g$ turns out to be constant.

The proof of this theorem is mostly based on the methods developed in [11],
translated from the euclidean to the hyperbolic setting. To this end, we
introduce the hyperbolic length, associated with the measure $m$.

######  Definition 3.

For a curve $\gamma\subset\mathbb{D}$ we define its hyperbolic length
$|\gamma|_{h}$ as

$|\gamma|_{h}=\int\limits_{\gamma}\frac{|dz|}{(1-|z|^{2})\sqrt{\pi}}.$

###### Proof of Theorem 2.1.

We start from the formula

(2.1) $-\mu^{\prime}(t)=\int_{u=t}|\nabla
u|^{-1}\frac{|dz|}{\pi(1-|z|^{2})^{2}}$

along with the claim that $\\{u=t\\}=\partial A_{t}$ and that this set is a
smooth curve for almost all $t\in(0,t_{0})$. These assertions are by no means
trivial, but the proof almost literally follows the proof of Lemma $3.2$ from
[11] and the discussion before it so we present here only the informal
geometric reasoning for formula (2.1). Since for $z\in\partial A_{t}$ we have
$u(z)=t$, $\nabla u$ is orthogonal to $\partial A_{t}$ and moreover it is
pointing into $A_{t}$ since for $z\in A_{t}$ we have $u(z)>t$. Thus, when we
decrease $t$ by a small number $\varepsilon$ at each point of $\partial A_{t}$
the set $A_{t-\varepsilon}$ is expanded in the direction orthogonal to
$\partial A_{t}$ by the value about $\frac{\varepsilon}{|\nabla u|}$. The
factor $\frac{1}{\pi(1-|z|^{2})^{2}}$ appears in (2.1) because we want to
differentiate the hyperbolic measure of $A_{t}$ and not the euclidean one.

Following the approach from [11], our next step is to apply the Cauchy–Schwarz
inequality to the hyperbolic length of $\partial A_{t}$:

(2.2) $|\partial A_{t}|_{h}^{2}=\left(\int_{\partial
A_{t}}\frac{|dz|}{\sqrt{\pi}(1-|z|^{2})}\right)^{2}\leq\left(\int_{\partial
A_{t}}|\nabla
u|^{-1}\frac{|dz|}{\pi(1-|z|^{2})^{2}}\right)\left(\int_{\partial
A_{t}}|\nabla u||dz|\right).$

The first integral on the right-hand side is $-\mu^{\prime}(t)$ so to proceed
we have to analyze the second one.

Let $\nu$ be the outward normal to $\partial A_{t}$. As explained above,
$\nabla u$ is parallel to it but directed in the opposite direction. Thus we
have $|\nabla u|=-\nabla u\cdot\nu$. Also, we note that since for
$z\in\partial A_{t}$ we have $u(z)=t$, we have for $z\in\partial A_{t}$

$\frac{|\nabla u|}{t}=\frac{|\nabla u|}{u}=-\frac{\nabla
u\cdot\nu}{u}=-(\nabla\log u)\cdot\nu.$

Now the second integral on the right-hand side of (2.2) can be evaluated by
Green’s theorem:

(2.3) $\int_{\partial A_{t}}|\nabla u||dz|=-t\int_{\partial A_{t}}(\nabla\log
u)\cdot\nu=-t\int_{A_{t}}\Delta\log u(z)dxdy.$

Note that here it is important that $u(z)\neq 0$ for $z\in A_{t}$ so the
function $\log u$ is well-defined on $A_{t}$ and $\partial A_{t}$. We have
$\Delta\log u(z)=a\Delta\log|f(z)|+b\Delta\log(1-|z|^{2})$. Since $f(z)\neq 0$
for $z\in A_{t}$, the first term is just $0$ while the second one is
$-4b\frac{1}{(1-|z|^{2})^{2}}$ which is proportional to the hyperbolic metric
$m$. Thus, the right-hand side of (2.3) is equal to $4\pi bt|A_{t}|_{H}$.

Combining everything, we get

$-\mu^{\prime}(t)\geq\frac{|\partial A_{t}|_{h}^{2}}{4bt|A_{t}|_{H}}.$

Our next step is to use the isoperimetric inequality for the hyperbolic plane
[14] (see also [7, 12]). In the case of curvature $-4\pi$ it says that for any
set $A$ we have

$|\partial A|_{h}^{2}\geq 4\pi|A|_{H}+4\pi|A|_{H}^{2}.$

Using it with $A=A_{t}$ and recalling that $|A|_{H}=\mu(t)$ we get

(2.4) $-\mu^{\prime}(t)\geq\frac{1+\mu(t)}{bt}.$

Note that here we used that $|A|_{H}>0$ (that is, $t<t_{0}$) to avoid division
by $0$.

Rewriting (2.4) for $g(t)=t^{1/b}(\mu(t)+1)$ we get
$g^{\prime}(t)=t^{1/b}(\frac{\mu(t)+1}{bt}+\mu^{\prime}(t))\leq 0$, thus $g$
is decreasing as required. ∎

We believe that the key reason why the above argument works is the
proportionality ${\Delta\log||K_{z}||\sim m(z)}$, where $K_{z}$ are the
reproducing kernels for our spaces. Note that the same kind of
proportionality, in the Euclidean setting, played a crucial role in [11].

Note that for the function $f(z)\equiv 1$ everywhere in the proof above we
have equalities for all values of $a$ and $b$. Indeed, in the Cauchy–Schwarz
inequality the functions are constant by radial symmetry, thus it is an
equality, and the hyperbolic isoperimetric inequality is an equality exactly
when the set is a hyperbolic disk. In fact, it is also an equality for all
reproducing kernels, but verifying this for the Cauchy–Schwarz part is a
rather long computation. This is also true in the upper half-plane. The reason
we chose to work in the unit disk is that for $f(z)\equiv 1$ these equalities
are easy to verify.

##  3\. Weak-type estimate for the Hardy spaces

In this section we are going to prove the following bound for the measure of
the superlevel sets of functions from the Hardy spaces. Theorem 1.1 follows
from it by a simple integration. In what follows we retain the notation from
the previous section.

######  Theorem 3.1.

Let $f\in H^{p}$ have norm $1$ and put $u(z)=|f(z)|^{p}(1-|z|^{2})$. Then for
all $t\in(0,\infty)$ we have

(3.1) $\mu(t)\leq\max\left(\frac{1}{t}-1,0\right).$

Equality in (3.1) holds for all $0<t<\infty$ if $f(z)\equiv 1$.

Note that this theorem verifies Conjecture $2$ from [3].

###### Proof.

Put $t_{0}=\max_{z\in\mathbb{D}}u(z)$. By the pointwise bound (1.1) we have
$t_{0}\leq 1$. In particular, for $t\geq t_{0}$ the bound holds trivially.

Assume that there exists some $0<t_{1}<t_{0}$ such that
$\mu(t_{1})>\frac{1}{t_{1}}-1$. Then $\mu(t_{1})=\frac{c}{t_{1}}-1$ for some
$c>1$. We claim that in that case for all $0<t<t_{1}$ we have
$\mu(t)\geq\frac{c}{t}-1$.

Indeed, applying the pointwise bound once again together with $u(z)\to 0$ as
$|z|\to 1$, we see that Theorem 2.1 can be applied to $f$ with $a=p,b=1$, and
we get that $g(t)=t(\mu(t)+1)$ is decreasing. Since $g(t_{1})=c$ we get
$g(t)\geq c,0<t<t_{1}$, which corresponds to $\mu(t)\geq\frac{c}{t}-1$.

Next we are going to use the fact that
$||f||_{A^{pr}_{r}}^{pr}\to||f||_{H^{p}}^{p}=1$ as $r\to 1$. Note that we can
express the $A^{pr}_{r}$ norms via $\mu(t)$:

$||f||_{A^{pr}_{r}}^{pr}=c_{r}\int\limits_{0}^{t_{0}}\mu(t)t^{r-1}dt,$

where $c_{r}=r(r-1)$ is so that
$c_{r}\int\limits_{0}^{1}(\frac{1}{t}-1)t^{r-1}dt=1$. The precise value of
$c_{r}$ is not important for us except that $c_{r}\to 0$ as $r\to 1$ which
corresponds to the fact that the norm in the Hardy space is supported on the
circle $\partial\mathbb{D}$ and not on the whole disk $\mathbb{D}$. By the
above bound we have

(3.2) $||f||_{A^{pr}_{r}}^{pr}\geq
c_{r}\int\limits_{0}^{t_{1}}(\frac{c}{t}-1)t^{r-1}dt.$

We have

$1=c_{r}\int\limits_{0}^{1}(\frac{1}{t}-1)t^{r-1}dt=c_{r}\int\limits_{0}^{t_{1}}(\frac{1}{t}-1)t^{r-1}dt+c_{r}\int\limits_{t_{1}}^{1}(\frac{1}{t}-1)t^{r-1}dt=A(r)+B(r).$

Since $c_{r}\to 0$ as $r\to 1$, we see that $B(r)\to 0$ as $r\to 1$ as well
because the function we are integrating is bounded. Therefore, $A(r)\to 1$ as
$r\to 1$. On the other hand, we have

$\frac{\frac{c}{t}-1}{\frac{1}{t}-1}=c+\frac{c-1}{\frac{1}{t}-1}\geq c,$

thus the right-hand side of (3.2) is at least $cA(r)$. Therefore $1=\lim_{r\to
1}||f||_{A^{pr}_{r}}^{pr}\geq c\lim_{r\to 1}A(r)=c$ which is a contradiction.
∎

######  Remark 3.2.

By looking more closely at the above proof we can actually get the following
formula for the $H^{p}$-norm:

(3.3) $||f||_{H^{p}}^{p}=\sup_{t:\mu(t)>0}t(\mu(t)+1)=\lim_{t\to
0}t(\mu(t)+1)=\lim_{t\to 0}t\mu(t),$

which seems to be new.

###### Proof of Theorem 1.1.

If $\lim_{t\to 0^{+}}G(t)>0$ then for all $f\in H^{p}$ with $||f||=1$ the
integral in (1.3) is $+\infty$. Similarly if $\lim_{t\to 0^{+}}G(t)<0$ then
the integral is always $-\infty$. Thus, we can assume that $\lim_{t\to
0^{+}}G(t)=0$. Then this integral can be expressed via $\mu(t)$ as

(3.4) $\int\limits_{0}^{\infty}\mu(t)dG(t).$

Note that here we used that the function $\mu(t)$ is continuous, that is the
sets $\\{u(z)=t\\}$ have zero measure.

Since $G$ is increasing, measure $dG(t)$ is positive. Thus, by (3.1) this
integral is at most

$\int\limits_{0}^{\infty}\max\left(\frac{1}{t}-1,0\right)dG(t),$

which is the value of (1.3) for $f(z)\equiv 1$. ∎

##  4\. proof of Theorem 1.2

As in the proof of Theorem 1.1, we begin by observing that if $\lim_{t\to
0^{+}}G(t)\neq 0$, then the integral in (1.4) is always $\pm\infty$. Thus, we
restrict ourselves to the case $\lim_{t\to 0^{+}}G(t)=0$. In that case, the
integral in (1.4) can be rewritten as

$\int_{0}^{\infty}\mu(t)G^{\prime}(t)dt,$

where $\mu(t)=m(\\{z:u(z)>t\\})$ and $u(z)=|f(z)|^{p}(1-|z|^{2})^{\alpha}$. We
wrote here $G^{\prime}(t)dt$ instead of $dG(t)$ as in (3.4) because $G$ is
convex and hence its derivative is an actual function and not just a measure.
We also assume that $||f||_{A^{p}_{\alpha}}=1$, that is

$\int_{0}^{\infty}\mu(t)dt=\frac{1}{\alpha-1}.$

Applying Theorem 2.1 to $f$ with $a=p,b=\alpha$ we get
$\mu(t)=\frac{g(t)}{t^{1/\alpha}}-1$ where $g$ is decreasing on $(0,t_{0})$
with $t_{0}=\max_{z\in\mathbb{D}}u(z)$. By the pointwise bound (1.2) we know
that $t_{0}\leq 1$.

We are going to make a change of variables $x=t^{1-1/\alpha}$ in both of the
above integrals. We get

(4.1) $\int\limits_{0}^{x_{0}}(h(x)-x^{1/(\alpha-1)})dx=\frac{1}{\alpha},$

where $x_{0}=t_{0}^{1-1/\alpha}\leq 1$ and $h(x)=g(x^{\alpha/(\alpha-1)})$ is
a decreasing function. We want to maximize

(4.2) $\int\limits_{0}^{x_{0}}(h(x)-x^{1/(\alpha-1)})s(x)dx,$

where $s(x)=G^{\prime}(x^{\alpha/(\alpha-1)})$ is an increasing function. From
now on we will treat $h$ as a generic decreasing function, forgetting for a
while that it came from the distribution of a holomorphic function, and we
also fix $x_{0}$ for now. To proceed we need the following lemma.

######  Lemma 4.1.

Let $s(x),0\leq x\leq x_{0}$, be a function satisfying

(4.3) $\int_{0}^{X}s(x)dx\leq Xs(X)$

for all $0\leq X\leq x_{0}$. Then among all decreasing functions
$h:[0,x_{0}]\to\mathbb{R}$ with $\int_{0}^{x_{0}}h(x)=c$ the constant function
$h(x)=\frac{c}{x_{0}}$ maximizes $\int_{0}^{x_{0}}s(x)h(x)dx$.

Note that any increasing function $s$ trivially satisfies condition (4.3).
However, even though there is a slightly simpler proof of this lemma in the
case of increasing $s$, the proof of the general case is still short, and
therefore we decided to prove lemma in full generality.

###### Proof.

For clarity of exposition, we will only prove the lemma in the case when the
function $h$ is in $C^{1}([0,x_{0}])$. The proof in the general case can be
obtained by the slight modification of the argument below.

Put $S(X)=\int_{0}^{X}s(x)dx$ and $l(x)=-h^{\prime}(x)\geq 0$ and integrate by
parts in both integrals. We get

$x_{0}h(x_{0})+\int_{0}^{x_{0}}xl(x)dx=c,$

and we want to maximize

(4.4) $S(x_{0})h(x_{0})+\int_{0}^{x_{0}}S(x)l(x)dx.$

Note that $\left(\frac{S(x)}{x}\right)^{\prime}=\frac{xs(x)-S(x)}{x^{2}}\geq
0$, thus $\frac{S(x)}{x}$ is increasing. Therefore we have

$\int_{0}^{x_{0}}S(x)l(x)dx\leq\int_{0}^{x_{0}}x\frac{S(x_{0})}{x_{0}}l(x)dx=\frac{S(x_{0})}{x_{0}}\int_{0}^{x_{0}}xl(x)dx.$

Plugging this into (4.4) we get

$S(x_{0})h(x_{0})+\int_{0}^{x_{0}}S(x)l(x)dx\leq\frac{S(x_{0})}{x_{0}}\left(x_{0}h(x_{0})+\int_{0}^{x_{0}}xl(x)dx\right)=c\frac{S(x_{0})}{x_{0}}.$

For $l(x)=0$ (that is, $h(x)$ being constant) we have equality here. ∎

Note that, for a fixed $x_{0}$, we know the value of $\int_{0}^{x_{0}}h(x)dx$
from (4.1), while in (4.2) we want to maximize $\int_{0}^{x_{0}}h(x)s(x)dx$
plus some constant depending on $x_{0}$. Therefore, if $x_{0}$ is fixed, then
we may assume that $h(x)$ is constant and equal to

$C(x_{0})=\frac{1}{x_{0}}\left(\frac{1}{\alpha}+\frac{\alpha-1}{\alpha}x_{0}^{\alpha/(\alpha-1)}\right),$

while (4.2) is equal to

$A(x_{0})=C(x_{0})S(x_{0})-\int_{0}^{x_{0}}x^{1/(\alpha-1)}s(x)dx.$

Our next goal is to show that $A(x_{0})$ is an increasing function of $x_{0}$.
To do so we first assume that $C(x_{0})$ is decreasing which we will prove
later. Taking the derivative of $A$ we get

$A^{\prime}(x_{0})=C^{\prime}(x_{0})S(x_{0})+C(x_{0})s(x_{0})-x_{0}^{1/(\alpha-1)}s(x_{0}).$

Since $S(x_{0})\leq x_{0}s(x_{0})$ and $C^{\prime}(x_{0})\leq 0$, this
quantity is at least

$C^{\prime}(x_{0})x_{0}s(x_{0})+C(x_{0})s(x_{0})-x_{0}^{1/(\alpha-1)}s(x_{0})=s(x_{0})\left(x_{0}C^{\prime}(x_{0})+C(x_{0})-x_{0}^{1/(\alpha-1)}\right).$

The expression in the brackets turns out to be exactly $0$ – this can be
either verified by a direct computation or, slightly informally, deduced from
the fact that for $s(x)=1$ (which corresponds to $G(x)=x$) we should always
get the same value and all our inequalities turn into equalities.

It remains to show that $C(x_{0})$ is a decreasing function. We first outline
an informal argument, which this time is a bit harder to make rigorous, so
later we will explicitly compute $C^{\prime}(x_{0})$ and verify that it is
negative. The informal argument is as follows: if we treat $h$ as coming from
the distribution of the analytic function and if for some $x_{1}<x_{2}$ we
would have $C(x_{1})<C(x_{2})$, then this would mean that all the superlevel
sets of the function corresponding to $x_{2}$ have larger hyperbolic measure
so they can not both have the same $A^{p}_{\alpha}$-norm. But since we already
abandoned Bergman spaces by treating $h$ as a generic decreasing function this
argument is not rigorous so we will just compute $C^{\prime}(x_{0})$:

$C^{\prime}(x_{0})=\frac{x_{0}^{a/(a-1)}-1}{ax_{0}^{2}}.$

Thus, $C^{\prime}(x_{0})$ is nonpositive for $0<x_{0}\leq 1$, therefore
$A(x_{0})\leq A(1)$ for $0<x_{0}\leq 1$.

It remains to note that for the case $f(z)\equiv 1$ we have $x_{0}=1$ and
$h(x)$ is constant, thus the value of (1.4) is exactly $A(1)$ and the Theorem
is proved. ∎

######  Remark 4.2.

As can be seen from the proof, it is enough to assume that the function
$s(x)=G^{\prime}(x^{\alpha/(\alpha-1)})$ satisfies (4.3) for all $X>0$ which
is strictly weaker than the assumption that $G$ be convex.

######  Remark 4.3.

Note that we actually proved that the value of (1.4) is at most $A(x_{0})$
where $x_{0}=t_{0}^{1-1/\alpha},\,t_{0}=\max_{z\in\mathbb{D}}u(z)$. In
particular, if the function $G$ is strictly convex such as
$G(t)=t^{s},1<s<\infty$ then the function $A$ is strictly increasing and thus
the reproducing kernels are the only maximizers of (1.4).

##  5\. Coefficient estimates for Hardy spaces

An important special case of contraction from the Hardy space to a Bergman
space is $H^{p}\subset A^{2}_{2/p}$ for $0<p<2$. It turns out that, given
$f(z)=\sum_{n=0}^{\infty}a_{n}z^{n}\in A^{2}_{2/p}$, we can express its norm
as follows

$||f||_{A^{2}_{2/p}}^{2}=\sum\limits_{n=0}^{\infty}\frac{|a_{n}|^{2}}{c_{2/p}(n)},\quad
c_{2/p}(n)=\binom{n+2/p-1}{n}.$

Thus, for a function $f\in H^{p}$ we have

(5.1)
$\sum\limits_{n=0}^{\infty}\frac{|a_{n}|^{2}}{c_{2/p}(n)}\leq||f||_{H^{p}}^{2}.$

This can be seen as sharpening of the classical Hardy-Littlewood inequality
[5]. Before only partial results were obtained in the direction of this
inequality, such as proving it in the case $\frac{2}{p}\in\mathbb{N}$ [4] and
proving it for the first few coefficients [1, 8] or with a constant slightly
worse than $1$ [10]. Note that inequality (5.1) is sharp in every coefficient
since it turns into an equality for all reproducing kernels.

By the inductive argument from [6] inequality 5.1 can be extended to the
functions from the Hardy space on the multidimensional disk $\mathbb{D}^{k}$:
for $f(z_{1},\ldots,z_{k})=\sum\limits_{n_{1},\ldots,n_{k}\geq
0}a_{n_{1},n_{2},\ldots,n_{k}}z_{1}^{n_{1}}\ldots z_{k}^{n_{k}}$ we have

(5.2) $\sum\limits_{n_{1},\ldots,n_{k}\geq
0}\frac{|a_{n_{1},n_{2},\ldots,n_{k}}|^{2}}{c_{2/p}(n_{1})\ldots
c_{2/p}(n_{k})}\leq||f||_{H^{p}(\mathbb{D}^{k})}.$

By passing to the limit and noting that $c_{2/p}(0)=1$, we can extend this
inequality to the analytic functions on the infinite-dimensional disk
$\mathbb{D}^{\infty}$. These spaces in turn can be realized as spaces of
Dirichlet series in the right half-plane. In this setting 5.2 takes the
following form.

######  Theorem 5.1.

For a Dirichlet polynomial $f(z)=\sum_{n=1}^{N}\frac{a_{n}}{n^{s}}$ and
$0<p<2$ we have

$\sum_{n=1}^{N}\frac{|a_{n}|^{2}}{d_{2/p}(n)}\leq||f||_{\mathcal{H}^{p}}^{2},$

where $d_{2/p}(n)$ are the coefficients in
$\zeta(s)^{2/p}=\sum_{n=1}^{\infty}\frac{d_{2/p}(n)}{n^{s}}$ and

$||f||_{\mathcal{H}^{p}}^{p}=\lim_{T\to\infty}\frac{1}{2T}\int_{-T}^{T}|f(it)|^{p}dt.$

Combining this theorem with the methods from [2] we can slightly improve the
bounds for the pseudomoments of the Riemann zeta function, though the
improvement is only in the constant factor and not asymptotic.

### Acknowledgments

I would like to thank Kristian Seip for introducing me to the topic of
contractive inequalities, Yurii Lyubarskii for telling me about the paper
[11], Ivan Izmestiev for a discussion on isoperimetric inequalities and Fabio
Nicola, Jan Philip Solovej and Paolo Tilli for helpful comments.

## References

  * [1] A. Bondarenko, W. Heap, and K. Seip, ‘‘An inequality of Hardy-Littlewood type for Dirichlet polynomials’’, J. Number Theory, vol. 150, pp. 191–205, 2015.
  * [2] A. Bondarenko, O. F. Brevig, E. Saksman, K. Seip, and J. Zhao, ‘‘Pseudomoments of the Riemann zeta function’’, Bull. Lond. Math. Soc., vol. 50, no. 4, pp. 709–724, 2018.
  * [3] O. F. Brevig, J. Ortega-Cerdà, K. Seip, and J. Zhao, ‘‘Contractive inequalities for Hardy spaces’’, Funct. Approx. Comment. Math., vol. 59, no. 1, pp. 41–56, 2018.
  * [4] J. Burbea, ‘‘Sharp inequalities for holomorphic functions’’, Illinois J. Math., vol. 31, no. 2, pp. 248–264, 1987.
  * [5] G. H. Hardy and J. E. Littlewood, ‘‘Some new properties of Fourier constants’’, Math. Ann., vol. 97, no. 1, pp. 159–209, 1927.
  * [6] H. Helson, ‘‘Hankel forms and sums of random variables’’, Studia Math., vol. 176, no. 1, pp. 85–92, 2006.
  * [7] I. Izmestiev, ‘‘A simple proof of an isoperimetric inequality for Euclidean and hyperbolic cone-surfaces’’, Differ. Geom. Appl, vol. 43, pp. 95–101, 2015.
  * [8] A. Kulikov, ‘‘A contractive Hardy–Littlewood inequality’’, Bull. London Math. Soc., 53, pp. 740–746, 2020.
  * [9] E.H. Lieb and J.P. Solovej, ‘‘Wehrl-type coherent state entropy inequalities for SU(1,1) and its AX+B subgroup’’, Partial differential equations, spectral theory, and mathematical physics—the Ari Laptev anniversary volume, 301–314, EMS Ser. Congr. Rep., EMS Press, Berlin, 2021.
  * [10] A. Llinares, ‘‘On a conjecture about contractive inequalities for weighted Bergman spaces’’, arXiv:2112.09962.
  * [11] F. Nicola and P. Tilli, ‘‘The Faber-Krahn inequality for the Short-time Fourier transform’’, arXiv:2106.03423.
  * [12] R. Osserman, ‘‘The isoperimetric inequality’’, Bull. Amer. Math. Soc., 84(6), pp. 1182–1238, 1978.x
  * [13] M. Pavlović, ‘‘Function classes on the unit disk’’, De Gruyter Studies in Mathematics, vol. 52, De Gruyter, Berlin, 2014.
  * [14] E. Schmidt, ‘‘Über die isoperimetrische Aufgabe im n-dimensionalen Raum konstanter negativer Krümmung. I. Die isoperimetrischen Ungleichungen in der hyperbolischen Ebene und fur Rotationskörper im n-dimensionalen hyperbolischen Raum’’, Math. Z., 46, pp. 204–230, 1940.


11institutetext: Oklahoma State University, Stillwater, OK 08544, USA
22institutetext: University of Wisconsin–Madison,Madison, Wisconsin, USA
22email: abc,lncsuni-heidelberg.de 33institutetext: Georgia State University,
Atlanta. GA, USA
33email<EMAIL_ADDRESS>
# MPool: Motif-Based Graph Pooling††thanks: Supported by organization x.

Muhammad Ifte khairul Islam 11 Max Khanov 22 Esra Akbas 33

###### Abstract

Graph Neural networks (GNNs) has recently become a powerful technique for many
graph-related tasks including graph classification. Current GNN models apply
different graph pooling methods that reduce the number of nodes and edges to
learn the higher-order structure of the graph in a hierarchical way. All these
methods primarily rely on Graph Convolution Networks(GCNs) with the layer-wise
propagation base on the one-hop neighbors to calculate the assignment matrix
in the clustering-based method and score in the node selection-based method.
However, they do not consider the higher-order structure of the graph. In this
work, we propose a graph pooling method Motif Pool(MPool) that considers
motifs as the higher-order graph structure for pooling operation. We proposed
two types of graph pooling. As the first one, we develop node selection-based
graph pooling with designing node ranking model considering motif adjacency of
nodes. As the second one, we develop cluster-based graph pooling with
designing spectral clustering model using motif adjacency. We demonstrate
detailed experiments on eight benchmark datasets. We show that our proposed
method shows better accuracy than the current baseline method for graph
classification tasks.

###### Keywords:

Graph Neural Network GNN Pooling Motif Graph Classification.

##  1 Introduction

The graph is an important data structure for modeling complex systems in
different domains such as Twitter, Reddit, and IMDB from the social network
domain, protein-protein interaction, and drug-drug interaction from the
biological domain. Recently, deep learning models have been adopted for
graphs, and many different Graph Neural networks (GNNs) [Kipf] have been
proposed to capture the complex relation information within graph data. GNNs
have shown competitive performance for many graph-related tasks, such as semi-
supervised node classification, link prediction, and graph classification. By
inputting a graph with node attributes and message propagation along the
edges, while some GNN models learn the node-level representation for node
classification [Kipf, hamilton2017inductive, velivckovic2017graph], some
others learn graph-level representation for graph classification[gao2019graph,
pmlr-v97-lee19c, bianchi2020spectral].

Graph classification is the task of predicting graph labels with considering
node features and graph structure. To capture the local and global structural
information of the graph in the graph representation, current GNN models apply
different graph pooling methods. Motivated from the pooling layer in CNNs
[krizhevsky2012imagenet], graph pooling methods have been used to reduce the
number of nodes and edges to learn graph representation. Previous pooling
methods do the pooling operation in global by using neural network or
summation on node feature. However, these global methods are unable to capture
the higher-order structure as they pool all nodes in one step. As a solution
to this problem, current methods coarsen the graph in a hierarchical way by
reducing the size of the graph in multiple steps and the utilize every pooled
graph representation for the final graph representation.

There are mainly two types of hierarchical pooling methods for the graph in
the literature: clustering-based and selection-based methods. While
clustering-based methods merge similar nodes into super nodes using a cluster
assignment matrix, selection-based methods calculate a score for every node,
which represents their importance, and select top $k$ nodes based on the score
with discarding other nodes from the graph. All these methods primarily rely
on Graph Convolution Networks (GCNs) with the layer-wise propagation based on
the one-hop neighbors to calculate the assignment matrix in the clustering-
based method and score in the selection-based method. However, the current
hierarchical pooling methods fail to incorporate the higher-order structure of
the graph in pooling.
On the other hand, higher-order graph structures have been used in many graph
mining tasks, including classification [lee2019graph], community detection
[benson2016higher]. There are different technical tools to model higher-order
graph structures [benson2021higher] such as hypergraphs, simplicial complexes
[aktas2021identifying], and motifs [milo2002network]. Between these tools,
motifs (graphlets) are small, frequent and connected subgraphs that are mainly
used to measure the connectivity patterns of nodes [milenkovic2008graphcrunch,
elhesha2016identification] (see Figure 1 for a preview). They capture the
local topology around the vertices, and their frequency can be used as the
global fingerprints of graphs. Although motifs have been used for different
graph mining tasks, including classification [lee2019graph], community
detection [li2019edmot], to the best of our knowledge, they have not been used
in graph pooling operations. On the other hand, utilizing these structures for
pooling provides crucial information about the structure and the function of
many complex systems that are represented as graphs [paranjape2017motifs,
prill2005dynamic]. In this paper, we propose a motif-based graph pooling
method, MPool, that considers these higher-order graph structures for pooling
operation. We utilize motifs to model the relation between nodes and use this
model for message passing and pooling in GNN.

We develop two motif-based graph pooling models: selection-based and
clustering-based. For the selection-based graph pooling model, we design a
node ranking model considering motif-based relations of nodes. We calculate
the attention score of nodes for node selection. We use graph convolution to
calculate the attention where we use node attributes and also motif-based
graph topological information instead of pairwise edge information. Based on
the scores, we select the top $k$ nodes to create the pooled graph and remove
other nodes from the graph. For clustering-based graph pooling, we design a
motif-based clustering model using the neural network. Our pooling function
learns a differentiable soft assignment that groups nodes based on learned
embedding from the convolution layer. We jointly optimize this function by
minimizing the usual supervised loss and also unsupervised loss as a
relaxation of the normalized mincut objective. However, instead of defining
mincut objectives on the regular adjacency matrix, we define it in the motif
adjacency matrix. After learning the clustering assignment matrix from
clustering, we group the nodes in the same cluster and create a coarsened
graph. Both models take motif into consideration in defining the node
adjacency hence incorporating higher-order graph structure in graph pooling
operation. We further demonstrate detailed experiments on eight benchmark
datasets. Our results show that the proposed pooling methods show better
accuracy than the current baseline pooling methods for graph classification
tasks. We also do extensive experiments to demonstrate the effectiveness of
our models on graph reconstructions with an autoencoder.
The paper is formatted as follows: In Section 2, we discuss the related work
on GNNS, graph pooling, and how motifs are used in GNN. In Section 3, we
present the preliminary concepts for the problem formulation, GNN pooling
models for graph classification, and motifs. In Section 4, we explain our
methodology for motif-based graph pooling and how to incorporate them into GNN
models. In Section 5, we present our results on real-world datasets by
comparing current baseline pooling methods. Our final remarks with future work
directions are found in Section 6.

##  2 Related Work

In this section, we briefly discuss related works for graph neural network,
graph pooling and motifs.

###  2.1 Graph Neural Networks

In general, GNNs can be categorized via two different approaches: spectral and
non-spectral. In the spectral approach [Kipf, bruna2013spectral,
defferrard2016convolutional], convolution operation for the graph is defined
by Fourier transform and graph Laplacian. Spectral methods have a basis-
dependent problem in that they are not generalizable to graphs with different
structures. Using this approach, a model trained on one graph structure cannot
be effectively transferred to another. To overcome this problem, non-spectral
methods design convolution operations by directly aggregating neighbor nodes’
information [hamilton2017inductive, velivckovic2017graph]. These methods are
faster and more easily generalizable to graphs of different structures.
GraphSAGE [hamilton2017inductive] is one of the popular methods of non-
spectral methods where it samples a fixed-sized neighborhood and aggregates
its information. Moreover, Graph attention network (GAT)
[velivckovic2017graph] uses the attention mechanism to aggregate neighbor
information where it gives different weights to neighborhood representation.

###  2.2 Graph Pooling

Graph pooling operation on GNN is developed for learning hierarchical graph
representation learning. There are two different classes of graph pooling in
the literature: global pooling and hierarchical pooling. Global pooling
methods [vinyals2015order, zhang2018end] summarize entire graph in one step.
For example, Set2Set [vinyals2015order] implemented the global pooling using
LSTMs where it uses iterative content-based attention to calculate the
importance of nodes. Another method SortPool [zhang2018end] sorts the nodes
based on their embedding and feeds them to the next layers. However global
pooling method does not learn graph representation hierarchically, which is
very important for graph-level representation.

Hierarchical pooling methods learn graph representation hierarchically and
capture the local substructures of graphs. There are two different
hierarchical pooling methods in the literature: node cluster pooling and
selection pooling. Node cluster pooling methods [ying2018hierarchical,
bianchi2020spectral, ranjan2020asap, bacciu2021k] do the pooling operation by
calculating the cluster assignment matrix using node features and graph
topology. After calculating the cluster assignment matrix, they build the
coarse graph by grouping the nodes on the same cluster. For example, while
DiffPool[ying2018hierarchical] calculates the cluster assignment matrix using
a graph neural network, MinCutPool[bianchi2020spectral] calculates the cluster
assignment matrix using a multi-label perception.

Selection-based pooling methods [gao2019graph, pmlr-v97-lee19c, gao2021ipool,
zhang2019hierarchical] compute the importance scores of nodes and select top
$k$ nodes based on their scores and drop other nodes from the graph to create
the pooled graph. For example, while gPool [gao2019graph] calculates the score
using node feature and a learnable vector, SAGPool [pmlr-v97-lee19c] uses an
attention mechanism to calculate the scores. SUGAR [sun2021sugar] uses
subgraph neural network to calculate the score and select top-$K$ subgraph for
pooling operation. They use BFS algorithm to sample the subgraph from the
input graph. Selection-based pooling methods are generally more memory
efficient as they avoid generating dense cluster assignments and select nodes
based on their scalar projection values on a trainable vector. However, both
types of methods mainly use the node features and normal adjacency matrix with
GNNs for pooling operation. On the other hand, higher-order structures, i.e.,
motifs, are also important for the graph-based task. In our proposed method,
we use motif structure for the pooling operation to integrate higher-order
graph structure information during learning graph representation.

###  2.3 Motifs in Graph Neural Network

Motifs are the most common higher-order graph structure used in various graph
mining problems in different networks such as social network, biological
network and chemical network. A few works have used motif structure in GNNs as
well [yang2018node, Motif-Attention, peng2020motif, monti2018motifnet]. MCN
[Motif-Attention] creates motif attention mechanism for graph convolution
layer to learn node representation. All these methods employ motifs for
learning node or subgraph representation. In our proposed method, we use motif
for both types of graph pooling method: selection-based and clustering-based.
We further show that our methods outperform baseline methods for the most of
the datasets on graph classification task.

##  3 Preliminaries

In this section, we discuss the problem formulation of graph classification
and the notation. Then, we explain the graph neural network model with a
pooling operation for graph classification. At the end of the section, we
explain motif types and motif adjacency calculation.

###  3.1 Problem Formulation and Notation

We denote a graph as $G(V,A,X)$ where $V$ is the node set,
$A\in{\mathbb{R^{N\times N}}}$ is the adjacency matrix and
$X\in\mathbb{R}^{N\times d}$ is the feature matrix with $d$ dimensional node
feature and $N$ is the number of nodes in the graph. We denote a graph
collection as $(\mathcal{G},Y)$ where
$\mathcal{G}=\\{G_{0},G_{1},...,G_{n}\\}$ with $G_{i}$’s are graphs and $Y$ is
the set of the graph labels. In this paper, we work on the graph
classification problem, whose goal is to learn mapping function
$f:\mathcal{G}\rightarrow{Y}$ to predict the graph labels.

###  3.2 Graph Neural Network for Graph Classification

Recently, GNNs have been used for graph classification problem. These GNNs
have basically two modules: message-passing and pooling. For message passing
operation, Graph convolution network (GCN) [Kipf] is the most widely used GNN
model. GCN is a multilayer neural network to process the graph data where it
combines the features of each node from its’ neighbors with propagating the
information through the edges as follows:

$Z^{(l+1)}=\sigma{(\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}Z^{(l)}\theta^{(l)})}$
(1)

where $Z^{(l+1)}$ is the node representation matrix for layer $(l+1)$,
$\sigma$ is an activation function, $\tilde{A}=A+I$ is the adjacency matrix
with self-loop, $\tilde{D}\in{\mathbb{R^{N\times N}}}$ is the normalized
degree matrix of $\tilde{A}$, $\theta^{(l)}$ is trainable weight for
$l^{(th)}$ layer and $Z^{(l)}$ is the input node representation matrix for
${k+1}^{th}$ layer obtained from previous layer. $H_{0}=X$ is initial input
node feature matrix of the input graph. We also utilize this GNN model for
message passing operation in this paper.

The second module of GNNs for graph classification is the pooling operation.
The original purpose of GNN is to learn the node representations of the input
graph. For the graph classification problem, we need to obtain graph
representation, hence the need to encode node representations into one graph
representation. Graph pooling models are proposed for this sake. The main idea
behind graph pooling is to coarsen the graph by reducing the number of nodes
and edges to encode the information of the whole graph. Earlier methods do
graph pooling globally, where they do the pooling by summing up all node
features at once. However, these summarization methods do not capture graph
structure. To solve this issue, hierarchical pooling methods are proposed
recently that apply message passing and pooling in each layer in a
hierarchical way and gather all information at the end. In the literature,
there are two types of hierarchical graph pooling methods: selection-based and
clustering-based methods.

Selection-based methods calculate a score (attention) using a scoring function
for every node that represents their importance. Based on the calculated
scores, top $k$ nodes are selected to construct a pooled graph. The following
equation gives a general overview of the top $k$ selection graph pooling
method:

$\displaystyle S=score(G,X)$ (2) $\displaystyle idx=topK(S,[\alpha\times N])$
$\displaystyle A^{(l+1)}=A_{idx,idx}$

where $S\in R^{N\times 1}$ is the scores of nodes and $\alpha$ is the pooling
ratio, and N is the number of nodes.

In this paper, we use SAGPool [pmlr-v97-lee19c] as the base for our selection-
based pooling. SAGPool defines scores using the following graph convolution
function

$S=\sigma(GNN(X,A)).$

Clustering-based pooling methods learn a cluster assignment matrix $S\in
R^{N\times K}$ using graph structure and/or node features. Then, they reduce
the number of nodes by grouping them into super nodes by $S\in R^{N\times K}$
to construct the pooled graph at $(l+1)^{th}$ layer as follows

$\displaystyle A^{(l+1)}=S^{(l)^{T}}A^{(l)}S^{(l)}$ (3) $\displaystyle
H^{(l+1)}=S^{(l)^{T}}H^{(l)}.$

In this paper, as the base for our clustering-based pooling methods, we use
MinCutPool [bianchi2020spectral] that is defined based on Spectral clustering
(SC). SC is one of the commonly used methods to find strongly connected
communities on a graph. It finds the clusters by minimizing the overall intra-
cluster edge weights. SC is an NP-hard problem, and the solution with
eigendecomposition of the Laplacian is expensive to calculate. MinCUTpool
proposes to use GNN with a custom loss function to compute cluster assignment
with relaxing the normalized minCut problem. They defines the cluster
assignment matrix with MLP that maps the node features to as
$S=MLP(\tilde{X},\theta_{MLP})$ where $\tilde{X}=GNN(X,\tilde{A})$. In their
method, they show that their clustering approach is equivalent to spectral
clustering. However, they consider only the regular edge-based adjacency
matrix to find clusters. On the other hand, considering edge-type relations
between nodes may result in ignoring the higher-order relations. Including
higher-order relations like motifs for clustering may produce better groups
for pooling.

In our proposed method, we use motifs during the graph pooling operation.
Hence, we can capture higher-order graph structures to obtain the graph
representation.

###  3.3 Readout Function and Output Layer

To get a fixed-sized of representation from different layers’ pooled graph, we
apply a readout function[pmlr-v97-lee19c] that aggregates the node features as
follows:

$\displaystyle
Z=\frac{1}{N}\sum_{i=1}^{N}x_{i}||\overset{N}{\underset{i=1}{\max}}\ x_{i}$
(4)

where $N$ is the number of nodes, $x_{i}$ is the $i^{th}$ node feature and
$||$ denotes concatenation. After concatenating the results of all readout
functions as representation of the graph, it is given as an input to a
multilayer perceptron with the softmax function to classify the graph. For
graph classification, parameters of GNNs and pooling layers are optimized by a
supervised loss function $\mathcal{L}_{s}$. Equations are given as follows:

$\displaystyle\hat{Y}=softmax(MLP(Z))$ (5)
$\displaystyle\mathcal{L}_{s}=-\sum_{i=1}^{L}\sum_{j=1}^{C}Y_{i,j}log\hat{Y}_{i,j}$

where $Z$ is the graph representation and $\hat{Y}$ is the predicted label of
the graph, and $Y$ is the actual label of the graph.

###  3.4 Motifs and Motif-based Adjacency Matrix

Motifs (graphlets) are small, frequent, and connected subgraphs that are
mainly used to measure the connectivity patterns of nodes
[milenkovic2008graphcrunch, elhesha2016identification]. They are considered as
building blocks for complex networks [yaverouglu2014revealing]. Motifs of
sizes 2-4 are shown in Figure 1. Motifs differ based on the number of nodes
and their connection patterns. To include higher-order structural information
between nodes, we create the motif adjacency matrix $M_{t}$ for a motif $t$ as

$(M_{t})_{i,j}=\\#\textrm{ of the motif $t$ containing nodes $i$ and $j$}$

This matrix encodes motif structure information of the node. Neighborhoods
defined by different motifs can vary significantly. Also, the weight of the
motif adjacency tells us the structural similarity between nodes.

Figure 1: Motif Networks with size 2-4. Figure 2: Overall architecture of the
proposed GNN model with motif-based graph pooling layer. At each hierarchical
layer, we run GCN to update the node embeddings, then give them to the pooling
layer as input and generate coarsened graph from pooling layer. Output of each
layer is given to readout function and concatenated to get the final embedding
of the graph.

##  4 Methodology

In this section, we present our proposed graph pooling method. We first
discuss our overall framework. Then, we explain our selection-based and
clustering-based motif pooling methods. We further explain how we incorporate
these methods into GNN models. Lastly, we present the complexity analysis of
our models.

###  4.1 Framework

Figure 2 shows the overall framework of our proposed model for graph
classification. As the first layer, graph convolution (GCN) takes the
adjacency matrix $A$ and feature matrix $X$ of the graph as input and then
updates the feature matrix by propagating the features through the neighbors
and aggregating features coming from adjacent nodes. After getting the updated
feature matrix from the convolution layer, our proposed graph pooling layer,
MPool, operates coarsen on the graph. These steps are repeated $l$ steps, and
outputs of each pooling layer are aggregated with readout function
[cangea2018towards] to obtain a fixed-sized graph representation. After
concatenating the results of readouts, it is fed to the multi-layer perceptron
(MLP) layer for the graph classification task. We propose two types of motif-
based graph pooling methods: (1) $MPool_{s}$ is the selection-based method and
(2) $MPool_{c}$ is the clustering-based method. These are illustrated in
Figure 3.

In this proposed research, for a fair comparison, we adopted the model
architectures from SAGPool [pmlr-v97-lee19c] and MinCutPool
[bianchi2020spectral] and compared the baselines and our method using the same
architectures. On the other hand, our method is compatible with any graph
neural network that we show later in our experiment section.

Figure 3: An illustration of our motif-based pooling methods. After getting
motif-based graph with respect to selected motif type (triangle is selected in
this illustration), we rank the nodes with GCN and select top $k$ nodes as our
selection-based model MPoolS, and we learn the cluster assignment matrix with
spectral clustering as our clustering-based model MPoolC.

Next, we explain our pooling methods in detail.

###  4.2 Selection-based Pooling via Motifs: MPoolS

Previous selection-based methods [gao2019graph, pmlr-v97-lee19c] do the
pooling operation using a classical adjacency matrix. However, higher-order
structures like motifs show great performance on graph convolution network
[lee2019graph] and are also important structures for graph classification.
Therefore, while calculating attention scores of nodes, considering motif-
induced neighborhoods to integrate information could provide more relevant
information about graph structure [lee2019graph]. In our selection method, we
first calculate the motif adjacency matrix for a certain motif type, e.g.,
triangle, from the original graph as we discuss in Section 3.1. Then, we apply
the graph convolution network to the motif adjacency matrix and calculate the
motif attention score for each node using GNN. Based on these scores, we
select top $k$ nodes for pooling and construct the coarsened graph using the
pooling function. Figure 3 presents the overview of our selection-based graph
pooling method.

####  4.2.1 Motif attention

The attention mechanism is a popular method where models give attention to the
important features of the data. This method has been used in different fields
like deep learning [parikh2016decomposable, zhang2019self] and graph neural
network [velivckovic2017graph, han2018neural]. SAGPool [pmlr-v97-lee19c]
utilize attention mechanism for graph pooling. It obtains self-attention
scores of nodes based on both graph features and topology, where they use
classical graph adjacency matrix to propagate information and calculate the
score.

In our paper, we calculate the motif attention score of nodes to select nodes
to drop and nodes to retain. We use graph convolution to calculate the
attention where we use node attributes and also motif-based graph topological
information instead of pair-wise edge information. motif attention score is
defined as follows

$\displaystyle X=GNN(X,\tilde{A};\theta_{GNN})$ (6) $\displaystyle
S=\sigma{(D^{-\frac{1}{2}}\tilde{M}D^{\prime-\frac{1}{2}}X\theta_{att})}$

where $\tilde{A}$ is the normalized adjacency matrix and $\theta_{GNN}$ is the
learnable parameter, $\sigma$ is an activation function,
$M^{\prime}\in{\mathbb{R^{N\times N}}}$ is the motif adjacency matrix with
self loop where $\tilde{M}=M+I_{N}$, $D^{\prime}\in{\mathbb{R^{N\times N}}}$
is the degree matrix of $M$, and $\theta_{att}\in{R^{d\times 1}}$ is the
parameter matrix for pooling layer. Since we use graph features and motif
adjacency matrix with convolution for motif attention score, the output of
pooling is based on higher-order graph structures and features.

####  4.2.2 Pooling

Based on the motif attention score, we select the top $k$ nodes from the graph
following the node selection method in [gao2019graph]. The top
$k=\alpha\times{N}$ nodes are selected based on the $S$ value where $\alpha$
is the pooling ratio between 0 and 1. Thus, we obtain the pooling graph as
follows

$\displaystyle idx=topK(Z,[\alpha\times N])$ (7) $\displaystyle
X_{out}=X_{idx,:,}\odot Z_{idx},A_{out}=A_{idx,idx}$

where $idx$ is the indices of the top $k$ nodes from the input graph which is
returned by $topK$ function, $X_{idx}$ is the features of the selected $k$
nodes, $Z_{idx}$ is the motif attention value for those nodes. ${\odot}$ is
the element-wise broadcasted product, $A_{idx,idx}$ is row and column wised
indexed matrix, $A_{out}$ is the adjacency matrix and $X_{out}$ is the new
feature matrix of the pooled graph.

###  4.3 Clustering-based Pooling via Motifs: MPoolC

In our clustering-based method, we calculate the cluster assignment matrix $S$
utilizing motif adjacency information. We adopt spectral clustering method
[bianchi2020spectral] where we use multi-layer perceptron (MLP) by inputting
node feature matrix $X$. We use the softmax function on the output layer of
MLP. This function maps each node feature $X_{i}$ into the $i^{th}$ row of a
soft cluster assignment matrix $S$

$\begin{split}S&=MLP(X;\theta_{MLP})\text{}{}\\\
&=\textit{softmax}(ReLU(XW_{1})W_{2}).\end{split}$ (8)

However, as it is seen in Equation 8, we do not use adjacency but use
attributes of nodes obtained from the convolution part. Therefore, to include
motif information in the pooling layer, we use the motif adjacency matrix in
the convolution layer while passing the message to neighbors as

$X=GNN(X,\tilde{M};\theta_{GNN})$

where $\tilde{M}$ is the normalized motif adjacency matrix which we mention in
4.2.1, and $\theta_{GNN}$ and $\theta_{MLP}$ are learnable parameter.

We also incorporate motif information in the optimization. Parameters of the
convolution layer and pooling layer are optimized by minimizing a loss
function $\mathcal{L}$ including the usual supervised loss function
$\mathcal{L}_{s}$ and also an unsupervised loss function $\mathcal{L}_{u}$ as
follows

$\mathcal{L}_{u}=\mathcal{L}_{c}+\mathcal{L}_{o}$

where

$\mathcal{L}_{c}=-\frac{Tr(S^{T}MS)}{Tr(S^{T}DS)}\quad\textrm{and}\quad\mathcal{L}_{o}=\left\|\frac{S^{T}S}{||S^{T}S||_{F}}-\frac{I_{K}}{\sqrt{K}}\right\|_{F}$

Here $\mathcal{L}_{c}$ is the cut loss, which measures the MinCut of the
cluster assignment $S$ that encourages strongly connected nodes in motif
adjacency to be clustered together. $\mathcal{L}_{o}$ is the orthogonality
loss, which helps the clusters to become similar in size. $I_{K}$ is a
(rescaled) clustering matrix $I_{K}=\widehat{S}^{T}\widehat{S}$, where
$\widehat{S}$ assigns exactly $N/K$ points to each cluster.

After calculating the cluster assignment matrix, we do the pooling operation.
We compute the coarsened graph adjacency matrix and attribute matrix using $S$
as follows

$A_{out}=S^{T}MS$ $X_{out}=S^{T}X$

Here $A_{out}\in{R^{K\times K}}$ is the coarsened graph where entry $a_{i,i}$
represents the weighted sum of the edges between nodes of the same cluster $i$
and $a_{i,j}$ represents the weighted sum of the edges between nodes of
cluster $i$ and cluster $j$.

###  4.4 Graph Reconstruction

In addition to using pooling for the graph classification problem, we further
use it in autoencoder (AE) to construct graphs from their representations. We
build a model for graph reconstruction using an AE. Our goal is to preserve
the content information that is coming from node attributes and also
structural information that is coming from the adjacency matrix. We design an
AE by optimizing two objectives: (1) node attribute reconstruction and (2)
edge reconstruction. For the node attribute reconstruction, we use the mean
squared error (MSE) as the optimization function. For the edge reconstruction,
the predicted adjacency matrix is scored against the target adjacency matrix
using binary cross-entropy (BCE) loss. The model architecture is similar to
the one described in figure 2, however, instead of the combination of the
readout vectors going into one MLP, which is optimized with graph
classification task, we use two MLPs, one predicts the adjacency matrix with a
final sigmoid activation and the other one predicts the node attributes. Both
the edge and attribute MLPs use the ReLU activation for the first two layers
and are defined as follows

$\hat{\mathbf{A}}=MLP_{\text{edge}}(V;\theta_{MLP_{\text{edge}}})$
$\hat{\mathbf{X}}=MLP_{\text{attribute}}(V;\theta_{MLP_{\text{attribute}}}).$

To train AE, we replace the supervise loss with the sum of the edge
reconstruction loss and node attribute losses. For the clustering-based
pooling model, we also include $L_{u}$ loss as defined in Section 4.3

$\mathcal{L}_{\text{model}}=\mathcal{L}_{\text{edge}}+\mathcal{L}_{\text{attribute}}$

where

$\mathcal{L}_{\text{edge}}=\mathcal{L}_{BCE}(\textbf{A},\hat{\mathbf{A}})\quad\textrm{and}$
$\mathcal{L}_{\text{attribute}}=\mathcal{L}_{MSE}(\textbf{X},\hat{\mathbf{X}}).$

###  4.5 Complexity Analysis

The computational complexity of our methods involves two parts that correspond
to motif adjacency matrix calculation and pooling layer. Since we use the
method from [underwood2020motif] to calculate the motif adjacency matrix, the
computation complexity of motif matrix calculation for dense matrices is
$O(|V|^{3})$ and for sparse matrices is $O(|V|^{2})$ where $|V|$ represent the
number of vertices. In our selection-based method, we next do the graph
pooling operation similar to SAGPool [pmlr-v97-lee19c] which has time
complexity $O(|V|^{2})$ for dense matrices and $O(|E|)$ for sparse matrices
where $|E|$ is the number of edges. Since our implementation is sparse for our
selection method, the computational complexity is $O(|V|^{2}+|E|)$. For
clustering-based method, we adopt MinCutPool [bianchi2020spectral] that
requires $O(K(E+VK))$ computational cost where $K$ is number of cluster in the
cluster assignment matrix. It is further implemented by a dense matrix. Hence,
the total computational cost for our node cluster-based method is
$O(V^{2}+K(E+VK))$.

##  5 Experiment

In this section, we first introduce the datasets we use in our experiments,
and we discuss the parameter settings in our models. Next, we explain the
baseline methods compared for selection-based and clustering-based. Then, we
evaluate the performance of our models in graph classification problems and
compare our results with the baseline methods for selection-based and
clustering-based. We also give the results for the variation of our model by
utilizing different message-passing models. Further, we analyze the effect of
the motif types on the results of the pooling. Last, we show our experiment
for graph reconstruction.

Table 1: Graph statistics. $|G|,V_{avg}$, $E_{avg}$, and $|C|$ denote the number of graph, the average number of nodes and edges, the number of classes in each dataset, respectively. | Datasets | $|G|$ | $V_{avg}$ | $E_{avg}$ | $|C|$
---|---|---|---|---|---
| D&D | 1178 | 284.32 | 715.66 | 2
Biochemical | NCI1 | 4110 | 29.87 | 32.30 | 2
network | NCI109 | 4127 | 29.68 | 32.13 | 2
PROTEINS | 1113 | 39.06 | 72.82 | 2
| Mutagenicity | 4337 | 30.32 | 30.77 | 2
Social | IMDB-BINARY | 1000 | 19.77 | 96.53 | 2
network | REDDIT-BINARY | 2000 | 429.63 | 497.75 | 2
| COLLAB | 5000 | 74.49 | 2457.78 | 3

###  5.1 Datasets

We use eight benchmark graph datasets in our experiments
[morris2020tudataset]. Among these datasets, three datasets are social
networks, and five other datasets are biological and chemical networks.
Statistics of datasets are summarized in Table 1 with more descriptions as
follows: D&D is a protein structure graph dataset where the label of the graph
indicates if the protein is an enzyme or not. PROTEINS is also a protein
structure graphs dataset. NCI1 and NCI109 datasets are used for anticancer
activity classification. They are labeled as active or inactive against non-
small cell cancer. Mutagenicity is a small molecule drug dataset. Graphs are
labeled either mutagen or non-mutagen. IMDB-BINARY, REDDIT-BINARY, and COLLAB
are social network datasets. IMDB-BINARY is a movie collaboration network
where nodes represent actors/actresses. REDDIT-BINARY is an online discussion
network dataset where nodes represent users. Finally, COLLAB is a scientific
collaboration dataset where nodes represent researchers and edges represent
the collaboration.

Table 2:  Comparison of MPoolS with baseline selection-based pooling methods. Average accuracy. standard deviation and ranks are given for the 10 random seeds. Here MPoolS means selection-based motif pool. | Dataset | gPool | SAGPool | MPoolS
---|---|---|---|---
Biochemical | D&D | 75.01$\pm 0.86$ (3) | 75.71$\pm 3.67$ (2) |  77.21 $\pm 4.59$ (1)
NCI1 | 67.02$\pm 2.25$ (3) | 68.76$\pm 2.98$ (2) |  70.98$\pm 3.44$ (1)
NCI109 | 66.12$\pm 1.60$ (3) |  70.98$\pm 2.00$ (1) | 70.82$\pm 2.06$ (2)
PROTEINS | 71.10 $\pm 0.90$ (3) | 72.48 $\pm 3.95$ (2) |  72.67$\pm 4.21$ (1)
Mutagenicity | 71.90 $\pm 3.70$ (3) | 74.93$\pm 3.85$ (2) |  76.42 $\pm 3.11$ (1)
Social | IMDB-BINARY | 73.40 $\pm 3.7$ (2) | 73.00$\pm$ 4.06 (3) |  73.44$\pm 3.97$ (1)
REDDIT-BINARY | 74.70 $\pm 4.50$ (3) |  84.66$\pm 5.40$ (1) | 83.89$\pm 4.32$ (2)
COLLAB |  77.58 $\pm 1.6$ (1) | 72.4$\pm 2.51$ (2) | 68.95$\pm 2.72$ (3)
Avg. Rank | 2.63 | 1.87 | 1.5

###  5.2 Model Training and Evaluation Setup

To evaluate our models for the graph classification task, we randomly split
the data for each dataset into three parts. We use 80% data for the training
set, 10% data for the validation set and 10% data for the test set. We do the
splitting process 10 times using 10 random seed values. We implement our model
using PyTorch and PyTorch Geometric library. For optimizing the model, we use
Adam optimizer [kingma2014adam]. In our experiments, we take node
representation size as 128 for all datasets. Our hyperparameters are as
follows: learning rate in {1e-2, 5e-2, 1e-3, 5e-3, 1e-4, 5e-4}, weight decay
in {1e-2, 1e-3, 1e-4, 1e-5}, and pooling ratio in {1/2, 1/4}. We find the
optimal hyperparameters using grid search. We run the model for a maximum of
100K epochs, and there is an early stopping condition if the validation loss
does not improve for 50 epochs. Our model architecture consists of three
blocks, and each block contains one graph convolution layer and one graph
pooling layer like [pmlr-v97-lee19c]. We use the same model architecture and
hyperparameters with MinCuT and SAGPool models.

Table 3: Comparison of MPoolC with baseline clustering-based pooling methods. Average accuracy, standard deviation, and ranks are given for the 10 random seeds. Here MPoolC means clustering-based motif pool. | Dataset | MinCutPool | DiffPool | ASAP | MPoolC
---|---|---|---|---|---
Biochemical | D&D | 76.66$\pm 3.0$ (3) | 66.95$\pm 2.4$ (4) | 76.87 $\pm 0.7$ (2) |  78.48$\pm 3.3$ (1)
NCI1 | 73.11$\pm 1.4$ (2) | 62.23$\pm 1.9$ (4) | 71.48 $\pm 0.4$ (3) |  74.44$\pm 1.8$ (1)
NCI109 | 71.50$\pm 2.7$ (2) | 61.98$\pm 1.9$ (4) | 70.07 $\pm 0.6$ (3) |  73.12 $\pm 2.5$ (1)
PROTEINS | 76.33$\pm 3.6$ (2) | 68.20 $\pm 2.0$ (4) | 74.19 $\pm 0.8$ (3) |  78.13$\pm 3.3$ (1)
Mutagenicity | 75.93$\pm 2.7$ (3) | 77.60$\pm 2.6$ (2) | - |  78.77$\pm 2.1$ (1)
Social | IMDB-BINARY | 70.78$\pm 4.7$ (3) | 68.40 $\pm 6.1$ (4) |  72.74 $\pm 0.9$ (1) | 71.44$\pm 4.0$ (2)
REDDIT-BINARY | 75.67$\pm 2.7$ (2) | 66.65$\pm 7.7$ (3) | - |  78.77$\pm 5.0$ (1)
COLLAB | 69.91$\pm 2.3$ (4) | 74.83 $\pm 2.0$ (3) | 78.95 $\pm 0.7$ (2) |  83.62$\pm 5.2$ (1)
Avg. Rank | 2.63 | 3.5 | 1.75 | 1.125

###  5.3 Baselines

We use five graph pooling methods as baseline methods in our experiments.
Among them, gPool [gao2019graph] and SAGPool [pmlr-v97-lee19c] are selection-
based method and MinCut [bianchi2020spectral], DiffPool [ying2018hierarchical]
and ASAP [ranjan2020asap] are clustering-based method.

Selection-based models are as follows.

  * •

gPool learns the attention score for nodes using the only node features, and
they select the top $k$ nodes for the pooling operation.

  * •

SAGPool learns attention scores for nodes using GCNs that consider both node
features and graph structure and select top $k$ nodes to create the pooled
graph.

Clustering-based baseline models are as follows.

  * •

MinCut uses the spectral clustering method for graph pooling, where it
calculates the cluster assignment matrix with MLP using attributes of nodes
and uses the minCut loss function considering a graph structure for updating
the cluster assignment matrix.

  * •

DiffPool uses GNN, which considers both attribute and graph structure to
calculate the cluster assignment matrix. It trains the pooling layer by
optimizing the auxiliary link prediction objective and entropy of the cluster
assignment.

  * •

ASAP, Adaptive Structure Aware Pooling proposes a sparse pooling method with a
new self-attention framework for calculating the cluster assignment matrix.

###  5.4 Overall Evaluation

####  5.4.1 Performance on Graph Classification

In this part, we evaluate our proposed graph pooling methods for the graph
classification task on the given eight datasets. Each dataset contains a
certain number of input graphs and their corresponding label. In the graph
classification task, we classify the input graph by predicting the label of
the graph. We use node features of the graph as the initial features of the
model. If a dataset does not contain any node feature, we use node degrees as
initial features using one-hot encoding. Table 3 and Table 2 show the average
graph classification accuracy, standard deviation, and ranking of our models
and other baseline models for all datasets. We can observe from the tables
that both motif-based pooling methods consistently outperform other state-of-
art models, and both get the first rank for almost all datasets.

Table 2 shows the results for our node selection-based model MPoolS and other
selection-based baseline models. We obtain the reported results for gPool from
SAGPool paper since our model architecture and hyperparameters are the same as
SAGPool. As we see from the table, MPoolS gives the highest result for all
biochemical networks except NCI109, and it is almost the same with SAGPool for
it. In particular, MPoolS achieves an average accuracy of 77.21% on D&D and
76.42% on Mutagenity datasets which is around 2% improvement over the SAGPool
method as the second-best model. From social networks datasets, our model
gives better accuracy than gPool and SAGPool model for IMDB-binary and similar
results with SAGPool for the REDDIT-Binary dataset. Just for the COLLAB
dataset, MPoolS is lower than others. As we see, gPool gives the best result;
the reason for this might be that the COLLAB data set is too large, including
many dense graphs, and this could create noise for attention. We further
calculate the average rank for all models, where our models’ average rank is
the lowest at 1.5.

Table 3 shows the performance comparison with our clustering-based model
MPoolC and other clustering-based baseline models. The reported results for
DiffPool come from the SAGPool paper, as their model architecture and
hyperparameter settings are the same. Also, for the ASAP method, we obtain the
results from the initial publication (“-” means that results are not available
for that dataset). As we see from the table, our proposed method MPoolC
outperforms all the baseline methods for all datasets except IMDB-BINARY,
where our model is the second best with giving very close to the first one,
ASAP. In particular, MPoolC achieves an average accuracy of 83.62% on COLLAB
datasets, which is around 5% improvement over the ASAP method as the second-
best model and around 14% improvement over the MinCutPool, which is our base
model.

Figure 4: Performance comparison between MPoolS and MPoolC on graph
classification.

Furthermore, we present the performance comparison between our selection-based
model MPoolS and clustering-based model MPoolC in Figure-4. We can see from
the figure that MPoolC outperforms MPoolS for most of the datasets.
Furthermore, for D&D and PROTEINS datasets, MPoolC gives around 6% more
accuracy than MPoolS. While MPoolS gives better accuracy for two social
networks, IMDB-BINARY and REDDIT-BINARY, MPoolC is better for the COLLAB
dataset. For IMDB-BINARY and REDDIT-BINARY, MPoolS gives about 2% and 5% more
accuracy, respectively, than MPoolC. For the COLLAB dataset, there is a large
performance difference between MPoolS and MPoolC where MPoolS gives around 15%
better accuracy than MPoolC.

####  5.4.2 Ablation Study

While we use GCN as the base model for message passing, our pooling model can
integrate other GNN architectures. In order to see the effects of different
GNN models in our methods, we utilize the other three most widely used
convolutional graph models in the graph convolution layer and motif attention
score calculation part for MPoolS: Graph-SAGE [hamilton2017inductive], GAT
[velivckovic2017graph], and GCN-cheb [defferrard2016convolutional]. Table 4
shows average accuracy results for these GNN models using MPoolS on NCI1 and
IMDB-BINARY datasets. For this experiment, we use triangle motifs for the
motif adjacency matrix calculation. As we see in the table, the effects of GNN
models and which model gives the best result depend on the dataset. While for
the NCI1 dataset, Graph-SAGE gives the highest accuracy, for IMDB-BINARY, all
the models are very close to each other. For this dataset, GAT gives the
highest accuracy, whereas the second highest model is GCN-cheb which gets only
0.5% less accuracy than the GAT model.

Furthermore, Table 4 shows the accuracy for different GNN models using our
clustering-based model MPoolC. As our clustering-based model generates a dense
graph, we need a dense convolution layer. For this reason, we select GCN,
Graph-SAGE, and GraphConv [morris2019weisfeiler] convolution layer as they
support dense graphs. As we see from the table, there is no best model. While
GraphConv gives the highest accuracy for the NCI1 dataset, the GRAPH-SAGE
model gives the best performance for the IMDB-BINARY dataset.

Table 4: MPoolS performance with different GNN models. GNN Model | NCI1 | IMDB-BINARY | NCI1 | IMDB-BINARY
---|---|---|---|---
$MPool_{GCN}$ | 70.98 | 73.44 | 74.44 | 71.44
$MPool_{GraphConv}$ | 74.20 | 73.50 | 75.93 | 71.90
$MPool_{SAGE}$ | 74.69 | 73.00 | 74.13 | 72.22
$MPool_{GAT}$ | 67.15 | 74.00 |  |
Table 5:  MPoolS performance with different motifs. Motif |  DD |  NCI1 |  Mutagenicity |  IMDB-BINARY |  DD |  NCI1 |  Mutagenicity |  IMDB-BINARY
---|---|---|---|---|---|---|---|---
2-star | 77.21 | 69.48 | 70.11 | 73.00 | 78.48 | 73.56 | 73.56 | 71.20
Triangle | 75.63 | 70.98 | 76.42 | 73.44 | 75.80 | 74.44 | 78.77 | 71.44
2-star+triangle | 75.63 | 69.82 | 72.39 | 69.64 | 74.21 | 74.20 | 76.00 | 70.96

We further study the effect of the motif type for pooling. In this experiment,
we use 2-star, triangle, and a combination of 2-star and triangle motifs, as
these motifs are observed the most in real-world networks. We present the
graph classification accuracy for different motifs using MPoolS and MPoolC in
Table 5. As we see in the tables, we get the highest accuracy with the
triangle motif for three datasets. For D&D, we get the highest accuracy with
2-star motif adjacency. We also observe that for D&D, the accuracy of the
selection-based model does not vary much compared to the clustering-based
model. For Mutagenicity, different motifs have a large effect on the accuracy,
where triangle motif adjacency gives around 4% and 3% higher accuracy than the
2-star motif adjacency for the selection-based method and for the clustering-
based model, respectively. For IMDB-BINARY, 2-star and triangle motifs give
similar accuracy for both methods, and 2-star+triangle motif adjacency gives
less accuracy for the clustering-based method.

####  5.4.3 Performance on Graph Reconstruction

(a) Original

(b) MPoolC

(c) MinCutPool

(d) MPoolS

(e) SAGPool

Figure 5: Comparison of different pooling with our proposed models for graph
reconstruction.

We show our graph reconstruction results for our pooling methods and also
SagPool and minCUTpool in Figure 5. The blue graph is the original, and the
orange graph is the reconstructed one. Since the predicted adjacency is
probabilistic, if the value is greater than 50%, we put an edge. The node
attributes are 2D or 3D positions and are graphed in Figure 5. The losses as
MSE for node attributes as position are displayed in Table 6. For the bunny
graph, the clustering-based model gives better results, and MPoolC ties with
SAGPool for the lowest node attribute loss. However, the grid graph and ring
graph selection-based models have better results, and MPoolS has the lowest
node attribute loss for the grid. All methods have 100% accuracy for edges on
the ring and grid graph and an edge accuracy of 97.96% on the bunny graph.
From these results, we can easily see that our models are able to preserve the
content information and graph structure.

Table 6: Autoencoder position loss. Graph | $MPool_{S}$ | $MPool_{C}$ | SAGPool | MinCutPool
---|---|---|---|---
Bunny | 1.64e-07 | 7.49e-10 | 1.63e-07 | 7.49e-10
Ring | 4.12e-09 | 9.80e-08 | 2.44e-09 | 9.79e-08
Grid | 3.24e-09 | 1.11e-07 | 4.75e-09 | 1.11e-07

##  6 Conclusion

In this work, we propose a novel graph pooling method, MPool, that captures
the higher-order graph structures for graph level representation. We develop
graph pooling methods for both types of hierarchical graph pooling models,
namely selection-based and clustering-based. In our selection-based pooling
method, we use the motif attention mechanism, whereas, in the clustering-based
method, we use motif-based spectral clustering using the mincut loss function.
In both methods, we utilize node feature information and graph structure
information together during the learning of the graph feature vector. We show
that our proposed methods outperform baseline methods for most of the
datasets. In the future work, we plan to apply our methods to other graph
mining tasks such as graph visualization and graph clustering. We further plan
to create a motif subgraph from the input node and calculate the importance of
the subgraph for pooling operations that, we believe, can improve the
performance of our methods.