Weighted Spectral Embedding of Graphs

Many types of data can be represented as graphs. Edges may correspond to actual links in the data (e.g., users connected by some social network) or to levels of similarity induced from the data (e.g., users having liked a large common set of movies). The resulting graph is typically sparse in the sense that the number of edges is much lower than the total number of node pairs, which makes the data hard to exploit. A standard approach to the analysis of sparse graphs consists in embedding the graph in some vectorial space of low dimension, typically much smaller than the number of nodes [15, 19, 4]. Each node is represented by some vector in the embedding space so that close nodes in the graph (linked either directly or through many short paths in the graph) tend to be represented by close vectors in terms of the Euclidian distance.