Binary classification based on pairwise relationships I have a seemingly esoteric machine learning problem and I'm not sure where to start looking at literature.

I am trying to train a binary classifier that accepts/rejects each object in a collection of N objects. As input, it is given feature vectors describing each object, as well as feature vectors describing pairwise relationships between each object. The list of pairwise relationships is not complete, but not very sparse: approx 1/3 of the possible pairs are described.

The ground truth is the accept/reject label of each object, and I have a set of collections to train on. From domain knowledge I know that the global properties of the entire collection are important to determining the classification of the object, which is why I would like to use the pairwise relationships in classification.

Currently to classify the objects we are using a greedy algorithm that uses a rule-based score based on the relationship measure. (We start with an object that we trust to be very good, then we greedily add the other objects until no more objects have a positive total relationship score in relation to the already-accepted subset) So we know that the relationship measure is important and will be present in the test data. I am attempting to improve on this by using a machine learning approach.

My first attempt was to treat each pairwise relationship I have as a data point, and concatenate the two self-descriptor vectors to the relationship vector. Then, I labeled this as "1" if they were an accept-accept pair, or "-1" if it was an accept-reject pair. Then, during testing, I could put these predictions in one affinity matrix for each collection (if the pairwise relationship is unknown, it that matrix entry is left as 0) and use spectral clustering ("accept" and "reject" objects would have opposite signs in the first eigenvector). However, this performed worse than using only the self-descriptors for classification. I suspect this is because there is a considerable deficiency in this training protocol -- unlike the rule-based score we currently use, there is no indicator of how strong the agreement or disagreement between the two objects is.

Therefore, I would like to create a classifier that looks at the entire collection of self-descriptors and pairwise relationships, and uses the accept/reject labels directly as ground truth somehow.
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.