Introduction
In machine learning, achieving invariance—ensuring a model's output remains unchanged under transformations like permuting elements in a set or nodes in a graph—is a fundamental requirement for many tasks. However, traditional deterministic architectures often face a steep trade-off between expressivity and resource efficiency. For instance, Deep Sets require hidden layers proportional to the input size to achieve universality, while Graph Neural Networks (GNNs) are bounded by the Weisfeiler-Lehman test, leaving them unable to solve basic topological problems like graph connectivity regardless of parameter count.
This paper introduces Randomized Linear Classifiers (RLCs), a novel class of models that leverage external randomness to break these constraints. By relaxing the requirement for deterministic invariance and instead guaranteeing it with high probability, RLCs achieve universal approximation using significantly fewer parameters and memory than standard models.
Methodology: Randomness as a Computational Resource
The core innovation of RLCs is the shift from a single complex deterministic function to a distribution of linear classifiers. The process involves three primary steps:
- Random Weight Generation: A neural network $f_\theta$ takes external randomness as input and outputs the weights and bias for a linear classifier.
- Linear Inference: This sampled classifier is applied to the input data.
- Amplification: The process is repeated $m$ times, with the final prediction determined by a majority vote.
The authors utilize classical representation theorems from probability theory to design these weight distributions. Specifically, they employ de Finetti’s theorem for set invariance, the Aldous-Hoover theorem for graph exchangeability, and Freedman’s theorem for spherical data. These foundations allow RLCs to remain invariant to specific group transformations by construction.
Experimental Evaluation
The effectiveness of RLCs was evaluated on three synthetic tasks designed to highlight the theoretical and practical limitations of existing architectures:
- Sorting Task: A set-based task where the label depends on the sorted order of elements.
- Sign Task: A set-based task requiring the model to predict the sign of the sum of signs of input elements.
- Connectivity Task: A graph-based task where the model determines if a graph (sampled from a $G(n, p)$ model) is connected. This is a known "blind spot" for standard GNNs.
Key Results and Insights
Universal Approximation and Efficiency
The authors prove that RLCs can approximate any binary classification problem with a smooth boundary. Crucially, the resource requirements for Randomized Set Classifiers (RSetCs) depend on the task's complexity (smoothness) rather than the input sequence length, effectively decoupling parameter count from input size.
Generalization and Robustness
In the Sorting Task, RSetCs demonstrated superior generalization compared to Deep Sets, particularly in "Size OOD" (Out-of-Distribution) scenarios where the model is tested on sets larger than those encountered during training. RSetCs achieved these results while using smaller hidden layers, confirming their parameter efficiency.
Bypassing GNN Limitations
In the Connectivity Task, RGraphCs maintained high accuracy even as graph sizes increased. In contrast, standard GNN performance plummeted toward the level of a constant classifier. This confirms that RLCs can solve tasks that are theoretically "unsolvable" for traditional message-passing architectures by tying expressivity to whether a decision can be tested via an inner product.
Practical Implications and Future Work
RLCs offer unique advantages for edge computing. Because the heavy lifting (generating weights) can be done server-side, a low-power device only needs to perform simple linear computations. This preserves battery life and enhances data privacy.
Despite these strengths, the current framework is limited to binary classification. Future research is needed to extend RLCs to multi-class problems and regression. Additionally, while synthetic tests are promising, evaluating RLCs on large-scale real-world datasets—such as molecular graphs or 3D point clouds—remains a critical next step. Exploring broader invariances, such as 3D rotation ($SO(n)$), could further expand the utility of this randomized approach.
Summary updated