Binary classification based on pairwise relationships
The solution I needed was permutation-equivariant neural networks. The application in the paper is not classification, but nevertheless it has the correct properties to adapt to classification.