Graph Structural Aggregation for Explainable Learning
Authors: Alexis Galland
marc lelarge
Venue:  (2021)
Keywords: graph
deep
learning

Abstract: Graph neural networks have proven to be very efficient to solve several tasks in graphs such as node classification or link prediction. These algorithms that operate by propagating information from vertices to their neighbors allow one to build node embeddings that contain local information. In order to use graph neural networks for graph classification, node embeddings must be aggregated to obtain a graph representation able to discriminate among different graphs (of possibly various sizes). Moreover, in analogy to neural networks for image classification, there is a need for explainability regarding the features that are selected in the graph classification process. To this end, we introduce StructAgg, a simple yet effective aggregation process based on the identification of structural roles for nodes in graphs that we use to create an end-to-end model. Through extensive experiments we show that this architecture can compete with state-of-the-art methods. We show how this aggregation step allows us to cluster together nodes that have comparable structural roles and how these roles provide explainability to this neural network model.


Under review as a conference paper at ICLR 2021
GRAPH STRUCTURAL AGGREGATION FOR EXPLAIN- ABLE LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Graph neural networks have proven to be very efficient to solve several tasks in graphs such as node classification or link prediction. These algorithms that operate by propagating information from vertices to their neighbors allow one build node embeddings that contain local information. In order to use graph neural networks for graph classification, node embeddings must be aggregated to obtain graph representation able to discriminate among different graphs (of possibly various sizes). Moreover, in analogy to neural networks for image classification, there is a need for explainability regarding the features that are selected in the graph classification process. To this end, we introduce StructAgg, a simple yet effective aggregation process based on the identification of structural roles for nodes in graphs that we use to create an end-to-end model. Through extensive experiments we show that this architecture how this aggregation step allows us to cluster together nodes that have comparable structural roles and how these roles provide explainability this neural network model.
compete with state-of-the of-tth-art methods. We show
INTRODUCTION
Convolution neural networks (LeCun al. 1995) have proven to be very efficient learning mean- ingful patterns for many articificial intelligence tasks. They convey the ability to learn hierarchical information in data with Euclidean grid-like structures such images and text. Convolutional Neural Networks (CNNs) have rapidly become state-of-the art methods in the fields of computer vision (Russakovsky et al. 2015) and natural language processing (Devlin et al.) 2018).
However in many scientific fields, studied data have underlying graph or manifold structure such as communication networks (whether social or technical) or knowledge graphs. Recently there have been many attempts to extend convolutions to those non-Euclidean structured data (Hammond et al., 2011 Kipf & Welling 2016 Defferrard et al., 2016). In these new approaches, the authors propose to compute node embeddings in semi-supervin supervised fashion in order perform node classification. Those node embeddings can also be used for link prediction by computing distances between each node of the graph (Hammond al. 2011: Kipf & Welling 2016).
Graph classification is studied in many fields. Whether for predicting the chemical activity of molecule or cluster authors from different scientific domains based on their ego-networks (Freemann 1982). However when trying to generalize neural network approaches to the task of graph classification there are several aspects that differ widely from image classification. When trying to perform graph classification, we can deal with graphs of different sizes. To compare them we first need to obtain graph representation that is independant of the size of the graph. Moreover, for fixed graph, nodes are not ordered. The graph representation obtained with neural network algorithms must be independant of the order of nodes and thus be invariant by node permutation.
Aggregation functions are functions that operate node embeddings to produce graph representa- tion. When tackling a graph classification task, the aggregation function used is usually just a mean or max of node embeddings as illustrated in figure [b But when working with graphs of large sizes, the mean over all nodes does not allow us to extract significant patterns with a good discriminating power. In order to identify patterns in graphs. some methods try to identify structural roles for nodes. Donnat et al. (2018) define structural role discovery as the process of identifying nodes which have topologically similar network neighborhoods while residing in potentially distant areas of the network

---

Under review as a conference paper at ICLR 2021
illustrated in figure Those structural roles represent local patterss in graphs. Identifying them and comparing them among graphs could improve the discriminative power of graph embeddings obtained with graph neural networks. In this work, build aggregation process based on the identification of structural roles, called StructAgg.
The main contributions of this work summarized bellow:
1. Learned aggregation process. A differentiable aggregation process that learns how to ag- gregate node embeddings in order to produce a graph representation for graph classification task.
2. Identification of structural roles. Based on the definition of structural roles from Donnat ct al.] (2018), our algorithm learns structural roles during the aggregation process. This is innovative because most algorithms that learn structural roles in graphs not based graph neural networks.
3. Explainability of selected features for a graph classification task. The identification of structural roles enables understand and explain what features selected during training. Graph neural networks often lack explainability and there are only few works that tackle this issue. One contribution of this work is the explainability of the approach. We show how our end-to-end model provides interpretability to graph classification task based on graph neural networks.
4. Experimental results. Our method achieves state-of-the-an results on benchmark datasets. We compare it with kernel methods and state-of of-the-art message passing algorithms that use pooling layers aggregation processes.
(a) nodes with the same structural role are clas- sified together (same color).
(b) aggregation process to create graph embedding, the node features summed produce representation of the graph.
Figure 1: Identification of structural roles and aggregation of node features over the whole graph.
RELATED WORK
The identification of nodes that have similar structural roles usually done by an explicit featurization of nodes or by algorithms that rely on random walks to explore nodes' neighborhoods. A well known algorithm in this line of research RolX (Gilpin et al. 2013 Henderson al. 2012). matrix factorization that focuses on computing soft assignment matrix based on listing of topological properties set as inputs for nodes. Similarly struct2vec builds a multilayered graph based on topological metrics on nodes and then generates random walks capture structural information. In another line of research, many works rely on graphlets to capture nodes' topological properties and identify nodes with similar neighborhoods (Rossi et al. 2017 Lee et al. 2018 Ahmed et al.) 2018). In their work, Donnat et al. (2018) compute node embeddings from wavelets in graphs to caracterize nodes' neighborhood at different scales.
In this work, we introduce an aggregation process based on the identification of structural roles in graphs that is computed in end-to-ent trainable fashion. We build a hierarchical representation of nodes by using neural network models in graphs to propagate nodes' features at different hops. Recently there has been rich line of research, inspired by deep models in images, that aims
2

---

Under review as a conference paper at ICLR 2021
redefining neural networks in graphs and in particular convolutional neural networks (Defferrard et al. 2016; Kipf & Welling, 2016; Veličković et al. 2017 Hamilton et al. 2017 Bronstein et al. 2017 Bruna et al. 2013 Scarselli et al. 2009). Those convolutions be viewed meesage passing algorithms that are composed of two phases. A message passing phase that runs for T steps is first defined in terms of message functions and vertex update functions. A readout phase then computes a feature vector for the whole graph using some readout function. In this work we will see how to define a readout phase that learnable and that is representative of meaningful patterns in graphs.
3 PROPOSED METHOD
In this section we introduce the structural aggregation layer (StructAgg). We show how we identify structural classes for nodes in graphs; how those classes are used in order to develop an aggregation layer; and how this layer allows compare significant structural patterns in graphs for supervised classification task.
3.1 NOTATIONS
Let G E, be graph, where V is the of nodes of G, E the set of edges and X E Rxx the feature matrix of G's s nodes where f is the dimensionality of node features. Let n = [V] be the number of nodes of G and e | the number of edges of G.
Let A be the adjacency matrix of graph G and D) be its degree diagonal matrix. Let U; and ny be the tth and jth nodes of G, we have:
Ag =
{
if 0y) E Dus EAu
otherwise
Let (G,,..., Ga) be set of graphs and (B1.-.,, Vak be the labels associated with these graphs.
3.2 HIERARCHICAL STRUCTURAL EMBEDDING
Graph neural networks. We build our work upon graph neural networks (GNNs). Several archi- tectures of graph neural networks have been proposed by Defferrard et al. (016);; Kipf & Welling (2016); (Velikkvel et (2017) or Bruna & Li (2017). Those graph neural network models are all based propagation mechanisms of node features that follow general neural message passing architecture YYing et al. 2018 Gilmer et al. 2017):
= X0;
where (0) E RR are the node embeddings computed after steps of the GNN, ( X, and MP is the message propagation function, which depends on the adjacency matrix. ( is trainable weight matrix that depends on layer Let fi be the dimension of the node vectors after steps of the GNN, fo f.
The aggregation process that we introduce next can be used with any neural message passing algorithm that follows the propagation rule In all the following of our work we denote by M P the algorithm. For the experiments, we consider Graph Convolutional Network (GCN) defined by (Kipf & Welling 2016). This model is based on an approximation of convolutions on graphs defined by (Defferrard et al.]|201 2016) and that use spectral decompositions of the Laplacian. The popularity of this model comes from its computational efficiency and the state-of-the-art results obtained on benchmark datasets. This layer propagates node features to 1-hop neighbors. Its propagation rule is the following:
x(+1) MP(A, MP.AA GCN(A, = -,
3

---

Under review as a conference paper at ICLR 2021
Where p is non-linear function (a ReLU in case), A = A In is the adjacency matrix with added self-loops and D -
This propagation process allows us to obtain a node representation representing its l-hop neighborhood after layers GCN. We build a hierarchical representation for nodes by concatenating their embeddings after each step of GCN. The final representation X Xstracts of node is given by:
I. || 1=1
X sttructi
x
(3)
Where L is the total number of GCN layers applied.
Identifying structural classes. Embedding nodes with MP creates embeddings that close for nodes that are structurally equivalent. Some use handcrafted node embedding based on propagation processes with wavelets in graphs identify structural clusters based hierarchical representation of nodes (Donnat et al. 2018). By analogy, we learn hierarchical node embeddings and an aggregation layer that identifies structural roles for node in graphs. Those structural roles consistent along graphs of a dataset which allows us to bring interpretability to our graph classification task.
Node features Xstruct contain the information of their L-hop neighborhood decomposed into L vectors each representing their (-hop neighborhood for varying between 1 and L. We will show next that nodes that have the same L-hopp neighborhood are embedded into the same vector. To identify structural roles, we thus project each node embedding on a matrix E R Ristruet where
is the number of structural classes and fstruct
Σ fi is the dimensionality of Xstructs for each 1=1
node obtain a soft assignment matrix:
softmax (X struct)) Raxe
(4)
Where the softmax function is applied in row-wise fashion. This way, Cij represents the probability that node belongs to cluster j.
Definition 1. Let i and j be two nodes of a graph G = (V,E, -f) (i' S
be the l-hop neighborhood of which means all the nodes that are at distance lower of equal to of d being the shortest -ptt distance. Let X N, be the feature matrix of the l-hop neighborhood of Let Gij be the subgraph of G composed of the l-hop neighborhood of We say that i and are l-structurally equivalent if there exists isomorphism vb from.N(() Ni(1) such that the two following conditions are verified:
G.,1 = (GG,))
Yj' E EMG)), = X,'
Theorem 1. Two nodes i and j that are L-structurally equivalent have the same final embedding, X strrutt
X struct--
3.3 STRUCTURAL AGGREGATION
After having identified structural classes, we aggregate node embeddings over those classes, as illustrated in f The goal obtain an embedding that discriminates graphs that not belong to the same class and that selects similar patterns in graphs of the same class. Graphs that have similar properties and thus similar node patterns should have nodes with similar roles and similar embeddings.
Performing a structural aggregation. The structural aggregation aims at comparing embeddings of nodes that have similar roles in the graph. When computing the distance between two graphs, if those two graphs have the same distribution of structural roles, they will have embeddings that are close. Nodes that leaves nodes that are central in the graph should be compared separately.
4

---

Under review as a conference paper at ICLR 2021
Mathematically, the variance over all nodes if the graph may be high and decomposing nodes per structural roles aims at decreasing the variance per cluster and thus at bringing more information to the final graph embedding.
The structural aggregation layer performs an aggregation per structural role. This aggregation is mean of embeddings of nodes that belong to the same cluster. The final embedding is concatenation of the mean embeddings of the nodes per cluster of structural role.
Egraph = C2 XL)) E IR
Proposition 1.
The embedding graph is invariant by node permutation.
Moreover when performing soft classification, the output cluster assignment for each node should generally close to a one-hot vector so that each node has clear structural role identified. We therefore regularize the entropy of the
n cluster assigmnent matrix by minimizing Lyeg = Σ (C..) where H(C..)
is the entropy of the assignment vector C. of node i. This is often done when identifying classes for nodes. The same regularization is applied in (Ying et al. 2018) to identify communities in graphs develop a pooling layer.
Figure 2: Aggre- gation of node fea- tures structural classes
Remarks.
The structural classes identified by algorithm are local. They contain the information of the L-hop neighborhood of each node.
Compared to the structural embedding presented in Donnat al. (2018), our algorithm needs multiple graphs and is trained in su- pervised fashion. Donnat et al. (2018) introduced a node embedding that allows to identify structural classes in a single graph. It is not straightforward how to generalize this procedure to the case of set of graphs. Indeed, when dealing with single graph, this procedure is very efficient identifying structural roles. However, those structural roles are defined per graph and thus two nodes that have the same structural role but that lie in two different graphs can have embeddings that differ and can thus be classified in two different classes.
3.4 INTERPRETABLE GRAPH NEURAL NETWORK
Graph neural networks lack interpretability. In the case of convolutional neural networks on images, it is possible to visualize the activation of certain layers to have an idea of the patterns that are selected during the process image classification and of which pattern is usefull to discriminate images of certain class from the rest of the images of dataset. In the case of graphs, most algorithms based on neural network models bring no interpretability regarding the features that are selected and that make the classification accurate.
In this work, we bring some interpretability to this class of models and illustrate it in the next sections in experiments. By propagating information from node to node, we are able to identify structural roles in graphs. Those structural roles contain the information of local neighborhoods of nodes and of their local topological structure. By identifying roles in graphs, we compare between graphs the embeddings per structural roles. This way, caracterize each class with the combination roles they are made of. We show through extensive experiments that the information contained in the identification of roles allows to discriminate graphs of different classes and lead the way to other works that could bring interpretability to this field of research.
identify roles that are specific
certain class and
EXPERIMENTS
4.1 GRAPH CLASSIFICATION
Datasets: We choose a wide variety of benchmark datasets for graph classification to evaluate our model. The datasets can be separated in types. 2 bioinformatics datasets: PROTHINS and
5

---

Under review as a conference paper at ICLR 2021
D&D; and social network dataset: COLLAB. In the bioinformatics datasets, graphs represent chemical compounds. Nodes are atoms and edges represent connections between two atoms. D&D and PROTEINS contain two classes of molecules that represent the fact that molecule be either active or inactive against certain type of cancer. The aim to classify molecules according to their anti-cancer activity. COLLAB composed of ego-networks. Graphs' labels are the nature of the entity from which we have generated the ego-network. In Table [ we report some information on these datasets such the maximum number of nodes in graphs, the average number of nodes per graph, the number of graphs, the size of node features f (if available) and the number of classes. More details can be found in (Yanardag & Vishwanathan 2015). We also use the new database Open Graph Benchmark (OBG) to test our method on larger datasets (Hu et al. 2020). We use the ogb-molhiv dataset whose properties are listed bellow. Each graph represents a molecule, where nodes are atoms, and edges are chemical bonds. Input node features are 9-dimensional, containing atomic number and chirality, as well as other additional atom features such as formal charge and whether the atom is in the ring not.
We perform 10-fold cross validation split which gives 10 sets of train, validation and test data indices in the ratio 8:1:1. We use stratified sampling to ensure that the class distribution remains the structural roles, Ir the learning rate and finally the dimensions of the successive layers respectively chosen from the sets {2, 5, 10, 20). {0.01, 0.001, 0.0001). {8. 16, 32, 64, 128, 256}. The sets from which our hy perrparraeterss are selected vary according to the sizes of graphs in each dataset. We do set maximum number of epochs but we perform early stopping stop the training which means that we stop the training when the validation loss has not improved for 20 epochs. We report the mean accuracy and the standard deviation over the 10 folds on the validation set. We compare our method with kernel methods and with graph neural network that uses pooling layers (Ying al. (018). We should note that kernel methods do not use node features that are available on bioinformatics datasets. For COLLAB, we don't t have any features available nodes. We compute the one-hot encoding of node degrees that we use as node features for our algorithm.
Experimental setup:
across splits. We fine tune hyperparameters Trroes the number of
From the results of Table we can observe that StructAgg is competing with ffte-offthhear methods. Indeed, on most datasets, StructAgg has a score very close to those obtained by Ying et al. (2018) and Gao & Jil (2019). From Table StructAgg outperforms all algorithms COLLAB. Moreover, StructAgg allows us to improve classification results from GCN on ogb-molhiv dataset as illustrated in figure
Results:
Dataset
D&D
PROTEINS
COLLAB
Max #Nodes
5748
620
492
Avg #Nodes
284.32
39.06
74.49
#Graphs
1178
1113
5000
89
3
classes
2
Graphlet (Shervashidze et al.
2009
74.85
72.91
64.66
Shortest-Pard (Borgwardt & Kriegel
2005
78.86
76.43
59.10
1-WL
Shervashidze et al.
2011
74.02
73.76
78.61
WL-OA Kriege al.
2016
79.04
75.26
80.74
GraphSage Hamilton et al.
2017
75.42
70.48
68.25
DGCNN Zhang al.
2018
79.37
76.26
73.76
DIFFPOOL
(Ying al.
2018
80.64
76.25
75.48
g-U-Nets
Gao & Ji
2019
82.43
77.68
77.56
StructAgg
78.42
0.97
76.72 + 2.53
80.26 2.73
Table 1: Classification accuracy bioinformatics datasets

---

Under review as a conference paper at ICLR 2021
#Node per Graph
#Edges per Graph
Name
#Graphs
GCN
streutAgg
ogbg-molhiv
41127
25.5
27.5
0.7606 0.0097
0.7701 +: 0.0102
Table 2: OGB dataset for graph classification. The score reported is the ROC-AUC score.
4.2 IDENTIFICATION OF STRUCTURAL ROLES
(d)
(D)
Figure 3: Molecules drawn for bioinformatics dataset. The colors represent structural classes identified by our algorithm in figures Ba 3b and [3 compared to the output of GraphWave in figures 3d 3e and 3T To compare the structural classes output by the two algorithms, 3a and 3d are the same molecule, 3b and Belalso and (3c]and are the same molecule. To obtain comparable results, we run our algorithm and output the structural classes for each molecule. For each molecule, we then run Graph with the number of classes from StructAgg being set input of GraphWave.
We show some examples molecules of a molecular dataset and the roles identified by our algorithms. From figure we can see that there is some consistence the assignment of nodes structural roles. Moreover, great advantage of our method is that it takes into account node features that are in our case one-hot encoding of the atom type. Compared to Donnat al. (2018) whose embeddings do not include node features, our method identifies roles in macroscopic fashion by identifying similar roles in the whole dataset and not
single graph. Most methods rely on computed features that correspond to single graph and do not generalize to multiple graphs because of scales issues. It is the case for Graph Wave for which features computed in order to cluster nodes per roles depend on role assignment with GraphWave, computed assignments
the size of the graph. To compare per graph and not along the whole dataset. We can note that compared to Graph Wave, our algorithm uses node features select structal roles.
7

---

Under review as a conference paper at ICLR 2021
4.3 IMPORTANCE OF STRUCTURAL PATTERNS
Identifying roles graphs boils down to identifying significant patterns. As shown in subsection 4.2 the roles that we were able to identify represent coherent patterns in graphs. Graphs' final embeddings are made of two parts. Nodes' embeddings that are the result successive GCNs and the allocation of all nodes to different structural classes. We would like to quantify how much information is contained the structural roles and the decomposition of the graph in e classes improves our classification accuracy. To this end, from trained algorithm, we compute all allocation matrices of all graphs of dataset.
In order validate the fact that roles themselves have a high discriminative power, need to identify combinations of roles that are specific to different classes. We thus want to identify the structural roles that compose each graph.
Let's consider graph G and an allocation matrix C' E I We obtain a soft assignment matrix. We compute on it histogram per class over each node of the graph. The feature vector now concatenation of all histograms per class. We have:
FeatG = || j=1
hist(C.j, bins) E R binawo
Where bins is the number of bins for the histogram. The histogram upper and lower bounds are and because the values of C' are the output of softmax function.
Let (G1,.., Ga) be d graphs of labels (y1,.... Ma). After having computed all graphs' histograms we imputs of classifier. We use SVM and
obtain d vectors (Feate, s..., Feata,) that we display the results in tableeiin in order to compare the information that comes from the strutural roles identification and the information that comes from node embeddings.
We can see that the accuracy is lower when we don't consider node embeddings which is consistent with the fact that a lot of information is contained in the embeddings of nodes that are the outputs of GCNs. But the accuracy is significantly higher than random model which proves that we can identify some patterns in the distribution of structural roles among graphs and that those patterns are good first approximation to separate classes in dataset.
Dataset
D&D
PROTEINS
COLLAB
StruetAgg
78.42 = 0.97
76.72 + 2.53
80.26 = 2.73
StructHist
74.54 = 2.87
73.68 +:2 2.03
70.94 = 2.08
Table 3: Classification accuracy based the histogram of the assignment matrix (StructHist) compared to our algorithm (StructAgg).
CONCLUSION
Graph neural networks are very effective to build node embeddings by propagating node features in graphs. But in order to build a graph representation from these embeddings there are several ways to procede. In this work, we proposed a novel technique based on the identification of structural roles for nodes in graphs. We showed that the identification of roles allows us to compare patterns between graphs that are significant for graph classification. Moreover, this work opens new perspectives the field of explainability of graph neural networks. We showed that these patterns brought explainability to this task and to which kind of structures are selected by our algorithm during the process of graph classification. A better understanding of which features are selected during training can enable us to develop new methods based on drawn conclusion and maybe open new perspective applied mathematies for drug discovery.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Nesreen K Ahmed, Ryan Rossi, John Boaz Lee, Theodore L Willke, Rong Zhou, Xiangnan Kong, and Hoda Eldardiry. Learning role-based graph embeddings. arXiv preprint arXiv:1802 02896, 2018.
Karsten M Borgwardt and Hans-Peter Kriegel. Shortest-path kernels on graphs. In Data Mining, Fifth IEEE International Conference on, pp. 8-pp. IEEE, 2005.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18-42. 2017.
Joan Bruna and Xiang Li. Community detection with graph neural networks. arXiv preprint 1rXivv170S.08415. 2017.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:13/2.6200 2013.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filterin.. In Advances in Neural Information Processing Systems, pp. 3844-3852, 2016.
Jacob Devlin, Ming-Was Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint /8.0vv18810004805, 2018.
Claire Donnat, Marinka Zitnik, David Hallac, and Jure Leskovec. Learning structural node embed- dings via diffusion wavelets. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1320 1229. ACM, 2018
Linton C Freeman. Centered graphs and the structure of ego networks. Mathematical Social Sciences, 3(3):291-304, 1982.
Hongyang Gao and Shuiwang Ji. Graph u-nets, arXiv preprint arXiv:1905.05111 2019.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference Machine Learning- Volume 70, pp. 1263-1272. JMLR. org, 2017.
Sean Gilpin, Tina Eliassi-Rad, and Ian Davidson. Guided learning for role discovery (glrd) framework, algorithms, and applications. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 113-121, 2013.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in neural information processing systems, pp. 1024-1034, 2017.
David Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2): 2011.
Keith Henderson, Brian Gallagher, Tina Eliassi-Rad Hanghang Tong, Sugato Basu, Leman Akoglu, Danai Koutra, Christos Faloutsos, and Lei Li. Rolx: structural role extraction & mining in large graphs. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 1231-1239, 2012.
Weihua Hu, Matthis Fey, Marinka Zitik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.000 2020.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: 1609.02907, 2016.
Nils M Kriege, Fierre-Lous Giscard, and Richard Wilson. On valid optimal assignment kernels and applications to graph classification. In Advances in Neural Information Processing Systems, pp. 1623-1631, 2016.

---

Under review as a conference paper at ICLR 2021
Yann LeCun, Yoshua Bengio, et al. Convolutional networks for images, speech, and time series. The handbook of brain theory and neural networks, 3361(10):1995, 1995.
John Boaz Lee, Ryan A Rossi, Xiangnan Kong, Sungchul Kim, Eunyee Koh, and Anup Rao. Higher- order graph convolutional networks. arXiv preprint arXiv: 1809.0880007777 0809.07697, 2018.
Ryan A Rossi, Rong Zhou, and Nesreen K Ahmed. Deep feature learning for graphs. arXiv preprint arXiv:1704.08822 08829, 2017.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang. Andrej Karpathy, Aditya Khosla, Michael Bernstein, al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115(3):211-25,, 2015.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80 2009.
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. Efficient graphlet kernels for large graph comparison. Artificial Intelligence and Statistics, pp.
488-495, 2009.
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lhmmn graph kemels. Journal of Machine Learning Research, 12(Sep): 2539-2561, 2011.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10903, 2017.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 2 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1365-1374. ACM, 2015.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In Advances in Neural Information Processing Systems, pp. 4800 4810, 2018.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Thirty-Second AAAI Conference Artificial Intelligence, 2018.
A APPENDIX
You may include other additional sections here.
B PROOFS
B. PROOF OF THEOREM
Theorem 2. Two nodes and j that are L-structurally equivalent have the same final embedding, X Xetructs = X-tructj-
Proof. Let and j be two nodes of graph G = (V, E, that are L-structurally equivalent. Let P(I) be the following proposition:
Two nodes that are /-structurally equivalent for some 1, have the same embedding after I steps of GCN.
Let's prove this proposition by induction.
P(0) is true, two nodes that have the same embedding are 0-structurally equivalent after 0 step of GCN.
Let P(I) be true and let's prove P(L + 1).
Let and be nodes that l-structurally equivalent. After step of GCN have:
10

---

Under review as a conference paper at ICLR 2021
x GCN((A
So we have:
(D-12AA--12x())= = E
x
(EN(() Vdddy
Since i and are L-structurally equivalent, there exists an isomorphism v/ such that:
Vi' E Ni(i), E Ni()) such that x =
xx -(()) (()") x
Be X E PeGiNG ((1 E G,p' S'EN()) Vaccsdoors 4(4) jEN(() vd,d, x.)
(1)(() ddid,
9 x-(+11) = -100-12_b-11xx(11")
= -x((+1)
So two nodes i and j that are L structurally equivalent, are structurally equivalent for all between 0 and L and thus, Xstract; Xstruct, because X is the concatenation of embeddings after each layer.
B.2 PROOF OF PROPOSITION 2
Proposition 2. The embedding Zrraph is invariant by node permutation.
Proof. Let P E 0, nMx be any permutation matrix. Since is a permutation matrix we have PP = I. have (1++)) = GCN(PAP" (X
Z Zgraph~ = cd (())
(so (tmmat (X strr (L)
= (softmar( (P PX sttrraa))) pa PX(L)
Since the softmax is applied in row-wise fashion, we have:
Z Zgraph
(PT softmax([X stxttruc))) pT PX(1)
(ettmar(XXatratt]a) (L
Pgraph
Where Pgrrpp is the embedding of our graph to which we have applied the permutation P
11


Reviews:
[{"review_id": "NREjcrPTEk", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed the StructAgg, an aggregation algorithm in convolutional graph neural network that learns the structural roles for nodes in the graph embedding. In this algorithm, a structural representation of node is constructed through concatenation of latest p layers of node presentation in graph neural network, which consists of information from the p-hop neighborhood. The paper is good quality and its demonstration is clear.  The idea behind is original. However, learning embeddings through concatenation of multiple layers of neural representation is not completely new. The contribution of this paper to the community is not ground-breaking as well.  From the experiment results, it is hard to stress its significance as in most of times this method does not beat the state-of-the-art algorithms. \n\nPros: \n1.  As opposed to previous studies, this paper focus on learning node embeddings that preserve local information in a larger p-hop neighborhood. Such idea assumes that the node structural role can be identified via its neighborhood and the node embeddings should carry information regarding its structural roles. To achieve that, the learning algorithms should balance the predictability of the embedding in the node classification as well as the consistency of node representation towards underlying clustering in the graph. \n2.  The proposed representation learned by StructAgg, is able to provide the clustering of nodes as well as the node embeddings that are invariant to the permutation. \n3.  The StructAgg only need to concatenate the existing learned representation in lower layers, thus it is easy to implement. \n\nCons: \n1.  Ulta-high dimensional representation as the size of local neighborhood of interest increases: The concatenation operation expands the dimensionality of embeddings drastically as the local neigborhood expands. As a result, the StructAgg representation can only feasibly represent a structures that are present in small neighborhood graph. In some graph like trees, it is fine. But in complex graphs, with larger local structures, it is not efficient in both storage and computation. \n2. Tradeoff between the classification and clustering:  The proposed method defines the loss function as the combination of supervised node classification loss and unsupervised node cluster assignment loss (in terms of entropy of softmax assignment). The formation of this joint loss function implies that the node label is assigned consistently according to the structural role of the node in the graph with the number of total structural classes in the graph known. It can be imagined that with the number of structural classes increases, the label assignment may not be consistent and will result in decrease of performance. It seems that this method is more suitable for two or three structural classes as shown in the experiment. \n3.  Lack of robustness: The message passing algorithm in small neighborhood tends to preserve not just local information and local noises. In StructAgg, since the aggregation happens only within the same cluster, the noise level in different clusters may varies a lot, depending on the size of cluster. It is more likely to create noisy embeddings in this small clusters and present them in the final embeddings, while in traditional aggregation, such noise level is suppressed due to the involvement of more nodes.\n\nSome question need to clarify:\n1.  In proof of theorem 1, please explain for $\\sum_{i^{'}\\in \\mathcal{N}(i)}\\frac{a_{i,i^{'}}}{\\sqrt{d_{i}d_{i^{'}}}}X_{i^{'}}^{(l)} = \\sum_{j^{'}\\in \\mathcal{N}(j)}\\frac{a_{j,j^{'}}}{\\sqrt{d_{j}d_{j^{'}}}}X_{\\psi(j^{'})}^{(l)}$, what is the relation between coefficients $\\frac{a_{i,i^{'}}}{\\sqrt{d_{i}d_{i^{'}}}}$ and $\\frac{a_{j,j^{'}}}{\\sqrt{d_{j}d_{j^{'}}}}$. Also should it be like $\\sum_{j^{'}\\in \\mathcal{N}(j)}\\frac{a_{\\psi(j),\\psi(j^{'})}}{\\sqrt{d_{\\psi(j)}d_{\\psi(j^{'})}}}X_{\\psi(j^{'})}^{(l)}$ ?\n\n2. In proof of proposition 2, please explain in detail the reason behind $(softmax(P^{T}PX_{struct}p))^{T}P^{T}PX^{L} = (P^{T}softmax(PX_{struct}p))^{T}PP^{T}PX^{L}$. Here i believe it should be $(softmax(P^{T}PX_{struct}p))^{T}P^{T}PX^{L} = (P^{T}softmax(PX_{struct}p))^{T}P^{T}PX^{L}$, with a mistakenly added $P$ in original draft.  The reason is that the softmax is row operation, a row permutation $P^{T}$ does not affect the result of $softmax(\\cdot)$ at each row but their ordering. So  $softmax(P^{T}\\cdot)= P^{T}softmax(\\cdot)$, thus $(softmax(P^{T}PX_{struct}p)) = (P^{T}softmax(PX_{struct}p))$. This leaves \n$(softmax(P^{T}PX_{struct}p))^{T}P^{T}PX^{L} = (P^{T}softmax(PX_{struct}p))^{T}P^{T}PX^{L} \n= (softmax(PX_{struct}p))^{T}PP^{T}PX^{L}  = (softmax(PX_{struct}p))^{T}PX^{L} $", "extra_scores": {}, "extra_text": {}}, {"review_id": "LMlllUkBIN", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work tries to identify  local patterns that can be used to provide explainability to GNN models. Different from previous work using simple pooling function to generate graph representation, this work clusters nodes into a predefined number of clusters using their embeddings from L-hop neighbors. Each cluster produces a pooling representation. The representations of all clusters are concatenated to form the representation of the whole graph. However, the manuscript was not well written with some confusing notations and logical problems. It should be beneficial to readers if the manuscript can first clearly demonstrate problems in existing graph classification problems. Some analyses are not solid. The proposed method performed obviously worse than several baseline methods.\n\nThis work assumes that similar node embeddings should have similar structural roles and thus should be clustered together. Nodes with the same local structure may have the same embeddings, but not the other way around may not be true. The structural roles are defined is based on embedding similarity, which doesn’t guarantee to enhance explainability. The author(s) claimed that most GNNs were not explainable. This is not quite true. Recently, the attention mechanism was used in GNNs to enhance explainability. There exist some other works, like GNNExplainer, aiming at explainable GNNs.\n\nThe baseline models compared in this paper were proposed several years ago and not mainly focused on graph readout function. More typical methods for global pooling were missing in comparison. For instance, GlobalAttention (https://arxiv.org/abs/1511.05493) is also an explainable readout function. ASAPooling (https://arxiv.org/abs/1911.07979) is a recent work that also learns a sparse soft cluster assignment for nodes in the pooling phase. In addition, the proposed method performed worse than many baseline models in many cases. For experiments on OGB datasets, it only compares with original GCN model, but there has been a lot of state-of-art models proposed several month ago, achieving much better results than this paper. You can find the latest results on https://ogb.stanford.edu/docs/leader_graphprop/. \n\n\nSome notations need improvements.\n1.\tEquation (2): The trainable weight matrix is missing in GCN(A, X).\n2.\tDefinition 1 denotes two nodes as u and v, but the notation becomes i and j when representing their l-hop neighbors. X is first used as the feature matrix but later used to indicate node vector.\n\nSome claims are not correct.\n1.\tIn Section 3.2, “Embedding nodes with MP creates embeddings that are close for nodes that are structurally equivalent.” When many GCN layers are stacked together, final node embeddings tend to become similar.\n2.\t “When computing the distance between two graphs, if those two graphs have the same distribution of structural roles, they will have embeddings that are close. ” This may be true, but the overall graph topology information is omitted. Here structural roles represent local patterns. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "J333isNg_89", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "==========Summary==========\n\nIn this paper, the authors investigate how to improve pooling functions in graph neural networks for the purpose of better addressing graph classification problems. The core idea in this paper is to group node representations. In particular, the authors develop StructAgg, a softmax based implementation, to parameterize the grouping process, and the parameters in StructAgg can be learned from downstream supervision signals. Empirical results focus on three aspects: (1) Improvement in graph classification accuracy brought by StructAgg; (2) Visualization on grouped node representations; and (3) Comparison between two variants of StructAgg.\n\n==========Reason for the rating==========\n\nFor the current draft, I am leaning to reject. Although pooling for graph classification is a meaningful problem, it is difficult to see the unique perspective or value in the proposed technique compared with existing approaches. For now, the technical depth in this paper seems to be limited, and more convincing empirical evidences are expected.   \n\n==========Strong points==========\n1. This paper delves into a meaningful problem. Indeed, pooling functions in graph neural networks are critical for graph classification tasks. While existing solutions are simple and efficient, they may be sub-optimal in some cases.\n\n2. The authors propose a grouping-based method to reduce variance in graph representations, which potentially could improve generalization performance.\n\n3. Empirical evidences are provided to confirm the effectiveness and impact from StructAgg.\n\n==========Weak points==========\n1. The idea of \"grouping node representations using softmax for graph classification\" may have been investigated in existing works, e.g., [1]. For the core idea in this paper, the authors may need to discuss its connection with existing literature, and highlight the unique perspective.\n\n2. The technical impact of this paper could be limited. \n    - From the current draft, the proposed StructAgg looks like incremental changes to the existing methods. The authors may provide more theoretical or empirical evidences to motivate the problem, highlight the uniqueness in the technique, and justify their design choices.\n    - The theoretical results in Theorem 1 may need more work. Theorem 1 could aim to answer an important question in StructAgg, but the authors may raise the question first and justify why this is an important/non-trivial question. \n\n3. The empirical evidences could be stronger. \n    - From the current results, StructAgg only performs the best in one of the three datasets. The authors may consider more datasets that can highlight the value of StructAgg.\n    - StructAgg may work with the existing GNNs. The authors may connect StructAgg with the existing GNNs, and demonstrate the incremental gain from StructAgg.\n    - For the evaluation in Table 2, it is unclear why the comparison is limited between GCN and the proposed technique.\n    - For the evaluation in Table 3, the claim on \"node embedding\" may not be sound. Between StructAgg and StructHist, the difference is not just \"node embedding\", and one cannot ignore the impact from \"histogram\". The authors may need to carefully reason the conclusion from the empirical numbers.\n\n==========Questions during rebuttal period==========\n\nPlease address and clarify the weak points above. \n\nIn addition, it will be great if the authors could address the following questions.\n\nQ1. As the authors emphasize the term \"node embedding\", does this paper target on transductive or inductive settings? \n\nQ2. For the entropy minimization discussed in Section 3.3, is it going to bring more overfitting risk?\n\nQ3. For the first condition in Definition 1, it is a bit vague. The authors may give a more accurate mathematical description.\n\nQ4. For the first bullet in Remarks under 3.3, what does \"The structural classes identified by our algorithm are local\" exactly mean?\n\nQ5. In the experiment setup, what do $l_1$ and $l_2$ refer to?\n\n==========Reference==========\n\n[1] Substructure Assembling Network for Graph Classification, AAAI 2018\n\n==========Post rebuttal==========\n\nThe authors' response does not fully address my concerns. I keep the rating as it is. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "A4DqtLXz4-", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper focuses on deriving explainable features for use in graph classification. To that end, they propose StructAgg that is essentially an aggregation process based on the structural roles of nodes that is then used in an end-to-end model. Experiments demonstrate the effectiveness of the proposed approach as it provides comparable performance while providing some explainability. This is an important unsolved problem, and this work provides one such approach to obtain more explainable and intuitive features/embeddings for graph classification.\n\nThe example provided in Figure 1 (a) is trivial in the sense that one can assign structural roles to nodes based on degree. For instance, red nodes all have degree 1, orange nodes have degree 3, and yellow nodes have degree 2. Please provide a better example such as the one used in the recent survey paper “On Proximity and Structural Role-based Embeddings in Networks” (see Figure 1) where this is not the case, and one must look at the actual structural properties to discover roles. Also, I suggest showing actual meaningful features in (b) as this would make the example more complete. There are a few papers related to structural roles that are missing and should be referenced appropriately. For instance, using roles for graph similarity and comparison is discussed in “Role Discovery in Networks”. There are also incorrect references to a paper from 2018 for structural roles that need to be fixed. Overall, this paper is interesting, the problem is important, and the approach is shown to be effective.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper addresses an important unsolved problem, i.e. deriving explainable features for use in graph classification. It does it by providing:
i)  a simple to implement (local) node aggregation approach;
ii) some theoretical support to the proposed approach;
iii) empirical evidence that the proposed approach could be effective.

Notwithstanding the above merits, the reported work seems to still be in a preliminary phase. In fact:
i) reference to literature is missing some important recent contributions to the addressed problem (e.g.  Gated Graph Sequence Neural Networks, GNNExplainer);  if possibile, also experimental comparisons vs those approaches is desirable;
ii) experimental results do not provide a solid evidence that the proposed approach can really help to provide a clear explanation of the output, and the overall performance in classification is mostly below SOTA models; adding more datasets could help to give a more solid support to the main statement about explainability/performance;
iii) presentation needs to better highlight the original contribution w.r.t. relevant literature (which is not completely clear in the current version of the paper), to improve the explanation of proofs, to discuss (both from a theoretical and empirical perspective) some important issues, such as computational scalability with the increase of size of local structures, and robustness to noise of the proposed (local) aggregation method.

In summary, although the proposed approach seems to be of some value, more work is needed to better place the proposed approach in the context of current literature and to gain a stronger experimental support to the main claim of the paper w.r.t. explainability.
Decision: Reject