Hypergraph Pattern Machine: Compositional Tokenization for Higher-Order Interactions

Kyrie Zhao, Zehong Wang, Tianyi Ma, Fang Wu, Xiangru Tang, Pietro Lio, Sheng Wang, Yanfang YearXiv 2026 · arXiv

TL;DR

The Hypergraph Pattern Machine (HGPM) shifts the hypergraph learning paradigm from standard message passing to learning the compositional patterns of node subsets. By tokenizing both observed and unobserved subsets into a target-centered inclusion DAG, HGPM successfully captures whether higher-order interactions are compositional, emergent, or inhibitory. This approach achieves state-of-the-art results on standard benchmarks and excels at complex real-world tasks like predicting multi-drug interaction side effects.

What Problem Does This Paper Address?

Hypergraphs are powerful tools for modeling higher-order, multi-entity relationships, such as multi-drug prescriptions or group recommendations. A critical but often overlooked feature of higher-order data is interaction compositionality—how a group interaction relates to its smaller subsets.

Take polypharmacy as an example. If a clinician evaluates a three-drug regimen, they need to know how the triplet behaves relative to its pairs:

  • Compositional: The triplet compounds an existing pairwise effect (the third drug is redundant).
  • Emergent: The effect only appears when all three drugs are present jointly, but not in any pair.
  • Inhibitory: A pairwise effect disappears when the third drug is added (the third drug disrupts the interaction).
Figure 1: Interaction compositionality. (a) Existing hypergraph methods propagate messages only over observed hyperedges (a.1), failing to distinguish hyperedge pairs whose compositionality structure differs (a.2). (b) Each adjacent-order subset pair falls into one of three regimes by which endpoints are observed: compositional (b.1), emergent (b.2), and inhibitory (b.3). (c) HGPM tokenizes observed (solid) and unobserved (dashed) subsets containing a target node into an inclusion DAG with COMP/EMER/INHIB-labeled transitions (c.1, color-matched to (b)); the encoder is pretrained via masked-subset reconstruction with token-wise losses on subset semantics and existence (c.2).

Traditional hypergraph neural networks (HGNNs) rely on message passing exclusively over observed hyperedges. Because they only see what already exists, they cannot model emergent or inhibitory behaviors, which are fundamentally defined by what does not exist (absent subsets). As a result, standard methods collapse these distinct structural signals into a simple binary prediction of whether a combination exists, potentially missing dangerous drug interactions.

Methods

To prevent this structural information collapse, HGPM treats both observed and absent subsets as first-class entities using a three-stage pipeline:

  1. Compositional Tokenization via an Inclusion DAG: For a given target node, HGPM extracts local subsets (up to a maximum size) and organizes them into a target-centered inclusion Directed Acyclic Graph (DAG). Edges in this DAG represent subset-to-superset transitions and are explicitly labeled as COMP, EMER, or INHIB based on the data. To keep computation tractable, tokens are sampled within a bounded per-order budget.
  2. Inclusion-Aware Self-Attention: The DAG is linearized into a sequence and fed into a Transformer. To ensure the model doesn't lose the graph topology during linearization, the authors inject learned pairwise structural attention biases (encoding direction, composition labels, and overlap metrics) directly into the self-attention layers.
  3. Compositionality-Aware Pretraining: The model is trained using a masked reconstruction objective. It randomly masks subset tokens and jointly optimizes two tasks: predicting whether a subset is observed (existence loss) and reconstructing high-level subset semantics against a target generated by an Exponential Moving Average (EMA) teacher model.

Datasets

The authors evaluated HGPM across ten distinct benchmarks:

  • Homophilic Node Classification: Citeseer, Pubmed, Cora-CA, and DBLP-CA (co-citation and co-authorship networks).
  • Heterophilic Node Classification: Congress, Senate, Walmart, and House (political collaboration and co-purchase networks).
  • Higher-Order Drug Interaction Prediction:
    • HODDI: Derived from the US FAERS database, covering 1,821 drugs and 1,710 side-effect classes.
  • JADER: Derived from the Japanese Adverse Drug Event Report database, covering 4,230 drugs and 100 side-effect classes.

Key Insights and Ideas

  • Explicit Structure Beats Learned Structure: The authors found that compositionality cannot be easily learned implicitly from raw features. Injecting COMP/EMER/INHIB transition labels directly into the input and attention mechanisms is what drives the model's performance, particularly on heterophilic data.
  • Inductive Bias Over Model Capacity: Aligning the model's architecture with the problem structure matters more than adding raw parameters. For instance, replacing the Transformer encoder with a sequential GRU baseline degraded performance because it forced an arbitrary sequential order onto a permutation-invariant set of tokens.
  • Continuous Pretraining Targets Unlock Performance: Predicting simple binary existence labels during pretraining actually led to negative transfer. The model requires rich, continuous semantic targets (provided by the EMA teacher) to successfully learn the underlying hierarchy of the hypergraph.

Key Results

  • State-of-the-Art Performance: HGPM achieved the best test accuracy on six out of eight node classification benchmarks, earning an average rank of 1.6—significantly outperforming the second-best baseline (HealHGNN at 2.9). The performance leap was most pronounced on heterophilic datasets where traditional message passing struggles.
  • Clinical Discrimination: In a real-world case study involving the FOLFOX chemotherapy regimen, HGPM successfully distinguished between two near-identical antibody drugs (panitumumab and bevacizumab). While standard similarity-based models erroneously predicted that both would cause the same side effects due to feature similarity, HGPM correctly identified that bevacizumab would inhibit the side effect, matching clinical reality.

Limitations and Future Work

Despite its strong performance, HGPM has a few notable limitations:

  1. Combinatorial Scaling: The size of the inclusion DAG grows exponentially with the size of the interaction. While bounded sampling keeps it tractable, it introduces approximations for very large groups (e.g., 10+ drug regimens).
  2. Per-Target Inference: HGPM constructs a local DAG centered around a specific target node. Performing whole-graph inference on massive networks requires repetitive per-node sampling, which can be computationally expensive.

Future Directions: The authors suggest extending HGPM to handle weighted, signed, or multi-relational hypergraphs, as well as integrating these structural representations with mechanistic pharmacokinetic simulators to better bridge data-driven predictions with clinical reality.

Summary updated

Abstract

Hypergraphs model higher-order relations that drive real-world decisions, from drug prescriptions to recommendations. A central structural signal in such data, beyond what pairwise relations can express, is interaction compositionality: whether a higher-order relation is compositional, emergent, or inhibitory with respect to its observed or unobserved sets. In polypharmacy, the regime decides whether a drug should be dropped, kept, or excluded: a compositional drug triple can be safely simplified, an emergent triple requires all drugs jointly, and an inhibitory triple flags a drug that disrupts an existing interaction. However, existing hypergraph learning methods, which merely propagate messages over observed hyperedges, leave this compositional signal unmodeled, allowing dangerous drug combinations to slip through and be misclassified. To this end, we propose the Hypergraph Pattern Machine (HGPM), shifting the paradigm from message passing to learning the compositional pattern of subsets. It tokenizes compositional subsets, organizes them in an inclusion DAG, and trains an inclusion-aware Transformer under masked reconstruction. On ten hypergraph benchmarks, HGPM matches or exceeds state-of-the-art methods. Notably, in a real adverse-event prediction case, HGPM correctly identifies the drug addition that inhibits the side effect among feature-identical candidates, a discrimination existing methods cannot make. The code and data are in https://github.com/KryieZhao/HGPM.git.
BibTeX
@misc{zhao2026hypergraph,
  author = {Kyrie Zhao and Zehong Wang and Tianyi Ma and Fang Wu and Xiangru Tang and Pietro Lio and Sheng Wang and Yanfang Ye},
  title = {{Hypergraph Pattern Machine: Compositional Tokenization for Higher-Order Interactions}},
  year = {2026},
  eprint = {2605.16527},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2605.16527},
}

Loading related content...

Figure