Year: 2021

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.

heading: 1 INTRODUCTION
text: Many real-world datasets and problems can be modelled as sets of objects with different relationships between them, and so graphs are a natural choice for representing these problems. Common examples include modelling interactions between users in a social network, properties of molecules, or modelling connections between entities in a knowledge base.
Graph neural networks (GNNs) have become a popular technique for node and graph-level property 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,
in practical application settings, data is often complex and multi-typed, necessitating the use of heterogeneous 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 a 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-published-at-VENUE relationships may influence AUTHOR-associated-with-VENUE relationships by constructing a linear mapping between their adjacency matrices; see Fig. 1.
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 ∈ Rn×n, for any permutation matrix π ∈ {0,1}n×n, a neural network f ∶ Rn×n → Rn×n must have the property that f(πAπ⊺) = πf(A)π⊺) (equivariance), or when making graph-level predictions with f ∶ Rn×n → R, we require invariance f(πAπ⊺) = 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 maintaining 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.

heading: 2 RELATED WORK

heading: 2.1 HETEROGENEOUS GRAPH NETWORKS
text: The ubiquity of complex multi-typed data in real-world problems has caused heterogeneous graph learning to attract a 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 et al., 2021), and malicious account detection (Liu et al., 2018).
The majority of heterogeneous graph learning techniques rely on meta-paths: sequences of different node and edge types (Sun & Han, 2012; Shi et 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 at the same venue. These meta-paths are usually 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 et al. (2017)) aggregate node attributes using techniques such as random walks over different edge types, in order to obtain structure-preserving 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 Wu et al. (2020) for a 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 al., 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 as Heterogeneous Graph Transformer (HGT, Hu et al., 2020)
and Graph Transformer Network (GTN, Yun et al., 2019) can automatically discover what metapaths are worth using, but even then they are not able to capture as much information as if they were to directly use the full heterogeneous graph. For two recent surveys of heterogeneous graph representation learning techniques, see Yang et al. (2020) 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 (Veličković et al., 2017).

heading: 2.2 EQUIVARIANT AND INVARIANT LEARNING
text: A fundamental property that all graph neural networks share is an equivariance or invariance to node permutations. The general requirement that neural networks must be equivariant and invariant to certain symmetries of their input data has been a very active area of research and has motivated models for a diverse set of data types. Examples include models equivariant to the translational symmetries of images (LeCun et al., 1989), the permutation symmetry of sets (Zaheer et al., 2017), and symmetry to 3D rotations on a sphere (Cohen et al., 2018). As an inductive bias, equivariance of the network to a set of transformations is 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, equivariance 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 of Kondor et al. (2018), which introduces 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 to the more general case of heterogeneous graphs, where we are presented with a set of different edge types. Furthermore, while they characterise the set of equivariant linear bases, their analysis does not give a 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 a general implementation for arbitrary node and edge types. Albooyeh et al. (2019) give a pooling and broadcasting view of operations 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 a symmetry-based approach to GNNs include Maron et al. (2019); de Haan et al. (2020); Azizian & Lelarge (2020).

heading: 3 OUR MODEL

heading: 3.1 NOTATION
text: A heterogeneous graph G = ⟨D,R,V,X⟩ is a four tuple, where D = {1, . . . , d} is the set of node types. For each node type i ∈ D we have a set of ni nodes Vi = {v1, . . . , vni}. We use V = ⋃iVi for the set of all n = ∑i∈D ni nodes. R = {r1, . . . , r`} is the set of edge types, where r = ⟨r, r⟩ for r, r ∈ D is a pair of node types that appear in the edge type r. X is a set of node adjacency matrices X = {X r ∈ Rnr×nr ∣ r ∈ R}, one for each edge type r ∈ R. Such matrices can represent both node and edge attributes using diagonal and off-diagonal elements respectively. For simplicity, we initially assume scalar node and edge attributes, later we show generalization of this to vectors using multiple channels. In the definition above, D,R, and V contain the blueprint of the heterogeneous graph, while X contains the actual data.

heading: 3.2 EQUIVARIANCE FOR HETEROGENEOUS GRAPHS
text: Given the heterogeneous graph G our goal is to identify all equivariant linear operators that map the set of matrices X = {X1, . . . ,X`} to another set of matrices Y = {Y1, . . . ,Y`} of the same form. For this, it is sufficient to identify all such maps from one edge type to another
Lr→r ′ ∶ Rnr×nr → Rnr′×nr′ . The overall equivariant map LR→R can be built from the collection Lr1→r1 ,Lr1→r2 , . . . ,Lr1→r` , . . . ,Lr`→r` .
The equivariance condition on the linear operator Lr→r ′
ensures that any permutation of the input nodes of the same type leads to the same permutation of the nodes in the output for that node type. Let πi ∈ S(ni) be a permutation matrix acting on ni nodes of type i. Equivariance constraint requires
Lr→r ′ (πrX rπ⊺r ) = πr′ Lr→r ′ (X r)π⊺r′ ∀πr, πr, πr′ , πr ∈ S(nr) × S(nr) × S(n′r) × S(n′r) (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 operators 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 equivariance property Eq. (1).
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 desired linear map Lr→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 Lr→r ′
has the following form:
Lr→r ′ (X) = w1(X1nr1n′r) ⊺ +w21n′ r (1⊺nrX1nr)1 ⊺ n′r
(2)
where w1,w2 ∈ R are arbitrary weights and 1n is the identity vector of length n. Here, following Zaheer et al. (2017) we are performing pooling and broadcasting operations using multiplication by identity vectors. The first operation (X1nr1n′r)
⊺ pools over the columns of X (i.e., VENUES), and broadcasts the resulting column vector to create a nr′ × nr′ matrix which is then transposed to 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 over all the PUBLICATION nodes adjacent 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 a deep network).

heading: 3.3 CHARACTERIZING EQUIVARIANT LINEAR MAPS
text: The question is how to identify all equivariant linear operations for a given pair of edge types r, r′? In addition to the pooling, broadcasting, and transpose operation used in the example above, we need one additional operation, namely diag. We overload this operation so that for a square matrix diag ∶ Rn×n → Rn extracts the diagonal, and for a vector input diag ∶ Rn → Rn×n the output is a square matrix with that vector on its diagonal – this means diag(diag(x)) = x and diag(diag(X)) =X⊙I (where ⊙ is the Hadamard product and I is an identity matrix). The idea is to create all possible combinations of the linear operations above that take us from a nr × nr matrix to a nr′ × nr′ matrix. These operations vary based on the equality of some of these dimension – for example if r = r then the operation diag(X) is 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, a vector, or a matrix. Below, we use z,z, and Z to denote these intermediate products, and identify the condition under which we can perform each of these contraction operations:
Operation Condition 1. Identity operation Z⟨r,r⟩ = X⟨r,r⟩ - 2. Pooling over columns zr =X⟨r,r⟩1nr - 3. Pooling over rows zr =X⟨r,r⟩⊺1nr - 4. Pooling over rows and columns z = 1⊺nrX
⟨r,r⟩1nr - 5. Extracting the diagonal zr = diag(X⟨r,r⟩) r = r 6. Pooling the diagonal z = diag(X⟨r,r⟩)⊺1nr r = r
Expansion operations These operations expand the intermediate value to produce the target matrix. 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 ⟨r ′,r′⟩ = Z⟨r,r⟩ r′ = r, r′ = r 2. Transpose Y ⟨r ′,r′⟩ = Z⟨r,r⟩ ⊺ r′ = r, r′ = r 3,4. Broadcasting over columns Y ⟨r ′,r′⟩ = zr1⊺nr′ r = r ′
Y ⟨r ′,r′⟩ = zr1⊺nr′ r = r ′
5,6. Broadcasting over rows Y ⟨r ′,r′⟩ = 1nr′zr ⊺ r = r′
Y ⟨r ′,r′⟩ = 1nr′zr ⊺ r = r′
7. Broadcast over rows and cols Y ⟨r ′,r′⟩ = 1nr′ z1⊺nr′ - 8,9. Placing the diagonal Y ⟨r ′,r′⟩ = diag(zr) r′ = r′ = r
Y ⟨r ′,r′⟩ = diag(zr) r′ = r′ = r
10. Broadcasting over the diagonal Y ⟨r ′,r′⟩ = diag(z1nr′ ) r ′ = r′
Theorem 3.1. Given two edge types r, r′, all the linear maps Lr→r ′ ∶ Rnr×nr → Rnr′×nr′ that satisfy the equivariance condition of Eq. (1) are produced using the contraction and expansion operations above.
Proof. This is a special case of Theorem 6.1.

heading: 3.4 THE FEEDFORWARD LAYER
text: Now that we have enumerated all possibilities for permutation equivariant linear mappings Lr→r ′ , we can combine them to form a linear layer that acts on a set of adjacency matrices:
LR→R(X) = ⎧⎪⎪⎨⎪⎪⎩ ∑ X r∈X ∑ j wj L r→r′ j (X r) ∣ r′ ∈ R ⎫⎪⎪⎬⎪⎪⎭ (3)
Here, j indexes all valid combinations of contraction and expansion operations, and wj ∈ R 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.

heading: 3.4.1 MULTIPLE CHANNELS
text: We can extend the above definitions to include edge feature vectors in a straightforward way, if we instead replace the matrix X r with the tensor Xr ∈ Rnr×nr×f where f is some feature dimension. Now, instead of having scalar weights wj in Eq. (3), we have a collection of weight matrices Wj ∈ Rf
′×f . Each equivariant layer can then specify the number of feature dimensions in their input and output.

heading: 3.4.2 SPARSE IMPLEMENTATION
text: In practice, graphs tend to be very sparse, making it impractical to deal with full adjacency matrices. We instead represent an adjacency matrix with m nonzero entries as a tuple X = ⟨I,V ⟩, where
I ∈ Z2×m are the indices of nonzero values, and V ∈ Rm×f are the nonzero values. Each of the contraction and expansion operations of Section 3.3 for a mapping Lr→r ′ can be implemented using sparse operations with a space complexity ofO(m+m′ +nr +nr +n′r +n′r) and a time complexity of O ((m +m′) log(m +m′) + nr + nr + n′r + n′r).
The log-factor is because the Identity and Transpose expansion operations require that we match the nonzero indices of the input and output adjacency matrices, an operation that involves sorting, giving it a time complexity ofO((m+m′) log(m+m′)). However, this only needs to be computed once for a 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.

heading: 3.4.3 ENCODING AND DECODING LAYERS
text: It is also useful to have matrix-to-vector encoding and vector-to-matrix decoding layers. For example, an encoding layer can take in a set of adjacency matrices and output embeddings for each node of each type, while a decoding layer can take in node embeddings and output values for each possible edge, which may be used for link prediction. Maximally expressive linear encoding (decoding) layers can be constructed by combining all valid contraction (expansion) operations that are of the form Rnr×nr → Rnr′ (Rnr → Rnr′×nr′ ). Their explicit form is left to Appendix C.

heading: 4 TASKS AND ARCHITECTURES
text: Our heterogeneous graph layers, just like regular linear layers in a multilayer perceptron, can be stacked together and alternated with nonlinear activations to form a variety of neural network architectures. We describe here two conventional graph learning tasks, and what architectures we designed for them.

heading: 4.1 NODE CLASSIFICATION
text: For the task of node classification, we are provided with a heterogeneous graph, where a subset of nodes of one target type are labelled. We are tasked with predicting the labels of the other nodes of the target type.
We use an architecture consisting of a 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 we use channel-wise dropout at each layer to prevent overfitting. Following our stack of equivariant heterogeneous graph layers, we add an encoding layer. This encoding layer can either be used to directly predict classes for each node, or they can be used to get an embedding vector for each node which is then fed into a conventional linear classifier to get predictions. The network is trained using a negative log loss over labels.

heading: 4.2 LINK PREDICTION
text: 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 a 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, we 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 heterogeneous 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 are then passed into a decoding layer, producing matrices for each edge type. These matrices are passed through another stack of equivariant heterogeneous graph layers, outputting a confidence score for each potential edge for the target edge type. The
neural network is trained using binary cross-entropy loss over a 1:1 mix of positive samples of real edges of the target edge type, and randomly sampled negative edges.

heading: 5 EVALUATION
text: 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 classification 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 website1. We make comparisons against the heterogeneous graph neural networks Simple-HGN (Lv et al., 2021), RGCN (Schlichtkrull et al., 2018), HAN (Wang et al., 2019), GTN (Yun et al., 2019), RSHN (Zhu et al., 2019), HetGNN (Zhang et al., 2019), MAGNN (Fu et al., 2020), HetSANN (Hong et al., 2020), HGT (Hu et al., 2020), GCN (Kipf & Welling, 2016), and GAT (Veličković et al., 2017). All evaluation scores listed here are taken from Lv et al. (2021). Details on the specific hyperparameters searched over and used for each dataset, are included in Appendix B. A link to our anonymized code is included here: https://github.com/equivariant-hgn/equivariant_hgn.

heading: 5.1 NODE CLASSIFICATION
text: We look at four datasets: DBLP, IMDB, ACM, and Freebase. DBLP, ACM, and Freebase are multi-class classification tasks, and IMDB is a multi-label task. All datasets except for Freebase additionally include node attributes, and 24% of target nodes labels are used for training, 6% for validation, and 70% for testing. Further information is included in Table 1, which is adapted directly from Lv et al. (2021). The task is evaluated using the metrics of Micro-F1 and Macro-F1 scores (F1 scores that have been averaged over all nodes and all labels respectively).
A comparison between our 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.

heading: 5.2 LINK PREDICTION
text: 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 use 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 1.
Edge predictions are evaluated using two metrics: The area under the Receiver Operating Characteristic curve (ROC-AUC), and the Mean Reciprocal Rank (MRR). The ROC-AUC score evaluates
1https://www.biendata.xyz/hgb/
the model’s ability to discriminate between real and fake edges over different sensitivity thresholds. The MRR score evaluates the ability’s model to rank real candidate edges higher than false edges.
A comparison between our results and competing methods is shown in Table 3. Our method performs comparably to other leading methods on the LastFM benchmark, outcompetes all other methods on the Amazon benchmark, and for the PubMed benchmark it 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 so well by learning the interactions between each of these relationships.2
2While 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.

heading: 6 HETEROGENEOUS HYPERGRAPHS
text: In this section, we extend the theory of Section 3 to hypergraphs, where a hyperedge type r = ⟨r(1), . . . , r(m)⟩ relates m node types. What was previously a set of matrices is now a set of tensors X = {Xr ∈ Rnr(1)×...×nr(m) ∣ r ∈ R}. Similar to Eq. (3) 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 Lr→r ′ ∶ Xr ↦ Yr ′ . To characterize all such equivariant linear maps, we consider all combinations of pool and broadcast operations with extraction and placement of hyper-diagonals. To facilitate this, we introduce the following notation for these four operations:
Pooling poolP(X) pools over all the node indices P of its input – e.g., pool{1}X⟨2,1⟩ = 1⊺n2X ⟨2,1⟩
and pool{1,2}X ⟨2,1⟩ = 1⊺n2X ⟨2,1⟩1n1 .
Broadcasting broadcastr′(Zr) broadcasts the input tensor Zr into a tensor corresponding to hyperedge type r′. For example broadcast⟨2,1⟩x⟨2⟩ = x1⊺n1 . This requires the elements of r to appear in r′ – more accurately multi-set(r) ⊆ multi-set(r′), where multi-set returns its input tuple as a multi-set.
Extracting a hyper-diagonal A hyper-diagonal generalizes the notion of diagonal of a matrix. Given a tensor X⟨r(1),...,r(m)⟩, a hyper-diagonal is identified by a partitioning H of the set {1, . . . ,m} where r(i) = r(j) whenever i, j are in the same partition. With this definition of hyperdiagonal, the extraction operation extract-diagH(Xr) reproduces the effect of diag operation for a matrix by simply using H = {{1,2}}. In the extreme case where H = {{1}, . . . ,{m}} identifies the entire input tensor as the hyper-diagonal, this operation becomes the identity operation. Placing a hyper-diagonal place-diagr′,K(Z r) places the tensor Zr over the hyper-diagonal of a ten-
sor Yr ′ identified by the partition K.
We can write any equivariant linear operation: Lr→r ′ ∶ Rnr(1)×...×nr(m) → Rnr′(1)×...×nr′(m′) as a linear combination of different “compatible” choices for these four operations:
Yr ′ = Lr→r ′ (Xr) =∑wH,P,r′′,K place-diagr,K (broadcastr′′ (poolP (extract-diagH (X r)))) (4)
This composition of operations is first extracting a hyper-diagonal using H, pooling over a 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 of the output tensor, identified by K. Next, we show that these are the only operations needed to create an equivariant linear layer for homogeneous hyper-graphs. Theorem 6.1. All equivariant linear maps Lr→r ′ ∶ Rnr(1)×...×nr(m) → Rnr′(1)×...×nr′(m′) 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.

heading: 7 CONCLUSIONS
text: By enumerating all equivariant linear operations that can be applied to the data structure of heterogeneous 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 heterogeneous 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 relatively simple architectures using these equivariant layers, in principle we could create much more sophisticated models in the same way that sophisticated neural networks are based on simple linear layers.
ACKNOWLEDGMENTS
[Removed for anonymity]
REPRODUCIBILITY STATEMENT
The authors have made efforts to ensure reproducibility of our experimental results and clarity in our theoretical contributions. An anonymous repository containing our code is included here: https://github.com/equivariant-hgn/equivariant_hgn. The experimental 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 B. Our theoretical contributions are all based on Theorem 6.1, for which we have provided a proof in Appendix A.

heading: A PROOF OF THEOREM 6.1
text: Proof. It is easy to see that all the four operations used in Eq. (4) are equivariant. In order to show that these operations exhaust all possibilities, we count the number of compatible choices for H,P, r′′,K 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. A related problem for equivariant linear maps for incidence networks appears in Albooyeh et al. (2019), and the following proof is inspired by the combinatorial counting arguments in that paper.
Let {p q } be the number of ways we can partition a set of size p into q non-empty partitions. This is also known as the Stirling partition number. Moreover, we use κ(r, i) for i ∈ D to denote the number of occurrences of node type i in edge type r. Now we claim that the total number of compatible choices for H,P, r′′,K is given by
d
∏ i=1
min{κ(r,i),κ(r′,i)} ∑
m,m′=1 {κ(r, i) m }{κ(r ′, i) m′ } min{m,m′} ∑ l=0 (m l )(m ′ l )l! (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 r′ into m and m′ non-empty partitions respectively. The subsequent Stirling numbers count the number of ways in which we can produce these partitions. In the inner summation, we select l of these m 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 l out of m and m′ partitions (given by the Binomial coefficients), times all the possible pairings over these l partitions for the matching purpose (l!).
Now that we know what the expression above is counting, let us explain the connection to Eq. (4). The intuitive motivation is that we want to enumerate all possible pairings of outputs of extract-diag with inputs of place-diag. In Eq. (6), the number m represents the order of the output tensor of extract-diag with node type i, and m′ 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 Xr and Yr ′ respectively. Once we identify l 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. (4) in an alternate form:
d
∏ i=1
min{κ(r,i),κ(r′,i)} ∑
m,m′=1 {κ(r, i) m }{κ(r ′, i) m′ } min{m,m′} ∑ l=0 (m l )(m ′ l )l! (6)
= d
∏ i=1 min{κ(r,i),κ(r′,i)} ∑ l=0 κ(r,i) ∑ m=l κ(r,i) ∑ m′=l ((m l ){κ(r, i) m })((m ′ l ){κ(r ′, i) m′ }) l! (7)
= d
∏ i=1 Bell(κ(r, i) + κ(r′, i)) (8)
where in Eq. (7), we simply re-arrange the summations in Eq. (6). In arriving at Eq. (8) from Eq. (7) we use a combinatorial argument: recall that the Bell number Bell(k) is the number of different ways we can partition k objects into non-empty partitions. To see why Eq. (7) is counting the same number of partitions of κ(r, i)+κ(r′, i) objects, first partition each of these two sets into any number m,m′ ≥ l partitions. Next, merge l of those partitions from the first and second set in all possible ways to create a partitioning of κ(r, i) + κ(r′, i) into m +m′ − l 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) are 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.

heading: B HYPERPARAMETERS
text: For both the link prediction and the node classification task, we used the Adam Optimizer with weight decay. We also optionally apply a 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 hyperparameters, evaluating their performance against a held-out validation set. The hyperparameters used and the range we tested over are included in Table 4. The sets of hyperparameter values that yielded the best performance on the validation set for each dataset are included in Table 5.

heading: C ENCODING AND DECODING LAYERS
text: We define here an equivariant encoding mapping Pr→r ′ ∶ Rnr×nr → Rn′r and an equivariant decoding mapping Br→r ′ ∶ Rnr → Rnr′×nr′ . The equivariance conditions on these mappings are:
Pr→r ′ (πrX rπ⊺r ) = πr′Pr→r ′ (X r) ∀πr, πr, πr′ ∈ S(r) × S(r) × S(r′) (9)
Br→r ′ (πrzr) = πr′Br→r ′ (zr)π⊺r′ ∀πr, πr′ , πr′ ∈ S(r′) × S(r′) × S(r′) (10)
Theorem C.1. Given an edge type r′ = ⟨r′, r′⟩ and a node type r, all the linear maps Pr ′→r ∶ Rnr×nr → Rnr that satisfy the equivariance condition of Eq. (9) are produced using the valid contractions of the formRnr×nr → Rnr′ in Section 3.3. All linear maps Br→r ′ ∶ Rnr → Rnr×nr that satisfy the equivariance condition of Eq. (10) are produced using the valid expansions of the form Rnr→R nr′ ×nr′ in Section 3.3.
Proof. As with Theorem 3.1, 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:
PR→D(X) = ⎧⎪⎪⎨⎪⎪⎩ ∑ X r∈X ∑ j Pr→dj (X r) ∣ d′ ∈ D ⎫⎪⎪⎬⎪⎪⎭
(11)
BD→R(Z) = ⎧⎪⎪⎨⎪⎪⎩ ∑ zd∈Z ∑ j Bd→rj (zd) ∣ r ∈ R ⎫⎪⎪⎬⎪⎪⎭
(12)
where for P, j indexes each valid contraction operation, and for B, j indexes each valid expansion operation.

Review summaries:
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. 

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.   In 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.

This paper proposes a heterogeneous graph neural network model that is permutation-equivalent. It achieved permutation-equivalence by defining a set of linear mapping operations (contraction and expansion) that are permutation equivariant for of type-specific adjacency matrix. In the experiments, the model has shown positive results compared with non-equivariant heterogeneous graph neural networks in link prediction and node classification.