# Bot Electioneering Volume: Visualizing Social Bot Activity During Elections

Kai-Cheng Yang<EMAIL_ADDRESS>0000-0003-4627-9273 Center for Complex Networks
and Systems Research, Indiana UniversityBloomingtonIndiana47408 ,  Pik-Mai Hui
<EMAIL_ADDRESS>Center for Complex Networks and Systems Research, Indiana
UniversityBloomingtonIndiana47408 and  Filippo Menczer  cnets.indiana.edu/fil
0000-0003-4384-2876 Center for Complex Networks and Systems Research, Indiana
UniversityBloomingtonIndiana47408

(2019)

###### Abstract.

It has been widely recognized that automated bots may have a significant
impact on the outcomes of national events. It is important to raise public
awareness about the threat of bots on social media during these important
events, such as the 2018 US midterm election. To this end, we deployed a web
application to help the public explore the activities of likely bots on
Twitter on a daily basis. The application, called Bot Electioneering Volume
(BEV), reports on the level of likely bot activities and visualizes the topics
targeted by them. With this paper we release our code base for the BEV
framework, with the goal of facilitating future efforts to combat malicious
bots on social media.

bot activity, Twitter, elections

††journalyear: 2019††copyright: acmlicensed††conference: The Web Conference
2019; May 13–17, 2019; San Francisco, CA††booktitle: The Web Conference 2019,
May 13–17, 2019, San Francisco, CA††price: 15.00

##  1\. Introduction

Social bots have drawn great attention from the public recently. They are
accounts on social media platforms controlled at least in part by algorithms
to generate/share/retweet content and interact with human users (Ferrara et
al., 2016). The automated nature of social bots makes it easy to achieve
scalability, with which a single person is capable to control thousands of
accounts on one or more social media platforms. When needed, these social bots
can work collectively to manipulate the public by promoting certain accounts
or opinions.

Being social animals, human users are inevitably vulnerable to the efforts of
the social bots. Studies have shown ubiquitous social bots (Varol et al.,
2017) distort online discussions, and particularly those about politics.
During the 2010 US midterm election, primitive social bots were used to attack
some candidates (Metaxas and Mustafaraj, 2012) and spread tweets with links to
fake news websites (Ratkiewicz et al., 2011). A similar pattern emerged in the
2016 US presidential election, only with more sophisticated bots that aimed to
effectively push their messages to the target audience (Bessi and Ferrara,
2016). In particular, bots were most active in the core of the misinformation-
sharing network (Shao et al., 2018b) and effectively amplified the spread of
low-credibility content by posting it within seconds and by targeting
influential accounts (Shao et al., 2018a). Analogous automated campaigns were
reported in countries around the globe (Stella et al., 2018; Ferrara, 2017).

Figure 1. Illustration of BEV’s (a) crawler, (b) database, (c) analyzer, and
screen shot of (d) front-end interface. The upper panel of the frontend shows
the Bot Electioneering Volume for the past 8 days. Users can select a day of
interest to explore the top topics of that day. The bottom panels show a tag
cloud and entity lists for the selected day. The tag cloud presents entities
all together, with the size of each entity proportional to how often it is
tweeted by bots. The entity lists display hashtags, mentions, and links ranked
by how often each is tweeted by bots.

Here we present Bot Electioneering Volume (BEV), a platform that visualizes
the volume generated by bots and the corresponding targeted topics. BEV tracks
online traffic centered around elections from Twitter by feeding the streaming
API with a list of selected hashtags. By incorporating the bot-detection
ability of Botometer (Davis et al., 2016; Varol et al., 2017; Yang et al.,
2019), BEV is able to distinguish between content generated by likely bots and
humans. The measurement of average bot activity is then compared with random
samples of tweets to produce a number that quantifies electioneering activity
by bots. BEV also collects content topics, including hashtags, mentions, and
URLs shared by likely bots, and reports on their relative volumes.

BEV (botometer.iuni.iu.edu/bev) monitored public tweets about the 2018 US
midterm elections between October 22, 2018 and Dec 30, 2018. During the
collection period, BEV drew over 3,000 visits. An archive of the data from Oct
to Dec 2018 remains publicly available for retrospective inspections. We plan
to activate BEV again for future elections. Our goal is to raise public
awareness of bot activities and their impact during elections in the past, and
more importantly those in the future.

##  2\. System design

The BEV system contains 4 major parts: a crawler, a database, an analyzer, and
a front-end interface, as illustrated in Figure 1.

The crawler is in charge of tracking Twitter’s filtering API for public
election-related tweets, querying Twitter’s Spritzer API for random samples of
public tweets, and fetching bot scores. Crawled data is stored in the
database. The analyzer then extracts the required information and generates
the statistics for the visualization at the application frontend. The frontend
has three major parts: the Bot Electioneering Volume timeline, a tag cloud,
and entity lists. The Bot Electioneering Volume measures the activity of
likely bots, while the tag could and entity lists display the topics that are
most tweeted by likely bots. By clicking on the links in an entity list, users
are directed to Hoaxy (hoaxy.iuni.iu.edu) (Shao et al., 2016), where they can
explore more in-depth visualizations of the influence of bots around the
entities on Twitter in the recent minutes/hours/days.

The data collection runs in a streaming fashion, but fetching bot scores and
analyzing the data take time. The front-end interface is updated every 4 hours
to reflect newly incoming data.

###  2.1. Data collection

The collection of election-related tweets is crucial to our application. Our
collection process starts with a set of election-related hashtags that are
tracked using the Twitter filtering API. We seeded our set of hashtags with
several widely-used political hashtags including #2018midterms, #maga, and
#bluewave. We then repeatedly expanded the set with co-occuring hashtags
(Conover et al., 2012), resulting in a set of 110 hashtags. From this set we
manually removed 6 hashtags that are general and irrelevant to election. We
also added the hashtags for each US state’s Senate race: #casen, #nysen, and
so on. The full list of hashtags can be found in the FAQ page of the BEV
website. This methodology allows our system to collect most tweets with newly
emerging election hashtags, because it is likely that these tweets contain
some of the hashtags in our list as well.

Twitter’s free filtering API offers at most 1% of Twitter’s traffic. We
estimated that the traffic captured by our method is about 0.3–0.5% of
Twitter’s complete traffic (see Figure 2(a)). This means that instead of a
sample, BEV collects and visualizes bot activities based on _all_ of the
targeted election-related tweets.

###  2.2. Bot identification

BEV uses Botometer (botometer.iuni.iu.edu) (Davis et al., 2016; Varol et al.,
2017; Yang et al., 2019) to obtain bot scores for Twitter accounts involved in
election-related discourse. Botometer is a supervised machine learning
algorithm that considers more than a thousand features about an account and
its activity to estimate the likelihood that the account is automated. We
consider accounts with bot score above 4 (on a 5-point scale) as social bots.
This is a fairly conservative threshold choice, corresponding to a posterior
probability of automation near 50% (Yang et al., 2019) based on a 15% prior
probability (Varol et al., 2017).

###  2.3. Bot activity measurement

Figure 2. (a) Number of election tweets and unique users for each day. (b)
Average bot scores for election tweets and random sample. (c) BEV timeline.
The 2018 US midterm elections day, Nov 6, is highlighted by a vertical dashed
line.

To measure the bot electioneering volume, we first take daily averages of the
bot scores of accounts generating political tweets, weighted by their tweet
frequencies. Considering that spamming the same message is a common strategy
for bots, the weighted average better highlights the amount of bot-generated
content and their potential influence. To obrain a baseline of bot activity,
we produce the same weighted average for random tweets from Twitter’s Spritzer
API, with a rate of 1,000 tweets per hour. The daily average bot scores for
election and random tweets are shown in Figure 2(b).

The Bot Electioneering Volume is defined by the relative difference between
the two averages:

(1)
$\text{BEV}=\frac{S_{\text{Electoral}}-S_{\text{RandomSample}}}{S_{\text{RandomSample}}}\text{,}$

where $S_{\text{Electoral}}$ and $S_{\text{RandomSample}}$ represent the
average bot scores of electoral and random tweets, respectively. BEV is shown
as a percentage difference in the front-end interface, as shown in Figure
1(d). Figure 2(c) plots the Bot Electioneering Volume of the whole midterm
elections period.

In the design stage of BEV, we considered different metrics by replacing the
average bot score $S$ in Eq. 1 with the median score and the proportion of
tweets by bots. The Bot Electioneering Volume based on median values of the
scores yields patterns similar to the average score version. However, the
version based on the proportion of tweets by bots (denoted by BEV2) shows
different trends. As shown in Figure 3(a), the baseline proportion of tweets
by bots decreases steadily after the midterm elections. Consequently, the BEV2
value increases (Figure 3(b)). Since the proportion of tweets by likely bots
in the random sample is not stable, we decided to deploy the BEV metric based
on average bot scores.

Figure 3. (a) Proportion of tweets by bots for election tweets and random
sample. (b) BEV2.

The BEV front-end interface also visualizes the topics targeted by likely
bots. For simplicity, we only extract hashtags, mentioned accounts, and links
from the tweets generated by bots. The targeted topics are represented in a
tag cloud and entity lists.

##  3\. Discussion

BEV reveals many interesting patterns. In terms of the discussion intensity,
the number of election tweets before the election was about twice as many as
the number after the election day peak, as shown in Figure 2(a). For bot
activity, all the different metrics — average bot score, median bot score, and
proportion of tweets by likely bots — are much higher for election tweets,
suggesting that bots are actively generating election-related content; they
are indeed employed for electioneering.

The average bot scores of election-related tweets fluctuated from day to day.
The BEV on November 6 and 7 was drastically lower than on other days.
Considering the spike in election tweets, we hypothesize that the bot activity
was diluted by the huge amount of normal users around election day.
Furthermore, the average bot scores of election-related tweets after the
election are generally higher than those before the election. This is perhaps
because many human users ceased to tweet political content after the election,
but the bots kept working. BEV cannot reflect the changes in total volume of
tweets because it is based on averaging the daily scores. For the future, a
measurement that can leverage both the average bot score and the volume of
tweets may be preferable to better represent the volume generated by bots.

##  4\. Conclusion

We offer a real-time tool to visualize the electioneering activities of social
bots. Open-source code for BEV is at github.com/IUNetSci/BEV.

Around the 2018 US midterm elections, bot electioneering was rampant. The
great majority of content amplified by likely bots was on the conservative
side of the political spectrum. It remains to be seen if this will change in
the future.

The tool enables the public to gain a sense of the organic nature of the
online discussion regarding elections and spot possibly polluted content. By
performing the hashtag list generation procedure with different seeds, BEV can
be adapted to target future US elections, as well as elections and events in
other countries.

#### Acknowledgments.

We are grateful to the IU Network Science Institute (iuni.iu.edu) and the AWS
Cloud Credits for Research program for supporting the BEV infrastructure and
to Twitter for their free APIs. Botometer was developed with support from the
Democracy Fund.

## References

  * (1)
  * Bessi and Ferrara (2016) Alessandro Bessi and Emilio Ferrara. 2016.  Social bots distort the 2016 US Presidential election online discussion.  _First Monday_ 21, 11 (2016).
  * Conover et al. (2012) Michael D Conover, Bruno Gonçalves, Alessandro Flammini, and Filippo Menczer. 2012.  Partisan asymmetries in online political activity.  _EPJ Data Science_ 1 (2012), 6.  https://doi.org/10.1140/epjds6
  * Davis et al. (2016) Clayton Allen Davis, Onur Varol, Emilio Ferrara, Alessandro Flammini, and Filippo Menczer. 2016\.  BotOrNot: A system to evaluate social bots. In _Proc. 25th Intl. Conf. Companion on World Wide Web_. IW3CSC, Montreal, 273–274.
  * Ferrara (2017) Emilio Ferrara. 2017\.  Disinformation and Social Bot Operations in the Run Up to the 2017 French Presidential Election.  _First Monday_ 22, 8 (2017).
  * Ferrara et al. (2016) Emilio Ferrara, Onur Varol, Clayton Davis, Filippo Menczer, and Alessandro Flammini. 2016\.  The rise of social bots.  _Commun. ACM_ 59, 7 (2016), 96–104.
  * Metaxas and Mustafaraj (2012) Panagiotis T Metaxas and Eni Mustafaraj. 2012.  Social media and the elections.  _Science_ 338, 6106 (2012), 472–473.
  * Ratkiewicz et al. (2011) Jacob Ratkiewicz, Michael Conover, Mark R Meiss, Bruno Gonçalves, Alessandro Flammini, and Filippo Menczer. 2011.  Detecting and tracking political abuse in social media. In _Proc. Intl. Conf. on Weblogs and Social Media (ICWSM)_. AAAI, Barcelona, 297–304.
  * Shao et al. (2016) Chengcheng Shao, Giovanni Luca Ciampaglia, Alessandro Flammini, and Filippo Menczer. 2016\.  Hoaxy: A platform for tracking online misinformation. In _Proc. 25th Intl. Conf. Companion on World Wide Web_. IW3CSC, Montreal, 745–750.
  * Shao et al. (2018a) Chengcheng Shao, Giovanni Luca Ciampaglia, Onur Varol, Kai-Cheng Yang, Alessandro Flammini, and Filippo Menczer. 2018a.  The spread of low-credibility content by social bots.  _Nat. Commun._ 9 (2018), 4787.  https://doi.org/10.1038/s41467-018-06930-7
  * Shao et al. (2018b) Chengcheng Shao, Pik-Mai Hui, Lei Wang, Xinwen Jiang, Alessandro Flammini, Filippo Menczer, and Giovanni Luca Ciampaglia. 2018b.  Anatomy of an online misinformation network.  _PLoS ONE_ 13, 4 (2018), e0196087.  https://doi.org/10.1371/journal.pone.0196087
  * Stella et al. (2018) Massimo Stella, Emilio Ferrara, and Manlio De Domenico. 2018\.  Bots increase exposure to negative and inflammatory content in online social systems.  _Proc. Natl. Acad. Sci. U.S.A._ 115, 49 (2018), 12435–12440.
  * Varol et al. (2017) Onur Varol, Emilio Ferrara, Clayton A Davis, Filippo Menczer, and Alessandro Flammini. 2017\.  Online human-bot interactions: Detection, estimation, and characterization. In _Proc. Intl. Conf. on Web and Social Media (ICWSM)_. AAAI, Montreal, 280–289.
  * Yang et al. (2019) Kai-Cheng Yang, Onur Varol, Clayton A Davis, Emilio Ferrara, Alessandro Flammini, and Filippo Menczer. 2019.  Arming the public with AI to counter social bots.  _Human Behavior and Emerging Technologies_ 1, 1 (2019).  https://doi.org/10.1002/hbe2.115 In press; arXiv preprint 1901.00912.


# Message-passing Selection: Towards Interpretable GNNs for Graph
Classification

Wenda Li1111Equal Contribution<EMAIL_ADDRESS>Kaixuan
Chen111footnotemark: 1, Shunyu Liu1, Wenjie Huang1, Haofei Zhang1, Mingli
Song1222Corresponding author<EMAIL_ADDRESS>
Yingjie Tian2, Yun Su2
1Zhejiang University, 2State Grid Shanghai Municipal Electirc Power Company

###### Abstract

In this paper, we strive to develop an interpretable GNNs’ inference paradigm,
termed _MSInterpreter_ , which can serve as a plug-and-play scheme readily
applicable to various GNNs’ baselines. Unlike the most existing explanation
methods, _MSInterpreter_ provides a _M_ essage-passing _S_ election scheme
(_MSScheme_) to select the critical paths for GNNs’ message aggregations,
which aims at reaching the self-explaination instead of post-hoc explanations.
In detail, the elaborate _MSScheme_ is designed to calculate weight factors of
message aggregation paths by considering the vanilla structure and node
embedding components, where the structure base aims at weight factors among
node-induced substructures; on the other hand, the node embedding base focuses
on weight factors via node embeddings obtained by one-layer GNN. Finally, we
demonstrate the effectiveness of our approach on graph classification
benchmarks.

##  1 Introduction

Recently, several advanced approaches (Ying et al., 2019; Luo et al., 2020;
Schlichtkrull et al., 2021; Huang et al., 2022; Vu & Thai, 2020; Gui et al.,
2022; Yuan et al., 2021; Schnake et al., 2021; Yuan et al., 2020; Yu & Gao,
2022) have been proposed to explain the predictions of graph neural networks
(GNNs), and are divided into two categories (Yuan et al., 2023), i.e.,
instance and model-level explanation. The instance-level aims at critical
nodes or subgraphs; on the other hand, model-level focuses on a more high-
level explainability. However, most of existing GNNs’ explainers are post-hoc
and lack the study regarding message-passing selection for GNNs’ inference.

Figure 1: An illustration of the proposed _MSInterpreter_ framework, i.e.,
plugging the _MSScheme_ at the beginning of GNNs for an interpretable
inference.

In this paper, we aim at selecting the critical message-passing paths for
GNNs’ aggregations, and thus develop an interpretable GNNs’ inference
paradigm, i.e., _MSInterpreter_ , for the task of graph classification. As
shown in Figure 1, the main process is to build the _M_ essage-passing _S_
election scheme (_MSScheme_), and then plug it at the beginning of the
existing GNNs’ baselines to reach self-explainable inference. The
contributions and details are summarized as follows:

  * •

We propose the _MSScheme_ to calculate the weight factors among the connected
nodes and then select the critical message-passing path for GNNs’
aggregations.

  * •

We plug the _MSScheme_ at the beginning of an arbitrary GNN to build
_MSInterpreter_ , which is an end-to-end learnable framework to reach the
self-explainable GNNs.

  * •

We apply the _MSInterpreter_ into graph classification task and provide the
experimental analysis to support the claim that it can achieve significantly
improved explanations.

##  2 Method

Notation. A graph consisting of $n$ nodes can be represented as
$G=(\bm{A},\bm{X})$, where $\bm{A}\in\mathbb{R}^{n\times n}$ and
$\bm{X}\in\mathbb{R}^{n\times d}$ represent adjacency matrix and node feature
matrix respectively. For a set of labeled graphs
${\mathbb{S}}=\\{(G_{1},y_{1}),..,(G_{N},y_{N})\\}$, where
$y_{i}\in{\mathbb{Y}}$ denotes the label of $i$-th graph $G_{i}\in$
${\mathbb{G}}$. The graph classification task is to learn a function
$f:{\mathbb{G}}\rightarrow{\mathbb{Y}}$ that maps graphs to the labels’ set.
The message-passing path is initialized as $\bm{M}=\bm{A}$. $\mathcal{N}(v)$
denotes the neighbor set of vertex $v$. To efficiently obtain the critical
message aggregation path for GNNs’ inference with application to graph
classification, we introduce the elaborate _MSScheme_ as following.

MSScheme. The _MSScheme_ aims at the critical message-passing paths for GNNs’
inference, which is the essential module to reach the self-explaination. The
_MSScheme_ is formulated as:

$\bm{M}=\mathcal{M}(\bm{A},\texttt{Mask})\in\mathbb{R}^{n\times n}$ (1)

where $\mathcal{M}$ is the message-passing selection function using mask
matrix $\texttt{Mask}\in\mathbb{R}^{n\times n}$. To obtain mask matrix, we
firstly compute the edge weight factors. Then, we sort these weights, and set
the high-weight edges as true, and vice versa. Specifically, the edge weights
are obtained by considering two components: the vanilla structure base and the
node embedding base. For the vanilla structure base, we compute the edge
weight between nodes $v_{i}$ and $v_{j}$ using the intersection over union
(IoU) of the number of $\mathcal{N}(v_{i})$ and $\mathcal{N}(v_{j})$, i.e.,
$\texttt{W}_{str}(v_{i},v_{j})=\psi(\frac{num\left(\mathcal{N}(v_{i})\bigcap\mathcal{N}(v_{j})\right)}{num\left(\mathcal{N}(v_{i})\bigcup\mathcal{N}(v_{j})\right)})$,
where $\psi$ is a norm operation in a whole graph. On the other hand, edge
weight regarding node embedding is computed by
$\texttt{W}_{emb}(v_{i},v_{j})=\varphi(h_{v_{i}},h_{v_{j}})$, where
$h_{v_{i}}$ and $h_{v_{j}}$ denote the node embeddings of $v_{i}$ and $v_{j}$
via one-layer GNN. $\varphi$ is a mapping function like line or gaussian
kernel function, etc. The resulting edge factor is:

$\texttt{W}_{com}(v_{i},v_{j})=\texttt{W}_{str}(v_{i},v_{j})+\alpha\cdot\texttt{W}_{emb}(v_{i},v_{j}),$
(2)

where $\alpha$ is a hyperparameter to balance two weight factors.

MSInterpreter. To build the self-explainable GNNs, we plug the proposed
_MSScheme_ at the beginning of the GNNs predictions. As shown in the Figure 1,
we use the _MSScheme_ to select the critical message aggregation path to build
the interpretable GNNs’ inference, i.e., _MSInterpreter_ , which is beneficial
to build an end-to-end framework while training GNNs for the task of graph
classification.

##  3 Experiment

We compare _MSInterpreter_ with four popular explainable methods PGExplainer
(Luo et al., 2020), GNNExplainer (Ying et al., 2019) ,SubgraphX (Yuan et al.,
2021), and GStarX (Zhang et al., 2022). In Table 1, we list these methods’
accuracy, recall, and F1 score, and our method achieves the competitive
performances. More experimental details are provided in Appendix A.

Table 1: Evaluation of several explainable methods on two graph classification datasets (with annotated explanatory edges) using a three-layer GIN architecture. Dataset | BA-2MOTIFS | MUTAG0
---|---|---
Acc. | Rec. | F1 | Acc. | Rec. | F1
GNN-Exp. | 49.21 ±0.39 | 52.65 ±1.91 | 30.85 ±0.96 | 50.48 ±1.82 | 59.22 ±0.70 | 48.00 ±0.80
PGE-Exp. | 36.05 ±0.11 | 80.23 ±0.57 | 35.13 ±0.21 | 56.27 ±0.59 | 83.60 ±0.89 | 59.44 ±0.56
SubgraphX | 71.15 ±1.00 | 52.08 ±0.82 | 40.42 ±0.18 | 69.05 ±0.91 | 38.35 ±2.90 | 48.62 ±2.68
GStarX | 61.85 ±0.01 | 86.86 ±1.67 | 49.56 ±0.45 | 46.96 ±0.01 | 74.62 ±1.85 | 58.88 ±0.24
MSInterpreter | 66.34 ±0.37 | 90.78 ±0.87 | 53.75 ±0.53 | 79.31 ±0.95 | 88.69 ±1.63 | 76.12 ±1.04

##  4 Conclusions

In this paper, we introduce an novel framework to explain the GNNs’ inference
with application to graph classification. Firstly, we build a scheme
_MSScheme_ to analyze the weight factors of message-passing paths, which is
essential to obtain the crucial message aggregations for GNNs’ inference.
Then, we plug the _MSScheme_ at the begin of the GNNs’ predictions to build an
end-to-end interpretable paradigm, i.e., _MSInterpreter_ , which aims at
reaching the self-explaination GNNs for graph classification. Finally, we
perform our proposed method in graph classification to demonstrate its
superior performance.

### Acknowledgements

This work is supported by the Science and Technology Project of SGCC: Hybrid
enhancement intelligence with human-AI coordination and its application in
reliability analysis of regional power system (5700-202217190A-1-1-ZN).

### URM Statement

The authors acknowledge that at least one key author of this work meets the
URM criteria of ICLR 2023 Tiny Papers Track. Author Wenda Li meets the URM
criteria of ICLR 2023 Tiny Papers Track.

## References

  * Alghamdi et al. (2021) Norah Alghamdi, Wennan Chang, Pengtao Dang, Xiaoyu Lu, Changlin Wan, Silpa Gampala, Zhi Huang, Jiashi Wang, Qin Ma, Yong Zang, et al.  A graph neural network model to estimate cell-wise metabolic flux using single-cell rna-seq data.  _Genome Research_ , 31(10):1867–1884, 2021.
  * Boyaci et al. (2021) Osman Boyaci, Mohammad Rasoul Narimani, Katherine R Davis, Muhammad Ismail, Thomas J Overbye, and Erchin Serpedin.  Joint detection and localization of stealth false data injection attacks in smart grids using graph neural networks.  _IEEE Transactions on Smart Grid_ , 13(1):807–819, 2021.
  * Chen et al. (2022a) Kaixuan Chen, Shunyu Liu, Na Yu, Rong Yan, Quan Zhang, Jie Song, Zunlei Feng, and Mingli Song.  Distribution-aware graph representation learning for transient stability assessment of power system.  In _International Joint Conference on Neural Networks_ , 2022a.
  * Chen et al. (2022b) Kaixuan Chen, Jie Song, Shunyu Liu, Na Yu, Zunlei Feng, Gengshi Han, and Mingli Song.  Distribution knowledge embedding for graph pooling.  _IEEE Transactions on Knowledge and Data Engineering_ , 2022b.
  * Chen et al. (2023) Kaixuan Chen, Shunyu Liu, Tongtian Zhu, et al.  Improving expressivity of gnns with subgraph-specific factor embedded normalization.  In _ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD)_ , 2023.
  * Fey & Lenssen (2019) Matthias Fey and Jan Eric Lenssen.  Fast graph representation learning with pytorch geometric.  _arXiv preprint arXiv:1903.02428_ , 2019.
  * Gui et al. (2022) Shurui Gui, Hao Yuan, Jie Wang, Qicheng Lao, Kang Li, and Shuiwang Ji.  Flowx: Towards explainable graph neural networks via message flows.  _arXiv preprint arXiv:2206.12987_ , 2022.
  * Han et al. (2022) Gengshi Han, Shunyu Liu, Kaixuan Chen, Na Yu, Zunlei Feng, and Mingli Song.  Imbalanced sample generation and evaluation for power system transient stability using ctgan.  In _International Conference on Intelligent Computing and Optimization_ , 2022.
  * Huang et al. (2022) Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, and Yi Chang.  Graphlime: Local interpretable model explanations for graph neural networks.  _IEEE Transactions on Knowledge and Data Engineering_ , 35(7):6968–6972, 2022.
  * Jing et al. (2021) Yongcheng Jing, Yiding Yang, Xinchao Wang, Mingli Song, and Dacheng Tao.  Meta-aggregator: learning to aggregate for 1-bit graph neural networks.  In _IEEE/CVF Computer Vision and Pattern Recognition Conference_ , 2021.
  * Jing et al. (2022) Yongcheng Jing, Yining Mao, Yiding Yang, Yibing Zhan, Mingli Song, Xinchao Wang, and Dacheng Tao.  Learning graph neural networks for image style transfer.  In _European Conference on Computer Vision_ , 2022.
  * Li et al. (2022) Jiachen Li, Siheng Chen, Xiaoyong Pan, Ye Yuan, and Hong-Bin Shen.  Cell clustering for spatial transcriptomics data with graph neural networks.  _Nature Computational Science_ , 2(6):399–408, 2022.
  * Liu et al. (2021) Meng Liu, Youzhi Luo, Limei Wang, Yaochen Xie, Hao Yuan, Shurui Gui, Haiyang Yu, Zhao Xu, Jingtun Zhang, Yi Liu, et al.  Dig: A turnkey library for diving into graph deep learning research.  _Journal of Machine Learning Research_ , 22(1):10873–10881, 2021.
  * Liu et al. (2022) Shunyu Liu, Jie Song, Yihe Zhou, Na Yu, Kaixuan Chen, Zunlei Feng, and Mingli Song.  Interaction pattern disentangling for multi-agent reinforcement learning.  _arXiv preprint arXiv:2207.03902_ , 2022.
  * Luo et al. (2020) Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang.  Parameterized explainer for graph neural network.  _Advances in Neural Information Processing Systems_ , 2020.
  * Riesen & Bunke (2008) Kaspar Riesen and Horst Bunke.  Iam graph database repository for graph based pattern recognition and machine learning.  In _Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition and Structural and Syntactic Pattern Recognition_ , 2008\.
  * Schlichtkrull et al. (2021) Michael Sejr Schlichtkrull, Nicola De Cao, and Ivan Titov.  Interpreting graph neural networks for nlp with differentiable edge masking.  In _International Conference on Learning Representations_ , 2021.
  * Schnake et al. (2021) Thomas Schnake, Oliver Eberle, Jonas Lederer, Shinichi Nakajima, Kristof T Schütt, Klaus-Robert Müller, and Grégoire Montavon.  Higher-order explanations of graph neural networks via relevant walks.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 44(11):7581–7596, 2021.
  * Tan et al. (2022) Juntao Tan, Shijie Geng, Zuohui Fu, Yingqiang Ge, Shuyuan Xu, Yunqi Li, and Yongfeng Zhang.  Learning and evaluating graph neural network explanations based on counterfactual and factual reasoning.  In _ACM Web Conference_ , 2022.
  * Tavakoli et al. (2022) Mohammadamin Tavakoli, Aaron Mood, David Van Vranken, and Pierre Baldi.  Quantum mechanics and machine learning synergies: graph attention neural networks to predict chemical reactivity.  _Journal of Chemical Information and Modeling_ , 62(9):2121–2132, 2022.
  * Vu & Thai (2020) Minh Vu and My T Thai.  Pgm-explainer: Probabilistic graphical model explanations for graph neural networks.  In _Advances in Neural Information Processing Systems_ , 2020.
  * Ying et al. (2019) Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec.  Gnnexplainer: Generating explanations for graph neural networks.  _Advances in Neural Information Processing Systems_ , 2019.
  * Yu & Gao (2022) Zhaoning Yu and Hongyang Gao.  Motifexplainer: a motif-based graph neural network explainer.  _arXiv preprint arXiv:2202.00519_ , 2022.
  * Yuan et al. (2020) Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji.  Xgnn: Towards model-level explanations of graph neural networks.  In _ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ , 2020.
  * Yuan et al. (2021) Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji.  On explainability of graph neural networks via subgraph explorations.  In _International Conference on Machine Learning_ , 2021.
  * Yuan et al. (2023) Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji.  Explainability in graph neural networks: A taxonomic survey.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 45(5):5782–5799, 2023.
  * Zhang et al. (2023) Haofei Zhang, Xiaokang Liu, Mengqi Xue, Kaixuan Chen, Jie Song, and Mingli Song.  Schema inference for interpretable image classification.  In _International Conference on Learning Representations_ , 2023.
  * Zhang et al. (2022) Shichang Zhang, Yozen Liu, Neil Shah, and Yizhou Sun.  Gstarx: Explaining graph neural networks with structure-aware cooperative games.  In _Advances in Neural Information Processing Systems_ , 2022.
  * Zhong et al. (2022) Zipeng Zhong, Jie Song, Zunlei Feng, Tiantao Liu, Lingxiang Jia, Shaolun Yao, Min Wu, Tingjun Hou, and Mingli Song.  Root-aligned smiles: a tight representation for chemical reaction prediction.  _Chemical Science_ , 13(31):9023–9034, 2022.

##  Appendix A Appendix

Dataset. We compare two datasets with edge interpretation labels: MUTAG0 and
BA2Motifs. The statistics for the BA2Motif (Luo et al., 2020) and MUTAG0 (Tan
et al., 2022) datasets are shown in Table 2.

  * $\bullet$

MUTAG0 is a molecular dataset for graph classification tasks and consists of
4,337 molecular graphs. In this dataset, nodes represent different atoms, and
edges represent chemical bonds. Each graph is assigned to one of the two
categories according to its mutagenic effects (Riesen & Bunke, 2008). We
observe that carbon rings are present in both mutagenic and non-mutagenic
graphs, but the carbon rings with the chemical groups $NH_{2}$ or $NO_{2}$ are
mutagenic. Therefore, the carbon ring can be considered a shared base map, and
the two groups $NH_{2}$ and $NO_{2}$ are the base sequence of the mutagenic
map. For the non-mutagenic graphs, there is no explicit base sequence. For the
mutagenic graphs, there are true edge masks that mark the edges of the
mutagenic motifs.

  * $\bullet$

BA2Motifs is a synthetic graph motif detection dataset. BA2Motifs contains
Barabasi-Albert (BA) base graphs of size 20, and each graph has five node
patterns. The node features are 10-dimensional all-one vectors. Patterns can
be house-like structures or cycles. The graphs are divided into two categories
based on the topics they contain. Therefore the interpretation of this dataset
is the edges that make up the two patterns.

Experiments Settings. We use three-layer GIN as the backbone network and set
the hidden dimensions as 128. We divide the dataset into three random groups
(80%/10%/10%) as training, validation, and test sets.

For the BA2Motifs dataset, we compute the three metrics only for correctly
predicted data. For the MUTAG0 dataset, we add one more restriction that the
prediction category is mutagenic since only mutagenic data have interpreted
edges. We uniformly set the batch size to 64 and the number of epochs to 100.
For our method, we keep the sparsity at 0.5, and the hyperparameter $\alpha$
is set to 0.5.

Our implementation is based on Python 3.8.15, PyTorch 1.12.0, PyTorchGeometric
2.2.0 (Fey & Lenssen, 2019), and DIG (Liu et al., 2021). We adopt the GNN
implementation and the provided implementation of the baseline explainer from
the DIG library.

Graph Classification. We provide the accuracy of graph classification in table
3.Compared to the four post-hoc explainers, our method keeps the accuracy no
less than the accuracy of backbone.

Table 2: Dataset Statistics. Dataset | Graphs | Edges(avg.) | Nodes(avg.) | Classes
---|---|---|---|---
MUTAG0 | 2301 | 32.54 | 31.74 | 2
BA2Motifs | 1000 | 25.00 | 51.39 | 2
Table 3: Accuracy of graph classification for various interpretation methods | GIN | GNN-Exp. | PGE-Exp. | SubgraphX | GSTtarX | MSInterpreter
---|---|---|---|---|---|---
MUTAG0 | 0.995 | 0.826 | 0.995 | 0.904 | 0.934 | 1.0
BA2Motifs | 1.0 | 0.993 | 1.0 | 0.931 | 0.964 | 1.0

Discussion. The developments of graph neural networks (GNNs) have
revolutionized the domains non-Euclidean space (Jing et al., 2022; Chen et
al., 2023). Especially, graph representation learning and other graph
symmetries with application to various graph downstream tasks are well
studied, e.g., vision tasks (Jing et al., 2021; Zhang et al., 2023), cell
clustering (Alghamdi et al., 2021; Li et al., 2022), chemical prediction
(Tavakoli et al., 2022; Zhong et al., 2022; Chen et al., 2022b), reinforcement
learning (Liu et al., 2022) and power system (Boyaci et al., 2021; Chen et
al., 2022a; Han et al., 2022). However, the predictions of these GNN baselines
lack explainability, i.e., their inferences for handling graph-structure data
are still treated as black boxes, which limits their applications in some
crucial areas.

Recently, several advanced approaches (Ying et al., 2019; Luo et al., 2020;
Schlichtkrull et al., 2021; Huang et al., 2022; Vu & Thai, 2020; Gui et al.,
2022; Yuan et al., 2021; Schnake et al., 2021; Yuan et al., 2020; Yu & Gao,
2022) have been proposed to explain the predictions of graph neural networks
(GNNs), and are divided into two categories (Yuan et al., 2023), i.e.,
instance and model-level explanation. The instance-level aims at critical
nodes or subgraphs; on the other hand, model-level focuses on a more high-
level explainability. _However, most of existing GNNs’ explainers are post-hoc
and lack the study regarding message-passing selection for GNNs’ inference._