Transformers Generalize DeepSets and Can be Extended to Graphs & Hypergraphs
Authors: Jinwoo Kim
Saeyoon Oh
Seunghoon Hong
Venue: NeurIPS 2021 Poster (2021)
Keywords: transformer
graph
hypergraph
self-attention
graph transformer
kernel attention
graph regression
graph prediction
hyperedge prediction
graph neural network

Abstract: We present a generalization of Transformers to any-order permutation invariant data (sets, graphs, and hypergraphs). We begin by observing that Transformers generalize DeepSets, or first-order (set-input) permutation invariant MLPs. Then, based on recently characterized higher-order invariant MLPs, we extend the concept of self-attention to higher orders and propose higher-order Transformers for order-$k$ data ($k=2$ for graphs and $k>2$ for hypergraphs). Unfortunately, higher-order Transformers turn out to have prohibitive complexity $\mathcal{O}(n^{2k})$ to the number of input nodes $n$. To address this problem, we present sparse higher-order Transformers that have quadratic complexity to the number of input hyperedges, and further adopt the kernel attention approach to reduce the complexity to linear. In particular, we show that the sparse second-order Transformers with kernel attention are theoretically more expressive than message passing operations while having an asymptotically identical complexity. Our models achieve significant performance improvement over invariant MLPs and message-passing graph neural networks in large-scale graph regression and set-to-(hyper)graph prediction tasks. Our implementation is available at https://github.com/jw9730/hot.

Transformers Generalize DeepSets and Can be Extended to Graphs and Hypergraphs
Jinwoo Kim, Saeyoon Oh, Seunghoon Hong
School of Computing, KAIST
[jinwoo-kiie saeyoon17, seunghoon. (etpg/oonn.oog))ooo.. hong) ac.
Abstract
We present a generalization of Transformers to any-order permutation invariant data (sets, graphs, and hypergraphs), We begin by observing that Transformers generalize DeepSets, or first-order (set-input) permutation invariant MLPs. Then, based recently characterized higher-order invariant MLPs, we extend the concept self-attention to higher orders and propose higher-order Transformers for order-k data (k: for graphs and k >> 2 for hypergraphs). Unfortunately, higher-order Transformers turn out to have prohibitive complexity (n)2*) ) to the number of input nodes To address this problem, we present sparse higher-order Transformers that have quadratic complexity to the number of input hyperedges, and further adopt the kernel attention approach to reduce the complexity to linear. In particular, we show that the sparse second-ordes Transformers with kernel attention are theoretically more expressive than message passing operations while having asymptotically identical complexity. Our models achieve significant performance improvement over invariant MLPs and message-paseen passing graph neural networks in large-scale graph regression and set-to- (byperrabyy prediction tasks. Our implementation is available https:: //gi titt..u..... com wom/3/w730/hot.
Introduction
Graph universal data modality used model social networks 28 chemical compounds [T]] biological structures [9), and interactions in particle physics [2 29
Recent graph neural networks (GNNs) adopt peessage-passingg scheme 39 32 where the node features are propagated and aggregated recurrently according to the neighborhood structure given in the input graph. Despite the simplicity, the local and recurrent nature makes them unable to discover dependency between any two nodes with distance longer than the message-passing steps [1] The locality of message-passing is also known to be related to the over-smoothing problem that prevents scaling of GNNs 23
An alternative approach is using a more general set of operations that involve global interactions while respecting the permutation symmetry of graphs. Such operations either produce the same output regardless of the node ordering of input graph (permutation invariance), or commute with node an equivariant operation. but restricted to local neighborhoods defined by the input graph. Recently, Maron et. al. (2019) 26 characterized the full space of invariant and equivariant linear layers. turned out that these layers span not only the local neighborhood interactions of message- paggiingganng GNNs, but also global interactions such as one between disconnected nodes, and even edge-to-node, or node-to-edge interactions (Figure) TT. Notably, their formulation naturally extends to layers with different input & output orders (e.g., edge in, node out), and higher-order layers for hypergraphs. In theory, an invariant MI. composed of these layers should be more powerful than message- meesaag--psssng passing GNNs as they can model long-range dependency between nodes (Figure []]. However, they are currently not widely adopted due to relatively low performance and high asymptotic memory complexity.
reordering (permutation equivariance).
cessage-passingg
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Output graph
Query
Key
Input
graph
posssage-passing
Equivariant linear layer
Second-order Transformer layer
Figure I: Illustrated operations of a message-passing GNN, an equivariant linear layer, and a second- order Transformer layer. A single output node is highlighted.
Contributions In this work, we present higher-order Transformers that address the low performance and high complexity of invariant MLPs. First, based on an observation that the renowned Transformer encoder generalizes first-order equivariant linear layers or DeepSets [35], we formulate higher-order Transformer layers that generalize equivariant linear layers by extending self-attention to higher orders (Figure ! Second, while Transformer layers with input and output orders k, has O(n (1) asymptotic complexity, we show that by leveraging the sparsity of input hypergraphs, we can obtain ((m)) complexity given input with m hyperedges. Further adopting kernel attention approaches, we propose variant that reduces the complexity to (m)) and theoretically prove that they are more expressive than message passing networks. Finally, we test higher-order Transformers on range of tasks, and demonstrate that they achieve significant improvements over invariant MLPs and are highly competitive performance and scalability to the state-of-the-arr GNNs.
2 Preliminary
In this section, first describe how (hyper)graphs can be treated as higher-order tensors. We then describe linear layers that operate on higher-order tensors while respecting node permutation symmetry. In particular, we analyze operations within linear layers for second-order tensors (graphs) and show they involve global interactions on top of local aggregation.
Let us define some notations. We denote a set as {a, b), tuple as (a....,b). and denote [n] {I....,n] n.. We denote the space of order-k tensors as IR" where d feature dimension. For an order-k tensor A E R= xd we use multi-index i = (i1, is) E [mx] to denote A; = Aig....f E RRd Let S,, be the set of all permutations of [n]. π E S,, acts i by (i) (T(i1); ..., (ix)) and acts on an order-k tensor A by (i A); = A,))
(Hyper)graphs as tensors Generally, a (hyper)graph data G can be represented tuple (V, A), where a set of n nodes and A IR=* xd encodes features attached to hyperedges. The type of the hypergraph is indicated by the order is of the tensor A. First-order tensor is set of features (e.g.. point cloud, bag-of-we words) where A, is the feature of node i. Second-order tensor encodes edge features (e.g., adjacency) where A is the feature of edge (i1, Generally, order-k tensor encodes hyperedge features (e.g., mesh) where Ai....ii is the feature of hyperedge (i1,..,, ix).
Permutation invariance and equivariance Our problem interest is building a functional rela- tion f(A) T between tensor A and target T. If T is single output vector, often require that is permutation invariant, that it satisfies f'(T A) = f(A); if T is tensor T = T, we often require that f is permutation equivariant, satisfying f(T - A) π f(A), for all S, and A E Raa xd In a typical design setup where a neural network f is built using linear layers and non- non-linear activations, the construction of reduces to finding invariant and equivariant linear layers.
Invariant and equivariant linear layers We summarize invariant linear layers L Ra xd d and equivariant linear layers T RRn xd - R² xd identified in Maron al. (2019) (26 In summary, given an input A E R xd
Note that invariant layer is a special case of La-sz with the order-l output of an equivariant layer LR-i1 can be written with E [m]] E [n]] as:
L LA)I(A); ΣΣ BK + EcJ...
where wp E Rdxdd' by E ddd are weight and bias parameters, B E Ra*+! and CA E TR' are basis tensors (will be defined), and μ and X are equivalence classes of order-(k + and order-/

---

Local interaction (emessage-passing)
Global interactions
(a) edge->node
(b) node->node
(c) edge->node
(d) node->edge
Output edge (21,
Cl 3]
(1,
[.. 1)
(1, 2)
b(4)=15 # total
Input edge i2)
(a.
Input with node idb.
(3,3)
(4.4)
(3.4)
(3.3)
(4.
14 {(i),, (1)))
p {(i,, (a), G1,j22) iimit, jimja, feejs
(in, ia), (1), G23] iewla, Rejh, 12-)1, Jinja iimla, ieel,, iteja, jieja
μ {(in), (ia), (1,
Iiwi,, 12n/1,, Jinja
Figure 2: Example operations in a second-order layer L2-2. We illustrate how input edges (d1, 12) = are aggregated to an output edge (21,12) = j in various equivalence classes (i.j) E f via basis tensor B Note that a loop ((11; i1) or (j), represents node.
multi-indices, respectively. The equivalence classes are defined upon equivalence relation that, for multi-indices i.j E [m]],, i ~ j iff (i1,... i&)) (#(j),..., (jik)) for some node permutation Sn.. Then, a multi-index and all members j in its equivalence class have the same equality pattern: i, i, + jo js. for all a. b E [be]. Consequently, each equivalence class (or A) a distinct set of all order- (A: + I) (or order-I) multi-indices having a specific equality pattern.
cormmutation-ivvaiiann
Notably, we can represent each equivalence class of order-k multi-indices as a unique partition of [k] regardless of n, where the partition specifies the equality pattern. e.g., with k 2. we have two partitions and respective equivalent classes: μl {f11, }2}} the set of all (01, i2) with i ig and H2 = {{i)). }. {ig}} the set of all (i,, i2) with i A i2. Thus, with b(k) the k-th Bell number or number of partitions of [kj. we have +() equivalence classes μ for the weight and b(() equivalence classes
for the bias. We guide the readers interested in derivation to Maron et. al. (2019) 226
With the equivalence classes, basis tensors are then defined as follows:
BJ = { 1
(i.j) E μ otherwise
C
-
jE otherwise
0
In Eq. ①1 each equivalence class μ determines which (hyper)edges participate and how they interact summation E, By Aj. As an example, let us consider 22-22 that maps input edges = (11, i2) to output edges j (j,ūz). An equivalence class = {[i,, 22), {ir, }2}} represents all (i.j) E / that i2, J1 j2, and * f1- Then, due masking by B only input elements Ai, with in i2 participate in the summation and gives output L2-2(A) jA) for ji ja, é + ji. Intuitively, this is analogous to computing node feature by sum-pooling all the other nodes (Fig. (b). Different μ accounts for other interactions as shown in Figure 2 Notably, it contains a richer set of operations beyond local interactions modeled by message-passing (Fig. a))) such as global interaction across all nodes (Fig. b)), and edge-to-node (Fig. ())), node-to-edge interactions (Fig. d))
We finish the section by writing out the first-order equivariant layer L1 As b(2) 2, the layer has two equivalence classes μl = {(11,1) and μ/2 = {(1)) }. Then, we have B = I, and Bu2 1n Ins with 1, E IR" vector of ones. Then, given set of features E Raaxd
L (A) = Au, + (1 - Au/ + 1T
(3)
= A, + 1, 1, Auy + 1T,
(4)
where W1, W2, w/, w/ Raxxd' E Rdd' I1-11 is analogous a combination of elementwise feedforward ((1) and sum-pooling of set elements (112), and is also known as a DeepSet layer [35].
3 Higher-Order Transformers
we introduced higher-order linear equivariant layers Lg-st, and showed that they contain various global and node/edge interactions that are not covered by message- message-passing In this section, we establish a connection between the first-order equivariant layer LI-11 and self-attention of Transformer encoder layers [1 Then, we extend the relationship to higher orders by tensorizing queries and keys, and formulate higher-order Transformer layers. We finish the section by proposing principled parameter reduction for queries and keys, which reduces fair amount of computation.
In Section 2]
3

---

3.1 Transformers generalize DeepSets
As shown in Section first-order linear layer, or DeepSet, has simple structure composed of feedfor- ward and sum-pooling (Eq. 44) Although it is theoretically proven to be a universal approximator of permutation-invariiat functions (35) static sum-pooling could be limited in capturing interactions of set elements, motivating the use of sophisticated pooling. In particular, the self-attention mechanism of Transformer encoder [31 was shown to achieve large performance gain in set modeling via context aware weighted pooling [22 34]. To see this, let us write out the Transformer encoder layers.
A Transformer encoder layer is function Enc Raxd + Raxd consisting of two layers: self- attention layer Attn Ruad - Rand and an elementwise feedforward layer MI.P; R -> Raxd For set of n input vectors X E IRndd Transformer layer computes the following:
n
Attn(X); X4 +
X, w wh.
(5)
A=1j=1
Enc( (X); = Att(X);; + MLP(Attn(X)):
(6)
where a² =o (X is an attention coefficient with an activation o, H is the number of heads, du is head size, dy is hidden dimension, and 1o E Rddxd, xd, wX. wff w E Rdxdd
Now, we show that Transformer layers are generalized first-order linear equivariant functions. By setting o = 1 and assuming that MLP(Y) approximates a linear layer Yw" + +b following the universal approximation theorem [6). the Transformer layer reduces to the following
Enc(X); = X,(In + w² + Σ Exw vo (In + (²)) ) +
(7)
j=1
where vo h== w/ wh. This is equivalent to a DeepSet layer in Eq. with wT Ln wf.. We vo (In + ) and b b". In other words, we can convert DeepSets Transformers by changing the static pooling to attention and replacing elementwise linear mapping with an MLP. We generalize this approach to higher-order input and output, which leads to the formulation of higher-order Transformers for graphs and hypergraphs.
3.2 Higher-order Transformer layers
In Section [. we showed that Transformer layers are generalized first-order equivariant linear layers L1-1. Notably, the generalization procedure was equivalent changing and adding feedforward MLP. In this section, we generalize the approach to LE-.! with arbitrary orders ie and I and formulate higher-order Transformer layer Encą--i.
static pooling to attention
In general, we define higher-order Transformer layer as a function Enck RBn''dd - Ra xd with two layers: a higher-order self- attention layer Attn R=* xd + Rn xd and feedforward layer MLP Rnn xd >> TR" xd, For an input tensor A E IR" xd Transformer layer computes:
ML . (A)) = T (AttL
(8)
Enc, (A) = At + MLP (APt
(9)
where L/n, gn'xd-n'' xdy and - R xdp xd are equivariant linear layers with hid- den dimension dr. Remaining question is how to define and compute higher-order self-attention Att))
To design Autness we remove the bias from Eq. ① and introduce attention coefficients. It is achieved by changing each B E BR to an attention coefficient tensor "., R with multiple heads:
H ΣΣ hilt
Attn i (A),
V O aij AwtY hh
(10)
h=1 P
where hh E RRdux V
W. E Bdxda are learnable parameters, H denotes the number of heads, and d denotes head size. Then similar to first-order case (Section 3.1). we can show the following:
I Note that we omitted normalization after Aum(-) and MI.((-) for simplicity as in
In practice, Transformer employs softmax in attention and deviates from Deepsets due normalization.

---

Theorem 1. Enck= (Eq. 9 is a generalization of Lk-s (Eg. ①
Proof. Let A3 for all h, us and (i.j) E μ.. This renders a ai B from the definition of B (A)); = Σx b for all
Additionally, let and reduces to an invariant bias in Eq. 1 Then, Eq.
j E [m]². That is, MLP ignores input p reduces to the following:
Enck->(()) =
Σ
B i
A
V hi
+ Egsbb..
(1I)
h=1
A
which is equivalent Eq. with Wp >1=1
"K
hhpp
Now, we describe how to compute each attention tensor a E R=* from imput A E R xd (Eq. (T0). we drop head index h for brevity). We obtain each attention tensor from higher-order query and key:
(O K2//Z3
(i.j) E where Q" = (A), = = (A).
a =
(12)
otherwise
where 2j = --E of (Q) K is normalization constant, Note that query and key tensors are computed from the input A using the equivariant linear layers in Eq. I This leads to permutation cquivariance (or invariance) Transformer encoder layer Enc in Eq.
Reducing orders of query and key definition of higher-order self-attention, we observe that there exist a lot of unnecessary computations. Specifically, there exist elements of query Q" and key K" that are unused in computation of attention coefficient afj as it depends only on indices satisfying (i.j) E p.. In fact, turns out that the effective orders query and key are much smaller than and k. as we show below:
Although Eq. (OP and Eq. 12 provide simple and generic
Proposition From Eq. (12p, let u(-) denote the number of unique entries in a multi-index. With "y - uj), U₁ u(i) for some (i,J) E ns can always find suitable linear layers L Lk L L
and index space mappings ft [n]] [r]]0e, ft |m0] +
[n]]* that satisfy the following.
at = o Qaj. KB)/ / vi. E 1
(13)
where Zj = Eiiiier of (Ô k) Q = k (A), K2 = L (A) 1/ SE.
Proof. We leave the proof in Appendix A.I.I
Based on Proposition I linear layers with output orders uy and uı instead of and k. In our experiments, we observe that this optimization is very useful in reducing the number of parameters and memory footprint to a feasible level without affecting the effective model capacity.
compute query and key in Eq. (12 in much compact way using
4 Asymptotically Efficient Higher-Order Transformers
In Section 3 we formulated higher-order Transformer layers Enck-,/ and showed that they generalize linear equivariant layers Lt However, this capability comes with cost; the high asymptotic complexity of the Transformer encoder limits its practical merits. Specifically, we show the following:
Property 1. Given input size n, the asymptotic complexity of a linear layer Lk-1 (Eq. (T) is O(n*+1), and complexity of an encoder layer Enck-1 (Eq. 1 O(r + + n!
Proof. We leave the proof in Appendix A.1.2
Thus, in this section, we further analyze the encoder layer and propose number of optimization and relaxation to reduce the asymptotic complexity with a minimal impact on capability. Notably, combin- ing all our strategies reduces the complexity to ((m) given hypergraph with m hyperedges. Even with such efficiency, we show that the reduced version of higher-order' Transformer theoretically more expressive than all cessage-passing neural networks.
5

---

4.1 Linear layers with reduced complexity
A major computation bottleneck within Transformer encoder layer Ence-1 is the higher-order linear layer, since it is used for key, query, and feedforward layer. By exploiting only a subset of basis, we show that we can implement lightweight version of linear layer with reduced asymptotic complexity. Proposition 2. Given linear layer T-k-st in Eq. (T. we can always find a nonempty subset M of equivalence classes such that computation of the following for all j has (nd)) complexity.
Tx = ΣΣ
B
A + Lgpb.
(14)
NEM
Proof. We leave the proof in Appendix A.1.3
We term the reduced linear layer LE_. in Eq. 14) lightweight linear layer. In practice,
choose M among equivalence classes that do not involve summation over input. For instance, for
L1-1, we use only the basis for elementwise mapping (I..) and drop sum-pooling (1,11)) from
Eq. 4.. This approximation effectively reduces the complexity of linear layers at the cost of losing inter-element dependencies. We employ the lightweight linear layers within the Enca- (Eq. ) to compute query and key embeddings, while the element dependency within Ence-1 is handled by the higher-order self-attention using all equivalence classes as in Eq. (12). This design is coherent to original (first-odeer) Transformers, where the elements are first linearly projected to query/key with elementwise basis (I,) and interaction is handled by attention (implicitly 1, 1, Importantly, this does not hurt Theorem as attention coefficients can still reduce to one and MLP can reduce to bias.
By using lightweight linear layers in Enc =t. we can significantly reduce the computational cost, The complexity of - - and MLP in Eq. 13 and Eq. (9) reduces O(n²), (n²') and O(n'), respectively, and as result Ence-> becomes (n As result, we have higher-order Transformer layers Enc;- that generalize LE- while retaining the complexity (n From here we assume that all linear layers for key, query, and MLP are lightweight.
4.2 Sparse Transformer layers
Even with lightweight linear layers, (n**t)) complexity of Enc,- is still impractical. For example, for graphs, complexity larger than (nn²) is regarded prohibitive while Encg- is O(n²). Fortunately. leveraging the sparsity inherent in real-world graphs can significantly reduce the complexity. As we show, it reduces the complexity of Encx-I to O(m²) for processing hypergraph with m hyperedges.
Let E the set of hyperedges of input hypergraph G. Each hyperedge is generally represented by a multi-index i E [m]]. so we denote E = {i......im.) with m hyperedges. Leveraging sparsity of E is straightforward when the order of the hypergraph is fixed (e.g., LR-+R); can perform computations with only respect to the existing hyperedges i, E E. However, in our framework, order can change by layers (e.g., LL-1), making it difficult to directly transfer the sparsity structure E to different-ordee output. Inspired by network projection (L). we remedy this by constructing E" such that for any j E", there exists E E' containing all unique elements of For example, for L3-22- this corresponds to projection of third-order E to second-order E' by obtaining edges from sides of triangles. Despite simplicity, this simple heuristic works well in general and generalizes to any order.
Then, we integrate the hyperedge sets E, E' into computation of linear layer in Eq. (4) as follows:
Lا (A, = Σpem Eieg Bi + Σx Cbbb
j c EY otherwise
(15)
0
Likewise, integrating E, E' into attention computation in Eq. 10) and Eq.
12 we have:
Attn: -I (A, E'1 =
Eh= En Eier
aij
A
V who
j E' otherwise
(16)
0
o(Q K!a)) (i.j) E.iE
where ag h1
(17)
otherwise
where Q²1a== The Ih, F.), Khin Ih (A, F), 24 = EmjESEE a (Q) hi1 K.
With the computations, we can show the following:
Property 2. When given E with m elements, the equivariant linear layer in Eq. (5p has (m) complexity, and self-attention computation in Eq. (16) has Omm²) complexity. Consequently, the computation done by a Ency-sl composed of the layers has (m)) complexity.
Proof. We leave the proof in Appendix A.I.5

---

4.3 Kernel attention trick
Section 4.2 shows that, by constraining linear layers within Enca-I to have sparse input and output, we can reduce (n complexity to quadratic (mm²) to input size. Yet, even O(m²) can be demanding with large dense input. As the quadratic term comes from self-attention computation, we follow the prior work in kernel attention [8 6 and view attention coefficients as pairwise dot-product scores. As we will show, this allows to further reduce the complexity of Enc;=1 to
On" + n') and even (m) for sparse version, at the cost of relaxing some modeling assumption.
We begin by approximating attention coefficient in Eq. 12 using pairwise dot-product kernel [88
6
af = Φ ( (K())/2
(i. E μ
where Zg =
Σ (Q0))(((K)))))
(18)
otherwise
i((i)))
where Rd Rdk is kernel feature map. The choice of kernel can be flexible, and in our implementation we adopt Performer kernel [6] that has strong theoretical and empirical guarantee.
Substituting Eq.
18 in Eq. (00). have:
Attn: -1 (A)s
= Σ 2
Σ
( ((K)) Arw
up
1
1(JDEP
Σ 4jj (Qf)T
Σ
(K{))
(19)
[(J)
where Zj = (Q
Σ
(K))
(20)
{((J)
Here, the annrr-summaiinns in Eq. (19) and Eq. (0) are over the key index i, which is coupled with
the query index by (i.j) E p. This coupling causes the major computational bottleneck, since
the inner-summations should be computed for every j-th query. We propose an approximation by
decoupling the key and query indices and taking inner-summations over I = U, (i((i.) E p):
Attn:-((A)) Σ3 (QO))
Σ iET
Auu wh where Zj = p())) Σ o(K)). (21)
The approximation allows a query to attend to some additional keys (depending μ)) but it does not hurt the central requirement of attention that each query can assign different attention weights the keys. With the approximation, we can compute the summations Eiez o(K,) and Liez ((K))) only once and reuse them across all query indices to reduce the cost. Specifically, we show:
The encoder Ency-s! with approximation in Eq. (2I) has a complexity of O(" + n!). Exploiting sparsity further reduces the complexity O()), linear to the number of hyperedges m.
Property 3.
Proof. We leave the proof in Appendix A.1.6
4.4 Theoretical analysis and comparison to message-passing
We showed that exploiting sparsity and adopting kernel attention reduces the computational com- plexity of the Transformer encoder to linear to input edges. Considering graphs (k / = 2), this complexity is equivalent to better than O(n + m) complexity of the message passing operation Still, we show that our (approximate) encoder is theoretically more expressive than message passing.
Specifically, we show the following:
Theorem 2. A composition of two sparse Transformer layers Enco-1 with kernel attention can approximate any message passing algorithus (Gilmer et. al. (2017) (10)) to arbitrary precision, while the opposite is not true.
Proof. We leave the proof in Appendix A.1.7 A.I.7
This leads to the following corollary:
Corollary 1. Second-order sparse Transformers with kernel attention are more expressive than any message-passing neural networks within the framework of Gilmer al. (2017) [TO].
In the proof, we note that local information propagation message-passingg GNNs carried out in Enc,-12 by single {{t, }, (iz, ig. 1 Other types of μ would carry out different operations, which provides intuition on the powerfulness of Transformers.
In practice, place node features on the diagonals of the adjacency matrix, leading O(n m))
7

---

Forward
Peak Memory Consumption
Dogaimmenn [GB]
log227) (sec)
HUP,15 15:
bun [9]
Outa (0.
Incar stope
-10
10
14
16
14 16
log2t/ml edges)
log2tral (ar edges)
Figure 3: Comparison all second-order models in terms of forward time, memory consumption, and maximal possible input size. Plots are shown until each model runs into out-of-memory error on a RTX 6000 GPU with 22GB.
5 Experiments
In this section, we demonstrate the capability of higher-order Transformers variety of tasks including synthetic data, large-scale graph regression, and set-to-(hyper)graph prediction. Specifi- cally, we use a synthetic node classification dataset from Gu al. (2020) [1] molecular graph regression dataset from Hu et. al. (2021) 177, two set-to-graph prediction datasets from Servian- sky al. (2020) [29]. and three hyperedge prediction datasets used in Zhang et. al. (2020) (36). Details including the datasets and hyperparameters can be found in Appendix [A.]] We implemented invariant MLP in Maron et. al. (2019) [26] as one of baselines, which we abbreviate as MLP,,
We build our model by gradually adding lightweight linear layers (Sec. 4.1. sparse linear layers (Sec. 4.2 and kernel attention (Sec. 4.3) and denote them by (D), (S), and (Φ) respectively.
Runtime and memory analysis To experimentally verify our claims on linear complexity in Sec. 4.3 we conducted a runtime and memory consumption analysis on all second-order models using random graphs; details can be found in Appendix [A.2.3] The results are shown in Figure Consistent with our theoretical claims, sparse second-order Transformer with kernel attention (Ours (S, Φ)) is the only variant that linearly scales input size terms of both time and memory. Also, the only one that successfully scales to graphs with >> 50k edges, while still very fast in smaller graphs.
Synthetic chains To test the ability of higher-order Transformers in modeling long-range inter- actions in graphs, we used synthetic dataset where the task is node classification in chain graphs. Binary class information is provided in terminal node, model is required to propagate the information across the chain by handling long-range dependency. We used training and test sets with chains of length 20 and 200 respectively. As baselines, we used 3 saassage-passingg networks, a sparse invariant MLP, and ablated versions of sparse second-order Transformers where for global pooling removed (w/o global). Further details be found in Appendix A.2.4
The test performances are in Table We first note that second-order Transformers successfully capture long-range dependency up to 200 nodes apart, while message-passing networks fail. Importantly, when the subset of basis that accounts for global pooling is eliminated, the performance of Transformers drops similar to message- -aassagg networks, showing their importance in modeling long-range interaction. Yet, simply having global basis is not enough, as seen in the failure of MLP,. This indicates fine-grained interaction modeling via attention is essential even
Table 1: Chain node classification results.
Method
Micro- Pi (%)
Macro- Fj (%)
GCN
47.78 4.17
33.58
1.86
GIN-O
53.72 = 4.17
36.22
1.86
GAT
47.78 + 4.17
33.58
1.86
MLP, (S)
53.5 4.16
36.04
1.97
Ours (S) w/ global
53.72 :: 4.17
36.22
1.86
Ours (S, w/o global
50.77 = 5.15
35.22
2.17
Ours
10010
100 1
Ours (S,
100
100 +
in this simple task.
Large-scale graph regression To further evaluate higher-order Transformers in large-scale setting, we used the PCQM4M-LSC dataset from Open Graph Benchmark [17). which is the largest graph- level regression dataset composed of 3.8M molecular graphs. As test data is unavailable, we report the Mean Absolute Error (MAE) on validation dataset. In addition to the baselines from the benchmark, we also report the performances of second-orde invariant MLP and vanilla (first-oreer) Transforme for comparison. Further details can be found in Appendix A.2.5
As vanilla Transformer operates node features only, we used Laplacian graph embeddings 2 g as positional embeddings that the model can consider edge structure information.
8

---

The results are in Table 2 Second-order Transformer out- performs the message- passiing GNNs (GCN, GIN) by large margin, including the ones with virtual node that can model long-range interactions (GCN-VN, GIN-VN). It suggests that higher-order attention is potentially better in handling long- range interactions on graphs than the current practice of aug- menting GNNs with a virtual node. Furthermore, second-order Transformer outperforms invariant MLP, indicating that re- placing sum-pooling with attention is important for scale-up. Finally, second-orde order Transformer significantly outperforms vanilla Transformer with Laplacian graph embeddings. This is presumably because node embeddings are insufficient to utilize features associated with edges, while second-order Transform- ers can naturally use all edge information. We also note that invariant MLP and vanilla Transformer have worse complexity than the second-order Transformer (O(m²) ) and O(n²), respec-
Table 2: PCQM4M-LSC large-
scale graph regression results. ii-- dicates results are obtained with a shorter schedule (10% of the full iterations).
Model
Validate MAE
MIP-FINGERPRINT GCN ((7)
0.2044
0.1684
GIN (12)
0.1536
VC
0.1510
GIN-VN
0.1396
Transformer Laplaciin PE+
0.2162
MLP, (S)*
0.1464
Ours ()) SMALL"
0.1376
Ours (S. er
0.1294
Ours (S,
0.1263
tively), while the second-order Transformer has (m) complexity identical to GCN.
Set-to-graph prediction An important advantage of our framework distinguished from most ex- isting GNNs is that, by design, it can be applied to any learning scenario with different input and output orders (mixed-order). To demonstrate this, tested higher-order Transformers in set-to- to-grahh prediction tasks where the goal is to predict edge structure of a graph given a set of node features. We used two datasets following the prior work [29]. The first dataset Jets originates from particle physies experiments, where collision of high-energy particles gives a set of observed particles. The task is to partition the feature of observed particles according to their origin. By viewing each subset of parti- cles as a fully-connected graph, the problem is cast as a set-to-grapp -gagph prediction. For the second dataset Delaunay, the task is to predict Delaunay triangulation [7] given set of points in 2D space. Two datasets are used for this task, one containing 50 points and the other containing varying number of points E {20, ..., 803. For the baselines, we take the scores reported in Serviansky et. al. (2020) (29), which includes GNNs and invariant MLPs (S2G, S2G+) with -i and L1 Our model is made by substituting the linear layers with Enc and Enci-s2 (mixed-order) respectively. Further details including the datasets, metrics, and baselines can be found in Appendix A.2.6
The results are outlined in Table 3 Mixed-order Transformers, both softmax and kernel attention, have favorable scores over all baselines. Especially, they outperform all baselines by large margin in Delaunay: note that GNNs fall into trivial solution with high recall but very low precision. We particularly note that the Transformers' performance in Delaunay (20-80) is comparable to Delaunay (50), with 0.3-0.7% drop in Fl score, Compared with S2G that exhibits ~ 12% drop, this indicates attention mechanism within Enc helpful in modeling varying number of nodes
Table 3: Set-to-graph results. Lower-right panel shows Delaunay (20-80) sample from ours and S2G.
Method
F1
R1
ARI
Method
Acc
Pree
Roc
F1
AVR
0.565
0.612
0,318
SIAM
0.939
0.766
0.653
0.704
MLP
0.533
0.643
0.315
SIAM-3
0.911
0.608
0.538
0.570
SIAM
0.606
0.675
0.411
GNNO
0.826
0.384
0.966
0,549
Jets
(B)
SIAM-3
GNN
0.597
0.586
0.673
0.661
0.396
0.381
Delaunay (50)
GNN5
GNNIO
0.809
0.759
0,363
0.311
0.978
0.985
0.471
0,530
S2G
0.546
0.736
0.491
S2G
0.984
0.927
0.926
0.926
S2G+
0.747
0.508
S2G+
0.983
0.925
0.926
Ours (D)
0.667
0.746
0,520
Ours (D)
0.994
0,981
0.967
0.974
Ours
0.670
0.751
0.526
0.991
0.967
0.952
0.959
AVR
0.695
0.650
0.326
SIAM
0.919
0.667
0.764
0.687
MLP
0.686
0.658
0,319
SIAM-3
0.895
0.578
0.622
0.587
SIAM
0.729
0.695
0.406
GNNO
0.810
0,387
0.946
0.536
Jets (C)
STAM-3
0.719
0.710
0.421
Delaunay
GNNS
0.777
0.352
0.975
0.506
GNN
0.720
0.689
0.390
(20-80)
GNNI0
0.746
0,322
0.970
0.474
S2G
0.457
$2G
0.947
0.934
0.799
S2G+
0.751
0.733
0.467
S2G+
0.947
0.735
0.934
0.798
Ours
0.469
(D)
0.993
0.960
Ours (D. d)
0.757
0.735
0.473
Ours (D. d)
0.989
0.948
0.956
0.952
AVR
0.970
0.965
0.922
MLP
0.960
0.957
0.894
STAM
0.973
0.970
0.925
Jets (L)
GNN
SIAM-3
0.895
0.972
0.970
0.876
0.929
0.729
S2G
0.972
0.970
0.931
S2G+
0.971
0.969
0.929
Ours (D)
0.974
0.972
0.935
(Dvs)
Ours (D.
0.974
0.972
0.935

---

Table 4: k-uniform hyperedge prediction results. For SAGNN, we reproduced the scores using the open-sourced code. For additional baselines including node2vec, we take the scores reported in Zhang et. al. (2020) [36]
GPS
MovicLens
Drig
AUC
AUPR
AUC
AUPR
AUC
AUPR
node2vec-mean ((66)
0.563
0.191
0.562
0.197
0.670
0.246
node2vec-min ([36)
0.570
0.185
0.539
0.186
0.684
0.258
DHNE (36))
0.910
0.668
0.877
0,668
0.925
0.859
AGNNN-
0.947
0.788
0,922
0.792
0.963
0.897
Hyper-S AGNN-W
0.907
0.632
0.909
0.683
0.956
0.890
S2G+ (S)
0.943
0.726
0,918
0.737
0.963
0.898
Ours (S, ()
0.952
0.804
0.923
0.771
0.964
0.901
k-uniform hyperedge prediction One major advantage of our framework is that it naturally extends to higher-order data (hypergraphs). To demonstrate this, consider higher-order extension of set-to-graph prediction task, where the goal is predicting k-uniform hyperedges (c.g., user-location- activity) from node features. For evaluation, following the prior work [36]. The first dataset GPS derives from a GPS network [88. and contains duser-location-actiityy hyperedges. The second dataset MovieLens is social network dataset of tagging activities [33, containing (user-movie-tage hyperedges. The third dataset Drug comes from medicine network from FAERS containing (user-drug-reacttn
used three datasets for transductive 3-edge prediction
hyperedges. As baselines, consider higher-order invariant MLP (S2G+) and the state-of-the-art, self-attention based Hyper- SAGNN [36). We implemented higher-order Transformer and S2G+ by substituting Ene and L1-1 in set-to-graph architectures to Enci-s3 and 11-3, respectively. Further details including the datasets, metries, and baselines can be found in Appendix A.2.2 and Appendix A.2.7 The results are in Table 4 Higher-order Transformer outperforms S2G+ in all datasets, and Hyper- SAGNN in all but one metric in MovieLens. The results suggest that higher-order self-attention effective in learning higher-order representation beyond second-order graphs. The results are encouraging especially because did not introduce any form of task-specific heuristics into the model, while some of the baselines such as Hyper-SAGNN depend on many inductive biases (static/dynamic branches, Hadamard power, etc.).
6 Discussion
In this paper, we proposed a generalization of Transformers to higher-orders, and applied a number of design strategies that reduce their complexity to a feasible level. Higher-order Transformers are attractive, both in theory and application. In theoretical aspect, it inherits the theoretical completeness and expressive power of invariant MLPs. In application aspect, it is potentially more powerful than message- saasagggp neural networks due to global interaction modeling, and can be extended to a variety of useful mixed-order tasks involving sets, graphs, and hypergraphs.
At the same time, our work has some limitations that need be addressed in future work. First, although complexity to input size can be lowered to linear, the number of basis grows rapidly with increasing order due to ( 792k/ In(k + 1))²) asymptotic formula of k-th Bell number [3) still making the model infeasible in higher orders. Improvement approaches such as finding compact subset of basis that retains universality (29] and exploiting unorderedness [26] are promising in this direction. Second, our work builds upon tensor-based representation of graphs, which makes it difficult to be directly extended to hypergraphs containing edges with varying orders (e.g., co-citation
networks). This is common challenge all tensor- basor- methods [14] 26 25
19 29 and
believe addressing this would be an important future research direction.
This work was supported in part by National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (202 RIIICC11224540 2021R (02131A443032834) and Institute of Information & Communications Technology Planning & Evaluation (ITPP) grant (2021-0-00537, 2019-0-00075).
Acknowledgements
"hnps:/wwww.dhhggo/DDnggg
10

---

References
[1] Ba, R. Kiros, and G. E. Hinton. Layer normalization. arXiv, 2016.
J.
[2] M. Belkin and P. Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Comput., 2003.
[3] D. Berend and T. Tassa. Improved bounds on bell numbers and on moments of sums of random variables. Probability and Mathematical Statistics., 2010.
[4] C. Cai and Y. Wang. note on over-smoothing for graph neural networks. arXivv 2020.
[5] T. Carletti, F. Battiston, Cencetti, and D. Fanelli. Random walks on hypergraphs. Physical Review 2020.
K. M. Choromanski, V. Likhosherstov, Dohan, Song, Gane, Sarlós, Hawkins, J. Q. Davis,
A. Mohiuddin, L. Kaiser, D. B. Belanger, L. Colwell, and A. Weller. Rethinking attention with performers. In ICLR, 2021.
[7] B. Delaunay. Sur sphère vide. Bulletin l'Académie Sciences de L'URSS, Classe des Sciences Mathématiques et Naturelles. 6: 793-800., 1934.
[8] V. P. Dwivedi
Bresson. A generalization of transformer networks to graphs. arXiv, 2020.
A. Fout, J. Byrd, B. Shariat, and A. Ben-Hlur. Protein interface prediction using graph convolutional networks. NIPS, 2017.
[10] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. In JCML, 2017.
[11] F. Gu, H. Chang. W. Zhu, S. Sojoudi, and L. E. Ghaoui. Implicit graph neural networks. In NeurlPS, 2020.
[12] B. Hanin and M. Sellke. Approximating continuous functions by relu nets of minimal width. arXiv, 2017.
[13] F. M. Harper J. A. Konstan. movielens datasets: History and context, ACM Trans. Interact. Intell. Syst., 2016.
[14] Hartford, D. Graham, K. Leyton-Brown, and S. Ravanbakhsh. Deep models of interactions across sets. In JCML, 2018.
[15] Hendrycks and K. Gimpel. Gaussian emor linear units (gelus). arXiv, 2018.
[16] K. Hormik, M. B. Stinchcombe, and H. White. Multilayer feedforward networks universal approximators. Neural Networks, 1989.
[17] W. Hu, M. Fey, H. Ren, M. Nakata, Y. Dong, and J. Leskovee, OGB-LSC: large-scale challenge for machine learning on graphs arXiv, 2021.
[18] A. Katharopoulos, A. Vyas, N. Pappas, and E. Fleuret. Transformers are mns: Fast autoregressive transformers with linear attention. In ICMI, 2020.
[19] N. Keriven and G. Peyré. Universal invariant and equivariant graph neural networks. In NeurIPS, 2019.
[20] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
[21] T. N. Kipf, Fetaya, K. Wang, M. Welling, and Zemel. Neural relational inference interacting systems. In ICML, 2018.
[22] Lee, Y. Lec, Kim, A. R. Kosiorek, S. Choi, and W. Tch. Set transformer: A framework for attention-based permutation-invariant neural networks. In /CML, 2019.
[23] Q. Li, Z.. Han, and X. Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI, 2018.
[24] Loshchilov and F. Hutter. Decoupled weight decay regularization. In ICLR, 2019.
[25] Н. Maron, H. Ben-Hamu, H. Serviansky, and Y. Lipman. Provably powerful graph networks. In NewrIPS, 2019.
[26] H. Maron, H. Ben-Hamu N. Shamir, and Y. Lipman. Invariant and equivariant graph networks. In ICLR. 2019.

---

[27] K. Oono and T. Suzuki. Graph neural networks exponentially lose expressive power for node classification. In ICLR, 2020.
[28] J. Qiu, J. Tang, H. Ma, Y. Dong, K. Wang, and J. Tang. Deepinf: Social influence prediction with deep learning. In KDD, 2018.
[29] H. Serviansky, N. Segol, J. Shlomi, K. Cranmer, E. Gross, H. Maron, and Y. Lipman. Se12graph: Learning graphs from sets. In NeurlPS, 2020.
[30] N. Srivastava, G. E. Hinton, A. Krizhevsky, Sutskever, and R. Salakhutdinov. Dropout: simple way prevent neural networks from overfitting, J. Mach. Learn. Rex., 2014.
[31] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin. Attention is all you need. In NeurlPS, 2017.
[32] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu. A comprehensive survey graph neural networks. IEEE Trans. Neural Networks Learn. Syst., 2021.
[33] R. Xiong, Y. Yang, D. He, K. Zheng. S. Zheng, C. Xing, H. Zhang, Y. Lan, I. Wang, and T. Liu. On layer normalization in the transformer architecture. In ICMI., 2020.
[34] C. Yun, S. Bhojanapalli, A. S. Rawat, S. J. Reddi, and S. Kumar, Are transformers universal approximators of sequencce-o--sqquence functions? In ICLR, 2020.
[35] M. Zaheer, S. Kottur, S. Ravanbakhsh, B. P6ezos, R. Salakhutdinov, and A. J. Smola. Deep sets. In NeurIPS, 2017.
[36] R. Zhang, Y. Zou, and J. Ma. Hyper-sagnn: a self-attention based graph neural network for hypergraphs. In ICLR, 2020.
[37] Z. Zhang, P. Cui, and W. Zhu. Deep learning on graphs: A survey, arXiv, 2018.
[38] V. W. Zheng, B. Cao. Y. Zheng, X. Xie, and Q. Yang. Collaborative filtering meets mobile recommendation:
A user-centered approach. In AAAI, 2010.
[39] J. Zhou, G. Cui, Z. Zhang, C. Yang, Z. Liu, and M. Sun. Graph neural networks: A review of methods and applications. arXiv, 2018
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See abstract and introduction.
(b) Did you describe the limitations of your work? [Yes] See Section 6
(c) Did you discuss any potential negative societal impacts of your work? [No] Due to the lack of space, we will discuss in the supplementary file.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See supplementary.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] We will provide
a code or link to the code in the supplementary file.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See supplementary file.
(c) Did you report error bars (e.g., with respect the random seed after running ex- periments multiple times)? [Yes] We reported standard deviation of ten repeated experiments in T
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See supplementary file.
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See citations.
(b) Did you mention the license of the assets? [N/A] Not applicable.
(c) Did you include any assets either in the supplemental material URL? [N/A]
Not applicable.
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A] All datasets used are open- sourced.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] No datasets contain identifiable content.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A] Not applicable.
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A] Not applicable.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A] Not applicable.
13


Reviews:
[{"review_id": "xTxDwbn4uCh", "reviewer": "Reviewer_tk1s", "summary": "The authors propose a framework to generalize transformers to any order permutation invariant data, especially hypergraphs. While the generalization itself is incremental compare to [20], the naïve approach gives unbearable computational complexity. Hence, the authors propose a series of tricks to lower the computational complexity which is their main contribution.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n\n(+) The idea itself sounds appealing.\n\n(+) The experiment results seem to provide evidence that the proposed method has better performance in general.\n\nWeaknesses:\n\n(-) The proposed tricks to reduce computational complexity are lack clarity. Moreover, some of them seem problematic in simple examples. (See detail comments)\n\n(-) The authors only use $L_{2\\rightarrow 2}$ layers at most. Hence, it is unclear to see whether the model complexity is indeed $O(m)$, independent of orders $l,k$.\n\n(-) This paper mainly focuses on the case where the input is a hypergraph. However, neither any experiments on hypergraphs nor hypergraph neural network baselines are included in the experiment section. \n\nDetail comments:\n\nWhile I like the idea of this paper a lot, its unclarity avoids me from supporting acceptance. My first concern is about its complexity reduction tricks. I find myself have at least one doubt for all three tricks (Section 4.1, 4.2, and 4.3).\n\nIn section 4.1, line 191-198. In the example of $L_{1\\rightarrow 1}$, the authors mention that they only use the basis $I_n$ and ignore the sum-pooling $11^T$ in Eq (4). Then they claim this light-weighted design is still able to model “interactions” between input elements. However, if we drop the sum-pooling $11^T$ in Eq (4), then no interactions between elements are considered, as now it only uses the basis $I_n$. This part really confuses me. Please elaborate more. Note that in the simple graph example, the proposed light-weighted design of $L_{1\\rightarrow 1}$ is to ignore all “edge features” which means the graph information is completely neglected. Clearly, it is impossible to recover this information barely from attention among node features in general.\n\nThe heuristic approach of Section 4.2, especially the use of E’ is unclear. Since the authors say it is a heuristic, I expect that this approach will lose some information in (at least) some special cases? Please provide a minimal illustrative example (i.e. k=2, l=1?) to explain the use of E’.\n\nLine 240. The definition of set $\\mathcal{I}$ is unclear. Does it mean the set that union all $\\mathbf{i},\\forall (\\mathbf{i},\\mathbf{j})\\in \\mu$ over all possible $\\mathbf{j}$? If this is the case, then shouldn’t the term that we actually summing over in eq (19) “less” than eq (20)? Why this resulting in further reduction needs more elaboration.\n\nOn the experiment side, since I feel the main contribution of the current paper is reducing the complexity of higher-order Transformer, I think the authors should at least conduct one experiment on it. More precisely, for a fixed hypergraph with $m$ hyperedges, I expect to see the experiment showing the time complexity of the proposed model remain unchanged even for increasing order $l,k$ in $L_{l \\rightarrow k}$. I think it is necessary to verify the proposed analysis result by experiments. In line 327-334. The authors mention that due to the growth of $k^{th}$ order bell number, the higher-order model is actually infeasible. In this case, I feel the importance and contribution of the current paper are greatly degraded.\n\nFinally, since the paper mainly focuses on the case where the input is a hypergraph, I think the authors should have some experiments regarding hypergraphs. However, neither any experiments on hypergraphs nor hypergraph neural network baselines are included in the experiment section. I suggest the authors either conduct experiments on hypergraphs and compare with SOTA hypergraph neural networks, or tone down the emphasis of hypergraphs at least in the abstract and introduction.\n\n***\nAfter rebuttal:\n\nI really appreciate the detailed response by the authors, which resolves most of my questions especially those for Section 4. I do think that the work should emphasize more on Transformer side (which is exactly the main focus of this paper) and tone down its application to hypergraphs. Still, I think the new experiments comparing with Hyper-SAGNN and S2G are great to be included in the revision. I will raise my score to 6.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "m4wnqC8U7bs", "reviewer": "Reviewer_fYvj", "summary": "This paper generalizes Transformer to higher-order Transformer, which is higher-order permutation invariant. To reduce the complexity, the authors propose to use sparse higher-order Transformer to achieve quadratic complexity, and further adopt the kernel attention approach to linear complexity.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n- This paper is well-written and well-organized, which is easy to follow.\n- The idea taht extend the concept high-order permutation invirant to Transformer, or say self-attention, is novel and indeed practical.\n- The design of higher-order self-attention makes sense to me.\n- The propsed model works well on synthetic dataset, which demonstrates that the model could match the motivation of this paper.\n\nCons:\n- It lacks a theoretical analysis of the performance (expressivenss, convergence, etc) about the two efficient tricks: sparse and kernel trick.\n- It lacks a empirical study about the running time in terms of the number of the nodes.\n- The original paper efficient transformers with kernel tricks (Performer, Transformers are RNNs, etc)  that cliam the performance would be degenerated if the models are trained from scratch. I wonder how the proposed higher-order Transformer with kernel trick solve this issue?\n- The baseline methods are too weak and old, most of the baseline methods are published at or before 2019. Even though, the proposed method could not outperform all baseline methods on all datasets.\n\nOne possible reason is that, the datasets used in this paper are relative small, and Transformer would be benefited from massive data (see Bert or ViT). Please consider to use large dataset to demonstrate your method.\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "cCVninHjywj", "reviewer": "Reviewer_385N", "summary": "The paper proposes a generalization of Transformer architecture to hypergraphs, with a particular focus on developing a fast sparse version.", "questions": "", "limitations": "", "rating": 8, "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 well written and the main motivation is clear. The proposed solution is novel, and, even though not so exciting from the modelling point of view, technically correct. The paper goes at great lengths to improve the scalability of the approach, and appears to do so successfully without compromising on the quality of the solutions and without introducing non-differentiable heuristics.\n\nMy main pain point is evaluation these models on the TU graph kernel datasets. As there are around 20-30 datasets, it is easy to overfit the model architecture and design choices to that particular task. While I do not believe this is true, it would be really nice to have some actual higher-order interaction dataset (academic co-authorship), even if it takes some time to produce/process.\n\nOverall, seems like a good paper to appear at the conference.\n\n\nEDIT: After the authors' comments, I raise my score to 8.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations paragraph is written greatly and directly calls for subsequent work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "TbN_vVy1Cy6", "reviewer": "Reviewer_uPAM", "summary": "In this paper, the authors proposed a transformer layer that generalizes the equivariant linear layers with self-attention to higher order tensor input. They defined the attention coefficient for each equivalence class $\\mu$ with indices satisfied $(i, j) \\in \\mu$ to reduce unnecessary computation between queries and keys matrices. To further reduce the computation complexity of higher order transformers, the authors provides 3 steps of approximation: i) a lightweight linear layers defined only for subset of equivalence class to decouple the indices $i$ and $j$. ii) adding proxy hyperedges $E'$ that is contained in original hyperedges $E$ and help reducing the computation to only $m$ hyperedges across different layers. iii) a kernel trick to decompose the attention coefficients into kernel map of query and keyword matrices. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "pros:\n- Generalized higher order linear layers with transformer encoder with self attention. \n- Reduced the complexity of transformer through above-mentioned approximations. \n- Overall, the transformer does have a larger expressive power than simple first order message passing algorithms.\n- Extensive and detailed experiments with synthetic and real world datasets in different graph-related tasks. \n\ncons:\n- I am concerned about sharing queries $\\tilde Q$ and keys $\\tilde K$ across all equivalence classes, as they might correspond to completely different propagation schemes with various bases. \n- Most of the results are still order 1 or 2 transformer layers, and the dataset are ordinary graphs. Lack of actual higher order interactions and hypergraph applications. \n- Some idea of proof is preferable in the main text instead of leaving all to supplementary. \n- The complexity is regarding to the number of matrix multiplication, but it can still be time/memory consuming in cases of large graph with higher feature dimension. An running time comparison in the experiment section would be a nice add-on for showcasing the efficiency. \n- The approximation of kernel attention in equation (20) removes correlations between $j$ and $i$ and shared across different input indices $i$ seems like a big trade-off and may raise some questions on whether the attention mechanism is still needed. \n- More detail on how the edge/node features of synthetic data are generated, how train/valid/test split are done with the chained labeled data is also missing. \n- Dataset statistics are missing. \n- Table 1 does not have any standard error. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors addressed the limitation in Section 6 and potential social impact in the supplementary. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper develops transformers for order permutation invariant data such as sets, graphs  and hypergaphs. Overall, the reviewers and I have enjoyed reading the paper since moving transformers towards structured data is an important research direction. The experimental results presented in the rolling discussion on sharing queries and keys across all equivalence classes as well as the ones comparing with Hyper-SAGNN and S2G have to be included in the final version. They really showed the pros of the proposed approach. While making those changes the authors may also wish to add the clarifications posted in the rolling discussion. 

Decision: Accept (Poster)