Equivariant Heterogeneous Graph Networks
Authors: Daniel Levy
Siamak Ravanbakhsh
Venue: ICLR 2022 Submitted (2022)
Keywords: Heterogeneous Graphs
Graph Neural Networks
GNN
Equivariance

Abstract: Many real-world datasets include multiple distinct types of entities and relations, and so they are naturally best represented by heterogeneous graphs. However, the most common forms of neural networks operating on graphs either assume that their input graphs are homogeneous, or they convert heterogeneous graphs into homogeneous ones, losing valuable information in the process. Any neural network that acts on graph data should be equivariant or invariant to permutations of nodes, but this is complicated when there are multiple distinct node and edge types. With this as motivation, we design graph neural networks that are composed of linear layers that are maximally expressive while being equivariant only to permutations of nodes within each type. We demonstrate their effectiveness on heterogeneous graph node classification and link prediction benchmarks.

Under review as a conference paper at ICLR 2022
EQUIVARIANT HETeROGENEOUS GRAPH NETWORKS
Anonymous authors Paper under double-bling review
ABSTRACT
Many real-world datasets include multiple distinct types of entities and relations, and so they are naturally best represented by heterogeneous graphs. However, the most common forms of neural networks operating on graphs either assume that their input graphs are homogeneous, or they convert heterogeneous graphs into homogeneous ones, losing valuable information in the process. Any neural net- work that acts graph data should be equívariant or invariant to permutations nodes, but this is complicated when there are multiple distinct node and edge types. With this as motivation, posed of linear layers that are maximally expressive while being equivariant only permutations of nodes within each type. We demonstrate their effectiveness heterogeneous graph node classification and link prediction benchmarks.
design graph neural networks that are
INTRODUCTION
Many real-world datasets and problems be modelled of objects with different relation- ships between them, and so graphs are a natural choice for representing these problems. Common examples include modelling interactions between users in social network, properties of molecules, or modelling connections between entities in knowledge base.
2
2
Tt1, π²
An example heterogeneous graph, with node types and 4 edge types. repre- sents AUTHORS, @ represents PUBLICATIONS, and m represents VENUES. This heterogeneous graph can be represented as a set of adjacency matrices, one for each edge type. In this paper, we design linear mappings between each adjacency matrix, allowing colleagues-winn With-AUTHOR relationships and relationships.
Figure Left:
learn, for example, how AUTHOR- relationships can in-
fluence wwtpooo-ssooiaaeddiii------aaa
Right: The effect of applying separate permutations and лΟ to the AUTHOR and VENUE nodes. While the graph itself unaffected, with nodes simply relabelled, the adjacency matrices are mod- ified. We characterize linear maps that are equivariant to such permutations as pooling and broad- casting operations.
Graph neural networks (GNNs) have become popular technique for node and graph-level prop- erty predictions. These models have mostly focused on standard homogeneous graphs, wherein all nodes and edges are treated the same, with any differences encoded as feature vectors. However,

---

Under review as a conference paper at ICLR 2022
in practical application settings, data is often complex and multi-typed, necessitating the use of het- erogeneous graphs, where nodes and edges can be of different types, with potentially completely different semantics. Typical ways to apply GNNs to heterogeneous networks involve preprocessing techniques such as encoding node and edge types into feature vectors or collapsing heterogeneous networks into homogeneous ones by replacing paths along multiple different edge types with single edges. These techniques reduce the structural information available for any network to learn from and often require domain knowledge and hand-engineered features.
In this paper, we design a neural network that can operate directly on entire heterogeneous graphs while fully respecting the independence and relationships between different node and edge types. We model a heterogeneous graph as collection of node-node adjacency matrices, one for each edge type, and create mappings from each edge type to every other edge type. For example, in a heterogeneous network that includes PUBLICATIONS, AUTHORS, and VEnUES, and the relationships between these entities, our model can learn how PUBLICATION TUBLICAATIO--uublisee--att publiseed-at--iettnee influence LitHo--associated-wiii VENUE relationships by constructing a linear mapping between their adjacency matrices; see Fig. I
relationships may
A key property of any neural network that operates on graphs is that they must be invariant or equivariant to permutations of nodes. That is to say, if a graph is represented by an adjacency matrix A R"*", for any permutation matrix E {0, 1]"xn, a neural network f =x Raxn must have the property that A(T = x =f(A)= "))=") (equivariance), or when making graph-level predictions with f : IR nxm R. we require invariance [(TA=') f(A).
For heterogeneous graphs, this invariance or equivariance constraint is to permutations within each node type. We identify all linear operations that map one adjacency matrix to another while main- taining permutation equivariance within each separate node type. By combining these operations, we are able to construct maximally expressive linear equivariant layers that can then be stacked together to produce a heterogeneous graph neural network. We create two different architectures, and apply them to two common heterogeneous graph tasks: node classification, and link prediction. Finally, we extend our treatment to the general case of relationships involving hyperedges between more than two node types, providing a general prescription of how to efficiently implement linear layers that act on heterogeneous hypergraphs.
RELATED WORK
2.1 HETEROGENEOL'S GRAPH NETWORKS
The ubiquity of complex multi-typed data in real-world problems has caused heterogeneous graph learning attract lot of attention in applied settings. Heterogeneous graph networks have been applied to such diverse tasks as text classification (Linmei et al.) 2019). disease diagnosis (Wang al. 202T), and malicious account detection (Liu 2018).
The majority of heterogeneous graph learning techniques rely on mela-paths: sequences of different node and edge types (Sun & Han| 2012 Shi al., 2017). For example, in a citation network with AUTHORS, PAPERS, AND VENUES, the "path" AUTHOR PUBLICATION VENUE PUBLICATION AUTHOR represents one meta-path between two AUTHORS that have published the same venue. These meta-paths are usually hand hand-designed, requiring domain knowledge.
Heterogeneous graph learning techniques can be broadly classified into either "shallow" embedding models, or "deep" neural models (Dong et al., 2020 Yang et al. 2020). Shallow methods (such as Dong et al.) (2017): Tang et al. (2015): Fu al. (2017)) aggregate node attributes using techniques such as random walks over different edge types, in order to obtain dructure-preservin embeddings for each node, which are then passed on to other machine learning models for downstream tasks.
These are limited to transductive settings.
Deep methods extend conventional GNNs, but learn parameters or embeddings specific to each node or edge type; see Wwu et al. (2020) for survey of homogeneous GNNs. Examples include R-GCN (Schlichtkrull et al. 2018) which extends GCN by learning edge-specific weight matrices, Heterogeneous Graph Attention Network (HAN, Wang et 2019) and Metapath Aggregated Graph Neural Network (MAGNN; Fu et al.) 2020), which extend graph attention to attend over different meta-paths. Some methods, such Heterogeneous Graph Transformer (HGT, Hu al. 2020
2

---

Under review as a conference paper at ICLR 2022
and Graph Transformer Network (GTN, Yun et al., 2019) can automatically discover what meta- paths are worth using, but even then they are not able to capture as much information as if they were to directly the full heterogeneous graph. For two recent surveys of heterogencous graph representation learning techniques, see Yang et al. (020) and Dong et al. 2020).
Lv et al. 2021 recently called into question whether most heterogeneous graphs neural networks are able to properly exploit the information provided by node and edge types. They show that under fair comparisons, they are often outperformed by conventional graph neural networks that simply ignore node and edge type information, such as GCN (Kipf & Welling 2016) and GAT (Veličković
al. 2017).
2.2 EQUIVARIANT AND INVARIANT LEARNING
A fundamental property that all graph neural networks share is equivariance invariance to node permutations. The general requirement that neural networks must be equivariant and invariant certain symmetries of their input data has been very active area of research and has motivated models for diverse set of data types. Examples include models equivariant to the translational sym- metries of images (LeCun et al. 1989). the permutation symmetry of sets (Zaheer et al.) (017), and symmetry to 3D rotations on sphere (Cohen et al. 2018). As an inductive bias, equivariance of the network to a set of transformations intuitively equivalent to having seen all such transformations of each training data-point. Since the set of such permutation is exponentially large for graph data, cquivariance is essential for any graph neural network.
Several works directly seek the set of operations with this property to use them as building blocks in graph neural networks. Of particular relevance is the work Kondor et al. (2018), which in- troduces permutation equivariant operations that can be applied to tensor representations of graphs, and |Maron et al.] (2018), which characterizes a basis for equivariant linear operations on tensor representations of graphs and hypergraphs. Our work extends this work the more general case of heterogeneous graphs, where we are presented with a set of different edge types. Furthermore, while they characterise the of equivariant linear bases, their analysis does not give practical algorithm since such large matrices that form the linear bases are too large to store in memory for any large graph. While Maron et al. (2018) give an efficient implementation based on pooling and broadcasting for standard homogeneous graphs. they do not provide general implementation for arbitrary node and edge types. Albooyyh al. (019) give pooling and broadcasting view of op- erations for hyper-graphs and incidence structures of other geometric entities. However, all such structures have a single node type that is assumed exchangeable. Some other related works that have symmetry- based approach GNNs include Maron et al. (2019); de Haan et al. (2020); Azizian & Lelarge (0200).
3
OUR MODEL
3.1 NOTATION
is a four tuple, where ID = {1....,d) d} is the set of node types. For each node type i E D we have set of n; nodes V. = {uI,..., }. We use V = U. V; for the set of all
A heterogeneous graph 9 =
Σien T4; nodes. R = (ri,...,,fp Te) is the set of edge types, where (7, for F,r ID) is a pair of node types that appear in the edge type r. X (X* R "=x==
a set of node adjacency matrices represent both
R]. one for each edge type E R. Such matrices node and edge attributes using diagonal and off-diagonal elements respectively. For simplicity, we initially assume scalar node and edge attributes, later show generalization of this to vectors using multiple channels. In the definition above, IB, IR, and V contain the blueprint of the heterogeneous graph, while X contains the actual data.
3.2 EQUIVARIANCE FOR HETEROGENEOUS GRAPHS
Given the heterogeneous graph G our goal is to identify all equivariant linear operators that map the set matrices X (X,.... X,) to another set of matrices Y = (Yi...., Y, of the same form. For this, it is sufficient identify all such maps from edge type to another
3

---

Under review as a conference paper at ICLR 2022
L I. R _ The overall equivariant map L, L can be built from the collection 1.
The equivariance condition on the linear operator L' ensures that any permutation of the input nodes of the same type leads to the same permutation of the nodes the output for that node type. Let n. E S(n,) be permutation matrix acting on n, nodes of type i. Equivariance constraint requires
(TT -T TT L (x') VTT TT. S(nz) x S(nz) S(n)) x S(2,))
(1)
where the permutation matrices correspond to two pairs of node types that appear in the input (r)
and output edge types (r').
As also observed in related contexts (Kondor et al. 2018 Albooyeh et al. 2019) such linear opera- tors often involve pooling and broadcasting over input and output matrices. Our plan is to enumerate all such operations and prove that these are indeed the only linear operations with the desired equiv- ariance property Eq. IT.
Example 1. To build an intuition for these operations, consider two relations between (AUTHOR, VENUE) and (PUBLICATION, AUTHOR). Let r (1,2) denote the former and r' (3. 1) be the latter, noting that these two edge types have a node type in common. The desived linear map r. should be equivariant to independent permutation of AUTHOR nodes, PUBLiCATION nodes and VENUE nodes in our graph. The results that follow this example show that any equivariant L has the following form:
(X) (x)==1(a (X1n, w2 (
(2)
where wi; W2 E R are urbitrary weights and L, is the identity vector of length n. Here, following performing pooling and broadcasting operations using multiplication
Zaheer et al. (017 by identity vectors. The first operation (X1ng1a4) pools over the columns of X (i.c., VENUES), and broadcasts the resulting column vector to create a nhe x n7 matrix which is then transposed match the dimensions of the target edge type. We can think of the pooling operation above as collecting edge attributes from all the VENUES that are adjacent to each AUTHOR. Similarly, the broadcasting operation disperses this pooled information to each AUTHOR. This example shows that an equivariant linear map is able to propagate relevant information across different edge types (within a single layer of deep network).
all the PUBLICATIOn nodes adjacent
3.3 CHARACTERIZING EQUIVARIANT LINEAR MAPS
The question is how to identify all equivariant linear operations for given pair of edge types r'? In addition to the pooling, broadcasting, and transpose operation used the example above, we need one additional operation, namely diag. We overload this operation so that for a square matrix diag: : R > R" extracts the diagonal, and for a vector input diag: IR" - R the output is square matrix with that vector its diagonal this means diag (dia(x))) = and slag(diag (X)) -XII (where @ is the Hadamard product and I is an identity matrix).
The idea is create all possible combinations of the linear operations above that take us from AF ng matrix to n. x n matrix. These operations vary based on the equality of some of these dimension for example if then the operation diag( (X well-defined, and otherwise it is not feasible. To help with this enumeration, we break any such linear operation into parts:
Contraction operations These include pooling over the rows, columns, both rows and columns, extraction of diagonal and pooling over the diagonal, as well as the identity operation. The result could be a scalar, vector, matrix. Below, intermediate products, and identify the condition under which we can perform each of these contraction operations:
2, 2, and Z to denote these
4

---

Under review as a conference paper at ICLR 2022
Operation
Condition
1. Identity operation
Z X
2. Pooling over columns
x² X X
3. Pooling rows
=² X 1n
4. Pooling over rows and columns
1 x
5. Extracting the diagonal
=² diag( X (()
P=I F=r
6. Pooling the diagonal
2 diag( (X (
Expansion operations
These operations expand the intermediate value produce the target ma- trix. The operations include broadcasting over rows, columns, both rows and columns, diagonal placement, diagonal broadcasting, as well as the identity operation and matrix transpose.
1. Identity operation
y(E) 2
-T = F'LLE'' =F 7=7
2. Transpose
3,4. Broadcasting over columns
(( = 11
((22) #11
I=
5,6. Broadcasting over rows
(((2) 1
r=r
F'=L=F (((2)) 1 m
r=r
7. Broadcast over rows and cols
(( 1 1 #1
8,9. Placing the diagonal
(F diag
(rrr)) diag( 2z)
7'=r= =I 7'=r'
10. Broadcasting over the diagonal
Y r') diag( 211mp)
Theorem 3.1. Given two edge r,,,s all the linear maps L T- R + R that satisfy the equivariance condition of Eq. ① are produced using the contraction and expansion operations above.
Proof. This a special case of Theorem 6.1
3.4 THE FEEDFORWARD LAYER
Now that have enumerated all possibilities for permutation equivariant linear mappings L L--r we can combine them to form linear layer that acts on a set of adjacency matrices:
R- (x) = L
(X') (X') X
Here, j indexes all valid combinations of contraction and expansion operations, and wy E IR is a weight for that combination that may be learned. In practice, both the inner and outer sum can be replaced by any permutation invariant aggregation function, such as taking the maximum or taking the mean.
3.4.1 MULTIPLE CHANNELS
We can extend the above definitions to include edge feature vectors in straightforward way, if we instead replace the matrix X with the tensor X' Rurxnzx where some feature dimension. Now, instead of having scalar weights wy in Eq. (3), we have collection of weight matrices W, R/'f, Each equivariant layer can then specify the number of feature dimensions in their input and output.
3.4.2 SPARSE: IMPLEMENTATION
In practice, graphs tend to be very sparse, making it impractical to deal with full adjacency matrices. We instead represent adjacency matrix with nonzero entries tuple X (I, V), where
5

---

Under review as a conference paper at ICLR 2022
I 12*m the indices of nonzero values, and V R are the nonzero values. Each of the contraction and expansion operations of Section 3.3 for mapping I. can be implemented using
sparse operations with a space complexity of O m + m' + ni + ny ng + n()) and a time complexity
of O (mm+ m') log(m m') + ny By + T4.- + n²))
The log-factor because the Identity and Transpose expansion operations require that match the nonzero indices of the input and output adjacency matrices, an operation that involves sorting, giving it time complexity of (((m + m') Iog(m m')). However, this only needs to be computed once for given input and output sparsity mask, rather than for every pass through a layer.
This means that the feedforward layer effectively has a linear complexity in the number of nodes and edges of the graph, making it efficient for large datasets. However, inducing the sparsity on the output of the feedforward layer should be seen as an non-linear operation. Since permutation of node types also permutes the sparsity patterns, this non-linear operation is equivariant.
3.4.3 ENCODING AND DECODING LAYERS
It is also useful to have matrix-to-vere encoding and vector-to-matrix decoding layers. For exam- ple, an encoding layer can take a set adjacency matrices and output embeddings for each node of each type, while decoding layer can take in node embeddings and output values for each possi- ble edge, which may be used for link prediction. Maximally expressive linear encoding (decoding) layers be constructed by combining all valid contraction (expansion) operations that are of the form Ru.xn= R (R R.) Their explicit form left to Appendix
4 TASKS AND ARCHITECTURES
Our heterogeneous graph layers, just like regular linear layers in multilayer perceptron, can be stacked together and alternated with nonlinear activations to form a variety of neural network ar- chitectures. We describe here two conventional graph learning tasks, and what architectures designed for them.
4.1 NODE CLASSIFICATION
For the task of node classification, we are provided with a heterogeneous graph, where a subset of nodes of one target type lahelled. We are tasked with predicting the labels of the other nodes of the target type.
We use an architecture consisting of stack of equivariant heterogeneous graph layers separated by nonlinear activation functions. We apply batch normalization over the nonzero entries for each of the matrices at each layer, and use channel-wise dropout each layer prevent overfitting. Following our stack of equivariant heterogeneous graph layers, we add an encoding layer. This encoding layer can either be used directly predict classes for each node, or they can be used to get an embedding vector for each node which is then fed into conventional linear classifier to get predictions. The network is trained using a negative log loss over labels.
4.2 LINK PREDICTION
For the task of node classification, we are provided with a heterogeneous graph where a subset of edges of one target type have been removed. Given set of candidate edges, half of which are real and half of which have one node with the tail node randomly replaced with another 2-hop neighbour, are tasked with assigning a confidence score to each potential edge.
To accomplish this task, we use an autoencoder architecture. We create a stack of equivariant het- erogeneous graph layers separated by nonlinearities, followed by an encoding layer that produces node embeddings for each node of each node type. This makes up the encoding module of our autoencoder. These node embeddings for each edge type. These matrices are passed through another stack of equivariant heterogeneous graph layers, outputting confidence score for each potential edge for the target edge type. The
then passed into decoding layer, producing matrices

---

Under review as a conference paper at ICLR 2022
neural network is trained using binary cross-entropy loss 1:1 mix of positive samples of real edges of the target edge type, and randomly sampled negative edges.
5 EVALUATION
We evaluate our architectures using the recently created Heterogeneous Graph Benchmark (HGB) (Lv et al.) 2021), which gives a set of standardized datasets and training/test splits in node classi- fication and link prediction. To prevent any possible test set leakage, test set labels are withheld, and evaluation metrics are obtained by submitting predictions to the HGB website " We make com- parisons against the heterogeneous graph neural networks Simple-HGa (Lv et al. 202T). RGCN Schlichtkrull et al., 2018), HAN (Wang et al. 2019). GTN Yun et al. 2019), RSHN (Zhu et al., 2019). HeiGNN (Zhang et al. 2019), MAGNN (Fu et al. 2020). HeISANN (Hong et al.) 2020), HGT (Hu et al.) 2020). GCN (Kipf & Welling 2016), and GAT (Veličković et al.]22017 All eval-
uation scores listed here are taken from Lv et al. (2021). Details on the specific hyperparameters searched over and used for each dataset, inc included in Appendix A link to our anonymized code
included here: https: /githu.......ggggggg com/ http//qqivviairii hhnn heagg//quiaarai aattriantttite ant_hqnn
Table I: Characteristics of each of the datasets tested (Lv et al. 2021).
Node
Nodes
Node Types
Edges
Edge Types
Node
Target
Classes
Classification
Attributes
DBLP
26,128
4
239,566
6
Yes
Author
4
IMDB
21,420
4
86,642
6
Yes
Movie
5
ACM
10,942
4
547.872
8
Yes
Paper
3
FREEBASE
180,098
8
1,057,688
36
No
Book
Link Prediction
Target
AMAZON
10,099
1
148,659
2
Yes
Product-product
LASTEM
20,612
3
141,521
No
user-artist
PUBMED
63,109
4
244.986
10
Yes
discase-disease
5.1 NODE CLASSIFICATION
We look at four datasets: DBLP, IMDB, ACM, and Freebase. DBLP, ACM, and Freebase are multi-class classification tasks, and IMDB a multi-label task. All datasets except for Freebase additionally include node attributes, and 24% of target nodes labels used for training, 6% for validation, and 70% for testing. Further information is included in Table which is adapted directly from Lv et al. (2021). The task is evaluated using the metries of Micro-FT and Macro-F1 scores (F1 scores that have been averaged over all nodes and all labels respectively).
A comparison between results and competing methods is shown in Table 2 It can be seen that our method generally performs comparably with other top methods, and yields higher performance than the state of the art for two particular metrics.
5.2 LINK PREDICTION
We look at three datasets: Amazon, LastFM, and PubMed. Amazon and PubMed additionally include node attributes, and PubMed also includes edge attributes. While our method is easily able to incorporate edge attributes, we ignored them in the case of PubMed in order to make a fair comparison with other methods that do not them. For each dataset, 81% of edges of the target edge type are used for training, 9% are used for validation, and 10% are withheld for the test set. Further information on these datasets is included in Table
Edge predictions are evaluated using two metrics: The area under the Receiver Operating Charac- teristic curve (ROC-AUC), and the Mean Reciprocal Rank (MRR). The ROC-AUC score evaluates
https:/wwww.hhentta.....yyy
7

---

Under review as a conference paper at ICLR 2022
Table 2: Comparison of method the node classification task.
DBLP
IMDB
Method
Macro-F1
Micro-F1
Macro-F1
Micro-F1
Simple-HGN
94.01=0.24
94,46+0.22
62.05+1.36
67.36=11.6
RGCN
91.52+0.50
92.07=0.50
58.85 + 0.26
62.05=+0.15
HAN
91.67+0.49
92.05=0.62
57.74#0.96
64.63+0.58
GTN
93.52+0.55
93.97=0.54
60.4740.98
65.1420.45
RSHN
93.34+0.58
93.81+0.55
59.85+3.21
64.22::103
HeIGNN
91.76+0043
92.33+0.41
48.25+0.67
51.16+0065
MAGNN
93.28+0.51
93.76=0.45
56.4943.20
64.67+1.67
HetSANN
78.55+2.42
80.56+1.50
49.47=1.21
57.68+0.44
HGT
93.01#0.23
93,49=0.25
63.00#1.19
67.20+0.57
GCN
90.84+0.22
91.47+0.34
57.88+1.18
64,8240.64
GAT
93.83+0.27
93.3940.30
58.94+1.35
64.86++0.43
Equivariant HGN (ours)
92.79+0.33
93.29+0.3
63.15+1.06
66.67 +0.92
ACM
FREEBASE
Method
Macro-Fi
Micro-F1
Macro-F1
Micro-F1
Simple-HOO -GN
93,42+0.44
93.35+0.45
47.72+1148
66.29:0.45
RGCN
91.55=0.74
91,41
46.78+0.77
58.33+1157
HAN
90.89+0.43
90.79+0.43
21.31+1.68
54.77+1.40
GTN
91.31=0.70
91.20+0.71
RSHN
90.50#1.51
90.32+1.54
HetGNN
85.91
86.05+0.25
MAGNN
90.88+0.64
90.77+0.65
HetANN
90.02+0.35
89.91+0.37
HGT
91.1240.76
91.00+0.76
29.28+2.52
60.51#1.16
GCN
92.17+0.24
12.12+0.23
27.8443.13
60.23*0.92
GAT
92.26+0.94
92.1940.93
40.7442.58
65,26:10800
Equivariant HGN (ours)
92.26+0.44
92.17 #0.45
48.35+1.57
63.42+0.29
the model's ability to discriminate between real and fake edges over different sensitivity thresholds. The MRR score evaluates the ability's 's model to rank real candidate edges higher than false edges.
A comparison between results and competing methods is shown in Table Our method per- forms comparably to other leading methods on the LastFM benchmark, outcompetes all other meth- ods the Amazon benchmark, and for the PubMed benchmark outcompetes all other methods by a very large margin. The PubMed dataset contains many node and edge types, and we believe that our model is able to perform well by learning the interactions between each of these relation- ships
Table 3: Comparison of our method on the link prediction task.
AMAZON
LASTFM ROC AUC
PUBMED
Method
ROC AUC
MRR
MRR
ROC AUC
MRR
Simple-HGN
93.40=0.62
96.94+0.29
67.59=0.23
90.81=0.32
83.3920.39
92.07=0.20
RGCN
86.34=0.28
93.92+0.16
$7.21=0.09
77.68+0.17
78.29+0.11 18
90.26#0.22 24
GATNE
77.3920.50
92.04:0.36
66.87+0.16
85.93+0.63
63.3920.65
80.0540
HetGNN
77.74=0.24
91.79+0.03
62.09=0.01
83.56+0.14
73.63+0.01
84.00=0.04
MAGNN
$6.81=0.05
72.93+0.59
HGT
88.26=2.06
93. 03.8720.65
54.9920.28
74.9621.46
80.12+0.93
90.85+0.31
GCN
92.84+0.34
97.05+0.12
59.1740.31
79.38+0.65
80.48+0.81
90.99+0.56
GAT
91.65+0.80
96. $8+0.8
58.56+0.66
77 77.04+2.11
78.05
90. 00.02+0.53
Equivariant HGN (ours)
96.75+0.16
97.78+0.15
60.94+0.36
82.3640.71
99,89+0.01
99.86=2.03
"While our results for the PubMed dataset are suspiciously strong, because the test-set is withheld by the curators of the dataset and also used by other methods in this table. we see no obvious reason to doubt the performance of our model. However, we have communicated this to the curators in case there is any issue with data processing and split.
8

---

Under review as a conference paper at ICLR 2022
6 HETEROGENEOUS HYPERGRAPHS
In this section, we extend the theory of Section 3 to hypergraphs, where a hyperedge type (r(1).....,7 7 (mm) relates node types. What was previously set of matrices is now a set of tensors XX' (=(()))..))((())))) |re R).
Similar to Eq. in heterogeneous graphs, the linear map for this setup also decomposes into blocks, and it is sufficient to identify the form of equivariant linear maps L X' Y To characterize all such equivariant linear maps, we consider all combinations of pool and broadcast operations with
extraction and placement of hyper-diagonall To facilitate this, we introduce the following notation for these four operations:
Pooling poole( () pools over all the node indices P of its input e.g., (ool(1) ( 1 X (2.1)
and pool(1.2) X (2.1) = 1 (
Broadcasting broadcast, (Z') broadcasts the input tensor Z" into tensor corresponding to hyper- edge type r'. For example proadcast(g,1,ef =11,,- This requires the elements of to appear in r' - more accurately multi-sct(r) multi-set(r'), where multi-sct returns its input tuple as a multi-set.
Extracting hyperadiagonal A hyper-diagonal generalizes the notion of diagonal of matrix. Given a tensor ((+())...r(m)) a hyper-diagonal is identified by a partitioning HH of the set {1,...,m) m) where r(i) r(j) whenever i. are in the same partition. With this defi- nition of hyperdiagonal, the extraction operation extract-diagx (iag=(X)) reproduces the effect of diag operation for matrix by simply using Ii [1,2)): In the extreme case where - [[1).... {m}} identifies the entire input tensor as the hyper-diagonal, this operation becomes the identity operation.
Placing a hyper-diagonal place-diag, .x (Z) places the tensor Z' over the hyper-diagonal of a ten- sor Y identified by the partition K.
We can write any equivariant linear operation: L R (m(m))))))))))) - R as linear combination of different "compatible" choices for these four operations:
Y -- (X)) = WHE...'. place-diag,, (broadcast," (pooly (extract-diaga (X')))
(4)
This composition of operations is first extracting a hyper-diagonal using H. pooling over subset of indices identified by P. broadcasting some of these dimensions and permuting them according to r", and finally placing the resulting tensor over a hyper-diagonal the output tensor, identified by K. Next, show that these are the only operations needed create equivariant linear layer for homogencous graphs.
Theorem 6.1. All equivariant linear maps I. r R R between two hyperedge types in a hypergraph are of the form Eq. (4)
Proof. The full proof of this theorem is included in Appendix A
7 CONCLUSIONS
By enumerating all equivariant linear operations that can be applied to the data structure of heteroge- neous graphs, we have demonstrated how they may be combined to create effective heterogeneous graph neural networks. We demonstrated their effectiveness in the task of link prediction, their competitiveness for node classification, and give an efficient implementation that can be used for any collection of arbitrary interactions between nodes of different types. Further work is possible to evaluate the effectiveness of equivariant heterogeneous graph networks on the task of heteroge- neous graph classification (a task where the expressive abilities of a network are very important), and learning of heterogeneous hypergraphs (an underexplored area). While we only created two rel- atively simple architectures using these equivariant layers, in principle could create much more sophisticated models in the same way that sophisticated neural networks are based on simple linear layers.

---

Under review as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
[Removed for anonymity]
REPRODUCIBILITY STATEMENT
The authors have made efforts to ensure reproducibility of our experimental results and clar- ity our theoretical contributions. An anonymous repository containing our code is included here:
cttp:ttait..omeeetaaaaaaaaattata heattt/hggngeiivaaiisssss hgn The experimen- tal setup follows from the publicly accessible Heterogeneous Graph Benchmark (Lv et al.) (2021), with architectural details, including hyperparameters searched over and used for each experiment, included in Appendix [] Our theoretical contributions are all based on Theorem 6.1 for which we have provided proof in Appendix A
REFERENCES
Marjan Albooyeh, Daniele Bertolini, and Siamak Ravanbakhsh. Incidence networks for geometric deep learning. arXiv preprint arXiv: 11460, 2019.
Waiss Azizian and Mare Lelarge. Expressive power of invariant and equivariant graph neural net- works. arXiv preprini arXiv:2006. 15646, 2020.
Taco S Cohen, Mario Geiger, Jonas Köhler, and Max Welling, Spherical cnns. arXiv preprint 180i 2018.
Pim de Haan, Taco Cohen, and Max Welling. Natural graph networks. arXiv preprint 2rXiv:2007.08349, 2020.
Yuxiao Dong, Nitesh Chawla, and Ananthram Swami. metapath2vec: Scalable representation
learning for heterogeneous networks. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pp- 135-144, 2017.
Yuxiao Dong, Ziniu Hu, Kuansan Wang. Yizhou Sun, and Jie Tang. Heterogeneous network repre- sentation learning. In IJCAI, volume 20, pp. 4861-4867, 2020.
Tao-yang Fu, Wang-Chien Lee, and Zhen Lei. Hin2vec: Explore meta meta-paths in heterogeneous information networks for representation learning. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, pp. 1797-1806, 2017.
Xinyu Fu, Jiani Zhang, Ziqiao Meng, and Irwin King. Magnn: Metapath aggregated graph neural network for heterogeneous graph embedding. In Proceedings of The Web Conference 2020, pp. 2331-2341, 2020.
Huiting Hong, Hantao Guo, Yucheng Lin, Xiaoqing Yang, Zang Li, and Jieping Ye. An attention- based graph neural network for heterogeneous structural learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 4132-4139, 4139, 2020.
Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. Heterogencous graph transformer. In Proceedings of The Web Conference 2020, pp. 2704-2710. 2020.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. arXiv preprint arXiv: we..1..0909..7. 2016.
Risi Kondor, Hy Truong Son, Horace Pan, Brandon Anderson, and Shubhendu Trivedi. Covariant compositional networks for learning graphs. arXiv preprint arXiv:1801.021444 2018.
Yann LeCun, Bemhard Boser, John S Denker, Donnie Henderson, Richard Howard, Wayne Hub- bard, and Lawrence D Jackel. Backpropagation applied to handwritten zip code recognition. Neural computation, (44):541-551, 1989.
Hu Linmei, Tianchi Yang, Chuan Shi, Houye Ji, and Xiaoli Li. Heterogeneous graph attention networks for supe-supe short text classification. In Proceedings of the 2019 Conference Empirical Methods in Natural Language Processing and the 9th International Joint Conference Natural I Language Processing (FMNNIP-IJCNIPP, pp. 4821-4830 2019.
10

---

Under review as a conference paper at ICLR 2022
Ziqi Liu, Chaochao Chen, Xinxing Yang, Jun Zhou, Xiaolong Li, and Le Song. Heterogeneous graph neural networks for malicious account detection. In Proceedings of the 27th ACM International Conference Information and Knowledge Management, pp. 2077-2085, 2018.
Qingsong Lv, Ming Ding, Qiang Liu, Yuxiang Chen, Wenzheng Feng, Siming He, Chang Zhou, Jianguo Jiang, Yuxiao Dong, and Jie Tang- Are really making much progress? revisiting. benchmarking, and refining heterogeneous graph neural networks. 2021.
Haggai Maron, Heli Ben- Cam-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. arXiv preprint arXiv: (8X20999/220992,,, 2018.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. arXiv preprint
2019.
Michael Schlichtkrull, Thomas N Kipf. Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European semantic web conference, pp. 593-607. Springer, 2018.
Chuan Shi, Yitong Li, Jiawei Zhang, Yizhou Sun, and Philip S. Yu. A survey of heterogencous information network analysis. IEEE Transactions on Knowledge and Data Engineering, 29(1): 17-37, 2017. doi: 10. 1..10//KDEE.20062555566
Yizhou Sun and Jiawei Han. Mining heterogeneous information networks: principles and method- ologies. Synthesis Lectures on Data Mining and Knowledge Discovery, 3(2):1-159, 2012.
Jian Tang, Meng Qu, and Qiaozhu Mei. Pte: Predictive text embedding through large-scale hetero- geneous text networks. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1165-1174, 2015.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: /710. 10903, 2017.
Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip S Yu. Heterogeneous graph attention network. In The World Wide Web Conference, pp. 2022-2032, 2019.
Zifeng Wang, Rui Wen, Xi Chen, Shilei Cao, Shao-Lun Huang, Buyue Qian, and Yefeng Zheng. Online disease diagnosis with inductive heterogeneous graph convolutional networks. In Pro- ceedings of the Web Conference 2021, pp. 3349-3358, 2021.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Yu Philip. A comprehensive survey graph neural networks. IEEE transactions neural networks and learning systems, 32(1):44204) 24, 2020.
Carl Yang, Yuxin Xiao, Yu Zhang, Yizhou Sun, and Jiawei Han. Heterogeneous network repre- sentation learning: A unified framework with survey and benchmark. IEEE Transactions on Knowledge and Data Engineering, 2020.
Seongjun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, and Hyunwoo J Kim. Graph trans- former networks. Advances Neural Information Processing Systems, 32:1 1198--1999,, 2019.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan R Salakhutdinov, and Alexander J Smola. Deep sets. In Advances in Neural Information Processing Systems 30, pp.
Curran Associates, Inc., 2017.
Chuxu Zhang, Dongjin Song, Chao Huang, Ananthram Swami, and Nitesh V Chawla. Heteroge- neous graph neural network. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 793-803, 2019.
Shichao Zhu, Chuan Zhou, Shirui Pan, Xingquan Zhu, and Bin Wang. Relation structure aware heterogeneous graph neural network. In 2019 IEEE International Conference on Data Mining (ICDM), pp. 1539. IEEE, 2019.
11

---

Under review as a conference paper at ICLR 2022
A
PROOF OF THEOREM 6.1
Proof. It is easy to that all the four operations used in Eq. 44 equivariant. In order to show that these operations exhaust all possibilities, we count the number of compatible choices for H. IP, r", IK for a given input/output pair of edge types r and r' Through this counting, we arrive at the same number of operations as what is given by (Maron et al., 2018) 's Theorem 3, where the maximality is also established. related problem for equivariant linear maps for incidence networks appears in Albbooye et al. (2019). and the following proof is inspired by the combinatorial counting arguments in that paper.
Let [P] be the number of ways we can partition a set of size p into q non-empty partitions. This lg
also known as the Stirling partition number. Moreover, we use <(r, i) for i e DD to denote the number of occurrences of node type i in edge type Now claim that the total number of compatible choices for HI, TP, ",,", K. is given by
d (annetrraaat Σ VIL
(K((,)) (x((())) m N m'
min (m,mm)) Σ I=O
( (m)(T)
(5)
Because our operations for each node type are independent, the first product is over all possible node types. In the next summation, we only consider the occurrences of node type i, and partition these in both r and I' into m and m' non-empty partitions respectively. The subsequent Stirling numbers count the number of ways in which we can produce these partitions. select I of these and m' partitions to match them against each other. The number of such possible choices is given by the number of ways we can select I out of m and m' partitions (given by the Binomial coefficients), times all the possible pairings over these partitions for the matching purpose (!!).
the inner summation, we
Now that we know what the expression above is counting. let explain the connection Eq. The intuitive motivation is that we want to enumerate all possible pairings of outputs of extract-diag with inputs of place-diag. In Eq. ( the number m represents the order of the output tensor of extract-diag with node type i, and mn' represents the order of the input tensor to place-diag. The Stirling numbers are counting the number of different hyper-diagonals of the input and output tensors X" and Y' respectively. Once we identify 1 of these partitions on hyper-diagonals to match, the remaining dimensions from the input hyper-diagonal are pooled, while we broadcast over those of the output hyper-diagonal.
Now we write the combinatorial expression of Eq. 44 in an alternate form:
(s(T, (K((,
min(m.m' m')
(1)) ("))))
Σ
N ml
Σ
(6)
2-0
min(N(r.)) oet (() w(r.)) K(ri))
(mm)
(1((1,
((M)
(ro( 1
Σ
Σ
Σ
(7)
m²
m'=l
= [ Bell((((r,) ())()))((()((())) +((, 1-1
(8)
where in Eq. 7 we simply re- arrange the summations in Eq. (6) In arriving at Eq. (8) from Eq. we use combinatorial argument: recall that the Bell number Bell(k) is the number of different
ways we can partition objects into non-empty partitions. To see why Eq. (7) is counting the same number of partitions of s(r, i) x(r', objects, first partition each of these two sets into any number m, m,m' m 2 partitions. Next, merge of those partitions from the first and second set all possible ways to create partitioning of x(r,i) + x(r', i) into m + m - partitions. It is easy to see that this procedure does not produce the same partitioning twice and all different partitions of <((r, i) +(r', i) produced in this way. This last expression is what appears in Maron et al. (2018) in Theorem 3. The argument above shows that the number of different ways we can perform Eq. (4) is equal to this Bell number and therefore all equivariant linear maps of interest have this form.
[
12

---

Under review as a conference paper at ICLR 2022
B HYPERPARAMETERS
For both the link prediction and the node classification task, we used the Adam Optimizer with weight decay. We also optionally apply fully connected layer to the graph node attributes before passing it on to the rest of our network. For each dataset, we ran sweeps on a range of hyperparam- eters, evaluating their performance against held-out validation set. The hyperparameters used and the range we tested over are included in Table 4 The sets hyperparameter values that yielded the best performance on the validation set for each dataset are included in Table 5
Table 4: Hyperparameters tested for each task.
Task
Hyperparameter
Description
Sweep Range
ACT.FN
Nonlinear activation function
ReLU, LeakyReLU, Tanh
DROPOUT
Channel-wise dropout Optimizer learning
0, 0.1, 0.3, 0.5 lc-3, 5c-4, le-4 mean, max
Both
POOL.OP
Pooling operation used instead
inner summation in Eq. (3)
WEIGHT_DECH
Optimizer weight decay
le-3, Ic-4, le-5, 1c-6 16, 32, 64
WIDTH
Number of feature dimensions for each equivariant layer
DEPTH
Number of equivariant layers + op- tional input fully connected layer Input dimension of optional additional fully connected layer after obtaining node embeddings
1,2.3,4.55 5,
Node Classitication
LAYER
0, 16. 32, 64, 128
FEATS_TYPE
If True, ignore node features of non- larget nodes If true, the first layer of the network is be fully connected layer instead of an equivariant layer
True, False
IN.FC_AYERR
True, False
DEPTH
Number of equivariant and fully nected layers in both the encoding and decoding modules
2, 5,
Link Prediction
EMBEDDING DIM IN_FCLLAEER
Dimensions of node embeddings If true. the first layer of the encoding module and the last layer of the decod- ing module set be fully connected layers instead equivariant layers
32, 64, 128 True, False
Table 5: Hyperparameters selected for each dataset for both tasks.
Node Classification
Link Prediction
DBLP
IMDB
ACM
FREEBASE
AMAZON
LASTFM
PuBMEd
ACT.FN
LeL
LeakyReLU
ReLU
Tanh
ReLU
ReLU
ReLU
DEPTH
6
3
5
4
3
DROPOUT
0
0.3
0.3
0.1
0
EMBEDDINGLDIM
64
64
32
FC_LAYER
32
128
64
16
FEAES_TYPE
0
False
False
False
True
True
True
True
LR
0.001
0.0001
0.001
0.0005
0.001
0.001
0.0001
POOL_OP
mean
mean
mean
mean
mean
max
WEIGHT_DECAT
0.001
0.0001
1.00E-05
1.00E-06
0.001
0,0001
0.0001
WIDTH
64
64
64
16
128
128
32
13

---

Under review as a conference paper at ICLR 2022
C ENCODING AND DECODING LAYERS
We define here an equivariant encoding mapping pr- RR - R and an equivariant decoding
mapping B" Rh R"" The equivariance conditions on these mappings are:
pr m,+) Tr. pr (X") VTy, Tr, Te E ((T) x S(r) x S(r')
(9)
B (TZZ') B mp WTy S(T') S(T') S(r')
(10)
Theorem C.1. Given an edge type = (F',L') and node type T, all the linear maps p R R that satisfy the equivariance condition of Eq. 9 are produced using the valid
contractions of the form R=rx"== + -² Section 3.3 All linear maps B²r :R R= that
satisfy the equivariance condition of Eq. 10 produced using the valid expansions of the form
in Section 3.3
Proof. As with Theorem these are also special cases of Theorem 6.1
As with the standard equivariant layers we' ve defined, these equivariant mappings can be combined together to form layers:
DR-D
Σ EP. ('
(11)
X
B (2)
Σ BB (2 |reR R
(12)
z'e2
where for P.j indexes each valid contraction operation, and for B, j indexes each valid expansion operation.
14


Reviews:
[{"review_id": "lmkLKObReil", "reviewer": "Reviewer_cyQD", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The paper is written well and easy to follow.\n\n## Strengths:\n1. The paper proposes a model and details the various operations under which it maintains the equivariance property. \n2. It goes on to show that all linear maps that satisfy the invariance property can be made from the given set of operations. \n3. In addition, it also shows that the neural networks are highly expressive.\n4. Results for link prediction tasks (particularly for PubMed is pretty impressive).\n\n## Weaknesses:\n1. Proposed novelty is marginal in the light of existing prior works.\n2. The results are not as impressive for node classification and in link prediction, it falls behind significantly for Last FM.\n3. There is no explanation given for these phenomenon. I would encourage the authors to add explanation as to why an expressive GNN with equivariance property is not able to leverage itself better for node classification and on the Last FM dataset.\n\nIn light of the above, I am inclined to rate this marginally below acceptance threshold.", "summary_of_the_paper": "Most Graph Neural Networks (GNNs) are often proposed for homogeneous graphs or convert heterogeneous graphs into homogeneous graph and utilize them. This paper proposes a graph neural network which maintains its expressivity while retaining the equivariance property.", "summary_of_the_review": "The paper is clearly written and easy to follow. The theoretically analysis is fairly clean and the model, as a whole, is very cleanly motivated. The results on link prediction tasks, particularly on Pubmed, is impressive. However, novelty is marginal in light of existing prior works and the performance for node classification and link prediction on Last FM is quite underwhelming.\n\nIn light of the above, I am inclined to rate this marginally below acceptance threshold.\n\n----\n\nUpdate post response phase:\nMost reviewers do agree that this is an interesting and important problem and that the authors have done a good job laying out the various operations with equivariant property. Also, most reviewers also have identified that some of the experiment results are very positive and encouraging as well.\n\nHowever, limited novelty is a point that most other reviewers have also raised. I also noticed that they requested for additional baseline comparisons which seems like a fair request. Also, the performance of the model doesn't seem to be stable, sometimes its good and in some cases, it much worse and there doesn't seem to be any reasonable explanation for the same. This is another point, that has quite come up in other reviews as well.\n\nIn light of this, I am inclined to retain my current assessment of marginally below acceptance threshold.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "b8EKd8CA72", "reviewer": "Reviewer_XzQS", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Strength \n\n1 - Propose a new equivariant operation-based model for heterogeneous graph representation learning. \n\n2 - Presentation is clear for me. \n\nWeakness\n\n1 - The novelty of this work is incremental.\n\n2 - Lack discussion of important related works. \n\n3 - Experiment should be improved.   \n\nDetailed Review\nThe novelty of proposed method is incremental for me. This is not the first work to study equivariant graph neural network, discussion of important related work is missing, such as:\n\nE(n) Equivariant graph neural network, ICML 2021\n\nDespite of the difference in equivariant operation design, I do not think this work is novel and the combination of numerous equivariant operations is not a significant contribution. \n\nIn addition, the experiments should be improved. First, since this model involves different types of equivariant operations, it is necessary to study the impacts of different operations (ablation study). Second, according to Table 2/3, the performance of proposed model is worse than the best baseline methods for many cases, raising the concern of model effectiveness. Third, the authors mentioned hypergraphs in Section 6, while not experiments support this extended model. \n\nMinor issues also exist, such as typo. For example, the first sentence of section 4.2 should be: for the task of link prediction... ", "summary_of_the_paper": "This paper proposes an equivariant heterogeneous graph neural network model for heterogeneous graph representation learning. The proposed model introduces numerous operations over adjacency matrix and combines them as final aggregation result. Experiments are conducted to show that the proposed method outperforms some baseline methods. ", "summary_of_the_review": "The novelty of this work is incremental. It lacks existing equivariant graph neural network discussion and comparison. In addition, experiments should be improved. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "D85X-DV_LYl", "reviewer": "Reviewer_Q6T2", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Pros:\n- The performance is impressive for edge prediction. Not that this is not the case for node prediction. Experiments do not show a statistically significant improvement in the node classification task over H-GCN.\n-The authors do a nice job at formalizing the types linear mapping that they allow, and stating the desiderata of GNNs in terms of relative exchangeability of nodes.\nCons:\n- The authors do not test their method fully.  It would have been interesting to test the method a little more through artificial datasets, allowing the authors to control the ground truth --- would they have then been able to state why their method was so much more impressive on PubMed? Does it have to do with the sparsity of the graph? Or the number of different edges as they posit? More insights based on the limitations and ideal use case of this method would be useful. As such, the paper does not address any fundamental questions on the deployability of the method.\n- The results on PubMed do look a little suspicious --- the authors do say so themselves, so this is not necessarily a con, but more of an axis of reflexion: I wonder how this could be explained. Could it be the case that the network is really overfitting? It would have been interesting to list the complexities (in terms of the number of parameters) of the different methods. The splitting of the network in test and training set is completely artificial in the GNN literature ---  it's all on the same network, so as long as we're doing message-passing, this seems really artificial, and not providing what we want to achieve by splitting the data into training and testing. What we need is an estimate of \"out-of-sample\" error or risk. I suppose the method here is not inductive, and cannot be applied to a new node, so we're stuck....Unless we try out methods in the spirit of [1], and we subsample neighborhood or subnetworks within our large graph, fit the Neural Network parameters based on empirical loss functions such as [1]? The authors could also have done ablation studies, and perturbation studies (maybe these could give indications towards overfitting?).\n\n[1] Veitch, Victor, et al. \"Empirical risk minimization and stochastic gradient descent for relational data.\" The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2019.\n", "summary_of_the_paper": "The focus of this paper is in the design of GNNs that are amenable to operate on heterogeneous graphs --- that is, networks where relationships can be of different types. Current methods do not account for these different types of edges, or reduce everything to the same graph --- thereby loosing valuable information. \n\nIn this case, the heterogeneous graph is modelled as a collection of node-node adjacency matrices, one for each edge type. The additional desiderata that they add here is that  that the GNNs that they seek must be invariant or equivariant to permutations of nodes (depending on whether we're doing node level or graph level predictions). For heterogeneous graphs, this invariance or equivariance constraint is to permutations within each node type (eg, within authors, or venues). To build a repository of linear operations that verify these properties, the authors simply enumerate them.", "summary_of_the_review": "Overall, this is an interesting paper, that includes a nice formalization of the problem of defining equivariant operators in GNNs. However, the validation of the proposed method is not convincing enough, as it does not stress-test the method, nor does it provide insights into when the method should be applied with respect to other SOTA approaches.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "-2fv4Ml6x7N", "reviewer": "Reviewer_Nimp", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "\nStrength:\n\n1. Heterogeneous graph neural networks are common in different applications.\n   It is of importance to extend previous permutation-equivariant graph neural\n   networks to the heterogeneous setting.\n\n2. Some of the experimental results are very positive, for example, on the PubMed dataset. The method achieves almost perfect link prediction performance.  \n\nWeakness:\n\n1.The novelty of the proposed method is marginal. There has already been\nprevious works that make graph neural network permutation equivalent. Maron et\nal. (2018) and Albooyeh et al. (2019) have used equivariant pooling and\nbroadcasting operations for building equivariant graph neural network models.\nIn this work, the core idea is very similar, and the contribution is to extend\nthat idea to multiple types of nodes and edges, which is of marginal novelty\nin my opinion.\n\n2. A major concern about the experiments is that many important baselines are\nmissing. For the compared baselines, none of them are designed for\npermutation-equivalent, but there do exist graph neural networks that are\npermutation-equivalent. Without comparing with such baselines, it's hard to\njudge how much this work has advanced this direction.\n\n3. The performance of the proposed model has highly varying performance on\ndifferent tasks and data sets. For example, for link prediction, the model\nachieves almost perfect performance on PubMed, but the gaps are much smaller\non the other two datasets. For node classification, the performance of the\nmodel is sometimes even worse than the vanilla graph neural network. Although\nthe author briefly explained their performance variance on link prediction,\nit's much better to give a more thorough and detailed analysis.\n\n", "summary_of_the_paper": "This paper proposes a heterogeneous graph neural network model that is\npermutation-equivalent. It achieved permutation-equivalence by defining a set\nof linear mapping operations (contraction and expansion) that are permutation\nequivariant for of type-specific adjacency matrix. In the experiments, the\nmodel has shown positive results compared with non-equivariant heterogeneous\ngraph neural networks in link prediction and node classification.\n", "summary_of_the_review": "This paper is studying an interesting problem of permutation-equivariant\nheterogeneous graph neural network. Some of the experimental results are very\npositive. However, the novelty of this paper is marginal, the results are\nhighly varying, and some important baselines are missing.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a design of GNNs that are amenable to operating on heterogeneous graphs. The proposed model introduces numerous operations over the adjacency matrix and combines them as a final aggregation result. Experiments are conducted to show that the proposed method outperforms some baseline methods.

The submission suffers from, an incremental novelty, missing important references, and unconvinced experiments. 

All reviewers tend to reject this submission before and after the rebuttal.
Decision: Reject