0
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ The way you have described this problem is incredibly confusing. What are you trying to classify and how are the nodes/edges related to this classification? Are the paired relations relations between features or individual datapoints that are all defined by the same features (variables)? Some sample data and desired/anticipated results might be illuminating. $\endgroup$
    – David Marx
    Commented Nov 14, 2013 at 17:40
  • $\begingroup$ dear David, I explained the goal in my comment below about medicines. each node has just one feature between -10 and 10 which shows solubility of that medicine in water. so if the value of this (node1's feature,node2's feature) is 1, it means that the medicine is effective when we use them together. now, by knowing the other data I want to predict the edges of the left-out medicine, means that with which one of the medicines in the dataset the value of my evaluation expression would be 1. you are right it is not classification, it is like predicting the edges in the graph by having other edges $\endgroup$
    – user667222
    Commented Nov 14, 2013 at 17:57
  • 1
    $\begingroup$ You should add these details to your main question: not everyone reads through all of the comments. $\endgroup$
    – David Marx
    Commented Nov 14, 2013 at 18:34
  • $\begingroup$ i edited the question, i hope it got more clear.. $\endgroup$
    – user667222
    Commented Nov 14, 2013 at 18:40
  • $\begingroup$ I tried to improve your question. I'm afraid I get lost with the last three sentences... $\endgroup$
    – chl
    Commented Nov 14, 2013 at 22:20

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ thanks but don't you think that one feature is very little information for this problem ? specially when the node size grows $\endgroup$
    – user667222
    Commented Nov 14, 2013 at 2:17
  • $\begingroup$ and btw the aforementioned book doesn't contain such chapter. the chapters containing ghraph subject are: "Directed graphical models (Bayes nets)" and "Undirected graphical models (Markov random fields)" and "Exact inference for graphical models" and "Graphical model structure learning" $\endgroup$
    – user667222
    Commented Nov 14, 2013 at 2:31
  • $\begingroup$ Those subjects are probabilistic graphical models. Honestly, it isn't entirely clear to me what you want. I should have commented and asked a question first. My thought was that a Bayes net implicitly solves for the parameters associated with each "node" in your dependency structure. Honestly though, I'm a little lost. Maybe if you reworded your question with the shape of your dataset, how it was made and what you want to infer or use the model for. $\endgroup$
    – Jessica Collins
    Commented Nov 14, 2013 at 2:58
  • $\begingroup$ well the data is about medicine. each medicine has one feature (solubility). there are some medicines that get more effective when we use them together. so the dataset is about testing the two medicine together. now if the medicine (node) gets more effective for lets say an illness then the value of (node1,node2) would be 1. that means there will be an edge in graph. we've done this experimentally and now what i want to do is to leave-one-node-out learning and trying to guess it's edges and in this way to justify my experiment more $\endgroup$
    – user667222
    Commented Nov 14, 2013 at 3:07
  • $\begingroup$ So you want to test if the combination of two medicines is better than the individual ones? $\endgroup$
    – Jessica Collins
    Commented Nov 14, 2013 at 3:36
1
$\begingroup$

Oversized comment warning

You could phrase your problems in terms of link prediction. There is a lot of literature on this for things like social networks and whatnot. The problem that is going to make all (almost all) of of that standard techniques I'm aware of inapplicable is that you've assumed you don't know any of the links for the node you're trying to infer the links for. Typically in link prediction, you assume you know some of the links, and want to infer others.

As you've framed the problem, the graph structure is actually irrelevant. You're simply trying to predict, for a given medicine, which other medicines can be combined with it to make it more effective. This is just multi-label classification. In other words if $M$ is your set of medicines, and for medicine $m \in M$ you have features $\phi(m)$, you want to learn a function $$ h \colon \phi(M) \to 2^M, $$ where $\phi(M) = \{\phi(m) \colon m \in M\}$. I somewhat doubt if that would be very useful or effective in your case given that you only have a single feature for each medicine. It might be worth a try.

Improve this answer
$\endgroup$
5
  • $\begingroup$ (+1) I like how you framed the problem in terms of link prediction. Just for my own interest, what resources have you found to be most helpful in introducing this concept? $\endgroup$
    – Sycorax ♦
    Commented Nov 14, 2013 at 19:41
  • $\begingroup$ @user777 It has been a while since I did any reading on the subject, so my memory is a bit fuzzy. I think I started with this survey by Liben-Nowell and Kleinberg. Either way, it is very well cited and seems fairly approachable. $\endgroup$
    – alto
    Commented Nov 14, 2013 at 21:18
  • $\begingroup$ so you mean that 1: my feature number is small, single feature may not be sufficient but we should try and see 2: leave-one-node-out and its edges could not be applicable and at least i need some of the links to predict the others $\endgroup$
    – user667222
    Commented Nov 14, 2013 at 22:06
  • $\begingroup$ @user667222 1.) Yes, that would be my worry if you decided to treat your problem as multi-label classification. I'm not familiar with the domain though. Maybe this single feature is informative enough. The only way to know is to try. 2.) I think if you want to apply standard link prediction methods, you need to know some of the links for the node you want to predict links for. See the reference I linked in a previous comment. In either case it is worth noting that your leave-one-node out is just leave-one-out cross validation. This technique is covered several times on this site and elsewhere. $\endgroup$
    – alto
    Commented Nov 15, 2013 at 12:20
  • $\begingroup$ well, thank you for your help and was really illuminating. I am going to read that edge prediction paper to understand the problem better and contemplate on how to apply it on my own. $\endgroup$
    – user667222
    Commented Nov 15, 2013 at 20:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.