I've been working on some problems that are heavy on graph theory. Specifically, I work in the chemistry domain and use the connectivity graph of small molecules or a geometric separation graph to describe the chemical of interest. I've wanted to explore this representation further, but I'm having a hard time finding references (books, articles, web pages, etc.) that describe feature extraction or feature development from graphs. If anyone has some recommendations, please post them. -Kirk

You'll have to describe what sorts of "features" you're trying to extract. Subgraph isomorphism is a known-hard problem. Fuzzy subgraph isomorphism, I wouldn't even know where to start.

Sorry for the lack of explanation.

I was looking for for the ability to extract numerical features from the graph itself. Given that the nodes have identities (elements in this case) and the edges have identities (bonds in this case), I would like to be able to extract numerical features from the graph itself which can be used for pattern recognition (classification/regression). I've seen features that involved such things as sum of vertex degrees, edge count, etc. and more esoteric features like minimum eigenvalues, maximum eigenvalues, eigenvalues of the inverse and so on. But, I've never been able to find a reference that describes what types of things can be done with the graph in order to extract such features. I'm sure there are millions of things that could be done, but what has been done? How was it applied? What domain was it used in?

Anything that could relate to extracting a set of descriptive features from a give graph that might be useful (speculatively useful is OK, too) for pattern recognition.

This might be a good place to start. Spectral graph theory is a pretty obscure discipline, but you might be able to tease out useful techniques.

Thanks for the link. I'll give it a shot.

Try looking at Alessandro Sperduti's page: http://www.math.unipd.it/~sperduti/per-web-06-2004/node3.html

Gil,

Thanks for the link!! One paper on that page in particular is perfect - Design of New Biologically Active Molecules by Recursive Neural Networks

If anyone has links to anything similar, please post them.

-Kirk