Graph theory as part of ML/Stats Algorithms

[whock]

Hey everyone,

So far we've been thinking of graph theory tools as being the main tool to do a job that would give us our desired result. Like estimate a connectome, or figure out how to divide the brain into modules. But from another class it seems like people also use graph theory as part of larger algorithms where the graph stuff is an intermediate step to the final answer. Two examples of this are locally linear embedding [1] and Isomap [2]. The purpose of both of these algorithms is for dimensionality-reduction: given a high-dimensional dataset how to extract lower-dimensional info? This is not inherently a graph theoretic problem but both use graph theory to solve their problem. They both define the points in a dataset as nodes and define neighborhoods of nodes to estimate the local or global geometry so it can be projected to a lower-dimensional space (I may have worded this badly - the papers are much bettr).

So what other ways can graph theory be used as part of a larger learning/ML/whatever algorithm? And what does this say about the underlying structure of the relationships in nature? That the same tools can be used on FB friends, datapoints in a learning algorithm, or neurons in the brain? Cool stuff :)

[1] Roweis, Sam T., and Lawrence K. Saul. "Nonlinear dimensionality reduction by locally linear embedding." Science 290.5500 (2000): 2323-2326.

[2] Tenenbaum, Joshua B., Vin De Silva, and John C. Langford. "A global geometric framework for nonlinear dimensionality reduction." Science 290.5500 (2000): 2319-2323.

[mblohr]

A couple that come to mind are Bayesian Belief Networks (probabilistic graphical models used for inferencing) and decision trees (used for decision analysis).

[mblohr]

I'm glad to see someone bring up Isomap and related algorithms - I think they are very interesting and am investigating some applications for work. Which other class discussed these topics?