# Equation of spin motion for a particle with electric and magnetic charges
and dipole moments

Alexander J. Silenko<EMAIL_ADDRESS>Bogoliubov Laboratory of Theoretical
Physics, Joint Institute for Nuclear Research, Dubna 141980, Russia  Research
Institute for Nuclear Problems, Belarusian State University, Minsk 220030,
Belarus

###### Abstract

The general classical equation of spin motion is rigorously derived for a
particle with electric and magnetic charges and dipole moments in
electromagnetic fields. The equation describing the spin motion relative to
the momentum direction in storage rings is also obtained. The importance of
the derivation follows from a possible appearance of magnetic charges and EDMs
due to the pseudoscalar _CP_ -violating electromagnetic interaction caused by
dark matter axions.

equation of spin motion; magnetic charge; axion

A study of spin motion is one of the most important methods of a search for
new physics. Witten EWitten  has shown that a pseudoscalar _CP_ -violating
electromagnetic interaction leads to a transformation of electrically charged
particles to dyons having nonzero electric and magnetic charges. A similar
statement has been made in Ref. AxionCao  in relation to axion-induced
electromagnetic effects. In Refs. Hill ; Hill2016 ; AxionAlexander  and, with
some reservations, in Ref. AxionWang , an existence of oscillating electric
dipole moments (EDMs) caused by axion-photon coupling has been stated.
Certainly, the presence of real EWitten  or effective AxionCao  magnetic
charges changes spin dynamics as compared with the known equation (see Refs.
FukuyamaSilenko ; PhysScr  and references therein) for particles with EDMs.
The problem of a spin motion of a particle with electric and magnetic charges
and dipole moments is still unsolved and is rather important because
experiments on a search for dark matter axions in spin interactions are now
performed by several collaborations GrahamPhysRevD2018 ; XENONaxion ;
axiondJEDI . In such experiments, a possible presence of magnetic charges
should be taken into account. In the present paper, we rigorously derive a
general equation of spin motion for a particle with electric and magnetic
charges and dipole moments. Certainly, _effective_ magnetic charges AxionCao
do not need to be quantized. For them, the problem of coexistence of electric
and magnetic charges does not appear.

We use standard denotations of Dirac matrices (see, e.g., Ref. BLP ) and the
system of units $\displaystyle\hbar=1,~{}c=1$. We include $\displaystyle\hbar$
and $\displaystyle c$ explicitly when this inclusion clarifies the problem.

The equation of spin motion in electromagnetic fields for a charged (or
uncharged) particle with electric and magnetic dipole moments generalizing the
well-known Thomas-Bargmann-Michel-Telegdi equation has the form (see Refs.
FukuyamaSilenko ; PhysScr  and references therein)

$\begin{array}[]{c}\bm{\Omega}=-\frac{e}{mc}\left[\left(G+\frac{1}{\gamma}\right){\bm{B}}-\frac{\gamma
G}{\gamma+1}({\bm{\beta}}\cdot{\bm{B}}){\bm{\beta}}-\left(G+\frac{1}{\gamma+1}\right)\bm{\beta}\times{\bm{E}}\right.\\\
+\left.\frac{\eta}{2}\left({\bm{E}}-\frac{\gamma}{\gamma+1}(\bm{\beta}\cdot{\bm{E}})\bm{\beta}+\bm{\beta}\times{\bm{B}}\right)\right].\end{array}$
(1)

Here $\displaystyle G=(g-2)/2,~{}g=2mc\mu/(es)$,
$\displaystyle\eta=2mcd/(es)$, $\displaystyle s$ is the spin number,
$\displaystyle\bm{\beta}=\bm{v}/c$, and $\displaystyle\gamma$ is the Lorentz
factor.

In the relativistic spin theory, one introduces the spin four-pseudovector and
the momentum four-vector, $\displaystyle a^{\mu}$ and $\displaystyle p^{\mu}$,
whose definition in the particle rest frame is given by BLP

$a^{\mu}=(0,{\bm{\zeta}}),\qquad p^{\mu}=(m,{\bm{0}}).$ (2)

So, in any frame

$a^{\mu}p_{\mu}=0,~{}~{}a_{\mu}a^{\mu}=-\bm{\zeta}^{2}.$ (3)

In a frame moving with the velocity $\displaystyle{\bm{v}}={\bm{p}}/\epsilon$
($\displaystyle\epsilon$ is the total kinetic energy), the four-pseudovector
$\displaystyle a^{\mu}=(a^{0},~{}{\bm{a}})$ is defined by

$a^{\mu}=(a^{0},~{}{\bm{a}}),\quad{\bm{a}}=\bm{\zeta}+\frac{{\bm{p}}(\bm{\zeta}\cdot{\bm{p}})}{m(\epsilon+m)},\quad
a^{0}=\frac{{\bm{a}}\cdot{\bm{p}}}{\epsilon}=\frac{{\bm{p}}\cdot\bm{\zeta}}{m},\quad{\bm{a}}^{2}=\bm{\zeta}^{2}+\frac{({\bm{p}}\cdot\bm{\zeta})^{2}}{m^{2}}.$
(4)

The Lorentz force $\displaystyle\bm{F}$ acting on the electric charge
$\displaystyle e$ and the Lorentz-like force $\displaystyle\bm{F}^{*}$ acting
on the magnetic charge $\displaystyle e^{*}$ are given by Rindler1989

$\frac{d\bm{p}}{dt}=\bm{F}+\bm{F}^{*}=e(\bm{E}+\bm{\beta}\times\bm{B})+e^{*}(\bm{B}-\bm{\beta}\times\bm{E}).$
(5)

The equation of motion depends on the electric and magnetic charges and reads

$m\frac{du^{\mu}}{d\tau}=eF^{\mu\nu}u_{\nu}+e^{*}\widetilde{F}^{\mu\nu}u_{\nu},$
(6)

where the dual tensor of electromagnetic field is defined by
$\displaystyle\widetilde{F}^{\mu\nu}=\epsilon^{\mu\nu\rho\sigma}F_{\rho\sigma}/2$
and $\displaystyle a_{\mu}u^{\mu}=0$. With the denotations of Ref. LL2 ,
$\displaystyle F^{\mu\nu}=(-\bm{E},\bm{B})$ and
$\displaystyle\widetilde{F}^{\mu\nu}=(-\bm{B},-\bm{E})$.

The relativistic equation of spin motion has the general form

$\frac{da^{\mu}}{d\tau}=A_{1}F^{\mu\nu}a_{\nu}+A_{2}u^{\mu}F^{\nu\lambda}u_{\nu}a_{\lambda}+A_{3}\widetilde{F}^{\mu\nu}a_{\nu}+A_{4}u^{\mu}\widetilde{F}^{\nu\lambda}u_{\nu}a_{\lambda}.$
(7)

The coefficients $\displaystyle A_{i}~{}(i=1,2,3,4)$ are determined as follows
(cf. Ref. FukuyamaSilenko ). In the instantaneously accompanying frame
(particle rest frame), Eq. (7) reduces to

$\frac{da^{i}}{dt}=\frac{d\zeta^{i}}{dt}=A_{1}F^{ij}\zeta_{j}+A_{3}\widetilde{F}^{ij}\zeta_{j}=A_{1}(\bm{\zeta}\times{\bf
B})^{i}-A_{3}(\bm{\zeta}\times{\bf E})^{i}.$ (8)

In this frame, the equation of spin motion for the spin $\displaystyle s=1/2$
is given by

$\frac{d\bm{\zeta}}{dt}=2\mu{\bm{\zeta}}\times{\bf B}+2d\bm{\zeta}\times{\bf
E}.$ (9)

For an arbitrary spin

$\frac{d\bm{\zeta}}{dt}=\frac{\mu}{s}{\bm{\zeta}}\times{\bf
B}+\frac{d}{s}\bm{\zeta}\times{\bf E}.$ (10)

Comparing this equation with Eq. (8), we obtain

$A_{1}=\frac{\mu}{s},\qquad A_{3}=-\frac{d}{s}.$ (11)

Values of $\displaystyle A_{2},A_{4}$ result from the equation of motion.

We should be rather careful. Interactions of the electric charge and dipole
with the electric field and the magnetic charge and dipole with the magnetic
field are very similar. However, Eq. (5) shows that interactions of the
electric charge with the magnetic field and the magnetic charge with the
electric field have different signs. Therefore, the normal (Dirac) magnetic
moment originated from the electric charge has the sign opposite to the sign
of the “normal” EDM caused by the magnetic charge. As a result, the connection
between the EDM and the magnetic charge should have the form $\displaystyle
G^{*}=(g^{*}-2)/2,~{}g^{*}=-2mcd/(e^{*}s)$.

Multiplying Eq. (7) by $\displaystyle u_{\mu}$ and taking into account that
$\displaystyle u_{\mu}u^{\mu}=1$ leads to

$u_{\mu}\frac{da^{\mu}}{d\tau}=\left(\frac{\mu}{s}+A_{2}\right)F^{\mu\nu}u_{\mu}a_{\nu}+\left(-\frac{d}{s}+A_{4}\right)\widetilde{F}^{\mu\nu}u_{\mu}a_{\nu}.$
(12)

Since

$\frac{d(a_{\mu}u^{\mu})}{d\tau}=0,\qquad
u_{\mu}\frac{da^{\mu}}{d\tau}=-a_{\mu}\frac{du^{\mu}}{d\tau}=\frac{1}{m}\left(eF^{\mu\nu}+e^{*}\widetilde{F}^{\mu\nu}\right)u_{\mu}a_{\nu},$
(13)

we obtain

$A_{2}=\frac{e}{m}-\frac{\mu}{s}\equiv-\frac{\mu^{\prime}}{s},\qquad
A_{4}=\frac{e^{*}}{m}+\frac{d}{s}\equiv\frac{d^{\prime}}{s}.$ (14)

Here $\displaystyle d$, $\displaystyle-e^{*}s/m$, and $\displaystyle
d^{\prime}$ are the total, “normal” (Dirac-like), and “anomalous” EDMs. This
distribution repeates the distribution for the magnetic moments
$\displaystyle\mu,~{}es/m$, and $\displaystyle\mu^{\prime}$.

As a result, the equation of spin motion takes the form

$\frac{da^{\mu}}{d\tau}=\frac{\mu}{s}F^{\mu\nu}a_{\nu}-\frac{\mu^{\prime}}{s}u^{\mu}F^{\nu\lambda}u_{\nu}a_{\lambda}-\frac{d}{s}\widetilde{F}^{\mu\nu}a_{\nu}+\frac{d^{\prime}}{s}u^{\mu}\widetilde{F}^{\nu\lambda}u_{\nu}a_{\lambda}.$
(15)

Unlike the Thomas-Bargmann-Michel-Telegdi equation Thomas ; BMT , this
generalized equation takes into account the effective AxionCao  or real
EWitten  magnetic charge and the EDM.

In the above derivation, we followed Ref. FukuyamaSilenko . Next calculations
utilize the approach by Jackson Jackson  and almost repeate Ref. PhysScr .

With the use of Eq. (6), the obtained equation can be presented in the form

$\frac{da^{\mu}}{d\tau}=\frac{\mu}{s}\left(F^{\mu\nu}a_{\nu}-u^{\mu}F^{\nu\lambda}u_{\nu}a_{\lambda}\right)-\frac{d}{s}\left(\widetilde{F}^{\mu\nu}a_{\nu}-u^{\mu}\widetilde{F}^{\nu\lambda}u_{\nu}a_{\lambda}\right)-u^{\mu}\frac{du^{\lambda}}{d\tau}a_{\lambda}.$
(16)

It is convenient to denote

$\Phi^{\mu}=\frac{\mu}{s}\left(F^{\mu\nu}a_{\nu}-u^{\mu}F^{\nu\lambda}u_{\nu}a_{\lambda}\right)-\frac{d}{s}\left(\widetilde{F}^{\mu\nu}a_{\nu}-u^{\mu}\widetilde{F}^{\nu\lambda}u_{\nu}a_{\lambda}\right).$
(17)

Evidently, $\displaystyle\Phi^{\mu}=(\Phi^{0},\bm{\Phi})$ is a four-vector.
Since $\displaystyle
u_{\mu}\Phi^{\mu}=\gamma(\Phi^{0}-\bm{\beta}\cdot\bm{\Phi})=0$, it satisfies
the relation $\displaystyle\Phi^{0}=\bm{\beta}\cdot\bm{\Phi}$. The last term
in Eq. (16) can be transformed as follows Jackson :

$u^{\mu}\frac{du^{\lambda}}{d\tau}a_{\lambda}=-u^{\mu}\gamma\bm{a}\cdot\frac{d\bm{\beta}}{d\tau}.$
(18)

Thus, Eq. (16) leads to

$\frac{da^{0}}{d\tau}=\Phi^{0}+\gamma^{2}\bm{a}\cdot\frac{d\bm{\beta}}{d\tau},\qquad\frac{d\bm{a}}{d\tau}=\bm{\Phi}+\gamma^{2}\bm{\beta}\left(\bm{a}\cdot\frac{d\bm{\beta}}{d\tau}\right).$
(19)

The equation of motion for the rest-frame spin $\displaystyle\bm{\zeta}$ can
be calculated with the relations

$\displaystyle{\bm{\zeta}}=\bm{a}-\frac{\gamma}{\gamma+1}{\bm{\beta}}({\bm{\beta}}\cdot\bm{a}),\qquad\frac{d}{d\tau}\left(\frac{\gamma}{\gamma+1}{\bm{\beta}}\right)=\frac{\gamma}{\gamma+1}\frac{d\bm{\beta}}{d\tau}+\frac{\gamma^{3}}{(\gamma+1)^{2}}{\bm{\beta}}\left({\bm{\beta}}\cdot\frac{d\bm{\beta}}{d\tau}\right).$

Therefore, the equation of spin motion has the form (cf. Refs. PhysScr ;
Jackson )

$\frac{d\bm{\zeta}}{d\tau}=\bm{\Phi}-\frac{\gamma\bm{\beta}}{\gamma+1}\Phi^{0}+\frac{\gamma^{2}}{\gamma+1}\bm{\zeta}\times\left({\bm{\beta}}\times\frac{d\bm{\beta}}{d\tau}\right).$
(20)

The transformation of the given four-vector $\displaystyle\Phi^{\mu}$ to the
instantaneously accompanying frame results in
$\displaystyle\bigl{(}\Phi^{(0)}\bigr{)}^{\mu}=\bigl{(}0,\bm{\Phi}^{(0)}\bigr{)}$,
where

$\displaystyle\bm{\Phi}^{(0)}=\bm{\Phi}-\frac{\gamma}{\gamma+1}\bm{\beta}(\bm{\beta}\cdot\bm{\Phi})=\bm{\Phi}-\frac{\gamma\bm{\beta}}{\gamma+1}\Phi^{0}.$

We should differ $\displaystyle\Phi^{0}$ and $\displaystyle\bm{\Phi}^{(0)}$.

Since $\displaystyle dt=\gamma\,d\tau$, the derivation of
$\displaystyle\bm{\Phi}^{(0)}$ from Eq. (17) leads to the following equation
of spin motion:

$\frac{d\bm{\zeta}}{dt}=-\left(\frac{d\bm{E}^{(0)}}{s\gamma}+\frac{\mu\bm{B}^{(0)}}{s\gamma}\right)\times\bm{\zeta}-\frac{\gamma^{2}}{\gamma+1}\left({\bm{\beta}}\times\frac{d\bm{\beta}}{dt}\right)\times\bm{\zeta}.$
(21)

The angular velocity of spin precession is given by PhysScr ; Jackson

$\bm{\Omega}=-\left(\frac{d\bm{E}^{(0)}}{s\gamma}+\frac{\mu\bm{B}^{(0)}}{s\gamma}\right)-\frac{\gamma^{2}}{\gamma+1}\left({\bm{\beta}}\times\frac{d\bm{\beta}}{dt}\right)=\bm{\Omega}^{(0)}+\bm{\omega}_{T},$
(22)

where

$\begin{array}[]{c}\bm{\Omega}^{(0)}=-\frac{d\bm{E}^{(0)}}{s\gamma}-\frac{\mu\bm{B}^{(0)}}{s\gamma}\end{array}$
(23)

and $\displaystyle\bm{\omega}_{T}$ is the angular velocity of the Thomas
precession:

$\begin{array}[]{c}\bm{\omega}_{T}=-\frac{\gamma^{2}}{\gamma+1}\left(\bm{\beta}\times\frac{d\bm{\beta}}{dt}\right).\end{array}$
(24)

Therefore, the total angular velocity of spin precession is the sum of two
parts. The first part is given by the Lorentz transformation between the
instantaneously accompanying frame and the lab frame. The fields in the
instantaneously accompanying frame are equal to Jackson

$\begin{array}[]{c}\bm{E}^{(0)}=\gamma\left[\bm{E}-\frac{\gamma}{\gamma+1}\bm{\beta}(\bm{\beta}\cdot\bm{E})+\bm{\beta}\times\bm{B}\right],\\\
\bm{B}^{(0)}=\gamma\left[\bm{B}-\frac{\gamma}{\gamma+1}\bm{\beta}(\bm{\beta}\cdot\bm{B})-\bm{\beta}\times\bm{E}\right].\end{array}$
(25)

The second part is the contribution from the Thomas precession. This part
defines the additional spin precession caused by a purely kinematical effect
of a rotation of the particle rest frame (see, e.g., Refs. Jackson ; Rindler
). Only the second part depends on the magnetic charge.

The particle acceleration expressed in terms of the lab frame fields is
defined by Eq. (5). The total acceleration reads

$\begin{array}[]{c}\frac{d\bm{\beta}}{dt}=\frac{e}{mc\gamma}\left[\bm{E}+{\bm{\beta}}\times{\bm{B}}-\bm{\beta}(\bm{\beta}\cdot{\bm{E}})\right]+\\\
\frac{e^{*}}{mc\gamma}\left[\bm{B}-{\bm{\beta}}\times{\bm{E}}-\bm{\beta}(\bm{\beta}\cdot{\bm{B}})\right].\end{array}$
(26)

With the use of Eqs. (25) and (26), one can bring Eqs. (23) and (24) to the
form

$\begin{array}[]{c}\bm{\Omega}^{(0)}=-\frac{\mu}{s}\left[\bm{B}-\frac{\gamma}{\gamma+1}{\bm{\beta}}({\bm{\beta}}\cdot{\bm{B}})-\bm{\beta}\times{\bm{E}}\right]\\\
-\frac{d}{s}\left[\bm{E}-\frac{\gamma}{\gamma+1}{\bm{\beta}}({\bm{\beta}}\cdot{\bm{E}})+\bm{\beta}\times{\bm{B}}\right],\\\
\bm{\omega}_{T}=\frac{e}{m}\left[\frac{\gamma-1}{\gamma}\bm{B}-\frac{\gamma}{\gamma+1}{\bm{\beta}}({\bm{\beta}}\cdot{\bm{B}})-\frac{\gamma}{\gamma+1}\bm{\beta}\times{\bm{E}}\right]\\\
-\frac{e^{*}}{m}\left[\frac{\gamma-1}{\gamma}\bm{E}-\frac{\gamma}{\gamma+1}{\bm{\beta}}({\bm{\beta}}\cdot{\bm{E}})+\frac{\gamma}{\gamma+1}\bm{\beta}\times{\bm{B}}\right].\end{array}$
(27)

The resulting angular velocity of spin motion reads

$\begin{array}[]{c}\bm{\Omega}=-\frac{e}{m}\left[\left(G+\frac{1}{\gamma}\right){\bm{B}}-\frac{G\gamma}{\gamma+1}({\bm{\beta}}\cdot{\bm{B}}){\bm{\beta}}-\left(G+\frac{1}{\gamma+1}\right)\bm{\beta}\times{\bm{E}}\right]\\\
+\frac{e^{*}}{m}\left[\left(G^{*}+\frac{1}{\gamma}\right){\bm{E}}-\frac{G^{*}\gamma}{\gamma+1}({\bm{\beta}}\cdot{\bm{E}}){\bm{\beta}}+\left(G^{*}+\frac{1}{\gamma+1}\right)\bm{\beta}\times{\bm{B}}\right].\end{array}$
(28)

When $\displaystyle e^{*}=0$, Eq. (28) takes the form (1). Equation (28) is
useful for experiments with atoms.

While the magnetic charge and the EDM caused by dark matter axions are
oscillating, the angular velocity of their oscillations,
$\displaystyle\omega_{a}=m_{a}c^{2}/\hbar$, is very small as compared with
$\displaystyle\Omega$ and $\displaystyle\omega$. As a result, it is convenient
to determine the spin motion of particles in storage rings relative to the
velocity and momentum direction. Such a transformation presents Eq. (28) in
terms of the unit vector in this direction,
$\displaystyle{\bm{N}}={\bm{\beta}}/\beta=\bm{p}/p$:

$\displaystyle\frac{d{\bm{N}}}{dt}=\frac{\dot{\bm{\beta}}}{\beta}-\frac{\bm{\beta}}{\beta^{3}}\left({\bm{\beta}}\cdot\dot{\bm{\beta}}\right)=\bm{\omega}\times{\bm{N}},\qquad\bm{\omega}=\frac{e}{m\gamma}\left(\frac{{\bm{\beta}}\times{\bm{E}}}{\beta^{2}}-{\bm{B}}\right)+\frac{e^{*}}{m\gamma}\left(\frac{{\bm{\beta}}\times{\bm{B}}}{\beta^{2}}+{\bm{E}}\right),$

where $\displaystyle\bm{\omega}$ is the angular velocity of rotation of the
velocity and momentum direction. Thus, the angular velocity of the spin
rotation relative to this direction (i.e., in the Frenet-Serret coordinate
system) is given by

$\begin{array}[]{c}\bm{\Omega}_{FS}=\bm{\Omega}-\bm{\omega}=-\frac{e}{m}\left[G{\bm{B}}-\frac{G\gamma}{\gamma+1}({\bm{\beta}}\cdot{\bm{B}}){\bm{\beta}}-\left(G-\frac{1}{\gamma^{2}-1}\right){\bm{\beta}}\times{\bm{E}}\right]\\\
+\frac{e^{*}}{m}\left[G^{*}{\bm{E}}-\frac{G^{*}\gamma}{\gamma+1}({\bm{\beta}}\cdot{\bm{E}}){\bm{\beta}}+\left(G^{*}-\frac{1}{\gamma^{2}-1}\right){\bm{\beta}}\times{\bm{B}}\right].\end{array}$
(29)

The quantities $\displaystyle e^{*}$ and $\displaystyle d$ (but not
$\displaystyle G^{*}$) oscillate with the frequency $\displaystyle\omega_{a}$.

For more detailed derivations, especially for calculations of systematical
errors, it is helpful to use the cylindrical coordinates PRStAcBeam .

In summary, the general classical equation of spin motion has been rigorously
derived for particles with electric and magnetic charges and dipole moments in
electromagnetic fields. While we do not use any dual transformation, this
equation possesses the dual symmetry $\displaystyle e\rightarrow
e^{*},~{}G\rightarrow
G^{*},~{}\bm{E}\rightarrow\bm{B},~{}\bm{B}\rightarrow-\bm{E}$. The equation is
also presented in the form convenient for the description of spin motion in
storage rings. The necessity for our derivation follows from Refs. EWitten ;
AxionCao  substantiating an appearance of magnetic charges and EDMs due to the
pseudoscalar _CP_ -violating electromagnetic interaction.

The author is grateful to N.N. Nikolaev for helpful discussions and comments.

## References

  * (1) E. Witten, Dyons of Charge $\displaystyle e\theta/2\pi$, Phys. Lett. B 86, 283 (1979).
  * (2) ChunJun Cao and A. Zhitnitsky, Axion detection via topological Casimir effect, Phys. Rev. D 96, 015013 (2017).
  * (3) C. T. Hill, Axion Induced Oscillating Electric Dipole Moments, Phys. Rev. D 91, 111702 (2015).
  * (4) C. T. Hill, Axion Induced Oscillating Electric Dipole Moment of the Electron, Phys. Rev. D 93, 025007 (2016).
  * (5) S. Alexander and R. Sims, Detecting axions via induced electron spin precession, Phys. Rev. D 98, 015011 (2018).
  * (6) Zihang Wang and Lijing Shao, Axion induced spin effective couplings, Phys. Rev. D 103, 116021 (2021).
  * (7) T. Fukuyama and A. J. Silenko, Derivation of Generalized Thomas-Bargmann-Michel-Telegdi Equation for a Particle with Electric Dipole Moment, Int. J. Mod. Phys. A 28, 1350147 (2013).
  * (8) A. J. Silenko, Spin precession of a particle with an electric dipole moment: contributions from classical electrodynamics and from the Thomas effect, Phys. Scripta 90, 065303 (2015).
  * (9) P. W. Graham, D. E. Kaplan, J. Mardon, S. Rajendran, W. A. Terrano, L. Trahms, and T. Wilkason, Spin precession experiments for light axionic dark matter, Phys. Rev. D 97, 055006 (2018).
  * (10) E. Aprile _et al._ (XENON Collaboration), Excess electronic recoil events in XENON1T, Phys. Rev. D 102, 072004 (2020).
  * (11) S. Karanth _et al._ (JEDI Collaboration), First search for axionlike particles in a storage ring using a polarized deuteron beam, Phys. Rev. X Phys. Rev. X 13, 031004 (2023).
  * (12) V. B. Berestetskii, E. M. Lifshitz, and L. P. Pitayevskii, Quantum Electrodynamics, 2nd ed. (Pergamon, Oxford, 1982).
  * (13) W. Rindler, Relativity and electromagnetism: The force on a magnetic monopole, Am. J. Phys. 57, 993 (1989).
  * (14) L. D. Landau and E.M. Lifshitz, _The Classical Theory of Fields_ , 4th ed. (Butterworth-Heinemann, Oxford, 1980).
  * (15) L. H. Thomas, The motion of the spinning electron, Nature 117, 514 (1926); The kinematics of an electron with an axis, Phil. Mag. 3, 1 (1927).
  * (16) V. Bargmann, L. Michel, and V. L. Telegdi, Precession of the polarization of particles moving in a homogeneous electromagnetic field, Phys. Rev. Lett. 2, 435 (1959).
  * (17) J. D. Jackson, _Classical Electrodynamics_ , 3rd ed. (Wiley, New York, 1998).
  * (18) W. Rindler, _Relativity: Special, General, and Cosmological_ , 2nd ed. (Oxford Univ. Press, Oxford, 2001), pp. 199-200; R. U. Sexl and H. K. Urbantke, _Relativity, Groups, Particles: Special Relativity and Relativistic Symmetry in Field and Particle Physics_ , (Springer, New York, 2001); A. A. Ungar, _Beyond the Einstein Addition Law and its Gyroscopic Thomas Precession_ , (Kluwer Acad. Publ., Dordrecht, 2001).
  * (19) A. J. Silenko, Equation of spin motion in storage rings in the cylindrical coordinate system, Phys. Rev. ST Accel. Beams 9, 034003 (2006).


# Preserve, Promote, or Attack? GNN Explanation via Topology Perturbation

Yi Sun
MIT
<EMAIL_ADDRESS>Abel Valente
IBM Research
<EMAIL_ADDRESS>Sijia Liu
Michigan State University
<EMAIL_ADDRESS>Dakuo Wang
IBM Research
<EMAIL_ADDRESS>
###### Abstract

Prior works on formalizing explanations of a graph neural network (GNN) focus
on a single use case — to Preserve the prediction results through identifying
important edges and nodes. In this paper, we develop a multi-purpose
interpretation framework by acquiring a mask that indicates topology
perturbations of the input graphs. We pack the framework into an interactive
visualization system (GNNViz) which can fulfill multiple purposes: Preserve,
Promote, or Attack GNN’s predictions. We illustrate our approach’s novelty and
effectiveness with three case studies: First, GNNViz can assist non expert
users to easily explore the relationship between graph topology and GNN’s
decision (Preserve), or to manipulate the prediction (Promote or Attack) for
an image classification task on MS–COCO; Second, on the Pokec social network
dataset, our framework can uncover unfairness and demographic biases; Lastly,
it compares with state-of-the-art GNN explainer baseline on a synthetic
dataset.

Figure 1: Illustration of GNNViz visual analysis on MS-COCO dataset with
Preserve, Promote, and Attack.

##  1 Introduction

Graph neural network (GNN) is increasingly adopted in various applications for
analyzing data with graph structures (e.g., social network and molecule),
where the graph can be represented as a set of entities (namely, nodes) and a
collection of relationships (namely, edges) between these entities [38, 47,
20, 35, 41]. However, in real-world applications, the users of such GNN-based
models also need to understand why and how a model makes certain predictions
[45, 25, 16, 39, 4]. Thus, many researchers have worked on designing various
explanation mechanism for GNN-based models [2, 27, 43].

However, existing works fall short for one of the following two reasons: the
graph topology as a characteristic signature of GNN has not been well studied
in the GNN explanation literature; and the existing works primarily target GNN
experts to analyze the model, thus they do not provide an easy-to-use tool for
non-expert end users to fulfill their multi-purpose user needs. In this paper,
we aim to answer the two research questions: Can we build an interpretation
algorithm to reveal to what degree the graph topology structure affects the
cause of GNN’s prediction? Can we implement an interactive visualization
system so that the end user can use it to interpret and alternate the GNN
predictions?

The key to answer the first question is that, different from the existing
interpretation mechanisms leveraging only the continuous input node features
[2, 27], the graph topology is typically discrete Boolean-valued input, which
poses combinatorial complexity when analyzing the sensitivity of GNN’s
prediction to the topology variations. One recent relevant work GNNExplainer
[43] has to cast the GNN explanation problem with respect to the input graph
as a graph learning task. Then, identifying an explainable sub-graph is
equivalent to maximizing the mutual information between the original GNN’s
prediction and predictions of all possible sub-graph candidates. However,
their approach can only work for the single interpretation use case (we refer
it as Preserve mode), but in real-world use cases, people also have the needs
to change the prediction results to improve it (Promote mode) or to defend
potential attacks (Attach mode). To accommodate all the three use cases, we
tackle the GNN explanation task through a topology perturbation approach and
design a computationally-effective and multi-purpose GNN explanation
framework.

To address the second research question, we learn from the existing works on
building human-in-the-loop machine learning (HITL ML) systems. Many
interactive visualization systems have been build to interpret and debug NN
models in various scenarios (e.g. face recognition [24], automatons driving
[18], and medical image analysis [22]), so that end users can understand why
the ML system made certain suggestions whether they should trust it in their
decision making. In this work, we follow this line of work to develop the
first interactive visualization system GNNViz for GNN explanation, and
illustrate its effectiveness in a case study with a MS–COCO classification
task. Our contributions are three-fold:

$\bullet$ We propose a general problem formulation and optimization framework
for GNN explanation via the design of sparse edge perturbations.

$\bullet$ We implement the first interactive visualization system GNNViz for
GNN explanation.

$\bullet$ We perform extensive quantitative and qualitative analyses with
three typical GNN tasks (MS–COCO, Pokec social network, and a synthetic data)
to illustrate the novelty of the proposed method over baselines.

##  2 Related work

DNNs are successful to achieve or even exceed human-level performance on many
complex tasks. However, due to their black-box nature, it is generally
difficult to understand why DNNs make certain decisions. Typically, there are
two approahces to explain DNN: the model-specific and model-agnostic
explanation approaches [25, 16, 39, 4]. The model-specific explanation
approach [28, 39] creates a naturally-explainable model, such as decision
trees or sparse linear or polynomial models, to mimic a DNN model as the
explanation. Model distillation [39] is one commonly-used strategy that learns
a specific and inherently explainable machine learning model to mimic the
input-output behavior of a target black-box DNN model. By contrast, model-
agnostic explanation methods do not creating specific interpretable models for
a given DNN model. Instead, these approahces target the trained models (post
hoc) [4]. For example, input attribution map (IAM) [1] is one well-established
approach, which is to identify the aspects from the input data that drive the
decisions of the DNN. Our research on GNN explanation follows the IAM line of
work.

#### DNN explanation via IAM.

In visual recognition tasks, IAM has been widely used to assign importance
scores to individual input features towards explaining a classification
decision about this input. IAM can roughly be classified into two types:
Jacobian saliency map [30, 32, 31, 33, 46, 29, 9] and class-discriminative
perturbation mask [44, 26, 14, 13]. The former often calls input gradient to
characterize the sensitivity of a model’s decision to feature variations.
Examples include Vanilla Gradient [30], Guided Backpropogation [32],
SmoothGrad [31], Integrated Gradient [33, 46], GradCAM [29], and GradCAM++
[9]. By contrast, class-discriminative perturbation mask directly localizes
sparse input features or image regions that maximally affect a model’s output.
Compared with Jacobian saliency map, class-discriminative perturbation mask is
ease of localizing the input sparse patterns, where a decision maker focuses
on. Examples include Occlusion [44], RISE [26], Mask [14], and Smooth Mask
[13].

#### GNN explanation.

The GNN’s input can be considered as a graph topology and its node-wise input
features. Some recent works [2, 27] have extended Jacobian saliency map to
reveal the influence of node features on GNN’s prediction. However, little
work studied GNN explanation using the graph topology (except the recent
GNNExplainer [43]). Since a graph topology is typically binary-valued, to use
the graph topology would introduce combinatorial complexity when tracking the
prediction change by flipping individual edges on and off. Such complexity
makes the construction of topological saliency map very challenging. To walk
around this challenge, GNNExplainer[43] consider the GNN explanation as a task
to find the class-discriminative perturbation mask. That is, extracting a
subgraph that contributes most to a GNN’s prediction by maximizing the mutual
information between a GNN’s prediction and predictions conditioned on possible
subgraph structures.

Besides the factual GNN explanation (Preserve and Promote modes) [2, 27, 43],
another line of research relevant to ours is adversarial perturbation against
graph topology in GNN [49, 12, 48, 40]. It was shown that a small amount of
edge perturbations (e.g., edge addition or removal) can easily fool a well-
trained GNN for an erroneous prediction. The method of generating adversarial
topology perturbation provides a means of counterfactual explanation (Attack
mode). It finds a similar graph tpology by changing some of the edges for
which the predicted outcome of GNN changes in an adversarial way (namely, a
flip in the predicted class).

In this paper, we aim to develop a unified GNN explanation method and a visual
analytics system. Existing literature on visual analytics systems for model
explanation [8, 3, 37, 36] also inspire our work. For example, Activation
Atlas visualizes neuron activations of a convolutional neural network (CNN)
via feature inversion [8].

##  3 Problem statement

In this section, we present the problem of GNN explanation by seeking topology
attributions, which can shed light on the effect of graph topology (input) on
the GNN’s prediction (ouput). We also revisit the direct application of
Jacobian saliency map to GNN explanation, and explore its connection to
topology attributions of our interest.

#### Preliminaries on GNN.

Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ denote a graph, where
$\mathcal{V}$ is the vertex (or node) set with cardinality $|\mathcal{V}|=N$,
and $\mathcal{E}\in(\mathcal{V}\times\mathcal{V})$ denotes the edge set. The
topology of $\mathcal{G}$ is represented by its adjacency matrix $\mathbf{A}$,
where $A_{ij}=1$ if $(i,j)\in\mathcal{E}$, and $0$ otherwise. Each node
$i\in\mathcal{V}$ in $\mathcal{G}$ is associated with a node feature vector
$\mathbf{x}_{i}\in\mathbb{R}^{M_{0}}$. The goal of GNN is to learn a graph
representation used for downstream classification based on the graph topology
$\mathbf{A}\in\mathbb{R}^{N\times N}$ and the node features
$\mathbf{X}=[\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{N}]^{T}\in\mathbb{R}^{N\times
M_{0}}$.

Formally, a GNN of $L$ layers obeys the following layer-wise propagation rule
[20, 42]

$\displaystyle\mathbf{H}^{(l)}=\sigma\left(\tilde{\mathbf{A}}\mathbf{H}^{(l-1)}\mathbf{W}^{(l)}\right),\quad
l\in[L],$ (1)

where $\mathbf{H}^{(l)}\in\mathbb{R}^{N\times M_{l}}$ denotes the graph
representation at the $l$th layer with $\mathbf{H}^{(0)}=\mathbf{X}$,
$\sigma(\cdot)$ is the element-wise activation function,
$\mathbf{W}^{(l)}\in\mathbb{R}^{M_{l-1}\times M_{l}}$ represents the model
weights at the $l$th layer, $[L]$ denotes the integer set
$\\{1,2,\ldots,L\\}$, and $\tilde{\mathbf{A}}$ is a normalized adjacency
matrix
$\tilde{\mathbf{A}}=\hat{\mathbf{D}}^{-1/2}\hat{\mathbf{A}}\hat{\mathbf{D}}^{-1/2}$.
Here $\hat{\mathbf{A}}=\mathbf{A}+\mathbf{I}$, and $\hat{\mathbf{D}}$ is the
degree matrix of $\tilde{\mathbf{A}}$.

A classification head is then introduced over the graph representation
$\mathbf{H}^{(L)}$ acquired using (1) to make node-wise or graph-wise
classification decisions. Together with labels of training data, a cross-
entropy loss $\ell(\mathbf{W};\mathbf{A})$ is then minimized for seeking the
optimal GNN parameters $\mathbf{W}=\\{\mathbf{W}^{(l)}\\}_{l\in[L]}$. Here for
ease of presentation, we omit the dependence of $\ell$ on node features
$\mathbf{X}$ and training labels except its dependence on the graph topology
$\mathbf{A}$.

#### GNN explanation: A warm-up on Jacobian saliency map.

Jacobian saliency map (JSM) is one of the most straightforward approaches,
which assigns importance scores to individual input features toward explaining
a model’s decision. The application of JSM to GNN has been explored with
respect to (w.r.t) node features [2, 27]. Here we revisit it from a graph
topology perspective.

Given a well-trained GNN $\mathbf{W}^{*}$ (which minimizes
$\ell(\mathbf{W};\mathbf{A})$) and a specific input pair
$(\mathbf{X},\mathbf{A})$, let $p_{c}(\mathbf{A};\mathbf{W}^{*},\mathbf{X})$
denote the prediction score of class $c$ for the learned GNN at input
$\mathbf{X}$ and $\mathbf{A}$. The goal is to seek (explainable) topology
attributions that can reveal the effect of $\mathbf{A}$ on prediction
$p_{c}(\mathbf{A};\mathbf{W}^{*},\mathbf{X})$. From the perspective of JSM,
the topology attribution map can be cast as

$\displaystyle\mathbf{J}\mathrel{\mathop{:}}=\frac{\partial
p_{c}(\mathbf{A};\mathbf{X},\mathbf{W}^{*})}{\partial\mathbf{A}},$ (2)

where $\frac{\partial p_{c}}{\partial\mathbf{A}}$ denotes the gradient
operation w.r.t. $\mathbf{A}$. Besides the generation of topology
attributions, the problem formulation and approaches proposed in our work are
also applicable to generating node feature attributions of a GNN.

The rationale behind JSM (2) can be drawn by solving the following prediction
maximization problem w.r.t. a topology perturbation variable $\bm{\Delta}$,

$\displaystyle\begin{array}[]{ll}\displaystyle\operatorname*{\text{maximize}}_{\|\bm{\Delta}\|_{\infty}\leq\epsilon}&p_{c}(\mathbf{A}+\bm{\Delta};\mathbf{X},\mathbf{W}^{*}),\end{array}$
(4)

where $\epsilon$ is the radius of an $\ell_{\infty}$-norm based perturbation
ball. By Taylor expansion, we obtain

$\displaystyle p_{c}(\mathbf{A}+\bm{\Delta};\mathbf{X},\mathbf{W}^{*})\approx
p_{c}(\mathbf{A};\mathbf{X},\mathbf{W}^{*})+\langle\bm{\Delta},\mathbf{J}\rangle,$
(5)

where $\langle\cdot,\cdot\rangle$ is the inner product operation. By
maximizing (4) with the first-order approximation (5), the solution is

$\displaystyle\bm{\Delta}=\epsilon\times\mathrm{sign}(\mathbf{J}),$ (6)

where $\mathrm{sign}(\cdot)$ is the element-wise sign operation.

The implications of JSM can then be acquired from its connections to the
topology perturbation $\bm{\Delta}$ via (6). First, the positive entries of
$\mathbf{J}$ provide a factual explanation of edge attributions:

$\bullet$ If $J_{ij}>0$, namely, $\Delta_{ij}>0$ in (6), then the promotion of
edge attribution from $A_{ij}$ to $A_{ij}+\Delta_{ij}$ contributes to
prediction maximization. $J_{ij}$ denotes the $(i,j)$th entry of $\mathbf{S}$.

Second, $-\bm{\Delta}$ can be regarded as adversarial perturbation [17, 23]
for prediction minimization by solving problem (4) with the objective function
$-p_{c}(\mathbf{A}+\bm{\Delta};\mathbf{X},\mathbf{W}^{*})$. Thus, the negative
entries of $\mathbf{J}$ provide a counterfactual explanation:

$\bullet$ If $J_{ij}<0$, namely, $-\Delta_{ij}>0$ in (6), then the promotion
of edge attribution from $A_{ij}$ to $A_{ij}-\Delta_{ij}$ minimizes prediction
accuracy, namely, causes the vulnerability of GNN against the edge-wise
adversarial attack [49, 12, 48, 40].

Although the continuous-valued JSM (2) provides interesting insights on
factual and counterfactual explanation of edge attributions, it has been shown
in [43] that JSM cannot accurately characterize the impact of the discrete-
valued graph topology $\mathbf{A}$ on GNN’s prediction. The GNN explanation
method proposed in [43] is most relevant to ours. However, it was restricted
to seeking a sub-graph of $\mathbf{A}$ for factual explanation only, and it
called a computationally-intensive mutual information based optimizer. Spurred
by these limitations, we ask: Is it possible to develop a unified and
computationally-efficient approach for multi-purpose GNN explanation? We
tackle this problem in next section.

##  4 Methodology of multi-purpose explanation

In this section we devise the topology attribution map for GNN explanation
from topology perturbations perspective.

#### General idea.

Given the binary adjacency matrix $\mathbf{A}$, (with zeros in the diagonal),
its supplement is given by
$\bar{\mathbf{A}}=\mathbf{1}\mathbf{1}^{T}-\mathbf{I}-\mathbf{A}$, where
$\mathbf{I}$ is an identity matrix, and
$(\mathbf{1}\mathbf{1}^{T}-\mathbf{I})$ corresponds to the fully-connected
graph. All the possible edge perturbation candidates (addition and removal)
are then given by $\mathbf{C}=\bar{\mathbf{A}}-\mathbf{A},$ where the diagonal
entries of $\mathbf{C}$ are zeros, and its off-diagonal entries are within
$\\{-1,1\\}^{N\times N}$. The negative entry of $\mathbf{C}$ denotes the
existing edge that can be removed from $\mathbf{A}$, and the positive entry of
$\mathbf{C}$ denotes the new edge that can be added to the graph $\mathbf{A}$.
Thus, $\mathbf{C}$ is decomposed as

$\displaystyle\mathbf{C}=\mathbf{C}^{\mathrm{-}}+\mathbf{C}^{\mathrm{+}},~{}\mathbf{C}^{\mathrm{-}}\leq
0,~{}\mathbf{C}^{\mathrm{+}}\geq 0,$ (7)

where $\mathbf{C}^{\mathrm{-}}$ (or $\mathbf{C}^{\mathrm{+}}$) characterizes
the non-positive (or non-negative) entries of $\mathbf{C}$.

Based on (7), we then introduce two Boolean edge selection variables
$\mathbf{S}^{\mathrm{-}}$ and $\mathbf{S}^{\mathrm{+}}$ associated with
$\mathbf{C}^{\mathrm{-}}$ and $\mathbf{C}^{\mathrm{+}}$, respectively. Here
$\mathbf{S}^{\mathrm{-}}$ (or $\mathbf{S}^{\mathrm{+}}$) maintains zero
entries of the same positions as $\mathbf{C}^{\mathrm{-}}$ (or
$\mathbf{C}^{\mathrm{+}}$). And $S^{\mathrm{-}}_{ij}=1$ if the edge $(i,j)$ is
selected for removing from $\mathbf{A}$, and $0$ otherwise. Similarly,
$S^{\mathrm{+}}_{ij}=1$ if the edge $(i,j)$ is selected for adding to
$\mathbf{A}$, and $0$ otherwise. With the aid of $\mathbf{S}^{\mathrm{-}}$ and
$\mathbf{S}^{\mathrm{+}}$, the topology attribution map is modeled by the
perturbed graph

$\displaystyle\mathbf{A}^{\prime}(\mathbf{S})=\mathbf{A}+\mathbf{C}^{\mathrm{-}}\circ\mathbf{S}^{\mathrm{-}}+\mathbf{C}^{\mathrm{+}}\circ\mathbf{S}^{\mathrm{+}},$
(8)

where $\mathbf{S}=[\mathbf{S}^{\mathrm{-}},\mathbf{S}^{\mathrm{+}}]$
summarizes the edge manipulation operations, and $\circ$ represents the
element-wise product. Our goal is to seek the optimized $\mathbf{S}$ such that
$\mathbf{A}^{\prime}(\mathbf{S})$ encodes the edges that contribute most to
the GNN’s prediction.

#### Sparsity-promoting optimization.

We cast the problem of graph explanation as a sparsity-promoting optimization
problem over the perturbation variables
$\mathbf{S}=[\mathbf{S}^{\mathrm{-}},\mathbf{S}^{\mathrm{+}}]$,

$\displaystyle\begin{array}[]{ll}\displaystyle\operatorname*{\text{maximize}}_{\mathbf{S}}&\mathcal{R}(\mathbf{A}^{\prime}(\mathbf{S});\mathbf{X},\mathbf{W}^{*})+\lambda_{1}\|\mathbf{S}^{\mathrm{-}}\|_{1}-\lambda_{2}\|\mathbf{S}^{\mathrm{+}}\|_{1}\\\
\operatorname*{\text{subject to}}&S_{ij}\in[0,1],\forall i,j,\end{array}$ (11)

where $\mathcal{R}$ denotes a utility function to measure the GNN’s prediction
performance under a perturbed graph $\mathbf{A}^{\prime}(\mathbf{S})$,
$\lambda_{1}>0$ (or $\lambda_{2}>0$) is a regularization parameter to strike a
balance between the prediction performance and the number of removed edges (or
the number of added edges), the original Boolean variable $S_{ij}\in\\{0,1\\}$
is relaxed to its convex hull $S_{ij}\in[0,1]$ for ease of optimization, and
$\ell_{1}$ norms are introduced in the objective function for promoting the
sparsity of $\mathbf{A}^{\prime}(\mathbf{S})$. In (11), if $\gamma_{1}$ and
$\gamma_{2}$ increase, then the sparsity of $\mathbf{A}^{\prime}(\mathbf{S})$
increases as the larger $\|\mathbf{S}^{-1}\|_{1}$ indicates removing more
edges and the smaller $\|\mathbf{S}^{+}\|_{1}$ corresponds to adding less
edges. Since $\mathbf{S}$ are non-negative,
$\|\mathbf{S}^{\mathrm{-}}\|_{1}=\mathbf{1}^{T}\mathbf{S}^{\mathrm{-}}\mathbf{1}$
and
$\|\mathbf{S}^{\mathrm{+}}\|_{1}=\mathbf{1}^{T}\mathbf{S}^{\mathrm{+}}\mathbf{1}$.
As a result, problem (11) can efficiently solved using a continuous
optimization solver, e.g., projected gradient descent.

We remark that once the continuous optimization problem (11) is solved, one
can regard the resulting $\mathbf{S}$ as a probability matrix with elements
drawn from Bernoulli distributions. Thus, a hard thresholding operation (e.g.,
compared with $0.5$) or a randomized sampling method can be called to map a
continuous solution to its discrete domain [5].

Moreover, in node classification task, this formulation can be adapted to
provide explanations for a subset $\Theta$ containing $m$ nodes. In this case,
the utility function in problem (11) becomes
$\frac{1}{m}\sum_{i=1}^{m}\mathcal{R}(\mathbf{A}^{\prime}(\mathbf{S});\mathbf{X}_{i},\mathbf{W}^{*})$,
where $\mathbf{X}_{i}$ indicate features of node $i$. This formulation can be
particular useful for providing explanations on the group level.

Lastly, we note that GNNExplainer [43] can be regarded as a special case of
(11) by excluding the case of edge addition, namely, imposing
$\mathbf{S}^{\mathrm{+}}=\mathbf{0}$. In this case, the perturbed graph
$\mathbf{A}^{\prime}(\mathbf{S})$ encodes a sub-graph of the original graph
$\mathbf{A}$ by only allowing edge removals based on the perturbation scheme
$\mathbf{S}^{\mathrm{-}}$.

####  Preserve, Promote and Attack mode.

Based on the choice of the utility function $\mathcal{R}$ in (11), we can use
the same formulation to achieve GNN explanation for three use cases: (1)
preserving the original predictions, (2) correcting the original predictions,
and (3) attacking the original predictions. We call these three different
modes Preserve, Promote, and Attack.

Preserve mode seeks the sparse graph pattern
$\mathbf{A}^{\prime}(\mathbf{S})$, which provides factual GNN explanation.
Toward this goal, we choose the utility function $\mathcal{R}$ as the negative
cross-entropy between the original predicted classes and the predicted classes
under perturbed topology:

$\displaystyle\mathcal{R}(\mathbf{A}^{\prime}(\mathbf{S});\mathbf{X},\mathbf{W}^{*})=$
$\displaystyle\sum_{c\in\Omega}y_{c}\log
p_{c}(\mathbf{A}^{\prime}(\mathbf{S});\mathbf{X},\mathbf{W}^{*}),$ (12)

where $\Omega$ is the set of original prediction labels.

Promote mode aims to fix GNN’s wrong predictions. Mathematically, the goal is
to seek a sparsity-promoting topology $\mathbf{A}^{\prime}(\mathbf{S})$ so
under this perturbed topology, the model predicts the desired set of
prediction labels with higher probability compared to other alternative
labels. This goal can be modeled with C&W-type objective function [7]:

$\displaystyle\mathcal{R}(\mathbf{A}^{\prime}(\mathbf{S});\mathbf{X},\mathbf{W}^{*})=$
$\displaystyle\min\left\\{\min_{c\in\Omega}p_{c}(\mathbf{A}^{\prime}(\mathbf{S});\mathbf{X},\mathbf{W}^{*})\right.$
$\displaystyle\left.-\max_{t\notin\Omega}p_{t}(\mathbf{A}^{\prime}(\mathbf{S});\mathbf{X},\mathbf{W}^{*}),\kappa\right\\},$
(13)

where $\Omega$ is the set of desired prediction labels, and $\kappa\geq 0$ is
a given confidence level. The rational behind (4) is that the maximization of
$\mathcal{R}$ would force the margin of correct prediction
$\min_{c\in\Omega}p_{c}(\mathbf{A}^{\prime}(\mathbf{S});\mathbf{X},\mathbf{W}^{*})-\max_{t\notin\Omega}p_{t}(\mathbf{A}^{\prime}(\mathbf{S});\mathbf{X},\mathbf{W}^{*})$
to reach the confidence level $\tau$. This also implies
$p_{c}(\mathbf{A}^{\prime}(\mathbf{S});\mathbf{X},\mathbf{W}^{*})\geq
p_{t}(\mathbf{A}^{\prime}(\mathbf{S});\mathbf{X},\mathbf{W}^{*})$ for any
$c\in\Omega$ and $t\notin\Omega$, namely, the obtained
$\mathbf{A}^{\prime}(\mathbf{S})$ promotes the set of desired labels. Note
that this formulation can also be used for the purpose of preserving
predictions, though we observe (12) is more straightforward and performs
better in practice.

Attack mode aims for counterfactual explanation: We seek the most sensitive
edges to adversarial attacks, thus altering them would successfully fool a
GNN. We thus modify the objective function (4) to

$\displaystyle\mathcal{R}(\mathbf{A}^{\prime}(\mathbf{S});\mathbf{X},\mathbf{W}^{*})=$
$\displaystyle\min\left\\{\max_{t\notin\Omega}p_{t}(\mathbf{A}^{\prime}(\mathbf{S});\mathbf{X},\mathbf{W}^{*})\right.$
$\displaystyle\left.-\max_{c\in\Omega}p_{c}(\mathbf{A}^{\prime}(\mathbf{S});\mathbf{X},\mathbf{W}^{*}),\kappa\right\\}.$
(14)

In contrast to (4), the maximization of (4) forces
$\max_{t\notin\Omega}p_{t}(\mathbf{A}^{\prime}(\mathbf{S});\mathbf{X},\mathbf{W}^{*})\geq(p_{c}(\mathbf{A}^{\prime}(\mathbf{S});\mathbf{X},\mathbf{W}^{*})+\kappa)$
for any $c\in\Omega$. This implies that under the perturbed graph
$\mathbf{A}^{\prime}(\mathbf{S})$, there exists an incorrect prediction
$t\notin\Omega$ with $\kappa$ higher confidence over all the true labels
$\\{c\in\Omega\\}$.

##  5 Experiments and quantitative analysis

In this section, we set up experiments to quantitatively analyze the empirical
performance of the topology attribution map $\mathbf{A}^{\prime}(\mathbf{S})$
obtained by solving problem (11). We show how
$\mathbf{A}^{\prime}(\mathbf{S})$ characterizes an explanatory topology (mask
on the original graph) can encode essential edges to preserve, promote, or
adversarially altering the prediction (attack) a well-trained GNN.

###  5.1 Experiment tasks setup

####  Task1: GCN-based image classification .

We use the image classification task on MS–COCO dataset [21] as an
illustration, and a well-cited GCN-based multi-label classification model [10]
as the target model for explanation, but our explanation framework and GNNViz
system are applicable to other GNN models and datasets as well. Unlike
previous approaches that treat each object classifier as independent, [10]
proposes to use a graph convolutional network (GCN) to capture the label
correlations (Appendix Fig.A1). The ground-truth adjacency matrix is generated
by computing the co-occurence probability of labels in the training set. We
evaluate the explanation results of the three modes on a subset of validation
dataset with 5500 images, used in[10].

####  Task2: Bias detection in a social network dataset.

Biases in social network stems from the fact that people tend to connect with
those sharing similar sensitive characteristics, and the use of GNN could
further reinforce such biases.

Pokec [34] is a popular online social network dataset with millions of user
profile data in Slovakia. The profile data contains gender, age, hobbies,
interest, professions, which is a good candidate to examine biases existed in
GNN. We randomly extract a subset of 67,796 nodes from the Pokec dataset based
on a user’s region information. The target model’s prediction task is to
predict the professions of the users [11], we treat region (e.g., low-income,
high-income) as a sensitive attribute.

####  Task3: Benchmark on synthetic dataset.

To benchmark the quality of explanations, we aslo use the node classification
synthetic datasets defined in [43]. Each dataset is constructed by attaching
meaningful motifs (house, cycle, grid) to a synthetic base graph, and the
motifs are treated as ground-truth topology attribution map. Note this dataset
can only benchmark the preserve mode explanation, whereas the promote and
attack modes are not investigated in prior studies.

#### Implementation details.

During learning of the explanation masks, we adopt Adam as the optimizer
running over $200$ steps with learning rate $0.1$. For Task3, we choose the
regularization parameters $\lambda_{1}=0.005$ and $\lambda_{2}=0$, and the
confidence tolerance $\kappa=0.4$. For Task1 and Task2, we use $\kappa=0.2$
for all three modes, $\lambda_{1}=0.001$ and $\lambda_{2}=0.0005$ for promote
and attack modes.

In order to evaluate the explanation mask, we only keep the top edges in the
attribution mask. In preserve mode, we keep the top 10 edges in the final
explanation mask. In promote mode, we seek to make the prediction correct by
allowing a maximum of 5 edge additions. For attack mode, we allow a maximum of
5 edge removals and 5 edge additions to make top-1 label wrong.

###  5.2 Task1: GCN-based image classification

#### Evaluation metrics.

Although ground-truth explanations are usually unavailable, we can still
quantitatively measure the effectiveness of the explanation methods by
defining following evaluation metrics:

$\bullet$ Accuracy (ACC) : For Preserve mode, we measure accuracy as the
consistency between prediction on the whole graph and the explanation
subgraph. For promote and attack mode as the mean average precision (mAP) of
the top 3 predicted labels.

$\bullet$ Explanation Quality (EQ): For the multi-label classification
problem, explanation quality captures whether the explanation mask could
identify edges between relevant labels. Further detailed formulation are in
Appendix.

#### Experiment results.

In Table-1, we present the effectiveness of our algorithm on Task1. As we can
see, all of the three modes are successful in achieving their respective
goals.Preserve mode maintains $95.67\%$ of the original prediction. The
original model prediction reaches mAP of $83.0\%$, and the promote and attack
mode is able to increase and decrease mAP, respectively.

In terms of explanation quality, the sparse explanation graph in preserve is
able to identify $62.8\%$ of the edges connecting predicted labels. Figure-2
demonstrates that edge additions proposed by promote mode statistical
significantly increase connectivity between true labels.

Mode | Preserve | Promote | Attack
---|---|---|---
Accuracy | $95.67\%$ | $90.36\%$ | $25.18\%$

Table 1: Quantitative results for Task1. For preserve, accuracy measures the
mAP w.r.t the original predicted labels. For promote mode and attack, accuracy
measures the mAP w.r.t the true labels.

Figure 2:  The x-axis is the number of edge additions, and y-axis is the
$P$-value $\times 100\%$. The dashed line indicates statistically significance
line ($P$-value=$0.05$). the Left: 0-hop neighborhood (immediate neighbors) of
true labels. Right: 1-hop neighborhood of true labels. The result demonstrates
that the edge addition proposed by our method statistical significantly
increases connectivity between true labels.

###  5.3 Task2: Bias detection in social network dataset

GNN’s prediction may have fairness issues in a social network dataset. Can
interventions (adding artificial edges) correct GNN’s prediction biases? We
show the using promote explanation mode can be used to address this question.

#### Evaluation metrics.

We use the absolute difference of Equalized Odds ($\Delta EO$) [19] to measure
the fairness loss of GCN’s prediction. Let $s\in\\{0,1\\}$ denotes the binary
sensitive label, $y$ and $\hat{y}$ indicates the true label and the predicted
label respectively. Fairness loss can be measured as:

$\Delta EO=|\mathbb{P}(\hat{y}=1|y=1,s=0)-\mathbb{P}(\hat{y}=1|y=1,s=1)|$

After training for 200 epoches, the GCN model is able to achieve 71.3% test
accuracy, with $\Delta EO=0.103$, indicating that there is a discrepancy when
predicting users come from the majority group and the minority group.

#### Experiment results.

Figure 3: An example graph identifying the sources of biases in Pokec dataset.
For both user 1 (majority group) and user 2 (minority group), their intra-
group connections are highlighted in the explanation mask.

We first illustrate how our explanation framework helps to identify the source
of biases existed in GNN’s prediction. In Figure-3, a green node indicates GNN
predicts the node’s label (profession) correctly, and a red node indicates a
wrong prediction. The shape of a node indicates their group (square represents
the minority class based on the region sensitive attribute). As shown in the
graph, there are more intra-group edges than inter-group edges. In addition,
intra-group edges are also more important in GNN’s prediction and more likely
to be highlighted in the explanation mask. This further exaggerates GNN’s
performance discrepancy on majority group and minority group.

In Table-2, we also show how accuracy and equalized odds changes as we add
more edges to the adjacency matrix. As expected, as we add more inter-group
edges to network, the discrepancy of equalized odds decrease with a slight
decrease in accuracy.

# edges | n=50 | n=100 | n=500 | n=1000 | n=5000
---|---|---|---|---|---
ACC | 0.713 | 0.712 | 0.712 | 0.703 | 0.676
$\Delta EO$ | 0.103 | 0.101 | 0.097 | 0.093 | 0.052

Table 2: Experiment results on Task3. ACC and $\Delta EO$ as the number of
added edges increases in adjacency matrix.

###  5.4 Task3: Benchmark on synthetic dataset

Lastly, the evaluation experiment in Task3 is a classification task, where the
predicted scores are the importance weights in the explanation mask of the
ground-truth graph [43]. The explanation accuracy is measured by the AUC score
of the classification task. We compare the explanation accuracy with two
baselines: gradient-based saliency map (Grad) and GNNExplainer [43]. Note that
both baselines only consider factual explanation, thus we are only able to
compare accuracy in preserve mode. As shown in Figure-4, and Table-3, Our
method is able to correctly identify the motifs and achieve similar
explanation accuracy as GNNExplainer and significantly outperforms Grad.
Although its accuracy is slightly worse in comparison to GNNExplainer, but our
algorithm is not optimized solely for this single metric and preserve mode,
thus our approach can provide a satisfying performance on this metric while
being more flexible in supporting additional use cases and insights.

Figure 4: Example of identified cycle-shaped motifs for Tree-Cycles.Left:
Grad. Middle: GNNExplainer. Right: Ours.

Method | BA-Shapes | Tree-Cycles | Tree-Grid
---|---|---|---
Grad | $0.882$ | 0.905 | 0.667
GNNExplainer | $0.925$ | 0.948 | 0.875
Ours | $0.902$ | 0.921 | 0.836

Table 3: Explanation accuracy on synthetic dataset with different motifs.

##  6 Interactive visualization system GNNViz and qualitative visual analytics

Figure 5:  GNNViz System on MS–COCO data analysis. To the top-left, the system
shows the image input, the groundtruth label, prediction label, and the
updated labels when user changes the graph topology. To the bottom-left, it
allows users to alternate among the three models (currently on Promote mode).
To the right, it shows the identified subgraph (solid black lines) on top of
the global graph (translucent), and the suggested two links to add in the
Promote mode (in green dash lines).

We build GNNViz system to enable non-expert end users to easily leverage on
our explanation algorithm to fulfill their multiple user purposes. As shown in
Fig.5, the system has functionalities that allow a user to quickly navigate
through the data points of a dataset, examine the data’s groundtruth labels,
and interpret the GNN predictions in three modes. A more detailed description
is in Appendix.

In this section, we use only Task1: GCN-based image classification on MS–COCO
[10] as an illustration of how the end users can perform qualitative analytics
in three modes with GNNViz system, but our system can support other GNN models
and datasets as well. The majority space of UI is dedicated to the global
graph topology. The global graph topology map in this case is calculated from
the label co-occurence probability from the entire training dataset. Thus,
each node in the graph represents a label, and each directed edge represents
an co-occurence relationship. The edges are binary, with a threshold of
conditional probability at 0.4, as suggested by the original paper [10].

The default user mode is preserve mode. The preserve mode falls into the
factual explanation use case – the explanation algorithm identifies a less
complex subgraph for prediction, but still try to maintain the best prediction
performance as using the original global graph topology. The second user mode
is promote mode, and it is illustrated in Fig.5. The promote mode is also for
the factual explanation user scenario. Our GNNViz algorithm can suggest new
edges to add into the graph topology and promote the correct prediction
results. The third user mode is attack mode. In contrary to the previous two
user modes, this mode is to visualize the counterfactual explanation user
scenarios. GNNViz can recommend the minimal edge changes (both edge addition
and deletion) to attack the GCN prediction algorithm – manipulate the updated
prediction results to move away from the correct predictions. It uses green
dash lines to indicate the edge addition, and uses red solid lines to indicate
edge removal, as shown in Fig. 1.

The layout of this graph (Fig. A2 C) uses a force-directed graph layout [15]
and the implementation uses a D3.js javascript library [6].

###  6.1 Visual analytics: case study on Task1

The model builders and model users can use the GNNViz visualization system to
interpret why a graph-based model produces certain correct or incorrect
predictions. This is considered as the factual explanation use case. In
addition, there is also a counterfactual explanation use case. That some other
users may be more interested in the adversarial robustness of a graph-based
model, thus they want to identify the vulnarability points of a GNN model
through attacking its graph topology. In this section, we use one example
(Fig.1) to illustrate how GNNViz system can support the multiple user
scenarios. In Appendix, we attach more example images. And upon paper
acceptance, GNNViz will be publicly available.

As shown in Fig.1, we present one image’s three modes (each in a column). The
first column presents the raw image, its groundtruth label, and its prediction
result generated by the GCN model [10] that GNNViz aims to explain. Sometimes
GCN model may generate incorrect predictions. In this example, the GCN model
fails to predict the Handbag label, but mis-predicts an extra Car label.

#### How does the graph topology contribute to a graph-based model’s correct
or incorrect prediction results?

In the Preserve mode, our interpretation algorithm preserves a sparse subgraph
(by default ten edges) to reduce the complexity while still maintaining a
relative good performance. By looking only at the raw images column and the
preserve mode column, we can see that for the data instance, the preserve mode
subgraph successfully captures the most important edge Person–to–Motorcycle in
the topology (thickness). But the GCN model fails to predict Handbag, as the
edge is not in the top-ten edges in the preserved subgraph. It also mis-
predicts the Car label. And the preserve subgraph reflects such misprediction
as it believes the Person–to–Car edge has a high importance level. The user
can further dive into the graph topology and the CNN classifier to examine why
this mistake happens.

#### How to improve a graph-based model’s prediction performance?

In the Promote mode, our interpretation algorithm suggests new edges to add to
the graph to improve the prediction correctness. The GCN model fails to
predict Handbag. Our explanation algorithm correctly suggests to add a
Chair–to–Handbag link to put more weights on Handbag related topology. And if
the user agrees with such suggestion and clicks on that edge in the subgraph,
the GCN model will recalculate the prediction result and successfully predict
the Handbag label. GNNViz set parameter to suggest only one edge to add, but
the user can use UI to interactively change such setting.

#### How to attack a graph-based model?

In the Attack mode, our interpretation algorithm can suggest edges to be added
or deleted from the global graph. The attack mode also targets the global
graph topology. We use the green dash line to indicate the edges suggested to
add, and the red solid line to indicates the edges to be removed. By default,
GNNViz suggests only one edge to add and one edge to remove, but the user can
change this hyperparameter in the control panel via the UI. As shown in Fig.1,
the GCN model initially correctly predicts Motrocycle and Person. The GNNViz
algorithm suggests to add the WineGlass–to–Motorcle link and remove the
Handbag–to–Person link from the graph topology. If the user applies such
suggestions, the GCN model will recalculate the prediction result and
mistakenly believes Wine Glass is the top prediction label.

##  7 Conclusion

In this paper, we develop a multi-purpose system for interpreting topology
attribution of GNN. The underlying algorithm provides a unified formulation
for factual explanation, counterfactual explanation, and universal
explanation. The effectiveness of our proposal has been demonstrated in GNN-
based image classification and social bias detection.

## References

  * [1] Julius Adebayo, Justin Gilmer, Michael Muelly, Ian Goodfellow, Moritz Hardt, and Been Kim.  Sanity checks for saliency maps.  In Advances in Neural Information Processing Systems, pages 9505–9515, 2018.
  * [2] Federico Baldassarre and Hossein Azizpour.  Explainability techniques for graph convolutional networks.  arXiv preprint arXiv:1905.13686, 2019.
  * [3] David Bau, Bolei Zhou, Aditya Khosla, Aude Oliva, and Antonio Torralba.  Network dissection: Quantifying interpretability of deep visual representations.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 6541–6549, 2017.
  * [4] David Bau, Jun-Yan Zhu, Hendrik Strobelt, Agata Lapedriza, Bolei Zhou, and Antonio Torralba.  Understanding the role of individual units in a deep neural network.  Proceedings of the National Academy of Sciences, 2020.
  * [5] Christian Blum and Andrea Roli.  Metaheuristics in combinatorial optimization: Overview and conceptual comparison.  ACM computing surveys (CSUR), 35(3):268–308, 2003.
  * [6] Michael Bostock, Vadim Ogievetsky, and Jeffrey Heer.  D3 data-driven documents.  IEEE transactions on visualization and computer graphics, 17(12):2301–2309, 2011.
  * [7] Nicholas Carlini and David Wagner.  Towards evaluating the robustness of neural networks.  In IEEE Symposium on Security and Privacy (SP), pages 39–57. IEEE, 2017.
  * [8] Shan Carter, Zan Armstrong, Ludwig Schubert, Ian Johnson, and Chris Olah.  Activation atlas.  Distill, 2019.  https://distill.pub/2019/activation-atlas.
  * [9] Aditya Chattopadhay, Anirban Sarkar, Prantik Howlader, and Vineeth N Balasubramanian.  Grad-CAM++: Generalized gradient-based visual explanations for deep convolutional networks.  In 2018 IEEE Winter Conference on Applications of Computer Vision (WACV), pages 839–847. IEEE, 2018.
  * [10] Zhao-Min Chen, Xiu-Shen Wei, Peng Wang, and Y. Guo.  Multi-label image recognition with graph convolutional networks.  2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 5172–5181, 2019.
  * [11] Enyan Dai and Suhang Wang.  Say no to the discrimination: Learning fair graph neural networks with limited sensitive attribute information.  Proceedings of the 14th ACM International Conference on Web Search and Data Mining, 2020.
  * [12] Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song.  Adversarial attack on graph structured data.  arXiv preprint arXiv:1806.02371, 2018.
  * [13] Ruth Fong, Mandela Patrick, and Andrea Vedaldi.  Understanding deep networks via extremal perturbations and smooth masks.  In Proceedings of the IEEE International Conference on Computer Vision, pages 2950–2958, 2019.
  * [14] Ruth C Fong and Andrea Vedaldi.  Interpretable explanations of black boxes by meaningful perturbation.  In Proceedings of the IEEE International Conference on Computer Vision, pages 3429–3437, 2017.
  * [15] Thomas MJ Fruchterman and Edward M Reingold.  Graph drawing by force-directed placement.  Software: Practice and experience, 21(11):1129–1164, 1991.
  * [16] Leilani H Gilpin, David Bau, Ben Z Yuan, Ayesha Bajwa, Michael Specter, and Lalana Kagal.  Explaining explanations: An overview of interpretability of machine learning.  In 2018 IEEE 5th International Conference on data science and advanced analytics (DSAA), pages 80–89. IEEE, 2018.
  * [17] Ian Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  ICLR, 2015.
  * [18] Sorin Grigorescu, Bogdan Trasnea, Tiberiu Cocias, and Gigel Macesanu.  A survey of deep learning techniques for autonomous driving.  Journal of Field Robotics, 37(3):362–386, 2020.
  * [19] Moritz Hardt, E. Price, and Nathan Srebro.  Equality of opportunity in supervised learning.  In NIPS, 2016.
  * [20] T. N. Kipf and M. Welling.  Semi-supervised classification with graph convolutional networks.  arXiv preprint arXiv:1609.02907, 2016.
  * [21] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick.  Microsoft coco: Common objects in context.  In European conference on computer vision, pages 740–755. Springer, 2014.
  * [22] Geert Litjens, Thijs Kooi, Babak Ehteshami Bejnordi, Arnaud Arindra Adiyoso Setio, Francesco Ciompi, Mohsen Ghafoorian, Jeroen Awm Van Der Laak, Bram Van Ginneken, and Clara I Sánchez.  A survey on deep learning in medical image analysis.  Medical image analysis, 42:60–88, 2017.
  * [23] Sijia Liu, Pin-Yu Chen, Xiangyi Chen, and Mingyi Hong.  signSGD via zeroth-order oracle.  In International Conference on Learning Representations, 2019.
  * [24] Iacopo Masi, Yue Wu, Tal Hassner, and Prem Natarajan.  Deep face recognition: A survey.  In 2018 31st SIBGRAPI conference on graphics, patterns and images (SIBGRAPI), pages 471–478. IEEE, 2018.
  * [25] Grégoire Montavon, Wojciech Samek, and Klaus-Robert Müller.  Methods for interpreting and understanding deep neural networks.  Digital Signal Processing, 73:1–15, 2018.
  * [26] Vitali Petsiuk, Abir Das, and Kate Saenko.  Rise: Randomized input sampling for explanation of black-box models.  arXiv preprint arXiv:1806.07421, 2018.
  * [27] Phillip E Pope, Soheil Kolouri, Mohammad Rostami, Charles E Martin, and Heiko Hoffmann.  Explainability methods for graph convolutional neural networks.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 10772–10781, 2019.
  * [28] Cynthia Rudin.  Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead.  Nature Machine Intelligence, 1(5):206–215, 2019.
  * [29] Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra.  Grad-CAM: Visual explanations from deep networks via gradient-based localization.  In Proceedings of the IEEE International Conference on Computer Vision, pages 618–626, 2017.
  * [30] Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman.  Deep inside convolutional networks: Visualising image classification models and saliency maps.  arXiv preprint arXiv:1312.6034, 2013.
  * [31] Daniel Smilkov, Nikhil Thorat, Been Kim, Fernanda Viégas, and Martin Wattenberg.  Smoothgrad: removing noise by adding noise.  arXiv preprint arXiv:1706.03825, 2017.
  * [32] Jost Tobias Springenberg, Alexey Dosovitskiy, Thomas Brox, and Martin Riedmiller.  Striving for simplicity: The all convolutional net.  arXiv preprint arXiv:1412.6806, 2014.
  * [33] Mukund Sundararajan, Ankur Taly, and Qiqi Yan.  Axiomatic attribution for deep networks.  In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pages 3319–3328. JMLR. org, 2017.
  * [34] L. Takac.  Data analysis in public social networks.  2012\.
  * [35] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio.  Graph attention networks.  arXiv preprint arXiv:1710.10903, 2017.
  * [36] Dakuo Wang, Judith S Olson, Jingwen Zhang, Trung Nguyen, and Gary M Olson.  Docuviz: visualizing collaborative writing.  In Proceedings of the 33rd Annual ACM conference on human factors in computing systems, pages 1865–1874, 2015.
  * [37] Daniel Karl I Weidele, Justin D Weisz, Erick Oduor, Michael Muller, Josh Andres, Alexander Gray, and Dakuo Wang.  Autoaiviz: opening the blackbox of automated artificial intelligence with conditional parallel coordinates.  In Proceedings of the 25th International Conference on Intelligent User Interfaces, pages 308–312, 2020.
  * [38] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip.  A comprehensive survey on graph neural networks.  IEEE Transactions on Neural Networks and Learning Systems, 2020\.
  * [39] Ning Xie, Gabrielle Ras, Marcel van Gerven, and Derek Doran.  Explainable deep learning: A field guide for the uninitiated.  arXiv preprint arXiv:2004.14545, 2020.
  * [40] Kaidi Xu, Hongge Chen, Sijia Liu, Pin-Yu Chen, Tsui-Wei Weng, Mingyi Hong, and Xue Lin.  Topology attack and defense for graph neural networks: An optimization perspective.  In International Joint Conference on Artificial Intelligence (IJCAI), 2019.
  * [41] K. Xu, W. Hu, J. Leskovec, and S. Jegelka.  How powerful are graph neural networks?  In ICLR, 2019.
  * [42] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?  In International Conference on Learning Representations, 2019.
  * [43] Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec.  Gnnexplainer: Generating explanations for graph neural networks.  In Advances in neural information processing systems, pages 9244–9255, 2019.
  * [44] Matthew D Zeiler and Rob Fergus.  Visualizing and understanding convolutional networks.  In European conference on computer vision, pages 818–833. Springer, 2014.
  * [45] Quan-shi Zhang and Song-Chun Zhu.  Visual interpretability for deep learning: a survey.  Frontiers of Information Technology & Electronic Engineering, 19(1):27–39, 2018.
  * [46] B. Zhou, A. Khosla, A. Lapedriza, A. Oliva, and A. Torralba.  Learning deep features for discriminative localization.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2921–2929, 2016.
  * [47] Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun.  Graph neural networks: A review of methods and applications.  arXiv preprint arXiv:1812.08434, 2018.
  * [48] Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann.  Adversarial attacks on neural networks for graph data.  In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2847–2856. ACM, 2018.
  * [49] Daniel Zügner and Stephan Günnemann.  Adversarial attacks on graph neural networks via meta learning.  arXiv preprint arXiv:1902.08412, 2019.

##  Appendix A Additional experiment details

For MS-COCO dataset, we use a well-cited GCN-based multi-label classification
algorithm [10] as the target model for explanation, and demonstrate our
interpretation algorithm and the GNNViz system, despite the interpretation
algorithm and GNNViz system are applicable to other GNN algorithms and
datasets. The global graph topology map in this case is calculated from the
label co-occurence probability from the entire training dataset, as shown in
Fig. A1. Thus, each node in the graph represents a label, and each directed
edge represents an co-occurence relationship. The edges are binary, with a
threshold of conditional probability at 0.4, as suggested by the original
paper. A GCN is used to map this global graph to a set of inter-dependent
object classifiers.

Figure A1:  The label dependency map illustration for MS-COCO dataset from the
original GCN algorithm paper [10]. Label_A to Label_B means when Label_A
appears, Label_B is likely to appear. The original paper used 0.4 as the
threshold for the conditional probability to binarize this topology graph, and
we followed their parameter settings.

An useful explanation in this application is to identify the edges in the
global graph that connect labels of interests so the users could understand
when certain labels are predicted together. We define a reasonable explanation
mask as the one that connects relevant labels within $k$-hops. Formally, the
$k$-hop neighbors of adjacency matrix $\mathbf{A}$ is defined as
$(\mathbf{A})^{k}$. Given the prediction label set $\Omega$, we can define the
set of relevant edges as
$\mathcal{S}_{\mathrm{rel}}=\\{(\mathbf{A})^{k}_{i,j}=1,i\in\Omega,j\in\Omega\\}$
and the set of edges in perturbed graph as
$\mathcal{S}_{\mathrm{hit}}=\\{(\mathbf{A}^{\prime}(\mathbf{S})^{k}_{i,j}=1,i\in\Omega,j\in\Omega\\}$

#### Evaluating preserve mode

We measure the explanation quality as the percentage of relevant edges
detected by the algorithm,
$\frac{|\mathcal{S}_{\mathrm{hit}}|}{|\mathcal{S}_{\mathrm{rel}}|}$ As
mentioned in the Section 5.2, the sparse explanation graph in preserve mode is
able to identify 62.8% of the relevant edges connecting predicted labels.

#### Evaluating promote mode

One of the assumption is that suggested edge additions increase probability of
true labels by increasing connectivity between true labels in the adjacency
matrix. To verify it, we calculate the $P$-value of the influence of
recommended perturbed graph on GNN’s prediction against randomly perturbed
graphs. Let $m$ be the number of walks between true labels after adding top
$k$ of the recommended edges. Let $n_{i}$ be the number of walks between true
labels after randomly adding $k$ random edges outside the adjacency matrix (we
call this a realization of a random mask). The $P$-value is then given by the
probability of significance on how the real observation $m$ is located among
the random observations $\\{n_{i}\\}_{i=1}^{1000}$ for $1000$ random trials,
namely, $P(m)=\mathrm{Prob}(m\geq R_{n})$, where $R_{n}$ is a random variable
uniformly drawn from $\\{n_{i}\\}$.

##  Appendix B GNNViz system overview

Figure A2: The User Interface of GNNViz. It has two views: a browser view
(TOP), and a detailed view for a single data instance (BOTTOM).

We design GNNViz as an interactive and multi-purpose visualization system for
interpreting GNN models, as shown in Fig.A2. In this section, we elaborate its
two user views: a browser view (Fig.A2 Top), and a detailed view (Fig.A2
Bottom).

#### Browser View

The browser view is the landing page for a user. It consists with three main
sections: a filter (Fig.A2 A) that allows a user to specify the filtering
condition based on the images’ ground truth labels; a navigation list (Fig.A2
B) that allows users to browse all the data instances; and a graph canvas
(Fig.A2 C) that presents the global graph learned from the entire dataset,
which is agnostic to individual data instances.

The main function of the browser view is to allow a user to quickly navigate
through a large amount of data instances and identify the data instances that
may be of interest to the user. As shown in Fig.A2 B, the list contains each
image, and its groundtruth labels and the targeted GCN algorithm [10]
predicted labels. Noted that the targeted GCN algorithm can have incorrect
predictions. For example, in the presented image example in (Fig.A2 B), GCN
failed to predict the chair label, but add an extra bench label, when compared
to the groundtruth labels.

Different user groups may have different user needs for interpretation, thus
the system allows each individual user to choose which data instances may be
more of interest to them. For example, an non-expert model user may be
interested in understanding only the correct prediction cases, thus he or she
can click on the images that have an accurate prediction result; whereas an
expert GNN model builder may want to understand why the examined GCN algorithm
always fails to predict certain labels, thus he or she can click on those
images to explore further details.

The filter function in Fig.A2 A is to further ease such user navigation. In
the demonstrated MS-COCO dataset, there are hundreds of thousands image data
instances, and it is really hard for a user to manually browse through all the
images, thus they can use the filter function to limit the UI to show only a
subset of images based on their groundtruth labels. The filter function also
support AND operation when a user enters more than one label as the filtering
criteria, thus it can further helps users to navigate through large datasets
like the demonstrated MS-COCO.

The majority space of the browser view UI is dedicated to the global graph
topology. This global graph topology can be considered as equivalent to a
knowledge graph that contains the domain knowledge of the MS-COCO dataset. By
nature, this knowledge graph is agnostic to individual data instances. In the
original paper [10], the authors only presented an illustrative graph with 5
nodes (Fig. A1). GNNViz presents the entire graph topology with all 80 labels
as nodes. The color of nodes are defined by the node categories in the MS-COCO
dataset. For example, bird, giraffe, cow and a few other nodes are colored in
blue as they all belong to the animal category; and the sport category nodes
(baseball bat, skateboard, frisbee, etc) are colored in light green.

The layout of this graph (Fig. A2 C) uses a force-directed graph layout [15]
and the implementation uses a D3.js javascript library [6]. The rendering
algorithm first identifies the central node by calculating the graph’s
centrality and the degree of the nodes (person node in this case), then
distribute other nodes based on their connectivity to the central nodes and
their degrees. The disconnected nodes are automatically pushed to the
peripheral areas. This global graph is the foundation of the targeted GCN
algorithm for interpretation, and it can already convey some meaningful
information, such as the oven, refrigerator, toaster and other kitchen
appliance are often appear together in an image, whereas giraffe or bear is
often alone in an image in the MS-COCO dataset.

#### Detailed View

After navigating through the browser view (Fig.A2Top) and identifying a
particular image of interest, a user can go to an image’s detailed view
(Fig.A2Bottom) by clicking on that image. The detailed view has four major
areas, in addition to the selected raw image: the groundtruth label and the
GCN prediction result (Fig.A2D), the updated prediction results (Fig.A2E)
after the user apply one of the three user actions (i.e., preserve, promote,
and attack modes), a user control panel that a user can switch between the
three user actions and manipulate hyperparameters (Fig.A2F), and the graph
topology canvas (Fig.A2G).

The default user mode is preserve mode, which is not shown in Fig.A2. The
preserve mode falls into the factual explanation use case – the explanation
algorithm identifies a less complex subgraph for prediction, but still try to
maintain the best prediction performance as using the original global graph
topology. In the user control panel (Fig.A2F), users can adjust the percentile
range selector to revise how many edges they want to keep in the subgraph,
which will further impact the updated prediction results in Fig.A2E. The less
edges a user keeps in the subgraph, the worse updated prediction result is. By
default, the algorithm identify the subgraph with 10 edges. All rest of the
unpreserved edges are shown in a 10% opacity in the background. In the
following visual analytics subsection, we will present more details of this
preserve explanation mode.

The second user mode is promote mode, and it is illustrated in Fig.A2. The
promote mode is also for the factual explanation user scenario. For the
targeted GNN prediction algorithm (GCN from [10] in this case), our GNNViz
algorithm can suggest new edges to add into the graph topology and promote the
correct prediction results. In the control panel in Fig.A2F, a user can adjust
the progress bar at the bottom to decide how many additional edges they want
the GNNViz algorithm to suggest. For example, in Fig.A2Bottom, the user sets
the parameter to two edges for addition. In Fig. A2G, the suggested two edges
appears in green dash lines (chair to sandwich and chair to wine glass). If a
user agrees with the recommendation and wants to explore this suggestion, they
can simply click on the green dash lines in Fig. A2G to add those edges into
the graph topology. The GCN prediction algorithm will recalculate the
prediction result using this manipulated graph topology, and the prediction
results will be updated in Fig. A2E. By default, promote suggests one edge to
add. Later in the visual analytics subsection, we will showcase the
effectiveness of the proposed GNNViz algorithm with a few data instances.

The third user mode is attack mode. In contrary to the previous two user
modes, this mode is to visualize the counterfactual explanation user
scenarios. GNNViz can recommend the minimal edge changes (both edge addition
and deletion) to attack the GCN prediction algorithm – manipulate the updated
prediction results to move away from the correct predictions. The user
interface looks similar to the promote mode shown in Fig. A2 Bottom. The
difference between promote mode and attack mode is that in the graph canvas
Fig. A2 G, the attack mode hide the entire graph topology in the background
and highlight only the edges recommended for attacking. It uses green dash
lines to indicate the edge addition, and uses red solid lines to indicate edge
removal, as shown in Fig. A3.

In summary, the proposed GNNViz system provides an easy-to-use and interactive
visualization system for both graph-based model experts and non-technical
model users to visually interpret, analyze, and attack GNN models. The
implemented three modes — preserve, promote, and attack — satisfy both the
factual explanation use case and the counterfactual explanation use case. The
visualization system architecture is implemented as a general purpose API-
based web service, thus researchers can easily switch the interpretation
backend to their own interpretation algorithms and visually interpret its
usefulness. Also, if the researcher is not interested in GNN interpretation
research topic, the visualization system can simply be used to examine a
graph-based model’s prediction performance at the instance level.

Figure A3: Each row represents one data instance and its preserve mode,
promote mode, and attack mode.

##  Appendix C Qualitative visual analytics with MS-COCO as a case study

As noted in the previous subsection, the model builders and model users can
use the GNNViz visualization system to interpret why a graph-based model
produces certain predictions, both correct and incorrect ones. This is
considered as the factual explanation use case. In addition, there is also a
counterfactual explanation use case. That some other users may be more
interested in the adversarial robustness of a graph-based model, thus they
want to identify the vulnarability points of a GNN model through attacking its
graph topology. In this section, we will use a few examples (Fig.A3) to
illustrate how our implemented GNNViz algorithm and visualization system
support both use cases.

As shown in Fig.A3, we present four image data instances (each in a row) and
their three modes (each in a column). In the first column, we present the raw
image, its groundtruth label, and its prediction result generated by the GCN
model [10] that GNNViz aims to explain. Sometimes the GCN prediction model may
generate incorrect predictions. For example, in the second row of the data,
the GCN model fails to predict the Handbag label, but mis-predicts an extra
Car label. For the labels that GCN correctly predicts, a user may be
interested to know why the graph-based model makes such correct prediction;
for the incorrect labels, a user may want to know why the model makes a wrong
prediction. These user needs are categorized as factual explanation use cases,
and we design a Preserve mode and a Promote mode for it. In addition, a user
may wants to increase the robustness of a graph-based model, thus he or she
needs to identify the adversarial vulnerability of the graph topology–where in
the graph a user can spent the minimal effort to change the edges and to
negatively impact the prediction result. We treat this use case separately as
a counterfactual explanation need and design the Attack mode for it.

In summary, we will use the rest of this subsection to illustrate how GNNViz
visualization system can help a user to understand, improve, and attack a
model’s prediction outcome by examining and interacting with the visual graph
topology.

####  Preserve explanation mode

In the preserve mode, our interpretation algorithm preserves a sparse subgraph
(by default ten-edges) to reduce the complexity while still maintaining a
relative good performance. By looking only at the raw images column and the
preserve mode column, we can see that for the data instance (1), the preserve
mode subgraph successfully captures the most important edge
Person–to–Motorcycle in the topology, because the Person–to–Motorcycle link is
the thickest one. But the GCN model fails to predict Bird, Bagpack or Handbag,
as these edges are not in the top-ten edges in the preserved subgraph.

In contrary, we can see from the second data instance (2) that the GCN model
mis-predicts the Car label. And the preserve subgraph reflects such
misprediction as it believes the Person–to–Car edge has a high importance
level. The model builder can further dive into the graph topology and the CNN
classifier to examine why this mistake happens.

####  Promote explanation mode

In the promote mode, our interpretation algorithm suggests new edges to add to
the graph to improve the prediction correctness. Worth to mention, the promote
mode is targeting the global graph topology, instead of the preserved
subgraph. The user can click on the suggested edges in the subgraph in the
promote mode and the selected edges will be added onto the graph topology, and
the prediction probabilities will be recalculated and updated. By default and
as illustrated in Fig.A3, we set the parameter to allow GNNViz algorithm to
suggest only one edge to add, but the user can use the control panel in
Fig.A2F to interactively change such setting.

For example, for the fourth data instance, the GCN model fails to predict
Banana and Orange. As shown in the Promote mode, the GNNViz algorithm
correctly suggest to add a Banana–to–Apple link. And if the user agrees with
such suggestion and clicks on that edge in the subgraph, the GCN model will
recalculate the prediction result and successfully predict the Banana and
Orange labels, while not affecting other labels.

####  Attack explanation mode

In the attack mode, the interpretation algorithm can suggest both edges to be
added and edges to be deleted. The attack mode also targets the global graph
topology, thus the edges to be added or to be deleted are selected from the
global graph. We use the green dash line to indicate the edges suggested to
add, and the red solid line to indicates the edges to be removed. By default,
we set the parameter for GNNViz algorithm to suggest only one edge to add and
one edge to remove, but the user can change this hyperparameter in the control
panel via the UI.

As shown in the first data instance, the GCN model initially correctly
predicts Motrocycle and Person. The GNNViz algorithm suggests to add the
WineGlass–to–Motorcle link and remove the Bench–to–Person link from the graph
topology. If the user applies such suggestions, the GCN model will recalculate
the prediction result and mistakenly believes Kite is the top prediction
label. Similarly, in the third data instance row, if the user agrees with the
algorithm suggestion by adding Spoon–to–BaseballBat and removing
Bowl–to–Person edges, the GCN model can not predict the Person label anymore,
and the attack is successful.