2212

# Alcubierre Warp Drive in Bohmian Quantum Gravity

Sijo K. Joseph  GITAM Deemed to be University, Hyderabad, Telangana, India.
<EMAIL_ADDRESS>
(September 3, 2024)

###### Abstract

Alcubierre warp drive metric is coupled to quantum mechanical scalar matter
field. The requirement of the exotic matter for the warp drive is mapped into
a conformal wave equation. This result into a fourth order partial
differential equation in terms of the quantum mechanical density. Finding a
proper quantum mechanical density obeying the proposed partial differential
equation will be a resolution to the exotic matter problem of Alcubierre warp
drive in Bohmian Quantum Gravity context.

###### pacs:

04.60.-m,03.65.-w,04.50.Kd

##  I Introduction

Generalization of Einstein’s theory of gravity is under intense theoretical
exploration. Main motivation behind this research involves both mathematical
and physical reasons. In a purely mathematical perspective, the Lagrangian
density $\mathscr{L}$ of Einstein’s gravity is simply linear to the Ricci
scalar $R$. One is always tempted to generalize this simple Einstein-Hilbert
Lagrangian to more general ones, resulting into $f(R)$ theories Capozziello
and Faraoni (2011); Bergmann (1968); Deruelle  _et al._ (2010); Shin’ichi and
Odintsov (2007); Atazadeh  _et al._ (2009) and $f(R,T)$ theories etc. Harko
_et al._ (2011) . In addition, there are several physical motivations to study
generalized Einstein theory, for example, the dark energy problem is one among
them Capozziello  _et al._ (2006). Quantum gravity considerations is also
there, which hints the extension of Einstein’s theory for a concise physical
picture.

Even though there are several mathematical route for the generalization of
Einstein’s theory, $f(R)$ theory is mathematically more straightforward. Later
it was shown that $f(R)$ theory of gravity Oikonomou and Karagiannakis (2014);
Capozziello and de Laurentis (2011) is equivalent to scalar tensor theory of
gravity Ntahompagaze  _et al._ (2017). Based on the nature of the covariant
derivative of the metric tensor, Einstein’s gravity can also be generalized in
a different manner. Metric compatibility ($\nabla_{\sigma}g_{\mu\nu}=0$) and
zero torsion ($\Gamma^{\sigma}_{\mu\nu}-\Gamma^{\sigma}_{\nu\mu}=0$) are the
two essential conditions in Einstein’s theory. Both of these conditions can be
relaxed and different kind of extensions Einstein’s theory can be obtained.
Relaxing the metric compatibility condition, one is naturally lead to Weyl
differential geometry Scholz (2017). Due to the research in the last few
decades, it is identified that the Weyl type of differential geometry is very
useful to incorporate quantum mechanical scalar matter fields as a correction
to Einstein’s theory Shojai and Golshani (1998) . Based on the deBroglie-Bohm
version of quantum theory Bohm and Hiley (1975); Bohm (1952a, b), one is able
to couple quantum theory with classical gravity. There are several research
work along this interesting direction.

Usual quantum gravity approaches like Loop Quantum Gravity focuses on the
quantization of gravity Ashtekar and Pullin (2017); Rovelli and Vidotto (2014)
while Bohmian Quantum Gravity gives only a geometrical way to couple quantum
mechanical scalar matter fields with Einstein’s gravity Shojai and Golshani
(1998); Shojai and Shojai (2000); Shojai (1999). Note that gravity is still
treated as classical and we are only focusing on how classical field theories
are coupled each other. We will first focus on the essential equations in
Bohmian Quantum Gravity and more specifically the stress-energy tensor is
analyzed in connection with warp drive. Then we will explore Alcubierre warp
drive metric, taking it as the background space-time coupled to quantum
mechanical scalar matter field. Here we search for the properties of the
quantum system in order to support Alcubierre metric as the background space-
time.

##  II Bohmian Quantum Gravity

In previous research works Gabay and Joseph (2018a); Joseph (2020, 2021), the
following action is taken into account, where the quantum mechanical scalar
matter field is coupled to gravity in a geometric manner (de Broglie-Bohm
manner),

$\displaystyle A[g_{\mu\nu},{\Omega},S,\rho,\lambda]=$
$\displaystyle\frac{1}{2\kappa}\int{d^{4}x\sqrt{-g}\left(R\Omega^{2}-6\nabla_{\mu}\Omega\nabla^{\mu}\Omega\right)}$
$\displaystyle+\int{d^{4}x\sqrt{-g}\left(\frac{\rho}{m}\Omega^{2}\nabla_{\mu}S\nabla^{\mu}S-m\rho\Omega^{4}\right)}$
$\displaystyle+\int{d^{4}x\sqrt{-g}\lambda\left[\ln{\Omega^{2}}-\left(\frac{\hbar^{2}}{m^{2}}\frac{\nabla_{\mu}\nabla^{\mu}\sqrt{\rho}}{\sqrt{\rho}}\right)\right]}.$
(1)

It is already shown that, minimizing the action with respect to $\rho$ and $S$
leads to real and imaginary parts of the Generalized Klein-Gordon Equation.
Here Eq. 2 describes the real part of the Klein-Gordon Equation and it is
given by,

$\begin{split}\nabla_{\mu}S\nabla^{\mu}S-m^{2}\Omega^{2}+\frac{\hbar^{2}}{2m\Omega^{2}\sqrt{\rho}}\Bigl{[}\Box{\Bigl{(}\frac{\lambda}{\sqrt{\rho}}\Bigr{)}}-\lambda\frac{\Box\sqrt{\rho}}{\rho}\Bigr{]}=0.\end{split}$
(2)

Here Eq. 3 gives the generalized continuity equation which is the imaginary
part of the more general Klein-Gordon Equation (see Ref .Gabay and Joseph
(2018b) for more details),

$\displaystyle\nabla_{\mu}(\rho\Omega^{2}\nabla^{\mu}S)=0.$ (3)

One can also see that the constraint equation is given by,

$\displaystyle\Omega^{2}=\exp{\left(\frac{\hbar^{2}}{m^{2}}\frac{\nabla_{\mu}\nabla^{\mu}\sqrt{\rho}}{\sqrt{\rho}}\right)}.$
(4)

where the conformal factor is identified as a quantum mechanical quantity i.e.
the exponential of the Bohmian quantum potential. In varying the action with
respect to $\Omega$, one obtains an equation of motion for the scalar
curvature $R$

$\displaystyle
R\Omega+6\Box\Omega+\frac{2\kappa}{m}\rho\Omega(\nabla_{\mu}S\nabla^{\mu}S-2m^{2}\Omega^{2})+\frac{2\kappa\lambda}{\Omega}=0.$
(5)

Finally, varying the action with respect to the inverse metric tensor
${g}^{\mu\nu}$, the conformally transformed Einstein equation, along with its
stress-energy tensors, are obtained

$\displaystyle\mathcal{G}_{\mu\nu}=T^{\bf{matter}}_{\mu\nu}(S,\rho)+T^{\bf{qm}}_{\mu\nu}(\Omega)+T^{\bf{med}}_{\mu\nu}(\lambda,\rho)$
(6)

where the stress-energy tensors are given by,

$\displaystyle T^{\bf{matter}}_{\mu\nu}(S,\rho)$ $\displaystyle=$
$\displaystyle-\frac{2\kappa}{m}\rho\nabla_{\mu}S\nabla_{\nu}S+\frac{\kappa}{m}\rho\,g_{\mu\nu}\nabla_{\sigma}S\nabla^{\sigma}S$
(7) $\displaystyle-\kappa m\rho\Omega^{2}g_{\mu\nu}.$ $\displaystyle
T^{\bf{qm}}_{\mu\nu}(\Omega)$ $\displaystyle=$
$\displaystyle\frac{(g_{\mu\nu}\Box{\Omega^{2}}-\nabla_{\mu}\nabla_{\nu}{\Omega^{2}})}{\Omega^{2}}+6\frac{\nabla_{\mu}\Omega\nabla_{\nu}\Omega}{\Omega^{2}}$
(8)
$\displaystyle-3g_{\mu\nu}\frac{\nabla_{\sigma}\Omega\nabla^{\sigma}\Omega}{\Omega^{2}}.$
$\displaystyle
T^{\bf{med}}_{\mu\nu}(\lambda,\rho)=-\frac{\kappa\hbar^{2}}{m^{2}\Omega^{2}}\Biggl{[}\nabla_{(\mu}$
$\displaystyle\sqrt{\rho}\nabla_{\nu)}\Bigl{(}\frac{\lambda}{\sqrt{\rho}}\Bigr{)}$
(9) $\displaystyle-
g_{\mu\nu}\nabla_{\sigma}\Bigl{(}\lambda\frac{\nabla^{\sigma}{\sqrt{\rho}}}{\sqrt{\rho}}\Bigr{)}\Biggr{]}.$

Note that, the resulting Einstein’s equation is composed of stress-energy
tensors related to the matter $T^{\bf{matter}}_{\mu\nu}(S,\rho)$, quantum
$T^{\bf{qm}}_{\mu\nu}(\Omega)$ and mediating field
$T^{\bf{med}}_{\mu\nu}(\lambda,\rho)$ contributions. The vacuum density
$\lambda$ obeys a first order differential equation coupled to $\sqrt{\rho}$ ,
which is given by,

$\displaystyle\lambda=\frac{\hbar^{2}}{m^{2}(1-Q)}\nabla_{\mu}\Bigl{(}\lambda\frac{\nabla^{\mu}\sqrt{\rho}}{\sqrt{\rho}}\Bigr{)}.$
(10)

This $\lambda$ equation is obtained by comparing trace equation given in Eq. 5
with the trace of the tensor equation given in Eq. 6 . It is found that
$\lambda$ term can give additional corrections to standard quantum theory (see
Ref. Joseph (2020, 2021) for more details) .

##  III Alcubierre Warp Drive

Usually Alcubierre metric is studied using Einstein’s General Theory of
Relativity and one is encountered with the problem of the exotic matter
Alcubierre (1994). Later, considerable amount of research works were carried
out in relation to the physical feasibility of the Warp drive solution Van Den
Broeck (1999), its energy requirements Broeck (1999); Santiago  _et al._
(2022). Advacing further, some of the modifications to Alcubierre warp drive
were also suggested Natario (2002); White (2003, 2011). Recently various
matter-energy sources is explored in order to see whether it supports
Alcubierre warp drive metric solution and a relation to Burgers’ equation is
found O.L. Santos-Pereira and Ribeiro (2020, 2021a, 2021b, 2021c).

Here we focus on the more generalized theory of Einstein’s gravity, i. e. the
Bohmian Quantum Gravity which incorporate quantum mechanical matter field
coupling to gravity using conformal factor. In order to explore the warp drive
in the context of Bohmian Quantum Gravity, we use the following assumption
that the background space-time is Alcubierre warp-drive metric which is
coupled to a quantum mechanical scalar matter field
$\phi=\sqrt{\rho}\exp{(\frac{i}{\hbar}S)}$. In Bohmian Quantum Gravity, this
complex scalar matter-field can be coupled to gravity and the total metric of
the system is given by
$g_{\mu\nu}^{\bf{qm+gr}}=\Omega^{2}\,g_{\mu\nu}^{\bf{gr}}$ where $\Omega^{2}$
is the quantum mechanical conformal factor. Here the gravitational background
metric $g_{\mu\nu}^{\bf{gr}}$ is simply represented as ${g}_{\mu\nu}$. In
$(+---)$ signature, Alcubierre metric can be written as,

$\displaystyle ds^{2}$ $\displaystyle=$ $\displaystyle
g_{\mu\nu}dx^{\mu}dx^{\nu}$ (11) $\displaystyle=$
$\displaystyle{\bigl{(}1-v_{s}(t)^{2}f(r_{s}(t)^{2}\bigr{)}}{dt^{2}}$
$\displaystyle+2v_{s}(t)^{2}f(r_{s}(t)){dx}\,{dt}-dx^{2}-dy^{2}-dz^{2},$

where $v_{s}(t)=\frac{dx_{s}(t)}{dt}$ is the warp bubble velocity. While the
metric tensor $g_{\mu\nu}$ with $(+---)$ signature can be written as,

$\displaystyle
g_{\mu\nu}=\begin{pmatrix}1-v_{s}^{2}f(r_{s})^{2}&v_{s}f(r_{s})&0&0\\\
v_{s}f(r_{s})&-1&0&0\\\ 0&0&-1&0\\\ 0&0&0&-1\\\ \end{pmatrix}.$ (12)

The inverse metric tensor $g^{\mu\nu}$ can be evaluated as,

$\displaystyle g^{\mu\nu}=\begin{pmatrix}1&v_{s}f(r_{s})&0&0\\\
v_{s}f(r_{s})&-1+v_{s}^{2}f(r_{s})^{2}&0&0\\\ 0&0&-1&0\\\ 0&0&0&-1\\\
\end{pmatrix}.$ (13)

Here $f(r_{s})$ is termed as the shape function of the warp metric since it
describes the shape of the warp bubble.

$\displaystyle
f(r_{s})=\frac{\tanh{[\sigma(r_{s}+R)]}−\tanh{[\sigma(r_{s}-R)]}}{2\tanh{(\sigma
R)}},$ (14)

where $\sigma$ is inversely related to the thickness of the warp bubble and
$R$ is the warp bubble radius. The variable $r_{s}(t)$ is defined as the
distance from the center of the bubble $[x_{s}(t),0,0]$ to an arbitrary point
$(x,y,z)$ on the surface of the bubble and it is given by,
$r_{s}(t)=\sqrt{(x-x_{s}(t))^{2}+y^{2}+z^{2}}$. Alcubierre already had
mentioned that this shape function can approach a step function as
$\sigma\to\infty$, i.e $|r_{s}(t)|<R$ then $f(r_{s})=1$, whereas for distances
where $|r_{s}(t)|\gg R$ then $f(r_{s})\to 0$. The components for the Eulerian
(normal) observers’ 4-velocities are given by,
$u^{\alpha}=[1,v_{s}(t)f(r_{s}),0,0]$ and $u_{\alpha}=[1,0,0,0]$. Note that
these vectors are considered in $(+---)$ signature. Here also one can obtain,

$\displaystyle\mathcal{G}_{\mu\nu}u^{\mu}u^{\nu}=\frac{-v_{s}^{2}\bigl{(}y^{2}+z^{2}\bigr{)}}{4r_{s}^{2}}\Bigl{(}\frac{df}{dr_{s}}\Bigr{)}^{2}.$
(15)

Using the relation $\mathcal{G}_{\mu\nu}={T}_{\mu\nu}$ (see Eq. 6) the
following expression is obtained,

$\displaystyle{T}_{\mu\nu}u^{\mu}u^{\nu}=-\frac{v_{s}^{2}\bigl{(}y^{2}+z^{2}\bigr{)}}{4r_{s}^{2}}\Bigl{(}\frac{df}{dr_{s}}\Bigr{)}^{2}.$
(16)

Note that this expression is derived using the geometric arguments only.
Alcubierre had started with a warp drive metric and found a condition for the
energy density in order to have a solution that he desires Alcubierre (1994).
Then one needs to look into the proper stress-energy tensor $T_{\mu\nu}$ which
can support the desired warp drive space-time structure. In usual general
relativity one is compelled to accept the requirement of the exotic matter in
order to the get the desired warp drive solution. Warp drive metric is no
longer a solution to Einstein’s General Relativity since it violate the energy
conditions allowed in the theory. Hence one is instructed to look into a more
generalized theory which can easily support the warp drive solution without
much difficulty and Bohmian Quantum Gravity is a good candidate for that.

Since we are taking into account the extended theory of Einstein General
Relativity i.e a Scalar-Tensor Theory which contains an additional scalar
degrees of freedom apart from the Einstein’s gravitational tensor field. Note
that the scalar field is quantum mechanical in origin. There are many
different types of scalar tensor theories but the Bohmian Quantum Gravity
impose a special physical meaning to the scalar field and it is intimately
related to the conformal factor in the theory which is quantum mechanical in
nature. The quantum mechanical conformal factor is getting coupled to gravity.
Once quantum mechanical matter field couples with gravity, one can find the
exact expression for the stress energy tensor $T_{\mu\nu}$ and it contains
three contributions (see Eq. 7, Eq. 8 and Eq. 9). Substituting the expression
of $T_{\mu\nu}$ in the equation, one can find the condition which needs to be
satisfied in the Bohmian Quantum Gravity.

Even-though the space-time is rigid in the Riemannian sense, it is not so in
Weyl sense. In Riemannian geometry, the length of a vector remains constant
and only the orientation changes during parallel transport . While in Weyl
Geometry the length of a vector and orientation changes during parallel
transport.

$\displaystyle\nabla_{\alpha}g_{\mu\nu}=0$ $\displaystyle\implies$ Riemannian
Geometry (17)
$\displaystyle\nabla_{\alpha}g_{\mu\nu}=\mathcal{\sigma}_{\alpha}g_{\mu\nu}$
$\displaystyle\implies$ Weyl Geometry (18)

In Riemannian geometry the covariant derivative of the metric is zero while it
is not true in the Weyl Geometry. Since the length changes during the parallel
transport, the covariant derivative of the metric gives a nonzero
contribution. In Weyl geometry, one can think about different conformal frames
where the metric is different by a conformal scaling but the physics remains
the same. In Bohmian Quantum Gravity frame-work, one can see that the quantum
potential $Q$ appears as the Weyl scalar field $\mathcal{\sigma}$ since
$\nabla_{\alpha}g_{\mu\nu}^{\bf{qm+gr}}=Q_{\alpha}\,g_{\mu\nu}^{\bf{gr+qm}}$
and it is purely a quantum mechanical effect. Parallel transporting a vector
along a Weyl manifold will make a change in the length of the vector and such
a freedom is not there in Riemannian manifold. In other words, Space-time is
rigid in the Riemannian sense but it is not so rigid in Weyl sense, hence
using quantum effects one is able to manipulate space-time structure easily.
This interesting fact is reflected while analyzing the contribution coming
from ${T}_{\mu\nu}u^{\mu}u^{\nu}$ and major contribution is from
$T^{\bf{qm}}_{\mu\nu}(\Omega)u^{\mu}u^{\nu}$. Note that the inverse
gravitational constant $1/{\kappa}$ appearing as a term in front of the usual
expression for the exotic matter is not present while considering
$T^{\bf{qm}}_{\mu\nu}(\Omega)u^{\mu}u^{\nu}$ term. Since we adopt the Weyl
Geometry, it can be seen that the Weyl length change is associated to
conformal factor $\Omega^{2}$ which is purely quantum mechanical in origin.
Hence quantum mechanical contribution can make space-time manipulation much
easier than the usual gravitational bending of space-time.

From our previous studies Gabay and Joseph (2018a); Joseph (2020, 2021), it is
found that there is a dynamical cosmological term which appears along with the
$g_{\mu\nu}$ term. The dynamical cosmological term is written in terms of the
quantum potential $Q$ and Lagrange multiplier $\lambda$. Hence, focusing on
$T^{\bf{qm}}_{\mu\nu}(\Omega)u^{\mu}u^{\nu}$ term’s $g_{\mu\nu}$ part and
ignoring other contributions (they are smaller due to the presence of
$\kappa$), one is lead to

$\displaystyle{T}_{\mu\nu}u^{\mu}u^{\nu}$ $\displaystyle\approx$
$\displaystyle T^{\bf{qm}}_{\mu\nu}(\Omega)u^{\mu}u^{\nu}$
$\displaystyle{T}_{\mu\nu}u^{\mu}u^{\nu}$ $\displaystyle\approx$
$\displaystyle\frac{\Box{\Omega^{2}}-3{\nabla_{\sigma}\Omega\nabla^{\sigma}\Omega}}{\Omega^{2}}g_{\mu\nu}u^{\mu}u^{\nu}$

Since $g_{\mu\nu}u^{\mu}u^{\nu}=1$ in $(+---)$ signature, one can obtain,

$\displaystyle{T}_{\mu\nu}u^{\mu}u^{\nu}\approx\frac{\Box{\Omega^{2}}-3{\nabla_{\sigma}\Omega\nabla^{\sigma}\Omega}}{\Omega^{2}}.$
(20)

This is the result from Bohmian Quantum Gravity and combining this with our
previous expression for the exotic matter, one can get,

$\displaystyle\frac{\Box{\Omega^{2}}-3{\nabla_{\sigma}\Omega\nabla^{\sigma}\Omega}}{\Omega^{2}}=-\frac{v_{s}^{2}\bigl{(}y^{2}+z^{2}\bigr{)}}{4r_{s}^{2}}\Bigl{(}\frac{df}{dr_{s}}\Bigr{)}^{2}$
(21)

Note that, while establishing Eq.22, one is utilizing more general
gravitational theory. Rearranging the terms, one is lead to a Klein-Gordon
type wave equation in terms of the conformal factor $\Omega^{2}$, i.e

$\displaystyle{\Box{\Omega^{2}}-3{\nabla_{\sigma}\Omega\nabla^{\sigma}\Omega}}+\frac{v_{s}^{2}\bigl{(}y^{2}+z^{2}\bigr{)}}{4r_{s}^{2}}\Bigl{(}\frac{df}{dr_{s}}\Bigr{)}^{2}{\Omega^{2}}=0$
(22)

Let us recall the expression of exotic matter as Alcubierre exotic function
$\mbox{Alc}(x,y,z)$ and it is given by
$\mbox{Alc}(x,y,z)=\frac{v_{s}^{2}\bigl{(}y^{2}+z^{2}\bigr{)}}{4r_{s}^{2}}\Bigl{(}\frac{df}{dr_{s}}\Bigr{)}^{2}$,
then Eq. 22 becomes,

$\displaystyle{\Box{\Omega^{2}}-3{\nabla_{\sigma}\Omega\nabla^{\sigma}\Omega}}+\mbox{Alc}(x,y,z)\,{\Omega^{2}}=0$
(23)

Here the Alcubierre exotic function appear like the positive mass of the
conformal wave equation. Note that, the conformal wave equation is purely a
quantum mechanical feature, since $\Omega^{2}$ is intimately related to the
quantum potential $Q$ which in turn related to the square root of the quantum
mechanical matter wave density. The constraint equation indicates that

$\displaystyle\Omega^{2}=\exp{\Bigl{(}\frac{\hbar^{2}}{m^{2}}\frac{\Box{\sqrt{\rho}}}{\sqrt{\rho}}\Bigr{)}}=\exp{(Q)}.$
(24)

Note that $\Omega^{2}$ has a double property, in one had, it can be written as
a purely a quantum mechanical quantity and on the other hand it has a definite
geometrical meaning as a conformal factor which can be written in terms of a
Weyl scalar field. Substituting the expression of $\Omega^{2}$ in Eq. 23, one
can write the equation in terms of the quantum potential $Q$. Hence the
equation becomes,

$\displaystyle{\Box{Q}+\frac{1}{4}{\nabla_{\sigma}Q\nabla^{\sigma}Q}}+\mbox{Alc}(x,y,z)=0$
(25)

Substituting the expression for $Q$ in terms of the quantum mechanical matter
wave density, i.e using the following relation,

$\displaystyle
Q=\frac{\hbar^{2}}{m^{2}}{\Bigl{(}\frac{\Box{\sqrt{\rho}}}{\sqrt{\rho}}\Bigr{)}}.$
(26)

One can get,

$\displaystyle\frac{\hbar^{2}}{m^{2}}\Box{{\Bigl{(}\frac{\Box{\sqrt{\rho}}}{\sqrt{\rho}}\Bigr{)}}}-\frac{1}{4}\frac{\hbar^{4}}{m^{4}}{\nabla_{\sigma}{\Bigl{(}\frac{\Box{\sqrt{\rho}}}{\sqrt{\rho}}\Bigr{)}}\nabla^{\sigma}{\Bigl{(}\frac{\Box{\sqrt{\rho}}}{\sqrt{\rho}}\Bigr{)}}}$
$\displaystyle+\mbox{Alc}(x,y,z)=0$ (27)

Ignoring the higher order terms i.e $O(\hbar^{4})$ terms, one can obtain,

$\displaystyle\Box{{\Bigl{(}\frac{\Box{\sqrt{\rho}}}{\sqrt{\rho}}\Bigr{)}}}+\frac{m^{2}}{\hbar^{2}}\mbox{Alc}(x,y,z)=0$
(28)

Laplace-Beltrami operator on a curved space-time is given by,

$\displaystyle\Box{\sqrt{\rho}}=\frac{1}{\sqrt{-g}}\partial_{\mu}\Bigl{(}\sqrt{-g}\,g^{\mu\nu}\partial_{\nu}{\sqrt{\rho}}\Bigr{)}.$
(29)

Since $\sqrt{-g}=1$ (for Alcubierre metric ), in our context, the fourth order
contribution $\Box{{\Bigl{(}\frac{\Box{\sqrt{\rho}}}{\sqrt{\rho}}\Bigr{)}}}$
becomes,

$\displaystyle\Box{{\Bigl{(}\frac{\Box{\sqrt{\rho}}}{\sqrt{\rho}}\Bigr{)}}}=\partial_{\alpha}\Bigl{(}g^{\alpha\beta}\partial_{\beta}\Bigl{(}\frac{\partial_{\mu}\bigl{(}g^{\mu\nu}\partial_{\nu}{\sqrt{\rho}}\bigr{)}}{\sqrt{\rho}}\Bigr{)}\Bigr{)}.$
(30)

Thus Eq. 28 becomes,

$\displaystyle\partial_{\alpha}\Bigl{(}g^{\alpha\beta}\partial_{\beta}\Bigl{(}\frac{\partial_{\mu}\bigl{(}g^{\mu\nu}\partial_{\nu}{\sqrt{\rho}}\bigr{)}}{\sqrt{\rho}}\Bigr{)}\Bigr{)}+\frac{m^{2}}{\hbar^{2}}\mbox{Alc}(x,y,z)=0$

Expanding this equation in terms of the components of the metric tensor (given
in Eq.12), one is lead to the expression containing the fourth order space-
time derivative of $\sqrt{\rho}$ with other terms involving the Alcubierre
shape function $f(r_{s})$ and the velocity of the warp bubble $v_{s}$.

It is difficult to find the analytical solutions of these kinds of fourth
order differential equations but one can take very simplified toy versions of
the wave equation in order to have an idea of the new physics emerging out
from the equation presented here. The main achievement we have made in Eq. III
is mapping the problem of the exotic matter into finding a suitable quantum
density for the matter field as a solution to the fourth order partial
differential equation on curved space-time. If the square root of the quantum
density ($\sqrt{\rho}$) satisfy the wave equation given in Eq. III, it is
equivalent to having an exotic matter in usual general relativity. Thus, one
needs to expand the idea of having exotic matter into the determination of
proper quantum mechanical density. Hence the gravitational problem is mapped
into a purely quantum mechanical problem. In the Bohmian Quantum Gravity
sense, these quantum mechanical density will result into a conformal wave
equation.

Now let us assume a simple fourth order wave equation where the space-time is
flat and the quantum density is confined along the $x$-direction and instead
of $\mbox{Alc}(x,y,z)$, we have just a constant $\beta^{4}$. Hence we can
present a toy equation as follows,

$\displaystyle\partial_{t}^{4}\sqrt{\rho(t,x)}-\partial_{x}^{4}\sqrt{\rho(t,x)}+\beta^{4}\sqrt{\rho(t,x)}=0$
(32)

By the method of separation of variables, it is possible to find interesting
solutions to the quantum density. Apart from the usual trigonometric
functions, hyperbolic functions also appear as the solutions which is not
allowed in usual quantum theory, since the wave-equation is only second order.
But for this toy equation, one can see that
$\sqrt{\rho(t)}=c_{1}\cos(\gamma\,t)+c_{2}\sin(\gamma\,t)+c_{3}\cosh(\gamma\,t)+c_{4}\sinh(\gamma\,t)$,
where $c_{1},c_{2},c_{3},c_{4}$ and $\gamma$ are constants. Similarly one can
solve the spatial part of the quantum density i.e,
$\sqrt{\rho(x)}=d_{1}\cos(\delta\,x)+d_{2}\sin(\delta\,x)+d_{3}\cosh(\delta\,x)+d_{4}\sinh(\delta\,x)$,
where $d_{1},d_{2},d_{3},d_{4}$ and $\delta=\sqrt[4]{\beta^{4}+\gamma^{4}}$
are constants. The total quantum density is given by
$\sqrt{\rho(t,x)}=\sqrt{\rho(t)}\sqrt{\rho(x)}$. Hence the final solution
consists of the product of trigonometric and hyperbolic functions. The
presence of the hyperbolic terms arises from the fourth order derivative of
the toy equation and these are extra solutions only appear from the conformal
waves appearing in the Bohmian quantum gravity. Trignometric solutions are
already there in usual quantum theory but the hyperbolic solutions might be
bringing the new physics here, due to the fact that they are the extra
solutions appearing in the theory. Exotic matter that we perceive in usual
General Relativity is a simple effect arises from the complicated conformal
wave equations presented here (see Eq. III).

##  IV Conclusions

We have analyzed the Alcubierre warp drive in the Bohmian Quantum Gravity
context. The exotic matter problem is mapped into a 4th order quantum
mechanical density equation involving Alcubeirre shape function. It is found
that the fourth order wave equation in space-time can contribute to extra
solutions of quantum density which are usually not present in the quantum
theory since usual quantum theory is second order in nature. We have taken a
simple toy model of the partial differential equation and found that
hyperbolic functions of quantum density can appear which may contribute to the
new physics appearing in the theory. If one can find a viable distribution of
quantum mechanical density which obeys the wave equation given in Eq. III, we
will resolve our problem of exotic matter for Alcubierre warp drive in Bohmian
Quantum Gravity frame-work. The exact solution of quantum density can be
evaluated in further research works.

## References

  * Capozziello and Faraoni (2011) S. Capozziello and V. Faraoni,  _Beyond Einstein Gravity_ , first edition ed. (Springer Netherlands, Dordrecht, Holland, 2011).
  * Bergmann (1968) P. G. Bergmann, Int. J. Theor. Phys. 1, 25 (1968).
  * Deruelle  _et al._ (2010) N. Deruelle, M. Sasaki, Y. Sendouda, and D. Yamauchi, Progress. Theor. Phys. 123, 169 (2010).
  * Shin’ichi and Odintsov (2007) N. Shin’ichi and S. D. Odintsov, International Journal of Geometric Methods in Modern Physics 04, 115 (2007).
  * Atazadeh  _et al._ (2009) K. Atazadeh, A. Khaleghi, H. R. Sepangi, and Y. Tavakoli, Int. J. Mod. Phys. D 18, 1101 (2009).
  * Harko  _et al._ (2011) T. Harko, F. S. N. Lobo, S. Nojiri, and S. D. Odintsov, Phys. Rev. D 84, 024020 (2011).
  * Capozziello  _et al._ (2006) S. Capozziello, S. Nojiri, and S. Odintsov, Phys. Lett. B 634, 93 (2006).
  * Oikonomou and Karagiannakis (2014) V. Oikonomou and N. Karagiannakis, Astrophys Space Sci 354, 583 (2014).
  * Capozziello and de Laurentis (2011) S. Capozziello and M. de Laurentis, Physics Reports 509, 167 (2011).
  * Ntahompagaze  _et al._ (2017) J. Ntahompagaze, A. Abebe, and M. Mbonye, Int. J. Geom. Methods Mod. Phys. 14, 1750107 (2017).
  * Scholz (2017) E. Scholz, (2017), arXiv:math.HO/1703.03187.
  * Shojai and Golshani (1998) F. Shojai and M. Golshani, Int. J. Mod. Phys. A 13, 677 (1998).
  * Bohm and Hiley (1975) D. J. Bohm and B. J. Hiley, Found. Phys. 5, 93 (1975).
  * Bohm (1952a) D. Bohm, Phys. Rev. 85, 166 (1952a).
  * Bohm (1952b) D. Bohm, Phys. Rev. 85, 180 (1952b).
  * Ashtekar and Pullin (2017) A. Ashtekar and J. Pullin,  _Loop Quantum Gravity_ (World Scientific, 2017).
  * Rovelli and Vidotto (2014) C. Rovelli and F. Vidotto,  _Covariant Loop Quantum Gravity_ (Cambridge University Press, 2014).
  * Shojai and Shojai (2000) F. Shojai and A. Shojai, Int. J. Mod. Phys. A 15, 1859 (2000), gr-qc/0010012 .
  * Shojai (1999) F. Shojai, Phys. Rev. D 60, 124001 (1999).
  * Gabay and Joseph (2018a) D. Gabay and S. K. Joseph, (2018a), arXiv:gr-qc/1801.00161.
  * Joseph (2020) S. K. Joseph, arXiv e-prints , arXiv:2005.03996 (2020), arXiv:2005.03996 [physics.gen-ph] .
  * Joseph (2021) S. K. Joseph, arXiv e-prints , arXiv:2112.12964 (2021), arXiv:2112.12964 [gr-qc] .
  * Gabay and Joseph (2018b) D. Gabay and S. K. Joseph, (2018b), arXiv:gr-qc/1802.07678.
  * Alcubierre (1994) M. Alcubierre, Class. Quantum Gravity 11, L73 (1994).
  * Van Den Broeck (1999) C. Van Den Broeck, arXiv e-prints , gr-qc/9906050 (1999), arXiv:gr-qc/9906050 [gr-qc] .
  * Broeck (1999) C. V. D. Broeck, Class. Quant. Grav. 16 (1999).
  * Santiago  _et al._ (2022) J. Santiago, S. Schuster, and M. Visser, Phys. Rev. D 105, 064038 (2022).
  * Natario (2002) J. Natario, Class. Quant. Grav. 19, 1157 (2002).
  * White (2003) H. White, Gen. Relat. Grav. 35, 2025 (2003).
  * White (2011) H. White, J. Br. Interplanet. Soc. 66, 242 (2011).
  * O.L. Santos-Pereira and Ribeiro (2020) E. A. O.L. Santos-Pereira and M. Ribeiro, Eur. Phys. J. Plus 80, 786 (2020).
  * O.L. Santos-Pereira and Ribeiro (2021a) E. A. O.L. Santos-Pereira and M. Ribeiro, Gen. Relativ. Gravit 53, 23 (2021a).
  * O.L. Santos-Pereira and Ribeiro (2021b) E. A. O.L. Santos-Pereira and M. Ribeiro, Eur. Phys. J. Plus 136, 902 (2021b).
  * O.L. Santos-Pereira and Ribeiro (2021c) E. A. O.L. Santos-Pereira and M. Ribeiro, Eur. Phys. J. C 81, 133 (2021c).


# GCNH: A Simple Method For Representation Learning On Heterophilous Graphs

Andrea Cavallo12, Claas Grohnfeldt2, Michele Russo2, Giulio Lovisotto2 and
Luca Vassio1  Politecnico di Torino1, Huawei Munich Research Center2
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Graph Neural Networks (GNNs) are well-suited for learning on homophilous
graphs, i.e., graphs in which edges tend to connect nodes of the same type.
Yet, achievement of consistent GNN performance on heterophilous graphs remains
an open research problem. Recent works have proposed extensions to standard
GNN architectures to improve performance on heterophilous graphs, trading off
model simplicity for prediction accuracy. However, these models fail to
capture basic graph properties, such as neighborhood label distribution, which
are fundamental for learning.

In this work, we propose GCN for Heterophily (GCNH), a simple yet effective
GNN architecture applicable to both heterophilous and homophilous scenarios.
GCNH learns and combines separate representations for a node and its
neighbors, using one learned importance coefficient per layer to balance the
contributions of center nodes and neighborhoods. We conduct extensive
experiments on eight real-world graphs and a set of synthetic graphs with
varying degrees of heterophily to demonstrate how the design choices for GCNH
lead to a sizable improvement over a vanilla GCN. Moreover, GCNH outperforms
state-of-the-art models of much higher complexity on four out of eight
benchmarks, while producing comparable results on the remaining datasets.
Finally, we discuss and analyze the lower complexity of GCNH, which results in
fewer trainable parameters and faster training times than other methods, and
show how GCNH mitigates the oversmoothing problem.

###### Index Terms:

Graph Neural Networks, heterophily, disassortativity, graph representation
learning

##  I Introduction

GNNs are core components of current state-of-the-art methods for learning and
prediction on graph-structured data across domains and applications. Their
capability to encode semantic and contextual information into node embeddings
is known to be particularly effective on homophilous graphs, i.e., graphs in
which nodes of the same type tend to be connected [1, 2]. On the other hand,
in the case of heterophilous graphs, in which neighboring nodes tend to be
dissimilar in type, the achievement of competitive, or at least consistent,
GNN prediction accuracy remains an open research goal [3, 4].

Among other explanations for the inconsistent GNN performance in the
heterophilous case, [5] suggests that the message aggregation strategies of
standard GNNs could lead to weakly representative node embeddings, due to a
disproportionately high contribution of dissimilar neighbors. That is why some
works attempt to improve the generalization capability of GNNs to
heterophilous networks by either modifying the graph structure or tailoring
aggregation strategies and network architecture for such scenario [15, 3, 4,
7, 6, 18, 8, 16, 12, 13, 9, 11, 17, 10, 14]. Nevertheless, [19] shows that a
vanilla Graph Convolutional Network (GCN) can still outperform more complex
(heterophilous) models on some heterophilous graphs. [19] and [20] suggest
that this contradiction originates from the fact that the edge homophily ratio
should not be considered a representative indicator of GCN performance, and
instead recommend taking into account neighborhood structure and distribution
of node labels.

Based on these observations, we propose a simple yet effective GNN
architecture, namely GCN for Heterophily (GCNH), to improve node
representation capabilities for applications on heterophilous graphs.
Differently from other GNNs, GCNH learns two different functions that encode a
node and its neighbors separately. In addition, we allow the GCNH layer to
flexibly assign different relevance to the information present in the
neighborhood versus the information present in the center node. We discuss and
show how this design mitigates noisy neighborhood representations from
negatively influencing the learned embeddings while allowing informative
neighbors to strongly influence the final node embedding. These extensions
make GCNH more adaptive to heterophily than a vanilla GCN, while also
improving prediction accuracy over more complex models designed for
heterophily on common benchmarks.

We evaluate GCNH on the task of node classification using eight common real-
world datasets and one set of synthetic graphs with varying degrees of
heterophily. We show that GCNH is able to learn meaningful representations of
nodes independently of the homophily level of the graph, achieving new state-
of-the-art performance on heterophilous graph datasets while producing results
comparable to the state-of-the-art on homophilous benchmarks.

Our main contributions are summarized below.

  * •

We present GCNH, a simple yet effective GNN architecture that improves graph
representation learning capabilities on heterophilous graphs while preserving
the advantages of GCN.

  * •

We present extensive experiments on real and synthetic datasets with varying
degrees of heterophily for the node classification task. GCNH improves over
the state-of-the-art on four (out of eight) real-world benchmarks while
performing comparably to the state-of-the-art on all other datasets, including
homophilous graphs.

  * •

We showcase the lower complexity of GCNH compared to other state-of-the-art
models, both in terms of the training time and the number of trainable
parameters, and how it mitigates the oversmoothing problem.

##  II Related work

The analysis and improvement of GNN performance on heterophilous graphs have
received increasing attention in recent years [15, 3, 4, 7, 6, 18, 8, 16, 12,
13, 9, 11, 17, 10, 14]. GNNs generate node embeddings in two steps: message
transformation, where node messages, i.e., features or embeddings from the
previous layer, are transformed, and message aggregation, where the final node
embeddings are generated by aggregating the messages of neighbors in the
graph. One of the earliest and today most common GNN models is the GCN [1],
which defines message transformation as a learnable linear layer and message
aggregation as the average of the messages from the neighbors and from the
center node.

Several works have proposed new GNN architectures or graph transformations to
make the message-passing framework suitable for applications on non-
homophilous graphs. We compare a number of these approaches to our method in
Section V. Borrowing the categorization introduced in [5], these approaches
can be subdivided as follows.

###  II-A Non-Local Neighbor Extension

These methods selectively extend the receptive field of GNNs to include
potentially important nodes located outside of the local neighborhood. These
approaches are based on the assumption that neighboring nodes may be
dissimilar and that information about the target node, presumably carried by
nodes with the same label, is available in nodes belonging to higher-order
neighborhoods. In particular, methods such as [15, 3, 4, 7] create latent
representations for nodes using multiple neighborhoods at different hop
distances and combine them into one overall embedding. Other approaches, such
as [6, 18, 8, 16], do not consider entire neighborhoods but single nodes as
potential neighbors, regardless of their location in the graph, and aggregate
messages from the nodes that are estimated to be more relevant.

###  II-B GNN Architecture Adaptation

Methods in this category modify the GNN architecture with the goal of
improving representation learning capabilities on heterophilous graphs. A
common approach is to estimate the relevance of a node to a given target node
with respect to the prediction task at hand, and to assign individual weights
to messages from neighbors based on their relevance. This approach is used in
[12, 13, 9, 11, 17] among the others. Another approach is to learn separate
embeddings for the neighborhood and the target node and merge them at a later
stage. This mitigates the phenomenon of noisy embeddings, where information
from potentially highly dissimilar neighbors is mixed with the features of the
target node. Methods that follow this approach include [3, 18]. In addition,
[3, 10, 14] adopt the strategy of treating the information captured by
different GNN layers separately, instead of first aggregating the information
from all layers and then using the final node embeddings for prediction.

##  III Preliminaries

###  III-A Notation And Problem Statement

Let $G=(V,E)$ be an unweighted and undirected graph, where $V$ is the set of
nodes and $E$ is the set of edges. The connectivity information in the graph
is represented by the adjacency matrix $A\in\mathbb{R}^{n\times n}$, where
$n=|V|$ is the number of nodes and matrix elements $A_{uv}$ are equal to 1 if
nodes $u$ and $v$ are adjacent and 0 otherwise. Each node is associated with a
feature vector $x_{u}$ of size $f$, and the complete set of features in the
graph is denoted by $X\in\mathbb{R}^{n\times f}$. The neighbors of a node $u$
are the set of nodes adjacent to it, denoted by $\mathcal{N}_{u}$. Note that
$\mathcal{N}_{u}$ does not include node $u$.

The task addressed in this work is supervised node classification. In this
scenario, each node is associated with a label $y_{u}\in C$ representing the
class the node belongs to, where $C$ is the set of labels. The task
corresponds to learning a mapping $\mathcal{F}:V\rightarrow C$ that uses the
information of the graph $G$, the features $X$ and the labels to map nodes
into their ground-truth class. As is standard practice, we add a linear layer
that maps the final node representations of the last network layer
$H^{L}\in\mathbb{R}^{n\times e^{L}}$ (with $L$ total number of layers and
$e^{L}$ size of the final node embeddings) to class probabilities with the
addition of a softmax. For a node $u$:

$\tilde{y}_{u}=\text{softmax}(h_{u}^{L}W_{cl}),$ (1)

where $W_{cl}\in\mathbb{R}^{e^{L}\times|C|}$ is a learnable matrix. We omit
the bias term from the equation for simplicity. Note that
$\tilde{y}_{u}\in\mathbb{R}^{|C|}$ is the probability distribution over
classes for node $u$. During inference, networks assign to the node the class
with maximum probability:

$\hat{y}_{u}=\text{argmax}(\tilde{y}_{u}).$ (2)

To train the model, we minimize the negative log-likelihood loss on the
training data $\mathcal{L}(y_{u},\hat{y_{u}})$, where
$\hat{y_{u}}=\mathcal{F}(G,X,u)$ is the predicted label for node $u$. The loss
function $\mathcal{L}(\cdot,\cdot)$ describes the distance between the true
label $y_{u}$ and the predicted label. We focus on the transductive case: we
work on single-graph and separate nodes into training, validation and test
set.

###  III-B Homophily And Heterophily

Graph homophily is a social science-inspired property of graphs [21], defined
as the extent to which similar nodes in a graph are connected. Although other
definitions of node similarity exist [17, 19, 20], this work focuses on label
similarity, i.e., we define nodes as similar if they share the same label, and
we measure graph homophily using the standard edge homophily ratio, denoted by
$h$:

$h=\frac{|\\{(u,v):(u,v)\in E\land y_{u}=y_{v}\\}|}{|E|},$ (3)

which quantifies the fraction of edges in a graph that connect nodes with the
same label. Graphs with low values of h are called heterophilous or
disassortative. As discussed in Section I, GNNs perform inconsistently on this
category of graphs – we analyze this point in depth in Section V.

Figure 1: Architecture of the GCNH layer. To create an updated representation
for the center node (red), the GCNH layer explicitly separates the node from
its 1-hop neighborhood (blue). Two different MLPs encode center node and
neighborhood separately ($\text{{mlp}}_{u}$ and
$\text{{mlp}}_{\mathcal{N}_{u}}$, respectively). The encoded neighbors are
then aggregated with a permutation invariant function $\bigoplus$. Finally,
the aggregated neighborhood and the encoded center node are combined together
with a learnable weighting factor $\beta$ which regulates the contributions of
the center node versus its neighborhood to produce the final output embedding
for the node.

##  IV Method

In this section, we describe the architecture of the model proposed in this
paper, namely GCNH. Figure 1 illustrates the structure of the GCNH layer.

###  IV-A GCNH Layer Formulation

A GCNH network is composed of one or more, $L$, GCNH layers. The
$\ell^{\text{th}}$ layer receives in input the adjacency matrix and the node
representations computed at the previous layer $H^{\ell-1}$ and produces
updated node representations $H^{\ell}$. We set $H^{0}=X$.

Within a layer, node representations are transformed through two separate
1-layer MLPs, $\text{{mlp}}_{u}$ and $\text{{mlp}}_{\mathcal{N}_{u}}$,
resulting in latent representations $z_{u}$ and $z_{\mathcal{N}_{u}}$ of the
target node and its neighborhood, respectively. For a node $u$, at layer
$\ell$, we formally describe this step as follows. First, an intermediate
representation is computed for the node $u$:

$z_{u}^{\ell}=\text{{mlp}}_{u}(h_{u}^{\ell-1})=\sigma(h_{u}^{\ell-1}W_{1}).$
(4)

Secondly, all the representations of $u$’s neighbors ($v\in\mathcal{N}_{u}$)
are updated based on their current representations $h_{v}$ and aggregated
together to obtain a neighborhood representation:

$z_{\mathcal{N}_{u}}^{\ell}=\bigoplus_{v\in\mathcal{N}_{u}}(\text{{mlp}}_{\mathcal{N}_{u}}(h_{v}^{\ell-1}))=\bigoplus_{v\in\mathcal{N}_{u}}(\sigma(h_{v}^{\ell-1}W_{2})).$
(5)

In Equations 4 and 5, $W_{1},W_{2}\in\mathbb{R}^{e^{\ell-1}\times e^{\ell}}$
are learnable matrices, $\sigma(\cdot)$ is a generic activation function,
$e^{\ell}$ is the size of the embeddings created at the $\ell$-th layer and
$\bigoplus$ is a permutation invariant aggregation function over the nodes
$v\in\mathcal{N}_{u}$. We omit the bias terms of the MLPs in the equations for
clarity. The final output embedding for node $u$ is obtained as a linear
combination of $z_{u}^{\ell}$ and $z_{\mathcal{N}_{u}}^{\ell}$, parametrized
by a learnable scalar value $\beta$:

$h_{u}^{\ell}=(1-\beta)z_{\mathcal{N}_{u}}^{\ell}+\beta z_{u}^{\ell}$ (6)

where $\beta$ is normalized between 0 and 1 with a sigmoid$(\cdot)$ function.
Note that the MLPs, $\bigoplus$ and $\beta$ are different for each layer
$\ell$. We omit superscripts in the equations for clarity.

Benchmark | Cornell | Texas | Wisconsin | Film | Chameleon | Squirrel | Cora | Citeseer
---|---|---|---|---|---|---|---|---
$h$ | 0.30 | 0.11 | 0.21 | 0.22 | 0.23 | 0.22 | 0.81 | 0.74
MLP |  81.89$\pm$6.40 |  80.81$\pm$4.75 |  85.29$\pm$3.31 |  36.53$\pm$0.70 |  46.21$\pm$2.99 |  28.77$\pm$1.56 |  75.69$\pm$2.00 |  74.02$\pm$1.90
GCN |  60.54$\pm$5.30 |  55.14$\pm$5.16 |  51.76$\pm$3.06 |  27.32$\pm$1.10 |  64.82$\pm$2.24 |  53.43$\pm$2.01 |  86.98$\pm$1.27 |  76.50$\pm$1.36
GAT |  61.89$\pm$5.05 |  52.16$\pm$6.63 |  49.41$\pm$4.09 |  27.44$\pm$0.89 |  60.26$\pm$2.50 |  40.72$\pm$1.55 |  87.30$\pm$1.10 |  76.55$\pm$1.23
Geom-GCN |  60.54$\pm$3.67 |  66.76$\pm$2.72 |  64.51$\pm$3.66 |  31.59$\pm$1.15 |  60.00$\pm$2.81 |  43.80$\pm$1.48 |  85.35$\pm$1.57 | 78.02$\pm$1.15
H2GCN |  82.70$\pm$5.28 |  84.86$\pm$7.23 | 87.65$\pm$4.98 |  35.70$\pm$1.00 |  60.11$\pm$2.15 |  36.48$\pm$1.86 | 87.87$\pm$1.20 |  77.11$\pm$1.57
GPRGNN |  80.27$\pm$8.11 |  78.38$\pm$4.36 |  82.94$\pm$4.21 |  34.63$\pm$1.22 |  46.58$\pm$1.71 |  31.61$\pm$1.24 | 87.95$\pm$1.18 | 77.13$\pm$1.67
GGCN | 85.68$\pm$6.63 | 84.86$\pm$4.55 |  86.86$\pm$3.29 | 37.54$\pm$1.56 | 71.14$\pm$1.84 | 55.17$\pm$1.58 | 87.95$\pm$1.05 | 77.14$\pm$1.45
O(d)-SD | 84.86$\pm$4.71 | 85.95$\pm$5.51 | 89.41$\pm$4.74 | 37.81$\pm$1.15 | 68.04$\pm$1.58 | 56.34$\pm$1.32 |  86.90$\pm$1.13 |  76.70$\pm$1.57
GCNH | 86.49$\pm$6.98 | 87.84$\pm$3.87 | 87.65$\pm$3.59 | 36.89$\pm$1.50 | 71.56$\pm$1.86 | 61.85$\pm$1.54 |  86.88$\pm$1.04 |  75.81$\pm$1.14
TABLE I: Mean classification accuracy and standard deviation for GCNH on real-
world datasets, on the 10 splits taken from [6]. Best results are in red,
second best results in blue and third best in violet. The results for the
baselines are taken from [12] and [13]. We use sum as the aggregation function
in GCNH; other parameters of GCNH are selected from the best-performing
configuration (see Table VI in the Appendix for details on the
hyperparameters).

###  IV-B GCNH Design Choices

GCNH introduces two main design choices which differentiate it from a standard
GCN: (i) the separate encoding of the target node and its neighbors (Equations
4, 5) and (ii) the explicit parameterization of the contributions of
neighborhood and center node with $\beta$ (Equation 6).

The positive impact of separately processing the node and its neighborhood has
been previously outlined in [3, 18]. Intuitively, in homophilous settings,
where neighbors are similar, aggregation from the neighborhood brings useful
information. On the other hand, in heterophilous graphs, dissimilar neighbors
might bring detrimental information that a GNN cannot easily ignore. Compared
to [3], GCNH takes the separation principle further, while minimizing the
amount of complexity that this choice adds to the network architecture.
Specifically, three choices distinguish GCNH from the model proposed in [3]:
(i) we only use 1-hop neighborhoods, (ii) we learn separate MLPs for center
node and neighborhood and (iii) we combine separate embeddings using a learned
linear combination instead of concatenation. Note that (i) leads to faster
computation while retaining most of the information useful for node
representation, as shown in Section V, (ii) improves flexibility and (iii)
leads to models with fewer parameters. (i) and (iii) lead to lower time
complexity compared to [3] (see Section IV-C for a time complexity analysis).

Combined with the embedding separation, the explicit modeling of the
importance of the neighborhood informativeness with the coefficient $\beta$ in
GCNH allows to adaptively determine the impact of the neighborhood on the
final node embeddings based on how informative the neighbors are. Note that
informative neighbors might also exist in heterophilous graphs [19, 20];
therefore, the contribution of neighbors is not necessarily related to the
homophily level of the network. Intuitively, modeling and learning $\beta$
explicitly provides a helpful inductive bias that allows the network to
directly prefer the center node versus neighborhood information. Section V
shows how models that are equipped with similar, or better, flexibility (such
as GAT [2]) perform poorly in comparison [22].

###  IV-C Time Complexity

We compute the time complexity of a generic GCNH layer $\ell$ by analyzing the
individual processing steps of the model.

First, the node representations $H^{\ell-1}$ are transformed, separately for
the center node and the neighbors, as described in Equations (4) and (5). This
step has a time complexity of $\mathcal{O}\left(ne^{\ell-1}e^{\ell}\right)$.
Subsequently, the neighbors’ representations are aggregated and merged with
the center-node embedding according to Equation (6). All the neighbor
aggregation functions tested (see Section V-F) have a time complexity of
$\mathcal{O}\left(|E|e^{\ell}\right)$, whereas the weighted sum with the self-
node representation has a time complexity of
$\mathcal{O}\left(ne^{\ell}\right)$. This last term is dominated by the
complexity of the transformation. In total, the overall time complexity of the
GCNH layer is $\mathcal{O}\left(ne^{\ell-1}e^{\ell}+|E|e^{\ell}\right)$. The
linear dependency of the complexity of the GCNH layer on the number of nodes
$n$ makes it easier to scale on large graphs compared to attention-based
models (e.g., GGCN [12]), whose complexity depends quadratically on $n$.

##  V Experiments

In this section, we analyze the learning capability of GCNH on the task of
supervised node classification, commonly used for models dealing with
heterophilous graphs. We perform the evaluation both on synthetic datasets
with different levels of homophily ratio and on the real-world graphs widely
used in related works. Further information about the datasets is reported in
Appendix A.

###  V-A Baselines

The baselines used for comparison belong to two main categories. The first
category includes well-known methods:

  * •

MLP: Multi-Layer Perceptron.

  * •

GCN [1]: Graph Convolutional Network.

  * •

GAT [2]: Graph Attention Network.

Methods in the second category, instead, are specifically designed for
heterophilous graphs. In particular:

  * •

Geom-GCN [6] maps nodes to a latent space and defines a new graph based on
embedding similarity.

  * •

H2GCN [3] introduces three specific designs to boost performance on
heterophilous graphs: ego and neighbor-embedding separation, higher-order
neighborhoods and combination of intermediate representations.

  * •

GPRGNN [14] uses PageRank to determine relations between nodes.

  * •

GGCN [12] applies two designs to extend GNNs: degree correction and signed
messages.

  * •

O(d)-SD [13] is based on sheaf diffusion.

###  V-B Experimental Setting

We evaluate model performance in terms of classification accuracy, i.e., the
percentage of nodes in the test set that are assigned to the correct class. We
test different values for hyperparameters and we select the best ones. We
report further information about the grids for the hyperparameters in Appendix
B. The aggregation function $\bigoplus$ in Equation (5) is an element-wise sum
unless differently specified (see Section V-F for a comparison of aggregation
functions). We compute classification accuracies on 10 different
train/validation/test splits provided by [6] for each dataset, and we report
mean and standard deviation. The sizes of the splits are 48%/32%/20%. For each
dataset, we train the models on the training sets and the model performing
best on average across the validation sets is used on the test sets, on which
we compute the accuracy values.

We run experiments on an NVIDIA Tesla V100 PCIE with 16 GB, except for the
experiments in Table IV that we run on an NVIDIA Tesla T4. The code is
implemented in Python and PyTorch is used for deep learning models. Our code
is available at https://github.com/SmartData-Polito/GCNH.

###  V-C Results On Real-World Datasets

Table I reports classification accuracies for GCNH and baselines on real-world
datasets. GCNH achieves state-of-the-art performance on four out of the eight
datasets used; it ranks second and third on Wisconsin and Film and performs
slightly worse on the two homophilous graphs Cora and Citeseer. The results on
all the heterophilous graphs prove the effectiveness of the design choices of
GCNH. On Cornell, Texas, Wisconsin and Film, GCNH avoids the detrimental
influence of neighbors on the final embeddings observed, for example, in GCN
and GAT, with respect to which improvements are large (up to 35%). On
Chameleon and Squirrel, GCNH manages to encode the useful neighborhood
information present in the graph thanks to its separate processing of node and
1-hop neighbors. Indeed, on these two graphs, GCN performs quite well (it
ranks fourth on both), meaning that information contained in the 1-hop
neighborhood is useful for node classification, whereas more complex models
(e.g. Geom-GCN, H2GCN and GPRGNN) fail to capture this property and perform
worse (from 5 to 20% accuracy drop with respect to GCN). On the homophilous
graphs Cora and Citeseer, GCNH performs comparably to the other models,
although slightly worse. These results show that GCNH flexibly adapts to
various homophily settings, achieving consistent performance.

Figure 2: Comparison of the classification accuracy achieved by a set of
models on the syn-cora synthetic datasets. Each point shows the average
accuracy on three datasets generated with a specific homophily ratio.

###  V-D Results On Synthetic Datasets

To better understand how GCNH deals with different levels of homophily, we
evaluate it on synthetic graphs covering a wide range of values of $h$, while
keeping node features and other graph properties unchanged. We provide
additional details about the dataset used in Appendix A-B.

Figure 2 shows the accuracy of GCNH and three other simple baselines: MLP,
whose performance is not affected by the value of $h$ as it is a graph-unaware
method, and GCN and GAT, which achieve significantly worse results on
heterophilous settings. The hyperparameter configurations for these baselines
are reported in Appendix B-A. GCNH’s performance is significantly less
dependent on the homophily level of the graph than the performances of GAT and
GCN. On heterophilous graphs, GCNH improves by almost 50% over GCN and GAT and
by $\sim$2/8% over MLP, meaning that the separate encoding of the neighbors
has a positive impact. On homophilous graphs, GCNH performs comparably to GCN
and GAT, achieving perfect accuracy on perfectly homophilous graphs ($h=1$).

| Separate MLPs |  Learned $\beta$ | Cornell | Texas | Wisconsin | Film | Chameleon | Squirrel | Cora | Citeseer
---|---|---|---|---|---|---|---|---|---|---
GCN | ✗ | ✗ | 60.54 | 55.14 | 51.76 | 27.32 | 64.82 | 53.43 | 86.98 | 76.50
GCNH | ✓ | ✗ |  83.78( $+$23.2) |  86.49( $+$31.3) |  85.49( $+$33.7) |  36.01( $+$8.7) |  70.22( $+$5.4) |  59.74( $+$6.3) |  86.90( $-$0.1) |  75.65( $-$0.8)
GCNH | ✓ | ✓ |  86.49( $+$25.9) |  87.84( $+$32.7) |  87.65( $+$35.9) |  36.89( $+$9.6) |  71.56( $+$6.7) |  61.85( $+$8.4) |  86.88( $-$0.1) |  75.81( $-$0.7)
TABLE II: Mean classification accuracy of GCN and ablated GCNH. In parentheses, we report the performance  improvement or  degradation from the GCN baseline. “Separate MLPs” refers to whether we learn separate linear layers for node and neighborhoods ($W_{1},W_{2}$ in Equation 4 and 5, respectively). “Learned $\beta$” refers to whether we learn $\beta$ as a parameter or not; if not, it is fixed at $\beta$=0.5. Best results are in bold. Benchmark | Cornell | Texas | Wisconsin | Film | Chameleon | Squirrel | Cora | Citeseer
---|---|---|---|---|---|---|---|---
GCNH (sum) |  86.49$\pm$6.98 |  87.84$\pm$3.87 |  87.65$\pm$3.59 | 36.89$\pm$1.50 |  71.56$\pm$1.86 |  61.85$\pm$1.54 | 86.88$\pm$1.04 |  75.81$\pm$1.14
GCNH (mean) | 86.49$\pm$4.41 | 88.92$\pm$3.24 | 89.80$\pm$5.29 |  36.83$\pm$1.44 |  55.64$\pm$1.95 |  39.24$\pm$1.02 |  85.75$\pm$1.57 | 76.00$\pm$0.99
GCNH (max) |  85.41$\pm$8.18 |  88.65$\pm$4.56 |  88.04$\pm$3.26 |  36.07$\pm$1.26 | 71.64$\pm$1.85 | 63.35$\pm$1.99 |  86.68$\pm$1.10 |  75.96$\pm$1.33
TABLE III: Mean classification accuracy and standard deviation for GCNH with
different aggregation functions in Equation 5. Note that results for “max” are
obtained full-batch training only (see Table VI and discussion in Section
V-H), as it allows for more efficient implementation. Best results are in
bold. Figure 3: Values of learned parameter $\beta$ for GCNH on real and
synthetic datasets. Results are obtained using the best-performing
hyperparameter configuration for GCNH models with one layer.

###  V-E Analysis of the GCNH Design

To measure the impact of the design choices we made for GCNH, we perform an
ablation study by removing the two main components of GCNH, namely, the
separate MLPs and the learned importance coefficient $\beta$, to see how they
affect the performance. We report the results in Table II, where we use a
standard GCN as a baseline. The table shows how both components bring an
improvement in classification accuracy on heterophilous graphs, with a small
tradeoff on the performance on homophilous graphs. The MLPs separation leads
to the largest gain, and its combination with the $\beta$ coefficient
consistently brings further improvements.

We analyze further the behavior of $\beta$. Since $\beta$ balances the
contribution of messages of self-node and its neighbors, we expect
heterophilous graphs to lead to larger $\beta$s given that neighborhoods are
generally less informative in those cases. Figure 3 shows the values of the
parameter $\beta$ on different graphs. On synthetic graphs, $\beta$ is
evidently correlated with the edge homophily ratio measured by $h$. On most
real graphs, the values follow a trend similar to that observed in synthetic
graphs. Chameleon and Squirrel are exceptions: we find that, while these
datasets are heterophilous according to the $h$ metric, GCNH tends to learn
low values of $\beta$, corresponding to highly informative neighborhoods. This
corroborates the findings outlined in [19], which pointed out a similar
contradiction: how a standard GCN performs unexpectedly well on the
heterophilous Chameleon and Squirrel, even outperforming heterophily-specific
methods. In fact, this result further suggests that edge homophily ratio is
not suited to describe neighborhood informativeness in general.

###  V-F Aggregation Functions

We test three different aggregation functions for
$\bigoplus_{v\in\mathcal{N}_{u}}$ in Equation (5): element-wise sum, element-
wise mean across the neighbors and element-wise max. Table III reports a
comparison of the node classification results for these aggregation functions.

| N. Params | Cora | Citeseer | Chameleon | Squirrel | Film
---|---|---|---|---|---|---
GGCN | 118 k | 96.05 | 99.94 | 74.83 | 331.64 | 628.36
O(d)-SD | 46 k | 19.64 | 20.15 | 48.87 | 275.90 | 44.22
GCNH (sum) | 30 k | 8.79 | 10.28 | 8.56 | 12.61 | 15.59
GCNH (max) | 30 k | 11.26 | 13.19 | 10.71 | 17.20 | 12.82
TABLE IV: Number of trainable parameters and training times (sec) for two
state-of-the-art methods and GCNH on several graphs. Training is performed for
200 epochs on 10 splits for each dataset. Models have one layer and hidden
size 16. Shortest times for each dataset are in bold.

###  V-G GCNH And Oversmoothing

The performance of GNNs is known to gradually decrease when increasing the
number of layers. This decay is partly attributed to oversmoothing, i.e.,
repeated graph convolutions eventually making node embeddings
indistinguishable from each other [24, 23]. We show experimentally that the
design choices of GCNH alleviate the oversmoothing problem. As shown in Figure
4, GCNH’s accuracy decreases just slightly when increasing the number of
layers, whereas increasing the layers of GCN leads to a larger drop in
performance; see Section B-C in Appendix for the experimental details.

###  V-H Training Times And Trainable Parameters

We report in Table IV the training times required by GCNH and two of its main
competitors GGCN [12] and O(d)-SD [13], as well as their number of trainable
parameters. We take the implementations of these methods from the repositories
of the authors [25, 26]. We report the result for GCNH using sum and max
aggregation. We omit results for mean since sum and mean require the same
amount of computation as they can be implemented efficiently with a matrix
multiplication, i.e., their training times are the same. Max, instead,
requires a scattered max pooling operation for which we use the implementation
in [27]. GCNH is noticeably faster and has fewer trainable parameters than
both GGCN and O(d)-SD.

(a) Cora

(b) Citeseer

Figure 4: Accuracy for GCNH and GCN with different numbers of layers. With a
large number of layers, GCNH prevents oversmoothing.

##  VI Conclusions

We introduced GCNH, a simple yet effective GNN architecture that improves
representation capabilities on heterophilous graphs. GCNH leverages two design
choices: (i) two distinct learnable mapping functions that separately encode
the center node and its neighbors into intermediate representations and (ii)
the importance coefficients $\beta$, one per layer, to balance the
contributions of these two representations on the final node embeddings. We
analyze and demonstrate how these two components enhance the representation
capabilities of GCNH compared to GCN, as, together, they reduce the
detrimental contributions of noisy neighborhoods to the updated node
representations, while making effective use of basic structural information
beneficial for classification. Through extensive experiments on real and
synthetic graphs, we show that GCNH performs competitively on the node
classification task, outperforming state-of-the-art methods on four out of
eight common real-world datasets. In addition to its effectiveness, GCNH’s
simple design results in significantly faster training times and fewer
trainable parameters compared to competing methods.

## References

  * [1] Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Networks. In: International Conference on Learning Representations (ICLR), 2017.
  * [2] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. In: International Conference on Learning Representations (ICLR), 2018.
  * [3] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs. In: Advances in Neural Information Processing Systems (NeurIPS), 2020.
  * [4] Di Jin, Zhizhi Yu, Cuiying Huo, Rui Wang, Xiao Wang, Dongxiao He, and Jiawei Han. Universal Graph Convolutional Networks. In: Advances in Neural Information Processing Systems (NeurIPS), 2021.
  * [5] Xin Zheng, Yixin Liu, Shirui Pan, Miao Zhang, Di Jin, and Philip S. Yu. Graph Neural Networks for Graphs with Heterophily: A Survey. In: arXiv:2202.07082, 2022
  * [6] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-GCN: Geometric Graph Convolutional Networks. In: International Conference on Learning Representations (ICLR), 2020.
  * [7] Yu Wang and Tyler Derr. Tree Decomposed Graph Neural Network. In: Proceedings of the 30th ACM International Conference on Information and Knowledge Management, 2021.
  * [8] Wei Jin, Tyler Derr, Yiqi Wang, Yao Ma, Zitao Liu, and Jiliang Tang. Node Similarity Preserving Graph Convolutional Networks. In: Proceedings of the 14th ACM International Conference on Web Search and Data Mining, 2021.
  * [9] Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond Low-frequency Information in Graph Convolutional Networks. In: Conference on Artificial Intelligence (AAAI), 2021.
  * [10] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, Yaliang Li. Simple and Deep Graph Convolutional Networks. In: International Conference on Machine Learning (ICML), 2020
  * [11] Lun Du, Xiaozhou Shi, Qiang Fu, Xiaojun Ma, Hengyu Liu, Shi Han, and Dongmei Zhang. 2022. GBK-GNN: Gated Bi-Kernel Graph Neural Networks for Modeling Both Homophily and Heterophily. In: Proceedings of the ACM Web Conference 2022 (WWW ’22), 2022
  * [12] Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks. In: International Conference on Data Mining (ICDM), 2022.
  * [13] Cristian Bodnar, Francesco Di Giovanni, Benjamin Paul Chamberlain, Pietro Lio, and Michael M. Bronstein. Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNs. In: ICLR 2022 Workshop on Geometrical and Topological Representation Learning, 2022.
  * [14] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive Universal Generalized PageRank Graph Neural Network. In: International Conference on Learning Representations (ICLR), 2021.
  * [15] Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing. In: International Conference on Machine Learning (ICML), 2019.
  * [16] Dongxiao He, Chundong Liang, Huixin Liu, Mingxiang Wen, Pengfei Jiao, and Zhiyong Feng. Block modeling-guided graph convolutional neural networks. In: Conference on Artificial Intelligence (AAAI), 2022.
  * [17] Liang Yang, Mengzhe Li, Liyang Liu, Bingxin Niu, Chuan Wang, Xiaochun Cao, and Yuanfang Guo. Diverse Message Passing for Attribute with Heterophily. In: Advances in Neural Information Processing Systems (NeurIPS), 2021.
  * [18] Susheel Suresh, Vinith Budde, Jennifer Neville, Pan Li, and Jianzhu Ma. Breaking the Limit of Graph Neural Networks by Improving the Assortativity of Graphs with Local Mixing Patterns. In: ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2021.
  * [19] Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is Homophily a Necessity for Graph Neural Networks? In: International Conference on Learning Representations (ICLR), 2022.
  * [20] Andrea Cavallo, Claas Grohnfeldt, Michele Russo, Giulio Lovisotto, and Luca Vassio. 2-Hop Neighbor Class Similarity (2NCS): A Graph Structural Metric Indicative of Graph Neural Network Performance. In: arXiv:2212.13202, 2022.
  * [21] Miller Mcpherson, Lynn Smith-Lovin, and James Cook. Birds of a Feather: Homophily in Social Networks. In: Annual Review of Sociology 27, 2001.
  * [22] Derek Lim, Felix Matthew Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Prasad Bhalerao, and Ser-Nam Lim. Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods. In: Advances in Neural Information Processing Systems (NeurIPS), 2021.
  * [23] Kenta Oono and Taiji Suzuki. Graph Neural Networks Exponentially Lose Expressive Power for Node Classification. In: International Conference on Learning Representations (ICLR), 2020.
  * [24] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper Insights Into Graph Convolutional Networks for Semi-Supervised Learning. In: Conference on Artificial Intelligence (AAAI), 2018.
  * [25] Yujun Yan. Public code for “Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks”, [Online]: https://github.com/yujun-yan/heterophily_and_oversmoothing, Accessed on 03-02-2023.
  * [26] Twitter Research. Public code for “Neural Sheaf Diffusion”, [Online]: https://github.com/twitter-research/neural-sheaf-diffusion, Accessed on 03-02-2023.
  * [27] Matthias Fey et al. PyTorch Scatter, [Online]: https://github.com/rusty1s/pytorch_scatter, Accessed on 03-02-2023.
  * [28] Sunil Kumar Maurya. Public code for “Improving Graph Neural Networks with Simple Architecture Design”, [Online]: https://github.com/sunilkmaurya/FSGNN, Accessed on 03-02-2023.
  * [29] Graph-structured Data Mining and Machine Learning at University of Illinois at Urbana-Champaign (UIUC) and Jilin University (JLU). Public code for “Geom-GCN: Geometric Graph Convolutional Networks”, [Online]: https://github.com/graphdml-uiuc-jlu/geom-gcn, Accessed on 03-02-2023.
  * [30] Carnegie Mellow University, CMU World Wide Knowledge Base, [Online]: http://www.cs.cmu.edu/afs/cs.cmu.edu/project/theo-11/www/wwkb/, Accessed on 03-02-2023.
  * [31] Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social Influence Analysis in Large-Scale Networks. In: ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD, 2009.
  * [32] Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko and Liudmila Prokhorenkova. A critical look at evaluation of GNNs under heterophily: Are we really making progress? In: International Conference on Learning Representations (ICLR) (2023).
  * [33] Galileo Mark Namata, Ben London, Lise Getoor, and Bert Huang. Query-driven Active Surveying for Collective Classification. In: Workshop on Mining and Learning with Graphs, 2012.
  * [34] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective Classification in Network Data. In: AI Magazine 29.3, 2008.

Benchmark | Cornell | Texas | Wisconsin | Film | Chameleon | Squirrel | Cora | Citeseer | syn-cora
---|---|---|---|---|---|---|---|---|---
#Nodes | 183 | 183 | 251 | 7,600 | 2,277 | 5,201 | 2,708 | 3,327 | 1490
#Edges | 280 | 295 | 466 | 26,752 | 31,421 | 198,493 | 1,433 | 3,703 | 2965 to 2968
#Classes | 5 | 5 | 5 | 5 | 5 | 5 | 7 | 6 | 5
#Features | 1,703 | 1,703 | 1,703 | 931 | 2,325 | 2,089 | 1,433 | 3,703 | 1,433
Homophily $h$ | 0.30 | 0.11 | 0.21 | 0.22 | 0.23 | 0.22 | 0.81 | 0.74 | [0, 0.1, …, 1]
TABLE V: Statistics of real-world and synthetic datasets. Dataset | #Layers | Batch size | #Epochs | Hidden size | Dropout rate | $\beta$
---|---|---|---|---|---|---
Cornell |  {1, 2, 3} |  {50, $|V|$} |  {100, 200, 300} |  {16, 32, 64} |  {0.0, 0.25, 0.5} | 0.75
Texas |  {1, 2, 3} |  {50, $\bm{|V|}$} |  {100, 200, 300} |  {16, 32, 64} |  {0.0, 0.25, 0.5} | 0.62
Wisconsin |  {1, 2, 3} |  {50, $|V|$} |  {100, 200, 300} |  {16, 32, 64} |  {0.0, 0.3, 0.6} | 0.70, 0.69
Film |  {1, 2, 3} |  {300, 500, $|V|$} |  {150} |  {16, 32, 64} |  {0.0, 0.3, 0.6} | 0.72, 0.75
Chameleon |  {1, 2, 3} |  {300, 600, $|V|$} |  {500, 1000, 1500} |  {16, 32, 64} |  {0.0, 0.25, 0.5} | 0.12
Squirrel |  {1, 2, 3} |  {300, 1400, $|V|$} |  {500, 1000, 1500} |  {16, 32, 64} |  {0.0, 0.25, 0.5} | 0.35
Cora |  {1, 2, 3} |  {150, 300, $|V|$} |  {300} |  {16, 32, 64} |  {0.0, 0.25, 0.5, 0.75} | 0.69, 0.61
Citeseer |  {1, 2, 3} |  {150, 300, $|V|$} |  {300} |  {16, 32, 64} |  {0.0, 0.25, 0.5, 0.75} | 0.59
syn-cora | {1, 2, 3} |  {300, $|V|$} | {300} | {16, 32} | {0.0, 0.25, 0.5} |
TABLE VI: Hyperparameters and learned values of $\beta$ for GCNH. For each
dataset, the best hyperparameters are in bold. For 2-layer models, the values
of $\beta$ are in the order $\beta^{0},\beta^{1}$. For syn-cora, the best
hyperparameters and the values of $\beta$ are not reported as they depend on
the homophily value of the graph.

##  Appendix A Datasets

This section and Table V report details about the datasets.

###  A-A Real-World Datasets

These datasets are commonly used in most of the works dealing with
heterophilous graphs. Chameleon and Squirrel are taken from [28], the others
from [29]. We present further details in the following:

  * •

Texas, Wisconsin and Cornell are webpage datasets collected from different
universities [30]. Nodes represent web pages and edges are hyperlinks between
them.

  * •

Film (Actor), is the actor-only induced subgraph of the film-director-actor-
writer network [31]. Nodes correspond to Wikipedia pages of actors and edges
denote the co-occurrence of two actors on the same page.

  * •

Chameleon and Squirrel are Wikipedia pages on the specific topics of
chameleons and squirrels. Nodes are Wikipedia pages and edges are mutual links
between them. Note: contemporary to this work, [32] highlights drawbacks of
these two datasets.

  * •

Cora and Citeseer are citation networks where nodes represent papers and edges
represent citations of one paper by another [34, 33]. These datasets are
treated as undirected.

###  A-B Synthetic Datasets

The synthetic datasets used in this work are taken from [3], which defines a
graph generation strategy similar to [15]. The homophily ratio of the graph is
defined a priori. Then, the graph is generated such that the degree
distribution follows a power law. Classes are assigned randomly and features
are sampled from nodes of the corresponding class in the real graph Cora. For
each of the specified homophily levels, three different graphs are generated.

##  Appendix B Hyperparameters And Experimental Details

We report here additional details about the experiments in this work. All
models are trained with Adam optimizer, learning rate $5\cdot 10^{-3}$ and
weight decay $5\cdot 10^{-3}$.

###  B-A Baselines On Synthetic Datasets

We obtain the results for MLP, GCN and GAT on the synthetic graphs in Figure 2
through hyperparameter optimization among the following values: 100 epochs,
{1,2,3} layers, hidden size {16,32}. For all experiments on the synthetic
datasets, we randomly generate train/evaluation/test splits with sizes
50%/20%/30%. We compute results on a single split for each dataset and we
average the results of three different graphs for each level of homophily
ratio reported in the figure.

###  B-B GCNH

The hyperparameters for GCNH on real and synthetic graphs are optimized among
the values reported in Table VI. The activation function $\sigma(\cdot)$ in
Equations 4 and 5 is LeakyReLU. We perform batching by forwarding, for each
batch, the complete graph through the model and computing the loss only on the
nodes in the current batch.

###  B-C Experiments On Oversmoothing

The hyperparameters of the models in Section V-G are optimized among the
following values: batch size 300, epochs {300,500}, hidden size {16,32,64},
dropout rate {0.0,0.5}. Note that the results for GCN in Table I are taken
from [12], while those in Figure 4 are obtained from our own experiments, and
they slightly differ because the hyperparameter grid search is different.