Polyhedron Attention Module: Learning Adaptive-order Interactions

Tan Zhu, Fei Dou, Xinyu Wang, Jin Lu, Jinbo Bi

In multivariate predictive modeling, understanding how features interact—such as how the effect of "age" on a target variable changes based on "gender"—is crucial for both accuracy and interpretability. However, standard deep learning models face a significant trade-off when attempting to capture these dynamics.

Standard ReLU-activated networks are essentially piecewise linear; while powerful, they do not explicitly model high-order interactions within those linear "pieces." Conversely, polynomial models explicitly include interaction terms (like $x_1 \cdot x_2$), but they suffer from combinatorial explosion as the number of features and the order of interactions increase. Existing hybrid methods often apply fixed-order interactions (e.g., strictly 2-way or 3-way) across the entire feature space, failing to adapt to local data structures where some regions might require higher-order interactions than others.

To bridge this gap, researchers have introduced the Polyhedron Attention Module (PAM), a novel architecture that moves beyond piecewise linear limitations to create a flexible, piecewise polynomial model capable of learning adaptive-order interactions.

Introducing the Polyhedron Attention Module (PAM)

The core innovation of PAM is its geometric approach to feature interaction, replacing standard black-box layers with a structured, interpretable mechanism.

PAM Architecture Overview

PAM operates through several key mechanisms:

  • Space Partitioning via Oblique Trees: PAM uses an "oblique tree" structure to divide the input space into overlapping polyhedrons. Unlike standard decision trees that split on a single feature, oblique trees split the space using hyperplanes (linear combinations of features).
  • Adaptive-Order Attention: For each polyhedron, PAM calculates an attention score derived by multiplying the distances from an input point to the hyperplanes defining the polyhedron's boundaries.
  • If a point is far from all boundaries, it receives a "0-order" (constant) interaction.
  • If it is close to one boundary, it receives a "1st-order" (linear) effect.
  • If it sits near the intersection of multiple boundaries, the multiplication of those distance terms naturally creates high-order polynomial interactions.
  • Soft Splitting: To prevent abrupt jumps in the model's output and to improve training stability, PAM introduces an overlapping buffer (a "soft" partition) at the boundaries.
  • Built-in Interpretability: The authors provide a specific algorithm (Algorithm 1) to decompose the model's output into individual $k$-way interaction effects. This allows researchers to see exactly which feature combinations drive a prediction for any specific instance.

Conceptually, the paper offers a fascinating insight: standard ReLU networks can be reinterpreted as a restricted form of attention based only on the last layer's hyperplane. PAM generalizes this by allowing multiple boundary hyperplanes to contribute to the attention calculation, naturally learning that interactions are "local" phenomena.

Experimental Validation and Insights

The researchers evaluated PAM on three massive, high-dimensional datasets: two benchmark click-through rate (CTR) datasets (Criteo with 33M samples/2.1M features, and Avazu with 28.3M samples/1.5M features) and a medical database (UK Biobank, ~40k samples) where the task was to predict "brain-age" using grey matter volumes from 139 distinct brain regions.

Key Results: * State-of-the-Art Performance: PAM achieved the highest AUC on both Criteo and Avazu, and the highest $R^2$ on the UK Biobank dataset. In CTR prediction, where a 1‰ (0.001) improvement is considered highly significant, PAM outperformed the second-best models by 1.4‰ on Criteo and 0.6‰ on Avazu. * Medical Discovery: On the UK Biobank data, PAM successfully identified meaningful biological interactions without sacrificing predictive power. For example, it found that the interaction between the left and right frontal poles is a significant predictor of brain aging—a finding supported by existing neuroscience literature. * Parameter Efficiency: The authors mathematically proved a universal approximation theorem showing that PAM-augmented networks require significantly fewer parameters than pure ReLU networks to achieve the same level of approximation error for smooth functions. * Ablation Success: Removing the "overlapping" property or the "adaptive-order" capability led to a noticeable drop in performance, validating the core architectural choices.

Limitations and Future Directions

While PAM demonstrates strong results, the authors note a few areas for future growth. Currently, the oblique tree structure is fixed or grows to a predetermined depth; dynamic pruning during training could further regularize the model and improve efficiency. Additionally, the polyhedrons are currently defined by linear hyperplanes. Future work could explore non-linear boundaries to capture even more complex spatial partitions. Finally, while parameter-efficient, calculating distances to multiple hyperplanes per polyhedron adds some computational overhead during the forward pass compared to simple matrix multiplication.

Summary updated

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.
BibTeX
@inproceedings{zhu2023polyhedron,
  author = {Tan Zhu and Fei Dou and Xinyu Wang and Jin Lu and Jinbo Bi},
  title = {{Polyhedron Attention Module: Learning Adaptive-order Interactions}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=6JrckqCxtl},
}
Figure