Bipartite learning is a machine learning task aimed at predicting interactions among pairs of instances. It has been applied to a variety of domains, including drug-target interaction, RNA-disease association and regulatory network inference. Despite 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 to significantly reduce training time without impacting 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 against the current state-of-the-art. We achieve up to 30-fold improvement in training times against the state-of-the-art biclustering forests, while showing competitive or superior performance in most evaluation settings, especially 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.