 |
 |
|
Spectral Methods for Graphs
Graph FeaturesIn recent work, we have shown how to extract features from the eigenvalues and eigenvectors of graph Laplacians. These features can be used to represent the structure of a graph and are very quick to compute. They also allow matching, clustering and modelling to be performed in vector space rather than graph space. We have also shown how to extend these constructions to attributed graphs. Considerable challenges remain however, because the feature space is high-dimensional and does not always respond in a straightforward way with changes in graph structure. The feature space is also rich enough to allow the original graph to be reconstructed from the features.
Generative ModelsWe are also conducting research into generative models of graphs. These are defined as probability distributions over the space of graphs which then allow new graphs to be generated which are drawn from the distribution. This not onlyallows the generation of random graphs, but also brings to bear a wide range of techniques from statistical pattern recognition which are based on generative models of the data. To tackle this problem, we turn to the spectral decomposition to produce a robust and structurally salient vectorial representation of the graph. This representation can be used to reconstruct the original graph and allows the application of standard probability models.
|