Unveiling the sampling density in non-uniform geometric graphs
Authors: Raffaele Paolino
Aleksandar Bojchevski
Stephan Günnemann
Gitta Kutyniok
Ron Levie
Venue: ICLR 2023 poster (2023)
Keywords: graph neural network
graph representation learning
spectral method
non-uniform sampling
geometric graph
graphon

Abstract: A powerful framework for studying graphs is to consider them as geometric graphs: nodes are randomly sampled from an underlying metric space, and any pair of nodes is connected if their distance is less than a specified neighborhood radius. Currently, the literature mostly focuses on uniform sampling and constant neighborhood radius. However, real-world graphs are likely to be better represented by a model in which the sampling density and the neighborhood radius can both vary over the latent space. For instance, in a social network communities can be modeled as densely sampled areas, and hubs as nodes with larger neighborhood radius. In this work, we first perform a rigorous mathematical analysis of this (more general) class of models, including derivations of the resulting graph shift operators. The key insight is that graph shift operators should be corrected in order to avoid potential distortions introduced by the non-uniform sampling. Then, we develop methods to estimate the unknown sampling density in a self-supervised fashion.  Finally, we present exemplary applications in which the learnt density is used to 1) correct the graph shift operator and improve performance on a variety of tasks, 2) improve pooling, and 3) extract knowledge from networks. Our experimental findings support our theory and provide strong evidence for our model.

Published as a conference paper at ICLR 2023
UNVEILING THE SAMPLING DENSITY IN NON-UNIFORM GEOMETRIC GRAPHS
Raffaele Paolino
Aleksandar Bojchevski
Department of Mathematics & Munich Center for Machine Learning (MCML), Maaiigg-axxmmiiinss--ne paolino @ mathe
CISPA Helmholtz Center for Information Security bojchevski@ccispar
München
Stephan Günnemann
Gitta Kutyniok
Department of Computer Science & Munich Data Science Institute, Technical University of Munich
Department of Mathematics & Munich Center for Machine Learning (MCML.), -aeee--aaiiiii-nniiiiiaa München kutyniok muuce
S.guennemann tum.de
Ron Levie
Faculty of Mathematics,
Technion - Israel Institute of Technology levieron @ technion.ac.il
ABSTRACT
A powerful framework for studying graphs is to consider them as geometric graphs: nodes are randomly sampled from underlying metric space, and any pair of nodes is connected if their distance less than specified neighborhood radius. Currently, the literature mostly focuses uniform sampling and constant neighborhood radius. However, real-world graphs are likely to be better represented by a model in which the sampling density and the neighborhood radius both vary the latent space. For instance, in a social network communities can be modeled as densely sampled areas, and hubs nodes with larger neighborhood radius. In this work, we first perform rigorous mathematical analysis of this (more general) class of models, including derivations of the resulting graph shift operators. The key insight is that graph shift operators should be corrected in order to avoid potential distortions introduced by the non-uniform sampling. Then, we develop methods estimate the unknown sampling density in self- self-supervised fashion. Finally, we present exemplary applications in which the learned density is used to 1) correct the graph shift operator and improve performance pooling, and 3) extract knowledge from networks. Our experimental findings support theory and provide strong evidence for our model.
variety of tasks, 2) improve
INTRODUCTION
Graphs are mathematical objects used to represent relationships among entities. Their use is ubiq- uitous. ranging from social networks recommender systems, from protein-protein interactions to functional brain networks. Despite their versatility, their non-cuclidean nature makes graphs hard analyze. For instance, the indexing of the nodes is arbitrary, there no natural deñnition of orientation, and neighborhoods can vary in size and topology. Moreover, it is not clear how to compare a general pair of graphs since they can have a different number of nodes. Therefore, new ways of thinking about graphs were developed by the community. One approach is proposed in graphon theory (Lvvász 2012): graphs are sampled from continuous graph models called graphons, and any two graphs of any size and topology can be compared using certain metrics defined in the space of graphons. geometric graph is an important case of a graph sampled from a graphon. In a geometric graph, set of points is uniformly sampled from metric-measure space, and every pair of

---

Published as a conference paper at ICLR 2023
points is linked if their distance is less than specified neighborhood radius. Therefore, a geometric graph inherits a geometric structure from its latent space that can be leveraged to perform rigorous mathematical analysis and to derive computational methods.
Geometric graphs have a long history, dating back to the 60s (Gilbert extensively used to model complex spatial networks (Barthelemy [001] One of the first models of geometric graphs is the random geometric graph (Penrose 2003). where the latent space is a Euclidean unit square. Various generalizations and modifications of this model have been proposed in the literature, such as random rectangular graphs (Estrada & Sheerin 2015). random spherical graphs FAllen-Perking 2018). and random hyperbolic graphs (Krioukov al. (010)).
1961). They have been
Geometric graphs are particularly useful since they share properties with real-world networks. For instance, random hyperbolic graphs are small-world, scale-free, with high clustering (Papadopoulos et al. 2010 Gugelmann et al. (2012). The small-world property asserts that the distance between any two nodes is small, even if the graph is large. The scale-free property is the description of the degree sequence heavy-tailed distribution: a small number of nodes have many connections, while the rest have small neighborhoods. These two properties are related to the presence of hubs - nodes with large neighborhoods while the high clustering is related to the network's community structure.
However, standard geometric graph models focus mainly on uniform sampling, which does not describe real-world networks well. For instance, in location-based social networks, the spatial distribution of nodes is rarely uniform because people congregate around the city centers (Cho et al. 2011, Wang & González 2009p. In online communities such the LiveJournal social network, non-uniformity arises since the probability of befriending a particular person is inversely proportional to the number of closer people (Hu et al., 2011 Liben-Nowell al. 2005). In WWW network, there are more pages for popular topics than obscure ones. In social networks, different demographics (age, gender, ethnicity, etc.) may join a social media platform different rates. For surface meshes, specific locations may be sampled more finely, depending on the required level of detail.
The imbalance caused by non-uniform sampling could affect the analysis and lead biased results. For instance, Janssen et al. (2016) show that incorrectly assuming uniform density consistently overestimates the node distances while using the (estimated) density gives more accurate results. Therefore, it is essential to assess the sampling density, which is one of the main goals of this paper.
Barring a few exceptions, non-uniformity is rarely considered in geometric graphs. [yer & Thacker (2012) study a class of non-uniform random geometric graphs where the radii depend on the location. Marttnez-Martinez et { (2022) study non-uniform graphs on the plane with the density functions specified in polar coordinates. Pratt et al. (2018) consider temporal connectivity in finite networks with non-uniform measures. In all of these works, the focus is on (asymptotic) statistical properties of the graphs, such as the average degree and the number of isolated nodes.
1.1 OUR CONTRIBUTION
While traditional Laplacian approximation approaches solve the direct problem approximating a known continuous Laplacian with a graph Laplacian in this paper we solve the inverse problem- constructing graph Laplacian from an observed graph that is guaranteed to approximate an unknown continuous Laplacian. We believe that our approach has high practical significance, as in practical data science on graphs, the graph is typically given, but the underlying continuous model is unknown.
To be able solve this inverse problem, we introduce the non-uniform geometric graph (NuG) model. Unlike the standard geometric graph model, NuG is generated by a non-uniform sampling density and non-constant neighborhood radius. In this setting, we propose class of graph shift operators (GSOs), called non-uniform geometric GSOs, that are computed solely from the topology of the graph and the node/edge features while guaranteeing that these GSOs approximate corresponding latent continuous operators defined on the underlying geometric spaces. Together with Dasoulas et al. (2021) and [ahbi (2021), our work can be listed as a theoretically grounded way to learn the GSO.
Justified by formulas grounded in Monte-Carlo analysis, we show how to compensate for the non- uniformity in the sampling when computing non-um con-unffomm geometric GSOs. This requires having estimates both of the sampling density and the neighborhood radii. Estimating these by only observing the graph is a hard task. For example, graph quantities like the node degrees are affected both by the density and the radius, and hence, it is hard to decouple the density from the radius by only observing
2

---

Published as a conference paper at ICLR 2023
the graph. We hence propose methods for estimating the density (and radius) using self supervvieri approach. The idea is to train, against some arbitrary task, a spectral graph neural network. where the GSOs underlying the convolution operators are taken learnable density. For the model to perform well, it learns to estimate the underlying sampling density, even though it is not directly supervised to do so. We explain heuristically the feasibility of the self-supervision approach on a sub-class of non-uniform geometric graphs that we call geometric graphs with hubs. This is a class of geometric graphs, motivated by properties of real-world networks, where the radius is roughly weiee constant, and the sampling density is smooth.
non-uniform geometric GSO with
We show experimentally that the NuG model can effectively model real-world graphs by training a graph autoencoder, where the encoder embeds the nodes in an underlying geometric space, and the decoder produces edges according to the NuG model. Moreover, we show that using our non- uniform geometric GSOs with learned sampling density in spectral graph neural networks improves downstream tasks. Finally, we present proof-of-concep applications in which we use the learned density to improve pooling and extract knowledge from graphs
2 NON-UNIFORM GEOMETRIC MODELS
In this section, we define non-uniform geometric GSOs, and a subclass of such GSOs called geometric graphs with hubs. To compute such GSOs from the data, we show how to estimate the sampling density from given graph using self-supervision.
2.1 GRAPH SHIFT OPERATORS AND KERNEL OPERATORS
We denote graphs by 9 = EV, where V is the set of nodes, [V] is the number of nodes, and E is the set of edges. A one-dimensional graph signal is mapping dimension E N, a signal is a mapping u : V + IR.." In graph data science, typically, the data comprises only the graph structure and node/edge features u. and the practitioner has the freedom to design a graph shift operator (GSO). Loosely speaking, given graph g = (V, E), a GSO is any matrix L E |R| | that respects the connectivity of the graph, i.c., Li,j 0 whenever j) & E, i i (Mateos et al. 2019). GSOs are used in graph signal processing to define filters, as functions of the GSO of the form [L), where f: R + R is, e.g., polynomial (Defferrard et al. 2016) or a rational (Levie et al. 2019) function. The filters operate on graph signals u by [L) Spectral graph convolutional networks are the class of graph neural networks that implement convolutions as filters. When a spectral graph convolutional network is trained, only the filters f : R - R are learned. One significant advantage of the spectral approach is that the convolution network is not tied to specific graph, but can rather be transferred between different graphs of different sizes and topologies.
V - R. For higher feature
In this work, we see GSOs as randomly sampled from kernel operators defined underlying geometric spaces. The underlying spaces are modelled as metric spaces. To allow modeling the random sampling of points, each metric space is also assumed to be a probability space.
Definition 1. Let (S, d. μ) be metric-probablig let m E (S let K E (S x S). The probiicprobabilly Laplaciaa L LK. is defined as
space with probability measure μ and metric d;
L: L + (S), (Lu)(x)= / K(x, y) u(y) dulv) m(x)u(a))
For example, let S be Riemannian manifold, and take K K(x,)) (B.,))())/v(BB(c) and m(x) = 1, where B, (1:) is the ball or radius about ær In this case, the operator LK,m approximates the Saplace-Beltrant operator when a is small (Burago et al. 2019).
A random graph is generated by randomly sampling points from the metric- pettic-probabilitty space (S, d, jt).
As a modeling assumption, we suppose the sampling is performed according to a measure v. We assume is weighted measure with respect to μ, i.e., there exists density function p: S (0, xo)
'A metric-probability space a triple (5, d. p), where S is set of points, and / the Borel measure corresponding to the metric d.
AA function S + R is an element of I, (S) iff. 3M 0o: : nffa e S: lo(x)) > M)) = 0. The norm in I. (S) is the essential supremum, i.c. inf M 2 0: [=(x)) < M for almost every E S).
3

---

Published as a conference paper at ICLR 2023
such that dz(y)= p(y) du(y 1
We assume that p bounded away from zero and infinity. Using change of variable, is easy to see that
(Cu)(x) ((x,y) p(u) ((y) - m(x) u(x).
Let (x.) be random independent sample from S according the distribution v. The corresponding sampled GSO defined by
ي - N ()) -mzt).
(2)
Given a signal ( and its sampled version {u( ( ) 1--1- it is well known that (Lu);
approximates Lu(x;) for every i E {I,...,. N) (Hein et al. 2007 von Luxburg et al. 2008).
2.2 NON-UNIFORM GEOMETRIC GSOS
According to (2) GSO L can be directly sampled from the metric-probabilin Laplacian C. However, such an approach would violate our motivating guidelines, since we are interested GSOs that can be computed directly from the graph structure, without explicitly knowing the underlying continuous kernel and density. In this subsection, we define a class of metrie-probabiilig Laplacians that allow such direct sampling. For that, we first define model of adjacency in the metric space.
Definition 2. Let (S, d, μ) be a metric- mmtric-probabbiltyy space. Let a : S - (0, +oc) be a non-negative measurable function named neighborhood radius. The neighhorkood model A is defined as set- valued function that assigns to each x E S the ball ((x) = [v E S d(z, v) I max (a(x), avv)) }.
Since y E Mxx)) implies E (y) for all z, y S. Def. 2 models only symmetric graphs. Next, define a class of continuous Laplacians based on neighborhood models.
Definition 3. Let (S, d, μ4) be a petric-probabilityy space, and N neighborhood model as in Def. Let () I + be a continuous function for every i E {l...., 4). The metric-probabillty Laplacian model is the kernel operator Lx that operates signals S R by
/ (") (M())))) m²)) (m ) u(y) du(y)
(LNr) (z)
((#)
f m3 (μ (M(x))) m4 (μ (N(()) du(v) u(x). (())
In order to give concrete example, suppose the neighborhood radius a<x) = a is a constant, (x) = m (3) (x)) = x-1, and (x) = (x) 1, then (3) gives
(Cxu)(x) = (B. (w)
u(y) du(y) - u(x),
which is an approximation of the Laplace-Beltne Beltramii operator.
Since the neighborhood model of S represents adjacency in the metric space, make the modeling assumption that graphs are sampled from neighborhood models, as follows. First, random independent points x { are sampled from S according to the "non-uniform" distribution
before. Then, an edge is created between each pair 2, and xy if H E (Nx;), to form the graph g. Now, GSO can be sampled from metric-probabile continuous model is known. However, such knowledge is not required, since the special structure of
Laplacian model Cx by (2) if the underlying
the metric-probabilit Laplacian model allows deriving the GSO directly from the sampled graph G and the sampled density (x(+)) Def. 4 below gives such a construction of GSO. In the following, given a vector u E RN and a function m + R, we denote by m(u) the vector {m(u,)), and by diag(u) e N the diagonal matrix with diagonal
Formally, is absolutely continuous with respect μ4, with Radon-Nykodin derivative p.
4

---

Published as a conference paper at ICLR 2023
Definition 4. Let G (V,E) be graph with adjacency matrix A: let p : - (0, oo) be graph signal, referred to as graph density. The non -nn-ffoorm geometric GSO is defined to be
Lg == N 'D A DD - -N-1 -Niig (D Ab
(4)
where A A diag(p) -1 and D diag (m (N-1 Ap1))
Def. 4 can retrieve, as particular cases, the usual GSOs, shown in Tab. in Appendix C For example, in case of m (x) = (x) x-
m m()) (x) 1, and uniform sampling (4) leads to the random-walk Laplacian Lg.1 = D A I. The non-uniform geometric GSO
in Det. 4 the Monte-Carlo approximation of the metric- probriccpobbbility Laplacian in Def. 3 This is
shown in the following proposition, whose proof can be found in [Apenddxx D
Proposition 1. Let g = (V,E) be a random graph with i..dd sample x = { from the metric- probability space (S, d. μ1) with neighborhood structure N. Let Lg.p be the non-uniform geometric GSO as in Def. Let u L (S) and {u(z,)}; Then, for every I....,N..
E (LL. (Cxu)(zz)) O(N
(5)
In Appendix D we also show that, in probability at least 1 - p. it holds
Vie [1....,,N} uL) (CNr)(zz)) O (N- (N-
log(A))
(6)
means that if we given graph that was sampled from neighborhood model, and we know (or have an estimate of) the sampling density at every node of the graph, then we can compute a GSO according to that is guaranteed to approximate corresponding unknown metric-probbability Laplacian. The next goal is hence to estimate the sampling density from a given graph.
Prop.
2.3 INFERRING THE SAMPLING DENSITY
In real-world scenarios, the true value of the sampling density is not known. The following result gives first rough estimate of the sampling density in special case.
Lemma 1. Let (S, d, μ)) be metric- peobbbbprob space: let N' be neighborhood model; let be weighted measure with respect to p with continuous density bounded away from zero and infinity. There exists a function e S - S such that c(x) (xx) and (poc)(z) = (u((()))(((((())
The proof can be found in Appendix D In light of Lemma I if the neighborhood radius of z is small enough, if the volumes pxN(x) are approximately constant, and if p does not vary too fast, the sampling density at is roughly proportional to ((N())), that is, the likelihood point is drawn from (xx).. Therefore, in this situation, the sampling density p(x) can be approximated by the degree of the node x. In practice, are not constant. Still, a normalization of the GSO by the degree can soften the distortion introduced by non-uniform sampling, that the degree of node is a good input feature for method that learns the sampling density from the graph structure and the node features. Such method developed next.
are interested in graphs where the volumes of the neighborhoods p(N(xx)
least locally in areas where (()( is slowly varying. This suggests
2.4 GEOMETRIC GRAPHS WITH HUBS
When designing a method to estimate the sampling density from the graph, the degree is not sufficient input parameter. The reason is that the degree of node has two main contributions: the sampling density and the neighborhood radius. The problem of decoupling the two contributions is difficult in the general case. However, if the sampling density is slowly varying, and if the neighborhood radius is piecewise constant, the problem becomes easier. Intuitively, a slowly varying sampling density causes slight change in the degree of adjacent nodes. In contrast, sudden change in the degree caused by a radius jump. In time-frequency analysis and compressed sensing, various results guarantee the ability to separate signal into its different components, e.g., piccewise constant and smooth components (Do et al.] 2022) Donoho & Kutyniok 2013) Gribonval & Bacry 2003).
This motivates our model of geometric graphs with hubs.
5

---

Published as a conference paper at ICLR 2023
Definition 5. A geometric graph with hubs is random graph with non- non- uniuurfoomm geometric GSO, sampled from a metric-probability space (S, d. μ) with neighborhood model NV, where the sampling density is Lipschitz continuous in S and (x)) is piecewise constant.
We call this model a geometric graph with hubs since we typically assume that (xN(x)) has a low value for most points x E S, while only a few small regions, called hubs, have large neighborhoods. In In/tccioon 3.1] we exhibit that geometric graphs with hubs can model real-world graphs. To validate this, we train a graph auto-encoder on real-world networks, where the decoder is restricted to be geometric graph with hubs. The fact that such decoder can achieve low error rates suggests that real-world graphs can often be modeled as geometric graphs with hubs.
Geometric graphs with hubs are also reasonable from a modeling point of view. For example, it is reasonable to assume that different demographies join social media platform at different rates. Since the demographic is directly related to the node features, and the graph roughly exhibits homophily, the features are slowly varying over the graph, and hence, so the sampling density, On the other hand, hubs in social networks are associated with influencers. The conditions that make certain user an influencer are not directly related to the features. Indeed, the node features in a social network user interests, users that follow an influencer tend to share their features with the influencer, so the features themselves are not enough to determine if a node is deemed to be a center of a hub or not. Hence, the radius does not tend to be continuous over the graph, and, instead, is roughly constant and small over most of the graph (non-influencerss) except for some narrow and sharp peaks (influencers).
2.5 LEARNING THE SAMPLING DENSITY
In the current section, we propose a strategy to assess the sampling density p. As suggested by the above discussion, the local changes in the degree of the graph give us a lot of information about the local changes in the sampling density and neighborhood radius of geometric graphs with hubs. Hence, we implement the density estimator as a message- message-passing graph neural network (MPNN) θ because it performs local computations and it is equivariant to node indexing, property that both the density and the degree satisfy. Since we are mainly interested in estimating the inverse of the sampling density, O takes input the inverse of the degree and the inverse of the mean degree of the one-hop neighborhood for all nodes in the graph as two input channels.
However, it is not yet clear how train O. Since in real-world scenarios the ground-truth density is not known, we train θ in a self-supervised manner. In this context, we choose a task (link prediction, node graph classification, etc.) on a real-world graph and solve by means of a graph neural network V referred to as task network. Since we want V to depend on the sampling density estimator O, we define V/ spectral graph convolution network based on the non-uniform geometric GSO Lg e.g., GCN (Kipf & Welling 2017). ChebNet (Defferrard et al. 2016) or CayleyNet (Levie let al. 2019). We, therefore, train end-to-end on the given task.
The idea behind the proposed method is that the task depends mostly on the underlying continuous model. For example, shape classification, the label of each graph depends on the surface from which the graph is sampled, rather than the specific intricate structure of the discretization. Therefore, the task network l can perform well if it learns to ignore the particular fine details of the discretization, and focus on the underlying space. The correction of the GSO via the estimated sampling density (4)) gives the network exactly such power. Therefore, we conjecture that θ will indeed learn how to estimate the sampling density for graphs that exhibit homophily. In order to verify the previous claim, and to validate our model, we focus on link prediction on synthetic datasets (see Appendix B). for which the ground-truth sampling density is known. As shown in Fig. the MPNN O is able correctly identify hubs, and correctly predict the ground-truth density in a self-supervised manner.
3 EXPERIMENTS
In the following, we validate the NuG model experimentally. Moreover, we verify the validity of our method first synthetic datasets, then real-world graphs in a transductive (node classification) and inductive (graph classification) setting. Finally, we propose proof-of- applications in explainability, learning GSOs, and differentiable pooling.

---

Published as a conference paper at ICLR 2023
1.30
631
538 820
(a) 8 geometric graph with hubs.
(b) D geometric graph with hubs.
Figure 1: Example of the learned probability density function in link prediction, where the underlying metric space is (a) the unit-circle, and (b) the unit disk. (Left) Ground -rrtt sampling density vs. learned sampling density the nodes. (Right) Degree learned sampling density.
230
0,0
3.50
The
0:55
035
1:10
(a) Citeseer
(b) Cora
(c) Pubmed
1.40
338
5.00
3.0
235
Desider product
Pha pi0tut
030
(d) AmazonComputers
(e) AmazonPhoto
(1) Pageeao
Figure Test AUC for link prediction task function of the dimension of the latent space. Performances averaged across 10 runs on each value of the latent dimension.
3.1 LINK PREDICTION
The method proposed in Section 2.5 applied on synthetic datasets of geometric graphs with hubs (see for details Appendices A. to A.2) In Fig. I shown that θ able to correctly predict the value of the sampling density. The left plots of Figs. la and Tb show that the density is well approximated both at hubs and non-hubs. Looking at the right plots, it is evident that the density cannot be predicted solely from the degree.
Fig. 2 and Fig. in Appendix A.3 show that the NuG model is able to effectively represent world graphs, outperforming other graph auto-encoder methods (see Tab. for the number of parameters of each method). Here, we learn an auto-encoder with four types of decoders: inner product, MLP, constant neighborhood radius, and piecewise constant neighborhood radius corresponding to geometric graph with hubs (see Appendix A.3 for more details). Better performances are reached the graph is allowed be a geometric graph with hubs as in Def. Moreover, the performances of distance and distance+hubs decoder seem to be consistent among different datasets, unlike the inner product and MLP decoders. This corroborates the claims that real-world graphs can be better modeled geometric graphs with non-constant neighborhood radius. Fig. innn (Appedixx A.3 shows the learned probabilities of being hub, and the learned values of and (3, for the Pubmed graph.
3.2 NODE CLASSIFICATION
Another exemplary application is to use non-uniform geometric GSO Lg.p DDef. 4) in spectral graph convolution network for node classification tasks, where the density P; at each node is computed by different graph neural network, and the whole model is trained end-to-end on the task. The details are reported in Appendix A.2 In Fig. 3 we show the accuracy of the best-scoring GSO out of the ones reported in Tab. 3 when the density ignored against the best-scoring GSO when the sampling density is learned. For Citeseer and FacebookPagePage. the best GSOs are the symmetric normalized adjacency matrix. For Cora and Pubmed, the best density-ignored GSO is the symmetric
7

---

Published as a conference paper at ICLR 2023
Citeseor
Cora
(c) Pubmed
(d) AmazonComputers
(e) AmazonPhoto
FacebookPagePPaee
Figure 3: Test accuracy node classification task. Comparison between the best scoring GSOs when the density ignored (I) or learned (L). Results averaged across 10 runs: each point represents the performance at one run
0.0
(a) Combinatorial Laplacian
(b) Symmetric normalized adjacency
Figure 4: Test metries of the graph classification task the AIDS dataset, using the combinatorial Laplacian (a) and the symmetric normalized adjacency (b), averaged over 10 runs. Comparison when the importance p is ignored (I), used to correct the Laplacian (L), used for pooling (P). Each point represents the performance at one run. (a) the best performances are reached when p is used correct the Laplacian, and in (b) when p -1 is used for pooling.
normalized adjacency matrix, while the best density-normalized GSO the adjacency matrix. For AmazonComputers and AmazonPhoto, the best-scoring GSOs are the symmetric normalized Laplacian. This validates our analysis: if the sampling density is ignored, the best choice to normalize the Laplacian by the degree to soften the distortion of non- non-unifone uniform sampling.
3.3 GRAPHI CLASSIFICATION & DIFFERENTIABLE POOLING
In this experiment perform graph classification the AIDS dataset (Riesen Bunke 2008). as explained in Appendix A.2 Fig. 4 shows that the classification performances of a spectral graph neural network are better if quota of parameters is used learn p which is used in con-uniform geometric GSO (Def. 4). The learnable on the AIDS dataset can be used not only to correct the Laplacian but also perform better pooling (see Appendix A.2 for the details). Usually, graph convolutional neural network is followed by global pooling layer in order to extract a representation of the whole graph. A vanilla pooling layer aggregates uniformly the contribution implemented weighted pooling layer that takes into account the importance of each node. As shown in Fig. 4 the weighted pooling layer can indeed improve performances on the graph classification task. Fig. 6 Ojin|Appeddii A.2 shows comparison between the degree, the density learned to correct the GSO and the density learned for pooling. From the plot is clear that the degree cannot predict the density. Indeed, the sampling density nodes with the same degree have different values.
all nodes. We
8

---

Published as a conference paper at ICLR 2023
Figure 5: (Left) Distribution of chemical elements per class (active, inactive respectively in blue, red) computed as the number of compounds labeled active (inactive) containing that particular element divided by the number of active (inactive) compounds. This is a measure of rarity. For example, potassium is present in 5 out of 400 active compounds, and in over 1600 inactive compounds. Hence. it is more rare to find potassium in an inactive compound. (Right) The mean importance of each element when p=1 is used to correct the GSO (L., orange) and when it used for weighted pooling (P, green). Carbon, oxygen, and nitrogen have low mean importance, which makes sense as they are present almost every compound, as shown in the left plot. The chemical elements are sorted according to their mean importance when p is used to correct the GSO (orange bars).
3.4 EXPLAINABILITY IN GRAPH CLASSIFICATION
In this experiment, we show how to use the density estimator for explainability. The inverse density vector p-1 can be interpreted as measure of importance of each node, relative to the task at hand, instead of sampling density. Thinking about p as importance is useful when the graph is not naturally seen randomly generated from graphon model. We applied this paradigm to the AIDS dataset, as explained in the previous subsection. The better classification performances when p is learned demonstrates that p an important feature for the classification task, and hence, it can be exploited to extract knowledge from the graph. We define the mean importance of each chemical element as the of all values of p corresponding to nodes labeled divided by the number of nodes labeled e. Fig. 5 shows the mean importance of each element, when p is estimated by using it module in the task network in ways. (1) The importance p is used correct the GSO. (2) The importance p is used in a pooling layer, that maps the output of the graph neural network V to one feature of the form Σ/ Pj ' (X),. where X denotes the node features. In both cases, the most important elements are the same; therefore, the two methods seem to be consistent.
CONCLUSIONS
In this paper, we addressed the problem of learning the latent sampling density by which graphs sampled from their underlying continuous models. We developed formulas for representing graphs given their connectivity structure and sampling density using non-uniform geometric GSOs. We then showcased how the density of geometric graphs with hubs can be estimated using supervuuervii and validated approach experimentally. Last, showed how knowing the sampling density can help with various tasks, e.g., improving spectral methods, improving pooling, and gaining knowledge from graphs. One limitation of our methodology is the difficulty in validating that real-world graphs are indeed sampled from latent geometric spaces. While we reported experiments that support this modeling assumption, an important future direction is develop further experiments and tools to support our model. For instance, can we learn density estimator on one class of graphs and transfer it another? Can we use ground-truth demographic data validate the estimated density in social networks? We believe future research will shed light on those questions and find new ways to exploit the sampling density for various applications.

---

Published as a conference paper at ICLR 2023
REFERENCES
Alfonso Allen-Perkins. Random spherical graphs. Physical Review E, 98(3):032310, September 2018. ISSN 2470-0045, 2470-0053.
doi: 10.1 10.100//hhysReee.988.2.533
Mare Barthelemy. Spatial Networks. Physies Reports, 499(1-3):1-101) February 2011. ISSN 03701573. doi:
Dmitri Burago, Sergei Ivanov, and Yaroslav Kurylev. Spectral stability of metric-measure Laplacians. Israel Journal of Mathematies, 232(1):125-11) August 2019. ISSN 0021-21722 1565-8511. doi:
1880077/1115-01111 1865-7.
Eunjoon Cho, Seth A. Myers, and Jure Leskovec. Friendship and mobility: User movement in location- based social networks. In Proceedings of the 17th ACM SIGKDD International Conference Knowledge Discovery and Data Mining KDD '11, pp. 1082, San Diego, California, USA, 2011. doi: 10. 0011445/2020408.22205779
ACM Press. ISBN 978-1-4503-081333 13-00011117..000
Fan R. K. Chung. Spectral Graph Theory. Number 92 in Regional Conference Series in Mathematics. Published for the Conference Board the mathematical sciences by the American Mathematical Society, Providence, R.I, 1997. ISBN 278-0-8218-0315-2
Dragos Cvetkovic and Slobodan Simic. Towards a spectral theory of graphs based on the signless Laplacian, Publications de I'Instiuu Mathematique, 85(99):19 2009. ISSN 0350-1302, 1820-7405. doi: 10.2296/PLM0999019C.
George Dasoulas, Johannes F. Lutzeyer, and Michalis Vazirgiannis. Learning parametrised graph shift operators. In International Conference on Learning Representations, 2021. URL https
/ Eorum=id-001rrveee:.
//openreview.co net/
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016.
Van Tiep Do, Ron Levie, and Gitta Kutyniok. Analysis of simultaneous inpainting and geometric separation based on sparse decomposition. Analysis and Applications, 20(02):303-352 March 2022. ISSN 0219-5305, 1793-6861. doi: 10.1142/502995505221220 150007
David Donoho and Gitta Kutyniok. Microlocal Analysis of the Geometric Separation Problem. Communications on Pure and Applied Mathematics, 6661):1-477 January 2013. ISSN 00103640.
doi: 1.11002cppa.1444
Ernesto Estrada and Matthew Sheerin. Random Rectangular Graphs. Physical Review E, 91(4): 042805, April 2015. ISSN 1539-3755, 1550-2376. doi: 10. 1ew110//yyssee..1....o. 0422055.
E. Gilbert. Random Plane Networks. Journal of the Society for Industrial and Applied Mathematics, 94):5333554, December 1961. ISSN 0368-4244 -484,, 2168-3484. doi: 10. 10.1137/0109045.
R. Gribonval and E. Bacry. Harmonic decomposition of audio signals with matching pursuit. IEEE Transactions on Signal Processing, 5111)100111,, January 2003. ISSN 1053-587X. doi: 10.1 10.11999/SPP200280055522
Luca Gugelmann, Konstantinos Panagiotou, and Ueli Peter. Random Hyperbolic Graphs: Degree Sequence and Clustering. In Automata, Languages, and Programming, volume 7392, pp. 573-585, Springer Berlin Heidelberg, Berlin, Heidelberg, 2012. ISBN 978-3-642-3158888 978-3-642-31555 5. doi: 10.1007/978 3-4--31585--5551.
Matthias Hein, Jean-Y vee Audibert, and Ulrike von Luxburg. Graph laplacians and their convergence on random neighborhood graphs. Journal of Machine Learning Research, 8(48): 2007.
Yanqing Hu, Yong Li, Zengru Di, and Ying Fan. Navigation in non-uniform density social networks, January 2011.
Srikanth K. Iyer and Debleena Thacker. Nonuniform random geometric graphs with location- dependent radii. The Annals of Applied Probability, 22(5), October 2012. ISSN 1050-5164, doi: 10.1214/1 1-AAP823.
10

---

Published as a conference paper at ICLR 2023
Jeannette Janssen, Pawel Pralat, and Rory Wilson. Nonuniform Distribution of Nodes in the Spatial Preferential Attachment Model. Internet Mathematicc, 12(1-2)11114144 March 2016. ISSN 1542-7951, 1944-9488. doi: 10. 00.100/15427951.015.11.000
Diederik P. Kingma and Jimmy Ba. Adam: method for stochastic optimization. In Interna- tional Conference on Learning Representations, 2015. [RL.tttp://axxi wttp://wwwwgg//////////a//osss// 1412 6980
Thomas N. Kipf and Max Welling, Variational Graph Auto-Encoders. arXiv:1611.07300 [cs, stat), November 2016.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks In International Conference on Learning Representations, 2017. URL htttpps://oppeeeeeaeeet
net/
Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguñá. Hyperbolic geometry of complex networks. Physical Review E, 82(3):036106, September 2010.
ISSN 1539-3755, 1550-2376.
doi: 10.1 00.100/PhysReeE.822061000
Ron Levie, Federico Monti, Xavier Bresson, and Michael M. Bronstein. CayleyNets: Graph Convolutional Neural Networks With Complex Rational Spectral Filters. IEEÉ Transactions on Signal Processing, 67(1):97-109 January 2019, ISSN 1053-587X, 1941-0476. doi: 10.1 1099TSPSS 2018.2879624.
David Liben-Nowell, Jasmine Novak, Ravi Kumar, Prabhakar Raghavan, and Andrew Tomkins. Geographic routing in social networks. Proceedings of the National Academy of Sciences, 102(33): 11623-11628, August 2005. ISSN 0027-8424, 1091-6490. doi: 10. (0.1073/pnas.00 (50a000 18002.
László Lovász. Large Networks and Graph Limits, volume 60 of Colloquium Publications. American Mathematical Society, Providence, Rhode Island, December 2012. ISBN 978-0-8218-9085-1, 978-1-4704-1583--) doi: 10. 10.0////co1/06.
C. T. Marthnez-Marttne,, A. Mendez-Bermüddez, Francisco A. Rodrigues, and Ernesto Estrada. Nonuniform random graphs on the plane: A scaling study. Physical Review E, 105(3):034304, March 2022. ISSN 2470-0045, 2470-0053. doi: 10. 103/PhysRevE.10..0055.
Gonzalo Mateos, Santiago Segarra, Antonio G. Marques, and Alejandro Ribeiro. Connecting the Dots: Identifying Network Structure via Graph Signal Processing. IEEE Signal Processing Magazine, 36(3):16-43, May 2019. ISSN 1053-5888, 1558-0792. doi: 10. (0.11009/SP..21882880000
Fragkiskos Papadopoulos, Dmitri Krioukov, Marian Boguna, and Amin Vahdat. Greedy Forwarding in Dynamic Fcale-Free Networks Embedded in Hyperbolic Metric Spaces. In 2010 Proceedings IEEE INFOCOM, pp. 1-9, March 2010. doi: 10. 10.100//NNCCMM220000552222
Mathew Penrose. Random Geometric Graphs. Number 5 in Oxford Studies in Probability. Oxford University Press, Oxford New York, 2003. ISBN 978-0-19 19-866---....3
Pete Pratt, Carl P. Dettmann, and Woon Hau Chin. Temporal connectivity in finite networks with nonuniform measures. Physical Review E, 98(5):052310, November 2018. ISSN 2470-0045. 2470-0053. doi: (t..////hyyR......0522..1.
Kaspar Riesen and Horst Bunke. IAM Graph Database Repository for Graph Based Pattern Recogni- tion and Machine Learning. In Structural, Syntactic. and Statistical Pattern Recognition, volume 5342, pp. 287-297. Springer Berlin Heidelberg, Berlin, Heidelberg, 2008. ISBN 978-3-540-89688 3, 3,978-3-540-89688 doi: 10.1007/978-3 111-8-----0---889----88 33.
Benedek Rozemberezki. Carl Allen, and Rik Sarkar. Multi-Scale attributed node embedding. Journal of Complex Networks, 9())cnab004, May 2021. ISSN 2051-1310, 2051-1329. doi: 10.1093/
comnet/cnab014.
Hichem Sahbi. Learning Laplacians in Chebyshev Graph Convolutional Networks. In 2021 IEEE/CVF International Conference on Computer Vision Workshops (ICCVW), pp. 2064-2075, Montreal, BC, Canada, October 2021. IEEF. ISBN 978-1 978-1-66540-191-33
doi: 10. 109/CC/WWWW1

---

Published as a conference paper at ICLR 2023
Oleksandr Shehur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of Graph Neural Network Evaluation, June 2019.
Ulrike von Luxburg, Mikhail Belkin, and Olivier Bousquet. Consistency of spectral clustering. The Annals of Statistics, 36(2), April 2008. ISSN 0090-5364. doi: 10. 00.22440903360700000444
Pu Wang and Marta González. Understanding spatial connectivity individuals with non-uniform population density. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 367(1901):3321-333 August 2009. ISSN 1364-503X, 1471-2962. doi: 10. 1..1098//taa.200.00888
Yue Wang. Yongbin Sun, Ziwei Liu, Sanjay E. Sarma, Michael M. Bronstein, and Justin M. Solomon. Dynamic Graph CNN for Learning on Point Clouds. ACM Transactions on Graphics, 38(5):1-12, November 2019. ISSN 0730-0301, 1557-7368.
doi: 10.1 10.1345/332636..
Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In Proceedings of the 33rd International Conference on International Conference on Machine Learning- Volume 48, ICML' 16, pp. 40-48, 48, New York, NY, USA, 2016.
JMLR org.
12

---

Published as a conference paper at ICLR 2023
A
IMPLEMENTATION DETAILS
A.1 1 SYNTHETIC DATASET GENERATION
This section explains how to generate a synthetic dataset of geometric graphs with hubs. We first consider metric space, For our experiments, mainly focused on the unit-circle S and on the unit- disk D (see Appendix for more details). Each graph is generated as follows. First, non-uniform distribution is randomly generated. We considered angular non-uniformity described in Def. 6 where the number of oscillating terms, as well as the parameters c, n. μs, are chosen randomly. In the case of 2-dimensional spaces, the radial distribution is the one shown in Tab. 2| According each generated probability density function, N points {=: are drawn independently. Among them, m N are chosen randomly to be hubs, and any other node whose distance from a hub is less than some > 0 is also marked as a hub. We consider two parameters a, 3 > 0. The neighborhood radius about non-hub (respectively, hubs) nodes taken be (respectively a + 3). Any two points are then connected if
x is non-hub
my) S max(r(e;) r(o)
a + x hub
In practical terms, is computed such that the resulting graph is strongly connected, hence, it differs from graph to graph; /3 is set to be a and to be o
A.2 DENSITY ESTIMATION WITH SELF-SUPERVISIO
Density Estimation Network In our experiments, the inverse of the sampling density. 1/p, is learned by means of an EdgeConv neural network + (Wang et al. 2019), which is referred to as PNet in the following, where the message function is a multi-layer perceptron (MLP), and the aggregation function is max(-). followed by a abs(-) non-linearity. The number of hidden layers, hidden channels, and output channels is 3, 32, and 1, respectively. Since the degree is an approximation of the sampling density, as stated in Lemma
and since we are interested in computing its inverse to correct the GSO, the input of PNet is the inverse of the degree and the inverse of the mean degree of the one-hop neighborhood. Justified by the Monte-Carke approximation
= du(v)= = [ (lv) - R N Σ p(a.)) x2~ p N,
dv(y)=
the output of PNet is normalized by its mean.
Self-Supervision of PNet via Link Prediction on Synthetic Dataset train the PNet O for each graph G, use ( define GSO Lg Lg.e(g)- Then, define graph auto-encoder, where the encoder is implemented as a spectral graph convolution network with GSO Lg,e(g). The decoder is the usual inner- product decoder. The graph signal is slice of 20 random columns of the adjacency matrix. The number of hidden channels, hidden layers, and output channels is respectively 32, 2, and For each node j. the network outputs feature Og)); in R" Here, R" is seen the metric space underlying the NuG. In our experiments (Section 3.1) we choose n 2. Some results are shown in Fig.
Node Classification Let G be the real-world graph. In Section 3.2, considered G to be one of the graphs reported in Tab. I The task network Ve is a polynomial convolutional neural network implementing GSO Lg where θ is the PNet; the order of the polynomial spectral filters is 1, the number of hidden channels 32, and the number of hidden layers 2; the GSOs used are the ones in The optimizer ADAM (Kingma & Ba 2015) with learning rate 10-2 We split the nodes in training (85%), validation (5%). and test (10%) in a stratified fashion, and apply early stopping. The
Tab. 3
performances of the method are shown in Fig. 3
Graph Classification Let G be the real-worls graph. In Section 3.4 G is any compound in the AIDS dataset. The task network V is a polynomial convolutional neural network implementing a GSO Lg.e(g), where θ is the PNet; the order of the spectral polynomial filters is 1, the number of
13

---

Published as a conference paper at ICLR 2023
1.8
30-
1.4
2.0
1.5
3.4
Deginee
Deginee
Figure 6: Comparison between degree, density learnt to correct the GSO PL. and density learnt to perform weighted pooling PP, AIDS dataset.
hidden channels 128 and the number of hidden layers 2. The optimizer is ADAM with learning rate
10 20 We perform a stratified splitting of the graphs in training (85%), validation (5%), and test (10%), and applied early stopping. The chosen batch size is 64. The pooling layer is a global add layer.
In case of weighted pooling as in Section 3.3 the task network v implements GSO Lg while θ is used to output the weights of the pooling layer. The performance metrics of both approaches are shown in Fig.
A.3 GEOMETRIC GRAPHS WITH HUBS
Here, we validate that real-world graphs can be modeled approximately as geometric graphs with hubs, as claimed in (Section 3.1 We consider the datasets listed in Tab. 1 The auto-encoder defined as follows. Let G be the real-world graph with N nodes and F node features; let X E N X be the feature matrix. Let n the dimension of the metric space which nodes are embedded. Let V be a spectral graph convolutional network, referred to as encoder. Let v (XX); and (X(;,; IR" be the embedding of nodes and j respectively, decoder is a mapping Rn x I2 + [0, 1] that takes as input the embedding of two nodes i, and returns the probability that the edge (t. exists.
We use four types of decoders. (1) The inner product decoder from Kipf & Welling (2016) is defined (X)(),, L (X),)), where (-)) is the logistic sigmoid function. (2) The MLP decoder is defined (MLP([V (X),, Vrr (X)))))) where (X),, (X);] R denotes the concatenation of V (XX);; and (X()) j and MLP denotes multi-layer perceptron. (3) The distance decoder corresponds to geometric graphs. It defined as a(a ( (X): V (X) 5112), where a is the trainable neighborhood
radius. (4) The distance+ hubs decoder corresponds geometric graphs with hubs. It is defined trainable parameters that describe the radii of hubs and non-hubs. Y is amessage-passingg graph neural network (with the same architecture of PNet) that takes as input signal D computed from the node degrees (i.c., the inverse of the degree and the inverse of the mean degree of the one-hop neighborhood). and outputs the probability that each node is a hub. Y is learned end-to-end together with the rest of the auto-encoder. T()), I the network is followed by a min-max normalization.
a (a + max max(T(D)) (D); r(D),}3 [XX; Vr (X) ))ll))))) where o,
In order to guarantee that
The distance decoder is justified by the fact that the condition (X); v (X) l| S can be rewritten H(a || 1 (X), & (X), 1l2), where H(-) is the Heaviside function. The Heaviside function is relaxed to the logistic sigmoid for differentiability. Similar reasoning lies behind the formula of the distance+hubs decoder.
The encoder T is polynomial spectral graph convolutional neural network implementing GSO the symmetric normalized adjacency matrix; the order of the polynomial filters is 1, the number of hidden channels 32 and the number of hidden layers 2. In the case of inner-product, MLP and distance decoder, the loss the cross entropy of existing and non-existing edges. In the case of distance+hubs-decaae
also add ( //N to the loss, model we suppose the number of hubs is low. The optimizer is ADAM with learning rate 10-2 We split the edges in training (85%), validation (5%) and test (10%), and apply early stopping. The
regularization term, since in
14

---

Published as a conference paper at ICLR 2023
Table Real-world networks used for the link prediction task: graph statistics and number of param- eters of the auto-encoder for each of the three decoder types: inner product, distance, distance+hubs and MLP. Since the number of input channels of the MLP decoder depends on the latent dimension we report the number of parameter for n. 3.
Statistics
Decoder
Dataset
nodes
odges
features
classes
Inner product
Distance
Distance-Hobs
MLP
Yang al. 2016
Clieseer
9,104
237,154
237.155
239,750
2,708
10,556
1,433
91,874
91,875
94,409
94,470
Yang
Yang
Vubmed
19,717
88,648
500
3
32,162
32,163
34,697
34,758
AT102000 Com pit.er
Shichur 2019
13,752
491,722
767
10
49,250
49,251
51,785
51,846
Shchur et 2019
Amazon Mloto
7,650
238,162
745
8
47,842
47,843
30,377
50,438
RRozemberczki et
2021
22,470
342,004
128
4
8,354
8,155
10,889
10,950
Dacake Lneara -1
kca0
(a) Citeseer
(b) Cora
(c) Pubmed
1.01
2.90
675
639
Dormiio heer podaz
255
281
(9)
634
(d) AmazonComputers
(e) AmazonPhoto
(i) FacebookPagePage
Figure 7: Test AP for link prediction task as funetion of the dimension of the latent space. Performances averaged across 10 runs on each value of the latent dimension.
performances of both methods shown in Figs. 2 and while examples of embeddings and learned and B are shown in Fig.
The distance decoder has learnable parameter
than the inner-product decoder. Since PNet has fixed number of input channels, the distance+hubs decoder has 2, 535 learnable parameters more than the inner-product one. On the contrary, the mlp decoder has number of input channels that depends on the latent dimension; therefore, the number of hidden channels is chosen to guarantee that the number of learnable parameters of the mlp decoder approximately 2, 535.
B SYNTHETIC DATASETS A BLUEPRINT
In the following, we consider some simple latent metric spaces and construct methods for randomly generating non-uniform samples. For each space, structural properties of the corresponding NuG are studied, such as the expected degree of a node and the expected average degree, in case the radius fixed and the sampling is non-unin non-uniform. All proofs can be found in Appendix D if not otherwise stated.
Three natural metric measure spaces are the euclidean, spherical, and hyperbolic spaces. we restrict the attention to 2-dimensional spaces, a way to uniformly sample is summarized in Tab. In all three cases, the radial component arises naturally from the measure the space. A possible way to introduce con-uniformity is changing the angular distribution. In this way, preferential directions will be identified, leading to an anisotropic model.
15

---

Published as a conference paper at ICLR 2023
-15
-5.
-7.5
222
2.0
3002
122
1.3
12-
10
3002
3.
Decocer
Figure 8: (Top left) Embedding of Pubmed in 2 dimensions using distance+hubs decoder. The intensity of the color for each node i is proportional to the probability pt = Tg); of being hub. The three colours (red, green and blue) corresponds to the three different classes which node can belong, as reported in Tab. (Bottom left) Histogram of the probabilities hub divided per class. (Right) Learned values of the radius parameters a (top) and B3 (bottom) of the geometric graph with hubs auto-encoder on Pubmed, averaged across 10 runs for each value of the latent dimension. The average probability of being hub is 19.06%, and the number of nodes with probability of being hub greater than 0.99 is 10.10%.
YG)) of being
function of the latent dimension. Results
Table 2: Properties of euclidean, spherical and hyperbolic spaces of dimension 2. In the case of euclidean and hyperbolic spaces, the uniform distribution refers disk of radius R.
Property
Geometry
cuclidean
Measure of ball of radius
spherical
2 (1 - cos(())
hyperbolic
2 (cosh(a)) 1)
euclidean
(2m)-111 [-x,,)) (|-x,,,) (0)2R (0)2 2r 2r,
Uniform p.d.f.
spherical
(2 (an)-"1[xx.p (0)2-) (0_-sin(((p) (o.))))
hyperbolic
(2 (0T)-11[-x.)) [[x,,) (0)(cosh(()) ( (i.
euclidean
rt r 2r1r2 cos(O1 82)
Distance in polar coordinates
spherical
arccos (cos( (01) cos (62) + sin sin( cos(Az -22))
hyperbolic
arccosh(cosh((1) cosh(r22 sinh(r1) sinh((2)) cos(O) - 02))
16

---

Published as a conference paper at ICLR 2023
Definition 6. Given natural number C' N, and vectors R .nENGG 1 R
the function
cb(0,c,n,,p)
1 B
ca cos(n, (0 (p)+ + A
A Σ ccl. B 2
Ea
a continuous, 2x -rrppooo probability density function. It will be referred as spectrally bounded.
The cosine can be replaced by generic 2r-periodic function; the only change in the construction will the offset and the normalization constant.
Definition 7. Given natural number C' N, and the vectors RC, E No, the function
E 1A E R RC
mrM(O;,,n.
1
Σ
exp(Ks cos(n; (0 p4))
+
A
B
2T Io(rs)
B
i=1
where
exp(Ki)
exp(Re)
exp(xi)
A
2 (x:))
B
Σ mm:21
C
Σ
C
(o(ss))
Σ G
[o(
is continuous, -erppooo probability density function. It will be referred to multimodal von Mises.
Both densities introduced previously can be thought of as functions over the unit circle. Hence, the very first space to studied S = {x IR? |ل||| = 1} equipped with geodesic distance. As shown in the next proposition, the geodesic distance can be computed in a fairly easy way.
Proposition 2. Given two points x, y E S corresponding to the angles x, E [-T,, R), their geodesic distance is equal to
d(z. y) = π -
yl1
The next proposition computes the degree of node in non-uniform unit circle graph.
Proposition 3. Given a spectrally bounded probability density function as in Def. 6 the expected degree of a node in a unit circle geometric graph with neighborhood radius
deg(f)
2N
Σ
c cos(n, (0 14)) sin(n; +
Σ G + PX,=0
a
ns
im
and the expected average degree of the whole graph is
2 N
Σ
Σ Gej cos(n; (Mi H1)) (in(n
EG+a
Σ
)
+2
B
14
Co,, #0 jontE
km,=0
As direct consequence, in the limit of going to zero
Σ c 1 11)
lim a
[l)
1
Σ SED
c, cos(n; (0 p4))
lim a--tt
sin(m;aa) n. a
2a
B
=m;=0
sb(0; c, n,
thus, for sufficiently small the probability of ball centered is proportional to the density computed in Moreover, the emoor can be computed as
(0) 2a
sb(0:c, n.
Σ
2 C2
a²
which shows that the approximation worsens the more oscillatory terms there In the case of multimodal von Mises distribution, closed formula for the probability of balls does not exist. The following proposition introduces approximation based solely on cosine functions.
17

---

Published as a conference paper at ICLR 2023
Proposition 4. A multimodal Mises probability density function can be approximated by spectrally bounded one.
The previous result, combined with Prop. 3
gives a way approximate the expected degree of spatial networks sampled accordingly to multimodal von Mises angular distribution. However, the computation is straightforward when is the constant vector n 1, since the product of two von Mises pdf the kernel von Mises pdf
exp(X1 cos(n(0 (1))) exp(12 cos(n(8 - (2)))
2t (o(
2 lo (K52)
exp
V |5 + ni + 2n cos (os(n((11 122) cos (n(o sp)
n lo (K5) lo(k)))
where
Ki sin μ1) + K2 sin U2)
8 n arctan
cos(n (1) K2 cos(1) (22
The unit circle model is preparatory to the study of more complex spaces, for instance, the unit disk
= (x TR. ||x|| S }} equipped with geodesic distance, as Tab.
Proposition 5. Given spectrally bounded angular distribution as in Def. 6 the degree of node (r,0) 0) in a unit disk geometric graph with neighborhood radius
deg(r, 0) Rs 2T o² sb(0; n, p)
and the average degree of the whole network is
Σ A )
nx² a² N
(rdeg(r, 0)]
Σ Σ ces cos(n, (14 (s)) fo jom.mn
B
Cm,
Fig. 9a shows some examples of non-uniform sampling of the unit disk. The last example will be the hyperbolic disk with radius R >> 1, equipped with geodesic distance as in Tab. 2]
Proposition Given a spectrally bounded angular distribution as Def. the degree of node (r. 0) in a hyperbolic geometric graph with neighborhood radius is
deg(r, 0) 2 8 a-R--
sb(0; c, n. 1))
and the average degree of the whole network is O(N e "
The proof can be found in Appendix D The computed approximation is in line with the findings of Krioukov et (2010), where a closed formula for the uniform case is provided when a R. To the best of our knowledge, this is the first work that considers a + R. Examples of non-uniform sampling the hyperbolic disk are shown in Fig. 9h
C RETRIEVING AND BUILDING GSOS
In the current section, first show how to retrieve the usual definition of graph shift operators from Def. 4] and then how Def. 4 can be used to create novel GSOs. For simplicity, for both goals we suppose uniform sampling p can be rewritten
Lg,1 N diag (1) (N-1d) A diag m(()) (N-Id)
(3()) (N~ A diag ((()) (N-la)
N diag
diag
where A is the adjacency matrix and is the degree vector. Tab. 3 exhibit which choice of (m() 1 correspond to which graph Laplacian.
question that may arise is whether the innermost diag(-) in can factored out of the outermost one. As shown in the next proposition, it is not possible in general.
18

---

Published as a conference paper at ICLR 2023
8
(a) Non-uniform sampling of the euclidean disk.
(b) Non-uniform sampling of the hyperbolic disk.
Figure 9: Examples of non-uniform (a) euclidean and (b) hyperbolic sampling. The orange curve represents the angular probability density function, conveniently rescaled for visibility purposes.
Proposition 7. Let A NNNN A AT; let R and V diag(v), holds
diag [A1) V diag( A1) diag A1 V.
Moreover
diag AV1) diag VA1)
+ A.j = V.i.-- N ozj
Dj.
The proof of the statement can be found in Appendix the graph Laplacian
An important consequence of Prop. 7 is that
L AD diag D AD AD==1) D diag(d).
(8)
obtained with m (x) = - for every i E f1,..., 4], in general different from the symmetric normalized Laplacian, since
L= D -=D-AAD AD
diag AD +1) * AD D D'' diag (A1) L
In light of Prop. 7 the two Laplacians equivalent if every node is connected to nodes with the same degree, c.g., if the graph is k-regular.
The difference between the Laplacians can be better seen by studying their spectrum. The next proposition introduces an upper bound on the eigenvalues of the Laplacian in (8)
Proposition 8. Let G (V,E) E) be an undirected graph with adjacency matrix E NNN and degree matrix D diag(A1). Let À be an eigenvalue of the graph Laplacian
ADD diag ( (D-AAD-b1)
it holds |X| S 2
The proof of the proposition can be found in Appendix D It is well known that the spectral radius of the symmetric normalized Laplacian is less than equal to 2 (Chung 1997). with equality holding for bipartite graphs. However, this is not the case for the Laplacian in (8) as shown the next example.
19

---

Published as a conference paper at ICLR 2023
Table 3: Usual graph shift operators as metrrie-probabiiity Laplacians.
Graph Shift Operator
(x)
m
(x)
m (3) (x)
m (x))
Adjacency
1(x)
1(x)
((r)
((z)
Combinatorial Laplacian
1(x)
1(x)
1(x)
1(x)
Signless Laplacian
1(x)
1(x)
1(())
1(x)
Cvetkovic & Simic 2009)
Random walk Laplacian
x²
1(x)
1(x)
Right normalized Laplacian
1(x)
1(x)
Symmetric normalized adjacency
x-
((z)
((x)
(Kipf & Welling 2017)
Symmetric normalized Laplacian
x 3
x
x-1
1(x)
Equation (8)
x
x-
Example (Complete Bipartite Graph), Consider the complete bipartite graph with n nodes in the first part and m nodes in the second part. Its adjacency and degree matrix are
Opxn 1mx
1nxm
mmIxx
Ouxo
0mxm
D
0 0mxn
nImxm
simple computation leads
L= D AD diag (D AD-DAD ;1)
- m (nm)-
Ixx
(nm) 1xxm
1mxn
-n m
1 1mxm
It can be noted that L has null eigenvalue A1 corresponding to the constant eigenvector 1 1 (2,...,n)) } is eigenvector with eigenvalue
The vector v, -e e;, whose multiplicity is n 1. Analogously, v, = -e + e,+1, E {n + I,..., n2 + m - 1] is an eigenvector with eigenvalue A - /nn / m, whose multiplicity is m 1. Finally, the vector Vn+m [-m/n1 I is eigenvector with eigenvalues X x2 + Xg- Therefore, the spectral radius L is
-Vmmm n
m + n
A4
Vm
In the case of a balanced graph, implies that the spectral radius is 2. In the case of star graph, n = and [&al = O(ym) as m - oo; therefore, the asymptotic in Prop. is tight.
D PROOFS
Proof of Prop. Aand concentration of error. Let {x:) be i.i.d. random sample from p. Let K and m be the kernel and diagonal parts corresponding to the metric-probabilityy Laplacian Lvv Let L, be
Lij = N 2, -m(z))
= u(x;).
Note that the non non-uniform geometric GSO Lg based the graph G, which is randomly sampled from with neighborhood model M via the sample points x, is exactly equal to L. Conditioned on I; x, the expected value is
E (Lu), N Σ E p(z))
-((x)) m(z)u()) Cxu(x).
Since the random variables (x, 1 are i.i.d. to y, then also the random variables
((z,zz))(z,)) u(z;))
are i..dd, hence,
N Σ
var (Lu), = var N
K K(x, (=))((=))-'(((( -m(x) u(x)
==1
20

---

Published as a conference paper at ICLR 2023
NN. var (K(z,))p()) ()p(()))(11 -u(v))
S NN- E
[((x, (((x)))(()~ u(v))
N-1 / [K(z)))(()) uu() p(v) du(y)
$ N-1
((xx)))2( 11)(())
|| [
which proves (5)
Next, we prove the concentration of enror result. We know that there exist a, > O such that almost everywhere ((r,r,))(() (xx))))))x)-(((()) [a, bj. since K, 1/p and are essentially bounded. By Hoeffding's ss inequality, for / > 0,
2 (b - o)6
P (Lu), Lxu(x)) 2t s exp
Setting
2 t
exp
(b - a)
solving for f, we obtain that for every node there is an event with probability at least 1 - p/N such
that
(2 (Lu); Lxu(x)) < 2 (6 a)N Vlog22 p-1).
We then intersect all of these events to obtain an event of probability least p that satisfies 6
L
By hypothesis, there exist my, M, 0 such that m, S p(y) I M2 for all y E (xx). Therefore,
Proof of Lemma I
M=1 / du(y)= S f dp(y)= /
/
p(y)- s m
du(y),
((x)
N(x)) N(x)
(xx))
from which
SN du(y) JN du(y) S M
By the Intermediate Value Theorem, there exists co Nxx such that
p(cx)= = SN(N) dv(u)
SN(Ce) du(y)
from which the thesis follows.
Proof of Prop. Consider the map
: [- म, π) - St 0 + (cos(0), sin(
and the angles x, y, E [- π such that (p(x) x, (vy) y. it holds
d(z y) arccos x TTy) 4) arccos(cos(22 (z) cos(y) + sin(z)ssinn)))
arccos (cos(xr - y))
+ k
1-2 -m) T E [- 0) E [0, T)
V-
2 + y V, x E
[T, 2T)
21

---

Published as a conference paper at ICLR 2023
2
22
yl
x
y/
x
3/
x
yl
< π
vl1
Proof of Prop. 3 The expected degree of a node 8 is the probability of the ball centered at times the size N of the sample. The probability of ball can be computed by noting that
ta
2 2 (n, 144) sin(n; a)
n1 = 0
cos (n. (4)) d0
otherwise
74
Therefore, the average degree be computed
d = N / (0b::)))s((:
The inspection sb(0;e c, n, ps) and P[ shows that the only terms surviving integration are constant term and the product of cosines with the same frequency
cos (n, p4)) (0 -2)) do = π cos(ni(us - (i)), n. = n2
0,
# n2
from which the thesis follows.
Proof of Prop. Using Taylor expansion, it holds
exp(1; (0 14)))
cos(n: (0 11)))
m!
16 2m cos(n:(0 11,)))
22m)!
cos(n;(0 14)) 2m-1
(2m
1)!
m=1
first approximation be made noting that 20 cos(x)2 and cos(2))2m- as cos(1r) for all m 2 1, obtaining
exp(x; cos(n, - (.))) R= 1 (co)h((x)) - 1) cos(n, - ::))² sinh(K;) cos(n; -ms))
Such approximation deteriorates fast when K; increases. A more refined approximation is obtained considering the power of cosine with higher coefficient in the Taylor expansion. Using Stirling's approximation of factorial, it can be shown that
m
m!!
V2 mm
In order make the computation easier, suppose My is integer; When K2 + 1, it holds
1
K;
#1+1
c1tl
61+1
2 2T π (Rq + 1)
Ki
2 (r6s +
Kig
2 (Rc +1)
/2 Ka
where the first inequality is justified by the fact that (Ke/(K; + 1)) is increasing sequence that tends to 1/c. The previous formula shows that the coefficient with m = K; + 1 is always smaller than the coefficient with Kę- The same reasoning can be applied to all the coefficients with
22

---

Published as a conference paper at ICLR 2023
KG- Suppose now K2 3, if m S when m = Ki 1:
the previous reasoning holds. A peculiarity happens
K
84-1
ex
R4
2 nt (144 1)
Ki
2 Ki
Ki
π Kg
1//2 decreasing; therefore m = R; is the point of maximum, and m Ki is the second largest value. Therefore, the following approximation for exp(x; cos( [n,( (0 (s)))) holds:
because the sequence (Kt/ (K;
+ (cosh (N², 1) (ns(n, p4)))) + (inh(K)) (0 (1]1))]
K4 S 1 Ki Z 1, even
+ (cosh(x3 1) cos((n (0 pi)))) sinh((;)) cos(n; [z)))))==
(cosh (N²) - 1) (oos(n,( 14)))) sinh( cos(n, -44)))
K4 2 1, odd
The thesis follows from the equality
Ki
Ki
cos(n, - 14:))
cos( (2) - m.))
2
k
k=
Proof of Prop. The domain of integration can be parametrized as do((r, 0). (Fe. 0c)) S leading
x2+ -a²) a²
)
( , (2 + r -a² a² )
8
0g arccos
0 arccos
2rre
2r
Three cases must be discussed: (1)0 S - a S re + < (2) scenario (1), the ball B, (Te: 0c) is contained D. The probability of the ball can be computed as
< 0, (3) re + > 1. In
rota
P (a 6c)
sb(B:c,n. do dr
7e-a
0p-0p
222 + r2 a²
cos(n, (0.-Hi)
sin
arccos
dr
B 35
2r
re-a
roto
4
Σ
C A
arccos
2 + r2
a²
dr.
rr
k0,=0
(9)
where the last equality comes from Prop. 3 For simplicity, define
22 + + - a²
1.2 + r2 a
fn.-1(1) -r
1
Un.-1
2TTe
2r
y2 1+ a²) 2rr
g(r) arccos
where UR is the k-th Chebyshev polynomial of second kind. It is worthy to note that fn.-1(r+ta)
fn:-1(Te a) 0, fn,-1 -r)) and
a²
fn.-1(Fe) = =av1
a
Un-1 1
-mn-i(a)= = aa
Te Un.-1
Pe
2rc
2r
2a
2a
while g(r, + a) 0. g(r.
a) = 0. g(a
- rc)
(a -r)) and
a²
Te
g(r.) = To arecos
-
1 g(a)
arecos
2r
2a
23

---

Published as a conference paper at ICLR 2023
The integral in (9) can be approximated by the semi-area of ellipse having and fn.-1(re)
(respectively (Te))) as axes
tota
rota
Jn, fn.-i(r) fabm-((ro), / g(r) x 5
(10)
that can be seen modified version of Simpson's 's rule since the latter would lead to coefficient of 4/3 instead of π /2. comparison between the two methods is shown in Appendix the domain of integration contains the origin and the argument of arccos in inlpppedixx D coull be not
scenario (2)
well defined. The singularity can removed by decomposing the domain integration as union of disk of radius
Te around the origin and the remaining. Hence
0.+0,
P (Ba 0e) 22 /
{ a-r
sb(0;c, do dr +2
sb(0;c,n,,1) d0 dr
0--0,
atte
Bc+0,
(a - 22)2+ +2 2
sb(0;c,n..1) do dr.
Q-
0.-0.
The same reasoning as before leads to the approximations
a+ttc
a+te
fn. dr z π
2 Te fm-mm)aa))
g(r) = a 2 re)(a).
Q-Pc
a-re
In scenario (3) the domain of integration partially lies outside DD Hence
0.+0+
= f
P
sb(0;c,n,,)) d0 dr,
0.-0,
that can be approximated as
j fn)-1(r)dr dr Im-r(Te)
1-re rc Va² - (1 -11-re) rc)² arcsin
l-re
2
Te-a
g(r) dr g(re)
l- a a² - (1 11-90 r.)2 )2 + aresin
1-Te
2
The three scenarios can be summarized in one big formula. For simplicity, define the operator
I[f((r) aa + + minfa Te: re - at
a ( re + maxfa - Te. aa}
fn
2
2
max - a 10-1,10 1,0} fn. (rc)
1-
1 1- re Va² - (1- ro)2)
arccos
Te + +a--
a
a
that given function returns the ellipse approximation of the integral over balls, holds
P [Ba(re,
cos(n; (0. z4)) +
4
Σ c A I[al(re)
B
=m,
+ max (0, a- r
from which the thesis follows. To compute the average degree of spatial network from the unit disk, the quantity
d
2r
[r, cb
24

---

Published as a conference paper at ICLR 2023
Figure 10: Approximation of g(r) dr (top) and fr) dr (bottom) when a- Te and b a+T (left), re and b Te (center), and Te and (right) as function of ras
= 0.05.
must be computed. Using Prop. 3
the integral can be written in the form
Σ
C.
cos(mu (pr - ks)) / r rI(fmm-1((r) dr
B
n2g
in, #0 jamgang
2
16
Σ
G
A
B²
From U+(1) the following approximation can be derived
a²
I[Sn, -1)))
π n4
a²
2r
π
2
n1
a²
1
8
hence the integral boils down to
π I[f dr ~ nna2
4
The term
a + arccos (1_ a²
(r) dr
a
24
2
π a
log 2 V4-
- a²) - -log(a)
48
a
44 / -02)
Ta²
6
a=
π a
24
24
4
4
from which the thesis follows.
Proof of Prop. 6 parametrized as
Similarly to what has been done in Prop. 5
the domain of integration can be
(0. 0, 0 + 0,), 6, arccos (d+) d, cosh(r) cosh(r.) cosh(a)
sinh(ra) sinh(r)
In order to remove the singularity of the argument of arccos, the domain of integration can be decomposed as ball containing the origin and the remaining, leading to
2j
P... (re, 0.)l cR)
sinh(r) sb(0; c, dr
25

---

Published as a conference paper at ICLR 2023
0, () dr,
cosh(R))
ia 0.-8r
where 4 = 0, u1 max - To: 03.0),4. 12 = la - Tal and U2 = minfre + a, R...
cosh(u1) +
sinh(r) IP [Ba, (fc) dr
cosh(R) (R) -
cosh (R) -
l2
2
Σ ci +
u2
cosh(u1) -
:n,=0
+
sinh(r)0, dr
coshi(1)) (t) -
B (cosh( 1)
u2
2
C (0c 11:)
cosh( R
The approximations 0, & v2 d, and d, ~ 2 te ca- E a-rr-r as in Gugelmann al. 2012) be used analyze the behaviors of both integrals, For large R, it holds
sinh(r) 0, dr z
e- C d, dr
cosh([t) 1
b
2 2
R ea-se-r ae--re------------ c c 2r rr
02
2
2Rla no
V 1 2a a-- -e-aa-t dr
12
Rd 4e
where the last approximation is justified by vI+ + ((r) when |x| S 1. Noting that
-1 f dr < 1, one can get rid of the polynomial contribution
R R R 1 d2 dr
sinh(r) cosh(()) - VI Un, n,
R
R
dy v 1 d, dr
R
V2n m
28 a
1 + dr dr
R-R-ro
2 4 nzC
Therefore, the probability of balls is approximately
1)
Σ Ea+a {
8e
(r.. (.))
Σ
c; cos(nn (0c- (0c-4))) +
B
im
26

---

Published as a conference paper at ICLR 2023
and the expected average degree of the network is
R
sinh(r) d0 dr cosh( -
d = N
P| (r, sb) sb(0:c.n.
Eata))
16 π N
E ΣE E
city cos(n; (e: -1)) +2
A
B2
BRL jonmnn
:n;=0
Proof of Prop.
Equality (2) is trivial, since diagonal matrices commutes; equality (1) follows from
diag( (og((A1),3 (VA1);
Σ (A1), Σ
Vi
Ai,k (V diag A1 A1)) Σ Vr Vi, Σ
k=1
k=1
In order to prove (3), we note that can be decomposed as E U; (00000" Therefore
(diag diag( VA
diag Σ
n
2
Ae
e(0)
Ui
(e Σ
A
=
Σ
Ui
Ak.i - Uk
A
i=1
j=1
1=1
1=1
(o Au,s
1=1
must hold for all values of k. Consider the indices k1, ke...... k, corresponding the values Uk < Uk2 ... < Uk then
n
(Us Uk
Ak
20
then Ag. = O for each such that vn > Uk
Take the index kn and consider
U2
Uko
A
Uka
Absd + (Uk, Uk Aba.
20
The second addend because 1h can be either equal to oky which case the difference null, or Uka > Uk, in which case from the previous step Akak 0. Therefore Akz 0 for each i such that D4 > Uky. By finite induction, the thesis holds when A has null entries in position (i.j) whenever v # Vz.
Proof of Prop. The eigenvalues can be characterized via the Rayleigh quotient
u, diag (D-1 AD 21) - D AD u
(u, u.
Using Prop. and considering u D Y the previous formula can be rewritten
D Dåv. diag AD #1) D 0-12 A
vT diag DD'AD* $1) A
Ddv,Dtvv
TTDv
27

---

Published as a conference paper at ICLR 2023
Let d, Das the degree of the i-th node, using the symmetry of A, the numerator can be rewritten
as
d
Av.s
Σ
dj
1
di
Σ
2
Ar
+
Σ
Av. - E
2
dj
2 i.j
di
U v //))))
Σ
mAs
di Vdj
- 14
Ans -
2
i,j
1
Σ
4/ vd.
Avs
(vdivs- - vdjuz)
dj
Ar.
(Vdus-vagy
d:dj
1.j
From the last equality follows that the eigenvalues are all positive. From (a b)2 s 2(a² + + follows
Aij
(dre + +dzu))
v
d.dj
w
di 2
Aij
dj"
1.
$ 2 N
duy
2 N Dv
from which the thesis follows.
28


Reviews:
[{"review_id": "_fpkPFsKCr", "reviewer": "Reviewer_Gd1j", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper has considered non-uniformly sampled graphs from a metric-probability space and developed methods to estimate the unknown sampling density from those graphs. Also, the authors have experimentally tested the model and approach on synthetic and real-world graphs.", "summary_of_the_review": "See the above. ", "strength_and_weaknesses": "Strength: The topic seems quite interesting and is of high practical value. \n\nWeakness: the presentation of the paper overall is not good. There are lots of typos and grammar issues that prevent me from understanding the paper well. Authors are suggested to overhaul the whole organization of the paper as well.\n\n1) Subsection 1.1 on page 2, titled *Our Contributions* is poorly written. It actually states not *contributions* but more about *motivations*. Thus, I suggest integrating it into part of the introduction. \n\n2) Hard to appreciate the contributions in the paper. Suggestions: please state the primary approach to estimate the unknown sampling density, highlight the differences between the proposed method and existing ones, and identify challenges that arise from uniform sampling to non-uniform sampling. Especially please explain in detail the implications and significance of Proposition 1 on top of page 5 in the estimation of the sampling density. I was given the impression that the techniques presented in the paper are just simple generalizations of the existing ones (perhaps I am wrong). ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ZA2F405kHd", "reviewer": "Reviewer_swjz", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This work considers geometric graphs having both non-uniform sampling density, as well varying neighborhood radius. Under this model, a GSO can be though of as a discretization of the latent continuous Laplacian. In order for this GSO to approximate the continuous laplacian, the adjacency matrix needs to be normalized according to the sampling density. The non-uniform geometric graph model considered here seems a plausible model for real-world graphs. Of course, though, the sampling density is not known in practice. For this reason, it estimates the sampling density using a NN in a self-supervised manner. Experiments on synthetic datasets, where the ground truth sampling density is known, show that indeed this NN approach can well approximate the true underlying sampling density. Finally, it concludes with a set of experiments that seem to validate the hypotheses stated earlier in this work. More precisely, performance is improved in classification tasks, while learning density values can be used as a way to assign importance scores to nodes.", "summary_of_the_review": "I believe this work has some potential, though certain things need to be addressed. Mostly related to clarity, better motivating this work and focussing on the exact question/problem it tries to answer/solve. This will drive both the theoretical explanation and empirical evaluation in a more clear and concrete way.", "strength_and_weaknesses": "*  After the introduction of the non-uniform geometric graph model, the resulting GSO is properly derived with a bound on the convergence of it to the continuous laplacian.\n* There is an admirable effort to justify the reasoning behind using the proposed geometric model through experiments where the decoder is restricted to be a geometric graph with hubs and with experiments that try to demonstrate the applicability of this work in practical tasks.\n* However, as the work builds on the assumption of slowly changing density functions and piece-wise neighborhood radius, there should be a better discussion of it with other models, e.g. in statistical models there is a notion of popularity/expansiveness that differs for each node [1].\n* From a clarity perspective, this work is, in my opinion, weakly motivated. For example, the relevant section starts with a discussion on ways to compare graphs for similarity. It is not clear how this is connected with this work. Moreover, while GSO are central to this work, the definition on them is not repeated in order to start a discussion on how they are used and why this approach can be better than other approaches. In general, reading this work leaves you with a question-mark on what the main target of it is.\n* Moreover, in the experimental section regarding classification accuracy there is no comparison with works that learn a parameterized form of GSO (like the one of dasoulas et al. cited in this work). It is a question of whether we could have both pgso and this work combined.\n* Finally, for the learned $1/\\rho$, of the real-world networks, it would be interesting to see some plots and how they are different from let's say $1/\\sqrt{deg}$.\n\n\n[1] https://arxiv.org/pdf/0912.5410.pdf", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "NNBnhZYW-N", "reviewer": "Reviewer_4pay", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper introduces a framework allowing to correct the matrix representation (or graph shift operator) of a non-uniform geometric graph according to how this graph is sampled from the underlying metric space, namely, according to a sampling density and a neighborhood radius that is assumed to vary across the graph. Further, it proposes a self-supervised method to estimate the sampling density when the underlying metric space is unknown, and empirically demonstrates that using these corrected graph shift operators improves performance in a number of learning tasks.", "summary_of_the_review": "The problem addressed in the paper is important and the proposed solution is well-motivated. However, the paper fails to consider weighted graphs; does not rigorously compare the proposed graph model with other models for real-world graphs; and has unclear definitions and limited numerical experiments.", "strength_and_weaknesses": "Strengths:\n\n- The problem addressed in this paper is important: indeed, commonly used graph shift operators do not provide precise information about sampling, e.g., it is not clear whether a high-degree node in an *unweighted* graph has high degree because the area surrounding it is densely sampled, or because the sampling radius is large.\n- There is a strong motivation to \"correct\" the graph shift operator by encoding this sampling information: empirically, degree normalized graph shift operators tend to do better than their unnormalized counterparts, so normalizing by an even more accurate measure of sampling density should fare well.\n- The numerical results are convincing (though limited).\n\nWeaknesses:\n\n- It is not clear if this framework only applies to unweighted or to both unweighted and weighted graphs. This is an important distinction because while in unweighted graphs it is not possible to discern whether high-degree nodes stem from high sampling density or large neighborhood radius, in weighted graphs the sampling density is more related to the number of edges incident to each node, and the neighborhood radius to their edge weights. Related to this, the paper does not include any numerical results on weighted graphs. \n- The \"geometric graph with hubs\" model is not motivated by real-world networks, but instead, by the ability to decouple the contribution of the sampling density and the neighborhood radius. While the model works well empirically on the synthetic/citation networks considered in the experiments, there is no discussion on whether its assumptions, in particular the slowly varying density assumption, are realistic. For example, it would be important to understand whether canonical graph models typically used to model real-world graphs---such as small-world, preferential attachment, household, etc.---can be modeled as geometric graphs with hubs.\n- The numerical experiments are lacking: \n   - The link prediction experiments are arguably the most important experiments, as they demonstrate the validity of the model. However, they are only performed on synthetic graphs and on relatively simple (low rank) citation networks, which are embedded in $\\mathbb{R}^2$. It would be interesting to see link prediction experiments on more complex networks (perhaps the AIDS dataset?), and with larger embedding dimension.\n   - The assumption motivating the self-supervised learning approach---that the task depends mostly on the underlying continuous model---is not rigorously justified, and may be too strong, e.g., in heterophilous graphs. \n    - By definition, geometric graphs with hubs have more degrees of freedom than the correlation (inner product) and conventional geometric graphs with which they are compared in Fig. 2. If possible, the authors should include comparisons with other graph models with more degrees of freedom.\n- The presentation is lacking and certain concepts are not well-defined, see below.\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "9Jdv6XkePOa", "reviewer": "Reviewer_EP8m", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper is interested in the study of geometric graphs, i.e. graphs sampled from an underlying metric space, such that the neighbourhoods are determined by the graph distance. In particular, it focuses on the case where the sampling measure $\\nu$ differs from the intrisic measure $\\mu$ of the underlying space (i.e. the one used to compute the classical Laplacian).\n\nThe authors develop a general form for a neighbourhood function and a geometric Laplacian, which can be understood as a Laplacian whose kernel $K(x, \\cdot)$ is simply the indicator of a given ball around $x$. They also provide the corresponding definition for the discrete graph Laplacian, which depends on the sampling density $\\rho = d\\nu/d\\mu$.\n\nThe next step is thus to estimate $\\rho$; the authors introduce the concept of \"Geometric graph with Hubs\", which approximates real-worlds graphs decently well. In this model, $\\rho$ is approximately proportional to the graph degree, and hence $\\rho^{-1}$ can be learned by an equivariant neural network taking as input the node degrees.\n\nFinally, they provide several numerical experiments showing how the density estimation step improves the performance of classical graph convolutional networks. They compare the performance when the Laplacian is corrected with $\\rho$ and when it's not, as well as when the correction is only done in the last pooling layer.", "summary_of_the_review": "This is a good paper, that could use some more work to broaden its appeal to non-expert readers.", "strength_and_weaknesses": "The problem of non-uniform sampling for geometric graphs is quite natural: it's normal to expect that the sampling measure does not exactly match the density of the graph. The methods developed are sound, and seem to be vindicated by the experiments, although it is interesting that adding density estimation mainly reduces the variance and does not affect too much the average/best performance.\n\nOn the other hand, the paper is a bit too technical in several aspects, which might hinder its readability for people that are not at the exact field intersection.\n- on the theoretical side, it glosses quite quickly over definitions 3 and 4. In particular, the functions m^{(i)} are added without any explanation, except the one given in Appendix C; it might be more illuminating to move part of the appendix to the main text, so that readers used to classical graph theory can make the link between the usual Laplacians and the one in Equation 3. I also don't see the point of introducing the multiplication operator for Definition 3, as opposed to the more explicit forms used previously. It does make a nice parallelism between $\\mathcal M$ and the diagonal matrices of Definition 4, but if that is the goal it should be made more explicit.\n- the experiment section makes several references to the internals of laplacian-based networks, especially the pooling layers; it would be interesting to see how the density estimation exactly factors into that, even as an additional appendix.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster