1
$\begingroup$

Imagine a world where we have places (e.g., cities, restaurants, national parks, etc.) but no roads connecting them.

Our objective is to build roads connecting any two places while going through some given places. For instance, connect Seattle to San Francisco and make sure the connection goes through restaurants X and Y and goes through the Red Wood national park. Note, there is not necessarily one possible road, hence multiple options as output are also acceptable.

We have some roads as examples to train the system. For instance, we have a road from Washington DC to Boston that goes through Baltimore.

So, the input to a machine learning system will be a list of strings (e.g., city names and places to go through) and the expected output is a tree/graph that connects the given points.

(Note, this cannot be a graph traversing problem, as a path the connects the points does not exist.)

I want a machine learning model that can produce/generate a novel graph in the output given a set of labels.

Any thoughts on what ML machine learning methods I can use and where to start?

Update 1

Note that I have neither of the following:

  1. A graph of route(s) from Seatle to San Francisco;
  2. A larger graph that contains a route from Seatle to San Francisco.

Instead, I have graphs for routes from Los Angles to Texas (with stops for eating and seeing landscape), from Milan to Rome, and etc.

Therefore, I think this is not a graph searching problem.

Update 2

I take that the initial question was not clear, so I reworded it.

Improve this question
$\endgroup$
4
  • $\begingroup$ It sounds a little like a Markov Decision Process. I'd imagine that any way that you frame the problem, it will be a graph searching algorithm that solves it rather than any machine learning. $\endgroup$
    – Cameron Chandler
    Commented Oct 21, 2020 at 6:01
  • $\begingroup$ This will need to generate novel graphs. $\endgroup$
    – Dr. Strangelove
    Commented Oct 21, 2020 at 21:15
  • $\begingroup$ I think this is a graph problem, where the initial graph is a fully connected graph since potentially every road can be built. The question is how you should determine the weights of the edges, based on interconnecting the maximum of cities in the most efficient way. $\endgroup$
    – Erwan
    Commented Dec 13, 2020 at 21:20
  • $\begingroup$ @Erwan in my application, I do not have a "complete" prior knowledge of the edges as some nodes cannot be connected to each other. Therefore, I'm not sure if first building a fully connected network and then traversing and weighting the edges would be feasible/appropriate for my application. $\endgroup$
    – Dr. Strangelove
    Commented Jan 20, 2021 at 5:59

1 Answer 1

Reset to default
1
$\begingroup$

Your graph is characterized by a set of nodes and edges. It means given a start point x, show me the next node z1, then from z1 show me z2 and so on. This looks like the definition of graph-searching algorithm.

However, maybe by definining a 'cost function' that you want to optimize (minimize or maximize) you can convert it to a supervised learning task. Basically, given a graph composed of weighted nodes and edges, you want to choose a subset (E,V) that minimzes the cost function.

I am not sure this problem fits a generative problem (as you emphasize on the word generate) whose goal is to learn a distribution.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the comment, please see my updated question. $\endgroup$
    – Dr. Strangelove
    Commented Oct 29, 2020 at 7:01

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.