Autoencoding Random Forests
Authors: Binh Duc Vu
Jan Kapar
Marvin N. Wright
David Watson
Venue: NeurIPS 2025 poster ()
Keywords: Random Forests
Compression
Kernel Methods
Constrained Optimization
Nearest Neighbors
Primary area: general_machine_learning
TL;DR: We propose a random forest autoencoder with applications in tabular, image and genomic data.

Abstract: We propose a principled method for autoencoding with random forests. Our strategy builds on foundational results from nonparametric statistics and spectral graph theory to learn a low-dimensional embedding of the model that optimally represents relationships in the data. 
We provide exact and approximate solutions to the decoding problem via constrained optimization, split relabeling, and nearest neighbors regression. These methods effectively invert the compression pipeline, establishing a map from the embedding space back to the input space using splits learned by the ensemble's constituent trees. The resulting decoders are universally consistent under common regularity assumptions. The procedure works with supervised or unsupervised models, providing a window into conditional or joint distributions. We demonstrate various applications of this autoencoder, including powerful new tools for visualization, compression, clustering, and denoising. Experiments illustrate the ease and utility of our method in a wide range of settings, including tabular, image, and genomic data.

Autoencoding Random Forests
Binh Duc Vu
Jan Kapar kapar@leeiniiz-bips.dd
binh. wwwkcl.ac.cc... uk
Marvin N. Wright wright@leibniz-biie
David S. Watson'
david. www.wwwwwwl............... ac.uk
Kinggs College London
Leibniz Institute for Prevention Research and Epidemiology BIPS University of Bremen
Abstract
We propose principled method for autoencoding with random forests. Our strat- egy builds on foundational results from nonparametric statistics and spectral graph theory to learn low-dimensional embedding of the model that optimally represents relationships in the data. We provide exact and approximate solutions to the decod- ing problem via constrained optimization, split relabeling, and nearest neighbors regression. These methods effectively invert the compression pipeline, establishing map from the embedding space back to the input space using splits learned by the ensemble's 's constituent trees. The resulting decoders are universally consistent under common regularity assumptions. The procedure works with supervised unsupervised models, providing window into conditional or joint distributions. We demonstrate various applications of this autoencoder, including powerful new tools for visualization, compression, clustering, and denoising. Experiments il- lustrate the ease and utility of our method in a wide range of settings, including tabular, image, and genomic data.
Introduction
81 In supervised applications, it can simplify regression or classification objectives, helping users better understand the internal operations of large, complicated models 42 [04] In reinforcement learning, embeddings help agents navigate complex environments, imposing useful structure on a potentially high-dimensional state space 2 63) In unsupervised settings, latent projections can be used for data compression [69], visualization 993 clustering (97), and generative modeling [92].
Engineering compact, informative representations is central to many learning tasks (58 96
The current state of the art in representation learning is dominated by deep neural networks (DNNs). Indeed, tendency of these algorithms learn rich embeddings widely cited as key component of their success [4], with some even arguing that large language models are essentially compression engines 29 It is less obvious how to infer latent factors from tree-based ensembles such as random forests (RFs) [77. popular and flexible function class widely used in areas like bioinformatics (23 and econometrics [3. DNNs are known to struggle in tabular settings with mixed continuous and categorical covariates, where tree-based ensembles typically match surpass their performance Though several authors have proposed methods for computing nonlinear embeddings with RFs (see Sect. 2 these approaches tend to be heuristic in nature. Moreover, the task of decoding latent vectors to recover input data in these pipelines remains unresolved.
86 48
Equua contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

We propose novel, principled method for autoencoding with RFs. Our primary contributions are: (1) We prove several important properties of the adaptive RF kernel, including that asymptotically universal. (2) These results motivate the use of diffusion maps to perform nonlinear dimensionality reduction and manifold learning with RFs. Resulting embeddings can be used for various downstream tasks. (3) We introduce and study multiple methods for decoding spectral embeddings back into the original input space, including exact and approximate solutions based on constrained optimiza- tion, split relabeling, and nearest neighbors regression. (4) We apply these methods in series of experiments and benchmark against a wide array of neural and tree-based alternatives. Our results demonstrate that the RF autoencoder is competitive with the state of the art across range of tasks including data visualization, compression, clustering, and denoising.
The remainder of this paper is structured as follows. After review of background material and related work (Sect. 2). we propose and study methods for encoding (Sect. 33 and decoding (Sect. 4 data with RFs. Performance is illustrated in series of experiments (Sect. 5). Following brief
discussion (Sect. we conclude with directions for future work (Sect. 7)
Background
Our starting point is the well established connection between RFs and kernel methods [6 28 83
The basic insight is that classification and regression trees (CART) [88, which serve as basis functions for many popular ensemble methods, a kind of adaptive nearest neighbors algorithm [66]. At the root of the tree, all samples are connected. Each split severs the link between one subset of the data and another (i.e., samples routed to left vs. right child nodes), resulting in a gradually sparser graph as depth increases. At completion, a sample's "neighbors" are just those datapoints that are routed to the same Icaf. Given some feature space X C Rdx,, the implicit kernel of tree 6, ((()) X' x X + {0, 1}. is an indicator function that evaluates to for all and only neighboring sample pairs This base kernel can be used to define different ensemble kernels. For instance, taking an average over B > 1 trees, get kernel with simple interpretation the proportion of trees in which two samples Ex=1 k((h) (x, x'). We call this the Scornet kernel after one of its noted who showed that ks is provably close in expectation to the RF similarity function:
colocate: k-5 [x, x') B-
proponents 83
A-CO) (x,x')
k
(x, =
(x,x:) x;
where E [n]] := {l...., ......n) n indexes the training samples. This represents the average of normalized tree kernels, and fully encodes the information learned by the RF fn via the identity:
fn(x) = Σ RF (x, x;) ys-
(2)
which holds uniformly for all x E X. Though S.S is sometimes referred to as "the random forest kernel" [28] 76), this nomenclature misleading- k.RF satisfies Eq. 2 Non-adaptive variants
of k.R. have been previously studied [109], but we derive several novel properties of this similarity function without any such constraints.
Several nonlinear dimensionality reduction techniques are based on kernels, most notably kernel principal component analysis (KPCA) 80 We focus particular on diffusion maps 25 26 which
can be interpreted as form of KPCA [22] Bengio et al. [10] establish deep links between these algorithms and several related projection methods, demonstrating how to embed test data in all
settings via the Nyström formula, a strategy we adopt below. Inverting any KPCA algorithm to map latent vectors to the input space is nontrivial task that must be tailored to each specific kernel. For an example with Gaussian kernels, see (72).
perform multi- Previous authors have explored feature engineering with RFs. Shi and Horvath 85
dimensional scaling on a dissimilarity matrix extracted from supervised and unsupervised forests. However, they do not explore the connections between this approach and kernel methods, nor do they
'This ignores certain subtleties that arise when trees are grown on bootstrap samples, in which case k()) may occasionally evaluate to larger integers. For present purposes, we presume that trees are grown on data subsamples; see Appx.
2

---

X X2 Xx
(a)
(c)
(e)
4.6
Red
2.3
VAVT
(b)
(d)
Figure 1: Visual summary of the encoding pipeline. (a) Input data can be mix of continuous, ordinal, and/or categorical variables. (b) A RF (supervised unsupervised) is trained the data. (c) A kernel matrix K E [o, 1|mxn x is extracted from the ensemble. (d) K is decomposed into its eigenvectors and eigenvalues, as originally proposed by David Hilbert (pictured).
(e) Data is projected onto the top dz < principal components of the diffusion map, resulting in a new embedding Z E Rnxdz,
propose any strategy for decoding latent representations. More heuristic approaches involve running PCA on weighted matrix of all forest nodes (not just leaves), method that works well in some experiments but comes with no formal guarantees 77
Several generative algorithms based RFs have been proposed, building the probabilistic circuit literature [27 199. These do not involve any explicit encoding step, although the models they train could be passed through our pipeline to extract latent embeddings (see Sect. (5). Existing methods for sum num-product network encoding could in principle be applied to an RF following compilation into
corresponding circuit (95]. However, these can often increase rather than decrease dimensionality, and do not come with any associated decoding procedure.
Recent work has explored autoencoding for tree- and forest-based models. Carreira-Perpiiie and Gazizov [20] introduce a sparse oblique tree where each node performs a local linear reconstruction via PCA, yielding tree-structured autoencoder without of kernels ensembles. Aumon al. 4 propose an RF-informed neural autoencoder, which extracts forest-induced sample similarities to inject supervised signals into network embeddings for data visualization. By contrast, we learn latent representations directly from the RF and implement explicit decoding rules for both supervised and unsupervised settings without an auxiliary model.
Perhaps the most similar method to ours, in motivation if not in execution, is Feng and Zhou's 's encoder forest (eForest) [34.. This algorithm maps each point hyperrectangle defined by the intersection of all leaves to which the sample is routed. Decoding is then achieved by taking some representative value for each feature in the subregion (e.g., the median). Notably, this approach does not include any dimensionality reduction. On the contrary, the embedding space requires minima and maxima for all input variables, resulting in representation with double the number of features the inputs. Working from the conjecture that optimal prediction is equivalent to optimal compression [78 58 we aim to represent the information learned by the RF in relatively few dimensions.
3 Encoding
As preliminary motivation, we prove that the RF similarity function is proper kernel with several notable properties. The following definitions are standard in the literature. Let A' be compact metric space, and let C(X) be the set of all real-valued continuous functions on X.
Definition 3.1 (Positive semidefiiite. A symmetric function le X' X +> IR is positive semidefinite (PSD) if, for all xI....,X,
X, E X', n E N, and c; Cj E IR, we have: Ei, ej k(x,, x,) 2 0.
The Arone-Aronszajn theorem 1 states that PSD kernels admit unique reproducing kernel Hilbert space (RKHS) [12, providing a rich mathematical language for analyzing their behavior.
Definition 3.2 (Universal). We say that the RKHS H is universal if the associated kernel & is dense in C(X) with respect to the uniform norm. That is, for any f E C(X) and > there exists some H such that I| flloo e.
3

---

Several variants of universality exist with slightly different conditions on X' 87. Examples of universal kemells include the Gaussian and Laplace kernels 88
Definition 3.3 (Characteristic). The bounded measurable kernel k is characteristic if the function -++ Ix k x) du((x) is injective, where fs is Borel probability measure on A.
Characteristic kernels are especially useful for statistical testing, and have inspired flexible nonpara- metric methods for evaluating marginal and conditional independence [46] [39]. For instance, Gretton al. [47] show that, when using a characteristic kernel the maximum mean discrepancy (MMD) between two measures μ, on X' is zero iff ş = V. The MMD is defined as:
MMD? (1,, k) == Ex.x'~ - [K(x, x')l 2Ex (k(x, + Ey (ky, y')-
With these definitions in place, we state our first result (all proofs in Appx. A
Theorem 3.4 (RF kernel properties). Assume standard RF regularity conditions (see Appx. A Then: (a) For all n. E N, the function ki is PSD and the kernel matrix K E [0, 1jmx is doubly stochastic. (b) Let {fa] be sequence of RFs. Then the associated RKHS sequence {Ha} is asymptotically universal. That is, for any f E C(2) and 6 > O, we have:
lim P(IIf" fallo 26)= =0
12-000
(c) The RKHS sequence {H.) is asymptotically characteristic. That is, for any >> 0, the Borel measures μ. v are equal if and only if:
lim P(MMD( 1/; k 2) =
) =0
1-000
The literature on kernel methods is largely focused on fixed kernels such the radial basis function (RBF), Among adaptive partitioning alternatives, the Scornet kernel been studied in some detail 28 X 76. as has the Mondrian kernel 664 21 Zhou and Hooker [T09] show that a non- adaptive variant of kRF is PSD and bounded on the unit interval (a strictly weaker property than double stochasticity). To the best of our knowledge, we are the first to establish items (b) and (c) for the RF kernel. Thm. 3.4 confirms that kRP is flexible, informative, and generally "well-behaved" in ways that will prove helpful for autoencoding.
Spectral Graph Theory A key insight from spectral graph theory is that for any PSD kernel k, there exists an encoding X' + Z for any embedding dimension dz < n that optimally represents the data, in a sense to be made precise below. This motivates our use of diffusion maps 126 25), which are closely related to Laplacian eigenmaps [ 19, an essential preprocessing step in popular spectral clustering algorithms [75 97 [59.. These methods typically used with fixed kernels such as the RBF; by contrast, we use the adaptive RF kernel, which is better suited to mixed tabular data.
The procedure begins with a dataset of paired feature vectors x E X C Rdx and outcomes E y C R sampled from the joint distribution Pxy A RF of trees fu trained on (xi, Uo } Using Eq. I we construct the kernel matrix K [0. 1] with entries k; k-R X.). This defines weighted, undirected graph Gn over the training data. As K is doubly stochastic, it can be interpreted as encoding the transitions of a Markov process. Spectral analysis produces the decomposition KV = VA, where V E R'x= denotes the eigenvector matrix with corresponding eigenvalues E 00, 1]", and A diag(A) Indexing from zero, it can be shown that Vú is constant, with ... > A,, Following standard convention, we drop this uninformative dimension and take the leading eigenvectors from V1.
1 1= Ao 2
The elements of this decomposition have several notable properties For instance, the resulting eigenvectors uniquely solve the constrained optimization problem:
min VERuxdZ
Key
||, v5llz s.t. V V
EEven in the unsupervised case, typically train the ensemble with a regression or classification objective.
The trick is construct some Y that encourages the model make splits that informative w.r.t. Px (e.g..
85 99 ). For fully random partitions. Y can be any variable that is independent of features (e.g..
Observe that the eigenvectors of K are identical to those of the graph Laplacian L = I K. which has jth
eigenvalue 73 1 Ay. For more on the links between diffusion and Laplacian eigenmaps, see 62 52

---

for all dg E [n], thereby minimizing Dirichlet energy and producing the smoothest possible represen- tation of the data that preserves local relationships in the graph. These eigenvectors also simplify number of otherwise intractable graph partition problems, providing smooth approximations that motivate spectral clustering approaches 84 997- If we think of 9n as a random sample from Riemannian manifold M, then scaling each Vj by /nd; produces an approximation of the jth eigen- function the Laplace-Beltee -alaarem operator at time which describes how heat (or other quantities) diffuse across .M [8] [O]. Euclidean distance in the resulting space matches diffusion distances across Gn. providing a probabilistically meaningful embedding geometry [26]
The diffusion map Z = VV represents the long- run connectivity structure of the graph after t time steps of a Markov process. Test data can be projected into spectral space via the Nyström formula [TT i.. Zo = K2 ZA for some Kg E [0, _]mxx, where rows index test points and columns index training points. For more details on diffusion and spectral graph theory, see 24 74 97
4
Decoding
Our next task is to solve the inverse problem of decoding vectors from the spectral embedding space back into the original feature space-i.e., learning the function h 2 X such that x s ((()))). We propose several solutions, including methods based on constrained optimization, split relabeling. and k-nearest neighbors. To study the properties of these different methods, we introduce the notion of a universally consistent decoder.
Definition 4.1 (Universally consistent decoder). Let X + Z be a lossless encoder. Then say that the sequence of decoders {hn 2 + X3 is universally consistent if, for all distributions Px, any Px, and all >> 0, have:
lim (Inx-In(9"(x)) (at)llx22) 20)=
The first two methods- constrained optimization and split relabeling- are designed to infer likely leaf assignments for latent vectors If these correctly determined, then the intersection of assigned leaves defines a bounding box that contains the corresponding input vector x. Our estimate & is then sampled uniformly from this subspace, which is generally small for sufficiently large and/or deep forests. As a motivation for this approach, we show that a leaf assignment oracle would constitute a universally consistent decoder.
Let d be the number of leaves in tree b, and d4 = EB de the number of leaves in the forest f. The function Ty X ト {0, 1 maps each sample x to its corresponding leaves in f. It is composed by concatenating the outputs of B unique functions ; : X' + {0, 1] each satisfying for all x E X. Let thy Z + {0, 1jde be similar leaf assignment function, but for latent vectors. Then for a fixed forest f and encoder y, the leaf assignment oracle V7.g satisfies y (x) = ,. (g(x)), for all x E X.
|| (6) (x)]l
Lid. Theorem 4.2 (Oracle consistency). Let fu be a RF trained on (x:, Vi.. ~ be a decoder that (i) maps latent vectors to leaves fn via the oracle 1/ In-gi then (ii) reconstructs data by sampling uniformly from the intersection of assigned leaves for each sample. Then, under the assumptions of Thm. 3.4 the sequence (1r) is universally consistent.
PXY. Let hi 2 X
4.1 Constrained Optimization
Our basic strategy for this family of decoders is to estimate a kernel matrix from set of embeddings, then use this matrix to infer leaf assignments. Let E {1/ 1]] be vector inverse leaf sample
sizes, composed of tree-wiss wise vectors (b)) with entries 8, = = 1 (b) (x₃). Then the canonical feature map for the RF kernel can be written Φ(x) = (x), () (x)]. with tree-wise feature
maps (b() (x) x (b) (x) @ Vs(t), where denotes the Hadamard (element-wise) product. Now RF kernel evaluations can be calculated via the scaled inner product k (x, x') = B ())() o(x'),
which is equivalent Eq.
Say we have n training samples used to the forest fn. and m latent vectors to decode from an embedding space of dimension dz < n. We will refer to these samples a test set, since they may
5

---

not correspond to any training samples. We are provided a matrix of embeddings Zo E Rmxdz from which we estimate the corresponding kernel matrix K, = ZoAZi, where 2 denotes the Moore-Penrose pseudo-inverse of Z.
Now we must identify the most likely leaf assignments for each of our m (unseen) test samples Xu E Rmxxx given their latent representation Zy. Call this target matrix & E {0, 1 To estimate it, we start with the binary matrix of leaf assignments for training samples II {0, 1)mxde. Exploiting the inner product definition of a kernel, observe that our original (training) adjacency matrix K satisfies BK Φ IISII where T [0, 1]mxds is the RKHS representation of X, and S diag(s). We partition [d+] into B subsets ( that index the leaves belonging to tree b.
Recall that each tree partitions the feature space X' into (,))) hyperrectangular subregions x; C X,
one for each leaf E [L( Let R²!") {xx()) ...... 21,0) denote the region to which sample is routed in tree b. Then leaf assignments for test samples can be calculated by solving the following
integer linear program (ILP):
min the [=
[BKJ IIS 111
S.L. bi
Σ Vie 1, vi: n (EL
R BEIB]
b 7 U.
(3)
The objective an entry-wise L1 norm that effectively treats the resulting matrix as stacked vector. The first constraint guarantees that test samples are one-hot encoded on per-tree basis. The second constraint states that the intersection of all assigned hyperrectangles is nonempty. We call these the one-hot and overlap constraints, respectively. Together they ensure consistent leaf assignments both within and between trees. The ILP approach comes with the following guarantee.
Theorem 4.3 (Uniqueness). Assume we have a lossless encoder g" : X + such that the estimated
Kg coincides with the ground truth Kg. Then, under the assumptions of Thm. 3.4 as n + cc, with high probability, the ILP of Eq. 3 is uniquely solved by the true leaf assignments V
Together with Thm. 4.2 Thm. 4.3 implies that the ILP approach will converge on an exact recon- struction of the data under ideal conditions. While this may be encouraging, there are two major obstacles in practice. First, this solution scales poorly with m and dg. Despite the prevalence of highly optimized solvers, ILPs are No-complete and therefore infeasible for large problems. Second, even with an oracle for solving this program, results may be misleading when using noisy estimates
of Kg Since this will almost always be the case for dz < na-an inequality that is almost certain to hold in most real-world settings- the guarantees of Thm. 4.3 will rarely apply. We describe a convex
relaxation in Appx. C via the exclusive lasso [108]]] 19 approach that is more tractable than the ILP but still turns each decoding instance into a nontrivial optimization problem.
4.2 Split Relabeling
Another strategy for computing leaf assignments front-loads the computational burden so that down- stream execution requires just a single pass through a pretrained model, as with neural autoencoders. We do this by exploiting the tree structure itself, relabeling the splits in the forest so that they apply directly in embedding space.
The procedure works as follows. Recall that each split is literal of the form X, be x for some j E [dx].2 x E Xy, where ix E {<,=} (the former for continuous, the latter for categorical data). At each node, we create synthetic dataset X by drawing uniformly from the corresponding region. We embed these points with diffusion map to create the corresponding matrix 2. Samples are labeled with a binary outcome variable Y indicating whether they are sent to left or right child nodes. Next, we scarch for the axis-aligned split in the embedding space that best predicts Y. The ideal solution satisfies Zi < z + X, X x, for some E [dz]. z E Zg. Perfect splits may not be possible, but optimal solutions can be estimated with CART. Once all splits have been relabeled, the result is tree with the exact same structure as the original but a new semantics, effectively mapping a recursive partition of the input space onto a recursive partition of the embedding space.
This strategy may fare poorly if no axis-aligned split in approximates the target split in X. In principle, we could use any binary decision procedure to route samples at internal nodes. For example, using logistic regression, we could create a more complex partition of 2 into convex polytopes. Of course, this increase in expressive flexibility comes cost in space and time complexity. The use

---

Pes dogih
Dit dogtt
200 0A00
Fos degii -8
Label
Figure 2: Diffusion maps visualize RF training. Using a subsample of the MNIST dataset, we find that digits become more distinct in the embedding space as tree depth increases.
of synthetic data allows us to choose the effective sample size for learning splits, which is especially advantageous in deep trees, where few training points are available as depth increases.
4.3 Nearest Neighbors
Our final decoding strategy elides the leaf assignment step altogether in favor of directly estimating feature values via k-nearest neighbors (k-NN), First, we find the most proximal points the latent space. Once nearest neighbors have been identified, we reconstruct their associated inputs using the Ieaf assignment matrix II and the splits stored in our forest fn. From these ingredients, we infer the intersection of all leaf regions for each training sample- what Feng and Zhou (34) call the "maximum compatible rule". and generate a synthetic training set X by sampling uniformly in these subregions. Observe that this procedure guarantees g g = Z by construction.
Neighbors weighted in inverse proportion to their diffusion distance from the target Zo. producing the weight function w + A A Let K C. [n] denote the indices of the selected points and {& hie the corresponding synthetic inputs. Then the jth entry of the decoded vector Xa is given by toj = >iEk wi(2n) Zij. For categorical features, we take the most likely label across all neighbors, weighted by w, with ties broken randomly. The k-NN decoder comes with similar asymptotic guarantees to the previous methods, without assuming access to a leaf assignment oracle.
Theorem 4.4 (k-NN consistency). Let k + xo and k/n - 0. Then under the assumptions of Thm. 3.4 the k-NN decoder is universally consistent.
This approach is arguably truer to the spirit of RFs, using local averaging to decode inputs instead of just predict outputs. Like the split relabeling approach, this is modular decoding solution that does not rely on any particular encoding scheme. However, it is uniquely well suited to spectral embedding techniques, which optimally preserve kernel structure with respect to L2 norms in the latent space.
5 Experiments
In this section, we present a range of experimental results on visualization, reconstruction and denoising. Further details on all experiments can be found in Appx. B along with additional results. Code for reproducing all results available online The method is implemented as a package in (see previous footnote), as well as in Pythorf]
Visualization As a preliminary proof of concept, we visualize the embeddings of RF classifier with 200 trees as it trains on subset of the MNIST dataset (30) including samples with labels 3, 4, and 9 (see Fig. 2). Plotting a sequence of diffusion maps with d2 we find the model learning to distinguish between the four digits, which gradually drift into their own regions of the latent space. Early in training. the data are clumped around the origin. As depth increases, the manifold blooms and samples concentrate by class label. KPCI appears to separate 3 and from 4 and 9, which makes sense given that these respective pairs are often hard to distinguish in some handwritten examples. Meanwhile, KPC2 further subdivides 3 from 8. The relative proximity of 4's and 9's demonstrates that the RF somewhat uncertain about these samples, although with extra dimensions we find clearer separation (not shown). In other words, the embeddings suggest highly interpretable recursive partition, as we might expect from a single decision tree.
increasing tree depth,
httper//giihab..cmm/bpp.bbb/// httpp:///gicaab...oo/bbdddeee.ed
7

---

Table 1: Mean distortion (with standard errors) for each method and dataset, across all dz values used and all runs. Best result per row is bolded.
Dataset
RFAE
TVAE
TTVAE
AE
VAE
abalone
0.167 (0.002)
0.309 (0.005)
0.260 (0.003)
0.230 (0.025)
0.211 (0.006)
adult
0.326 (0.007)
0.158 (0.005)
0.195 (0.007)
0.401 (0.003)
0.391 (0.004)
banknote
0.100 (0.012)
0.312 (0.013)
0.276 (0.023)
0.724 (0.023)
0.771 (0.013)
bc
0.333 (0.003)
0.564 (0.003)
0.359 (0.005)
0.287 (0.008)
0,578 (0.003)
car
0.320 (0.011)
0.195 (0.014)
0.107 (0.015)
0.349 (0.012)
0.313 (0.011)
churn
0.352 (0.012)
0.603 (0.011)
0.422 (0.014)
0.861 (0.005)
0.731 (0.006)
credit
0.315 (0.004)
0.450 (0.005)
0.375 (0.011)
0.450 (0.005)
0.456 (0.004)
diabetes
0.479 (0.016)
0.726 (0.007)
0.643 (0.014)
0.799 (0.011)
0.895 (0.004)
dry bean
0.137 (0.002)
0.273 (0.002)
0.303 (0.008)
0.083 (0.014)
0.206 (0.001)
forestfires
0.575 (0.008)
0.804 (0.003)
0.705 (0.008)
0.782 (0.007)
0.790 (0.003)
hd
0.432 (0.008)
0.582 (0.003)
0.605 (0.006)
0.892 (0.003)
0.916 (0.002)
king
0.308 (0.008)
0.352 (0.006)
0.348 (0.008)
0.377 (0.011)
0,518 (0.004)
marketing
0,292 (0.009)
0.304 (0.005)
0.259 (0.011)
0.357 (0.007)
0.372 (0.004)
mushroom
0.083 (0.001)
0.093 (0.003)
0.011 (0.003)
0.055 (0.004)
0.035 (0.004)
obesity
0.227 (0.008)
0.354 (0.004)
0.299 (0.008)
0.306 (0.009)
0.358 (0.003)
plpn
0.176 (0.006)
0.282 (0.006)
0.224 (0.011)
0.384 (0.013)
0.410 (0.009)
spambase
0,558 (0.005)
0.825 (0.002)
0.807 (0.003)
0,446 (0.010)
0.784 (0.001)
student
0.371 (0.002)
0.424 (0.001)
0.426 (0.004)
0.536 (0.003)
0.551 (0.002)
telco
0.177 (0.003)
0.155 (0.003)
0.091 (0.007)
0.128 (0.005)
0.130 (0.005)
wq
0.240 (0.005)
0.691 (0.008)
0.759 (0.006)
0.467 (0.019)
0.708 (0.004)
Average Rank
1.80
3.38
2.45
3.27
4.10
Reconstruction We limit our decoding experiments in this section to the k-NN method, which proved the fastest and most accurate our experiments (for a comparison, see Appx. B.2). Hence- forth, this is what we refer to as the RF autoencoder (RFAE).
As an initial inspection of RFAE's reconstruction behavior, we autoencode the first occurrence of each digit in the MNIST test set for varying latent dimensionalities dz E {2. 4, 8, 16, 32} in Fig. For this experiment, we fit an (unsupervised) completely random forest [15] with B 1000 trees, train the encoder on full training data, project the test samples into 2 via Nyström, and decode them back using k 50 nearest neighbors. Although RFAES are not optimized for image data, the reconstructions produce mostly recognizable digits even with very few latent dimensions, with outputs that partially correspond to the wrong class. Best results can be observed at dz = 32, where the reconstructions appear quite similar to the originals. Additional results examining the influence of other parameters are presented Appx. B.2
Next, we compare RFAE's compression- distortion trade-off against two state-of-the-ann neural architectures for autoencoding tabular data (TVAE and TTVAE), along with standard and variational autoencoders (AE and VAE, respectively) that are not optimized for this task. Although there are some other notable deep learning algorithms designed for tabular data (e.g.. CTGAN [033. TabSyn [106), and TabPEN (56]). these do not come with inbuilt methods for decoding back to the input space at variable compression ratios. We also do not include eForest [34], another RF based au- toencoder, because only works with a fixed
d2
0
0
2
5 4
5
3 7 5 4
d2 0 0/234
8 9 7 8 9 3 4 6
4
5 7 8
d2
0
2 5 9
0 7 9
d2 16
0 2 3 4 0
4x 32
1 2
6
7
8 9
Original
0
/
2 8
4
5
6
7
8
9
Figure 3: MNIST digit reconstructions with vary- ing latent dimension sizes; original images are dis- played in the bottom row.
d2 2dx and is not capable of compression. For RFAE, we use the unsupervised ARF algorithm 99 with 500 trees and set = 20 for decoding.
In standard AEs, reconstruction error is generally estimated via La loss. This is not sensible with mix of continuous and categorical data, so we create combined measure that evaluates distortion on continuous variables via R² (i.c., the proportion of variance unexplained) and categorical
8

---

variables via classification error. Since both measures are on the unit interval, so too is their average across all dx features.
We measure this distortion across a range of compression factors (i.e., inverse compression ratios dz /dx in 20 benchmark tabular datasets. For more details on these datasets, see Appx. [B.1 Table 2 We evaluate performance over ten bootstrap samples at each compression factor, testing on the randomly excluded out-of-bag data. We find that RFAE is competitive in all settings, and has best average performance in 12 out of 20 datasets (see Table D. for an average rank of 1.80. For a more
granular view of performance on each dataset, see Appx. B.2
Fig.
Denoising As a final experiment, we con- sider a denoising example with single-cell RNA- sequencing (scRNA-seq) data. Pooling results from different labs is notoriously challenging in scRNA-seq due to technical artifacts collectively
known as "batch effects" [65]. We propose to harmonize data across batches by training
RFAE on a large baseline study and passing new samples through the autoencoding pipeline.
15451
Watth Conaree
As illustration, we compare two studies of the mouse brain transcriptome. Using the top dx = 5000 genes, we learn dz 64- dimensional embedding of the Zeisel et al. [105] dataset (n 2874). Our RF is completely ran- dom forest with B = 1000 trees. We project the Tasic al. [9]] data (m 1590) into the latent space and decode using the top k 100 nearest neighbors. Results are presented in Fig.
MG1
Sludy
Tasic et.
Zeisel
4 To avoid potential biases from reusing our own embeddings, we compare original and de- noised samples using PCA 600 and tSNE [93], two dimensionality reduction techniques that are widely used in scRNA-seq. both cases, we find that denoising with RFAF helps align the manifolds, thereby minimizing batch effects.
Figure 4: Denoising with RFAE alleviates batch
effects in scRNA-seq data.
6 Discussion
The building blocks of our encoding scheme are well established. Breiman himself took kernel perspective on RFs (16), a direction that has been picked up by numerous authors since 28
X 7
The theory of diffusion maps and KPCA goes back some twenty years [25 26 80] However, just as much RF theory has focused on idcalized variants of the algorithm [14, no prior works appear to have studied the properties of the true RF kernel, opting instead to analyze simpler approximations. And while there have been some previous attempts to generate RF embeddings [85] 77),, these have
been largely heuristic in nature. By contrast, provide principled approach to dimensionality reduction in RFs, along with various novel decoding strategies.
One notable difference between our method and autoencoding neural networks is that RFAE is not trained end-to-end. That is, while deep autoencoder simultaneously learns to encode and decode, RFAE is effectively a post-processing procedure for pre-trained RF, with independent modules for encoding and decoding. We highlight that
training represents a fundamentally different objective. Whereas traditional autoencoders are necessarily unsupervised, our method can be readily applicd to regression or classification forests, linking RFAE to supervised dimensionality reduction techniques [38 6). More generally, our goal is not just to learn efficient representation for its own sake, but rather to reveal the inner workings of a target model. One upshot of this decoupling is that our split relabeling and k-NN decoders can work in tandem with any valid encoding scheme. For instance, we could relabel an RF's splits to approximate the behavior of sample points in principal component space, indeed any Z for which we have map g : X + Z.
We highlight two notable limitations of our approach. First, the computational demands of our decoding strategies nontrivial. (For a detailed analysis, see Appx. D Second, when using the

---

k-NN approach, results will vary with the choice of k. (Experimental results on hyperparameter sensitivity are presented in Appx. B.2) However, we observe that autoencoding difficult task in general. Top deep learning models generally pose far greater computational burdens than RFAF, and require many more hyperparameters to govern model architecture and regularization penalties. Compared to the leading alternatives, RFAEs are relatively lightweight and user-friendly.
Autoencoders often motivated by appeals the minimum description length principle 778 55 49
Information theory provides precise formalism for modeling the communication game that arises when one agent (say, Alice) wants to send a message to another (say, Bob) using a code that is maximally efficient with minimal information loss. This is another way to conceive of RFAE- as sort of cryptographic protocol, in which Alice and Bob use shared key (the RF itself) encrypt and decrypt messages in the form of latent vectors which is presumably more compact (and not much less informative) than the original message x.
Several authors have persuasively argued that learning expressive, efficient representations is central the success of deep neural networks [I] 44). Our work highlights that RFs do something very similar under the hood, albeit through entirely different mechanisms. This insight has implications for how we use tree-based ensembles and opens up new lines of research for this function class.
7 Conclusion
We have introduced novel methods for encoding and decoding data with RFs. The procedure is theoretically sound and practically useful, with wide range of applications including compression, clustering, data visualization, and denoising. Future work will investigate extensions to generative modeling, as well as other tree-based algorithms, such as gradient boosting machines [35] 22]. Another promising direction is to the insights from this study to perform model distillation [54 37], compressing the RF into a more compact form with similar or even identical behavior. This possible with current methods, which still require the original RF to compute adjacencies and look up leaf bounds.
Acknowledgements
This research was supported by the UK Engineering and Physical Sciences Research Council (EPSRC) [Grant reference number EP/Y035216/1] Centre for Doctoral Training in Data-Driven Health (DRIVE-Health) King's ' College London and by the German Research Foundation (DFG), Emmy Noether Grant 437611051.
References
[1] N. Aronszaja. Theory of reproducing kernels. Transactions of the American Mathematical Society, 68(3):
337-404, 1950.
[2] Kai Arulkumaran, Mare Peter Deisenroth, Miles Brundage, and Anil Anthony Bharath. Deep reinforce- ment learning: A brief survey. IEEE Signal Processing Magazine, 34(6):26-38, 2017.
[3] Susan Athey, Julie Tibshirani, and Stefan Wager. Generalized random forests. Ann. Statist,, 47(2):
1 1148-117,, 2019.
[4] Adrien Aumon, Shuang Ni, Myriam Lizotte, Guy Wolf, Kevin R Moon, and Jake S Rhodes. Random forest autoencoders for guided representation learning. arXiv preprint, 2502. 13257, 2025.
[5] Francis Bach. Sharp analysis low-rank keree matrix approximations. In Proceedings of the 26th Annual Conference on Learning Theory, pages 185-209, 2013.
[6] Francis R. Bach and Michael Jordan. Predictive low-rank decomposition for kernel methods. In Proceedings of the 22nd International Conference on Machine Learning. page 33-40 40, 2005.
[7] M. Balog, B. Lakshminarayanan, Z. Ghahramani, D. M. Roy, and Y. W. Tch. The Mondrian keree.. In Proceedings of the 32nd Conference Uncertainty in Artificial Intelligence, pages 32-41, 2016.
[8] Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data represen- tation. Neural Computation, 13(3) 1396, 2003.
10

---

[9] Mikhail Belkin and Partha Niyogi. Towards a theoretical foundation for Laplacian manifold methods. Journal of Computer and System Sciences, 7488):1289-1308 2008. 2008.
[10] Yoshua Bengio, Olivier Delalleau, Nicolas Le Roux, Jean- François Paiement, Pascal Vincent, and Marie Ouimet. Learning eigenfunctions links spectral embedding and kernel PCA. 16(10):1197 2219, 2004,
[11] Yoshua Bengio, Aaron C. Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35:1798-1825 1828, 2012.
[12] Alain Berlinet and Christine Thomas Thomas-Agnan Reproducing kernet Hilbert spaces in probability and statistics. Springer, New York, 2003.
[13] Gérard Biau, Analysis of a random forests model. J. Mach. Learn. Res., 13: 13:1063-1095, 2012.
[14] Gérard Biau and Erwan Scornet. A random forest guided tour. TEST, 2552))192219 2016.
[15] Gérard Biau, Luc Devroye, and Gábor Lugosi. Consistency of random forests and other averaging classifiers. J. Much. Learn. Res., 9966):2015-20333 2008.
[16] Leo Breiman. Some infinity theory for predictor ensembles. Technical Report 579, Statistics Department, UC Berkeley, 2000.
[17] Leo Breiman. Random forests. Mach. Learn., 45(1):1-33,200 2001.
[18] Leo Breiman, Jerome Friedman, C. J. Stone, and R. A. Olshen. Classification and Regression Trees. Taylor Francis, Boca Raton, FL, 1984.
[19] Frederick Campbell and Genevera I, Allen. Within group variable selection through the exclusive lasso. Electron. Stat., 11()):420044255 2017.
[20) Miguel Á. Carreira- Periinnn and Kuat Gazizov. The tree autoencoder model, with application to hierarchical data visualization. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomezak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages 32281- 32306. Curran Associates, Inc., 2024. URL https: http://toooeeeee..eeeeee/o /
paappprrfllle_ Paper- Conf Conference. pdf
[21] Matias D. Cattaneo, Jason Klusowski, and William G. Underwood. Inference with Mondrian random forests. arXiv preprint, 2310.09702, 2023.
[22] Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, page 785-794, 2016.
[23] Xi Chen and Hemant Ishwaran. Random forests for genomic data analysis. Genom, (9)):333333,, 2012.
[24] F. Chung- Spectral graph theory. Conference Board of the Mathematical Sciences, Washington, 1997.
[25] R. R. Coifmann S. Lafon, A. B. Lee, M. Maggioni, B. Nadler, F. Warner, and S. W. Zucker. Geometric diffusions as a tool for harmonic analysis and structure definition of data: Difffusion maps. Proc. Natl. Acad. Sci., 102(21):7426-433)
2005. 2005.
[26] Ronald R. Coifman and Stéphane Lafon. Diffusion maps. Applied and Computational Harmonic Analysis, 21(1):5-300 30, 2006.
[271 Alvaro Corrcia, Robert Peharz, and Cassio P de Campos. Joints in random forests. In Advances in Neural Information Processing Systems, volume 33, pages 1 11404-1144 11415, 2020.
[28] Alex Davies and Zoubin Ghahramani. The random forest kernel and other kernels for big data from random partitions. arXiv preprint, 1402.4293, 2014.
[29] Grégoire Delétang, Anian Ruoss, Paul-Ambroise Duquenne, Elliot Catt, Tim Genewein, Christopher Mattern, Jordi Grau-Moya. Kevin Wenliang, Matthew Aitchison, Laurent Orseau, Marcus Hutter, and Joel Veness. Language modeling is compression. In The 12th International Conference on Learning Representations, 2024.
[30] Li Deng. The MNIST database of handwritten digit images for machine learning research [best of the web]. IEEE Signal Processing Magazine, 29(6):141 2012.

---

[31]
Misha Denil, David Matheson, and Nando De Freitas. Narrowing the gap: Random forests in theory and in practice. In Proceedings of the 31st International Conference on Machine Learning, pages 665-673, 2014.
[32] Luc Devroye, László Györfi, and Gábor Lugosi. A Probabilistic Theory of Pattern Recognition. Springer- Verlag, New York, 1996.
[33] Dheeru Dua and Casey Graff. UCI machine learning repository, 2019. URL http:///://r iics uci .edu/ml
[34] Ji Feng and Zhi-Hua Zhou. Autoencoder by forest. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence, 2018.
[35] Jerome H. Friedman. Greedy function approximation: A gradient boosting machine. Ann. Stat., 29(5): 1189 1232, 2001.
[36] Jerome H. Friedman, Trevor Hastie, and Rob Tibshirani. Regularization paths for generalized linear models via coordinate descent. J. Stat. Softw, 33(1):1-22, 2010.
[37] Nicholas Frosst and Geoffrey Hinton. Distilling neural network into soft decision tree. arXiv preprint, 1711.09784, 2017.
[38] Kenji Fukumizu, Francis R. Bach, and Michael Jordan. Dimensionality reduction for supervised learning with reproducing kernel hilbert spaces. J. Mach. Learn. Res., 3:73-99, 2004. ISSN 1532-4435.
[39] Kenji Fukumizu, Arthur Gretton, Xiaohai Sun, and Bernhard Schölkopf. Kernel measures of conditional dependence. In Advances in Neural Information Processing Systems, volume 20, 2007.
[40] Robin Genuer. Variance reduction in purely random forests. J. Nonparametr. Stat., 24(3):543-562, 2012.
[41] Pierre Geurts, Damien Ernst, and Louis Wehenkel. Extremely randomized trees. Mach. Learn., 63(1):
3-42, 2006.
[42] Amirata Ghorbani, James Wexler, James Y Zou, and Been Kim. Towards automatic concept-based explanations. In Advances in Neural Information Processing Syxtems, volume 32, 2019.
[43] T. R. Golub, D. K. Slonim, P. Tamayo, C. Huard. M. Gaasenbeek, J. Mesirov, H. Coller, M. L. Loh, J. R. Downing, M. A. Caligiuri, C. D. Bloomfield, and E. S. Lander. Molecular classification of cancer: Class discovery and class prediction by gene expression monitoring. Science, 286(5439):3115533 1999.
[44] Tan Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. org
MIT Press, 2016.
http:
//ww. www..deppeeaningglae
[45] Arthur Gretton, Karsten Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alex Smola. kernel method for the wwo-sanple-problem.. In B. Schölkopf. Platt, and T. Hoffman, editors, Advances in Neural Information Processing Systems, volume 19, 2006.
[46] Arthur Gretton, Kenji Fukumizu, Choon Teo, Le Song, Bernhard Schölkopf, and Alex Smola. A kernel statistical test of independence. In Advances in Neural Information Processing Systems, volume 20, 2007.
[47] Arthur Gretton, Karsten M. Borgwards, Malte J. Rasch, Bernhard Schölkopf, and Alexander Smola. kernel two-sample test. J. Mach. Learn. Res., (3(25):733-77, 2012.
[48] Leo Grinsztajn, Edouard Oyallon, and Gael Varoquaux. Why do tree-based models still outperform deep learning on typical tabular data? 36th Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2022.
[49] Peter Grünwald. The minimum description length principle. The MIT Press, Cambridge, MA, 2007.
[50] László Györfi, Michael Kohler, Adam Krzyžak, and Harro Walk. A Distribution-Free Theory of Nonpara- metric Regression. Verlag,--Vrrlag, New York, 2002.
[51] Fredrik Hallgren. Kernel PCA with the Nyström method. arXiv preprint, 2109.05578, 2021.
[52] Jihun Ham, Daniel D. Lee, Sebastian Mika, and Bernhard Schölkopf. A kernel view of the dimensionality reduction of manifolds. In Proceedings of the 21 International Conference on Machine Learning. 2004.
[53] Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner. variational framework. In International Conference Learning Representations, 2017.
Learning basic visual concepts with a constrained
12

---

[54] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network. arXiv preprint, 1503.02531, 2015.
[55] Geoffrey E Hinton and Richard Zemel. Autoencoders, minimum description length and Helmholiz free energy. Advances in neural information processing systems, 1993.
[56] Noah Hollmann, Samuel Müller, Lennart Purucker, Arjun Krishnakumar, Max Körfer, Shi Bin Hoo, Robin Tibor Schirrmeister, and Frank Hutter. Accurate predictions small data with tabular foundation model. Nature, 637(8005):3 199-322, 2025.
[57] Allison Marie Horst, Alison Presmanes Hill, and Kristen Gorman, palmerpenguins: Palmer Archipelago (Antarctica) penguin data, 2020. URL. htttp:://allsoooooreet github. 10/ ww/ppa/errpnngunns/ package version 0.1.0.
[58] M. Hutter. Universal Artificial Intelligence: Sequential Decisions Based on Algorithmic Probability. Springer Berlin Heidelberg, Berlin, 2004.
[59] Christopher R John, David Watson, Michael R Barnes, Costantino Pitzalis, and Myles J Lewis. Spectrum: fast density-aware spectral clustering for single and multi-omic data. Bioinformatics, 36(4): 159-11619116 2019.
[60] L.T. Jolliffe. Principal Component Analysis. Springer, New York, second edition. 2002.
[61] Richard M. Karp. Reducibility among Combinatorial Problems, pages 85-103. Springer US, Boston, MA, 1972.
[62] Risi Imre Kondor and John D. Lafferty. Diffusion kernels on graphs and other discrete input spaces. In Proceedings of the 19th International Conference on Machine Learning, page 315-322, 2002.
[63] Pawel Ladosz, Lilian Weng, Minwoo Kim, and Hyondong Oh. Exploration in deep reinforcement learning: A survey. Information Fusion, 85:1-22, 2022.
[64] Balaji Lakshminarayanan, Daniel M Roy, and Yee Whye Teh. Mondrian forests: Efficient online random forests. In Advances in Neural Information Processing Systems, volume 27, 2014.
[65] Jeffiey T. Leek, Robert B. Scharpf. Héctor Corrada Bravo, David Simeha, Benjamin Langmead, W. Evan Johnson, Donald Geman, Keith Baggerly, and Rafael A. Irizarry. Tackling the widespread and critical impact of batch effects high-throughput data, Nat. Rev. Genet., 11(10):733-73) 2010.
[66] Yi Lin and Yongho Jeon. Random forests and adaptive nearest neighbors. Am. Stat. Assoc. 101(474):
578-590, 2006.
[67] King's College London. King's computational research, engineering and technology environment (create).
http://2oo....///111188///////// m076 2022. Retrieved May 10, 2025.
[68] Gábor Lugosi and Andrew Nobel. Consistency of data-driven histogram methods for density estimation classification. Ann. Stat., 24(2):687 706, 1996.
[69] David J.C. MacKay. Information theory, inference, and learning algorithms. Cambridge University Press, Cambridge, 2003.
[70] Nicolai Meinshausen. Quantile regression forests. Mach. Learn. Res., 7:983-99 999, 2006.
[71] Defeng Sun Meixia Lin, Yancheng Yuan and Kim- Toh. A highly efficient algorithm for solving exclusive lasso problems. Optim. Methods Softw., 39835-89-- 2024.
[72] Schastian Mika, Bernhard Schölkopf, Alex Smola, RobertRobert Müller, Matthias Scholz, and Gunnar Rätsch. Kernel PCA and de-noising in feature spaces. Advances in Neural Information Processing Systems, volume 11, 1998.
[73] Jaouad Mourtada. Stéphanc Galffaa, and Erwan Scornet. Minimax optimal rates for Mondrian trees and forests. Ann. Statist,, 48(4):2253 2276, 2020.
[74] Boaz. Nadler, Stéphane Lafon, Ronald R. Coifman, and loannis Kevrekidis, Diffusion maps, spectral clustcring and reaction coordinates of dynamical systems. Appl. Comput. Harmon. Anal., 21(1):13-127,, 2006. Special Issue: Diffusion Maps and Wavelets.
[75] Andrew Ng. Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. In Advances in Neural Information Processing Systems, volume 14. The MIT Press, 2001.
13

---

[76] Sambit Panda, Cencheng Shen, and Joshua T. Vogelstein. Learning interpretable characteristic kemnels via decision forests. arXiv preprint, 1812.00029, 2018.
[77] Konstantinos Pliakos and Celine Vens. Mining features biomedical data using clustering tree ensembles.
J. Biomed. Inform., 85:40-48, 2018.
[78] Jorma Rissanen. Stochastic complexity in statistical inquiry. World Scientific, Singapore, 1989.
[79] Bernhard Schölkopf and Alexander J. Smola. Learning with Kermels: Support Vector Machines, Regular- ization, Optimization, and Beyond. The MIT Press, Cambridge, MA, 2001.
[80] Bernhard Schölkopf, Alexander Smola, and Klaus-Robert Müller. Nonlinear component analysis kernel eigenvalue problem. Neural Computation, 10(5):1299 1319, 1998.
[81] Bernhard Schölkopf, Francesco Locatello, Stefan Bauer, Nan Rosemary Ke, Nal Kalchbrenner, Anirudh Goyal, and Yoshua Bengio. Toward causal representation learning. Proc. IEEE, 109(5)611-6344 2021.
[82] Erwan Scomet. On the asymptotics of random forests. J. Multivar. Anal., 146:72-83, 2016.
[83] Erwan Scomet. Random forests and kernel methods. IEEE Trans. Inf. Theory, 62(3):1485 (23))1445-15000 2016.
[84] Jianbo Shi and Malik. Normalized and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell., 22(8):888-90) 2000.
[85] Tao Shi and Steve Horvath. Unsupervised learning with random forest predictors. J. Comput. Graph. Stat., 15(1):118-18) 138, 2006.
[86] Ravid Shwartz-Ziv and Amitai Armon. Tabular data: Deep learning is not all you need. Inf. Fusion, 81: 84 90, 2022.
1871 Bharath Sriperumbudur, Kenji Fukumizu, and Gert R.G. Lanekrict. Universality, characteristic kernels and RKHS embedding measures. J. Mach. Learn. Res., 12(70):2389 2410, 2011.
[88] Ingo Steinwart. On the influence of the kernel on the consistency of support vector machines. J. Mach. Learn. Res., 2:67-93, March 2002.
[89] Charles J. Stone. Consistent nonparametric regression. Ann. Statist., 5(4):595 620, 1977.
[90] Cheng Tang, Damien Garreau, and Ulrike Luxburg. When do random forests fail? In Advances in Neural Information Processing Systems, volume 31, 2018.
[91] Bosiljka Tasic, Vilas Menon, Thuc Nghi Nguyen, Tae Kyung Kim, Tim Jarsky, Zizhen Yao, Boaz Levi, Lucas T Gray, Staci A Sorensen, Tim Dolbeare, Darren Bertagnolli, Jeff Goldy. Nadiya Shapovalova, Sheana Parry, Changkyu Lee, Kimberly Smith, Amy Bemard, Linda Madisen, Susan M Sunkin, Michael Hawrylyez, Christof Koch, and Hongkui Zeng. Adult mouse cortical cell taxonomy revealed by single cell transcriptomics. Nat. Neurosci., 19(2):335 346, 2016.
[92] Jakub Tomezak. Deep generative modeling. Springer, New York, 2022.
[93] Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-SNE, J. Mach, Learn, Res., 9(66): 2579-2605, 2008
[94] Joaquin Vanschoren, Jan N. Rijn, Bernd Bischl, and Luis Torgo OpenML: networked science in machine learning. ACM SIGKDD Explorations Newsletter, 15(2):9-60, 2013.
[95] Antonio Vergari, Robert Peharz, Nicola Mauro, Alejandro Molina, Kristian Kersting, and Floriana Es- posito. Sum-product autoencoding: Encoding and decoding representations using sum-product networks. In Proceedings of the 32nd AAAI Conference Artificial Intelligence, 2018
[96] Pascal Vincent, Hugo Larochelle, Isabelle Lajoie, Yoshua Bengio, and Pierre-Antoine Manzagol. Stacked denoising autoeneoders: Learning useful representations in deep network with local denoising criterion. 2010.
J. Mach. Learn. Res.,
[97] Ulrike von Luxburg. A tutorial on spectral clustering, Stat. Comput., 17(4):395-416, 2007.
[98] Stefan Wager and Susan Athey. Estimation and inference of heterogeneous treatment effects using random forests. J. Am. Stat. Assoc., (13(52)::1288 1224-1222, 2018
14

---

[99] David S. Watson, Kristin Blesch, Jan Kapar, and Marvin N. Wright. Adversarial random forests for density estimation and generative modeling. In Pruceedings of the 26th International Conference on Artificial Intelligence and Statisticx, pages 5357-5375, 2023.
[100] Christopher Williams and Matthias Seeger. Using the nyström method speed up kernel machines. Advances in neural information processing systems, 13, 2000.
[101] Marvin N. Wright and Andreas Ziegler. ranger: fast implementation of random forests for high dimensional data in c++ and Stat. Softw., 77(1), 2017.
[102] Qinghua Wu and Jin-Kao Hao. review algorithms for maximum clique problems. European Journal of Operational Research, 242(3):933-799, 2015.
[103] Lei Xu, Maria Skoularidou, Alfredo Cuesta-Infante and Kalyan Veeramachaneni. Modeling tabular data using conditional GAN. H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32, 2019.
[104] Chih-Kuan Yeh, Been Kim, Sercan Arik, Chun-Liang Li, Tomas Pfister, and Pradeep Ravikumar. completeness-aware concept-based explanations in deep neural networks. In Advances in Neural Infor- mation Processing Systems, volume 33, pages
2020.
[105] Amit Zeisel, Ana B. Muñoz-Manchado, Simone Codeluppi. Peter Lönnerberg, Gioele La Manno, Anna Juréus, Sueli Marques, Hermany Munguba, Liqun He, Christer Betsholtz, Charlotte Rolny, Gonçalo Castclo-Branco, Jens Hjerling-Leffler, and Sten Linnarsson. Cell types in the mouse cortex and hippocam- pus revealed by single-cell RNA-seq. Science, 347(6226): 138- 142, 2015.
[106] Hengrui Zhang, Jiani Zhang, Zhengyuan Shen, Balasabramaniam Srinivasan, Xiao Qin. Christos Falout- sos, Huzefa Rangwala, and George Karypis. Mixed-type saxed-type tabular data synthesis with score-based diffusion latent space. In The Twelfth International Conference on Learning Representations, 2024.
[107] Kai Zhang, Ivor Tsang, and James T. Kwok. Improved nyström low-rank approximation and error analysis. In Proceedings of the 25th International Conference on Machine Learning, page 1232- 1239, 2008.
[108] Yang Zhou, Rong Jin, and Steven Chu-Hong Hoi. Exclusive lasso for multi-task feature selection. In Proceedings of the 13th International Conference on Artificial Intelligence and Statistics, pages 188-995, 2010.
[109] Yichen Zhou and Giles Hooker. Boulevard: regularized stochastic gradient bnosted trees and their limiting distribution. Journal of Machine Learning Research, 23(183): 2022.
15

---

A Proofs
Since several our results rely on RF regularity conditions, we review these here for completeness.
We say that a sequence of functions {fn] is universally consistent if it converges in probability on any target function. That is, for any f E C()) and all c > 0, we have:
lim P(Il=" - falle > <) = 0. 7-000
Under certain assumptions, it can be shown that RF's are universally consistent in this sense 70 31
82 98 Specifically, we assume:
(A1) Training data for each tree is split into two subsets: one learn split parameters, the other to assign leaf labels.
(A2) Trees are grown on subsamples rather than bootstraps, with subsample size n (h) satisfying
n (b) - 30, (h /n + as - oC.
(A3) At each internal node, the probability that tree splits any given Xy is bounded from below by some p > O.
(A4) Every split puts at least fraction y (0, 0.5) of the available observations into each child node.
(A5) For each tree b [B], the total number of leaves d satisfies d co, d /n 0 as 72 - DO.
Under (A1)-(A5), decision trees satisfy the criteria Stone's theorem 89 and are therefore univer-
sally consistent (see Devroye al. 32 Thm. 6. I] and Györfi al. [50] Thm. 4.2]). The consistency of the ensemble follows from consistency of the basis functions [5]. There is some debate the literature whether these assumptions
necessary for universal consistency- (A1) and (A2) in
particular may be overly strong but they are provably sufficient. See Biau 13 Rmk. 8]. Wager and
Athey 98 Appx. BJ, and Tang et al. [90] for discussion.
A.1 Proof of Thm. 3.4 (RF kernel properties)
This theorem makes three separate claims: that RF kernels are (a) PSD and stochastic; (b) asymptoti- cally universal; and (c) asymptotically characteristic.
(a) PSD Take PSD first. is well known that any convex combination PSD kernels is PSD (79], secure part (a) it is sufficient to prove that the standard decision tree kernel is PSD. This is simply a normalized indicator kernel:
A((0 [x, x') En
k DT (x,xxx
(x, x;)
(x,
which either evaluates to zero (if the samples do not colocate) or the reciprocal of the leaf sample size (if they do).
To show that DT is PSD, we take a constructive approach in which we explicitly define the canonical feature map ø X' + H. which maps input vectors an inner product space H. This suffices to establish the PSD property, since for any finite dataset the resulting kernel matrix KDT E [0, 1]mxx is Gram matrix with entries hD (0(x,), ø(x,)) As described in Sect. the DT feature map for tree is given by:
p0o) (x) = (0) (x) O (b)
where (b) X' + (0, 1e a standard basis vector indicating which leaf routes to in tree b, and E (1//n 1) is vector of corresponding inverse leaf sample sizes. Concatenating these maps over trees and taking the inner product for sample pairs, we get an explicit formula for the RF feature map, thereby establishing that ARF is PSD.
may not be immediately obvious that Eq. [ is equivalent to the scaled inner product B B-1(0(x), ((x)). For completeness, derive the identity. Expanding the inner product,
16

---

have
(o(x),
(0(6) (x), ())(0) (x'))
B
7 (b) (x) ① /s(0), x (x)) o Vs(o)
b=1
(x) z (x) 8
(6)
(8)
b
(b) If both and x' fall in leaf & of tree b, then o (x) n
(x') = 1; otherwise, the product evaluates to 0.
Let leal denote the inverse sample size of the leaf containing x in tree b. Then (x)) (x))) =
Seal x, x' fall the same leaf of tree or otherwise. Note that we have:
(b)
(6)
Icaf
E
((6) (x, x;)
since the number of training points the same leaf as x is given by Ei= (x,, Substituting and dividing by B gives:
110) x')
B (o(x),
Σ b=1 E k(b) (x, xx)
which completes the derivation.
Part (a) makes additional claim, however-thal k-RP is stochastic. This means that, for any X, the kernel k (x, x.) defines probability mass function over the training data as i ranges from I n. easy to see that the kernel is nonnegative, all entries are either zero (if samples do not
colocate) or some positive fraction representing average inverse leaf sample size across the forest (if they do). All that remains then is show that the values sum to unity. Consider the sum over all training points:
1:10) xi)
k
RF
[x,X,
B
Σソ= 1=1 1((() (x,
i=1
b=1
1 x5)
Σj 1: (x, x,)
1e(1)) xx)
B
k001 (x,
==
B
1.
Since the kernel is symmetric, the training matrix K E [0, 1| of kernel entries is doubly stochastic (i.e., all rows and columns sum to one).
(b) Universal Recall that the Moore Moore-Aronszajp theorem tells us that every PSD kernel defines a unique RKHS [.] Given that kRF PSD, universality follows if we can show that the associated RKHS H. is dense in C(2'). Of course, this is provably false at any fixed n, as dæ = o(n) by (A5), and finite-dimensional H. necessarily contains "gaps"-ia some functions f C(X) such that (f" = 0 for all h E H.
However, and de grow, these gaps begin to vanish. Since these two parameters increase at different rates, and it is the latter that more directly controls function complexity, we interpret the subscript e on Hr indexing the leaf count. (As noted above, focus the single tree case, as ensemble consistency follows immediately from this.)
The following lemma sets up our asymptotic universality result.
17

---

Lemma A.1 (RF subalgebra). Let He denote the set of continuous functions on the compact metric space X' representable by tree with & leaves, trained under regularity conditions (A1))(A5). Define:
00
A = :=UUL He. 8=1
Then A is subalgebra of (()) that contains the constant function and separates points.
Proof. The lemma makes three claims, each of which we verify in turn.
(1) is a subalgebra of C(X).
Each Hy consists of continuous, piecewise constant functions on X' induced by recursive binary partitions of X' into E leaf regions. These spaces are closed under addition, scalar multiplication, and multiplication, as the sum or product of two piecewise constant functions is piecewise constant over the common refinement of their partitions. Since A is the union of these He, it is closed under addition, multiplication, and scalar multiplication.
(2) A contains the constant functions.
This follows immediately, as any tree (and hence any HP) can represent constant functions for instance, trivial tree with no splits assigns the same value to all points.
(3) A separates points.
By regularity conditions (A3) and (A4), every coordinate has a nonzero probability / > 0 of being selected for splitting any node, and every split allocates at least fraction Y E (0, 0.5] of the points to each child node, Meinshausen [70] Lemma 2] has shown that, under these conditions, the diameter of each leaf goes to zero in probability. This amount to an asymptotic injectivity guarantee. Since N' is compact, for any pair of distinct points x, x' E X, there exists index é such that some ft He assigns different values to x and x'. In other words, some tree in A is guaranteed to route and x' to different leaves.
We now invoke the Stone- Weierstrass theorem to conclude the density of A. Theorem A.2 -eierssWirss Let be a compact Hausdorff space. If a subalgebra A of C(X) contains the constant functions and separates points, then A is dense in C(X) with respect to the uniform norm.
Combining Lemma A.l with this classical result, we conclude that the sequence (Hr) converges on a universal RKHS.
(c) Characteristic Item (c) follows from (b) under our definition of universality. This was first shown by Gretton et [55 Thm. 3] the non-asymptotic regime (although Sriperumbudur et al. [77 prove that the properties can come apart under slightly different notions of universality). We adapt the result simply by substituting a sufficiently close approximation in H. where proximity is defined w.r.t. the supremum norm. Since the existence of such close approximation is guaranteed by (b), the sequence ( (He) is asymptotically characteristic.
A.2 Proof of Thm. 4.2 (Oracle consistency)
This result follows trivially from the universal consistency of the RF algorithm itself. Any partition of X' that satisfies regularity conditions (A1)-(A5) converges on the true joint distribution Px as n. dp + 5o (see (68, Thm. 1] and 27 Thm. 2)). Resulting leaves have shrinking volume, effectively converging on individual points x with coverage proportional to the density p(x). Because there are no gaps in these leaves (i.e., no subregions of zero density), a weighted mixture of uniform draws-with weights given by the leaf coverage-is asymptotically equivalent to sampling from Px itself. A leaf assignment oracle would therefore be guaranteed to map each latent vector z E Z to the corresponding input point X, since leaf assignments effectively determine feature values in the large sample limit.
18

---

A.3 Proof of Thm. 4.3 (Uniqueness)
It is immediately obvious that when Ko = K. the true leaf assignment matrix & drives the IIP objective to zero and automatically satisfies the one-hot and overlap constraints. Our task, therefore, to demonstrate that no other binary matrix V + & can do the same.
For simplicity, consider just a single test point (m 1). Let J C 1) denote the feasible region of leaf assignment vectors, i.c. all and only those that satisfy the one-hot and overlap constraints. A sufficient condition for our desired uniqueness result is that no two feasible leaf assignments produce the same kernel values. More formally, if there exist no &b, ap' E F such that IS = IIS& then the map /b ++ IISb is injective over F, in which case only a single solution can minimize the ILP objective.
Note that this injectivity property cannot be shown to hold in full generality. As a minimal coun-
terexample, consider a case where the feature space is a pair of binary variables X = {00, 1}2 and our forest contains just two trees, the first placing single split on X1 and the second placing a single split on X2. Now, say our training data comprises just two points, x = [0, 0] and x = [.. We observe the kernel entries ((x,, x) k(x,, x') 1/2. In this case, we know that X colocates with each training sample exactly once, and therefore that it shares exactly one coordinate with each of our two training points. However, we do not have enough information to determine where these colocations occur, since both [0, 1] and [1, 0] are plausible feature vectors for Xu-
Such counterexamples become increasingly rare the forest grows more complex. As previously noted, under (A3) and (A4), leaf diameter vanishes in probability [70] Lemma 2]. This is why random forests are asymptotically injective, property we exploited in the proof for part (b) of Thm. 3.4 A corollary of Meinshausen'ss 's lemma is that for all distinct points x, x' E X::
lim (xf = fm,(x)) = 0. n-
By modus tollens, it follows that if function outputs converge on the same value, then corresponding inputs must be identical. This is important, since with fixed training labels Y, model predictions are fully determined by kernel evaluations via Eq. 2 If two distinct vectors 3 v produce identical values when left-multiplied by IIS, then the corresponding inputs x, x' cannot be separated by fn- Therefore, with probability tending toward I as sample size grows, we conclude that the II. of Eq. uniquely solved by the true leaf assignments.
A.4 Proof of Thm. 4.4 (k-NN consistency)
To secure the result, we must show that
(a) x 3 x: sampling uniformly from the intersection of each sample's assigned leaf regions asymptotically recovers the original inputs; and
(b) x 2 NNNN regression the spectral embedding space is universally consistent.
Item (a). which amounts to universal consistency guarantee for the eForest method of Feng and Zhou [34], follows immediately from our oracle consistency result (Thm. (.2)., plugging in the identity function for g. Since we know the true leaf assignments for each training sample, under universal consistency conditions for RFs, we can reconstruct the data by taking uniform draws from all leaf intersections.
Item (b) follows from the properties of the k-NN algorithm, which is known to be universally consistent as A + o0, k/n
[89]
B Experiments
RFs are trained either using the ranger package [101], or the arf package 199), which also returns a trained forest of class ranger. Truncated eigendecomppsitions are computed using RSpectra. Memory-efficient methods for sparse matrices are made possible with the Matrix package. We use the RANN package for fast k-NN regression with kd-trees. For standard lasso, we use the glmnet package [6), and ExclusiveLasse for the exclusive variant [19]. In both cases, we do not tune the
19

---

Table Summary of datasets used. % Categorical indicates the proportion of categorical features. Classes indicates the total cardinality of all the categorical features.
Dataset
Code
#Samples
#Numerical
#Categorical
Total
% Categorical
#Classes
Abalone
abalone
4177
0.11
3
Adult
adult
45222
14
0.64
100
Banknoote Auth.
banknote
1372
5
0.21
2
2
1728
0
7
1.00
Bank Cust. Chur
churn
10000
5
11
0,56
German Credit
credit
1000
Diabetes
diabetes
768
2
Dry Bean
dry_bean
13611
16
17
0,06
7
Forest Fires
forestfires
517
2
13
0.15
19
Heart Discase
Countyy Housing
21613
19
0
19
0.00
0
Bank Markeling
marketing
45211
7
10
17
01.99
44
Mushroom
mushroom
8124
22
119
Levels
obesity
Palmer Penguins
plpn
333
8
0.38
8
Spambuse
spanbase
4601
58
59
0.02
2
Student Performance
student
Telco Churn
telco
7032
0.85
Wine Quality
4898
12
0
12
0.00
0
penalty parameter X, but simply leave it fixed at a small value (0.0001 in our experiments). This is appropriate because not attempting solve prediction problem, but rather ranking problem over coefficients.
B.1 Reconstruction benchmark
We describe the setup for the experiments presented in the main text, Sect. 5
For the compression reconstruction benchmark, Learning Repository [33]. OpenML. 194), Kaggle, and the palmerpenguins [57] package. In each dataset, we remove all rows with missing values. We also remove features that are not rele- vant to this task (e.g., customer names), features that duplicate in meaning (e.g., education and education onn on_ num adult) and date-time features. We report the subsequent in Table describing for each used dataset the number of rows, features, and the proportion of categorical features in the total feature set, as a measure the 'mixed" -ness of the tabular data.
20 datasets sourced from the UCI Machine
Then, our pipeline proceeds as follows:
For each dataset, we take ten different bootstrap samples, form ten training sets, and use the remaining out-of-bag data as the testing set. We do this to ensure data is not unnecessarily unused, which could skew results in datasets with small n.
For each dataset, we define 10 compression ratios, or latent rates, going uniformly from 0.1 (10% of the number of features) (100% the number of features). For each value, find dæ = dx x latent_ rate
For each dataset and bootstrap,
each method with the specified d for the dimension- ality of their latent embeddings. This involves training the method on the bootstrap training data, then passing the testing data through its encoding and decoding stages produce reconstruction.
We then compute the distortion of these reconstructions compared to the original test samples, using metries described in the main text. For each bootstrap and dz on dataset, aggregate the results into mean, and report the standard error error bars. This standard error represents a combination any stochastic component of the methods used, well the finite sample uncertainty of the used data.
Within this specification, we run each method 20 x 10 10 2000 times, and for 5 methods this balloons to 10,000 runs. To meet these computational demands, we run these experiments from hegh-peeformance computing partition, with 12 AMD EPYC 7282 CPUs, 64GB RAM, and an
20

---

NVIDIA A30 graphics card. These high- teg--perforaacc computing units were used as part of King's College London's CREATE HPC [67]
Next, we describe in detail each of the methods used in the reconstruction benchmark:
TVAE TTVAE:
For both the TVAE and TTVAE models, we do not make any changes to the underlying model architecture. However, we make minor modifications to not perform any sampling/interolatiion at the latent stage, and simply decode the same embeddings that we acquired from the encoder.
Autoencoder: We use an MLP-based autoencoder for this benchmark. This is in contrast CNN-based autoencoder, which is more suited image data, but is not relevant in tabular data tasks, where there is no inherent structure that could be extracted by convolution kernels. We structure our network have five hidden layers, where the size of these layers are adaptive to dx and dz. In particular, we want to structure the network such that the size of each hidden layer reduces uniformly from dx to dz at encoding and increases uniformly from dz to dx at decoding. Our structure then is: Input(dxx) - Dense(dx (dx d2) 1/3) Dense(dx - (dz d2) 2/3) Latent(dzdz) + Dense(dx - (dx - dz) x 2/3) + Dense(dx (dx dz) x 1/3) + Output(dxx).
If dx = 8, dz then with this rule the network will + 6 - 4
-
For hyperparameters, we use common defaults: epochs = 50, optimizer ADAM We use ReLU activations hidden layers, sigmoid for the output, and a random 10% validation set from the training data.
Variational Autoencoder:
Similar to the autoencoder, we use an MLP-based variational autoencoder. For comparison, mimic the autoencoder's architecture, activation function, and defaults, only changing epochs = 100 and adding batch_sii 32. We also
impose coefficient inspired from [53] at value of 0.1.
The RF training approach we use here is the adversarial random forests (ARFs) 199
Using this
algorithm allows us to train the forest unsupervised, and preserve all features. Other approaches
involving unsupervised random forests can also be used, such as the ones proposed in Shi and Horvath (85) or Feng and Zhou [34). However, we choose ARF on the basis that our decoders' complexity scale on dæ, which is smaller for the ARF than others, because it learns its structure over several iterations of training.
We present the results in Fig. 5 corresponding to the plots in Table
B.2 Additional results
We present the results of additional experiments comparing different decoding methods, hyper- parameter analysis on MNIST, supervised vs. unsupervised RF embeddings as well as runtime experiments.
Decoder Comparison We compare the performance of three decoders that we describe in section the kNN, the split relabelling and the LASSO decoder, on smaller compression / reconstruction benchmark. We follow the same experimental setup as the previous experiment, but only use two datasets of small size (credit & student), and for each of these, we only use the first bootstrap splits. This is because we only aim to illustrate the performance of these decoders side by side, and also because of the both the relabeling and LASSO's decoder much higher complexity compared to KNN. We maintain the RFAE setup as previously described in Appx. B.I. To make comparison casier, for each iteration we run the encoding stage once, and apply the three decoders to the same embeddings. We describe the relabeling and the LASSO decoder in more detail:
For the relabeling decoder, we take the original RF object, and go through each split to find corresponding split with the data on the latent space with the highest simple matching coefficient (SMC) to replace it. This process is global, so all data points are used in each split.
Relabeling Decoder:
An alternative approach to this is to re-find splits locally, i.e., only use the data located at each split in the original forest. However, in practice, the lack of training points at high
21

---

abslone
Adut
denkentte
0.5
0.0
0.6
0.4
0.5
0.50
0.25
0.3
0.2
0.0
ctum
credit
diabetes
dry. telnn
Eresitines
1.0
0.5
0.8
0.3
0.4
0.6
0.7
Distoriion
0.2
0.4
0.3
0.0
0.1
0.6
king
marketing
0.6
0.5
0.4
0.5
0.10
0.6
0.4
0.3
0.2
0.05
0.00
0.25
0.8
0.20
0.6
0.30
0.6
0.5
0.10
0.4
0.05
0.2
0.23
0.30
0.75
1.50
9.50
0.75
1.00
0.2
0.50
0.75
1.50
0.25
0.30
0.75
1.50
0.25
0.50
0.75
1.00
Comoression Factor
Method
AFAE
TVAE
TTVAF
VAB
Figure 5: Compressionddistorioo trade-off on twenty benchmark tabular datasets. Shading represents standard errors across ten bootstraps.
depths will cause the relabeled splits to inaccurate, so we use the global approach. Once the forest is 'relabeled', can pass the embeddings for test data through it, and sample by using the leaf bounds of the original forest.
LASSO Decoder: For the LASSO decoder, we follow the derivations in the main text and compute the kernel matrix K2 Az and recover the leaf assignments for test samples via the LASSO & greedy leaf search algorithm in Appx. C Once the leaf assignments are recovered, we once again sample by using the forest's leaf bounds.
To reduce complexity, we impose sparsity on the number of training samples allowed in the LASSO, sorted by the the values of the estimated kernel matrix. Because in most cases, a test sample will only land in the same leaf with small number of training samples, even across an entire forest, this allows us to narrow the search space significantly with minimal impact on the model performance. For our datasets with 649 and 1000 samples, we set sparsity 100.
We present the results in Fig. where the kNN method is denoted as RFAE.
0.7
6.6
0.2
Ostorioon
0.4-
0.0
Method
#EAF
14550
Figure 6: Compression-distoriis trade-off on student and credit. Shading represents standard errors across five bootstraps.
22

---

From this plot, we can see that the kNN decoder dominates performance. Several reasons can explain the poor performance that the other decoders display. For the relabeling decoder, because our only criteria is to find the best matching split, if all candidates are bad, the best matching split does not have to be an objectively good choice. Given the forest's s hierarchical nature, inaccuracies can be compounded traversing down the tree, and the final forest is completely dissimilar to the original. The small dz also means more variance is introduced into the process.
For the LASSO decoder, several things may have caused this performance. First, the estimation of K may not be accurate, which is passed on to the LASSO optimization. The LASSO is also an approximate optimization, and variance here can lead to the greedy leaf algorithm to find the wrong leaf assignments for the test samples. This, in combination with the high complexity, motivate us to use the kNN decoder for RFAF.
50
0
/
2
3
4
4
6
7
2
7
8 3 100
0
/
2
3
4
0
6
7
8
9
0
6 7
0 2
7
8
9
Hoarunc 10000
0
2
3
4
0
6 7
3
B = 300
0 2/3 4
0
6
7
8
9
Mourune 9000
0
2
3
4
0
6 7
8
1000
0 / 2 3 4
0
6
7
8
0X20
0
/ 2
3
4
9
6
7
8
9
Original
0 / 2 3 4 5
6 7 8
A
Original
0
/ 2
3
4
5
6
7
8
A
(a) Varying number of decision trees forest.
random
(b) Varying number of training points en used for encoder training.
0
/
2
3
4
6
6
7 8
2
k=0
0
2
3
4
G
6
7
8
6=2
0
2
3
4
8
b
7
8
9 6 A 6
1=1
0
/
2
3
4
G
6
7
8
0
/ 2
3
4
6
7
8 8 8
<-2
0
/ 3
4
6
6
7
8
9
k-5
0
/ 2
3
4
6
7
0
/ 2
3
4
0
6
7
8
9
1-10
0
/ 2
3
4
0
6
7
4= 10
0
/ 2
3
4
0
6
7
8
9
=0
1
2
3
4
0
4
7
8
9 A
0
/ 2
8
4
6
0
7
8 4
0
/ 2
3
4
6
6
7
8
Original
0 / 2
8
4
5
6
7
8
Original
0
8
4 6 6 7
8 9
(c) Varying number of time steps for diffusion map encoding.
(d) Varying number of nearest neighbors used for base- decoding.
Figure 7: MNIST digit reconstructions produced by RFAE with varying parameter values; original images are displayed in the bottom row.
MNIST reconstruction: hyperparameter analysis Fig. 7 complements Fig. 3 in Section 5 by
showing the effects of different parameters on the reconstruction performance for MNIST test digits:
the number of trees B (Fig. 7ah. the number of samples Reminn emc used for encoder training (Fig. 7b).
the diffusion time step t (Fig. 7c). and the number of nearest neighbors used for decoding (Fig. 7d.
In each subpiot, the respective parameter varies in pre-detined range, while all other ones are kept
fixed at = 1000, Thrainn ene 30 000, = 1, and = 50; the latent dimension is set to dz = 32 throughout.
RFAE (suparvised)
0 / 2 3 4
8 9 8 9 7 6 7 8
6 6 6
RFAF (completely rendom)
0 2
3 4
6
7
ConvAE
0
/ 2
8
4
5
6
8 9
Originl
0
/ 2
8
4
5
Figure 8: MNIST digit reconstructions produced by RFAE using supervised and copmletely random forests, and by a convolutional autoencoder, original images are displayed in the bottom row
23

---

Fig. 8 compares RFAE reconstructions using supervised and (unsupervised) completely random forests with those produced by a convolutional autoencoder with three convolutional layers. All models were trained on full training data and with dg 32.
Supervised vs. unsupervised embeddings RF embeddings provide different perspectives on the data depending on whether we use su- pervised or unsupervised learning objectives. We train a standard RF classifier to distinguish acute lymphoblastic (ALL) from acute myeloid (AML) leukemia samples well known tran- scriptomic dataset 43 After filtering, the feature matrix includes expression values for dx 3572 genes recorded in n 72 patients. These kind of short, wide datasets are common in bioinformatics, but can be challenging for many learning algorithms. RFs excel in these settings, attaining out-of-bag accuracy of 98% on this task. KPCI clearly separates the two classes in the left panel, while KPC2 appears to isolate a potential outlier within the AML cohort. Using an unsupervised adversarial RF [99], find far greater overlap among the classes (as expected), although ALL and AMI. samples are hardly uniform throughout the latent space. This example demonstrates the flexibility of method. Whereas standard spectral embedding algorithms with fixed kernels are limited to unsupervised representations, RFAE can take any RF input.
Figure 9: Embeddings can represent supervised or unsupervised RFs. Data from the Golub et al. (43 leukemia transcriptomics study.
Runtime Experiments Our runtime experiments consists of two tests; where we compare the runtime of methods within the reconstruction benchmark (see B.I method and dataset details), and one where we exclusively examine the runtime of RFAE more closely. For the first experiment, we conduct a controlled runtime comparison of all five methods (AE, VAF, TVAE, TTVAR and RFAE) on three moal--to datasets (plpn, student, credit). These experiments on a laptop with Intel Core 15-10300H CPU, NVIDIA GeForce GTX 1650 (4GB), and 24GB DDR4 RAM. Each method run 100 times across varying compression ratios, according the same specifications as in the benchmark. We report the runtimes in Table in seconds.
conducted
Table 3: Runtime comparison across five models and three datasets.
Dataset
AE
VAE
RFAE
TTVAE TVAE
plpn
161.6
185.9
523.8
744.2
2252.8
student
190.9
227.8
1058.6
3611.2
5148.7
credit
223.2
277.3
1379.5
2212.5
4046.0
Here, the results indicate RFAE's superiority in runtime over the other two state-of of-theeart methods in TVAE and TTVAE, while being slower than the naive AE and VAEs which did poorly in the actual benchmark.
For the second experiment, we evaluate RFAE alone across 20 datasets, using a fixed compression ratio 0.2 (10 runs per dataset). These were run on a HPC unit with an AMD Threadripper 3960X (24 cores, 48 threads) CPU and 256GB RAM, with no GPU unit used for the experiment. We report the average runtime for training and inference (as well as the total time), and their corresponding standard errors, ordered by average total runtime, in Table 4 in seconds. The results suggest RFAE scales well with dataset size.
C Leaf assignments via lasso and greedy search
In this section, we briefly describe the lasso relaxation of the ILP in Eq, 3 First, we split the task into m separate subproblems, one for each test vector. Let ko denote row of Ko. say for test point xg- Observe that this adjacency vector is generally sparse, since most training points are unlikely to be neighbors of X Let a = |ooo be the number of neighbors for Xo. and write kj E [0, 1] for the
'That neighbors vanish as a proportion of training samples is common consistency condition for nonpara- metric models in general and local averaging estimators in particular (
24

---

Table 4: RFAE runtime performance across datasets (sorted by total mean).
Dataset
Training
Training r Inference μ
Inference r
Total
Total
Samples
Features
plpn
1.89
0.00
1.35
0.01
3.24
0.03
333
8
credit
2.82
0.32
3.18
0.01
6.01
0.41
1,000
car
2.90
0.00
2.87
0.00
5.77
0.00
1,728
7
student
3.03
0.41
3.30
0.03
6,33
0.63
649
33
diabetes
3.16
0.01
3.97
0.01
7.13
0.01
768
9.
hd
4.17
0.00
5.99
0.00
10.16
0.00
298
14
forestfires
4.63
0.30
6.12
0.02
10.76
0.36
517
13
be
1.11
2.65
0.01
9.53
1.17
570
32
abalone
6.82
0.02
5.58
0.03
12.39
0.03
4,177
wq
7.90
0.73
6,38
0.01
14.28
0.81
4,898
12
obesity
8.74
0.02
12.11
0.08
20.85
0.05
2,111
16
churn
12.28
0.18
11.75
0.08
24.03
0.24
10,000
11
mushroom
13.80
0.23
11.53
0.10
25.33
0.48
8.124
22
telco
13.96
0.01
16.45
0.05
30.41
0.09
7,032
20
spambase
29.52
0.90
27.78
0.51
57.30
1.12
4,601
dry_bean
43.19
5.09
19.63
0.10
62.82
5.25
13,611
17
king
54.31
42.78
32.04
1.87
86.36
44.36
21,613
19
adult 150.27
304.30
89.47
24.85
239.75
469.52
45,222
14
marketing 148.96
4831.41
91.50
374.82
240.46
7889.97
45,211
17
reduction of ku to just its nonzero entries. We also write [() C L(b) for the of leaves which X neighbors are routed in tree b. with cardinality de < d and dj = (b) (Though the reduction operation is defined only w.r.t. some Xo, we suppress the dependency to avoid clutter.)
This implies corresponding reductions of 4 to the submatrix t E {0, 1 with one row per neighbor of Xo and columns for each leaf which at least neighbor routed in and S to s E [0, 1] x with diagonal entries for each leaf in Uo L()*
Following these simplifications, we solve:
min [Bkk] S + e
Σ BE
BELON
where the penalty factor promotes a sparse solution with similar effect to the one-hot constraint above. Specifically, it encourages competition both within trees (via the L1 norm), and between trees (via the L2 norm). Eq. L is an exclusive lasso problem, which can be efficiently solved via coordinate descent [108 19 dual Newton methods (71). The interval (rather than integer) constraints our decision variables effectively allow for "fuzzy" leaf membership. in which samples may receive nonzero weight in multiple leaves of the same tree.
Exploiting these fuzzy leaf assignments, we propose greedy method to determine leaf member- ship. The method provisionally assigns a sample to the leaves with maximal entries in e If any inconsistencies arise, we replace the "bad" assignments i... those less likely to overlap with other assigned regions-with the next best leaves according to ab. The procedure repeats until assignments are consistent. Though convergence is guaranteed, greedy search may prove inaccurate if coefficients poorly estimated.
Alg. provides an overview the greedy Icaf assignment procedure. This is run for single sample X, which has associated fuzzy leaf assignment vector p E [0, 1]de, We select the leaf coordinates associated with tree E [B] by writing (b) [0, 1]dd) We overload notation somewhat by writing R! X denote the hyperrectangular region associated with leaf E
[d(²) of tree b E [B] in step 5; and then R. (t) to denote the region associated with leaf g (0) (t). which maximizes (b) among all leaves that intersect with the feasible region S(t). If the arg max in step is not unique, then we select among the maximizing arguments at random. Similarly, if there are multiple overlaaalgg maximal cliques, then we select one random in step 14. (This should be exceedingly rare in sufficiently large forests.) The undirected graph (()) encodes whether the regions associated with assigned leaves overlap. Since consistent leaf assignments require intersecting regions for trees, the algorithm terminates only when ((t) is complete. The procedure is greedy the sense that edges
25

---

Algorithm GREEDYLLAAASSIGMMMNTSS
Input: Fuzzy leaf assignments p [0, 1]46
Output: Hard leaf assignments q E (I...., 1
I: Initialize: & <- 0, C(t) < S(t) < X, converged FALSE
while not converged
3: I <- +++
4: for all trees 6 e [ do
5: Find leaf with maximum fuzzy value in the feasible region:
(1)
arg max (1)
s.t. R. n.(()) #
xE(d?)
Let Rg) (t) the region corresponding leaf q (t)
7: end for
8:
Let G(t) ((B)) be graph with edges:
E(t = {i,j E [B] R (t) n R (1) 0}
if (1) is complete then 10: converged TRUE
9:
else
12:
if the maximal clique of ((t) is unique then
13:
Let C(t) c [b] be the unique maximal clique of G(t)
14:
clse if the maximal cliques of (() have nonempty intersection then
15:
Let (+t) [B] be the intersection of all maximal cliques of (tt)
16:
else
17:
Let C(t) = [B] be any maximal clique of (tt)
18: end if
19: Let (() beaay n4 (2((() (1) be the feasible region associated with C(1)
20:
end if
21:
end while
22: q f q(t)
only be added and never removed, leading to larger maximal cliques C(I) and smaller feasible regions S(L) with each passing round.
While the algorithm is guaranteed to converge on a consistent set of leaf assignments, this may only be achievable by random sampling of leaves under a consistency constraint. Such uninformative results are likely the product of noisy estimates for Kg Note that while the maximal clique problem is famously NP-complete [61], must solve this combinatorial task at most once (at 1). In subsequent rounds 2 2, we simply check whether any new nodes have been added to C(tt 1). Maximal clique solvers are highly optimized and have worst-case complexity B/3), but are often far more efficient due to clever heuristics [102]. In practice, the method tends to find reasonable leaf assignments in just a few rounds. When computing leaf assignments for multiple test points, we may Alg. D in parallel, solutions are independent for each sample.
D Computational complexity
In this section, we study the complexity of different RFAE pipelines.
The encoding step requires O(n²) space to store the adjacency matrix. For large datasets, this can be approximated by using subset of the training data compute K, the cost of losing the exact functional equivalence of Eq. Similar tricks are common in the kernel methods literature
[000 107 5).
While the ILP solution is generally intractable, the lasso relaxation requires (dd)) operations [19 to score leaves (although de can in fact be reduced to a, = ||k|lo for each test point i E [m]] see Appx. C.. The subsequent greedy leaf assignment algorithm searches for the maximal clique in graph with B nodes for each test sample, incurring worst-case complexity O( (B)( Though the maximal clique problem is famously NP-complete [61], modern solvers often execute very quickly due to clever heuristics [102]. We can also parallelize over the test samples, each greedy solution
26

---

is independent. Note that both the cubic term in the exclusive lasso task and the exponential term in the greedy leaf assignment algorithm are user-controlled parameters that can be reduced by training forest with fewer and/or shallower trees. Alternatively, we could use just subset of the RF's trees to reduce the time complexity of decoding via constrained optimization, much like we could use subset of training samples to reduce the space complexity of encoding.
The split relabeling method essentially iterated CART algorithm, and therefore requires Odznñ log ni time to relabel each split, where is the number of synthetic samples X. How- ever, since the number of splits is generally exponential in tree depth, this can still be challenging for deep forests.
The most efficient decoder the k-NN method, which proceeds in two steps. First, we find the nearest neighbors in embedding space, which for reasonably small dz can be completed in O( log n) time using kd-trees. Next, we compute the intersection all leaf regions for selected neighbors, incurring cost of O (kmdgdx))
27

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: As stated in our abstract, our contribution is a random forest autoencoder that composes of encoder and decoder which are supported by universal consistency proofs. We benchmark our autoencoder and demonstrate each the stated applications, while remaining within the literature of autoencoders and random forests.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss limitations within the Discussion section of our paper, as well as in the appendix when relevant.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
28

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Each theorem stated in the main text is accompanied by a corresponding proof in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We include the model, code, and data required to run our experiments within our supplemental material, as well as the specifications that we used and any additional instruction necessary to reproduce them.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
29

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Our model and code is included along with our paper within the supplemental material. We also include the datasets we used, and the scripts needed to reproduce the results on our benchmark, and these are also available on GitHub publicly.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed run reproduce the results. See the NeurIPS code and data submission guidelines (https
//wips.ccppublii. wttpcc/pppppgppu.ieeeeeeeo.op guwdee/deeeeee CodeSuumi soiobiiiiii for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We summarize experimental setup in the main text and describe in detail within the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We report error bars in our benchmarks and experiments, whenever they are relevant, and report how we calculate them either in the main text the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
30

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We specify the computer resourees used for our experiments in our Appendix. However, given the nature of our model, the development process includes many stages of experiments, and we are unable to report the total compute used.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported didn't 'tttt make it into the paper).
paper (e.g., preliminary or failed experiments that NeurlPS Code of Ethics https: http://ppw....p..b.....ccccaaaaa
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the
Answer: [Yes]
Justification: We have reviewed the NeurIPS Code of Ethics and have conformed to it, in every respect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
31

---

Justification: Our contributions are foundational in nature, and our model is an autoencoder, which does not carry direct path to any negative applications. On the other hand, we describe some general applications within health data science for which our work could be applied.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our model makes use of publicly available datasets, models and packages, and is designed for general purpose usage, not a specific application. Therefore, there are no such risks for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual- use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We cited all the datasets and all the other models we used within our benchmark, as well as those that are relevant to our work. We explicitly stated any modifications that we performed on previous assets.
32

---

Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com camdsatasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Our asset contribution is a codebase containing our model, the scripts used for our benchmarks, and the datasets used. We include these within the supplemental material, and documentation can be found either here or within the appendix.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/cood/mmodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
33

---

Answer:
[NA]
Justification:
Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification:
We did not involve LLMs in any core method development within our research.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy htteep///oaarrsssccc//ooffeereee for what should or should not be described.
34


Reviews:
[{"review_id": "bz2ijW1Mdu", "reviewer": "Reviewer_58sa", "summary": "The authors propose an autoencoder based on Kernel Principal Component Analysis, where a Random Forest is used to compute a kernel matrix.\n\nEncoder: The kernel $k(x,y)$ is computed based on the proportion of trees in which samples $x$ and $y$ are routed to the same leaf, with a specific normalization applied. Then, the eigendecomposition of the resulting kernel matrix is computed, and the top eigenvectors are used to form the embedding. The proposed method does not have an exact out-of-sample mapping and relies on the Nystrom approximation.   \n\nDecoder: The algorithm does not have a natural way of decoding, so the authors propose several approximation methods:\n- Constraint Optimization: This method uses an integer linear program to find the most likely leaf assignments for a given latent vector. After the optimal leaf in each tree is identified, the final reconstruction is generated by sampling a point uniformly from the intersection of all the corresponding leaf hyper-rectangles.   \n- Split Relabeling: This approach reconstructs the decision tree to operate in the low-dimensional latent space, such that instances follow the same route as in the original tree. Once a latent vector is routed to a final leaf in this new tree, the corresponding hyper-rectangle from the original tree is identified, and the reconstruction is sampled from that region.   \n- k-Nearest Neighbors (k-NN): This method, accelerated with kd-trees, finds the $k$ closest points in the latent space and identifies the corresponding regions in the original feature space. The final reconstruction is the weighted average of points sampled from these regions, with weights determined by the diffusion map.\n\nThe first two methods proved to be less accurate and more computationally intensive, so the experimental comparisons with other algorithms exclusively use the k-NN approach. Experiments are conducted on 20 tabular datasets with a maximum dimensionality of 59, single-cell RNA-sequencing data, and the MNIST dataset.", "questions": "- How is assumption (A3) enforced in practice, given that common RF implementations (e.g., scikit-learn, XGBoost) perform greedy split selection without guaranteed feature inclusion probabilities?\n- If a split perfectly separates the classes but violates (A4), is it discarded? How are such constraints enforced in practical tree growth?\n- Eq. (1) appears to normalize the kernel differently for each row, potentially making the matrix non-symmetric. Are the resulting eigenvalues guaranteed to be real and the matrix PSD?\n- Can the decoder operate on new samples without needing access to the full training dataset? If not, how is this handled in deployment scenarios?\n- Were the VAE models adequately tuned in terms of architecture and optimization? The result that a tree-based method outperforms VAEs on MNIST is surprising and needs stronger justification.", "limitations": "Discussed in weaknesses.", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- The authors consider a fundamental problem of dimensionality reduction from the perspective of decision trees and provide a thorough theoretical justification for their work, proving several important properties of the adaptive RF kernel.   \n\nWeaknesses:\n\n- The core idea is effectively a Kernel PCA where the kernel is derived from a Random Forest, which is not an entirely new concept. The use of trees as autoencoders is also not novel, as demonstrated by the recently proposed in [1].\n\n- The proposed work does not have a true out-of-sample mapping capability and must rely on approximations. Furthermore, the most viable decoding method (k-NN) requires access to the entire original training dataset to reconstruct a new sample, which can be a significant limitation in practice.   \n\n- The authors' claim that \"having just a single hyperparameter to worry about is a rare luxury in this field\" is an oversimplification. The backbone of the proposed work is a Random Forest, which has many of its own hyperparameters that affect the final tree structures (e.g., depth, number of trees, splitting criterion). Additionally, the diffusion time step $t$ controls the scale of the embedding, and the k-NN decoder requires selecting $k$. The paper's own appendix shows that reconstructions vary significantly with the hyperparameters.   \n\n- A significant portion of the paper is dedicated to developing complex decoders based on constrained optimization (ILP and a LASSO relaxation), yet these methods are shown to be computationally inefficient and ultimately perform worse than the simple k-NN approach. This makes the most novel methodological contributions appear to have little practical value.   \n\n- The experiments are conducted on 20 tabular datasets where the maximum feature dimension is 59. This raises questions about the method's practicality and performance on truly high-dimensional tabular data, which is common in many real-world applications.   \n\n- The experimental evaluation lacks a crucial baseline comparison with Principal Component Analysis (PCA). While the authors focus on sophisticated neural network autoencoders, PCA serves as a fundamental, widely-used linear method for dimensionality reduction. Including PCA would have provided a performance floor and helped quantify the actual benefit of the proposed method's complexity, especially since calculating its reconstruction error is straightforward.\n\n[1] M. Á. Carreira-Perpiñán and K. Gazizov. The tree autoencoder model, with application to hierarchical data visualization. (NeurIPS 25)", "was_revised": true, "final_justification": "All of my concerns have been addressed. In particular:\n- The authors clarified the necessity of a training dataset for out-of-sample mapping for the encoder.\n- The authors provided a clearer explanation of the proof, which was unclear in the main paper.\n- While the idea is not highly innovative, it presents an interesting approach to implementing autoencoders.", "rebuttal": "We sincerely thank reviewer 58sa (henceforth R3) for their detailed review and thoughtful feedback. We reply to each comment/question below:\n\n-”The core idea is effectively a Kernel PCA...” We acknowledge that several authors have explored kernels and RFs before (see our copious bibliography) but want to emphasize that our primary contributions include (1) novel theoretical results establishing important properties of the RF kernel (e.g., that it is asymptotically universal and characteristic); and (2) various new methods for decoding these representations (we are unaware of any authors who have attempted this before).\n\n-“The use of trees as autoencoders is…not novel”: We thank R3 for bringing the tree autoencoder to our attention. We were unaware of this paper and will be sure to discuss it in the revised text. It appears that this method is only for continuous features, not mixed tabular data as we emphasize in our experiments. Moreover, the trees in question use half-plane splits as opposed to axis-aligned splits. This may be helpful in some settings but severs the connection to CART and RFs. One of our aims in this paper is to better understand this widely used class of supervised learners using the tools of nonparametric statistics and coding theory.\n\n-“Must rely on approximations”: We suspect that this comment conflates the Nyström method for approximating a Gram matrix (which we do not use) with the Nyström formula for embedding test points (which we do). The latter is  ubiquitous in autoencoding (see, e.g., IsoMAP, LLE, MDS, and more [1]) and is only “approximate” in the sense that the embedding space is low rank (but this is unavoidable in compression). With fixed $d_Z < n$, we are unaware of any more exact method for embedding test points. We are confused by R3’s judgment that RFAE “does not have a true out-of-sample mapping capability” – would R3 care to elaborate? \n\n-“requires access to the entire original training dataset”: We **do not** require the entire training dataset to reconstruct a new sample. All we need is the RF itself. From this, we create a synthetic dataset with the same leaf assignments as the training data, in the spirit of Feng & Zhou’s eForest [2]. This synthetic data is subsequently used for kNN, not the original training data. See the first paragraph of Sect. 4.3, where this is explicitly explained.\n\n-On hyperparameters: we thank R3 for highlighting this claim, which we agree amounts to an oversimplification. What we meant to say is that RFs are famously robust to hyperparameter selection and are known to work well with default settings in many different applications. Indeed, we did not tune any hyperparameters in our experiments. That said, we do use different numbers of trees for different tasks (heuristically, not systematically), and acknowledge some sensitivity to $k$ in our decoding. We have rewritten the discussion section to better reflect these points.\n\n-On constrained optimization: We begin our discussion of decoders with constrained optimization methods because of their attractive theoretical properties, which we suspect may tempt others to pursue this direction. However, as our work illustrates, there are more efficient alternatives. Proposing sound but intractable objectives before relaxing them into more feasible alternatives is standard practice in computer science. We are confused why R3 judges the kNN method to be of “little practical value” when it is universally consistent and far more efficient and accurate in practice than the ILP or split relabeling approach. We reiterate that we do not require the training data for kNN decoding but generate it on the fly using the forest structure. This novel methodological contribution goes on to fare well in a wide range of experiments.\n\n-On data dimensionality: We direct R3’s attention to our denoising experiment in the main text (Fig. 5), in which we use the top 5000 genes from two scRNA-seq datasets. In addition, we include a transcriptomics experiment with 3572 features in Appx. B2 (Fig. 9). Much like RFs themselves, our method scales well in high dimensions, especially when signals are relatively sparse. \n\n-On PCA: We thank R3 for inquiring about PCA, as our reason for excluding this baseline may have been unclear from the main text. The issue is that PCA is optimized for continuous data and struggles with categorical features, which must be one-hot encoded in preprocessing, artificially increasing dimensionality and making reconstruction a heuristic maximization procedure. As our main benchmark experiment focuses on mixed tabular data, we only considered methods that are specifically designed for handling such inputs. See Appx B, Table 2 for a summary of the breakdown between continuous/categorical features in these datasets. We can add PCA as a naive baseline, but would expect poor results as the proportion of categorical variables and number of category levels increase.\n\n-On assumption (A3): We acknowledge that (A3) may be violated when training a RF with greedy splits on some datasets, a point that should be addressed in the main text. However, three points are in order: (1) Such violations should be rare in the asymptotic regime ($n, B \\rightarrow \\infty$) provided that all features have nonzero entropy. Of course, this is still possible if a feature is fully independent of the outcome, but then it should arguably be excluded prior to model training. (2) In several experiments (including our MNIST experiment), we use completely random forests [2], which explicitly guarantee a uniform split probability on all features. (3) This assumption is ubiquitous in RF theory [3]. Though it may be a slight idealization, it is used to ground results for widely used implementations including of quantile forests [4] and generalized RFs [5]. That said, there is a persistent gap between RF theory and practice [6], a point we will address directly in the revised text.\n\n-On assumption (A4): We are unsure whether we understand R3’s question here. To violate (A4), a split must be “empty”, i.e. place 100% of the available data into one child node and 0% into the other. Such a split could not possibly “perfectly separate the classes”. Moreover, we are unaware of any standard RF implementation that permits such splits.\n\n-On PSD kernels: This is an important point, and we thank R3 for raising it. At first glance, Eq. 1 may appear asymmetric. However, the kernel is provably symmetric and PSD. For full details, see the proof in Appx. A1(a). The high-level intuition is that for any tree $b \\in [B]$ and samples $\\mathbf x, \\mathbf x’ \\in \\mathcal X$, the kernel similarity $k^{(b)}(\\mathbf x, \\mathbf x’)$ must take one of two possible values: either (a) 0, if the samples do not colocate; or (b) the inverse leaf sample size, if they do. So if $\\mathbf x, \\mathbf x’$ colocate in a leaf to which 10 training points are routed, we would have $k^{(b)}(\\mathbf x, \\mathbf x’) = k^{(b)}(\\mathbf x’, \\mathbf x) = 1/10$. Again, we refer R3 to Appx. A1(a) for more details.\n\n-“Can the decoder operate on new samples without…access to the full training dataset?” Yes! See our comment above, and Sect. 4.3 for details. We generate a synthetic training set on the fly and use this for kNN, not the original training data itself.\n\n-“Were the VAE models adequately tuned…?” We are unsure which specific result R3 has in mind. We do not run any experiments with VAEs on MNIST. We do include a convolutional AE experiment on MNIST in the appendix (see Appx B.2, Fig. 8), where the neural decoder clearly outperforms RFAE, as expected. VAEs would presumably also do very well in this experiment. That said, we refer R3 to Feng & Zhou’s eForest paper [2], in which an RF based method for decoding performs very well on MNIST. (However, their method is not a proper autoencoder, for reasons we state in the main text.) \n\n\nReferences\n\n[1] https://direct.mit.edu/neco/article-abstract/16/10/2197/6863/Learning-Eigenfunctions-Links-Spectral-Embedding?redirectedFrom=fulltext \n\n[2] https://aaai.org/papers/11732-autoencoder-by-forest/ \n\n[3] https://jmlr.org/papers/v9/biau08a.html \n\n[4] https://hal.science/hal-05006431v1/file/main.pdf \n\n[5] https://jmlr.org/papers/v7/meinshausen06a.html \n\n[6] https://projecteuclid.org/journals/annals-of-statistics/volume-47/issue-2/Generalized-random-forests/10.1214/18-AOS1709.full \n\n[7] https://proceedings.mlr.press/v32/denil14.html"}, {"review_id": "UNn0FBHwZO", "reviewer": "Reviewer_FErW", "summary": "This paper proposes methods to embed data into compact representations with Random Forest kernels and diffusion maps. It also proposes methods to decode the embeddings back into the original input space, by utilizing methods like k-nearest neighbors. The resulting embedding can be used for downstream tasks.", "questions": "While the reconstruction results with MNIST benchmark appear interesting, they do not show how they compete with the similar results obtained by other baselines like deep neural networks. \nThe experiments reported in Figure 4 do not clearly show that the proposed method is a definitive winner. It would be helpful if the authors analyse when (under what benchmark characteristics) the proposed methods outperforms the other baselines. The authors should also supply computational time information.\nIn Figure 5, the authors claim that the denoising with RFAE helps align the manifolds, thereby minimizing batch effects. However, it is not clear by just looking at the figures. They should give more hints to the readers.\n\n- I wonder if the defintion of the diffusion map should be something like $\\boldsymbol{Z} = \\sqrt{n}\\boldsymbol{\\Lambda}\\boldsymbol{V}^\\top$.", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n+ The authors provide theoretical results including Theorem 3.4, which proves that the RF kernel is asymptotically universal and thus generally well-behaved.\n+ The proposed RFAE methods can encode data which is a mix of continuous, ordinal and/or categorical variables. \n+ The proposed RFAE is a post-processing procedure for a pre-trained RFs which are either supervised or unsupervised.\n+ The authors have shown that RFs can encode and decode data effectively just like deep neural networks do but through entirely different mechanisms. \n\nWeaknesses\n- The proposed methods are computationally demanding. \n- The experimental results do not clearly show the superiority of the proposed methods compared with the other baselines.", "was_revised": true, "final_justification": "I have read the authors' response and other reviewers comments.\nI acknowledge the novelty of the proposed decoder.\nI will keep my score.", "rebuttal": "We thank reviewer FErW (who we will refer to as R2) for their thoughtful review, and address all comments/questions below:\n\n-‘The proposed methods are computationally demanding’: We acknowledge that RFAE is not trivial in terms of computational cost. However, to the best of our knowledge, there are no existing methods for autoencoding mixed-type tabular data that are both faster and easier to implement while achieving comparable or better performance. State-of-the-art methods such as TTVAE [1] and TVAE [2] are also computationally intensive and, in our benchmarks (Figure 4 and Appx. B, Table 2), generally perform worse than RFAE in terms of reconstruction quality.\n\n-‘The experimental results do not clearly show the superiority…’: While Figure 4 provides a high-level overview, we agree that it may not make the overall ranking fully clear. RFAE outperforms all other methods on 12 out of 20 datasets and achieves the best average rank (1.8), with the next closest competitor, TTVAE, at 2.45 (Appx. B, Table 2). We will move this summary table into the main text in the final version to improve clarity. Although no single method dominates across all datasets, the results clearly favor RFAE.\n\n‘While the reconstruction results with the MNIST benchmark appear interesting…’: We include comparisons with convolutional autoencoders in Appx. B.2 (Figure 8), and will move these to the main text in the final version. That being said, we note that random forests are not optimized for image data, and RFAE is not expected to compete with CNN-based autoencoders in this setting. Still, the performance remains respectable and supports the generality of our approach.\n\n‘The experiments reported in figure 4 do not show that the proposed method is a definitive winner…’: We once again acknowledge that Figure 4 alone may have been difficult for readers to evaluate and refer R2 to Appx. B, Table 2 for a definitive summary. \n\n‘The authors should also supply computational time information’: Thank you for this practical suggestion. We did not originally include runtime comparisons due to differences in implementation: RFAE is implemented in R and only runs on CPUs, while all other methods are implemented in Python and make use of GPU acceleration. Additionally, we ran experiments on high-performance computing infrastructure with varying configurations, making uniform comparison challenging.\n\n\nRegardless, in response to this comment, we have since conducted a controlled runtime comparison of all five methods (AE, VAE, TVAE, TTVAE, RFAE) on three small-to-medium datasets (plpn, student, credit), using the same hardware: a laptop with Intel Core i5-10300H CPU, NVIDIA GeForce GTX 1650 (4GB), and 24GB RAM. Each method was run 100 times across varying compression ratios, according to the same specifications as in the reconstruction benchmark. We report the results below, in seconds: \n| Dataset |   AE   |  VAE   |  RFAE  |  TVAE  | TTVAE  |\n|---------|--------|--------|--------|--------|--------|\n| plpn    | 161.6  | 185.9  | 523.8  | 744.2  | 2252.8 |\n| student | 190.9  | 227.8  | 1058.6 | 3611.2 | 5148.7 |\n| credit  | 223.2  | 277.3  | 1379.5 | 2212.5 | 4046.0 |\n\nHere, the results indicate RFAE’s superiority in runtime over the other two state-of-the-art methods in TVAE and TTVAE, while being slower than the naive AE and VAEs – which did very poorly in this benchmark.\n\nAdditionally, we conducted a smaller-scale experiment evaluating RFAE alone across 18 datasets, using a fixed compression ratio of 0.2 (10 runs per dataset). Further datasets will be included in later camera-ready versions. We report the **average** runtime for training and inference (as well as the total time), and their corresponding standard errors, ordered by average total runtime, in seconds:\n| Dataset      | Training Mean | Training SE | Inference Mean | Inference SE | Total Mean | Total SE | #Samples | #Numerical | #Categorical | #Total |\n|--------------|----------------|-------------|------------------|----------------|-------------|-----------|-----------|-------------|----------------|--------|\n| plpn         | 3.714370       | 0.1332954   | 2.747021         | 0.2124611     | 6.461391   | 0.1932904 | 333       | 5           | 3              | 8      |\n| hd           | 3.822021       | 0.1437412   | 3.150167         | 0.2734484     | 6.972188   | 0.2667718 | 298       | 7           | 7              | 14     |\n| forestfires  | 4.450743       | 0.2971702   | 4.388958         | 0.1633418     | 8.839701   | 0.3532595 | 517       | 11          | 2              | 13     |\n| diabetes     | 4.732641       | 0.2556412   | 4.996549         | 0.2930842     | 9.729190   | 0.2435917 | 768       | 8           | 1              | 9      |\n| student      | 6.058696       | 0.4275493   | 6.718135         | 0.1241273     | 12.776831  | 0.4241161 | 649       | 16          | 17             | 33     |\n| credit       | 6.067794       | 0.2360919   | 7.017453         | 0.4312034     | 13.085247  | 0.6467874 | 1000      | 7           | 14             | 21     |\n| car          | 6.630258       | 0.2198116   | 6.909130         | 0.3269201     | 13.539389  | 0.4177712 | 1728      | 0           | 7              | 7      |\n| bc           | 12.171863      | 0.8757384   | 5.946692         | 0.2399783     | 18.118555  | 0.9651042 | 570       | 30          | 1              | 32     |\n| obesity      | 12.329533      | 0.3206506   | 9.920699         | 0.2508384     | 22.250232  | 0.5250324 | 2111      | 8           | 8              | 16     |\n| abalone      | 15.487057      | 0.1780608   | 11.296093        | 0.2203116     | 26.783150  | 0.3053351 | 4177      | 8           | 1              | 9      |\n| wq           | 17.698180      | 0.7578806   | 13.827139        | 0.3397825     | 31.525319  | 0.9755364 | 4898      | 12          | 0              | 12     |\n| mushroom     | 20.174338      | 0.3323456   | 24.847520        | 0.5722045     | 45.021858  | 0.8267018 | 8124      | 0           | 22             | 22     |\n| telco        | 27.032822      | 0.1789329   | 24.761390        | 0.5617190     | 51.794212  | 0.6939195 | 7032      | 3           | 17             | 20     |\n| churn        | 27.056492      | 0.3402298   | 30.225112        | 0.4099171     | 57.281603  | 0.5554646 | 10000     | 6           | 5              | 11     |\n| spambase     | 29.522823      | 0.9029132   | 27.781345        | 0.5143533     | 57.304168  | 1.1237604 | 4601      | 58          | 1              | 59     |\n| dry_bean     | 225.109069     | 8.0783953   | 45.221534        | 0.3427446     | 270.330602 | 7.9269351 | 13611     | 16          | 1              | 17     |\n| king         | 261.519581     | 13.9615926  | 103.128532       | 2.9978589     | 364.648112 | 14.8875831| 21613     | 19          | 0              | 19     |\n\nHere, the results suggests RFAE scales well with dataset size. \n\n-‘In Figure 5, the authors claim that the denoising with RFAE should help align the manifolds…’: To aid with interpretation, we have calculated the average distance between data points from each study before and after batch correction, in PCA space and tSNE space.\n\n|                | PCA     | tSNE    |\n|----------------|---------|---------|\n| Original       | 44.889  | 45.085  |\n| Batch-corrected| 22.289  | 35.661  |\n\n-‘I wonder if the definition of the diffusion map should be something like…’: This is very close to the precise definition that we offer at the end of Section 3 (line 147 of the manuscript), where we simply add the exponent $t$ to record the number of time steps in the Markov process. Since we keep this fixed at $t = 1$ in our experiments, our definition aligns with the one R2 proposes.\nReferences:\n[1]: https://www.sciencedirect.com/science/article/pii/S0004370225000116\n[2]: https://dl.acm.org/doi/10.5555/3454287.3454946"}, {"review_id": "O7irETg3HJ", "reviewer": "Reviewer_B5CF", "summary": "This paper proposes RFAE (Autoencoding Random Forests), a framework that turns a trained random forest into a data-dependent autoencoder. \n\nThe method constructs a kernel from the forest's structure, applies diffusion maps for encoding, and introduces three nonparametric decoders (ILP, k-NN, and split-relabel) to reconstruct the original input. \n\nThe paper also provides theoretical justification for the proposed kernel and decoder consistency. \n\nExperiments show that RFAE achieves good reconstruction quality and offers interpretability benefits.", "questions": "1. How sensitive is the encoding-decoding quality to the number and depth of trees? How it depends on the RF quality?\n2. Is there a way to extend this into a generative model? Any simple ideas?\n3. Can the pipeline be simplified for users? For example, some kind of \"default configuration\" that works well for most datasets?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Pros:\n- The paper tackles a pretty novel problem. It provides an explicit autoencoding framework based on random forests, and this encoder-decoder does not requires training a network. Training-free is especially interesting.\n- Theoretical guarantees: The paper proves kernel universality and consistency/uniqueness (Theorems 3.4, 4.2-4), which strengthens its technical depth.\n- Empirical results are convincing. The method shows competitive or better reconstruction quality compared to neural AEs/VAEs, especially on structured and small-scale tabular datasets.\n- Interpretability: both embedding and reconstruction steps more transparent. You can reason about how the embedding and decoding work, which isn’t true for most neural approaches.\n\nCons:\n- The pipeline is a bit complicated in practice. It involves RF training, spectral embedding (via diffusion maps), and then choosing among several decoder options. It increases implementation and deployment burden, and configs need to be tuned.\n- The method is purely reconstructive. It can’t sample new data like VAEs.\n- It’s quite dependent on the quality of the RF. This sensitivity is mentioned but not thoroughly analyzed.", "was_revised": true, "final_justification": "The responses address my earlier concerns on complexity, sensitivity to RF parameters, and potential generative extensions. In particular, the note that the k-NN decoder suffices in practice and that a default configuration works robustly across datasets improves my confidence in the method's practicality. I will maintain my accept recommendation.", "rebuttal": "We sincerely thank reviewer B5CF (who we will refer to as R1) for their thoughtful and kind review. We address each of the comments below:\n\n-‘The pipeline is a bit complicated in practice…’: While we propose multiple decoder options, in our benchmarks, only the k-NN decoder is used for its simplicity and efficiency. In practice, this reduces the configuration to tuning the random forest (RF) and the number of neighbors for k-NN, making the method considerably easier to deploy than it may initially appear.\n\n-‘The method is purely reconstructive…’:  We concede that RFAE is not designed for data generation. This aligns with classical autoencoder frameworks (including neural methods), which focus on representation learning and reconstruction (as opposed to variational autoencoders, which the reviewer may have in mind). In principle, it could be possible to augment the model with a density estimator for the representation space, but this is outside the scope of our objectives.\n\n-‘It’s dependent of the quality of the RF’: We acknowledge that the reconstruction quality will generally depend on the quality of the underlying RF. However, we argue that any autoencoding method would inherently depend on the quality of its base model, and that in the mixed tabular data setting, RFs are generally a strong and efficient choice. Alternatively, we can view the RFAE as a way to characterize the quality and behaviour of the RF itself, as illustrated in Fig. 2.\n\n-‘How sensitive is the encoding-decoding quality…? How does it depend on the RF quality?’: Regarding sensitivity to depth, we did not constrain tree depth in our experiments and observed consistently strong performance. This suggests good model robustness and avoids introducing extra hyperparameters. For forest size, increasing the number of trees tends to improve performance up to a point. It would also increase the complexity of computing the kernel matrix $K$, increasing granularity and allowing RFAE to capture more complex relationships. Thus, the sensitivity to number of trees and RF quality should generally scale to the complexity of the task.\n\n-‘Is there a way to extend this into a generative model?’: We thank R1 for this interesting question. There exist generative RF models [1], but extending RFAE to synthetic data generation would require some method for sampling from the latent space. Since the latent space of RFAE is not parameterized (not multivariate normal, for instance, as in VAEs), this would presumably require generic density estimators such as KDE. Such ideas are doable in principle, but we reiterate from our above comment that it falls outside of our current objectives.\n\n-‘Can the pipeline be simplified…’ We appreciate this practical concern. A key strength of RFs is that they often perform well with minimal tuning. While we do modify settings across our different experiments (purely heuristically), within each experiment, we kept consistent hyperparameter values. Most notably, we used the same configuration for all datasets in our reconstruction benchmark (500 trees, the ranger default, and k=20), despite their highly variable structure and size. While it is likely the case that an optimal configuration exists for each dataset, our strong performance on this benchmark suggests that the settings we used can be a reasonable default configuration in implementation.\n\n\nReferences:\n[1]: https://proceedings.mlr.press/v206/watson23a.html"}]

Author rebuttal:

Meta-review: The paper proposes an autoencoder based on kernel PCA, using a kernel derived from a trained random forest.

The paper proposes an interesting approach to an important problem and also provides theoretical guarantees. The reviews are positive, and although there were initially a number of concerns, these have largely been addressed by the authors in discussion. I recommend publication.

The authors have promised a number of changes during discussion, and these should be included with care, especially the clarifications in the proof of theorem 3.4.
Decision: Accept (poster)