Oxytrees: Model Trees for Bipartite Learning

AI summary

Overview

• Research area: Machine learning — specifically bipartite learning (also called interaction prediction, dyadic prediction, or network inference), with decision-tree/biclustering-forest methods and bioinformatics benchmarks.
• Technical level: Advanced. The paper assumes familiarity with decision-tree impurity functions, Kronecker product kernels, regularized least squares, positive-unlabeled learning, and asymptotic complexity notation.
• Scope: The paper proposes Oxytrees, an ensemble of proxy-based biclustering model trees that compresses the interaction matrix into row- and column-wise proxy matrices, uses RLS-Kron linear models in leaf nodes, and introduces a batched leaf-assignment routine, then benchmarks it against prior bipartite learning methods on 15 datasets under several train/test splits and positives-masking percentages.

What This Paper Is About

Bipartite learning means predicting whether two objects of different types interact — for example, a drug and a protein, or a user and an item. Existing methods tend to be built for one specific application (such as a single drug-target task), or they scale poorly, or they cannot make predictions for instances never seen during training. The paper's goal is a general-purpose tree-based method that is much faster to train and predict than the current state-of-the-art biclustering forest (BICTR) while remaining competitive or better in predictive accuracy, especially in the inductive setting where both sides of a test pair are new.

Key Contributions

1. Proxy-based training for biclustering trees. Oxytrees aggregate the impurity of one dimension of the interaction matrix Y into small "proxy" matrices (row-wise and column-wise), which are then reused when evaluating many split candidates. This avoids re-aggregating across the full matrix for every candidate split, cutting training time.
2. A new batched leaf-assignment algorithm. Instead of traversing the tree once per dyad, Oxytrees pass the entire test feature matrices X1 and X2 down the tree, partitioning only the relevant dimension at each split and predicting all dyads in X1,leaf × X2,leaf at the leaf.
3. Model trees with RLS-Kron leaf models. Leaves return a regularized least squares regression using the Kronecker product kernel rather than a constant (mean label). This lets instance pairs in the same leaf receive different predictions, produces shallower trees, and extends predictions beyond dense regions of the training data.
4. An extensive comparative study plus a reproducible toolkit. Oxytrees are compared against prominent methods on 15 datasets under transductive, semi-inductive and inductive splits and four positives-masking percentages (0%, 25%, 50%, 75%), with all implementations, preprocessed datasets and evaluation measures released through a Scikit-Learn-based Python API.

Main Findings

• Training speed: Oxytrees were reported in the empirical complexity experiment as 35.49 ± 0.75 times faster to train than BICTR (p < 4·10⁻⁵, Wald, in Section 6.3; the conclusion reports p < 4·10⁻⁸), and the abstract characterizes the improvement as up to 30-fold over state-of-the-art biclustering forests.
• Inference speed: Oxytrees predicted 9.98 ± 0.84 times faster than BICTR (p < 4·10⁻⁵, Wald).
• Theoretical complexity: BuildOxytree ∈ Θ(n₁² (log(n₁) + m)) versus BuildPBCT ∈ Θ(m·n₁² log(n₁)), a reduction of a factor of log(n₁) when m ∈ Ω(log(n₁)) and a factor of m otherwise. Batched inference is Θ(n_test²) when n_test ∈ Ω(n_train), and Θ(n_test² log(n_train)) otherwise (BICTR is Θ(n_test² log(n_train)) in all cases).
• Predictive performance (inductive, 0% PMP): Oxytrees had the best average ranking for all but one of the inductive settings analyzed, with no statistically significant differences versus the state-of-the-art. Oxytrees performed consistently better than RLS-Kron alone.
• Semi-inductive setting: Oxytrees, BICTR and RLS-Kron were the top performers, with no statistically significant differences between their scores.
• Transductive setting: NRLMF, BICTR and RLS-Kron had the best overall scores. Scores in the inductive and semi-inductive settings were considerably lower than in the transductive setting.
• NRLMF does not transfer to inductive use: NRLMF was among the worst performers in the inductive setting despite its strong transductive results, which the authors say motivates the earlier NRLMF + biclustering forest combination (BICTR).
• WkNNIR underperformed BICTR on the 15 datasets used here, contrary to what was previously observed for drug-target interaction prediction.
• Robustness to missing positives: All models degraded as the positives-masking percentage increased. BLMNII and RLS-avg showed the smallest performance drop, suggesting simple local linear models are robust to missing labels. MLP results were inconsistent.
• Ablation — leaf models matter: Removing the leaf model (using the average label instead) significantly degraded performance, even when NRLMF-based interaction matrix reconstruction (YR) was applied. Using YR while enforcing minimum leaf dimensions of 5 by 5 was the worst overall strategy.
• Leaf size dependence: Forests without leaf models lost performance as minimum leaf dimensions grew, especially beyond 20 by 20; Oxytrees with RLS-Kron leaf models stayed stable, with a slight score increase up to 20 by 20 leaves.
• Tree count: Oxytrees required 42% ± 3% of the trees that BICTR needed to reach 98% of the score obtained with 200 trees (p < 2·10⁻⁴, Wilcoxon). The conclusion frames this as requiring up to 50% fewer trees.

Methodology in Plain English

The authors treat the data as two feature matrices (one per dimension) plus an interaction matrix holding known outcomes. They first prove that their impurity measure — the variance of the vectorized interaction matrix — can be decomposed into per-element functions, which is what makes the proxy trick possible. BICTR's impurity (averaging variances over rows or columns) does not satisfy this property, which is why BICTR cannot use the optimization.

Then, instead of recomputing impurity over the whole interaction matrix for every candidate split, Oxytrees precompute one summary matrix per dimension once per node. Horizontal split candidates are scored from the row proxy, vertical candidates from the column proxy. To add representational power, leaves hold a kernel ridge regression model (RLS-Kron) rather than a constant, so large leaves can still produce varied predictions. For prediction, the whole batch of test instances is pushed through the tree so each split rule is evaluated only once per instance instead of once per dyad.

For evaluation, they split each dataset instance-wise in both dimensions and then dyad-wise within the training portion, producing four test sets: transductive (LD → TD), row-inductive (TL), column-inductive (LT), and inductive (TT). Cross-validation uses k × k folds with label stratification, and 25%, 50% or 75% of positive annotations are masked to simulate unlabeled positives. Metrics are AUPRC and AUROC, with Friedman and Nemenyi post-hoc tests for statistical comparison. Ensembling follows BICTR by using extremely randomized Oxytrees, with nested 2 × 2 cross-validation and AUPRC for hyperparameter selection.

Why This Matters

• Research impact: The paper provides the authors' claim of the most extensive comparative study to date in inductive bipartite learning, covering 15 datasets — including five (TE-piRNA, LncRNA-miRNA, lncRNA-disease, lncRNA-cancer, miRNA-disease) that they say have never previously been used as benchmarks for interaction prediction in general. It also shows a structural reason why certain impurity functions permit the proxy speed-up and others do not.
• Reproducibility: All implementations, preprocessed datasets and evaluation measures are released through a Scikit-Learn-style Python API, lowering the barrier for new groups to enter the field.

Real-world applications named or implied by the paper:

• Drug-target interaction prediction, including drug-nuclear receptor, drug-GPCR, drug-ion channel, drug-enzyme, inhibitor-kinase (Davis, KIBA) settings.
• RNA-disease associations, such as miRNA-disease and lncRNA-disease link prediction.
• Regulatory network inference, including gene–transcription-factor networks (SRN, ERN) and lncRNA-protein interactions (NPInter).
• Recommender systems, framed as a user-item interaction problem where the paper's focus on inductive performance corresponds directly to the cold-start problem.

Industry relevance: The 35.49× training and 9.98× inference speed-ups, combined with a lower required tree count, make ensembles of these trees more practical on larger interaction matrices than BICTR. Because the method is explained as applicable to any interaction problem and produces interpretable trees, it is relevant to settings beyond biology where interpretability and inductive generalization matter.

Future Directions

• Regression for bipartite learning. The authors explicitly want to explore Oxytrees for regressive tasks such as drug-target affinity prediction, since the current work targets binary classification only.
• Comparison with deep learning on raw data. They propose benchmarking against deep methods that operate directly on unstructured inputs such as protein sequences and molecular structures.
• Reducing the remaining gap in hard settings. Scores in the inductive and semi-inductive settings were considerably lower than in the transductive setting, indicating that generalizing to new instances on both sides of a pair remains an open challenge.
• Improving robustness to missing positives. Performances dropped for all models as the positives-masking percentage increased, and the authors note the local linear models (BLMNII, RLS-avg) were the most robust, while MLP behaved inconsistently — leaving room to investigate why.

Target Audience

Machine learning researchers working on interaction prediction, dyadic prediction, link prediction or network inference will get the most from this paper, particularly those interested in tree-based and biclustering-forest methods and in complexity-aware algorithm design. Bioinformatics and cheminformatics practitioners who need fast, inductive, interpretable models for drug-target, RNA-disease or regulatory network data are the primary applied audience. Practitioners building cold-start-resistant recommender systems and engineers looking for a Scikit-Learn-compatible bipartite learning toolkit will also find it relevant. Beginners will likely find the Kronecker kernel leaf model, the impurity decomposition requirements and the asymptotic arguments demanding without background in kernel methods and algorithm analysis.

Authors’ abstract

Bipartite learning is a machine learning task that aims to predict interactions between pairs of instances. It has been applied to various domains, including drug-target interactions, RNA-disease associations, and regulatory network inference. Despite being widely investigated, current methods still present drawbacks, as they are often designed for a specific application and thus do not generalize to other problems or present scalability issues. To address these challenges, we propose Oxytrees: proxy-based biclustering model trees. Oxytrees compress the interaction matrix into row- and column-wise proxy matrices, significantly reducing training time without compromising predictive performance. We also propose a new leaf-assignment algorithm that significantly reduces the time taken for prediction. Finally, Oxytrees employ linear models using the Kronecker product kernel in their leaves, resulting in shallower trees and thus even faster training. Using 15 datasets, we compared the predictive performance of ensembles of Oxytrees with that of the current state-of-the-art. We achieved up to 30-fold improvement in training times compared to state-of-the-art biclustering forests, while demonstrating competitive or superior performance in most evaluation settings, particularly in the inductive setting. Finally, we provide an intuitive Python API to access all datasets, methods and evaluation measures used in this work, thus enabling reproducible research in this field.