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.

• How could you have two feature vectors, one specific to the object and other describe pairwise relationships? I know from my experience that the former could describe the variation observed in the data. Anyway you don't have all the pairwise relationships if you do you could simply concat both feature vectors and use an off-the-shelf classifier. May 19, 2018 at 0:58
• Lets see the relationship measure as an engineered feature. Firstly, think upon whether this feature will help your classifier find a pattern or worsen it. Secondly will you have this relationship features for your unseen/ test data in practice. ponder on these points for your dataset. May 22, 2018 at 5:00
• Hi @mankind_008, yes to both of your questions. 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. May 22, 2018 at 20:30
• Hi. The relationship measures looks more like Similarity matrix that can directly be used for clustering but not for classification. For Classification: Rather than using the relationship measure directly as relationship vector , keep the raw inputs/ properties of objects that are used to calculate the relationship measure. This will let the classification algorithm find the best way to figure out a pattern. if this approach gives you better results than try engineer features out of those raw features. It would be better if you could provide some dummy data. May 22, 2018 at 22:07
• Hi @mankind_008 , I am certain that using the intrinsic properties of the objects alone to classify them individually won't be enough, because two identical objects may be accepted/rejected in different collections. I am open to the idea of only describing the objects themselves and letting the ML algorithm learn how to form the relationships, but the relationships must be accounted for, explicitly or implicitly. So this is actually more of a regression problem, where the input is the description of the entire collection, and the output is the binary vector that accepts/rejects each object. May 23, 2018 at 0:21