Automorphic Equivalence-aware Graph Neural Network
Authors: Fengli Xu
quanming yao
Pan Hui
Yong Li
Venue: NeurIPS 2021 Poster (2021)
Keywords: graph neural network
automorphic equivalence
structural role
graph analysis

Abstract: Distinguishing the automorphic equivalence of nodes in a graph plays an essential role in many scientific domains, e.g., computational biologist and social network analysis. However, existing graph neural networks (GNNs) fail to capture such an important property. To make GNN aware of automorphic equivalence, we first introduce a localized variant of this concept --- ego-centered automorphic equivalence (Ego-AE). Then, we design a novel variant of GNN, i.e., GRAPE, that uses learnable AE-aware aggregators to explicitly differentiate the Ego-AE of each node's neighbors with the aids of various subgraph templates. While the design of subgraph templates can be hard, we further propose a genetic algorithm to automatically search them from graph data. Moreover, we theoretically prove that GRAPE is expressive in terms of generating distinct representations for nodes with different Ego-AE features, which fills in a fundamental gap of existing GNN variants. Finally, we empirically validate our model on eight real-world graph data, including social network, e-commerce co-purchase network, and citation network, and show that it consistently outperforms existing GNNs. The source code is public available at https://github.com/tsinghua-fib-lab/GRAPE.

Automorphic Equivalence-aware Graph Neural Network
Fengli Xu', Quanming Yao
Pan Hui
Yong Li
BNRIST & EE Department, Tsinghua University
24Paradigm Inc.
3CSE Department, HKUST.
1 1iyong07@tsinghua eewighhuaaeeu......
Abstract
Distinguishing the automorphic equivalence nodes in a graph plays an essential role in many scientific domains, e.g., computational biologist and social network analysis. However, existing graph neural networks (GNNs) fail to capture such important property. To make GNN aware of automorphic equivalence, we first introduce a localized variant this concept - ego-centered automorphic equivalence (Ego-AE). Then, we design a novel variant of GNN, i.e., GRAPE, that uses learnable AE-aware aggregators to explicitly differentiate the Ego-AE of each node's neighbors with the aids of various subgraph templates. While the design of subgraph templates can be hard, we further propose a genetic algorithm automatically search them from graph data. Moreover, we theoretically prove that GRAPE is expressive in terms of generating distinct representations for nodes with different Ego-AE features, which fills in fundamental gap of existing GNN variants. Finally, we empirically validate our model on eight real-world graph data, including social network, e-commerce co- co-purchase network, and citation network, and show that it consistently outperforms existing GNNs. The source code is public available https:/ // gi thub. com/ts ts//ghunnnua-
GRAPE.
1 Introduction
The past few years have witnessed the phenomenal success of GNNs in numerous graph learning tasks, such as node classification [24], link prediction [59], and community detection [19], which is largely due their capability of simultancously modelling the connecting patterns and feature distribution in each node's local neighborhood. As result, it leads to a surge of interests from both academia and industry develop more powerful GNN models [52]. Despite of various architectures, the most popular GNNs. like GCN [24], GraphSAGE [19], GAT [48] and GIN [55], apply permutation invariant aggregate function on each node's 's local neighborhood to learn node embeddings, which leads to concerns about their representational power [17,55].
In this paper, we investigate GNN's expressiveness from important but largely overlooked angle, Le., the capacity to distinguish automorphic equivalence within each node's local neighborhood. Automorphic equivalence (AE) [14] is classic concept to differentiate the structural role of each node in given graph. Specifically, two nodes are considered to be AE only if they are interchangeable in some index permutations that preserve the connection matrix, i.e., graph automorphisms [35]. AB can identify the nodes that exhibit identical structural features in graph, which makes it a central topic in computational biologist, social network analysis and other scientific domains [33, 34]. For example, empirical studies show AE is an important indicator of social position and behavior similarity in social network [16, 37], which thus might significantly benefit GNN architecture design.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Empirically efficient heuristics have been proposed to identify the AE in moderate scale graphs by enumerating all the possible automorphisms [6. 45]. However, previous analytic methods only classify nodes into categorical equivalence sets. Although categorical features can be jointly optimized with GNNs under various frameworks [30, 54), little previous efforts are invested to principally incorporate AE into GNNs. Thus, we aim to design novel GNN model that is provably expressive in capturing AE features and can be tuned in a data-dependent manner based on the graph data and targeted applications, which will effectively allow us to learn expressive function to harness the power of AE feature.
Here, we propose GRaph AutomorPhic Equivalent network, i.e.. GRAPE, novel variant of GNN that can learn expressive representation by differentiating the automorphic equivalences of each node's ss neighbors. First, GRAPE extends the classic AE concept into localized setting, i.e., Ego-AE, to accommodate the local nature of GNNs. Specifically, Ego-AE identifies the local neighborhoods of each node by mapping with given subgraph templates and then partitions the neighboring nodes into Ego-AE sets based on the graph automorphisms in neighborhood. Second, we design a learnable AE- aware aggregators to model the node features in these Ego-AE sets, which adaptively assigns different weights to neighboring nodes in different Ego-AE sets and explicitly model the interdependency among them. Moreover, in order to capture complex structural features, GRAPE proposes to fuse the embeddings learned from Ego-AE sets identified by different subgraph templates with a squeeze-and- excitation module [22]. Finally, alleviate the barrier of subgraph template design, we propose an efficient genetic algorithm to automatically search for optimal subgraph templates. Specifically, gradually optimizes randomly initiated population of subgraph templates by iteratively exploring the adjacency of good performing candidates and eliminating the bad performing ones. To accelerate the search process, we further design an incremental subgraph matching algorithm that can leverage the similarity between subgraphs to greatly reduce the complexity of finding matched instances.
We theoretically prove that the proposed GRAPE is expressive in terms of learning distinct repre- sentations for nodes with different Ego-AB AE sets, which fundamentally makes up the shortcomings of popular GNN variants, e.g., GCN [24], GraphS AGE [19], GAT [48] and GIN [55]. Moreover, we empirically validate GRAPE on eight real-world datasets, which cover the scenarios of social network, citation network and e-commerce co- purchase network. Experiments show GRAPE is consistently the best performing model across all datasets with up to 26.7% accuracy improvement. Besides, case studies indicate GRAPE can effectively differentiate the structural roles of each node's neighbors. Moreover, the proposed genetic algorithm efficiently generates high quality subgraph templates that have comparable performance with the hand-crafted ones.
2 Related Works
In the sequel, we define a graph G = (V,E), where V {ui.... ........0 (v.). is the set of nodes and = {v,, v;)} is the set of edges. Let the feature vector of node v; be X(v)), and ((v:) represents the set of v; 's neighbor nodes. N is the number of node and M is the embedding size.
2.1 Automorphic Equivalence (AE) in Graph Analysis
Here, we investigate one of the most popular structural equivalence concepts, i.e., automorphic equivalence (AE) [14] which plays a central role in computational biologist, social network analysis and other scientific domains [33, 34). The most interesting part of AE is that it identifies the nodes with exact same structural patterns, e.g., degree and centrality [15], but not necessarily connecting to the same neighboring nodes. Basically, AE is defined as follows.
Definition 2.1. Given a graph G = EV, an automporphism π (+)) is a node permutation that preserves the adjacency matrix, ie., the permuted nodes x (vv)) and π (v6) are connected if and only if nodes vo and Up are connected. Two nodes Va and vn are considered to be Automorphic Equivalence (AE) if there is a graph automorphism that maps one onto the other, i.e., T (va) Ub-
Nodes that are AE with each other constitutes a AE set. An example of such sets Figure I (a). Specifically, AE sets can be identified by enumerating the automorphism group of the given graph with efficient Nauty algorithm [35], and the nodes that are mapped onto each others in different automorphisms will be partitioned into same AE sets.

---

Example Graph Adjacency Matric:
Matched with Trinngl:
P1
U4
Aggregator
0
0
Automorphism Group:
AE Sets:
Matched with chordal cycle:
F2
P2
F4
F2
1. Ma]
Aggregator 2
P. My P4
2g U. by Vg]
Up
By Pu
11 12
(a) Example Graph and AE Sets
(b) Ego-AE for v1 's Local Neighborhood (c) Computation Graph of MPNN
Figure 1: Illustration of AE and the limitation of MPNN framework.
Previous works have attempted preserve the structural similarities on graph via various node embedding algorithms [12, 2, 40]. Recently, GraphWave [12] was proposed to leverage wavelet diffusion patterns to capture the structural roles in node representations. Besides, role2vec [2] introduced generalized feature-based random walks that aims to represent the structural similarities among nodes.
However, the connection between AE and GNN has not been examined in existing literature. More- over, AE is defined on whole graph level, which infeasible compute in large graphs and goes against the inherent local nature of most GNN frameworks. In this paper, we aim to extend the AE concept local setting, and propose a novel GNN model to harness its power.
2.2 The Expressive Power of GNNs
The recent success of GNNs draws increasing interests in investigating their capability in capturing structural properties [55, 17J. Specifically, message passing neural network (MPNN) is the most popular GNN framework [18, 19, 55].
Let AGG be the aggregate function that collects feature from neighbors, and COMB be the combine function that integrates each node's 's self feature with those from AGG. Generally, MPNN generates representation for a node at k-th layer as
h COMB AGG(H(,1))
where h (x;) = (1;), and 1 = (h E (((e)). Existing MPNNs use local permutation invariant AGGs to compute node embeddings, which subsumes large class of popular GNN models such as GCN [24], GraphS AGE [19], GAT [48], Geniepath [31] and GIN [55]. The family of MPNNs is proven to be theoretically linked to Weisfeiler-Lchman (WL) subtree kernel [19]. Subsequently, they are at most as powerful as 1-WL test on discriminating graph isomorphisms [55].
More recently. several attempts have been made to improve the expressiveness of GNN beyond MPNN framework. They can mainly be classified into two categories: augmenting node features and designing more powerful architectures. In terms of augmenting node feature, recent works proposed to introduce various additional feature [42, 25, 59]. 3D-GCN uses additional 3D point cloud feature to differentiate neighbors and facilitate learnable graph kernels [29]. Moreover, GNN variants can in theory achieve universal approximation on graph by equipping nodes with randomly initialized feature vector [43], but they are difficult to generalize to different graphs in practice [5]. Previous work also proposed to augment node feature with substructure count [5], which however cannot reveal the local structural roles in each node's 's neighborhood. On the other hand, the previous efforts of designing more powerful GNN architecture are dedicated to different structural properties, egg., graph isomorphism [55] and graph moment [11]. Although AE is an important concept for graph data analysis, it has not been addressed by previous GNN research. More detailed comparison with the existing GNN variants is provided in Appendix A.
However, previous works have shown that identifying automorphic equivalence a strictly more difficult task than discriminating graph isomorphisms [46]. Specifically, two AE nodes always have
3

---

Template 5
1
Squeeze-and-En Loozze-and-Excitatton Excitttion
P
A
@
P3
P
P11
V4
P5
F1
Template S
hh(v))
V6
P1c
P3
22
P3
A2.3
(b) Mapping with subgraph templates
(d) Multi-channel node embedding fusion
(a) Input graph
(c) AE-aware aggregator
Figure 2: The GRAPE model. (a) The input graph with node e as ego node. (b) Mapping node VI 's neighborhood with given subgraph templates, where nodes with same color are Ego-AE. (c) Aggregating features from AE sets with learnable AE-aware aggregators. (d) Fusing multi-channel node embedding with squeeze-and-exciratio module.
isomorphic neighborhood, while the nodes with isomorphic neighborhood are not necessary AE [15]. Therefore, it raises concerns about MPNN's expressive power of AE feature, which has not been adequately investigated in previous research. In this paper, we aim to design a novel GNN model that provably expressive in modeling Ego-AE, which falling in the category of designing novel GNN architecture. To the best of our knowledge, capturing automorphic equivalence.
the first to empower GNN with the capability of
2.3 Genetic Algorithm
Genetic algorithm [13] is a widely adopted algorithm for combinatorial optimization problems, e.g. traveling salesman problem. Recently, has also been used to tune typer-parameters [32] and search neural architectures for deep networks [57, 53]. Basically, genetic algorithm mimics the natural selection process to iteratively to search for better solutions by exploring the adjaceney of promising candidates and eliminating the worst- const-performig ones [10]. Therefore, it can iteratively optimize the candidate population from parent generation to children generation. Specifically, genetic algorithms are often made up the following four components: (i) Mutation: explores the adjacency of promising candidates parent generation by generating slightly different candidates in children generation; (ii) Crossover: search for different combinations of genetic features in the candidates in parent generation; (iii) Evaluation: measure the fitness of candidates in given tasks; (iv) Selection: eliminating the candidates with worst performance.
Here, we design a genetic algorithm automatically optimize the subgraph templates in the proposed GRAPE. It effectively allows us to search the architecture of GRAPE in a data-dependent manner, which significantly reduces the barrier of subgraph template design.
3 The Proposed Method
One prominent feature of most GNN variants is that the node embedding are generated based on the local neighborhood, which significantly improved the scalability and generalization of GNN models. To accommodate the local nature of GNNs, the concept of AE needs to be fundamentally extended and redefined on each node's 's local neighborhood. Besides, the local neighborhoods defined by different subgraph templates may exert different influence on the ego node [58, 2]. Thus, we propose a subgraph cemplate-dpendded
local version of AE, i.e., ego-centered automorphic equivalence (Ego-AE). Specifically. subgraph template is defined as connected graphlet S = (24 R), where 44 and R are the sets of nodes and edges, respectively. To differentiate the unique role of ego node, we set an anchoring node in subgraph template that always maps to the ego node. Given graph (U, R) and node Vt, the Ego-AE. AE on U4 's local neighborhood
G G= (V,E), a subgraph template is defined as follow.
Definition 3.1. We define (s(vt) as the set of subgraphs that match the subgraph template S in local neighborhood. An ego-centered automorphism (+) is an automorphism the matched

---

subgraphs m E MMs(vt) that has fixed index of node v2 i.e, Te(VE) Two nodes va and Us are considered to Ego-centered Automorphic Equivalence (Ego-AE) if there exists an automorphism Te(*) that maps one onto the other, i.e., (V(Va) Ub-
Without loss of generality, various forms of subgraph template S can be adopted capture the structural patterns of different semantics. Figure 1 (b) shows the Ego-AE on 0j 's local neighborhoods with the subgraph templates of triangle and chordal cycle. Specifically, we first identify all the matched subgraphs with the anchoring nodes (white color) in subgraph templates fixed to the ego node v1, and then the nodes covered by the matched instances are partitioned into Ego-AE sets based on the corresponding automorphisms. We can observe that Ego-AE successfully differentiates the roles of 01 's neighboring nodes based on the structural features.
However, GNN's capacity in capturing Ego-AE is largely unknown in the literature. fact, we prove that the standard MPNN has fundamental limitations (see Section 3.3), while other GNN variants focus on different graph properties which largely overlooked Ego-AE.
3.1 The Proposed GRAPE Model
We aim to propose a novel GNN model, i.e., GRaph AutomorPhic Equivalence network (GRAPE), that is provably expressive in capturing Ego-AE. The overall framework is in Figure 2. In the sequel, we describe them in details, and the complete algorithm of GRAPE is in Appendix C.I.
3.1.1 AE-aware Aggregator
Here, we design a novel AE-aware aggregators to learn from the Ego-AR sets in each node's local neighhorhood with given subgraph templates. Specifically,
denote 12 Ego-AE sets with subgraph template S as T: = (e),) ..... Ar, (vi),... ......... A.....,,m (vt)). where (vr) ) is the set of nodes corresponding to the j-th sets of Ego-AE nodes St and my the total number Ego-AE sets. Then, U2 's node embedding h (vz) can be computed as follows:
(v) MLP Σ, B1. E E..
h ---1 (v,))
where Bi,s's 's are learnable weights that model the importance of (v: and MLP(.) is multi-layer perception (MLP) function [21] that generates output embeddings.
Equation (2) is illustrated in Figure (c). Differs from MPNNs, the proposed AE-aware aggregator can explicitly differentiate the neighboring nodes with different structural roles by assigning different weights 31, to them. It allows GRAPE to capture the combination of important Ego-AE AE sets and effectively models the interdenpendency among them. Note that GRAPE does not have an explicit COMBINE function to account for the ego node's 's self feature, since the ego node will always be captured unique Ego-AE set, such as the A1,1 and A2 in Figure (c).
3.1.2 Fusing Embeddings from Different Aggregators
To simultaneously capture different structural feature, we design a squeeze-and-excitatio module to fuse the node embeddings learned from set of subgraph templates, which is inspired by the channel-wiss enhancement technique recently proposed in [22]. Specifically, by leveraging a set of subgraph templates Ω {S1, S2..., ..., Sr}, GRAPE can learn multiple AE-aware aggregators with each subgraph template to capture different structural features respectively. The GRAPE can learn to assign different weights a for hf (vx) and generate the fused embedding for v, as following
h²(ww) (v) = E
*[ (v).
(3)
Here, the learnable weights a is computed as following
~ = 1
Σ N
MEAN(K) (v,)), a ReLU ReLLLRR >>))),
(4)
where * is the global average pooling the node embeddings learned with subgraph template S,, W and W are two learnable matrices with RLxL size, and ReLU is the relu activation function.
5

---

Algorithm Genetic Algorithm for Subgraph Template Optimization
1: Input graph G (V;E); node feature X(v); probability of edge mutation, node mutation,
crossover = Pe: Pei size gene pool B; subgraphs per gene I,; elimination size Z;
2: gene = InitPool( L);
3: for k 1.... 2 do
4: genePool = Mutaategemme Pool, Pe, Pr);
Mutute Subgraph Templates*/ /*Generate Different Combinations
5: genePool = Crossoveergenee Pool, Pe);
6: for gene gone do
7: {T....., TL Match( gene)
M*Mtth on Graph.
8: accuracy .., T2),
/*Evaluate Performance. */
9:
10: end for
11: gene Pool genePool = Select(gene metricPool, 7)
Elliinnate and Reproduce*/
12:
end for
13:
return Best performing gene E genePool.
3.2 Genetic Search of Subgraph Templates
To reduce the barrier of hand-crafted subgraph templates, formulate the automatic subgraph template design problem as an optimization problem that aims to search for the best performing combinations of subgraph templates Ω2 Let the designed GRAPE in Section 3.1 be F with model parameter e, which leverages the Ego-AE sets {Tr.... Tz} identified by Matching on the given graph G. This subsequently leads to the following bi-le optimization [7] problem:
(TI Tz} Match(G, 6 = maxe F( T2),9)
(ajc]) (ITI, (() s.t.
(5)
However, the proposed optimization problem is difficult mainly for two reasons: 1) the search space of subgraph templates is discrete and not differentiable; 2) matching subgraph templates in large graph is computationally expensive.
Our key intuition to address these challenges is that similar subgraph templates often have slightly different pools of matched instances, which likely to result in similar model performance. Therefore, effectively
by gradually exploring the adjacent space of good performing subgraph templates avoid bad candidates. This inspires us to design a genetic optimization framework, which can navigate through the discrete search space via the gradual mutations between generations. Moreover, the similarities between iteratively searched subgraphs can be further leveraged to design efficient subgraph matching algorithm. The details are described follows.
3.2.1 Genetic Subgraph Template Search
We define gene population as a set of B genes, where each gene is a set of L subgraph templates. The gene population is initiated the most basic subgraph templates, i.e., edge. Then, the gene population is optimized through K₂ rounds of genetic operations, which consists of mulale, crossover, evaluate and select. The mutale operation allows templates, iee, the subgraph templates with one randomly added nodes or edges, which are denoted as children subgraphs. Besides, the crossover operation will randomly exchange some subgraph templates between two genes, which allows us to try different combinations of subgraph templates. Moreover, the evaluate and select operations will identify and remove the worst-performing Z genes and reproduce the best-performing genes. Finally, we use the subgraph templates encoded in the best performing gene as the input of F. Thus, these operations allow to gradually explore the adjacent search space of promising genes and automatically optimize the subgraph templates. The genetic algorithm is presented in Algorithm
explore slightly more complex subgraph
3.2.2 Efficient Subgraph Template Matching
We have the following Proposition 3.1 for the matched instances of the mutated children subgruph, which can be leveraged accelerate the Match function in Algorithm 1. The proof straightforward since the children subgraphs are extended from parent subgraphs by randomly adding node or

---

edge. In fact, the adding edge mutation effectively acts as a filtering mechanism on matched instances, and the adding node mutatioo effectively grows the matched instances of parent subgraph. Therefore, instead of computing the matched instances of children subgraph from scratch, the muiate operation facilitates us to save significantly amount of computation by reusing and extending the matched instances of the corresponding parent subgraphs. As result, we propose an incremental subgraph matching algorithm to leverage this proposition to accelerate subgraph matching process, which is illustrated in Appendix C.2 in details.
Proposition 3.1. Given graph G, parent subgraph Sp and a children subgraph Se, we denote Sp and So 's match instances set as Mn and M.. respectively. Then, we have mp C m.i 2mp E &Mp for Vine E .Me- That is the matched instances of children subgraphs me will always contain matched instance of parent subgraphs ma. Thus, me can be efficiently identified by incrementally extending my.
3.3
Theoretical Analysis
Here, we aim to answer two questions: 1) how does the expressiveness of AE-aware aggregator relate to previous works; and 2) is our designed AE-aware aggregator expressive enough to capture Ego-AE feature. Previous researches mainly investigate the expressiveness of GNN through the scope of graph isomorphism test, while it is expressive power on capturing AE feature is largely unknown. Specifically, we have the following proposition about the limitations of standard MPNNs.
Proposition 3.2. There exist graphs that have different Ego-AE sets for given node, but MPNNs in (/) with arbitrary number of layers and hidden units cannot distinguish them.
We provide a constructive proof in Appendix B.I. Therefore, this proposition shows MPNNs have fundamental limitations modeling the structural role of each node's neighbors. On the contrary, we have the following theorem about the expressive power of the proposed AE-aware aggregator. The theoretical proof of this theorem is provided in Appendix B.2. shows our AE-aware aggregator is provably expressive in capturing Ego-AE feature.
Theorem 3.1. For countable feature space X. let Ua and vs be two nodes with different Ego-AE sets. The AE-aware aggregator in (2) can discriminate two nodes with learned distinct embeddings.
Remark 1. Previous works on GNN's 's structural feature expressiveness mainly follow the hierarchy of neighborhood isomorphic, i.e., can the GNNs differentiate two nodes that have different isomorphisms in their local neighborhoods. However, graph automorphism is a special isomorphism that maps graph on itsef [35]. Therefore, Ego-AE is a stricter structural condition than neighborhood tsomorphic. That is two automorphically equivalent nodes are always neighborhood isomporphic, while the converse statement is false even if the local neighhorhoods expand the entire graph [15]. As a result, previous works that aim to differentiate neighborhood isomorphic nodes with various forms of WL tests, e.g., GIN [55] and k-GNN (38], cannot capture Ego-AE feature. Our GRAPE model aims to fill in this gap.
4 Experiments
Datasets.
Three types of real-world datasets are used, i.e., academic citation networks, social networks and e-commerce co-purchase network.
Citation networks [44]: We consider widely used citation networks, i.e. Cora and Citeseer. In these datasets, nodes represent academic papers and (undirected) edges denote the citation links between them. Following the setting in previous work [24], we use each paper's ' bag-of-worde vector as its node feature and the subject its label.
Social networks [47]: We use 5 real-world social networks which are collected from the Facebook friendships within 5 universities, i.e., Hamilton, Lehigh, Rochester, Johns Hopkins (JHU) and Amherst. The nodes represent students and faculties. Besides, we use one-hot encoding of their gender and major as node feature, and set the labels their enrollment years.
E-commerce co co-purchase networks [26]: This dataset was collected by crawling the music items in Amazon website. If an item a is frequently co-purchased with b, the graph contains directed edge from a to b. We use the average ratings of items as node labels, and we set the node features the number of reviews and downloads.
7

---

Compared Methods. We compare our GRAPE with oftte-of-the-art GNN models, including GCN [24). GraphSAGE [19], GIN [55]. GAT [48], Geniepath [31], Mixhop [1]. Meta-GNN [41] and DE-GNN [27]. Specifically, GCN and Graph are two most popular GNN variants, and GIN customized to better capture structural property. Besides, GAT' and Geniepath use the attention mechanism to learn adaptive neighborhood for each node. Moreover, Mixhop, Meta-GNN and DE-GNN learn node embeddings from higher-order structural information. Specifically, Mixhop proposes difference operators on different hops of neighbors; Meta-GNN lever- ages predefined subgraphs to identify higher-order neighborhood; DE-GNN encodes the shortest path distance among nodes. To ensure fair comparison, we follow the optimal architectures as described in previous works, and we use the official implementations released by the authors or integrated in Pytorch platform [39].
more recent baselines,
Following the common design choices in previous works [24, 19, 48), we adopt a 2-layer architecture. The byper-parameter tuning and detailed experiment settings are discussed in Appendix D.I. Based on the prior knowledge in related areas [3, 20), we design five subgraph templates (S,) for each domain of datasets respectively, which are described in Appendix D.2. We use same subgraph templates for Meta-GNN for fair comparison.
4.1 Benchmark Comparison
The classification accuracy of all methods are compared in Table 1. We observe that GRAPE is the best performing model across all datasets. Specifically, the performance gains are most prominent in social datasets. The improvements are smaller yet still significant on citation and E-commerce datasets. One plausible explanation is the structural features play more important roles in social network analysis. Following [49, 55], to investigate the influence of the node feature on the expressiveness of GNN, we also evaluate the models on datasets that use all-ones dummy node features and randomly initialized node features (see Appendix D.3 for details). We observe that GRAPE achieves consistent performance gains independent of node features, which echos the findings in previous studies that stronger topological feature can usually boost GNN's learning performance [55, 59, 49].
Table 1: Classification accuracy on datasets with original node feature (%). The best pertopeeforming
GNNs are in boldface, and the second best ones are underlined.
Social
Citation
Ecomm.
Model
Hamilton
Lehigh
Rochester
JHU
Amherst
Cora
Citeseer
Amazon
GCN
19.4::2.0
2..0+1.2
21.1
20.5 17.0+1.4
8..9 7..8+1.0 1.3
GraphSAGE
20.5+:2.0
17.8+2.2
18.5#1.8
17.1 17.8+1.6 85.6+0.9 1.3
19,6
GIN
23.7=3.1 19.0#2.0
21.2:0.9
21.5#3.5
26.3+3.8
1..5+1.2
72.6+1.5
48.5+2.5
GAT
18.342.1
22.7
20.2+1.6
19,8#1.4
17.742.2
87.1=2.1
74.6+1.7
39,4
Geniepath
19.1
22.9#1.0
21.7#1.1
19.8
17.5
81.2#1.5
69.8
57.9
Meta-GNN
1..9=1.8 24.3+2.3
23.240.5
27.3#2.9
23.542.2
86.8#1.1
74.4#1.1
56.6
Mixhop
0..
23.2+0.22
18.0+0.0
18.3+0.1
17.0+0.1
80.9+0.7
72.9+0.8 0..
DE-GNN
21.7+2.5
24.9#2.1
18.0+0.0
19.811.7
18.942.2
31.940.00
39.112.3 58.1
GRAPE
28.1-2.11
27.313.8 25 34.61:1.3 32.6-2.2 87.1 7..6 58.6
We show the computation cost of GRAPE and exemplar GNNs in terms of wall-clock training time in Figure (a). Note that both Geniepath and GAT leverage attention mechanism, which can only be trained on CPU (the training with GPU causes the out-of-memory error). Meta-GNN is coupled with complex graph sampling process and takes much more time to train. Thus, these methods are not plotted. We observe GRAPE takes comparable time to train on the example dataset the classic GNN variants of Mixhop and GraphSAGE, which demonstrates the efficiency of our model. The theoretical time complexity analysis is provided in Appendix C.3.
Besides, we also analyze the learned squeeze-and-excitatien Ego-AE set. From Figure 3 (b), we observe the weight is significantly skewed to edge template S in first layer, while it distributes more evenly on more complex templates in the second layer. One plausible reason is that the model tend to keep the neighborhood large in the first hop to collect more
weights on each subgraph template and
8

---

1.0
GGN
1.0
First layer
1.0
A.1
0N
Second layer
0.8
Modvo
Normalzzedd
0.6
D2 02-GWh
GRAFE
0.5
0.4
0.4
0.4
0.2
0.2
0.2
0.0
Seconds
5
S
Ss
Sn
S
S
(a) Wall-clock time
(b) Weights on subgraphs
(c) Weights on Ego-AE sets
Figure Illustrating the training time and the attention weights learned by GRAPE on Lehigh dataset.
feature. As result, it assigns higher weights to the simplest template, iee, S1 edge, in the first layer, while it fuses more diverse structural feature in the second layer by assigning more even weights to various subgraph templates. Figure 3 (c) shows the AE-aware aggregator can effectively distinguish the neighboring nodes with different structural roles. For example, in Lehigh dataset, GRAPE assigns lower weights to the Ego-AE of ego node {ui} } and higher weights to the AE of neighbors {u2} } on edge template S,, while the weights distribute more evenly between {ur and {u2, ua) on triangle template Sz. It suggests the connected neighborhood nodes are more important than ego node on edge template S1. while they have similar importance on triangle template Sg.
4.2 Case Study on AE-aware Aggregators
We conduct a case study to better understand how the AE-aware aggregators contribute to GRAPE. Specifically, we first randomly select a node ve in Lehigh dataset that is wrongly classified by all GNN variants except GRAPE, and then analyze its 2-hop neighborhood. A (ra) and the neighboring nodes that match triangle template S3 and 4-clique template S₃ Figure and Table 2. We observe that there are 3,600 nodes in (v.) and they distribute evenly on multiple labels, which not only might confuse MPNNs but also tend to cause over-smoothness problem [28]. the other hand, both templates S3 and S₁ significantly reduce the neighborhood size, and the percentage of neighbors that have same labels as Ve increases from 19.79 19.7% in (V (ranked 3rd) to 45.3%%~46.. in A3.2 (va) and As.2 (v,)) (ranked ) It shows the AE-aware aggregator successfully capture the "social homophily" effect, where the nodes in tightly connected communities, e.g., triangle and 4-clique structure, tend to have similar property [36].
Table Number of nodes and most frequent labels in v, 's 2-hop neighborhood and Ego-AE sets.
# nodes
The percentage of top labels (v, 's label 11)
2-hop neigh. N=(va
3,600
13 (23.2%), 12 (21.8%), 11 (19.7%), 10 (17.3%), 14 (12.9%
Ego-AE set As,2(1e)
46
11 (45.3%). 10 (17.2%), 12 (14.1%), 13 (12.5%). 9 (7.8%)
Ego-AE set A5,2
222
11 (46.0%), 12 (24.9%), 10 (13.8%), 13 (11.0%), 9 (2.8%)
(a) 2-hop neighborhood
(b) Matched with Sa
(c) Matched with S.
Figure 4: Case study of node v. Lehigh dataset. The ego node u. is positioned in the center and the inset of (a) shows 100 samples. Node colors represent the ground-truth label.

---

4.3 Subgraph Template Search
We evaluate the genetic subgraph template search algorithm on the social dataset. Specifically, we initialize GRAPE with three simplest subgraph template, i.e., edges. We compare our algorithm with two baseline methods: Genetic ESU, which replaces the incremental subgraph matching algorithm in our genetic framework with widely adopted baseline method, i.e., ESU [51]; 2) Random + ESU: search randomly initialized subgraph templates with ESU. Besides, we also add a Bayesian Optimization (BO) + ESU baseline, which uses the the classic Bayesian optimization to search for optimal subgraph templates [56]. We use the BO model implemented in Hyperopt framework [4]. The optimization results are shown in Figure 5 and Table 3. Specifically, Table 3 shows the proposed Genetic method (Genetic INC.) outperform all three baselines across all the datasets. Our genetic framework generates 3.0~8.0%% performance gain over the initialized simple edge template within 3000 seconds, which is 0.6~2.8% higher compared with the best performing baseline. Moreover, the optimized performance is comparable with the hand-crafted subgraph templates in Table 1.
Table Classification accuracy (%) and time composition after 3000 seconds genetic optimization.
Hamilton Lehigh Rochester
JHU
Amherst
Edge Template (Init.)
25.8
23.3
22.6
26.0
28.3
Classification Accuracy (%)
Random+ESU
29.2
24.5
24.8
26.0
28.3
BO+ESU
30.1
25.0
24.6
26.2
29.5
Genetic+ESU
31.0
27.0
25.0
27.5
33.0
Genetic+INC.
33.8
27.9
25.6
30.3
34.5
Time Composition
ESU Matching
648.7
889.4
2592.0
1389.2
1357.1
INC. Matching
24.0
55.3
134.3
129.9
124.6
(Seconds)
Model Evaluation
20.9
33.7
45.0
31.5
18.1
Figure 5 shows case study
Clasificatio Acquracy (1K)
0.28
11
14g
11
of efficiency and searched subgraph templates Algo- rithm I. We observe that Al- gorithm can generate simi- lar prediction accuracy com- pared to the hand-craft sub- graph templates in reasonable search time. Moreover, these subgraph templates are data- dependent.
0.27
0.26
12
2
24
14
0.25
Genetic Inc.
U
Genetic ISU
244
2000
5030
Figure 5: Effectiveness of the proposed genetic algorithm on the Lehigh Dataset. Left: search efficiency; right: subgraph templates.
We also evaluate the performance of various hand-craft subgraph templates in Appendix D.4. We can see that the classification accuracy on Lehigh dataset ranges from 22.6% to 26. 16,1%, which show the importance of subgraph templates and the need for automatic subgraph template search.
5 Conclusion
In this paper, we design theoretical framework to examine GNN's expressiveness through the lens of Ego-AE. We prove MPNNs have fundamental limitations in capturing this important structural property. Moreover, we propose a provably expressive GNN model, iee,, GRAPE, which effectively extend GNN's capability in modeling structural roles. We also design genetic subgraph template search algorithm to automatically optimize the model architecture. Experiments on real-world datasets show consistent performance gain of the proposed methods. One potential limitation of model is the scalability to large-scale real-world graphs (see complexity analysis in Appendix C.3). However, since our model is defined localized Ego-AE, sampling technique similar to GraphSage [19] can be designed to ensure the feasibility of computation overhead, which we will leave as a future work. Besides, our paper proposes general GNN framework and it could be customized for specific application domains, e.g., molecular property prediction [50], to achieve additional performance gain.
10

---

Acknowledgments and Disclosure of Funding
This work was supported in part by the National Key Research and Development Program of China under grant 2020AAA0106000 the National Natural Science Foundation of China under U1936217, 61971267, 61972223, 61941117,
The authors declare no competing interest.
References
[1] Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. arXiv preprint 1xXiv:990500007. 2019.
[2] Nesreen Ahmed, Ryan Anthony Rossi, John Lee, Theodore Wilkke, Rong Zhou, Xiangnan Kong, and Hoda Eldardiry. Role-based graph embeddings. IEEE TKDE, 2020.
[3] Austin R Benson, David F Gleich, and Jure Leskovec. Higher-order organization of complex networks. Science, 3536695) 2016.
[4] James Bergstra, Dan Yamins, David Cox, al. Hyperopt: A python library for optimizing the hyperparameters of machine learning algorithms. In Python in Science Conference, volume 13, page 20. Citeseer, 2013.
[5] Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael Bronstein. Improv- ing graph neural network expressivity via subgraph isomorphism counting. arXiv preprint arXiv:2006.09252: 09252, 2020.
[6] Charles J Colbourn and Kellogg S Booth. Linear time automorphism algorithms for trees, interval graphs, and planar graphs. SIAM Journal on Computing. 10(1):203-225, 1981.
[7] Benoît Colson, Patrice Marcotte, and Gilles Savard. An overview of bilevel optimization. Anmals of operations research, 153(1):235-255 2007.
[8] Luigi P Cordella, Pasquale Foggia, Carlo Sansone, and Mario Vento. A (sub) graph isomorphism algorithm for matching large graphs. IEEE TPAMI, 26( 10): 1367-1377 2004.
[9] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. arXiv preprint arXiv:2004.057/18 2020.
[10] Charles Darwin. The origin of species. PF Collier & son New York, 1909.
[11] Nima Dehmamy, Albert-Láászl Barabási, and Rose Yu. Understanding the representation power of graph neural networks in learning graph topology. In NeurlPS, pages 15387-15397, 2019.
[12] Claire Donnat, Marinka Zitnik, David Hallac, and Jure Leskovec. Learning structural node embeddings via diffusion wavelets. In SIGKDD, pages 1320-1329, 2018.
[13] Agoston Eiben, James Smith, et al. Introduction to evolutionary computing, volume 53. Springer, 2003.
[14] Martin G Everett, Role similarity and complexity in social networks, Social Networks, 7(4):353- 359, 1985.
[15] Martin G Everett, John P Boyd, and Stephen P Borgatti. Ego-centered and local roles: A graph theoretic approach. Journal of Mathematical Sociology, 15(3-4):163-17,, 1990.
[16] Noah E Friedkin and Eugene C Johnsen. Social positions in influence networks. Social Networks, 19(3):20--222, 1997.
[17] Vikas K Garg, Stefanie Jegelka, and Tommi Jaakkola. Gemeralization and representational limits of graph neural networks. arXiv preprint arXiv:2002.06157, 2020.
[18] Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In ICML, pages 1263-1272. JMLR. org, 2017.

---

[19] Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. In NIPS, pages 1024-1034, 2017.
[20] Robert A Hanneman and Mark Riddle. Introduction social network methods, 2005,
[21] Kurt Hornik, Maxwell Stinchcombe, Halbert White, al. Multilayer feedforward networks universal approximators. NN, 2(5):359-366, 1989.
[22] Jie Hu, Li Shen, and Gang Sun. Squeeze-and networks. In CVPR, pages 7132-7141, 2018.
[23] Hong Huang, Jie Tang, Sen Wu, Lu Liu, and Xiaoming Fu. Mining triadic closure patterns in social networks. In WWW, pages 499-504, 2014.
[24] Thomas N Kipf and Max Welling. Seni-supervised classification with graph convolutional networks. In ICLR, 2016.
[25] Johannes Klicpera, Janek Groß, and Stephan Günnemann. Directional message passing for molecular graphs. arXiv preprint 0rXiv:2003.03/23; 2020.
[26] Jure Leskovec, Lada A Adamic, and Bernardo A Huberman. The dynamics of viral marketing. ACM TWEB, 1(1):5-es, 2007.
[27] Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. In NewrlPS, volume 33, 2020.
[28] Qimai Li, Zhichao Han, and Xiao-Ming MaioMMing Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI, 2018.
[29] Zhi-Hao Lin, Sheng Yu Huang, and Yu-Chiang Frank Wang. Learning of 3d graph convolution networks for point cloud analysis. IEEE TPAMI, 2021.
[30] Yixin Liu, Shirui Pan, Ming Jin, Chuan Zhou, Feng Xia, and Philip S Yu. Graph self-supervised learning: A survey. arXiv preprint 2rXiv:2103.0011,,200 2021.
[31] Ziqi Liu, Chaochao Chen, Longfei Li, Jun Zhou, Xiaolong Li, Le Song, and Yuan Qi. Geniepath: Graph neural networks with adaptive receptive paths. In AAAI, volume 33, pages 4424-4431, 2019.
[32] Pablo Ribalta Lorenzo, Jakub Nalepa, Michal Kawulok, Luciano Sanchez Ramos, and José Ranilla Pastor. Particle swarm optimization for hyper-parameter selection in deep neural networks. GECCO, pages 481-488, 2017.
[33] Francois Lorrain and Harrison C White. Structural equivalence of individuals social networks. Journal of Mathematical Sociology, 1(1):49-80, 1971.
[34] Joseph J Luczkovich, Stephen P Borgatti, Jeffrey C Johnson, and Martin G Everett. Defining and measuring trophic role similarity in food webs using regular equivalence. Journal of Theoretical Biology, 220(3):303-32)) 2003.
[35] Brendan D McKay and Adolfo Piperno. Practical graph isomorphism, ii Journal of Symbolic Computation, 60:94-112, 2014.
[36] Miller McPherson, Lynn Smith- and James M Cook. Birds of feather: Homophily in social networks. Annual review of sociology, 27(1):4154444 2001.
[37] Mark S Mizruchi. Cohesion, equivalence, and similarity of behavior: A theoretical and empirical assessment. Social Networks, 15(3):275-355 -077 1993.
[38] Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI, volume 33, pages 4602-4609, 2019.
[39] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, herf-pperfommacc deep learning library. In NewrlPS, pages 8024-8035. 2019.
12

---

[40] Leonardo FR Ribeiro, Pedro HP Saverese, and Daniel R Figueiredo. struc2vec: Learning node representations from structural identity. In SIGKDD, pages 385-394, 2017.
[41] Aravind Sankar, Xinyang Zhang, and Kevin Chen-Chuan Chang. Meta-GNN: Metagraph neural network for semi-supervised learning in attributed heterogeneous information networks. In ASONAM, pages 137-144, 2019.
[42] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation ratios of graph neural networks for combinatorial problems. In NeurlPS, pages 4083-4092, 2019. 2019.
[43] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pages 333-341. SIAM, 2021.
[44] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al Magazine, 29(3):93- 93, 2008
[45] Malcolm K Sparrow. A linear algorithm for computing automorphic equivalence classes: the numerical signatures approach. Social Networks, 15(2):151-170 1993.
[46] Jacobo Torán On the hardness of graph isomorphism. SIAM Journal Computing, 33(5):1093-
1 1108, 2004.
[47] Amanda L Traud, Peter J Mucha, and Mason A Porter. Social structure of facebook networks. Physica A: Statistical Mechanics and its Applications, 391(16):4165-44 4180, 2012.
[48] Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. Technical report, arXiv preprint 1tXXv:1110.109000 2017.
[49] Xiao Wang, Meiqi Zhu, Deyu Bo, Peng Cui, Chuan Shi, and Jian Pei. Am-gen: Adaptive multi-channel graph convolutional networks. In SIGKDD, pages 1243-1253, 2020.
[50] Yaqing Wang, Quanming Abuduweili, Abulikemu Yao, and Dejing Dou. Property-aware relation networks for few-shot molecular property prediction. In NewrlPS, 2021.
[51] Sebastian Wernicke and Florian Rasche. Fanmod: a tool for fast network motif detection. Bioinformatics, 22(9):1152-1553 2006.
[52] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Yu Philip. A comprehensive survey on graph neural networks. IEEE TNNLS, 2020.
[53] Lingxi Xie and Alan Yuille. Genetic enn. In Proceedings of the IEEE international conference on computer vision, pages 1379-1388, 2017.
[54] Yaochen Xie, Zhao Xu, Jingtun Zhang, Zhengyang Wang, and Shuiwang Ji. Self-supervised learning of graph neural networks: A unified review. arXiv preprint 1xXiv22102.00557 2021.
[55] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.0082. 2018
[56] Quanming Yao, Mengshuo Wang, Yuqiang Chen, Wenyuan Dai, Yu-Feng Li, Wei-Wei Tu, Qiang Yang, and Yang Yu. Taking human out of learning applications: A survey on automated machine learning. arXiv preprint 18100 2018
[57] Xin Yao. Evolving artificial neural networks. Proceedings of the IEFE, 123)11423-14477, 1999.
[58] Rex Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zimik, and Jure Leskovec. Gnn explainer: A tool for post-hoc explanation of graph neural networks. arXiv preprini (003:0/90000880 2019.
[59] Jiaxuan You, Rex Ying, and Jure Leskovee. Position-aware graph neural networks. In ICML, pages 7134-7143, 2019.
[60] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. In NIPS, pages 3391-3401, 2017.
13


Reviews:
[{"review_id": "oiO2S17vgxs", "reviewer": "Reviewer_nRJR", "summary": "\nThis paper studies the problem of improving the expressive power of GNN models. It computes the automorphism equivalence set for each node and uses the set to enhance the message passing. This method is proven to be more expressive than standard MPNN.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "### Originality \n\nThis paper studies the problem of improving the expressive power of GNN models. It proposes to use automorphism-aware aggregation to achieve it.\n\nUsing a genetic algorithm to search for motif templates is novel. \n\nThe method using automorphism equivalence matching and counting to improve the expressive power of GNNs is previously proposed in [6], while the relation of this work to [6] is not adequately addressed and discussed. [6] also proved by matching and counting subgraph isomorphism, the expressive power of GNNs can be improved. Though the AE-aware aggregator is not the same as the counting based aggregation in [6], the similarity in the core idea should definitely be discussed more.\n\n\n### Quality\n\nThe claims in this paper are well justified. The experiments are well designed and able to show the effectiveness of the method.\n\n### Clarity\n\nThe presentation is clear.\n\n### Significance\n\nThis paper proposes to use automorphic matching to improve the graph neural networks’ expressive power. The motif template searching genetic algorithm can be useful in this direction, while the relation to [6] is not clearly discussed. My major concern is about the novelty here. I may raise my score if the connection to [6] can be clarified.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors addressed the limitations and potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "GV6AL5fsseJ", "reviewer": "Reviewer_H8ZW", "summary": "Overall this work contributes novel ideas from multiple aspects from introducing the new concept of GNNs being automorphic equivalence-aware to further push the expressiveness of these models, including the developed local definition of how to integrate this into the model, to the development of a genetic algorithm-based method for avoiding hand-crafted/hyperparameter tuned subgraph templates that are instead learned/efficiently searched.", "questions": "", "limitations": "", "rating": 7, "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": "Strengths:\n\nS1) See the summary above.\n\nS2) This work not only presents an empirically well performing method, but also theoretically proves the expressiveness to learn distinct representations of nodes having different local automophic equivalence sets which they have defined. \n\nS3) The background/related work of this work is well presented to provide context for the later method developed.\n\nS4) The empirical evaluation is quite thorough. For example, even an investigation is made on the strength of the proposed GA-based subgraph search algorithm against other search algorithms such as randomized and Bayesian optimization-based method where their proposed method consistently outperforms the others across all datasets.\n\nWeaknesses:\n\nW2) The motivation of the structural equivalence in the second paragraph of the introduction is still not very convincing from a high-level when compared with the more traditional message passing GNN framework that also includes more information from those nodes in a clique formation as compared to longer-reaching weak ties. Although this is presented better throughout the paper, at this stage it still seems lacking.\n\nW2) The comment that “previous analytic methods only classify nodes into categorical equivalence sets, which cannot be optimized for various specific applications in an end-to-end manner” seems to be incorrect as such non-categorical (structure) information has been presented in numerous self-supervised learning approaches to help guide graph neural networks. Please see the following surveys [1,2,3].\n\nOther comments:\n\n1) The way this work is searching for subgraph templates is somewhat related to the work in 3D GNNs that are learning appropriate 3D kernels [4] in point cloud and 3D molecule domain, which might be considered as related work. \n\n2) It would be appreciated to have more discussion on some of the findings (although acknowledging that space is already an issue with this work with much content being moved to the supplemental file), such as that in Figure 4(b) where the first layer is extremely biased towards S1, but in the second layer there seems to be hardly any statistical difference between the subgraphs. Also, discussing subgraph templates such as the triangle S3 in the main work, but only defining in the supplemental is not preferred.  \n\n\nReferences:\n\n[1] Xie, Yaochen, et al. \"Self-supervised learning of graph neural networks: A unified review.\" arXiv preprint arXiv:2102.10757 (2021).\n\n[2] Liu, Yixin, et al. \"Graph self-supervised learning: A survey.\" arXiv preprint arXiv:2103.00111 (2021).\n\n[3] Wu, Lirong, et al. \"Self-supervised on Graphs: Contrastive, Generative, or Predictive.\" arXiv preprint arXiv:2105.07342 (2021).\n\n[4] Lin, Zhi-Hao, Sheng Yu Huang, and Yu-Chiang Frank Wang. \"Learning of 3D Graph Convolution Networks for Point Cloud Analysis.\" IEEE Transactions on Pattern Analysis and Machine Intelligence (2021).\n\nI have read through the other reviews and responses, but am not inclined to update my score. Thank you.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is not needed in the body of their work and they have provided the following in their checklist:\n\"\"\"\nDid you discuss any potential negative societal impacts of your work? \nSince our paper propose a general graph neural network model and the datasets we use are public available, no direct potential negative societal impacts is associated with our work.\n\"\"\"", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "3k7QrPhNjIc", "reviewer": "Reviewer_jGmr", "summary": "In this paper, the author proposed a GNN model that leverages the concept of automorphic equivalence. Specifically, they proposed GRAPE that uses learnable AE-aware aggregators to explicitly differentiate the structural equivalences of each node's neighbors with the aids of various subgraph templates. Moreover, the author theoretically prove that GRAPE is expressive in terms of generating distinct representations for nodes with different AE features. Experiment on real-world dataset proves the effectiveness of GRAPE.", "questions": "", "limitations": "", "rating": 6, "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": "Overall, the paper is well written, and the formulation process including theocratic proofs are adequate and solid. However, I have concerns of the practicability of the proposed method. I think it is a borderline paper between 5-6 (weak reject to weak accept).\n\nReasons to accept:\n1. The paper is well written.\n2. The formulation process including theocratic proofs are solid. \n\nReasons to reject:\n1. The proposed algorithm requires subgraph template, which may not be easily available in many real-world applications. In addition, I didn't find the studies for the impact of different subgraph templates to the performance of the proposed algorithm. Does different subgraph templates and different number of templates have a huge impact to the proposed algorithm?\n2. The proposed algorithm seems to increase the complexity and might not be easily applied to real world applications. Although the authors showed the comparison of different algorithm's training time in Figure 4, the authors mentioned that two baselines Geniepath and GAT are trained on CPU, which is not a fair comparison. It is true that GAT used attention mechanism which will cost more GPU memory, but you can modify it to batch training, like in [1] https://arxiv.org/pdf/1806.01973.pdf, rather than training the whole graph at once. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "To me, there is no obvious negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "-w_p8geoVuX", "reviewer": "Reviewer_ULms", "summary": "The paper proposes a new GNN architecture, named GRAPE, which aims to take into account automorphic equivalence relationships in the egonets surrounding a node to improve the discriminative power of the learning architecture.\nThe authors present two theorems to support their architectural design and show numerical experiments on a number of datasets in which the new architecture appears to perform well.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "The paper considers a variation of GNN which account for (local) AE relationships. In my view, there are already many related ideas (though not quite the same) out there, so I would rank the originality of this approach to be not that high.\n\nI found a number of claims made in the paper to be somewhat surprising or lacking precision, e.g., it is stated that there are efficient algorithms to solve the graph isomorphism / automorphism problem. I don't think this is the case. These are clever heuristcs, but as far as I am aware there are no efficient (polynomial time) algorithms for solving the isomorphism problem. \n\nIn a similar vein I found the discussion related to the WL algorithm confusing -- the WL algorithm is precisely used in the context of graph isomorphisms, and previous works (Morris et al, Xu et al) show that standard message passing cannot be more powerful than this algorithm, but can in fact be as powerful as the WL algorithm. However, the WL algorithm can distinguish non-automorphic nodes based on their neighborhoods; so I am not fully sure I get the point of Proposition 3.1 and Theoem 3.2.\nAs another point, the description of the genetic algorithm to be lacking sufficent detail to appreciate what is really done here.\n\nOverall I found the theoretical contribution here to be not that convincing. In my view the proposed architecture is largely of interest because of its empirical performance -- which appears to be good. However, in this context a somewhat more rigorous experimental setup would have made for a much stronger paper and I would urge the authors to improve this section by including more relevant comparisons (like GNNs with random/unique initial node features, or GNNs based on higher-order WL equivalents); likewise the paper would benefit from the inclusion of a larger array of datasets.\n\n============\nUpdate post author reponse/discussion. I have raised my score to 6 following the responses of the authors", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Given the broad literature on limitations of GNN (in terms of WL test, robustness guarantees, etc), I find it surprising that a discussion of the weaknesses of the presented method is not really present.\nThe possible societal impact of using graph neural networks in classification task (e.g., in social networks, as considered here) is also not discussed in any detail.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a new GNN architecture which addresses the automorphic equivalence among nodes. The idea is novel and effective. The results have demonstrated the superiority of the proposed approach. The reviewers liked the idea, while raised concerns such as some theoretical claims, datasets and the selection of subgraph templates. The authors have done a great job in rebuttal and have clarified some claims that caused misunderstanding. In the end, the reviewers reached consensus in accepting this paper. 
Decision: Accept (Poster)