A Poincaré Inequality and Consistency Results for Signal Sampling on Large Graphs
Authors: Thien Le
Luana Ruiz
Stefanie Jegelka
Venue: ICLR 2024 spotlight (2024)
Keywords: large-scale graphs
signal sampling
graphons
Primary area: general machine learning (i.e., none of the above)
TL;DR: We formulate sampling problems in the graphon limit to discover intrinsic structures of large graph, with both theoretical guarantees and empirical evidence.

Abstract: Large-scale graph machine learning is challenging as the complexity of learning models scales with the graph size. Subsampling the graph is a viable alternative, but sampling on graphs is nontrivial as graphs are non-Euclidean. Existing graph sampling techniques require not only computing the spectra of large matrices but also repeating these computations when the graph changes, e.g., grows. In this paper, we introduce a signal sampling theory for a type of graph limit---the graphon. We prove a Poincaré inequality for graphon signals and show that complements of node subsets satisfying this inequality are unique sampling sets for Paley-Wiener spaces of graphon signals. Exploiting connections with spectral clustering and Gaussian elimination, we prove that such sampling sets are consistent in the sense that unique sampling sets on a convergent graph sequence converge to unique sampling sets on the graphon. We then propose a related graphon signal sampling algorithm for large graphs, and demonstrate its good empirical performance on graph machine learning tasks.

Published as a conference paper at ICLR 2024
A POINCARÉ INEQUALITY AND CONSISTENCY RE- SULTS FOR SIGNAL SAMPLING ON LARGE GRAPHS
Thien Le MIT chienle@mit.edi
Luana Ruiz
Stefanie Jegelka TU Munich, MIT stef
Johns Hopkins University 1 Trubini1g jh.
ABSTRACT
Large-scale graph machine learning is challenging as the complexity of learning models scales with the graph size. Subsampling the graph a viable alternative, but sampling on graphs is nontrivial as graphs are non-Fuclidean. Existing graph sampling techniques require not only computing the spectra large matrices but also repeating these computations when the graph changes, c.g., grows. In this pa- per, we introduce a signal sampling theory for a type of graph limit-the graphon. We prove Poincaré inequality for graphon signals and show that complements of node subsets satisfying this inequality are unique sampling sets for Paley-Wieen Wiener spaces of graphon signals. Exploiting connections with spectral clustering and Gaussian elimination, we prove that such sampling sets are consistent in the sense that unique sampling sets on convergent graph sequence converge unique sampling sets on the graphon. We then propose a related graphon signal sampling algorithm for large graphs, and demonstrate its good empirical performance on graph machine learning tasks.
INTRODUCTION
Graphs are ubiquitous data structures in modern data science and machine learning. Examples range from social networks (Kempe et al., 2003; Barabási et al., 2000) and recommender systems (Ying al., 2018) drug interactions (Zitnik et al., 2018) and protein folding (Jumper et al., 2021), in which the graph can have tens of thousands to millions of nodes and edges (Takac & Zäbovský, 2012). The ability to sense systems at this scale presents unprecedented opportunities for scientific and technological advancement. However, it also poses challenges, traditional algorithms and models may need to scale more efficiently to large graphs, including neural graph learning methods.
However, the large size of modern graphs does not necessarily indicate the degree of complexity of the problem. In fact, many graph-based problems have low intrinsic dimensions. For instance, the 'small-world phenomenon' (Kleinberg, 2000) observes that any two entities in network are likely connected by short sequence of intermediate nodes. Another example are power-law graphs, where there are few highly connected influencers and many scattered nodes (Barabási et al., 2000).
At a high level, this paper studies how to exploit these simplicities in large graphs to design scalable algorithms with theoretical guarantees. In particular, we combine two ideas: graph limits, which are used to approximate large, random graphs; and sampling theory, which studies the problem of representing (graph) signals using the smallest possible subset of data points (nodes), with the least possible loss of information. We then illustrate how to use the resulting sampling techniques to compress graphs for GNN training and to compute faster, subsampled positional encodings.
Graphons and graph limits. Leveraging continuous limits to analyze large discrete data is help- ful because limits often reveal the intrinsic dimension of the data. E.g., in Euclidean domain, the Fourier transform (FT) of continuous signal is easier analyze than the FT of its discrete coun- terpart, which is periodic and may exhibit aliasing. We propose to study the graph signal sampling problem graph limit called graphon. Graphons can be thought of as undirected graphs with an uncountable number of nodes, and are both random graph models and limits of large dense graphs (Borgs et al., 2008; Lovász, 2012).

---

Published as a conference paper at ICLR 2024
(Graph) signal sampling. Sampling theory is long-standing line of work with deep roots in signal processing. Traditionally, sampling seeks to answer the fundamental question: if one can only observe discrete samples of an analog (continuous) signal, under what conditions can the analog signal be perfectly reconstructed? On a graph on n nodes, signals are vectors x E IR" that map each node to some value. The graph signal sampling problem is then defined follows.
Problem 1. For some signal space X of interest, find subsets S of nodes such that xf x' E X and I; = x for all i E S then x; = x for all other nodes. Thus, such set can uniquely represent any signals in X and is called a uniqueness set for X.
Problem was first studied by Pesenson (2008), who introduced Paley-Wiened Wiener (PW) spaces for graph signals, defined graph uniqueness sets, and derived Poincaré inequality for discrete graph signals that allows recovering such uniqueness sets. These definitions are reviewed in Section 2. Graph signal sampling theory subsequently found applications in the field of graph signal processing (GSP) (Shuman et al., 2013; Ortega et al., 2018), with Chen et al. (2015) describing how sampling sets can be obtained via column-wise Gaussian elimination of the eigenvector matrix.
Current limitations. Though widely used, Chen et al. (2015)'s 's approach requires expensive spectral computations. Several methods, briefly discussed in Section 1.1, have been proposed to circumvent these computations; however, these approaches still present stringent tradeoffs between complexity and quality of approximation on very large graphs. Perhaps more limiting, the discrete sampling sets yielded by these methods are no longer applicable if the graph changes, as often happens in large real-world network problems, c.g., an influx of new users in a social network.
Contributions. To address the abovementioned issues, we propose sampling uniqueness sets on the limit graphon. By solving single sampling problem at the graph limit (graphon), we obtain a uniqueness set that generalizes to any large finite graphs in a sequence converging to the limit graphon. We provide both theoretical guarantees and experiments to verify this generalization in downstream graph-based tasks. In summary, our contributions are:
1. Motivated by Pesenson (2008), we formulate signal sampling over a graphon and study traditional sampling theory notions such as Paley-Wiener spaces and uniqueness sets in Euclidean setting of ( 1)) while still incorporating graph structure into the sampling procedure.
2. We prove Poincaré inequality for graphons and relate bandlimitedness in graphon signal space to optimal sampling sets'. This generalizes previous results on finite graphs and rigorously an- swers reconstruction question. Unlike other results for graphon signal processing in the litera- ture, we do not require any continuity or smoothness assumption on the graphon.
3. We uncover connection between graphon sampling and kernel spectral clustering and design based algorithm to sample from the graphon uniqueness set with provable consistency, using an argument from (Schiebinger et al., 2015).
4. We empirically evaluate our sampling method on two tasks: (1) transfcrability: training a GNN on subsampled graphs and testing the full graph; (2) accelerating the computation of positional encodings for GNNs by restricting them to a sampled subset of nodes.
1.1 RELATED WORK
Graphons in machine learning. In machine learning, graphons have been used for network model estimation (Borgs et al., 2015), hierarchical clustering (Eldridge et al., 2016) and to study the the- oretical properties of graph neural networks (GNNs) on large graphs. Specifically, Ruiz et al. (2020b) have shown that graph convolutions converge to graphon convolutions, further proving a non-asymptotie result that implies that GNNs are transferable across graphon-sampled graphs (Ruiz et al., 2020a). Similar studies have been done using graphops (Le & Jegelka, 2023), which are very general graph limits that range from graphons to very sparse graphs. Graphons have also been used to show convergence of GNN training on increasing graph sequences (Cervino et al., 2023), to prove PAC-Bayes bounds for GNN learning (Maskey et al., 2022), and to study the learning dynamics of wide large-graph NNs (Krishnagopal & Ruiz, 2023).
Similar sampling theory was also concurrently developed by Parada-Mayorga Ribeiro (2024).
2

---

Published as a conference paper at ICLR 2024
Graph signal sampling. Graph signal sampling has been studied at length in GSP. Chen et al. (2015) describe how sampling sets can be obtained via column- Gaussian elimination of the eigenvector matrix and derive conditions for perfect reconstruction. Noting that this approach quires expensive spectral computations, several methods were proposed to avoid them. E.g.. Anis al. (2016) calculate eigenvalue and eigenvector approximations using power iteration; Marques et al. (2015) compute n signal aggregations at single node to construct an re-dimensional local signal from which K elements are sampled; and Chamon & Ribeiro (2017) do greedy sampling and provide near optimal guarantees when the interpolation error is approximately supermodular.
Connections with other sampling techniques. The sampling algorithm we propose based on a greedy iterative procedure that attempts to find the signal with the lowest total variation on the com- plement of the current sampling set S, and adds the node corresponding to the largest component in this signal to S. This heuristic is derived by trying to maximize the largest eigenvalue of the normal- ized Laplacian restricted to S (see (Anis et al., 2016, Section IV.C) for detailed discussion). Thus, our algorithm has close connections with E-optimal design, which minimizes the largest eigenvalue of the pseudo-inverse of the sampled matrix (Pukelsheim, 2006), and with dual volume sampling (Avron & Boutsidis, 2013; Li et al., 2017), which provides approximation guarantees for E-optimal sampling. This type of objective also appears in effective resistance/leverage scores sampling (Ma al., 2014; Rudi al., 2018), which is used for graph sparsification (Spielman & Srivastava, 2008).
Recent work by Sarad-Maayrgee & Ribeiro (2024), concurrent with ours, also generalized PW spaces and uniqueness sets to graphons. Similarly, they proved a Poincaré inequality and proposed sampling algorithm for graphon signals. Their main results quantitatively compare the Poincaré con- stant across different graphon-signal spaces, implying convergence of this constant for a convergent graph sequence, unlike our work, which analyzes consistency of sampling via spectral clustering.
2
PRELIMINARIES
2.1 GRAPH SIGNAL PROCESSING
Setup. We consider graphs G (V.E) with nodes and edges E C V x V. We write graph's s adjacency matrix as E Raxx; its degree matrix as D = ((lgg(A):: and its Laplacian matrix as D A. We also consider the normalized adjacency and Laplacian matrices A (Di))?A(D"))?
and L I- - A (where is the pseudoinverse), with eigendecomposition L VAVT and eigen- values \ S ... S An. We further consider node signals x IR", which assign data value x; to node e.g., in social network, 2; may represent the political affiliation of person é.
Total variation and graph frequencies. The total variation of a graph signal is defined as TV(x). = x" Lx (Anis et al., 2016; Sandryhaila & Moura, 2014). This allows interpreting the eigenvalues A as the graph's essential frequencies, with oscillation modes given by the eigenvectors v, = [V]s.
Graph FT and Paley- Wiener spaces. We may analyze signals on the graph frequency domain via the graph Fourier transform (GFT). The GFT & of x is its projection onto the Laplacian eigenbasis & V x (Sandryhaila & Moura, 2014). The GFT further allows defining bandlimited graph signals, or, more formally. Paley-Wiener (PW) spaces. On G, the PW space with cutoff frequency A is defined (G) [x s.t. [ 0 for all X > }} (Anis et al., 2016; Pesenson, 2008).
Uniqueness sets. When X' is a PW space (G) with À S Ax for some < n, there exists a subset of at most K nodes that perfectly determine any signal in X called uniqueness set. The following theorem from (Anis et al., 2016) gives conditions under which a proposed subset S is a uniqueness set for (G).
Theorem 1 (Uniqueness sets for (G)) Let S C V. Let Vx E RRax denote the first K columns of the eigenvector matrix V and V. E KR be the submatrix of V with rows indexed by S. If rank g K, then S is uniqueness for (G) all X S (K( If SX AK+1 then rank 5 = K is also necessary.
In addition to providing a sufficient condition to verify if set is uniqueness set for some PW space, this theorem suggests a two-step strategy sampling method that outputs S such that rank K. However, these sampling strategies,
for obtaining such sets: first compute K, and then design
3

---

Published as a conference paper at ICLR 2024
e.g., the suggested by Thm. 1, can be limiting large graphs they require computing the eigendeconposition of large matrix.
2.2 GRAPHIO SIGNAL PROCESSING
Graphons and graphon signals. A graphon is symmetric, bounded, measurable function W Ω x Ω + [0, 1/, where Ω is a general measurable space (Borgs & Chayes, 2017). We assume that there exists invertible map 3 52 + [0, 1] and w.l.o.g..we can also write W : [0, 1)2 + [0, 1J. Graphons are only defined up to a bijective measure-preserving map, similar to how finite graphs are defined up to node permutations. Graphons are limits of graph sequences {G,} J in the so-called homomorphism density sense (Borgs et al., 2008), and can also be seen as random graph models where nodes Uj U are sampled from 52 and edges (us, Uj) Bernoulli (Wu,, u;)). Graphons can also be motivated via infinite exchangeable graphs (Hoover, 1979; Aldous, 1981).
Graphon signals are functions X : [0, 1] + R. They represent data on the "nodes" of graphon, i.e., X X()) is the value of the signal at node E [0,1] (Ruiz et al., 2021). Since two graphons that differ on a set Lebesgue measure O are identified, so are graphon signals. We restrict attention to finite-energy signals X E L ([0, 1J).
Graphon Laplacian and FT. Given a graphon W, its degree function is d(v) = Sg W(u, v)du.
Define the normalized graphon W(u, W (u, /l//d(u)d(() if d(u), d(u) * 0 and 0 other- wise. Given a graphon signal X, we define the normalized graphon Laplacian:
Cx= X
W(u, (u,,))X(u)eee (u)ddu
(1)
The spectrum of é consists of most countably many nonnegative eigenvalues with finite multiplic- ity in 20. Its essential spectrum consists of at most one point {1), and this is also the only possible accumulation point. We enumerate the eigenvalues
S A S Ag I ... S 2. The corresponding
set of eigenfunctions {1p hez,oo forms orthonormal basis of ( 1J): see App. B.
We define the graphon Fourier transform (WFT) of signal X as the projection
((A.) = L' (u))
(2)
for all i. Note that this is different from the WFT defined in (Ruiz et al., 2020b), which corresponds to projections onto the eigenbasis of different but related linear operator.
3 SAMPLING THEORY FOR GRAPHONS
We generalize the graph sampling problem studied in Pesenson (2008) to a graphon sampling prob- lem. The sampling procedure returns a (Lebesgue) measurable subset U C [0, 1]. Intuitively, we would like to choose set U such that sampling from U gives us the most information about the whole signal over [o, 1]. These are called uniqueness sets. Similar to finite graphs, when the graphon signals have limited bandwidth, there exist nontrivial (other than U = [0, 1) uniqueness sets. Find- ing these sets is the main focus the sampling theory for graphons that we develop here.
For an arbitrary bandwidth cutoff À > O, we use the normalized graphon Laplacian (1) with eigen- values 0 S A1 I X2 S ... S A_2 S A-1 S 2. First, we define the Paley-Wiener space: Definition (Graphon signal PW, (W) space). The Paley- Paley-Wiener Wiener space associated with À E [0, 1] and graphon W, denoted PW)(W), is the space of graphon signals X [0, 1] + R. such that (As) = 0 for all >; > X, where X is the projection operator defined in Eq. (2).
The definition of PW)(W) depends on the underlying limit graphon through the projection oper- ator (2), in particular the positions of its Laplacian eigenvalues. When À 2 X-1, PW, & is all of [[0 1)) as the definition above is vacuously satisfied. Decreasing À induces some constraints on what functions are allowed in PW,- At A = 0, PWo = {0) contains only the trivial function.
For any signal space H T.2 1)), we further define graphon uniqueness sets:
Definition 2 (Graphon uniqueness set), A measurable U S [o, 1] is a uniqueness set for the signal space H C ((,, 1)) if. for any X, Y E H. Su ((u)) 2 du 0 implies ||X - -V1 0.
4

---

Published as a conference paper at ICLR 2024
Since U |0, 1] is trivial uniqueness set for any H. S ([0, 1]), we mainly interested in the interplay between the bandwidth cutoff À in PW)(W), and its corresponding non non-trivial uniqueness sets. More precisely, we study the question:
Problem 2. Assume that a graphon signal comes from PWA(W) for some X and W. Is there an algorithm that outputs uniqueness set (x, W)?
We answer this question in the positive and provide two approaches. First, by generalizing results by Pesenson (2008) for finite graphs, we give graphon Poincaré inequality (Thm. 2) for nontrivial measurable subsets of [0. 1]. Then, in Thm. 3, we show that if a set S satisfies the Poincaré inequal- ity with constant A > 0 then the complement U [0, S is uniqueness set for PW 1/A (W) (Thm. 3). Thus, we can find uniqueness set U by first finding an that satisfies the Poincaré in- equality with constant 1/2.
The second approach is more direct: the analogous question for finite graphs admits a straightfor- ward answer using Gaussian elimination (see the discussion underneath Thm. 1). However, in the limit of infinitely many nodes, it does not make sense to perform Gaussian elimination as is. Instead, form a sequence of graphs (G.) that converges to the prescribed graphon W. We then prove, using techniques from (Schiebinger et al., 2015), that performing Gaussian elimination with proper pivoting for G, recovers sets that converge to a uniqueness set for PW (WW (Prop. 5). Finally, we implement and analyze this approach empirically in Section 6.
4
MAIN RESULTS
4.1 POINCARÉ INEQUALITY AND BANDWIDTH OF UNIQUENESS SET
We start with the first approach Problem 2, proving Poincaré inequality for subsets S [0, 1] and showing that this Poincaré inequality implies uniqueness of [0, 1 at some bandwidth.
First, need some definitions. These definitions generalize Pesenson (2008)'s observation that for finite graphs any strict subset of the vertex set satisfies a Poincaré inequality with con- stant determined by spectral properties of another graph I(T). Intuitively, T(T') is designed to capture the non-Euclidean geometry induced by nodes in T and their neighbors. We now want construct an analogous I(5) in the graphon case. Fix an arbitrary graphon W and measur- able subset S C. []. Define the neighborhood ((S)) of S as the measurable set A(S) =
{u E [o, 1]},5 Is W(u, r)du > 0}.
To define r(S), make copy of by letting S' be a set disjoint from [0. 1] such that there is a meaaure-ppreeervine bijection 5' + S. Let == S WSS) and 5 == UW()). Observe that one can extend 0 5' + S by mapping elements of (S(S) to itself. We will define graphon on the extended domain D = =5uB SUS::
W(u, v) W(O()),
if u E S and v E $ if E Š and v E S¹ otherwise.
T(S): D2 - [0, 1] (u,
(3)
Spectral properties of T(S) determine the constant in our Poincaré inequality: class of important results in functional analysis that control the action of the functional (normalized Laplacian) by the (non-Euclidean) geometry of the underlying space (here, a graph).
Theorem 2 (Graphon Poincaré inequality ). Let S ç [0. 1] such that N(S) has positive Lebesgue measure. Denote by A the smallest nonzero eigenvalue of the scaled normalized Laplacian operator applied to I'(S). Then for every X E ([0, 1]) supported only on S, |X|| S 1|
The proof of this theorem is in App. C and generalizes that in (Pesenson, 2008). Next, we prove that we can find a set S that satisfies a Poincaré inequality with constant A, then its complement is a uniqueness set for any PW, (W) with À < 1/A.
Theorem 3. Let S be a proper subset of [0, 1] satisfying the Poincaré inequality
(4) for all X E L²((0, supported only on Then, U = [0,1]VS S is a uniqueness set for any PW,(W) with X << 1/A.
|| S A|
5

---

Published as a conference paper at ICLR 2024
The proof of this result is in App. C, providing answer to Problem 2: given bandwidth limit X, one can find uniqueness set U by searching through measurable sets and computing the smallest nonzero cigenvalue Å₁ of (S)). If X < A then U [o, S is uniqueness set. This approach is inefficient as we may need to check every S. Next, we investigate a more efficient approach.
4.2 GAUSSIAN ELIMINATION AND CONVERGENCE OF UNIQUENESS SETS
Our second approach to Problem 2 relies on approximating the graphon with a sequence of graphs (G.. which has the graphon as its limit, and solving Problem 2 in one of these graphs. While attempting to solve the graphon sampling problem on a finite graph may appear tautological, our goal is to exploit the countable (and often finite) rank of the graphon make the problem tractable.
To establish the connection between the continuous sampling sets in a graphon and its finite rank K, we partition the graphon sampling set into K elements and view each element as representing mixture component or "cluster". This leads to connection to mixture models and spectral cluster- ing, which we exploit in two ways. First, to quantify the quality of the graphon sampling sets via a "difficulty" function borrowed from (Schiebinger et al., 2015) relating to the separability of the mixture components. Second, similar to consistency of kernelized spectral clustering. prove that in convergent graph sequences, graph sampling sets converge to graphon sampling sets.
Graphons equivalent to mixture models of random graphs. To make the above connection rigorous, the first step is to show we can view the graphon as a mixture model of random graphs.
Definition 3 (Mixture model for random graphs). Let Ω C Id be a compact space and P(2)) the space of probability measures Ω. For some number of components K, components {Pp; ((2)) weights {w; 2 1 that sum to 1, and a bounded, symmetric, measurable kernel k. : Ω x Ω + [0. mixture model for random graphs K( k) samples nodes from some mixture distribution; then sample edges using B the Bernoulli distribution over the kernel k;
K
ww P
W.P.,. 1 S n, (u,v) ((k(wi (. 1 u, n.
(5)
Historically, some authors (Borgs & Chayes, 2017) have defined graphons as in Def. 3, where PP is not necessarily mixture. Under mild conditions on IP assert that our simpler definition of graphon is still equivalent to a random graph model. We leave the proof to App. D.
Proposition 1. Assume the CDF of P is strictly monotone. Then, the mixture model IK(,, P, k) (Def. 3) is equivalent to the random graph model W[[0, 11, U, W) where W [0, 1J2 + [0, 1] is graphon given by W = k 3 and [0, 1] + Ω is the inverse of the CDF P.
Recall that Problem 2 prescribes bandwidth A, and requires finding a uniqueness set for graphon signals with the prescribed bandwidth. Let K be the number of eigenvalues of W which are smaller than A (i.e., K- s A ()). The following result shows that K is precisely the number of elements or samples that we need to add to the graphon uniqueness set.
Proposition 2. There exists a set of functions [ called frames, such that for any graphon signal X E (W) there is a unique reconstruction of X from samples (ffi, X))K
To see why this result is possible, recall that if X E PWA(W) for some À < AK41 then X is linear combination of K eigenfunctions {yp corresponding to KM Therefore, it suffices to calculate K coefficients c = (c by forming a full rank system (if one exists), which can then be solved via Gaussian elimination:
(fawPL) (f1122) " (f19x)
(1.X)
(Fiii) (f2/92) .. (Jaik)
(Fa.)
(iises) (fiies)) !i. (frip))
(xxx))
The next result tells us that different choices of mixture components and k result in frames with different approximation quality. Specifically, the approximation quality is a function of how well- separated the components in P are with respect to k and is measured quantitatively by a difficulty function ((, (Schiebinger et al., 2015). E.g.. if there are repeated components in the mixture, or bimodal component, we expect o to be high.

---

Published as a conference paper at ICLR 2024
P. ponents { the square-root kernelized density {q: := VJJ k(S,, ( K a frame approximation. Quantitatively, ler & be the subspace spanned by the eigenfunctions of W corre- sponding to {>il and Q the subspace spanned by the {q:) Then:
Proposition 3. When W is viewed mixture model of random graphs K( k) with K com-
[T - Tqllus S 16V12 + bo(
(6)
where ||-I|ss is the Hilbert-Schmice norm, II is the projection operator, and the difficulty function and the boundedness parameter b are as in (Schiebinger et al., 2015) and App. F!.
Next, we connect the square-root kernelized density q back to graphon uniqueness sets. The follow- ing result shows that when the q, 's align with eigenfunctions of W, there is clear correspondence between the uniqueness set and the mixture components. The proof is in App. D.
Theorem 4. Fix a small e >> O. Assuming that 19: -all (2(7.) < for all i E [K]; and that there exists a set of disjoint measurable subsets {A, C [0, 1] such that EITHER:
the kernelized density Ps == Jx k(w, (dPP;(W) is concentrated around an interval A; C [0,11] in the sense that Pi(A.)- -K2 EeyAm(Ae//(K -))² for each i E [K], OR
for each i E [K], the likelihood ratio statistic is large: p((A.)- K22 Exy; Pa(A.) > 1/(K - 1)}
then the ser U = = K A is a uniqueness set for (W) for any X E (Ak, Ak+1).
Put together, the above results culminate in method to find uniqueness sets by recovering the mixture components. However, this is still cumbersome to implement due to the continuous nature of graphons. Next we explore an efficient approach to find approximate uniqueness sets for graphon by finding uniqueness sets for finite graph sampled from (and thus converging to²) the graphon.
Gaussian climination (GE) on (approximations) of graphon eigenfunctions returns uniqueness sets for finite sampled graphs. We now derive a scheme to sample points w from a uniqueness set U with high probability. Assume that from W- = IK, we sample points to collect a dataset {w;} From a graphon perspective, these points are nodes in a finite graph G, of size n where the edges sampled with probability given by W. From mixture model perspective, the points Wi Ω are associated with a latent variable {z, E [K] that indicates the component the sample came from. By building on a result by Schiebinger al. (2015) on the geometry of spectral clustering, we can unify these two perspectives: rumning variant of GE over the Laplacian eigenvectors of large enough G,, returns a sample from each mixture component with high probability.
min" GE over the Laplacian eigenvectors of G, recovers K samples distributed according each of the mixture components F. 1 S i S K. with probability at least
Theorem 5. For any t > cov (n ( (8)
(1 (1-8K* exp- 82 Smar
C2nD'
(1- (1-a)<(A) -Tmin) K
(N (1++a)))mmm))) K K' with Memin
min Hi 21 = mE(K]
(7)
where a is upper bounded as a C1 (8)) ( functions C, S, On and ip are as in (Schiebinger et al., 2015) and App. F.
3/2 + (22)). The constants C1, C2 Wmin and ö, and the
Prop. 5 in App. D works out small example, corresponding to case where the IP's are uniformly distributed on disjoint domains. There, we show that by using GE, we end up solving an eigenvector problem of order K, the number of components, instead of the naive order n >> K.
Intuitively, for well-separated mixture models, embedding the dataset via the top Laplacian eigen- vectors returns an embedded dataset that exhibits an almost orthogonal structure: points that share the same latent variable (i.e., which came from the same mixture component) have high probability of lying along the same axis in the orthogonal system; while points sampled from different distri- butions tend to be positioned orthogonally. GE with proper pivoting G2 is thus good heuristic for sampling uniqueness sets, as it selects points that are almost orthogonal to each other, which is
For completeness, we have define and discuss the parameters of the difficulty function in App. F. Sequences of graphs sampled from graphon are always convergent (Borgs al., 2008).
7

---

Published as a conference paper at ICLR 2024
equivalent to picking sample from each component. The significance of this result is twofold: it bridges graphon sampling and kernelized spectral clustering, and the almost orthogonal structure ensures that the set sampled via GE is uniqueness set for large graphs sampled from W with high probability. This is stated in the following proposition, which we prove in App. D.
Proposition 4. Consider graph sequence G n-000 W. If there is a 8 E (0, [I/]|p/p// (b/ 2m)) such that the difficulty function' is small, i.e., Φn(6)= < that in Thm. there exists a minimum number of nodes NN such that, for all n N, the sampled nodes form a uniqueness set for the finite graph Gn, All quantities in the bound and additional assumptions are the same as in (Schiebinger et al., 2015) and App.
Wimt ) 13//++1cc then with probability at least
5 ALGORITHM
Motivated by Theorems 3-5, we propose a novel algorithm for efficient sampling of signals on large graphs via graphon signal sampling. When the regularity assumptions of our theorems satisfied, this algorithm will generate a consistent sampling set.
Consider a graph G, (V,E) and signal x,, from which we want sample subgraph G... and signal X with minimal loss of information (i.e., we would like the signal x, to be uniquely represented on the sampled graph G..). The proposed algorithm consists of three steps:
(I) Represent Gn as its induced graphon W, Wn(w, 0) Ei= I1 U...U In is the n-cquipartition of [0, 1].
E L.)((O 12) where
(2) Define a coarser equipartition I U... U r q < n, of [0, 1]. Given the bandwith À of the signal
Xn, sample graphon uniqueness interval Uy !", (Def. 2), p < q. from 1i TUU...P rg
(3) Sample the graph G. by sampling r [m/(p 1)J points from each of the 1/ ......,, - in the graphon uniqueness set (and the remaining procedure yields a uniqueness set for G, with high probability.
(p 1)r nodes from I, By Prop. 4, this
To realize (2), we develop a heuristic based on representing the graphon W,, n on the partition If U 11 as a graph G, with adjacency matrix given by [Ayli = Jr Jy Wn( y)drdy. We then sample p nodes from G.- G corresponding an interval 1/ C 1 U...U 12 using the graph signal sampling algorithm from (Anis et al., 2016). This algorithm is greedy heuristic closely connected to GE and E-optimal sampling but without spectral computations.
The sampling of m nodes from IA U., in step (3) is flexible in the way nodes in each interval sampled. Random sampling is possible, but one could design more elaborate schemes based on local node information. To increase node diversity, we employ a scheme using a local clustering algorithm based on the localized heat kernel PageRank (Chung & Simpson, 2018) to cluster the graph nodes into communities, and then sample an equal number of nodes from each community.
Runtime analysis. The advantages of algorithm (1)-(3) w.r.t. conventional graph signal sampling algorithms (c.g.. (Anis et al., 2016; Marques et al., 2015)) are twofold. First, if q < n, (2) is much cheaper. E.g., the heuristic from (Anis al., 2016) now costs O(pq²) as opposed to O(p|El). If step (3) uses uniform sampling then our method runs in O(E) [[E)+pq2 +m); whereas obtaining a uniqueness set of size m from Anis al. (2016) requires O(m)E) time. Second, given the graphon W, we only need to calculate the sampled intervals once and reuse them to find approximate uniqueness sets for any graph G,, generated from W as described in Section 2.2, provided that their node labels WW....,Wn (or at least their order) are known. Thus we save time on future sampling computations.
6 NUMERICAL EXPERIMENTS
Transferability for node classification. We use our sampling algorithm to subsample smaller graphs for training GNNs that are later transferred for inference on the full graph. We consider node classification citation networks (Yang al., 2016) and compare the accuracy of GNNs trained on the full graph, on graphs subsampled following the proposed algorithm, and on graphs
Notice a slight reparameterization.
8

---

Published as a conference paper at ICLR 2024
Table I: Accuracy and runtime for models trained the full graph, a sraphon-subsampae graph, and subgraph with randomly sampled nodes with the same size as (ii). The columns correspond to doubling the number of communities, doubling r, and doubling the eigenvalue index.
CiteSeer
buse
x2 comm..
x2 nodes per inl.
x2 cig.
base
x2 comm.
x2 modes per int.
x2 cig.
gruph
0,86
0.86
0.01
0.85
0.80
0.81
0.01
0.01
graphon sampl.
0.49
0.09
0.56 0.09
0.73 0.05
0.51 + 0.09
0.56
0.06
0.56 0.05
0.67 0.03
0.51 + 0.10
random sampl.
0.46 0.09
0.52 0.17
0.71 0.05
0.57 0.14
0.51
0.08
0.48
0.11
0.67 0.03
0.52 0.03
PubMed
runtime (s)
base
x2 commn.
nodes per
x2 eig.
Cora
CiteSeer
PubMed
fall graph
0.76 0.02
0.77 0.02
0.77 0.03
0.77 1: 0.01
0.9178
0.8336
0.8894
graphon sampl.
0.71 0,07
0.67 + 0.06
0.75 0.05
0.69 = 0.07
0.3091
0.2578
0.3204
random sampl.
0.69 0.07
0.71 0.07
0.74 0.07
0.72 + 0.04
0.3131
0.2514
0.3223
Table 2: Accuracy and PE compute runtime on MalNet-Tiny w/o PEs, w/ PEs computed on full graph, w/ PEs computed on graphon-sampless subgraph (removing or not isolated nodes), and w/ PEs computed subgraph with randomly sampled nodes (removing not isolated nodes).
graphon sampl. PEs
randomly sampl. PEs w/o
PE compute runtime (s)
no PEs
full graph PEs
w/ isolated
w/o
w/ isolated
mean
0.26:10.03
0.43
0.29-10.06
0.33
0.28+10.07 0.27+10.07 0.37
full 12.40 sampl. 0.075
max
0.30
0.51
0.40
0.42
0.35
sampled at random. To ablate the effect of different parameters, we consider base scenario and 3 variations. For Cora and CiteSeer, the base scenario fixes the cutoff frequency at the 5th smallest eigenvalue, As of the full graph. It partitions [0. 1] into q 20 intervals and samples p 10 intervals from this partition in step (2). In step (3), it clusters the nodes in each sampled interval into 2 communities and samples r 20 nodes from each sampled interval, 10 per community. For PubMed, the parameters are the same except q 30 and 15. The three variations are doubling (i) the number of communities, (ii) r, and (iii) the eigenvalue index. Further details are in App. G.
Table reports results for realizations. Graphon sampling performs better than random sampling in the base case, where the subsampled graphs have less than 10% of the full graph size. Increasing the number of communities improves performance for Cora and widens the gap between graphon and random sampling for both Cora and CiteSeer. For PubMed, it tips the scale favor of random sampling. which is not very surprising since PubMed has less classes. When difference between graphon and random sampling shrinks as expected. Finally, when we increase X, graphon sampling performs worse than random sampling. This could be caused by the sample size being too small to preserve the bandwith, thus worsening the quality of the sampling sets.
double r, the
Positional encodings for graph classification. Many graph positional encodings (PEs) for GNNs and graph transformers use the first K normalized Laplacian eigenvectors (or their learned represen- tations) as input signals (Dwivedi et al., 2021; Lim et al., 2022); they provide additional localization information for each node. While they can greatly improve performance, they are expensive to com- pute for large graphs. In this experiment, we show how our algorithm can mitigate this issue. We sample subgraphs for which the Laplacian eigenvectors are computed, and then use these eigenvec- tors as PEs for the full-sized graph by zero-padding them at the non-sam con-salple nodes.
We consider the MalNet- ManNet-Tiny dataset (Freitas et al., 2021), modified to anonymize the node features and pruned to only keep large graphs (with least 4500 nodes). After balancing the classes, we obtain a dataset with 216 graphs and 4 classes on which we compare four models: (i) without PFs, and qith PEs calculated from (ii) the full-sized graph, (iii) graphon-sampled subgraph, and (iv) a randomly sampled subgraph. For (ii) and (iv), we also consider the case where isolated nodes are removed from the sampled graphs to obtain more meaningful PEs.
We report results for 10 random realizations in Table 2. The PEs from the graphon-subsampled graphs were not as effective as the PEs from the full-sized graph, but still improved performance with respect the model without PEs. especially without isolated nodes. In contrast, on average, PEs from subgraphs with randomly sampled nodes did not yield as significant an improvement, and displayed only slightly better accuracy than random guessing when isolated nodes were removed.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
TL and SJ were supported by NSF awards 2134108 and CCF-2112665 (TILOS AI Institute), and Office Naval Research grant N00014-20-1-2023 (MURI ML-SCOPE). This work was done while LR was at MIT, supported by METEOR and FODSI fellowships.
REFERENCES
David J. Aldous. Representations for partially exchangeable arrays of random variables. Journal of Multivariate Analysis, (1(4)581-599 1981. ISSN 0047-259X. doi: https://oi.or//10
1016/0047-259X
URL attps://wwit / wtt.:eeett.co/ccieeeeeeeeee
a art.ccle/p1/0004755555 010099XX8899999... 900993.
A. Anis, A. Gadde, and A. Ortega. Efficient sampling set selection for bandlimited graph signals using graph spectral proxies. JEEE Trans. Signal Process., 64(14):3755-3788, 2016.
H. Avron and C. Boutsidis. Faster subset selection for matrices and applications. SIAM Journal on Matrix Analysis and Applications, 34(4):1464-149) 2013.
A. L. Barabási, R. Albert, and H. Jeong. Scale-free characteristics of random networks: the topol- ogy of the world-wide web. Physica A: Statistical Mechanics and its Applications, 281(1): 69-77, 2000. URL https://wwwt wwwwwwwwww.wwwwwwwwwwwwwt.t.t..w rect. com/ http://ceenne/ariceeep...p 503784371 0004333110001111
C. Borgs and Chayes. Graphons: A nonparametrie method model, estimate, and design algo- rithms for massive networks. In Proceedings of the 2017 ACM Conference Economics and Computation, pp. 665-672,60 2017.
C. Borgs, J. T. Chayes, L. Lovász, V. T. Sós, and K. Vesztergombi. Convergent sequences of dense graphs Subgraph frequencies, metric properties and testing. Adv. Math., 201 2008.
C. Borgs, J. Chayes, and A. Smith. Private graphon estimation for sparse graphs Neural Inform. Process. Syst., 28, 2015.
J. Cervino, L. Ruiz, and A. Ribeiro. Learning by transference: Training graph neural networks growing graphs. IEEE Trans. Signal Process., 2023.
L. F. O. Chamon and A. Ribeiro. Greedy sampling of graph signals. IEEE Trans. Signal Process., 66:34-47, 2017.
S. Chen, R. Varma, A. Sandryhaila, and J. Kovacevic, Discrete signal processing on graphs: Sam- pling theory. IEEE Trans. Signal Process., 63:6510-6523, 2015.
Chung and O Simpson. Computing heat kernel pagerank and a local clustering algorithm. European Journal of Combinatorics,, 68:96-119, 2018.
V. Dwivedi, Luu, Laurent, Bengio, and X. Bresson. Graph neural networks with learnable structural and positional representations. 10.00775 [cs.LG], 2021.
Eldridge, M. Belkin, and Y. Wang. Graphons, mergeons, and on! Neural Inform. Process. Syst., 29, 2016.
S. Freitas, R. Duggal, and D. H. Chau. MalNet: A large-scale image database of malicious software. arXiv:2102.01072 [cs.LG)) 2021.
Douglas N Hoover. Relations probability spaces and arrays of. Institute for Advanced Study, 1979.
J Jumper, R. Evans, A. Pritzel, T. Green, M. Figurnov, O. Ronneberger, K. Tunyasuvunakool, R. Bates, A. Zidek, A. Potapenko, A. Bridgland, C. Meyer, S. A. A. Kohl, A. Ballard,
A. Cowie, B. Homera-Paredess S. Nikoloy, R. Jain, J. Adler, T. Back, S. Petersen, D. Reiman,
10

---

Published as a conference paper at ICLR 2024
E. Clancy, M. Zielinski, M. Steinegger, M. Pacholska, T. Berghammer, S. Bodenstein, D. Sil- ver, O. Vinyals, A. W. Senior, K. Kavukeuoglu, Kohli, and D. Hassabis. Highly accu- rate protein structure prediction with AlphaFold. Nature, 596(7873):583-589 2021. URL
https:: doi worgr00/g.... /00 038/ 2088//41558 021-0381 9-2.
D. Kempe, J. Kleinberg, and É. Tardos. Maximizing the spread of influence through social network. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), pp. 137-146. Association for Computing Machinery, 2003.
M. Kleinberg. The small-world phenomenon: An algorithmic perspective. In Symposium Theory of Computing (STOC), 2000. URL https: /app/aapi... semant CorpusID: 221559836.
S. Krishnagopal and I.. Ruiz. Graph neural tangent kernel: Convergence on large graphs. Int. Conf. Mach. Learning. 202:1-15, 2023.
T. Le and S. Jegelka. Limits, approximation and size transferability for gnns on sparse graphs via graphops. arXiv:2306.0444 04445 [cs.LG],, 2023.
C. Li. S. Jegelka, and S. Sra. Polynomial time algorithms for dual volume sampling. Neural Inform. Process. Syst., 30, 2017.
D. Lim, J. Robinson, L. Zhao, T. Smidt, S. Sra, H. Maron, and S. Jegelka. Sign and basis invariant networks for spectral graph representation learning. arXiv:2202.13013 [cs.L.G], 2022.
L. Lovász. Large Networks and Graph Limits, volume 60. American Mathematical Society, 2012.
P. Ma, M. Mahoney, and B. Yu. A statistical perspective on algorithmic leveraging. In Int. Conference on Machine Learning (ICML), pp. 91-99. PMLR, 2014.
A. G. Marques, S. Segarra, G. Leus, and A. Ribeiro. Sampling of graph signals with successive local aggregations. IEEE Trans. Signal Process., 64:1832-1843, 2015.
S. Maskey, R. Levie, Y. Lee, and G. Kutyniok, Generalization analysis of message passing neural networks on large random graphs. Neural Inform. Process. Syst., 35:4805-4811 2022.
A. Ortega, P. Frossard, J. Kovačević, J. M. F. Moura, and P. Vandergheynst. Graph signal processing: Overview, challenges, and applications. Proc. IEEE, 106(5):808-825 2018.
Alejandro Paroda-Mayorga and Alejandro Ribeiro. Sampling and uniqueness sets in graphon signal processing. 2024.
Pesenson. Sampling Palcy-Wiener spaces on combinatorial graphs. Transactions of the
American Mathematical Society, 360 360(10):6033-5677, 2008
Pukelsheim. Optimal design experiments. SIAM, 2006.
A. Rudi, D. Calandriello, L. Carratino, and L. Rosasco. On fast leverage score sampling and optimal learning. Neural Inform. Process. Syst., 31, 2018.
L. Ruiz, L. F. O. Chamon, and A. Ribeiro. Graphon neural networks and the transferability of graph neural networks. In 34th Neural Inform. Process. Syst., Vancouver, BC (Virtual), 6-12 Dec. 2020a. NeurlPS Foundation.
L. Ruiz, L. F. O. Chamon, and A. Ribeiro. The Graphon Fourier Transform. In 45th IEEE Int. Conf. Acoust., Speech and Signal Process., pp. 5660-5664, Barcelona, Spain (Virtual), 4-8 May 2020b. IEEE
I. Ruiz, I.. F. O. Chamon, and A. Ribeiro. Graphon signal processing. IEEE Trans. Signal Process., 69:4961-4976, 2021.
A. Sandryhaila and J. M. F. Moura. Discrete signal processing on graphs: Frequency analysis. IEEE Trans. Signal Process., 62:3042-3054, June 2014.

---

Published as a conference paper at ICLR 2024
G. Schiebinger, M. J. Wainwright, and B. Yu. The geometry of kernelized spectral cluster- ing. The Annals of Statistics, 43(2), Apr. 2015. URL setpss//doli wtg//1.121199
2F14-a0s1283.
D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst. The emerging field of signal processing on graphs: Extending high-diment nigh-dimensional data analysis to networks and other irregular domains. JEEE Signal Process. Mag., 30(3):83-98, May 2013.
D. Spielman and N. Srivastava. Graph sparsification by effective resistances. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 563-568, 2008.
L. Takac and M. Zábovský. Data analysis in public social networks. International Scientific Conference and International Workshop Present Day Trends of Innovations, pp. 1-6, Jan. 2012.
Z. Yang, W. Cohen, and R. Salakhudinov. Revisiting semi-supervised learning with graph embed- dings. In Int. Conf. Mach. Learning, pp. 40-48. PMLR, 2016.
R. Ying, R. He, K. Chen, Eksombatchai, W. L.. Hamilton, and J. Leskovec. Graph convolu- tional neural networks for web-scale recommender systems. In ACM SIGKDD Conference Knowledge Discovery and Data Mining (KDD), KDD '18 pp. 974-983, Association for Com- puting Machinery, 2018 URL https:ttpp..mm http//do..ooo www.:.org/11... 11e..1115//22 981 9.1..81111111 9899890.
M. Zitnik, M. Agrawal, and J. Leskovec. Modeling polypharmacy side effects with graph convolu- tional networks, Bioinformatics, 34(13))4457ii46, 06 2018. URL https: /oii org/10. 1t93/biiiinfommatcccc///oo/o /btt299
A EXTRA NOTATIONS
For some probability measure Q, and some functions the same L²(()) spaces, denote by (a)) the (2) inner product and || |x)(C) the induced L norm. We will also abuse notation and write L (D) for some set D that is a closed subset of the real line to mean the L space supported on D under the usual Lebesgue measure. When the measure space clear, we will also drop and simply write 2
For some set of functions (J1,... JK). (01,-.. -0.....:9K' .K] where Js and Jn in the same 2 space, denote by (1) the K K matrix:
(fi,g)
(f1.92)12 (f2,92)12
(f).9k)
(J2,
(22
((ing)))
(8)
1
(fr.92)
(fx,9k) 12
B ADDITIONAL BACKGROUND
In this section, we revisit operator theory arguments in our construction various graphon objects (degree function, normalized graphon, graphon shift operators and normalized graphon Laplacian) from Section 2.2.
Recall that graphon W is bounded, symmetric and 1,²-meauraabe function from 00, 1J - (0.
and thus induces a Hilbert-Schhie kernel with open connected domain W : (0, - (0, 1]. We
will abuse notation and refer to both of these objects as graphons. The associated filbert-Schmide integral operator for W is:
- (,2 1)) X UL L' W(u, "((u,)) ())())
H:
where the resulting function understood to be in L When W is viewed as the adjacency matrix of graph with infinitely many vertices, if X is taken assign each nodes with feature in [0, 1], then H is understood as a message-passing operator that aggregates neighboring features into each node. Note that measurable functions only defined up set of measure O.
12

---

Published as a conference paper at ICLR 2024
In the paper, consider normalized version of W:
w(,,)) v) W( W(u,))//d(x)dd
if ( * 0 and d(u) + 0
(10)
otherwise.
where d E (2(( 11) is the degree function:
d(u)= So Wuu, v)de.
(11)
is clear that W is also bounded, symmetric and T,2 m.--maasuabble. The corresponding HS operator denotes H. When the kernel is symmetric and has bounded (2, -nor,, then Hilbert-Semidi operator theory tells us that // is continuous, compact and self-adjoint.
is
Spectral theory of HS operators then tell that H and H has countable discrete spectrum {Λı Z A2 2 ...,, {A1 X2 ...3 and the essential spectrum of single accumulation point (Lovász, 2012). Furthermore, each nonzero cigenvalues have finite multiplicity (Lovász, 2012). As compact self-adjoint operator, H and H admits a spectral theorem:
W(u, Σ (ESP(u))(x()),
(12)
KEN
for some eigenfunctions {pp I|px (Lovász, 2012).
Recall that Mercer's 's theorem asserts that continuous positive semi definieeinite kernel admits a spectral theorem: there exists set orthonormal functions {p, HeN and countable set of eigenvalues {Ai such that Σ (pppp (v) = k(u, v) where the convergence is absolute and uniform. For measurable kernels (graphons), Eq. (12) only converges in L norm. However, the sequence of eigenvalues admits stronger 2² convergence:
8
x
(13)
Note that by our normalization, W S and thus [ < for all N. Finally, we defined the normalized Laplacian operator Z Id H. It is then straightforward to see that the spectrum of Z
is just oHH) set-wise.
C POINCARÉ INEQUALITY
Proof of Thm. 2. The proof mirrors Pesenson (2008). Fix an X in L²( Define X' E (D) as:
X(u)
ifEE if U otherwise.
(')+)=
-((u)
(14)
It is clear that X' is measureable (with respect to Lebesgue measure on D), Consider:
[x'()) (x'(u)) + (X'()))) = (1)
(15)
and at the same time, for all u E U:
f W(u, v)du
JouNTy W(u, u)du = (T(U))( v)de.
(16)
This in particular means that normalizing I(U) as I(UY means scaling by the same scalar as nor- malizing W into W'
13

---

Published as a conference paper at ICLR 2024
Now investigate the image of X' under Laplacian operator:
X') = X')) - / (T(U)) (o)d
(17)
((u) So W (v)d
if
-X(u) - (w, (v)dd
if E U² otherwise,
(18)
('X(u)
iuEU
-L'X(u)
if U"
(19)
otherwise.
And therefore: (o v2|| | The point of construct-
ing TUY is that it has a nice eigenfunction that corresponds to eigenvalue Let you be such function, then
(T(U))(,, Cr(n)oo(u)= = =po(u)- - So (D(T(U)) o)dz (T(U)) 2)dz
po(vdde.
(20)
By inspection, setting po(u) == V (T())) v)dv satisfies the above equation and this is the eigenfunction of car) corresponding to eigenvalue Expand X' in the eigenfunction basis of fr(w) to get:
X (X
Σ (ENU
1(',
(21)
However, the first coefficient vanishes:
(X', po) = x'u))
J. (T(U)) v))ddu
(22)
W(u, old,du =[x(,)) x(u) V /
- -s, X(u)y) /
=
W ((,, v)dudu
0,
(23)
and we have:
22 (1 2 X'
(24)
= Σ 1
(25)
iEN
> A
(26)
= 12
(27)
which finishes the proof.
Proof of Thm. 3. X PW)(W), then X Y E (W)(W) and we have:
||ı(X- - -Y)Ilz S X||X - Y 1zz.
(28)
X and Y coincide on U, then X- x-Y
Y E eI?((S) and we can write the Poincaré inequality:
X - Yl1ıa & A1| Y)
(29)
Combining the two inequalities, we have:
|| Yl I AIIā(X Y)Il22 S - -YlKa
(30)
which only be true if || ||||XXX Y| 0 since AA < 1.
14

---

Published as a conference paper at ICLR 2024
D PROOF FROM SECTION 4.2
D.1 GRAPHIN IS EQUIVALENT TO MIXTURE MODEL FOR RANDOM GRAPIS
Proof of Prop. I. Let w ~ P(2).. We want to find strictly monotone function 3: [0, 1] - Ω such
that B (w) uniformly distributed over [0, 1]. Let (w) P(w S w), and assume
function 3 exists. Then, for all w can write
(w(w) P(w S w) P(((U) S w) - P(U 3 3 (w)
(31)
where the second equality follows from the fact that, since 3 strictly monotone, has an inverse. This proves that 3 exists and is equal to the inverse of the CDF of w.
Before continuing, let us introduce a few useful definitions. The Laplacian associated with the model K, K) is defined as
L - k(w (w)
(32)
where (w, K(w, ((w,))/(((()q())) and q(w) v k(w, 0)dP(O). The operator L self- adjoint and positive semidefinite, therefore it has non-negative real spectrum {Ai, J
To simplify matters, we will consider the problem of finding frames { allowing to uniquely represent signals in any (A)(A) with A S Ag. Note that the graphon W (and therefore its asso- ciated Laplacian) are themselves rank K. Recall that, in order to uniquely represent a signal, the frame {fr} must satisfy
(11+1)) (f21 (f2192)
(f1.92)
(fiPk) (f2
rank
K
(33)
((ki
(fx
(fK,Pk)
where { are the eigenfunctions associated with strictly positive eigenvalues of Lx. sorted according to their magnitude.
By (Schiebinger al., 2015, Thm.1), the functions (0) Sa K (w, 15 < K, form such a frame.
D.2 MIXTURE COMPONENT GIVES RISE TO UNIQUENESS SETS
In this section, we Leb to emphasize the Lebesgue measure on R being used in our integrals.
X (eA,(w) Pa pr(w)/p((A) where åg is the Dirac delta function for a measurable set E., for each
Proof of Thm. 4. Define the Heaviside frame {he
BIK as h₂(w)
i E [K] It is straightforward to check that h; is also in (p²(p;) for each i E [K]. De- fine the subspace H = phan, h.g) and the Heaviside embedding 4H X + B as (w))..
(w) = (hx(w)....xx(())
Step 1: Show that ((h,, 95))55m is full-rank. To show that ((ha, 9.)) is full-rank, we com- pute entries of ((he, 9 =5) for any i,j E [K].
Vp((A,) J. (www) ((())ddec)))) Vp((A)) I (=)()))(())dLLb(() (34) (pi,9))=
1
For diagonal entries, note that:
(h). (oi(A,) / py(w)dLeb(w) = (p,(A)).
1
(35)
15

---

Published as a conference paper at ICLR 2024
Fix an j E [K] and consider:
Vpi(As) J. A,
Σ
Σ
(36)
[1, ps Ps(w)dleebw)) V S.. pe(w)dLeb(w)
(37)
* Vpi(A.)
E
1
(.(())VP(AA))
(38)
#1 VDi(A,)
Py(A),
(39)
where the inequality is from Cauchy-Schwarz. In the first choice of assumption, we have ()(A,) Eitj - 1)2 and thus Vpj(Aj) Ke Ke (Eig, (AA))((()))))))))>
Eist V (A.), due to monotonicity of square root and Cauchy-Schwarz. Thus, we have shown that for every j E [K]. the j-th column of ((hs, q;)) q;)) has j-th entry larger (in absolute value) than the sum of absolute values of all other entries. Gershgorin circle theorem then tells us that eigenvalues of ((h, 9; 4)));==1 lie in at least one disk center at some diagonal value with radius sum of absolute value of remaining column entries. None of the Gershgorin disks contain the origin, and we can conclude that ((h,, gj )) /=j== has no eigenvalue. Therefore, it full rank.
Now, fix an E [K] and consider:
10hs uiحl = Σ Σ AFC
S71 (Pi( / A,
(40)
## (Pi) ( P/(W)dLee(()) / p((w))Leb(()
(41)
Σ
Pa)(A))P((AA)
(42)
HA VP((A.)
= Σ (A,(A))
(43)
In the second choice of assumption, the same thing happens: ((A))K22 > E)){P,(A)/(KK
1)² implics that (A.) Ke > Ejti (P.(A.) and once again, the center of any Gershgorin disk (but this time in the rows) are further away from zero than the sum of absolute value of other non-diagonal entries. Therefore, none of the disks contain the origin and ((h,, qj f5)){=m1 cannot have 0 eigenvalue, thus full-rank. Therefore, either choices of assumption leads to full-rank-ness of the system ((h,, g,))
Step 2. Full-rank implies uniqueness.
By the premise of this result, we have for each i,
|/q: Pillea
(44)
Thus,
(hr,9,) (h5, (hg. (99) E ((h,g)) e, (hi,g)) + c),
(45)
by Cauchy-Schwerr
Recall that ((h,, qj) Da, j.y is full rank, and that Gershgorin circle theorem applied in the previous step still has a slack of at least Ke. Therefore, perturbation element-wise of additive size of ((h, 9; ()) will still be full rank by Gershgorin circle theorem and conclude that ((ha, (p)))s is full-rank.
16

---

Published as a conference paper at ICLR 2024
Let X E (W)(W) for some À (Ax, Ak+1), then by definition, there exists vector E R k
such that X EE=1 Cjpj. Take inner product (in (1P L2(()), we have:
(11,
(11, (h2,100) (12,12))
(h1: pPk
(111, X) X)2
(h2, PK))
(46)
((bx, (2x) (kK,
( X)
To test U = U A, is a uniqueness set, we assume that || = 0. But Kha, X>I =
[h,, x)1 = ||,,]] [ = 0 for each in [K]. Thus:
(h1, p1)
(h1, p22)
(h1, pK)
T
1h2,411
(h2, 92)
(h2, px)
c=
(47)
(11) (2)))22)
(bK,
Finally, since (1))) is full rank, its null space is trivial, implying 0 and thus X 0, which proves uniqueness of U.
D.3 CONSISTENCY THEOREM
This result is an adaptation of (Schiebinger et al., 2015, Thm. 2), which reproduced below.
Theorem 6 (Thm.2, Schiebinger al. (2015)). There numbers c, co- Ct C2 depending only b and r such that for any E (0, bvēT t > comman on (5), the embedded dataset (wv(w)), Zz / has (a, 0) orthogonal cone structure with
[ satisfying condition (Schiebinger et al., 2015, 3.17) and any
Go
(6)
cos 0
<
(48)
w t Cu (6)
min
C1
1h () (21)
(49)
W 3/2
and this event holds with probability at least 1 8K2 exp
Cyn5
Thm. elucidates the conditions under which the spectral embeddings of the nodes w form an orthogonal cone structure (see (Schiebinger et al.. 2015, Def. 1) for precise definition). This is helpful for Gaussian elimination, as provided that we pick a pivot inside a cone, the other rows to be picked-which are orthogonal to the pivot- are themselves inside other cones, and therefore likely to belong to a different cluster (i.e., to distributed according to a different mixture component).
We first recall connections between graphons and mixture models and explain how each objects in the context of Thm. 6 can be understood in graphons terms. mixture model, we sample dataset (w,) from the mixture distribution. This is equivalent to sampling nodes under pushforward in when we sample finite graphs from a graphon. Thus, each data point W; is a 'node" of a finite graph sampled from the graphon. Next, the spectral embedding of datapoints in spectral clustering is equivalent to computing the eigenfunction of graphon Laplacian at that datapoint embedding it in frequency domain. Therefore, from graphon perspective, the theorem is asserting that given some underlying structure controlled by the difficulty function, embedding of nodes in finite graph from fix graphon into frequency domain under GFT has peculiar structure: an orthogonal cone. While we do not have easy access to graphon cigenfunction, computing an approximation once with a large graph suffices. This is because we can reuse the embedding when new points are sampled into the graph!
Proof of Thm. 5. Let us consider what happens when performing Gaussian elimination on the columns of (y) When picking the pivot, the probability of picking a "good" point inside cone, ie., a point that both inside a cone and that distributed according to the mixture com- a. Conditioned on this event, the probability of picking
ponent associated with that cone, is
17

---

Published as a conference paper at ICLR 2024
second "good" point from another cone is (U-o)(n-Ri) mn where n1 is the number of points distributed according to the pivot's 's distribution, denoted P1. More generally, the probability of picking a "good" point at the ith step, conditioned having picked - 1 "good" points, is
P(ith point is "good" 1....,;- i are "good") = (1 a)n-
(50)
(1 - aa
where n Σj=1 n ny and n4ii n-i-
Since Eq. (50) is decreasing function of n- the probability of picking K' good points is lower bounded by
,l,...., K are "good") 2 (1 az) (n 7mmin) )
(51)
(n - (1 x a))mmin) K
where mminn minigisk ny. Combining Eq. (51) with Theorem Thm. 6 gives the proposition' s result.
Proof of Prop. 4. The conditions the difficulty function in the hypothesis of Prop. 4 means that the angle 0 in the cone structure at least n/3.
Note that every finite graph G, induces graphon via stochastic block model:
a n
WG. =Σ
A e I.)(yy e 13)
(52)
From Ruiz et al. (2021), we know that the eigenvalues of the adjacency HS operator of WG.. converges to that of W. As the graphon Laplacian is scaled and translated operator from the adjacency operator, eigenvalues of the Laplacian also converges. Let the eigenvalues of the finite
graph be An, S ... S Ån,-1 Pick an ni large enough such that there a spectral gap \,, < An,K+1 for all n > no- Then pick an even larger such that À E (An, kn,K+1) for all > n1. Such choice of no, n1 guaranteed by convergence of eigenvalue.
Not only do eigenvalue converges, when there is an eigengap, the subspace spanned by the first K eigenfunctions also converges. The convergence is term of convergence operator norm of the projection operator (Ruiz et al., 2021). Let the projection operator be &c and &w. corresponding that for the finite graph G, and for the graphon W respectively. Therefore, we select yet larger n2 such that 2... 4w Hs for all n 122 and for some to be chosen later.
Recall that we picked some sample via Thm. and with high probability, our sample attains an orthogonal cone structure. In other words, there is permutation of samples such that for each 1/2 with high probability, where r(i) is the angle between yp(x;) and the unit vector with all zero entries but the i-th one. This means that for any (p.())///(()) (z)))) > 1 1/2. Therefore, the matrix:
i E [K], cos co))
(()))
p2(x1)
FK (x1)
(T(2) (2((2))
x (22)
(53)
(xr< (2(xx)
s (#x)
is full rank, since the off-diagonal absolute value sum does not exceed the absolute value of the diagonal entry for every row, via Gershgorin circle theorem. As corollary from Thm. of Anis et al. (2016), the system being full rank means that the samples drawn form uniqueness set and the proof is complete.
To select notice that there are still slack in Gershgorin circle theorem and one select such an that the two projection has cigenfunctions differs by at most that slack amount in L This is possible since full-ranked-net
is robust property: if matrix is full-rank then other matrices within a small ball from also full-rank. Thus, if there is a converging sequence of eigenfunctionleigensper to pxx) then the perturbed matrix analogous Eq. (53) would eventually enter the small ball of full-rank matrices. We leave more precise nonasymptotic analysis to future work.
18

---

Published as a conference paper at ICLR 2024
E SMALL EXAMPLE: BLOCK MODEL AND MIXTURE OF DISJOINT UNIFORM DISTRIBUTIONS
Let us consider simplified setting, consisting of a blockmodel kernel and uniform mixture compo- nents, to show example where Gaussian climination recovers intervals distributed according to the {q:)/11
Proposition 5. = U.NN be an N-partition of Let the kernel k be a K-block model coarser partition I' = 22 J...U Lixx of containing I (each block has value given by the integral of over the centroid). Let the P; be uniform over the Dt Then, column-wit Gaussian elimination over the positive eigenfunctions (vectors)) finds subsets Qjs:-.., Qix distributed with probability density functions equal to the corresponding qi, up to normalization.
Proof of Prop. 5. The kernel k can be written as
k(w,
anylw E 01)((0 07).
(54)
Therefore, the model K can be represented SBM graphon,
q
ik
iK
011
Q11
01K
01K
i1
011
011
01k
01K
A =
(55)
K
8
01K
01K
OKK
OKK
Kk
01K
01K
OKK
OKK
where 17 S ji < hy indexes elements of I contained in 22 (i.e., the support of Fi), and
Σj kj N. For a more concise representation, let us write
A11
A1K
A :
(56)
AIK
AKK_
where Aij a:j a.j11 11
Consider the normalized adjacency À ( which has the same block structure A but with blocks Áij- Note that technically, would find eigenvectors of the normalized Laplacian I Á but the identity shift only shifts the spectrum by (after inversion about the origin). Therefore it equivalent to finding the eigenvectors of A:
Å
Åιk
== Xu.
(57)
Á
ÅRк.
Note, however, that for each S i S K, the rows corresponding to [A À A are repeated, plugging A into eigensolver without simplifying À first is going ineur huge computational cost for little gain. We exploit the repeated structure of Å do some preprocessing first, via a variant of Gaussian elimination. Permuting the rows and columns this matrix to ensure the sequence 0a....., diK appears in the first K columns, and subtracting the repeated rows,
19

---

Au Published as a conference paper at ICLR 2024
rewrite this as
Ā11
b1
u
(58)
@1K
OKK
b 0
where the b, E RN-K are row vectors collecting the remaining entries of row i after permutation, and 0 denotes the all-zeros vector of dimension N K.
For the linear system in Eq. (58), it is easy to see that the solutions u must have form u [u ... Uk O 0J². Hence, the eigenvectors of the modified matrix in Eq. (58) are the eigenvec- tors of its K' x K principal submatrix padded with zeros. To obtain the eigenvectors of the original matrix Eq. (57), we simply have "revert" the operations performed get from there Eq. (58), with the appropriate normalizations to ensure orthonormality. By doing so, we get eigenvectors of the following form
kn times
u1
(59)
KK UK
kgg times :
i.e., in every eigenvector of A, entries corresponding sets Ω contained in the Di the same.
Now, assume that have found all K eigenvectors of Å and collect them in the matrix UK RN*K x To find a uniqueness set for the associated graphon, we perform columnwise Gaussian elimination UK. k. and add the indices of the zeros in the Kth row of the echelon form to the sampling set.
In the current example, this heuristic is always guaranteed to find uniqueness set. Any combination of indices corresponding to K different rows from UK forms such a set. Since through Gaussian elimination we are guaranteed to pick linearly independent rows, when picking a row from cluster Ω for arbitrary i, all k; rows are equally likely to be picked, they are equal and thus have the same "pivoting" effect. In an independent trial, the probability of picking a row from Q is thus (k:/N) x P,, Up to normalization. this probability is equal to q; AP;; The entries of this vector determine the level sets of qi as
(x(z) q:llxx 22
(60)
completing the proof.
F ELEMENTS FROM (SCHIEBINGER ET AL., 2015)
For completeness, we reproduce elements from (Schiebinger et al., 2015) that were used in our paper.
F.1 DIFFICULTY FUNCTION FOR MIXTURE MODELS
Recall Ω is measurable space and P(2) is a set of all probability measures on Ω. Let P, E P(22)
mixture components for 1..K. A mixture model convex combination:
K
w.P.i
(61)
i=1
for a set of weights w, 2 for = 1... K and Ee Wi 1. Recall that there also a kernel
associated with the mixture model.
20

---

Published as a conference paper at ICLR 2024
The statistics of how well-separated the mixture components be quantified through five defined quantities:
Similarity index. For any distinct pair of mixtures + the kernel-dependent similarity index between Pj and Pε is:
PPP = Jo Ja k(w, (dIP))) In Ja k(w, (ddP(w)
(62)
and the maximum over all ordered pairs of similarity index is:
Smax (P) max S(IP,, Pk)
(63)
In general, Smax measures the worst overlap between any two components with respect to the kernel k.
Coupling parameter.
The coupling parameter is defined as:
k(w,
k(w, 0)
2
C(P) = max
Wm ((w)g(0)
(64)
Iu (w) (w)) (0)
v k(w, (kw,0)dPPm) () measures the coupling of function spaces over P2 with respect to the Laplacian operator. When it is 0, for instance, the Laplacian over is the weighted sum of Laplacians over P. with weights wm-
where (()) = S (/lk((,,)dE)) ())P(w) and 4m (m)
Indivisibility parameter.
The indivisibility of probability measure is defined as:
T(Q): == inf p(2) Is Ssa k(w, ()Q(() SCR
(65)
(S5)
where p(S) = So k(w, (QQ(O))
And I' min (IP) := min. (mPm) measures how easy it is to split single component into two which suggestive of ill-fittedness of the current model.
Boundedness parameter. Finally, we define:
k(,, 0)
bmax == max
dlP (0)
(66)
Gm (.)) (0)
This is just a constant when the kernel is bounded.
The difficulty function. With these parameters set up, we can now define the difficulty function used in Prop. 3:
VK(Smas max (P) C(P))
((P, ()P,k)=
(67)
minm Wm r min (P)
F.2 FINITE-SAMPLE CONE STRUCTURE BLEMENTS
To get Theorem from (Schiebinger al.. 2015), we require additional concepts and notations.
For two vectors u, v in R we define the angle between them angle(u, v) = arccos (u.e) |||]|||||] An
orthogonal cone structure OSC' with parameter a, 0 is an embedding of n points {(X; R Ze e [K]))eem] into & such that for each m [K], we can find subset Sm with at least a (1 - a) proportion of all points with Z; where any K points taken from each of these subsets have pairwise angle at least 6.
In the derivation of Thm. 6, Schiebinger et al. (2015) also let b be such that k (0. b), and be such that ( 2 r > 0 with probability cp. ..... are then other constant that depends only on and r.
21

---

Published as a conference paper at ICLR 2024
Table 3: Citation network details.
Nodes (N)
Edges
Features
Classes (C)
Cora
2708
10556
1433
7
CiteSeer
3327
9104
3703
PubMed
19717
88648
500
3
In conjunction with other works on the topic, they also defined tail decay parameter:
K
(X)
(1)
TP
(68)
1m
m==
and an extra requirement and the difficulty function: that there exists d > such that:
1
(
(
K)
+ S cl min (IP).
(69)
min
In words, it means that the indivisibility parameter of the mixture model is not too small relative to the clustering function. Finally, in the statement of Thm. 6, the difficulty parameter is reparameter-
ized as the left hand side of Eq. (69):
(1/=+/+ Vn
[1+ +
on (1) = (P; +
(70)
r
min (P)
where n is the number points the dataset.
G ADDITIONAL EXPERIMENT DETAILS
All the code for the numerical experiments was written using the PyTorch and PyTorch Geometric libraries. The first set of experiments was A6000 GPU.
Intel i7 CPU, and the second set NVIDIA
Transferability for node classification. The details of the citation network datasets used in this experiment are displayed in Table 3. To perform graphon sampling, the nodes these networks were sorted by degree. We considered 60-20-20 sainiiggvallidation-tsst random split of the data for each realization. In all scenarios, we trained a GNN consisting of a 2-layer GCN with embedding dimension 32 and ReLU nonlinearity, and readout layer followed by softmax. We minimized the negative log- logelikllhood using ADAM with learning rate 0.001 and default forgetting factors over 100 training epochs.
Positional encodings for graph classification. We anonymized the MalNet -iny dataset by remov- ing the node features and replacing them with the all-ones signal. Since we focus on large graphs, we further removed any graphs with less than 4500 nodes. This brought the number of classes down to 4, and we additionally removed samples from certain classes at random to balance the class sizes, yielding dataset with 216 graphs in total (54 per class). We considered 60-20-20 random split of the data for each realization. In all scenarios, we trained a GNN consisting 4-layer GCN with embedding dimension 64 and ReLU nonlinearity, and 1 readout layer with mean aggregation followed by softmax. We minimized the negative log-likelihood using ADAM with batch size 8, learning rate 0.001 and default forgetting factors over 150 training epochs. The PEs the 10 first normalized Laplacian eigenvectors, and to obtain the graphon-sampler subgraph, we fix À A q = 20, p 10, communities, and 10.
22


Reviews:
[{"review_id": "XXyNQgcJg1", "reviewer": "Reviewer_KQ8B", "summary": "This paper proposes a novel signal sampling theory on a type of graph limit called a graphon. The authors demonstrate a Poincaré inequality for graphon signals and show that the complements of node subsets satisfying this inequality are unique sampling sets for Paley-Wiener spaces of graphon signals. They leverage connections with spectral clustering and Gaussian elimination to prove the consistency of these sampling sets. They also design a graphon signal sampling algorithm for large graphs and validate its performance on graph machine learning tasks.", "questions": "1. Given that the paper focuses on large graphs, how does the proposed graphon signal sampling algorithm scale with the size of the graph? While the paper discusses theoretical aspects and empirical performance, it does not delve into scalability and computational efficiency. Can the authors provide insights or discussions on how their algorithm performs as the graph size increases?\n\n2. The authors have demonstrated the utility of their method on specific tasks. However, how broadly applicable is the proposed method across different graph machine learning tasks? Can the authors provide examples or discussions on how their method could be applied to other types of problems within the graph machine learning domain?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper introduces an innovative approach to signal sampling on large-scale graphs using graphons, a type of graph limit, making it a significant contribution to the field.\n\n2. The authors successfully prove a Poincaré inequality for graphon signals and demonstrate that the complements of node subsets adhering to this inequality form unique sampling sets. These solid theoretical foundations enhance the reliability of their proposed methodology.\n\n3. The authors make a critical contribution by relating bandlimitedness in graphon signal space to optimal sampling sets. This achievement not only generalizes previous findings on finite graphs but also offers a new perspective towards problem-solving in the field.", "weaknesses": "The paper does not compare the computational efficiency of the proposed method with existing techniques in the field. Such a comparison could show whether the new method offers improvements in terms of time efficiency.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Q9DZBJiQt4", "reviewer": "Reviewer_1oL4", "summary": "This work considers the extension of sampling theory for bandlimited graph signals to signals on graphons, generalizing the notion of a finite sampling set for graphs to a measurable sampling set for graphons. With this notion in hand, the authors propose an algorithm for consistent sampling, as well as demonstrate its utility in training and inference with GNNs.", "questions": "1. In the statement of Theorem 2, signals $X\\in L^2(S)$ are considered, but then the operator $L$ is applied to $X$. It is not clear here which Laplacian $L$ is: I presume it is the scaled normalized Laplacian of $\\Gamma(S)$. My question, then, is how is the Laplacian understood to act on $X$ when $X$ is not a signal in $L^2(D)$, but rather $L^2(S)$. Is there a canonical inclusion $L^2(S)$ in $L^2(D)$ that I am missing here? Please clarify the statement of Theorem 2. Could you please provide a comment on Point 2 in the weaknesses section above? In particular, I would like to see further justification for applying methods based on signal bandlimitedness to the datasets used in Section 6. It is not obvious to me if these signals are bandlimited, in which case I have no reason to believe that the uniqueness sets yield stable representations of the signals.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "1. This paper reads very well: relevant background, theory, and results are presented clearly and in a logical manner. I can tell that the authors put a lot of thought into how this paper should be presented, which is very much appreciated.\n2. The results offered by the authors are novel and interesting, while still fitting well with the literature on graph/graphon signal processing.\n3. In studying this problem, the authors do not restrict to one single approach. Rather, they show two different solutions to Problem 2 via different methods, which makes for a very good discussion.\n4. In Section 5, the authors make a concrete connection between their theory of graphon uniqueness sets and applications to large graphs.", "weaknesses": "1. Applying knowledge of the uniqueness set for a graphon to graphs sampled from that graphon is difficult without knowing about the latent position of the graph's nodes. The authors acknowledge this weakness at the end of Section 5, though, so I don't count this as too strong of a weakness.\n2. It is not clear how robust the constructed uniqueness sets are to violations of perfect bandlimitedness. For instance, if a signal is only approximately bandlimited w.r.t. some cutoff frequency $\\lambda$, I would hope that a reconstruction of that signal using a uniqueness set for $\\lambda$ would be stable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qBsJyIOxaG", "reviewer": "Reviewer_3x8Y", "summary": "This paper studies graph reductions from the perspective of graphons. It finds a subset of vertices such as a signal on them can be uniquely reconstructed on the rest of the graph, given that the signal comes from a limited family. When the family of signals are coming from the top few eigenvalues, it gives an algorithms based on sampling points from intervals that form graphons. The effectiveness of this method is then experimentally tested against node classification and eigenvalues.", "questions": "Does the theorems developed in Section 4 imply a direct bound on the quality of applying the algorithm in Section 5 to node classification?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is closely connected with the extensive literature on graphons, as well as prior works on graph size reductions. It gives both theoretical bounds as well as experimental verifications of the approaches.", "weaknesses": "The algorithms as well as theorems in the paper feel more motivated by the theory of graphons than concrete applications. While there is a lot of general utility in such work, the amount of definitional work feels overwhelming to me, especially given that the end goal is to preserve eigenvalues / quality of classification algorithms. However, this is understandable given the extensive depth of this topic.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CTPTJUlcqG", "reviewer": "Reviewer_2prr", "summary": "The authors propose a theory on signal sampling from graphons and provide a poincare type inequality for graphon signals. In particular, they show that unique sampling sets on a convergent graph sequence converge to unique sampling sets on the corresponding graphon. They propose a graphon signal sampling algorithm and empirically test its performance.", "questions": "- One canonical way to motivate graphons is via the Aldous-Hoover theorem, which motivates a latent variable perspective on graphons if one sees the nodes as exchangeable. I think the paper by Aldous (1981) and Hoover (1979) are classical references that should be cited/acknowledged in studies discussing graphons. \n\n- One potential limitation of the graphon sampling approach is that many real life graphs are sparse, but graphons can only be reasonably motivated by dense graphs. Obviously, this is not a short coming of this research (since it is an open problem), but I think it would be reasonable for the authors to mention this explicitly in their paper to provide a comprehensive/balanced perspective.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality and Novelty: The approach that the authors propose is, to the best of my knowledge, original and novel.\nSignificance: Nowadays it is certainly an interesting and important topics to study graphons, graph signal processing, and related tasks in ML. The machinery proposed in this paper, such as the graphon Laplacian and the graphon fourier transform, are themselves interesting constructs that could find wider adoption potentially. \nQuality: The technical claims are, to the best of my knowledge, sound and reasonable, although I did not check any proofs in the appendix in detail. The convergence results on uniqueness sets are sufficiently deep for publication at a venue like ICLR. \nClarity: The article is written moderately clearly, but is presented in a very dense manner.", "weaknesses": "The main weakness is in the presentation and exposition: \n\nThe paper is presented in a very dense way,  My main suggestion to the authors is to provide more motivation and background for the readers. For example, a general ML audience might not have a very good idea of what a poincare inequality is. Setting the motivation and background up more allows for a broader audience and a more enjoyable read.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)