Polyhedron Attention Module: Learning Adaptive-order Interactions
Authors: Tan Zhu
Fei Dou
Xinyu Wang
Jin Lu
Jinbo Bi
Venue: NeurIPS 2023 poster (2023)
Keywords: Feature interaction modeling
model interpretation framework
adptive-order interaction
piece-wise polynomial

Abstract: Learning feature interactions can be the key for multivariate predictive modeling. ReLU-activated neural networks create piecewise linear prediction models, and other nonlinear activation functions lead to models with only high-order feature interactions. Recent methods incorporate candidate polynomial terms of fixed orders into deep learning, which is subject to the issue of combinatorial explosion, or learn the orders that are difficult to adapt to different regions of the feature space. We propose a Polyhedron Attention Module (PAM) to create piecewise polynomial models where the input space is split into polyhedrons which define the different pieces and on each piece the hyperplanes that define the polyhedron boundary multiply to form the interactive terms, resulting in interactions of adaptive order to each piece. PAM is interpretable to identify important interactions in predicting a target. Theoretic analysis shows that PAM has stronger expression capability than ReLU-activated networks. Extensive experimental results demonstrate the superior classification performance of PAM on massive datasets of the click-through rate prediction and PAM can learn meaningful interaction effects in a medical problem.

Polyhedron Attention Module: Learning Adaptive-order Interactions
Tan Zhu University of Connecticut tan. zhu@uconn.co edu
Fei Dou University of Georgia fei. dou@uga. edu
Xinyu Wang University of Connecticut xinyu. www.uuwwwnauuoo..nnomm edu
Jin Lu
Jinbo University of Connecticut jinbo. bi@uconn. edu
University of Georgia j jin. lu@uga. edu
Abstract
Learning feature interactions can be the key for multivariate predictive modeling. ReLU-activated neural networks create piecewise linear prediction models. Other nonlinear activation functions lead to models with only high-order feature inter- actions, thus lacking of interpretability. Recent methods incorporate candidate polynomial terms of fixed orders into deep learning, which is subject to the issue combinatorial explosion, learn the orders that difficult adapt different regions of the feature space. We propose Polyhedron Attention Module (PAM) create piecewise polynomial models where the input space split into poly- hedrons which define the different pieces and on each piece the hyperplanes that define the polyhedron boundary multiply form the interactive terms, resulting in interactions of adaptive order to each piece. PAM is interpretable to identify important interactions in predicting a target. Theoretic analysis shows that PAM has stronger expression capability than ReLU-activated networks. Extensive ex- perimental results demonstrate the superior classification performance of PAM on massive datasets of the click-througe rate prediction and PAM can learn meaningful interaction effects in a medical problem.
Introduction
Learning feature interactions provides insights into how predictors (features in x) interact to vary dependent variable y, and could significantly improve prediction performance in wide range of research areas, such as recommendation systems 2 3 4. genetic analysis [5] 6 and neuroscience
77 and help explain the decision -aaiing of complex model.
Interactions among features can significantly improve the model's expression capability. For simple example, by incorporating the two-way interaction effect between gender (0/1: female and male) and age into the linear regression model height ~ W1 gender + W2 age + W3 gender x age + wo (where up, W1, W2, Wy trainable parameters), the effects of female's 's age the heights will be different from that of male (wy v.s. W2 + w3). A predictive model fxx) has a k-way interaction effect it satisfies
Definition (k-way interaction effect) Let x be the input of a function f(x) ; IRP - IR, and æ; be the ith feature of x. Lei I C (1, 2, 2...,pp p} be a set of feature indices and (k > 2) be the cardinality of T. If
Ex ((x)
0,
(1)
Br,, da Bz,
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

f (x) exhibits a k-way interaction effect among features indexed by é1, ig....,... d E I.
A k-th order polynomial f(x can define k-order interactions which may not be k-way. A k-way interaction must occur among & different features. For instance, 2-way interaction between a; and 2j may occur as T;2y or z²a3. so can be generally written as E Wm,,m, 2; Ij some nonzero m, and mj if coefficients w's are nonzero. However, high dimensional features can generate enormous candidate interactions due to the combinatorial explosion, causing the curse of dimensionality. For example, & binary features can have 2 possible k-way interactions. This challenge in learning feature interactions attracts tremendous research interest in various models ranging from logistic regression to deep neural networks (DNN).
my for
Early methods learn the effects of feature interaction by multiplying features together and employing the multiplications as input to create an additive model. Two lines of methods have been used to reduce
the quantity of candidate interactions. Penalization methods (e.g., Hierarchical LASSO [10] [] and
Group-LASSO 122 assume hierarchy of interactions, so high-way interactions may be eliminated by removing low-way interactive terms. Factorization Machines (FM) require fewer parameters to fit all predefined interaction terms, which implicitly selects among candidate interactions [13 14 [5].
Only 2- and/or 3-way interactions were considered by these methods. To learn interactions among more features (higher-way), models such as FM-supported NN [16). product-based NN [77. AutoInt+ 18]. DESTINE [19] and AFN [20] predict the target with sigmoidal-activann
(such as the softmax or sigmoid function) DNNs. However, sigmoidal sigmoidal-activaeed DNN models only capture extremely high-order interactions among all features according to Definition| II. because sigmoidal activation functions have continuous (non-zero) derivatives up to infinite order with respect to all input features.
To capture interaction effects among a subset of features, an increasing number of works adopt Rel.U-activated plain DNN which fits piecewise linear function [21], as the backbone to develop interaction learning models. Models such as MaskNet 22 first form interaction effects and then use them as the input of ReLU-activated DNN, also known the stacked structure. Recently, more state-of-the-art performance has been achieved with models such as DeepIM (23], DeepFM (24), DCN [25], XDeepFM (26), AOANet 4,, DCN-V2 [25] EDCN (27 and FinalMLP (28 in parallel structure, which combines outputs of the proposed feature interaction learning models with those of a ReLU-activvted plain DNN by operators such summation, concatenation Hadamard product.
By fusing Rel.U-activated DNNs with models that explicitly incorporate interaction effects, piecewise polynomial functions can be formed. Rather than predicting the target with highly non-linear function infinitely differentiable on the input space, these methods divide the input space into pieces (e.g., polyhedrons), map instances to different pieces, and predict the target with piece-specific polynomial function. For all existing models, the piece-specific polynomial functions fit the same format of interactions (fixed I] [ x - terms for specific k) across all pieces once they are identified. However, data instances belonging to different pieces may endorse interactions in different ways. To address this problem, we propose new type of attention module called Polyhedron Attention Module (PAM). The main contribution this paper are summarized as follows:
PAM splits the input space into polyhedrons and predicts the target using a piecewise polynomial function which contains an attention term for each piece. The attention captures interaction effects of adaptive orders for different polyhedrons according to their local structure.
We propose a model interpretation approach for PAM identify important interaction effects for any given data instance.
We prove a universal approximation theorem for PAM, and show that DNNs incorporating PAMs need fewer parameters than ReLU-activated plain DNNs to maintain the same level of approxima- tion error in fitting functions in the Sobolev space.
Empirical studies are designed to validate PAM on benchmark datasets that are previously recog- nized to require feature interaction learning, such as the massive Criteo (33 million samples, 2.1 million features) and Avazu (28.3 million samples, 1.5 million features) thao-hhh datasets. Using medical database with feature meanings, we explore the interpretation of PAM.
2 Motivation Reinterpreting ReLU-based DNN
We argue that a plain fully-connected DNN with ReLUU activation function may be interpreted as an attention mechanism. Such neural network contains L consecutive blocks each constituting

---

fully-com colly-conneeted layer and ReLU-activation layer. Let x be the imput of the ε-th block which outputs a nested function ReLU( + b¹). The ReLU(z) returns when activated (if 2 2 0) or 0 otherwise. The consecutive I. blocks together create piecewise linear functions (each output in layer I. defines such function). For given raw input x, let 1e contains the indices of the activated ReI.U functions in layer & when x passes through the layer, and Wf= and bye contain the original weights, respectively, in W and 6f for those rows indexed in 1 and 0 vectors for those the complement set of I' (denoted by I² Then,
layer L, W(0x + b(() 2 where w(( II/= W and 6(0) = Σj=1 bys I 1 Wr... More precisely, it means that x stays in potyhedron that is defined by the intersection of all the half-spaces {x : W( x + b(0) 2 0} and {x w((c)x + ((t-) < <) for all L = 1, 1,.... L - 1 where W((-) W1+ I1 Wp and B(e-) =bc- + E b w I Wf+ specify those affine functions not activated in layer L. Here, Wre- and bye contain the original weights in W and bf for those rows indexed in / and 0 vectors for those in 1 For all in this polyhedron, the L-th layer outputs affine functions W(4)x b(L)
Precisely, the input space is divided into non-overlapping polyhe- drons and each polyhedron A is defined by a combination of acti- vated ReLU functions across the layers (a formal proof is given in Appendix A). To ease the notation, we simply use Á to denote the set of indices of the activated ReI.U across all layers that identify the polyhedron and A denotes the index set of the inactivated ReLU in the layers. We use an indicator function 1 (x E A) to define the poly- hedron which returns for all vectors that satisfy ((( and w(( x + ((5)) < O for L = 1,
2.5
4.
87
25-
5.
5.0
-25
0.0
5.0
Figure I: An example of 2-layer ReLU-activated plain DNN with output (the green shading shows the function value). Black lines are fitted in layer I (their intersec- tion defines the polyhedrons) and the red line fitted in layer 2 and varies on different polyhedrons.
x x 2 0 L - 1, and O otherwise. The i-th activated ReLU in the L-th layer corresponds
piece- wise linear function that computes W A, x + ( on each piece A.
Note that W(( and 2 vary for different polyhedrons due to the differences in the ReLU activation in the early layers (illustrated in
Fig. 1.. Denote the hyperplane {x: w(()) + b% 0} by H,,, which further splits A into two (L)
polyhedrons A = 1(x A, W A. x A 2 0) and A2 = 1(x A, W. x + (L)
0). Thus,
this piecewise linear function can be written as:
= ((x)=E1(xEE) ( (L) A,
(2)) = Ex1(XE ReLU
W(ll +
(L)
= =ss 1xX((E E( HA..I)) A.
+
1 E A2)dist(x, HA..L.)
attention
value on A
attention
value on Ag
(2)
where dist(x, H. means the distance from x to the hyperplane HA.LL The values on the two pieces A and Ag are constant ||W]|2]| || where || || is the l2 vector norm or O. The attention is function of x and depends on how far x is from one of the hyperplanes that define the polyhedron boundary (see Fig. for illustration).
We observe that a polyhedron A is defined using sequence of hyperplanes corresponding to the affine functions in different layers, but the attention of Rel.U-activated DNNs is calculated based only on the hyperplane in the last layer for the polyhedron (piece). Although not all of the hyperplanes in early layers make the active boundary of a polyhedron (i.c., the polyhedron can locate in the interior of half-space), using only one hyperplane in the attention is restrictive. An attention mechanism that allows multiple active boundary hyperplanes of polyhedron to aid attention calculation may increase the model's 's expression power. Let Hs contain all of the active boundary hyperplanes H of A. For convenient notation, and with mild relaxation, we rescale the WH to WWH for those inactivated affine functions in the DNN so the half-spaces can all be written in the form of WH + by 2 O. Then, 1 1(x E A) = II 1( + bu 2 0). To learn feature interaction effects, we multiply the distances from x to each hyperplane in Ha. Given hyperplane is linear in terms of x, multiplying the distances from x to two (m) hyperplanes creates quadratic (m-tt order) terms. Thus, the number of active boundary hyperplanes of A offers the upper bound on the order of the multiplicative terms
3

---

A
B
D
fr
ag
Inteprenrist franwerk
Viue (X)
PoMorroon
Make Kg)
Adi Peli)
AlteRAA Polyredron Sy(3) - dat, X cirt
Interadtion effedt
Figure 3: Overview description of the proposed method: (A) Split the imput space into overlapping polyhedrons with the oblique tree. (B) Calculate attention on each polyhedron based on distances to the polyhedron's 's boundaries. (C) Calculate the model's output based on the attention and value vector. (D) Extract main and interaction effects from the model.
each hyperplane used only once. allow the order to be adaptive to each A within the upper limit, we further enclose bounding constraint the distance (other strategies may exist, which leave for future investigation). Thus, the new attention formula can be written as follows:
0 (x) =1(x E A) IHEEA min(dist(x, H), [|
20n
II
1WWx + by 2 0) min(dist(x, H), [[W
20
=ITHEHA max (min [Wyx+bg 20H
([Wlll -[wll))
where Un determines an upper bound on the distance from x to and a trainable parameter. Fig. 2 demonstrates how adding the upper bounds Un allows the attention module to learn interaction effects of adaptive orders. For example, the instances in the area marked by in the figure (left) are far from each boundary hyperplane H beyond their respective upper bounds, so the min operator returns a constant |[
20 These x instances thus receive a constant attention that is the multiplication of these upper bounds each for H E HA. which gives O-order interaction. When is close to two of the hyperplanes (in those areas labeled by 2), two distance terms used in Eq. 3, defining two-way interactions.
Early methods pre-specify set of polynomial terms and use them as input features to a DNN (23] which limits the search space. another line of methods (20), each feature is associated with an order parameter m; and products in the form of II= are used as input (rather than raw fea- tures æ;) to Rei.U-activale to also learn the proper values of m,, an excellent ap- proach identify useful interactions, but once these m. 's are determined, the orders of feature interaction are fixed and cannot adapt to different pieces because the piccewise linear model (linear terms of the input products) learned by the DNN does not change interaction orders. Unlike these methods, our attention module automatically identifies appropriate orders according the topology of piece (particularly, using the number of active boundary hyperplanes of the polyhedron). Using introduced parameters UHr we can learn the ap- propriate order of the interactive terms within polyhedron by adjusting Unr (larger values of Uhr lead to higher-orders feature interaction). Our theoretical analysis (Section (5) shows that a DNN incorporating our attention module can approximate any function represented by ReLU-activated DNN at any arbitrarily accurate level with fewer model parameters.
al
bl
DNN. The DNN is required
Figure 2: For triangular polyhedron A this example, the attention oa can cap- ture constant, additive, 2-way interactive, and 3-way interactive effects in the areas, respectively, marked by 0. 1, 2, and 3, by ad- justing the upper bound parameter which smaller the left figure than in the right.
the interactions (polynomial terms) of
3 The Proposed Polyhedron Attention Module (PAM)
This section elaborates the PAM with the attention score defined in Eq. With input RP, DNN using PAM defines a function frAM:
SPAMs (x) Vx + (xxx(x)V(x;33))
where V(x; 0g) a global value function with trainable parameter lG. and (xx; 0x) is the local value function a piece A with trainable parameters 9s. We set both the global and local value

---

functions to be affine functions, so & contains the normal vector W and offset b. See 3.2 explains why affine functions are our choice. Instead of forming polyhedrons by intersecting hyperplanes as done in Rel.U-activated DNNs, we use tree search to partition the input space into overlapping polyhedrons. Note that the potential set of partitions created by tree search a superset of that created by hyperplance intersections (see Appendix B). We introduce how we generate polyhedrons and then discuss the attention and value functions.
3.1 Generating polyhedrons via oblique tree
Let Sa contain all the polyhedrons needed to form partition of the input space. We adopt the oblique tree to generate Sa. An oblique tree a binary tree where each node splits the space by a hyperplane rather than by thresholding single feature. The tree starts with the root of the full input space S, and by recursively splitting S, the tree grows deeper. For a D-depth (D 2 3) binary tree, there are 2D-1 node maintains a sub-space representing a polyhedron A in S, and each layer of the tree corresponds to partition of the input space into polyhedrons. Denote the polyhedron defined in node by A.. and the left and right child nodes of n by nt and ng. Unlike classic oblique trees that partition S into non-overlapping sub-spaces, we perform soft partition to split each An into Aay and Ann with an overlapping buffer. Let the splitting hyperplane be (x E IRP WnX + bn = 0}. Then the two sub-spaces And and Ang defined as follows:
internal nodes and 2 leaf nodes. As shown in Fig. 3A each internal and leaf
A nz. fxx E A, W bn 2 UU))
AnR = xx E A WnX - bn 2 -
where Un indicates the width of the overlapping buffer. Eq. 5shows that those instances satisfying [W,x + bnl < Un belong to the buffer in both An, and Ang- This buffer creates symmetric band around the splitting hyperplane.
Let Pn be the node set containing all the ancestor nodes above n. We can group the nodes in Pr into two subsets Pl, or P. where n appears in the left or right subtree of those ancestors. Let index the nodes in Pl, and j index the nodes in PK- Then for any node n except the root node, A, can be expressed as the intersection of the half-spaces:
An {x E IRP; Wix + b. U, E Pl, and W,x - bj -U Ewrh
(6)
Based on the polyhedron defined by Eq. 6 the attention 0s,, (x) (which we refer to as (x) to simplify notation) can be rewritten as
an (x) = IIEPP max(min( Wix+h, [[ill
21/ Will (.)))
I1) max(min( - x- +
20
0), (7)
[Wlll
[[.
where we use the buffer width U, to bound the corresponding distance term from above by TW.TT
20
Let Na consist of all the nodes the t layer of the tree, d (1,2,..., D). The nodes in Na altogether specify a soft partition of the input space that maps an instance x to one sub-space or an intersection of overlapping sub-spaces in [Ng). Rather than merely utilizing the instance partitioning map defined by the last layer of the tree (2 polyhedrons), we allow PAM to leverage polyhedrons generated at all layers in fPAM with SA 2 nn E Na) which gives 2D 2 polyhedrons.
3.2 Learning the attention and value functions
Each internal node in the oblique tree needs to learn two affine functions: a splitting function used form a hyperplane split the sub-space into child nodes, and value function. Because nested affine functions still produce affine functions, the set of affine functions is closed under linear transformations. Thus, we can use the value function to absorb the denominator ||Wi|| from the attention E In other words, for any learned 6,,, we can find a 6', (by rescaling 6,, with those [imi]] such that a,, (x) 8₂) = a', (x,,,,X, (%) where a', (x) IIeeP: max(min(Wa: + b, + U,,20 2U,), 0) Πee:: max (min( - W.x b, + U, 2U+), 0) and we use the subscript n to denote the polyhedron A represented in node n.. We thus directly set off to learn O', and use a', an.
More importantly, with affine value functions, we can derive another property. For any internal node n, the attention of its two child nodes contains an as factor, any (x) a, (xx maxxmmin(W,
5

---

- b, + Un. 2Un). 0). It gives rise an observation that no matter where x is located (inside the buffer or outside), anz (x) + ann (x) a, (x). Thus, we can substitute an (x) ) in the model [PAM by (x) - ang (x). Then, an (x) (x, 0x) + Ong. (x)V(x, Bn,,) + OnR (X)V(X Png) = (x) (V (V(x00n) 0n) 2U (x,
bn + Un, ,U,), 0) and ann (x) an (x)
ann (x) (V Bmn) ) V(x, )), which can be written as (x, 0) onn (x)V 0) for some parameters and & due to the closure of affine functions under linear transformations. Hence, once again, we directly learn 0 and 0 in our model training process. Note that we can recursively apply the above subsitution for all internal nodes n, so we can reduce the polyhedrons in S& by half. The following theorem characterize the above discussion (proof is in Appendix C.)
Theorem If all value functions V belong to a function set that is closed under linear transforma- tions, then the function learned by PAM fFAM can be equivalently written
fx) = (xx, 0G) + Enes, an (x 0n))
(8)
where the polyhedron set S contains half of the polyhedrons (e.g., the right child nodes or the left child nodes) in SA and
an (x(x)) = IIEP: (oxx(min(Wxx+r/tee 2U:), 0) I.EP, max(nin(-Wxx--bpp 200,,,U,)), (9)
Remark Although we include polyhedrons identified by the internal nodes our calculation,
fPAM only needs to learn _(20 - 2) 2D-1 1 value functions, which is actually in the same scale as that of only using leaf nodes in JPAM.
Optimization of PAM. The output of fPAMS can be treated as prediction of x's label or an embedding of x. PAM can be used as constituent component in a DNN to approximate a target y = f(frAM (x)). ) For classification task, we can calculate the conditional distribution ğ = Pr(y|x) = softmax [fr (x))) and optimize the cross-entropy I.CE- = - (x.x..))-DD) log j (1 y) log(1 - -) between the observed y and estimated ÿ to determine the parameters in PAM. For a regression task, the mean square loss LMSE = E (xx))DD(I - {(frAM(x))) can be used.
4 Model Interpretation
We propose a conceptual framework to quantify and interpret the interaction effects learned by PAM. Without loss of generality, we assume that the DNN has single output. Additional outputs can be similarly interpreted using the derived algorithm. The fPAM can be rewritten as a summation of k-way interaction terms for all possible values of l S D: fPAM (x) Exg(1....... 인z (x) where (x) captures the total contribution to the output from the |Tl-way interactions among the features indexed in I. If + Ø, (x(x) ">; wT llgg x²!" where x; represents the 7th feature of x, my calculates the power of x; in the interaction, and w's are constant coefficients in front of the corresponding interaction terms. Given the definition of our attention in Eq[l the highest polynomial order is D in the attention, together with the affine value function, the highest polynomial order of frAM is D, so Σ m, can not exceed the depth of the tree. If = 2, Φr = We which is a constant. We develop a method here to estimate the contribution values d frAM = Eigne Φr for fixed input x without computing the individual polynomial terms.
For a given x, fPAM can be written explicitly out as g(x) according to which polyhedron(s)
Algorithm 1: Obtain Φx for an input
x belongs to. To determine g(x), we pass x through the model Eg and evaluate every term in Eq For instance, for the first product in Eq 9 x makes W,x + b, 2 Ug, we replace (Wxx + b, + U, 2U;). 0) by 20, if Wxx + b, S -U, we replace it by 0; or otherwise, we use W, + b, + U.. Once the function is computed. we can use Algorithm to evaluate the contribution Φr. VI C (1..... .P) simple example can used to demonstrate Algorithm Let I = (1,2) which means we calculate the sum of those cross terms that involve exactly σ1 and Ø2. Thus we set all other elements in x to 0
1: Input: input .(x), and I S (1, .... p}
2: Output: dz
3: Set 07 to a p-length vector with I's in positions indesed
hy I. and (1's elsewhere
4: Calculate the following fanction: (Note that (x) also calculated via the same recursive function.)
the term
1(( I x) Errrrrreeeee Oz (x),
(x), I # Ø.
(x)
[(O).
I Ø,
where @ the Hadamard product operator.

---

and calculate g(0 ④ x)) to obtain the value that adds the terms involving only and T2. We then additionally set either 21 0 or ø2 0, or 2 22 (i.e., make all elements 0), re-compute g to estimate the linear terms of either ιt or 22, or the constant term in 9, and subtract these values from e to eventually obtain Φr. The following theorem characterize our results.
Theorem 2 For any input x, by calculating (I(x) for each I S (1, p} via Algorithm 1 have Exg(1.....))) xx( fPAM
The instance-level explanation of fPAM can be obtained by examining the magnitude of Or which reflects the impact of the feature interaction among the features in If (x(xx) > the interaction increase the predicted value; if ΦΛ < O, it reduces the output. The model-level interpretation can be approximated by computing the mean absolute value of the Ør across all sample instances.
Theoretical Justification Approximation Theorems
We examine whether using PAM can enhance the expression power for universal approximation. We first introduce the Sobolev space, which characterizes a space of functions satisfying specific smoothness properties Lipschitz continuous up to order which is formally defined as:
Definition 2 (Sobolev space) Let Wm. (I0, 1]P) be the Sobolev space which comprises of functions on [0, 1 lying in L along with their weak derivatives up order n. The norm of a function f in 00 (10, 112) is
IIflw ((..1))
max ess sup [D"f((x) m:/nSSn xE(0.1]p
T2....., where (m1; n22 -.... mp) E (1,2....,.3%
n1 + n2 + + np and D f is the n-order
weak derivative. The essential supreme ess sup ( inf E R: ul(z E E f(x) > M)) =
0} captures the smallest value that the function g can approach or exceed on a set É, except for negligible subset of points with the measure μ. Essentially, the space Wm, ((0, 1Ip) is ((0,
whose functions' derivatives up to order n are Lipschitz continuous.
The following assumption is commonly used in the discussion of DNNs. Without loss of generality, it narrows our focus on a normalized Sobolev sphere. This assumption constrains the functions having Sobolev norm no greater than I within the sphere.
Assumption Let Fn. be a set of functions lying in the unit ball in Wm,00 (IO, 1).), we have
Fn. = ( E Wm ((0, 1JP) I1 ((0, 1)2) 1)
This assumption is sufficient for our analysis, functions encountered in real-world learning tasks can typically be linearly transformed into W ([0, 1)"), as shown in previous studies [29]. This allows to analyze the error bounds for terms in the polynomial approximation after performing Taylor expansion. Theorem 3 demonstrates that our model can almost surely approximate any Reattivit DNN model without error. All proofs can be found in Appendix E and F.
Theorem If x is bounded and sampled from a distribution with upper-bounded probability density function, then for any ReLU activated plain DNN model fDNv(x), there exists a PAM with
Pr(JPAM (x) = (DNN(x)) +
Theorem 4 examines the parameter efficiency, and demonstrates that networks incorporating the proposed polyhedron attention require fewer parameters compared to those relying solely on ReLU activation, while maintaining the same approximation error in fitting functions in the Sobolev space.
Theorem 4 For any p. 0 and E (0, 1), we have a PAM which can 1) approximates any function from Fn.p with an error bound in the sense of L with at most 2p + (1) + n parameters, ml
where N = =[
Remark For the purpose of comparison, the ReI.U-activated plain DNN needs (N 1)P(p ()ng((lg(L/e)) parameters under the same setting in Theorem 30 29).
7

---

It is worth noting that extensive research has been conducted on the approximation theory of DNNs with the ReLU-activation, which often concerns common function classes in specific function spaces such as Besov [3 32 and Sobolev spaces 33 34
These analyses reveal notable influence of the smoothness of the target function on the resulting approximation errors. Since Sobolev spaces characterize the smoothness properties of functions, we can investigate the ability of neural networks with ReLU activation to approximate functions with different degrees of regularity and smoothness. These theorems highlight the expressivity of our model and provide theoretical insights for the parameter efficiency of our proposed attention module in neural network architectures.
Empirical Evaluation
We evaluate the effectiveness and efficiency of PAM on three large-scale datasets: the Crited and Avazu' click-through-rate (CTR) datasets, and the UK Biobank² medical database. We conduct an analysis of the hyperparameters of PAM, and perform ablation studies by individually removing each of the three key components of PAM and evaluating the performance variations. Given the lack of known feature meanings in CTR benchmark datasets, we utilize the UK Biobank dataset validate the interaction effects
as example for studying model interpretation. Specifically, captured by our interpretation framework, as detailed in Sec. El in the prediction of brain-age by the grey matter volumes from distinct brain regions. For implementation details, computation and space complexity of our model, please refer to Appendix G.
6.1 Experimental Setup
Datasets. Both the Criteo and the Avazu are massive industry datasets containing feature values and click feedback for display ads, and are processed following the
benchmark protocol in BARS (35 36). The UK Biobank serves as comprehensive biomedical database and research resource, offering extensive genetic and health-related information, where objective is to predict participants' age by leveraging the grey matter volumes from 139 distinct brain regions. The summary statistics are listed in Table 1
Table Statistics datasets.
Dalaset
#Train #Valid #Test NFeatures
Criteo
33M
8.3M
4.6M
2.1M
Avazu
28.3M
4M
8.1M
1.5M
UK Biobank
31.8K
4K
4K
139
Evaluation metrics. Criteo and Avazu datasets are concerned with binary classification tasks, evaluated using Area Under the ROC Curve (AUC). For brain-age prediction, regression problem, we assess performance using the R2 score.
Baseline Algorithms. We compare PAM against the top 5 algorithms from pool of 33 baseline methods, selected based on the overall AUC scores in BARS, including DESTINE [19] (currently the best performer on Avazu), DCN 337, AOANet 44) EDCN (27) (best Criteo), and DCN-V2 (25) Given that our model and the selected algorithms are DNN- we also include a well-tune DNN as a strong baseline for our model comparison. is worth noting that several state-of-the-an studies on CTR datasets, such as Criteo and Avazu, from Google 2 24 37). Microsoft (38) and Huawei 24 have recognized that even marginal improvement of AUC at the level of 1% is considered a significant performance enhancement.
6.2 Effectiveness and efficiency evaluation
Performance Comparison. We compare the results over five runs. As shown Fig. 44. PAM achieves the highest AUC and R² score amongst all benchmark algorithms. PAM outperforms the second-best model by 1.4 %o for Criteo, 0.6 %o for Avazu, and 2.2 for UK Biobank, which is much higher than the improvement achieved by the second-best model from the next model (0.4 %o for Critco, 16 %o for Avazu and 0.6 %0 for UK Biobank). It is also worth noting that, despite being well-tuned, none of the benchmark algorithms performs optimally across all three datasets simultaneously. We evaluate the computation time of PAM by comparing the training and inferecing runtime (seconds) per batch to the number of trainable parameters (#Par). As shown in Table 2 almost all models have a similar amount of free parameters, and their runtime per batch is com- parable among the methods (PAM is superior than half of the methods and inferior than the other half.)
8

---

0.8160
0.8160
0.8160
(UK (UK Blobank) (Avazu) (Criteo)
AUC
0.8151
0.8158
0.8153
0.8143
0.8157
0.8147
0.8134
0.8155
0.8140
0.7660
0.7660
0.7660
AUC
0.7649
0.7649
0.7649
0.7638
0.7638
0.7638
0.7627
0.7627
0.7627
0.5200
0.5200
0.5200
R2
0.5033
0.5167
0.5167
0.4867
0.5133
0.5133
0.4700
DNN DESTINE
OCN DCN-V2 AOANet
EDCN
PAM
0.5100
1.5
2.5
7 8
0.5100
w/o OP w/o AL! w/o RW PAM
U
D
a)
b)
Figure 4: Experimental results. Error bars represent the means and standard deviations of AUC for classification and R' for regression. a) AUC and R² scores PAM and comparison methods. h) Hyper-parameter analysis of PAM. U: the initial value U.. D: the depth of the oblique tree in PAM. c) Ablation studies of PAM.
Hlyper-aarameter Study. Al- though U, 's are trainable param- eters PAM, their initialization may affect how well PAM works. We hence study the effects of the initial values of U, 's by testing a set of choices from to 3 by a step size of 0.5. We also exam- ine the effects of the tree depth on PAM's performance. Fig. 4p shows the comparison where the initial values of Un do not sub- stantially change PAM's performance, which indicates that Un may be well trained during the PAM optimization. As for the depth D, the performance of PAM initially improves as 1) increases, but when /) becomes large, the performance may deteriorate. An appropriate value of /) will help PAM learn more domain knowledge, but if D is too large, highly complex interactions may not necessarily lead to better prediction due to issues such as overfitting.
number parameters (MPrr training and inference of PAM and baseline models.
per (Sec/Batch) during the
Criteo
Avazu
UK Biobank
Model
Sec/Batch
Sec/Batch
Sec/Batch
#Par
#Par
Training Interence
Training Interence
Training Interence
PAM
22.3M
0.102
0.0330
14.IM
0.090
0.0263
315K
0.083
0.0018
DNK
21.8M
0.046
0.0139
13.8M
0.038
0.0129
380K
0.056
0.0063
DESTINE
21.5M
0.130
0.0344
13.6M
0.090
0.0188
384K
0.072
0.0069
DCN
0.080
0.0099
0.069
0.0064
DCN-V2
22.0M
0.103
0.0128
13.8M
0.091
0.0137
458K
0,059
0.0067
AOANer
21.MM
0.151
0.0314
0.338
0.0168
457K
0.066
0.0067
EDCN
21.5M
0.066
0.0119
13.1M
0.048
0.0113
63K
0.072
0.0071
Ablation Study of PAM. The following specifies the three components for our ablation experiments. 1) PAM without overlapping polyhedrons (PAM w/o OP). As shown in Eqs. 3 and overlapping polyhedrons generated in PAM to fit the target. To demonstrate the importance of soft splitting, calculate a, (x) with Iee:: max(min WWx x + b,, 2U,,. .), 0) Ihe max(min( W,x b, 2U,).)
2) PAM without adaptively learning interaction (PAM w/o ALI). As shown in Fig. 5 the upper- bound 20: enables PAM to learn interactions with different orders different polyhedrons. To exam the effectiveness of the upper bound, we remove this upper bound 20; from Eq. g
3) PAM without removing ||Will (PAM w/o RW). According to Theorem the denominator of Eq. can be removed without reducing the expression capability of PAM.. To examine the correctness of this claim, we directly use PAM without removing
[W,] from the denominator.
Fig. - clearly demonstrates a notable decline in the performance of the PAM when key components are removed. In particular, the standard PAM significantly outperforms the PAM w/o OP. confirms the critical role of overlapping polyhedrons in enhancing PAM's performance. The removal of ALI decreases the AUC and R²2 of PAM as well, indicating the significance of combining low-way interaction effects with high-way ones to fit the target. Moreover, PAM w/o RW shows that removing W&] from the denominator in Eq. 7 iiimproess PAM's performance. Although, according to Theorem I PAM without RW has the same expressive capability standard PAM, the inclusion of W's norm in the denominator of Eq. may result in unstable gradient variances, potentially compromising the performance of the optimizer.
6.3 Identified interaction effects among neural markers in predicting brain age
Although the interpretation framework was developed for PAM, can applied to those DNN architectures whose functions piece-wis, polynomials (see Appendix D). After carefully checking

---

B
LAC
U10C
BCI
BSC
LFP
Brlnurar
BVG
B-SC
RAGC
8T
RPOC
APP
20
20
26
-00
-20
20
-30 The distiibution impact the main
The diéribution of impact the effect
The distribution impart the mann effect
C)
(Ransular: TUFP)
ELAG, RRPPI
(RAP: TLFP)
1Rrmuller, (LFP)
ELPG: 1A00C
[RSS; (UPP))
(RIG. LPP
(R-OCS0 (RFP)
(UP))
PL-G; (RCR)
(LAOC) X-PP)
(RFP, (UP)
(R.FP: FPF
(R RE.00S:: F
-00
-0
2:00
6.35
0.5
0.75 1.00
1o0 6:0t 0.000 8.0m 0.004
The distribution of impect of the effect
The dist-ibuttin impact the way effect
The distribution of impact or the way effect
d)
Figure 5: Top main and 2-way interactions identified by PAM (Figs. and b), DCN (Figs. с and d) and AOANct (Figs. с and f) by sorting mean absolute values of each Φr. averaged over all participants. For cach effect, points (each corresponding to participant) are distributed according to á values calculated by Algorithm I in the beeswarm bars. L: left; R: right: CR: crus II cerebellum; FOC: frontal orbital Cortex; FG: frontal gyrus; PP: planum polare; OCSD: lateral occipital cortex, superior division; FP: frontal pole; LOC: lateral occipital cortex; PG: precentral gyrus; T: thalamus; SC: subcallosal cortex.
all baseline methods, found that our interpretation framework could be used to extract interactions from DCN and AOANet. Fig. presents the top five main effects (Figs. a, с and e) and two-way interaction effects (Figs. b, d and f) between brain regions to brain-age prediction, determined by the trained PAM, DCN and AOANet.
According to Figs. 5 and 5p. PAM found that the grey matter volumes (GMV) of both the left and right frontal poles (FP) play significant main effect as individual features, which well aligned with previous research findings 39 40 41. The other three brain regions, lateral occipital cortex (LOC),
precentral gyrus (PG) and thalamus (T), are also discussed in early studies [2 43 44) Existing aging studies primarily focus main effects of GMV, but the top five wao GMV interactions of identified brain regions have been acknowledged in works such as (4). As shown in Fig. [5p. 5p and 5f, the main effects of PG and T' identified by PAM were found by DCN and AOANet, respectively, and all three algorithms found the two-way interactions between the left and right FP. In addition to the shared top-5 brain regions identified by PAM, AOANet and DCN, PAM additionally identified the main effect of the LOC and FP and two-way interaction effects related to the insular and subcallosal cortex (SC) regions.
7 Conclusions and Future Work
We propose novel feature interaction learning module, namely Polyhedron Attention Module (PAM). to fit target with adaptive-order interaction effects. PAM produces a self-attention mechanism partitioning the input space into overlapping polyhedrons and learning the boundary hyperplanes for each polyhedron automatically. These hyperplanes multiply to identify interaction effects specific to individual polyhedrons. Under this mechanism, PAM automatically captures both simple and complex interaction effects. In our theoretic analysis, we show that PAM can enhance the model expression power for universal approximation. Experimental results demonstrate that the proposed model achieves better performance on massive datasets than the state-of-the-art In the future, we will study how to dynamically pruning PAM's s oblique tree during the training process to regularize the model. It will also be interesting investigate how define boundaries with non non-lineat functions.
10

---

Acknowledgments
This research has been conducted using the UK Biobank Resource under the Application 51296 Machine Learning Analysis of Brain Images, Behaviors, and Genotypes to Understand Mental Disorders, and was supported part by the NIH grant K02-DA043063 and NSF award #2122309.
References
[1] Xinran Hc, Junfeng Pan, Ou Jin, Tianbing Xu, Bo Liu, Tao Xu, Yanxin Shi, Antoine Atallah, Ralf Herbrich, Stuart Bowers, et al. Practical lessons from predicting clicks on ads at facebook. In Proceedings of the eighth international workshop data mining for online advertising, pages 1-9, 2014.
[2] Heng-Tze Cheng, Levent Koc, Jeremiah Harmsen, Tal Shaked, Tushar Chandra, Hrishi Aradhye, Glen Anderson, Greg Corrado, Wei Chai, Mustafa Ispir, et al. Wide & deep learning for recommender systems. In Proceedings of the 1st workshop on deep learning for recommender systems, pages 7-10, 2016.
[3] Paul Covington, Jay Adams, and Emre Sargin. Deep neural networks for youtube recommenda- tions. In Proceedings of the 10th ACM conference recommender systems, pages 191-198, 2016.
[4] Lang Lang, Zhenlong Zhu, Xuanye Liu, Jianxin Zhao, Jixing Xu, and Minghui Shan. Architec- ture and operation adaptive network for online recommendations. In Proceedings of the 27th ACM SIGKDD Conference Knowledge Discovery & Data Mining, pages 1139-3149, 2021.
[5] Bing Wang, Steven M Smith, and Jiayang Li. Genetic regulation of shoot architecture. Annual review of plant biology, 69:437-468, 2018.
[6] Sumanta Basu, Karl Kumbier, James B Brown, and Bin Yu. Iterative random forests to discover predictive and stable high-order interactions. Proceedings of the National Academy of Sciences, 1943, 2018.
[7] Shan Yu, Hongdian Yang, Hiroyuki Nakahara, Gustavo S Santos, Danko Nikolić, and Dietmar Plenz. Higher-order interactions characterized in cortical activity. Journal of neuroscience. 3 11545):77514-1556 2011.
[8] Baiying Lei, Shuangzhi Yu, Xin Zhao, Alejandro F Frangi, Ee-Leng Tan, Ahmed Elazab, Tianfu Wang, and Shuqiang Wang. Diagmosis of early alzheimer's disease based on dynamic high order networks. Brain Imaging and Behavior, 15(1):276 2876622872200 2021.
[9] Michael Tsang, Dehua Cheng, Hanpeng Liu, Xue Feng, Eric Zhou, and Yan Liu, Feature interaction interpretability: A case for explaining recoomeendationn systems via neural interaction detection. arXiv preprint arXiv:2006.1044 2020.
[10] Jacob Bien, Jonathan Taylor, and Robert Tibshirani. lasso for hierarchical interactions. Annals of statistics, 41(3):1111, 2013.
2013.
[11] Gregory Vaughan, Robert Aseltine, Kun Chen, and Jun Yan. Efficient interaction selection for clustered data via stagewise generalized estimating equations. Statistics in Medicine, 39(22):2855-288) 2020.
[12] Michael Lim and Trevor Hastie. Learning interactions via hierarchical group-lasso regulariztin. Journal of Computational and Graphical Statistics, 24(3):627-654, 2015.
[13] Steffen Rendle. Factorization machines. In 2010 IEEE International conference on data mining. pages 995-1000. IEEE, 2010.
[14] Harshit Pande. Field-embedded factorization machines for click-through rate prediction. arXiv preprint 20X0992000.09931, 2020.

---

[15] Yang Sun, Junwei Pan, Alex Zhang, and Aaron Flores. Fm2: Field-matrixed factorization machines for recommender systems, In Proceedings of the Web Conference 2021, pages 2828 2837, 2021.
[16] Weinan Zhang, Tianming Du, and Jun Wang. Deep learning over multi-field categorical data. In European conference on information retrieval, pages 45-57. Springer, 2016.
[17] Yanru Qu, Han Cai, Kan Ren, Weinan Zhang, Yong Yu, Ying Wen, and Jun Wang. Product-based neural networks for user response prediction. In 20/6 IEEE 16th International Conference on Data Mining (ICDM), pages 1149-1154, IEEE, 2016.
[18] Weiping Song, Chence Shi, Zhiping Xiao, Zhijian Duan, Yewen Xu, Ming Zhang, and Jian Tang. Autoint: Automatic feature interaction learning via self-attentive neural networks. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, pages 1 1161-1170, 2019.
[19] Yichen Xu, Yanqiao Zhu, Feng Yu, Qiang Liu, and Shu Wu. Disentangled self-attentive neural networks for click-thros thrckhhhhughhhh rate prediction. In Proceedings of the 30th ACM International Conference Information & Knowledge Management, pages 3553-3557, 2021.
[20] Weiyu Cheng, Yanyan Shen, and Linpeng Huang. Adaptive factorization network: Learning adaptive-order feature interactions. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3609-3616, 2020.
[21] Francesco Croce, Maksym Andriushchenko, and Matthias Hein. Provable robustness of relu networks via maximization of linear regions. In the 22nd International Conference on Artificial Intelligence and Statistics, pages 2057-2066 PMLR, 2019.
[22] Zhiqiang Wang, Qingyun She, and Junlin Zhang. Masknet: introducing feature-wise multi- plication to etr ranking models by instance-guien guided mask. arXiv preprint arXiv:2102.07619, 2021.
[23] Feng Yu, Zhaocheng Liu, Qiang Liu, Haoli Zhang, Shu Wu, and Liang Wang. Deep interaction machine: A simple but effective model for high-order feature interactions. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pages 2285-2288, 2020.
[24] Huifeng Guo, Ruiming Tang, Yunming Ye, Zhenguo Li, and Xiuqiang He. Deepfm: a factorization-machie based neural network for prediction. arXiv preprint 111:11703.04247,, 2017.
[25] Ruoxi Wang, Rakesh Shivanna, Derek Cheng, Sagar Jain, Dong Lin, Lichan Hong, and Ed Chi. Den v2: Improved deep cross network and practical lessons for web-scale learning rank systems. In Proceedings of the Web Conference 2021, pages 1785-1797, 2021.
[26] Jianxun Lian, Xiaohuan Zhou, Fuzheng Zhang, Zhongxia Chen, Xing Xie, and Guangzhong Sun. xdeepfm: Combining explicit and implicit feature interactions for recommender systems. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pages 1763, 2018
[27] Bo Chen, Yichao Wang. Zhirong Liu, Ruiming Tang, Wei Guo, Hongkun Zheng, Weiwei Yao, Muyu Zhang, and Xiuqiang He. Enhancing explicit and implicit feature interactions via information sharing for parallel deep etr models. Proceedings of the 30th ACM International Conference Information & Knowledge Management, pages 3757-3766, 2021.
[28] Kelong Mao, Jieming Zhu, Liangcai Su, Guohao Cai, Yuru Li, and Zhenhua Dong, Finalmlp: An enhanced two-stream mlp model for ctr prediction. arXiv preprint -XXv:2304.00000 2023.
[29] Feng-Lei Fan, Hang-Cheng Dong, Zhongming Wu, Lecheng Ruan, Tieyong Zeng, Yiming Cui, and Jing-Xiao Liao. One neuron saved is one neuron earned: On parametric efficiency of quadratic networks. arXiv preprint arXiv:2303.06 06316, 2023.
[30] Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94:103-114, 2017.
12

---

[31] Taiji Suzuki. Adaptivity of deep relu network for learning in besov and mixed smooth besov spaces: optimal rate and curse of dimensionality. International Conference on Learning Represeniations, 2019.
[32] Hao Liu, Minshuo Chen, Tuo Zhao, and Wenjing Liao. Besov function approximation and binary classification on low-dimensional manifolds using convolutional residual networks, In International Conference Machine Learning, pages 6770-6780 6780. PMLR, 2021.
[33] Hao Liu, Minshuo Chen, Siawpeng Er, Wenjing Liao, Tong Zhang, and Tuo Zhao. Benefits of overparameterized convolutional residual networks: Function approximation under smoothness constraint. In International Conference on Machine Learning, pages 13669-13703, PMLR, 2022.
[34] Sho Okumoto and Taiji Suzuki. Learnability of convolutional neural networks for infinite dimensional input via mixed and anisotropic smoothness. In International Conference on Learning Representations, 2022.
[35] Jieming Zhu, Quanyu Dai, Liangcai Su, Rong Ma. Jinyang Liu, Guohao Cai, Xi Xiao, and Rui Zhang. Bars: Towards open benchmarking for recommender systems. Proceedings of the 45th International ACM SIGIR Conference Research and Development in Information Retrieval, SIGIR '22. page 2912-2923 New York, NY, USA, 2022. Association for Computing Machinery.
[36] Jieming Zhu, Jinyang Liu, Shuai Yang, Qi Zhang, and Xiuqiang He. Open benchmarking for click-through rate prediction. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pages 2759-2769, 2021.
[37] Ruoxi Wang, Bin Fu, Gang Fu, and Mingliang Wang. Deep & cross network for ad click predictions. In Proceedings of the ADKDD' 17, pages -.17.01.
(38] Xiaoliang Ling, Weiwei Deng, Chen Gu, Hucheng Zhou, Cui Li, and Feng Sun. Model ensemble for click prediction in bing search ads. In Proceedings of the 26th international conference on world wide web companion, pages 689-698, 2017.
[39] Jason Steffener, Christian Habeck, Deirdre O'Shea, Qolamreza Razlighi, Louis Bherer, and Yaakov Stern. Differences between chronological and brain age are related to education and self-reported physical activity. Neurobiology of aging, 40:138-144 144, 2016.
[40] Dafna Sussman, Rachel C Leung, M Mallar Chakravarty, Jason P Lerch, and Margot Taylor. The developing human brain: age-related changes in cortical, subcortical, and cerebellar anatomy. Brain and behavior, 6(4):e00457, 2016.
[41] Susanne Mueller, Michael W Weiner, Leon J Thal, Ronald C Petersen, Clifford R Jack, William Jagust, John Q Trojanowski, Arthur W Toga, and Laurel Beckett. Ways toward an early diagnosis in alzheimer's disease: the alzheimer's disease neuroimaging initiative (adni). Alzheimer's 's & Dementia, 1(1):55-66 66, 2005.
[42] Johnny Wang, Maria J Knol, Aleksei Tiulpin, Florian Dubost, Marleen de Bruijne, Meike W Vernooij, Hieab HH Adams, M Arfan Ikram, Wiro Niessen, and Gennady Roshchupkin. Gray matter age prediction biomarker for risk of dementia. Proceedings of the National Academy of Sciences, 16(42):21213-2122 2019.
[43] David H Salat, Randy L Buckner, Abraham Z Snyder, Douglas N Greve, Rahul SR Desikan, Evelina Busa, John C Morris, Anders M Dale, and Bruce Fischl. Thinning of the cerebral cortex in aging. Cerebral cortex, 14(7):721-730, 2004.
[44] Rosemary Fama and Edith V Sullivan. Thalamic structures and associated cognitive functions: Relations with age and aging. Neuroscience & Biobehavioral Reviews, 54:29 37, 2015.
13


Reviews:
[{"review_id": "JjnOMxFC54", "reviewer": "Reviewer_61Ki", "summary": "The paper introduces a more general nonlinearity, PAM, to better capture the data features' interactions. Theoretical justification and interoperability are performed along with empirical results.", "questions": "It will be nice to simplify the notations and convey the concepts more plainly. The article can improve by reorganization. More experiments can also help to validate the method.", "limitations": "Limitations have been properly addressed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The method seems to be inspired from sharp mathematical observations. It has mathematical interpretation and a sound rational connecting existing methods.", "weaknesses": "The explanation and intuition behind the methods are unclear; for example, the introduction of k-way interaction is put in front of the article but lacks a description of what it means and why it is essential. \nIt is unclear how the method generalizes to complicated models and what the complexity will be.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your follow-up questions and comments. Below we address each question and minor questions in a point by point fashion.\n\nWeakness:\n\nResponse: We further explain the rational of the presentation of our paper here and will revise our paper to explain better with examples. Feature interactions can occur in many different forms. The k-way interaction is defined first (according to existing work) to provide us a mathematical basis so we can derive the quantitative algorithm in the subsequent sections. K-way interactions mean any kind of interaction among k different input features. A deep learning model with highly nonlinear activation function, for a simple example, $sigmoid(\\sum w_i x_i)$ with $i = 1, \\cdots, d$ specifies a d-way interaction of any arbitrary order (as $sigmoid$ has derivatives of arbitrary order), and lack of interpretability. Instead, a lower-order interaction among fewer features (lower way) can significantly improve the model explainability.  For a simple example, by incorporating the two-way interaction effect between gender (0/1: female and male) and age into the linear regression model  $height\\sim w_1\\cdot gender+w_2\\cdot age+w_3\\cdot gender\\times age+w_0$ (where $w_0,w_1,w_2$ and $w_3$  are trainable parameters), the effects of female's age on the heights will be different from that of male ($w_2$ v.s. $w_2+w_3$). Our approach seeks to identify such low-way and low-order interactions for better interpretability.\n\nThe most straightforward way to define k-way interactions is to form multiplicative terms among the k features (e.g., $x_1, x_2, \\cdots x_k$). Our attention module PAM adaptively derives multiplications of linear functions (corresponding to the boundary hyperplanes of a polyhedron) when learning the partition of the input space into polyhedrons. Thus, the linear function multiplication generates multiplicative terms among various features (being adaptive to different input regions/polyhedrons) in generally lower order polynomials. \n\nResponse: The following answers the second critique about how to generalize PAM to complicated models and the complexity of PAM. \nAs mentioned in Section 6 and Appendix G, the proposed PAM can be used as a basic module in a stack to generalize to complicated models. Each module maps its own input (output from early PAM blocks) according to Eq.4. PAM has already been used as the basic module in our experiments to build a complicated model whose architecture is given in Appendix G. \n\nThe computation complexity of other deep learning methods has been previously discussed. We follow the principle of Yan et al. 2022 [1] to now discuss the complexity of PAM. As shown in Eq. 4, the dimension of PAM's input is $p$. In our experiment, we consider two kinds of value functions in this work, i.e., $V(x;\\theta_n)=W_nx+b_n, W_n\\in\\mathbb{R}^{p\\times 1}, b_n\\in\\mathbb{R}$ and $V(x;\\theta_n)=b_n$, $b_n\\in\\mathbb{R}^p$. Since a PAM with a D-depth oblique tree has $2^{D-1}$ value functions (1 global value function following Eq. 3 and $2^{D-1}-1$ value functions for polyhedrons following Remark 1), the memory complexity of these two kinds of value functions is $\\mathcal{O}(2^{D-1}p)$. In addition to the value function, a D-depth oblique tree has $2^{D-1}-1$ hyperplanes with $\\mathcal{O}(2^{D-1}p)$ trainable parameters. Therefore, the total MEMORY complexity of PAM is $\\mathcal{O}(2^{D}p)$. \nAs for the time complexity, PAM need to 1) calculate the attention score following Eq. 9, 2) generate the corresponding values via value functions mentioned above, and 3) output $f_{PAM}$ by multiplying the attention with values following Eq 8. The computation complexity is shown as follows:\n\n| Value function | Step 1  |Step 2  |Step 3 |\n| ---- | ----------- |----------- |----------- |\n| $W_nx+b_n$ |$ \\mathcal{O}(2^{D-1}(p+D)) $      |$\\mathcal{O}(2^{D-1}p)$       |$\\mathcal{O}(2^{D-1})$       |\n|  $b_n$   | $\\mathcal{O}(2^{D-1}(p+D))$        |-       |$\\mathcal{O}(2^{D-1}p)$        |\n\nThus, the TIME complexity of PAM is $\\mathcal{O}(2^{D-1}(2p+D))$. Note that in our experiment $p\\gg D$. We will add this analysis to Remark 1 to illustrate the complexity of our model. \n\n[1] Yan, Bencheng, et al. \"APG: Adaptive parameter generation network for click-through rate prediction.\" Advances in Neural Information Processing Systems 35 (2022): 24740-24752.\n\nQuestions:\n\nResponse: We will simplify the notations and provide a notation table to link the different symbols. We will demonstrate the concepts with an overall figure as suggested by Reviewer wPpx (please see Fig. S1 in the attached pdf and response to Reviewer wPpx). \n\nMore experiments have been performed and added to validate our method (also in response to other reviewers' suggestions):\n\na) As shown in Table S1 in the attached pdf, the inference time of PAM and other baseline methods is compared.\n\nb) As shown in Table S2 in the attached pdf, the unpaired t-test has been conducted to evaluate the statistical significance of PAM's improvement over baselines (using the performance numbers in Figure 4a and additional runs of the different models).  "}, {"review_id": "aF8711DGzP", "reviewer": "Reviewer_8xSi", "summary": "The ReLU-activated DNN will split the input space into pieces such as polyhedrons. The author proposes a polyhedron attention module (PAM) to capture the interaction between different pieces of input spaces. And they propose an approximation theorem for PAM. The polyhedrons are generated via an oblique tree, and each tree node means a sub-space of a polyhedron. And for each node, two functions will be learned: the splitting function which decides how to further split the hyperplane, and the value function. The authors also show that such a module needs fewer parameters than the plain DNN. ", "questions": "N/A", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1: The author provides a detailed and clear explanation on how the proposed works. \n\n2: The general idea is novel. The split and attention step can dynamically capture the adaptive interaction between different data instances. \n\n3: The author also provides necessary justification for the methods. ", "weaknesses": "1: Since I am not familiar with the baseline proposed in the paper, in section 6.3, I want to see whether other methods can find the same effects and interactions or not. \n\n2: Table 2 still shows that the PAM has more parameters and more running time compared to other methods. It will be helpful if the author can add a few explanations. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your follow-up questions and comments. Below we address each question and minor questions in a point by point fashion.\n\nWeaknesses:\n\nResponse to 1: Reviewer asked about the baseline methods in Section 6.3 and whether these methods can find the same effects and interactions. As far as we know, our interpretation framework introduced in Section 4 is the first algorithm to extract the main and interaction effects from DNN models. We do stress that although it was developed for PAM, it can be applied to those DNN architectures where activation functions are piece-wise linear (e.g., ReLU, ReLU6, and HardTanh, please also consult with the proof in Appendix D). \n\nAfter carefully checking all baseline methods in Section 6, we found that our interpretation framework could be used to extract interactions from AOANet and DCN. The main effects of precentral gyrus and thalamus identified by PAM were found by DCN and AOANet, respectively (Fig. S2 in the attached pdf), and all three algorithms found the two-way interactions between the left and right frontal pole. In addition to the shared top-5 brain regions identified by these three algorithms, PAM additionally identified the main effect of the lateral occipital cortex and frontal pole and two-way interaction effects related to the insular and subcallosal cortex regions.\nWe will put these results into section 6.3.\n    \nResponse to 2: It does make sense to explain why PAM has more parameters and run time in the experiments. Note that our theoretical analysis shows that PAM has more parameter efficiency for universal approximation than ReLU-activated DNN. In other words, ReLU-activated DNN may need more parameters to reach universal approximation. However, it does not prevent the overfitting of the larger size DNN on a specific task. In our experiments, the standard DNN model (ReLU-activated), if using more parameters following Theorems 3 and 4, produced worse test performance than the one we reported.  For fair comparison, we reported on the architectures of all the other models which gave the best performance. It shows that these models used slightly smaller numbers of parameters, but their best tuned performance was worse than that of PAM (Fig. 4a). \n    \nFor experiments on Criteo and Avazu, although PAM has slightly more trainable parameters, its run time is comparable with that of the baselines with fewer trainable parameters (i.e., DESTINE and DCN-V2) because all value functions within the red box in Fig.1 in Appendix G have the same input $x$ and can thus be calculated in parallel. \n\nWe would also like to point out that we used pre-existing modules within the PyTorch package to implement PAM. These modules have well-optimized CUDA kernels for forward and backward functions, leading to efficient execution of DNN. However, the oblique tree data structure is not included in PyTorch. We believe that a customized CUDA kernel would further enhance the run time of PAM.\n\nWe will add these explanations to a supplemental section. "}, {"review_id": "zjIhhHDJTq", "reviewer": "Reviewer_wPpx", "summary": "The paper proposes a Polyhedron Attention Module (PAM) to create piecewise polynomial models to learn feature interactions in multivariate predictive modeling. Specifically, the input space is split into polyhedrons which define the different pieces and on each piece the hyperplanes that define the polyhedron boundary multiply to form the interactive terms, resulting in interactions of adaptive order to each piece. Theoretical analysis and experimental verification are provided to demonstrate the superior of PAM.", "questions": "1. The intuition of PAM is that the authors believe data instances belonging to different pieces may endorse interactions in different ways. Why should this be the case? It would be more convincing if the authors could provide real-world examples to illustrate why we should consider data interactions at a local scale.\n\n2. The common drawback of local methods is that inference can be expensive. For PAM's case, the heavy cost may lie in the step of generating polyhedrons for each data instance. How does tree search help reduce this cost?\n\n3. Why the polyhedrons should overlap? An ablation study between overlapping and non-overlapping polyhedrons will be beneficial.\n\n4. (Minor) The paragraph right after Eq. (5) is unfinished.\n\n5. The improvements on Criteo and Avazu datasets are incremental with around 0.1% AUC increase. Although the authors have compared with the improvements of the second-best method, it would be more convincing if the authors could conduct statistical significance tests for PAM's improvements.\n\n6. Overall, the standard deviations of PAM in the experiments are lower than other methods. Can the authors provide a thorough explanation for this improvement?\n\n7. An ablation study on training & inference time of PAM compared to other methods may be beneficial.\n\nI would happily increase my score if the authors carefully tackled my concerns above.\n", "limitations": "The authors have not included a limitation section.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The paper is written carefully with mathematical details. The tables and figures are quite clear.\n2. The paper provides both theoretical and experimental verifications for the proposed method.\n", "weaknesses": "1. The paper is quite difficult to follow. I would suggest the authors use more natural language for the analysis of the proposed method.\n2. A figure for an overview description of the proposed method is lacking.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your follow-up questions and comments. Below we address each question and minor questions in a point by point fashion.\n\nWeaknesses:\n\nResponse: The mathematical derivation can develop the approach rigorously and helps demonstrate the solid foundation of PAM, but we agree that it makes our paper uneasy to comprehend. We will rewrite Sections 2 and 3 (with a notation table in the appendix to link the different symbols) and importantly, we will use more plain explanation and revise the current Figure 1 for better demonstration and make it Figure 2. Then, as suggested by reviewer, we will add in an overall figure (new Figure 1) to demonstrate the main idea of PAM. (Please see Fig. S1 in the attached pdf and we welcome more suggestions on revising this overall figure).\n\nQuestions:\n\nResponse to 1: We utilize the real-world example in [1] to illustrate why different input regions (pieces or polyhedrons) may endorse different interactions.\n\n[1] Li, Zeyu, et al. \"Interpretable click-through rate prediction through hierarchical attention.\" Proceedings of the 13th International Conference on Web Search and Data Mining. 2020.\n\nA record movie genre = horror, user age = young, time = morning has conflicting factors: the combination of the first two encourages the user to watch the movie, whereas the combination of the latter two discourages it because movie-watching usually happens at night. Therefore, rather than capturing the global interaction among these three features, in which user age oppositely impacts on people's movie-watching behavior, categorizing individuals into two local groups based on their preference for movie-watching time or genre, and fitting the interaction weights of \"movie genre $\\times$ user age\" and \"time$\\times$ user age\" separately will achieve better performance.\n\nResponse to 2: We employ the oblique tree to search for appropriate polyhedrons in PAM because it could generate polyhedrons which cannot be obtained via simply using independent hyperplanes. As the example shown in Figs. S3a-S3d in the attached pdf, the oblique tree shown in Fig. S3a could divide the input space into three polyhedrons (P1, P2 and P3 in Fig. S3b). As shown in Fig. S3c, this division can not be obtained by two independent hyperplanes. If we split the input space using the hyperplanes H1 and H2, we will get four polyhedrons (see P1, P2, P3 and P4), which is different from those in Fig. S3b. On the contrary, as proved in our paper's Base Case of Appendix B, the oblique tree can identify all possible polyhedrons created by separating hyperplanes but not vice versa. For example, polyhedrons in Fig. S3c can be generated by the oblique tree demonstrated in Fig. S3d. \n\nWith $L-1$ hyperplanes (more precisely, truncated hyperplanes with $M$ parameters for each), an oblique tree can generate $2L-2$ polyhedrons. With $L$ value functions (with M parameters for each, $L-1$ for the oblique tree and $1$ for the global value function, see Eq. 4 and Remark 1 in the main text), an oblique tree results in $(2L-1)M$ trainable parameters. If we use the same hyperplanes found by the oblique tree to split the input space, it can create $2^{L-1}$ polyhedrons. It requires totally $(2^{L-1}+L)M$ trainable parameters to train the model. In this sense, the oblique tree does reduce the trainable parameters and computation cost.  \n\nResponse to 3: We have already conducted the ablation study comparing overlapping and non-overlapping polyhedrons in our paper (refer to Fig. 4c bar for \"w/o OP\"). We observed that overlapping polyhedrons did improve performance. This might be partially due to two reasons. Firstly, a sample can belong to multiple clusters simultaneously in real life, like a red and green apple may be in red and green groups. Treating a polyhedron as a cluster of input instances, the overlapping ones lead to a fuzzy clustering framework. There is also a practical issue when a sample can only belong to one polyhedron, which results in one and only one non-zero attention score (as per Eq. 3). Model parameters are trained based on gradients of the loss function, and a zero $a_{\\Delta}$ causes zero gradients for the value function $V_{\\Delta}$ in PAM (as per Eq. 4 and the chain rule), each training iteration will update solely the value functions presented in a leaf and its ancestor nodes in the oblique tree. Secondly, identifying the exact boundary between two polyhedrons is challenging and prone to errors. With overlapping polyhedrons, the actual boundary may lie in that overlapping buffer zone to make the method more robust. \n\nResponse to 4: Thank you for pointing out the unfinished sentence after Eq. 5. That half sentence should be removed.  \n\nResponse to 5: It is a great suggestion to conduct statistical significance tests. We performed more runs (5 additional) of PAM and baseline methods so we have enough data to conduct unpaired t-tests. This test result indicates that PAM significantly outperforms baseline algorithms on all Criteo, Avazu and UK Biobank datasets ($P<0.05$, respectively, as shown in Table S2 in the attached pdf). We will include this result to Appendix.  \n\nResponse to 6: We did observe this interesting result. It did perform more stably than many of the baselines. It may be because the same PAM module (the same architecture) is stacked (see Figure 1 in Appendix G), which could reduce the variance of the model’s performance according to existing research [2].\n\n[2] Fahmy, Hesham Ahmed, et al. \"An ensemble multi-stream classifier for infant needs detection.\" Heliyon 9.4 (2023).\n\nResponse to 7:  Following the reviewer's suggestion, we now added a new comparison of training and inference time. The new results are included in  Table S1 in the attached PDF file to compare the inference time of PAM with those of baseline methods. The training time comparison can be found in Table 2 in the original paper."}, {"review_id": "YggWySxkfv", "reviewer": "Reviewer_fykg", "summary": "This paper presents a feature interaction learning module called the polyhedral attention module (PAM). \n\nThe authors show that for any fully ReLU activated DNN, any input x is transformed with respect to a polyhedron defined as the intersection of the halfspace of each layer. Because the input is divided into distinct polyhedrons, the output of a DNN can be written in terms of these polyhedron, which the authors interpret as an attention mechanism.\n\nThe authors use this insight to define PAM, which incorporates interaction effects by multiplying the distance from x to each polyhedron. Therefore giving a DNN using PAM an interpretation as a piecewise polynomial function. That is when m activated segments are multiplied, it forms an m degree monomial representing a k-way interaction between the activated segments.\n\nThe authors then provide a concept framework for interpreting the learned interaction affects from the PAM. The authors validate the PAM theoretically and empirically on the Criteo, Avazu and the UB Biobank datasets, with PAM achieving the best overall results compared to other models in binary classification for Criteo and Avazu, and brain age prediction on UK Biobank, beating the next best model’s AUC score by 2.2%.\n", "questions": "* Reviewer has no suggestions for authors", "limitations": "Author adequately address limitations of paper.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* The authors provide an intuitive generalization of the geometric interpretation of DNN into piecewise polynomial function. The theoretical analysis is sound and validated with empirical results.\n* Paper is well organized and self contained, with the theoretical concepts being clearly discussed with intuitive supporting figures\nThe authors provides a general and expressive feature interaction learning model that achieves commendable result across all datasets in classification and regression tasks.", "weaknesses": "* Reviewer notices no apparent weaknesses", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate your positive review of our work and encouragement and we are open to any additional insights you may have. "}]

Author rebuttal:
We appreciate all four reviewers for their positive and encouraging summary about our paper's strength. All have noted that our paper provides a sound, novel approach with theoretical justification and empirical verification (e.g., from reviewer 61Ki, "sharp mathematical observations", "mathematical interpretation and a sound rational connecting existing methods"; from reviewer 8xSi, "the idea is novel"; from reviewer wPpx, "provides both theoretical and experimental verification", from reviewer fykg, "thereotical concepts being clearly discussed with intuitive supporting figures", "achieve commendable results"). Three reviewers suggested more experiments to either clarify baseline methods or further validate the proposed approach. We have performed all advised experiments and explain the results in the following point-by-point responses to all weaknesses arisen from the critiques which help us improve the quality of our paper. 

Meta-review: In this paper, the authors first explain the intuition of Deep ReLU networks as cutting the input space into polyhedrons and learning affine functions within each polyhedron. Then the authors use this intuition to build the proposed PAM network module, by cutting the input space into polyhedrons with oblique tree, and then parameterising the value functions associated with the polyhedrons as well as their interactions. Both theoretical analysis on expressiveness as well as empirical evaluations on click-through-rate prediction & medical dataset are provided.

Reviewers agree that the proposed approach is novel and the justifications (theoretical and empirical) are overall sound. In author feedback the authors provided further clarifications and experiments that also help enhance the paper. I would suggest the authors to include them in the final manuscript.

After a brief reading of the paper, I feel that while I agree with all the reviewers' recommendation of acceptance, I was wondering whether the use of k-way interaction motivation may also lead to some interesting further discussions. The PAM method, while is claimed to capture all the k-way interactions, does not do so explicitly compared to e.g., constructing polynomials. In this regard, I recommend the authors to discuss the line of work on (Generalised) Neural Additive Models and clarify the interpretability properties of PAM.
Decision: Accept (poster)