Sampling Large Data on Graphs

Ilan Shomorony, A. Salman Avestimehr

Introduction

Graphs arise as a natural way to represent large datasets obtained in many practical contexts, such as social, biological, and sensor networks . For a graph $G=(V,E)$ , the data can be embedded as scalar or vector-valued labels on the vertices $v\in V$ , while the weights $w_{e}$ of the edges $e\in E$ represent some underlying structure in the data. As an example, one can think of a graph where each vertex corresponds to a different movie title, and the edge weights represent a measure of similarity between the movies. In this case, the graph data can be the ratings given by a person to each movie title, and one would expect movies connected by edges with large weights to be given similar scores.

Particularly in big data scenarios, a natural question is how well a given sample of the data points can be used to estimate the remainder of the data. In other words, is it possible to predict the data point at one vertex by interpolating the data from another set of points? In the context of the movie ratings data, this can be viewed as the celebrated “Netflix” challenge , or more in general as data prediction problems for recommendation systems. Other applications include semi-supervised learning of categorized data and ranking problems .

Intuitively, the reason why this graph data interpolation should be at all possible is that the graph contains information about the underlying data structure; thus, a set of samples together with the graph edge weights should reveal information about the missing data points. As pointed out in , this can be viewed as assuming that the graph data is slow-varying or smooth on the graph. Therefore, analogous to the classical signal processing domain, where a smooth signal (i.e., a signal with a small bandwidth) can be recovered from a small set of samples, smoother graph signals should have a higher degree of redundancy in their data, and should be recoverable from a smaller set of samples. These ideas are part of what motivates the emerging field of signal processing on graphs and, in particular, the graph data sampling theory .

Classical sampling theory states that a signal with bandwidth $W$ can be recovered if we sample at a rate $2W$ . Therefore, given a sampling rate, one can compute the cut-off frequency; i.e., the highest frequency component that a given signal may have so that it is recoverable from the samples, which is known as the Nyquist frequency. In , the authors seek a similar characterization in the context of graph signals, by using tools from spectral graph theory. The notion of frequency is introduced via the eigenvalues and eigenvectors of the graph Laplacian. In order to obtain a sampling theorem for graph signals, they consider two questions: What is the maximum possible bandwidth (the cut-off frequency) of a graph signal such that it can be recovered from a given subset of nodes, and conversely, what is the smallest possible subset of nodes that allows the correct recovery of all signals up to a given bandwidth?

Several works prior to already dealt with these questions to some extent. For example, in , the cut-off frequency is established for bipartite graphs. For arbitrary graphs, sufficient conditions for unique recoverability from a sampling set are stated in , and then used to derive a lower bound on the cut-off frequency in . In , the authors make significant progress towards establishing a sampling theory for graph signals. They present linear-algebraic necessary and sufficient conditions for a given set of samples to correctly recover signals up to a given bandwidth, which is then used to obtain an increasing sequence of lower bounds on the cut-off frequency of a given sampling set. The drawback of such a characterization is that it is unclear in general whether this method can indeed provide arbitrarily close approximations to the cut-off frequency and, if so, how far in the sequence of lower bounds one needs to go.

In this work, we show that the linear-algebraic conditions from can be used in a different way, which yields an exact characterization of the cut-off frequency. This is done in Section 3. Then, in Section 4, we show that this characterization can be used to provide efficient algorithms for finding optimal sampling sets, in two senses. First, what is the subset of nodes of a given size with the largest cut-off frequency? Second, what is the smallest subset of nodes with a given cut-off frequency? In addition, in Section 5, we study the performance of random uniform sampling when compared to the centralized optimal sampling provided by the proposed algorithms.

Notation and Background

Characterizing the Cut-off Frequency

The cut-off frequency $\omega_{c}({\mathcal{S}})$ of a set ${\mathcal{S}}$ is the largest $\omega$ such that ${\mathcal{S}}$ is a uniqueness set for $PW_{\omega}(G)$ .

Suppose that ${\bf h}\in M\cap L_{2}({\mathcal{S}}^{c})$ with ${\bf h}\neq{\bf 0}$ . Then, for any ${\bf f}\in M-\{{\bf 0}\}$ , we have ${\bf g}={\bf f}+{\bf h}\in M$ . But this implies that ${\bf f}({\mathcal{S}})={\bf g}({\mathcal{S}})$ and ${\bf f}\neq{\bf g}$ . By Definition 1, ${\mathcal{S}}$ is not a uniqueness set for $M$ . Conversely, suppose $M\cap L_{2}({\mathcal{S}}^{c})=\{\bf 0\}$ . Take any ${\bf f},{\bf g}\in M$ with ${\bf f}({\mathcal{S}})={\bf g}({\mathcal{S}})$ . Then we must have ${\bf f}({\mathcal{S}})-{\bf g}({\mathcal{S}})={\bf 0}$ , and ${\bf f}-{\bf g}\in M\cap L_{2}({\mathcal{S}}^{c})$ , implying that ${\bf f}={\bf g}$ . ∎

In , the authors utilize the characterization of a uniqueness set given by Lemma 1 to estimate the cut-off frequency of a set ${\mathcal{S}}$ . More precisely, they show that ${\mathcal{S}}$ is uniqueness set for $PW_{\omega}(G)$ for any $\omega\leq\Omega_{k}\triangleq(\sigma_{1,k})^{1/k}$ , where $\sigma_{1,k}$ denotes the smallest eigenvalue of the reduced matrix $({\mathcal{L}}^{k})_{{\mathcal{S}}^{c}}$ , obtained by restricting ${\mathcal{L}}^{k}$ to the rows and columns corresponding to nodes in ${\mathcal{S}}^{c}$ . Since, as shown in , $(\sigma_{1,k})^{1/k}$ is increasing in $k$ , it provides an increasing sequence of lower bounds on the cut-off frequency $\omega_{c}({\mathcal{S}})$ .

As it turns out, Lemma 1 can be used in a different way in order to characterize $\omega_{c}({\mathcal{S}})$ exactly. Notice that, from (2), ${\mathcal{S}}$ is a uniqueness set for $PW_{\omega}(G)$ if and only if $PW_{\omega}(G)\cap L_{2}({\mathcal{S}}^{c})=\{\bf 0\}$ . Now, since $L_{2}({\mathcal{S}}^{c})={\rm span}\{{\bf e}_{j}:j\in{\mathcal{S}}^{c}\}$ , where ${\bf e}_{j}$ is the $j$ th standard basis vector, characterizing the largest $\lambda_{i}$ for which (2) holds with $M=PW_{\lambda_{i}}(G)$ can be done by simply testing, for $i=1,...,n$ , whether

This can in fact be done easily for each $i$ by noticing that

which implies that (3) holds if and only if the matrix $[{\bf u}_{1},...,{\bf u}_{i},{\bf e}_{j}:j\in{\mathcal{S}}^{c}]$ is full column rank. Therefore, the cut-off frequency $\omega_{c}({\mathcal{S}})$ can be calculated exactly as described above and we have the following result:

For a graph $G$ with normalized Laplacian ${\mathcal{L}}$ with eigenvalues $0=\lambda_{1}\leq\lambda_{2}\leq...\leq\lambda_{n}$ and corresponding eigenvectors ${\bf u}_{1},...,{\bf u}_{n}$ , the cut-off frequency of a subset of nodes ${\mathcal{S}}$ is given by

Hence ${\mathcal{S}}$ is a uniqueness set for $PW_{\omega}(G)$ if and only if $\omega\leq\omega_{c}({\mathcal{S}})$ .

The advantage of computing the cut-off frequency using Theorem 1 in comparison to the previously known estimate is illustrated in Fig. 1. We randomly generated a $300$ -node graph by adding each edge with probability $0.4$ and choosing the weight of each existing edge independently and uniformly at random from $(0,1)$ . We then selected a set ${\mathcal{S}}$ with $30$ nodes at random, and compared $\omega_{c}({\mathcal{S}})$ to the lower bound given by $\Omega_{k}=(\sigma_{1,k})^{1/k}$ for increasing values of $k$ . As shown in Fig. 1, the lower bound does seem to converge to $\omega_{c}({\mathcal{S}})$ but it seems to require large values of $k$ to be arbitrarily close.

In addition, we point out that more important than the actual value of $\omega_{c}({\mathcal{S}})$ is the number of eigenvalues of ${\mathcal{L}}$ below $\omega_{c}({\mathcal{S}})$ . That corresponds to the dimension of the subspace $PW_{\omega_{c}({\mathcal{S}})}(G)$ , which is the set of graph signals that can be correctly reconstructed from ${\mathcal{S}}$ . While for $k=120$ , the approximation given by $\Omega_{k}$ to $\omega_{c}$ seems to be good, as shown in Fig. 1, it implies that ${\mathcal{S}}$ can reconstruct signals in a subspace of dimension $17$ , as opposed to $30$ . Therefore, if we use the true cut-off frequency value as opposed to its estimate in an interpolation technique such as the one described in , a better prediction of the missing data can be obtained. Finally, we notice that since $|{\mathcal{S}}|=30$ , by dimensionality considerations we cannot expect ${\mathcal{S}}$ to reconstruct signals in a space with dimension larger than $30$ . Hence, ${\mathcal{S}}$ is optimal in the sense of having maximum cut-off frequency, even though it was chosen at random. As we discuss in Section 5, this seems to be the expected behavior, provided that the graph is connected.

Finding Optimal Sampling Sets

Besides characterizing the cut-off frequency of a set ${\mathcal{S}}$ , the approach from the previous section can be used to answer two optimization questions related to finding optimal sampling sets. Notice that finding an optimal sampling set, i.e., a set ${\mathcal{S}}$ with the highest cut-off frequency under some constraint, has significant practical relevance, since in big datasets, we are often interested in finding a small yet representative sampling set. The following two results and their proofs can be understood as providing approaches to selecting optimal sampling sets from the point of view of their cut-off frequencies.

The first problem we consider is to find, for a given $\omega$ , the smallest set ${\mathcal{S}}$ with $\omega_{c}({\mathcal{S}})\geq\omega$ .

can be solved in polynomial time and an optimal ${\mathcal{S}}$ has size $|{\mathcal{S}}|=m$ , where $\lambda_{m}$ is the smallest eigenvalue of ${\mathcal{L}}$ such that $\lambda_{m}\geq\omega$ .

From Theorem 1, we conclude that $w_{c}({\mathcal{S}})\geq\lambda_{m}\geq\omega$ . Moreover, for any ${\mathcal{S}}^{\prime}$ with $|{\mathcal{S}}^{\prime}|<m$ , we will have $|({\mathcal{S}}^{\prime})^{c}|>n-m$ , and we must have

and Theorem 1 now implies that $\omega_{c}({\mathcal{S}}^{\prime})\leq\lambda_{m-1}<\omega$ .

Computing a set ${\mathcal{S}}$ of minimum size satisfying $\omega_{c}({\mathcal{S}})\geq\omega$ requires first performing the eigendecomposition of ${\mathcal{L}}$ , and then constructing the basis $[{\bf u}_{1},...,{\bf u}_{m},{\bf e}_{j_{1}},...,{\bf e}_{j_{n-m}}]$ as described in Algorithm 1, all of which can be done in polynomial time, since ${\mathcal{L}}$ is positive semidefinite. ∎

The second optimization question is to find, for a given size, the sampling set ${\mathcal{S}}$ with the maximum cut-off frequency. As it turns out, the same algorithm provides an efficient solution to this problem.

can be solved in polynomial time and the optimal ${\mathcal{S}}$ has $\omega_{c}({\mathcal{S}})=\lambda_{m}$ .

We know from the previous corollary that we can find a set ${\mathcal{S}}$ of size $|{\mathcal{S}}|=m$ and cut-off frequency $\omega_{c}({\mathcal{S}})=\lambda_{m}$ using Algorithm 1 in polynomial time. Moreover, for any ${\mathcal{S}}$ with $|{\mathcal{S}}|\leq m$ , we have $|{\mathcal{S}}^{c}|\geq n-m$ , and Theorem 1 implies that $\omega_{c}({\mathcal{S}}^{\prime})\leq\lambda_{m}$ . ∎

In Fig. 2, we illustrate the application of Algorithm 1 to find the optimal set ${\mathcal{S}}$ in two scenarios. First we consider a random graph with $200$ nodes on the plane, where edges are added between nodes whose distance is below a fixed threshold and all edges have weight $1$ . In Fig. 2, we see the optimal set ${\mathcal{S}}$ with $|{\mathcal{S}}|=25$ . As intuition would suggest, the nodes in ${\mathcal{S}}$ try to cover the graph evenly, and the number of nodes in each connected component seems proportional to its size.

In Fig. 2, we consider a cycle with $200$ nodes and additional edges connecting a set $A$ of $4$ consecutive nodes to a set $B$ of $40$ consecutive nodes. We see that an optimal set ${\mathcal{S}}$ contains one node in $A$ and is essentially evenly distributed over the nodes in $V-B$ , since nodes in $B$ are close to the one node chosen from $A$ .

Performance of Random Sampling

As we noticed in Section 3, for the example illustrated in Fig. 1, a random set ${\mathcal{S}}$ of size $|{\mathcal{S}}|=30$ has $\omega_{c}({\mathcal{S}})=\lambda_{30}$ . From Corollary 2, this is in fact an optimal choice of ${\mathcal{S}}$ under the constraint $|{\mathcal{S}}|\leq 30$ . Theorem 1 in fact suggests that this should be the case under fairly general conditions, since it is reasonable that by picking a set of $n-m$ standard basis vectors ${\bf e}_{j_{1}},...,{\bf e}_{j_{n-m}}$ at random we will have

Notice however that, if the graph has disconnected components, random sampling may lead to one of the components not being sampled at all and, as illustrated in the example in Fig. 2, the optimal sampling set tries to keep the number of samples per connected component proportional to the size of the component. We conjecture the following:

Consider a connected graph $G=(V,E)$ and an arbitrary set ${\mathcal{S}}\subset V$ with $|{\mathcal{S}}|=m$ . For almost all assignments of the edge weights, if we let $0=\lambda_{1}\leq...\leq\lambda_{n}$ be the eigenvalues of the normalized Laplacian ${\mathcal{L}}$ ,

implying that $\omega_{c}({\mathcal{S}})=\lambda_{m}$ .

Numerical experiments where we assign the weights to the edges of a connected graph at random give strong support for this claim. If true, this shows that, in terms of the cut-off frequency, sampling uniformly at random from the nodes in a graph is optimal. From a practical point of view this is significant since it would obviate the need for a centralized algorithm such as Algorithm 1 to determine an optimal sampling set.

Nonetheless, this also shows a drawback of choosing a sampling set solely based on the cut-off frequency. For example, consider the graph in Fig. 3. The left half of the $100$ nodes is densely connected, while the right half is not. As intuition suggests, the optimal sampling set of size $|{\mathcal{S}}|=30$ picks many more points from the right half of the graph.

Acknowledgements

We would like to thank Aamir Anis and Prof. Antonio Ortega for motivating the problem studied in this paper and for fruitful discussions on the subject.