A Poincaré Inequality and Consistency Results for Signal Sampling on Large Graphs

We thank the reviewer for their time and thoughtful comments and will now address the questions raised.

1. Density of the paper and more motivation and reference needed.
   We thank the reviewer for their patience and would like to reassure them that we are working to make the paper more readable for the general ML audience. We have included a further explanation of Poincaré inequality in this setting, as well as Aldous and Hoover’s reference, which we agree is also a natural motivation for graphons, especially if one is to extend this framework to sparser limits.

2. Sparse graphs.

• We completely agree with the reviewer that developing similar frameworks for sparse graph limits is tremendously useful but at the same time tremendously difficult. In particular, most notions of sparse graph limits do not admit continuous eigenvalues/eigengaps at the limit. For some pathological cases, eigenvalues may not even exist for the limit object! As our framework is built on Fourier transform of the Hilbert-Schmidt operator of graphon, the degeneracy in sparse limit spectrum simply means that a lot more care is needed to define a unitary transform for sparse graph limits.
• Our results, however, also shed some positive light in the sparse case: in our proposition 4, after a large enough number of node N, assuming the generating graphon model admits nice mixture model reparameterization, the size of the uniqueness set no longer increases with the number of nodes n > N. This suggests that even in the limit of infinitely many nodes, there may still be a finite uniqueness set, which might be possible to be picked out by a more fine-grained topology than that offered by the Lebesgue measure!

We thank the reviewer for their time and thoughtful comments and will now address the questions raised.

1. Heavy notations/definitions/theorem statements.
   We have and will continue to work to simplify some of the notations in the main paper. For a simplified setting of stochastic block models where these notions are not necessary, please refer to Proposition 5 in Appendix D for a simplified exposition. To state a more general theorem for more complicated and realistic graphon models, we unfortunately need to build on foundational notions uncovered by Schiebinger et al. in their seminal paper in 2015. We have included all relevant definitions and intuitions for these definitions in Appendix F.

2. The algorithm was stated rather informally and whether the theorems in Section 4 imply a guarantee for the stated algorithm for node classification.

• When the conditions stated in theorem 3-5 are met, these theoretical guarantees do apply to the algorithm stated in section 5, provided that in step 2 of the algorithm, we use Gaussian elimination. This is formalized in Proposition 4 where with a large enough n, uniqueness set of G_n are clean samples from each mixture component (Theorem 4), which can be found via Gaussian elimination (Theorem 5). We have stated this more clearly in the main paper.
• However, it should also be noted that in order to make our algorithm even faster and competitive with existing finite graph sampling methods such as Anis et al. 2016, we use the same greedy heuristic as Anis et al., in place of Gaussian elimination in our experiments, as discussed in the paragraph following the algorithm. Our proposed algorithm is also highly flexible in practice and is amenable to more sophisticated sampling tools, such as via a local clustering algorithm in step (3). For these more sophisticated add-ons, theoretical guarantees are left open. However, we believe that the demonstrated flexibility is extremely important in making sure that our framework is useful in practice, while still being built on solid theoretical foundations.

Reference: A. Anis, A. Gadde, and A. Ortega. Efficient sampling set selection for bandlimited graph signals using graph spectral proxies. IEEE Trans. Signal Process., 2016.

We thank the reviewer for their time and thoughtful comments and will now address the questions raised.

1. Theorem 2 (Poincaré inequality)
   We thank the reviewer for pointing out a missing definition! Indeed the reviewer is correct that there is a canonical inclusion of $L_2(S)$ in $L_2([0,1])$ when $S$ is a subset of $[0,1]$: a graphon signal $X$ is in $L_2(S)$ if it is in $L_2([0,1])$ and the support of $X$ is in $S$. In other words, $X$ is $0$ everywhere outside $S$. The short proof of Theorem 3 details the intuition for this definition. But at a high level, we want to show that $S$ is not informative by showing that any bandlimited signal $X, Y$, with $X - Y$ supported only on $S$ (i.e. $X$ in $L_2(S)$), must have ${\|| X - Y \||}\_{L_2} = 0$. In other words, annihilating all parts of the signals from $[0,1]\S$ makes these signals indistinguishable (in $L_2$). To show this, we upper bound $||X - Y||\_{L_2}$. This is done via the Poincare inequality: $||X - Y||\_{L_2} \leq {\rm constant} ||\mathcal{L}(X - Y)||\_{L_2}$. The right hand side is then at most $\lambda ||X - Y||\_{L_2}$ due to bandlimitedness of $X$ and $Y$. $||X - Y||\_{L_2} = 0$ quickly follows.
2. Robustness to perturbation

• We agree that a perturbation theoretic analysis into the construction of these uniqueness sets is a very important and interesting future direction. In short, it is reasonable to expect the graphon uniqueness set to be robust to perturbation since Theorem 1 and Proposition 2 connect uniqueness sets to full-rank systems, and full-rankedness is a robust property: a matrix is full-rank iff its determinant is nonzero, so a small enough perturbation on the eigenvalues of the system will not cause the determinant to become 0. In fact, much of the technical part of the proof uses Gershgorin circle theorem to show full-rankedness of different systems!.
• To give another intuition, by Proposition 4, if the limiting graphon admits a nice (small difficulty function) mixture model reparameterization, we have that after a finite number of nodes $N$, uniqueness set of the finite graph $G_n$ does not change for all $n > N$. This implies that in the limit of infinitely many nodes, there is a uniqueness set with discretely many nodes. The theory of graphon is not enough to capture this fine-grained limit since graphons are $L_2$ functions and are only defined up to a set of measure 0. However, any measurable subset (let’s say union of intervals in general positions) containing these N points should contain enough information to be a uniqueness set themselves. Thus, a small perturbation of the boundaries of these intervals would not affect uniqueness of the computed graphon uniqueness set unless one of these N points lies exactly on a boundary of an interval, which is unlikely. In practice, q - the size of the uniqueness set, is a tunable hyperparameter that practitioners can control to obtain a tradeoff between compute-saving and information loss, in a case where bandwidth limit is not known a priori.

We thank the reviewer for their time and thoughtful comments and will now address the questions raised

1. Compare computational efficiency with existing techniques, and how does the proposed algorithm scale with the size of the graph?

• In the last paragraph of Section 5 on page 8, we provided a runtime analysis of the main computational step (step 2) of our sampling algorithm compared to the greedy heuristics in Anis et al., 2016. We have made this comparison more explicit in the main paper. The specific runtime of Anis et al. 2016 has been carefully analyzed and compared with other methods in their paper, and we will include these findings in the Appendix for completeness, together with our own numerical runtime.
• While we do gain some efficiency in step (2) of our algorithm compared to existing graph sampling algorithms, the main advantage and efficiency of our proposed method come from not having to redo this sampling step every time the graph grows in size. This is due to the fact that the sampled structures follow the same graphon. We also experience significant savings in downstream analysis tasks. For instance, training GNNs on smaller graphs (of size q << n) and transferring to testing on larger graphs, or computing positional encoding of size q and then 0-padding to get positional encoding of size n, all benefit from massive savings since the learning algorithms only interact with these smaller graphs.
• In real-world datasets, we can expect q to be much less than n, as the uniqueness set captures some notion of the intrinsic difficulty of the problem while n captures the resolution of the problem. This intuition is rigorously supported by our theorems, which demonstrate that q scales with the number of mixture components/number of communities when the underlying limit graphon can be parameterized as a mixture model with a low difficulty function value. In a simple setting of stochastic block models, such as Proposition 5 in Appendix D, it is clear that q is, in fact, independent of n, and our algorithm does not become slower as n increases (ignoring the preprocessing steps (1) and (3)).

2. Provide examples of other applications within the graph machine learning domain. The paper proposes the use of information contained in a certain small subset of nodes (a uniqueness set) to solve problems on the full graph.

• Practically, our algorithm allows q - the size of the subset - to be a tunable hyperparameter for practitioners to choose and obtain an informative subset of size q. Apart from our citation network experiments involving graph classification and positional encoding using almost eigenvectors, there exist numerous other, more nuanced tasks where focusing on this small subset could be advantageous. However, we have not attempted these and leave them for future studies. For example, in a scenario with a vast unlabeled dataset with graph-based input, one could imagine finding a crucial, small subset for manual labeling and subsequently learning an algorithm to predict other labels in a semi-supervised manner. In another scenario, consider a dataset with censors as nodes in a graph. Applying our algorithm to identify a key subset of censors to focus computational efforts on is a feasible and scalable idea.
• Theoretically, our framework works as long as one can justify a low signal bandwidth setting for the task at hand. Under the lens of mixture models, one way to justify such low-bandwidth assumptions, as we have demonstrated, is when there is a process that aggregates nodes into a small number of clusters, leading to regularity in the frequency domain.

Reference: A. Anis, A. Gadde, and A. Ortega. Efficient sampling set selection for bandlimited graph signals using graph spectral proxies. IEEE Trans. Signal Process., 2016.