I have a dataset of paired relations, indicating whether $a$ is in relation with $b$. It is better to consider this dataset as a graph where each node has a numerical value as its feature. Let's say this feature could possibly be varying between $-10$ and $10$. Now the question is: Are two nodes related one to each other, or not? If they are then the value of this expression is $1$: $(text{node}_1,text{node}_2) = 1$, and there will be an edge between them in the graph, otherwise $(text{node}_1,text{node}_2) = 0$, which means that there will be no edge between $text{node}_1$ and $text{node}_2$.

Let's put the problem in context this way. The data is about medicine. Each medicine has one feature (solubility), and some medicines are more effective when used together. So the dataset is about testing the two medicine altogether. Now if the medicine (node) gets more effective for, say, an illness then the value of $(text{node}_1,text{node}_2)$ would be 1, or in other words there will be an edge in the graph. We've done this experimentally, but now what I want to do is to leave-one-node-out learning and trying to guess it's edges, for I could add more support toward my experiment. Now that I have the data, I want to predict the edges of a new node in a way that each time I am leaving one node out or leave-one-node-out. I am leaving the node and all its connections(edges) out and from the information I have about the other nodes in dataset I want to predict the edges of the node which i left out.

My question is what is the best method/algorithm and solution for my problem?

**Contents**hide

#### Best Answer

This is a problem for Probabilistic Graphical Models. "Machine Learning: A Probabilistic Perspective" has an excellent chapter on the subject. "Probabilistic Graphical Models" is a more intensive study of the subject.