Latent Graph Inference using Product Manifolds
Authors: Haitz Sáez de Ocáriz Borde
Anees Kazi
Federico Barbero
Pietro Lio
Venue: ICLR 2023 poster (2023)
Keywords: Latent Graph Inference
Product Manifolds
Graph Neural Networks

Abstract: Graph Neural Networks usually rely on the assumption that the graph topology is available to the network as well as optimal for the downstream task. Latent graph inference allows models to dynamically learn the intrinsic graph structure of problems where the connectivity patterns of data may not be directly accessible. In this work, we generalize the discrete Differentiable Graph Module (dDGM) for latent graph learning. The original dDGM architecture used the Euclidean plane to encode latent features based on which the latent graphs were generated. By incorporating Riemannian geometry into the model and generating more complex embedding spaces, we can improve the performance of the latent graph inference system. In particular, we propose a computationally tractable approach to produce product manifolds of constant curvature model spaces that can encode latent features of varying structure. The latent representations mapped onto the inferred product manifold are used to compute richer similarity measures that are leveraged by the latent graph learning model to obtain optimized latent graphs. Moreover, the curvature of the product manifold is learned during training alongside the rest of the network parameters and based on the downstream task, rather than it being a static embedding space. Our novel approach is tested on a wide range of datasets, and outperforms the original dDGM model.

Published as a conference paper at ICLR 2023
LATENT GRAPH INFERENCE USING PRODUCT MANIFOLDS
Haitz Sáez de Ocáriz Borde University of Oxford
Anees Kazi Harvard University
Federico Barbero University of Oxford
Pietro Liò University of Cambridge
ABSTRACT
Graph Neural Networks usually rely on the assumption that the graph topology is available to the network well as optimal for the downstream task. Latent graph inference allows models to dynamically learn the intrinsic graph structure of problems where the connectivity patterns of data may not be directly accessible. In this work, we generalize the discrete Differentiable Graph Module (dDGM) for latent graph learning. The original dDGM architecture used the Euclidean plane to encode latent features based on which the latent graphs were generated. By incorporating Riemannian geometry into the model and generating more complex embedding spaces, we can improve the performance of the latent graph inference system. In particular, we propose a computationally tractable approach to pro- duce product manifolds of constant curvature model spaces that can encode latent features of varying structure. The latent representations mapped onto the inferred product manifold are used to compute richer similarity measures that are leveraged by the latent graph learning model to obtain optimized latent graphs. Moreover, the eurvature of the product manifold is learned during training alongside the rest of the network parameters and based on the downstream task, rather than it being a static embedding space. Our novel approach is tested on a wide range of datasets, and outperforms the original dDGM model.
INTRODUCTION
Graph Neural Networks (GNNs) have achieved state-of-the performance in number of applica- tions, from travel-time prediction (Derrow- Pinion- et al. (2021)) to antibiotic discovery (Stokes et al.) (2200). ). They leverage the connectivity structure of graph data, which improves their performance in many applications as compared to traditional neural networks (Bronstein et al. (2017)) Most current GNN architectures assume that the topology of the graph is given and fixed during training. Hence, they update the input node features, and sometimes edge features, but preserve the input graph topology. A substantial amount of research has focused on improving diffusion using differ- ent types of GNN layers. However, discovering an optimal graph topology that can help diffusion has only recently gained attention (Topping et al. (202I): Cosmo al. (2020); Kazi et al. (2022)). )
In many real-worte applications, data can have some underlying but unknown graph structure, which we call latent graph. That is, we may only be able to access pointcloud of data. Nevertheless, this does not necessarily mean the data is not intrinsically related, and that its connectivity cannot be leveraged to make more accurate predictions. The vast majority of Geometric Deep Learning research so far has relied on human annotators simplistic pre-processing algorithms to generate the graph structure to be passed to GNNs. Furthermore, in practice, even in settings where the cor- rect graph is provided, it may often be suboptimal for the task at hand, and the GNN may benefit from rewiring (Topping et al. (202T). In this work, we drop the assumption that the graph adja- cency matrix is given and study how to learn the latent graph in fully-differentiabh manner, using

---

Published as a conference paper at ICLR 2023
product manifolds, alongside the GNN diffusion layers. More elaborately, we incorporate Rieman- nian geometry to the discrete Differentiable Graph Module (dDGM) proposed by Kazi et al. (2022). We show that it is possible and beneficial to encode latent features into more complex embedding spaces beyond the Euclidean plane used in the original work. In particular, we leverage the conve- nient mathematical properties of product manifolds to learn the curvature of the embedding space in a fully-differentiabl manner.
Contributions 1) We explain how to use model spaces of constant curvature for the embedding space. To do so, outline a principled procedure to map Euclidean GNN output features to constant curvature model space manifolds with non-zero curvature: we use the hypersphere for spherical space and the hyperboloid for hyperbolic space. We also outline how to calculate distances between points in these spaces, which are then used by the dDGM sparse graph generating procedure to infer the edges of the latent graph. Unlike the original dDGM model which explored using the Poincaré ball with fixed curvature for modeling hyperbolic space, in this work we use hyperboloids of arbitrary negative curvature. 2) We show how to construct more complex embedding spaces that can encode latent data of varying structure using product manifolds of model spaces. The curvature of each model space composing the product manifold is learned in dully-differenttable manner alongside the rest of the model parameters, and based on the downstream task performance. 3) We test our approach on 15 datasets which includes standard homophilic graph datasets, heterophilic graphs, large-scale graphs, molecular datasets, and datasets for other real-world applications such as brain imaging and acrospace engineering. 4) has been shown that traditional GNN models, such as Graph Convolutional Networks (GCNs) (Kipf & Welling (017)) and Graph Attention Networks (GATs) (Velikkovv et al. 20118) struggle to achieve good performance in heterophilic datasets (Zhu inductive bias by these models. Amongst other models, Sheaf Neural Networks (SNNs) (Hansen & Gebhart (2020); [Bodnar et al. (2022); Barbero al. 2022h ) have been proposed tackle this issue. We show that latent graph inference enables traditional GNN models to give good performance on heterophilic datasets without having to
et al. 2020), ) since in fact homophily is used
resort to sophisticated diffusion layers or model architectures such as SNNs. 5) To make this work accessible to the wider machine learning community, we have created new PyTorch Geometric
layer.
BACKGROUND
In this section we discuss relevant background for this work. We first provide a literature review regarding recent advances in latent graph inference using GNNs well as related work manifold learning and graph embedding. Next, we give an overview of the original Differentiable Graph Module (DGM) formulation, but recommend referring to Kazi et al. (2022) for further details.
2.1 RELATED WORK
Latent graph and topology inference is standing problem in Geometric Deep Learning. In contrast to algorithms that work on sets and that apply a shared pointwise function such as PointNet (Qi et al. (017)), in latent graph inference we want to learn to optimally share information between nodes in the pointcloud. Some contributions in the literature have focused on applying pre-processing steps to enhance diffusion based on an initial input graph (Topping al.) (202T): Gasteiger et al. 2019); Alon & Yahav/ (2021): Wu et al. (2019). Note, however, that this area of research focuses on improving an already existing graph which may be suboptimal for the downstream task. This paper is more directly related to work that addresses how to learn the graph topology dynamically, instead of assuming fixed graph at the start of training. When the underlying connectivity structure is unknown, architectures such as transformers /Vaswani et al.) (2017)) and attentional multi-agent predictive models (Hoshen (2017) 7)), simply assume the graph to be fully-connected, but this can become hard to scale to large graphs. Generating sparse graphs can result in more computationally tractable solutions (Fetaya et al. (2018) and avoid over-smoothing (Chen et al. (2000a)). For this a series of models have been proposed, starting from Dynamic Graph Convolutional Neural Networks (DGCNNs) (Wang et al. (2019). to other solutions that decouple graph inference and information diffusion, such the Differentiable Graph Modules (DGMs) in Cosmo al. (2020) and Kazi et al. (2022). Note that latent graph inference may also be referred to as graph structure learning in the literature. A survey of similar methods can be found in Zhu et al. (202)) and some additional
2

---

Published as a conference paper at ICLR 2023
classical methods include LDS-GNN (Franceschi et al. 2019), IDGL (Chen et al. 2020b), and Pro- GNN (Jin et al., 2020).
In this work, extend the dDGM module proposed by Kazi ct al. (2022) for learning latent graphs using product manifolds. Product spaces have primarily been studied in the manifold learning and graph embedding literature (Cayton (2005); Fefferman al. (003); Bengio al. (2012)). Recent work has started exploring encoding the geometry of data into rich ambient manifolds. In particular, hyperbolic geometry has proven successful in a number of tasks (Liu al. (2019), Chamberlain al. 2017);;Sale et al. (2018). Different manifold classes have been employed to enhance modeling flex- ibility, such as products of constant curvature spaces (Gu al. (2019)), matrix manifolds (Cruceru et al. (202I)), and heterogeneous manifolds (Di Giovanni et al. (2022). We will leverage these ideas and use product manifolds to generate the embedding space for constructing our latent graphs.
2.2
AN OVERVIEW OF THE DISCRETE DIFFERENTIABLE GRAPH MODULE
Kazi al. 2022
proposed a general technique for learning optimized latent graph, based on the output features of each layer, onto which to apply the downstream GNN diffusion layers. Here, we specifically focus on the dDGM module (not the cDGM), which is much more computationally effi- cient and recommended by the authors. The main idea is to use some measure of similarity between the latent node features to generate latent graphs which are optimal for each layer l. We can sum- marize the architecture as (1+1) = f (concat(X* (x(),, {)),
(1+1) p()) ((((((+))
( I (x(), A (1+ The node features in layer I, x are transformed into ( through a function feo. which has learnable parameters, and compared using a similarity measure (TT), which is parameterized by scalar learnable parameter T. On the other hand, Gø is a diffusion function which in practice corresponds to multiple GNN layers stacked together. Gø diffuses infor- mation based on the inferred latent graph connectivity structure summarized in A (1+1,, which is an unweighted sparse matrix. The dDGM module generates a sparse k-degree graph using the Gumbel Top-k trick (Kool et al. (2019)), stochastic relaxation of the kNN rule, to sample edges from the probability matrix P [X ()) (4), T), where each entry corresponds to
①1) Pij (0 exp(xe(
11 );T) exp((((((+)) (1+1) .2 (T))))))
The main similarity measure used in Kazi et al. (022) was to compute the distance based on the features of two nodes in the graph embedding space. They assumed that the latent features laid in an Euclidean plane of constant curvature Kg 0, so that Pij exp(-2d= (xx") f (x) )))
exp(-IDg(x) 11+1) _) ((+1))),, where dg denotes distance in Euclidean space. Then, based on (p. (lgg() ( log( (q)),, where R. is uniform i..d in the interval [o, 1], we can
sample the edges g()) (X) ( k) ((i,j..) (i, f122...., (i, f..).. i 1, ..., N). where k the number of sampled connections using the Gumbel Top-k trick. This sampling approach fol-
lows the categorical distribution
E.pry ay and ((x(); (0) T. k) is represented by the unweighted
adjacency matrix A (9) (()), A,)). Note that including noise in the edge sampling approach will result the generation of some random edges in the latent graphs which be understood as a form of regularization. In this work, we generalize Equation D to measure similarities based on distances but dropping the assumption used in Kazi et al. (2022) which they limit themselves to fixed-curee exee-ccrratture spaces, specifically to Eucliden space where Kg = O. We will use product mani- folds of model spaces of constant curvature to improve the similarity measure o and construct better latent graphs.
3 METHOD: PRODUCT MANIFOLDS FOR LATENT GRAPH INFERENCE
In this section, we first introduce model spaces, which are a special type of Riemannian manifolds, and explain how to map Euclidean GNN output features to model spaces with non-zero curvature. In case the reader is unfamiliar with the topic, additional details regarding Riemannian manifolds can be found in Appendix [ Then, we mathematically define product manifolds and how to calculate distances between points in the manifold. Next, introduce scaling metrics which help learn
3

---

Published as a conference paper at ICLR 2023
the curvature of each model space composing the product manifold. A discussion on product mani- fold curvature learning can be found in Appendix [ The intuition behind the method is that we can consider the embedding space represented by the product manifold as combination of more simple spaces (model spaces of constant curvature), and compute distances between the latent representa- tions mapped onto the product manifold by considering distances in each model space individually and later aggregating them in a principled manner. This allows to generate diverse embedding spaces which at the same time are computationally tractable.
3.1 CONSTANT CURVATURE MODEL SPACES
Curvature is effectively a measure of geodesic dispersion. When there no curvature geodesies stay parallel, with negative curvature they diverge, and with positive curvature they converge. Euclidean space, E = Rd is a flat space with curvature Kg = O. Note that here we use dg to denote dimensionality. On the other hand, hyperbolic and spherical space, have negative and positive cur- vature, respectively. We define hyperboloids as Hide {xp Rda+1, (xp: xp)c 1/Ka], where
KH 0 and <c is the Lorentz inner product (x, y) -11V1 + 2yj2 dd Tyyy, Vx,y E IRd++1, and hyperspheres S {xp E IRd++1, (xp: Xp/2 1/Kg), where Ks > 0 and <::)2 is the de
standard Euclidean inner product (x = _i=1 وززز Vx,y E Rd++1 Table provides a sum- mary of relevant operators Euclidean, hyperbolic, and spherical spaces with arbitrary curvatures. The closed forms for the distances between points in hyperbolic and spherical space use the arccosh and the arccos, their domains are {I E IR x 2 1} and {I E I -1 & x < 1}, respectively. We apply clipping to avoid giving inputs close the domain limits and prevent from instabilities during training.
Table 1: Relevant operators (exponential maps and distances between two points) in Euclidean, hyperbolic, and spherical spaces with arbitrary constant curvatures.
Space Model
carpa, (x)
xx,,)
E, Euelidean
Xp
X
H1, hyperholoid
eoch (y [x],)x, sinh (v * x
arcensh (Kg(x.))2)
8, hypersphere
cos [x) sin (v (RÍl
(K))x.y>))
The latent output features produced by the neural network layers are in Euclidean space and must be mapped to the relevant model spaces before applying the distance metrics. We use the ap- propriate exponential map (refer Table T. To map Euclidean data to the hyperboloid. we use !f the hyperboloid north pole, that is, the origin 0K= := (--Kg" 0, O..., 0) = (=
0) as refer-
ence point to perform tangent space operations. Using the trick described in Chami et al. 2019 I if is Fuclidean feature space at Knn Therefore, we can obtain the mapped features x = expa (concat(O, x)) via x okg
consider concat(0, x) to be point in the manifold tangent
zt
Vー cosh (V-KEl [x]] sinh KV-KKllsa --1 --Kn||
Similarly for the hypersphere using as
reference point k := ( VKg 0, ...,
...,..)) 0), (v/s cos (v (vKs xx]), sin (v (Kgl/ia (vKg[|xl) )
3.2 PRODUCT MANIFOLDS
i-1 M where K, and d, are the curvature and dimensionality of the manifold Ma respectively. We write points Xp P using K.
We define a product manifold as the Cartesian product x up
their coordinates X, = concat Xxp Xp Xp
(1) (2)
(nT)
(i) Ma k Also, the metric of the product Xp
manifold decomposes into the sum of the constituent metrics gp- >m> Ii, hence, gp) is also
a Riemannian manifold if ( ..),, Vi are all Riemannian manifolds in the first place. Note that the signature of the product space, that is, its parametrization, has several degrees of freedom: the number of components used, as well as the type of model spaces, their dimensionality. and curvature.
Note that in this paper they define curvature differently.
4

---

Published as a conference paper at ICLR 2023
If restrict P to be composed of the Euclidean plane Kgg
hyperboloids H
and hyperspheres
of constant curvature, we can write an arbitrary product manifold of model spaces as
P
Eds Kis
X
K
x
K
=
X
X Hl
X
X
SK
(2)
where KE 0, KJ O, and K > 0. The rightmost part of Equation 2 is included simplify the notation. P would have a total of + Yhg ni component spaces, and total dimension dg + En - = de As shown in Gallier & Quaintance (2020). in the case of a product manifold as defined in Equation 2 the geodesics, exponential, and logarithmic maps on P are the concatenation of the corresponding notions of the individual model spaces.
3.3 DISTANCES AND SCALING METRICS FOR PRODUCT MANIFOLDS
To compute distances between points in the product manifold we add up the square dis- tances for the coordinates in each of the individual manifolds dp (Xp1: : Xpn)² Dg
Xpi (1)
x 2
+
Σ Dm, x (1++)) ((+))) E Ds, (x([ (x(1+m++)) " x((++=+*)) where the overline denotes
that the adequate exponential map to project Euclidean feature entries to the relevant model space has been applied before computing the distance. In practice, this would be equivalent to mapping the feature outputs to the product manifold and operating on P directly. As suggested in Tabaghi jet al.) (2021), instead of directly updating the curvature the hyperboloid and hypersphere model spaces used to construct the product manifold, we can set K 1, Vj. and K 1, Vk, and use scaled distance metric instead. To do so, we introduce learnable coefficients aj and a
(p(x dg (1) (1)
E (ofDa, (x(1 x(1+))
E
(aEDa, (x ((llmm4))) xa ( (3)
which is equivalent to learning the curvature of the non-Fuclidean model spaces, but com- putationally more tractable and efficient (for further details how this coefficients are updated refer to Appendix (.2).. This newly defined distance metric can then ap- plied to calculate the probability of there existing edge connecting latent features
Pi (Q())
exp -Top
(x 1,,,),
Hence, (x(() (0,,kkkpp) =
{(i, (k.),, (i.jk.), .... (i.j..) : I,..,, N). As discussed in Kazi et al. (2022) the logarithms of the edge probabilities are used update the dDGM. This is done by incorporating an additional term to the network loss function which will be dependent on
log @1) (e))) = -TOp 1 (x (xx)) = -DDp (x(1) (()
(xpt pp xp
(4)
where the additional graph loss is given by Lei. MN" (o 0i) Di= E
logp:)
(1)
and 5 (y, 9.)
ac; is reward function based the expected accuracy of the model. The loss function to update the dDGM model, LGL. identical to the original loss proposed by Kazi [
ee al. (2022), for brief review may refer to Appendix [ Note that after passing the input
(1) x; through the dDGM parameterized function / the output f (x(" ()) = x
(4) ((+1) = xp: has
dimension dz + y 2j-1dj
dif + yan o and must be subdivided into + ne + nig subarrays for each of the component spaces. Each subarray must be appropriately mapped to its model space. Hence,
(!)) the overline in fe (xx") in Equation 4 Finally, Figure summarizes the method described in this section. Note that X, in Figure [ would correspond to the concatenation of the origins of each model space composing the product manifold.
5

---

Published as a conference paper at ICLR 2023
GMt Ddg
Figure I: Diagram depicting mapping procedure from GNN Euclidean output to latent manifold P. The appropriate exponential map used map the points from the tangent plane to the manifold. We construct the latent graph based on the distances on the learned manifold.
EXPERIMENTS AND RESULTS
The main objective the experimental validation is to show that latent graph inference can benefit from using products of models spaces. To do so, compare the performance of the dDGM module when using single model spaces against Cartesian products of model spaces. The model spaces are denoted Euclidean (dDGM-F/dDGM*... which is equivalent to the original architecture used by Kazi et af. (2022)). hyperbolic (dDGM-H/DDMM*..
and spherical space (dDGGM-S/DDGM* S). The asterisk sign in the model name denotes that the dDGM module is tasked with generating the latent graph without having access to the original adjacency matrix. dDGM models take as input (0) and A 10), whereas dDGM" models only have access to ( To refer to product mani- folds, simply append all the model spaces that compose the manifold the name of the module, namely, the dDGM-SS module embedding space is torus. In practice, we will use the same di- mensionality but different curvature for each of the Cartesian components of the product manifolds. Lastly, if GNN model uses the dDGM module, we name the diffusion layers and the latent graph inference module after. For example, GCN-dDGM-E refers to a GCN that instead of using the original dataset graph for diffusion, incorporates latent graph inference to the network and uses the Euclidean plane as embedding space.
Note that we only use single latent graph inference module per neural network, that is, networks diffuse information based on only one latent graph. This in line with previous work (Kazi et al. 22022). Additionally, in Appendix I. we investigate the effect of leveraging multiple latent graphs in the same network and conclude that in general it is better to use a single latent graph due to com- putational efficiency and diminishing returns. The study regarding computational efficiency can be found in Appendix C.3 In particular, we compare the runtime speedup obtained using symbolic ma- trices compared to standard dense PyTorrch matrices. We observe that more product manifolds and dDGM modules are included, the runtime speedup obtained using symbolic matrices becomes increasingly large. Moreover, without using symbolic matrices standard GPUs (we NVIDIA P100 and Tesla T4) run out of memory for datasets with O(10*) nodes such as PubMed, Physics, and CS. Hence, we recommend using symbolic matrices help with scalability. Model architecture descriptions for all experiments can be found in Appendix G
4.1 HOMOPHILIC AND HETEROPHILIIC BENCHMARK GRAPH DATASETS
We first focus on standard graph datasets widely discussed in the Geometric Deep Learning literature such as Cora, CiteSeer YYagg al. (016);; Lu & Getoor (2003 [en al. (2008). PubMed, Physies and CS (Shchur et al. (2018). which have high homophily levels ranging between 0.74 and 0.93. We also present the results for several heterophilic datasets, which have homophily levels between 0. and 0.23. In particular, we work with Texas, Wisconsin, Squirrel, and Chameleon (Rozemberczki et al. 2021). Results of particular interest for these datasets are recorded in Table 2 (benchmark models such LDS-GNN (Franceschi et al. 2019). IDGL, IDGL-ANCH (Chen et al. 2020b), Pro-GNN, Pro-GNN-fs (Jin et al. 2020), and GaN-Jaccard (Wu et al.) 2019) are also included).
Additional experiments are available in Appendix R.2 and E.4 in which we perform an in depth

---

Published as a conference paper at ICLR 2023
exploration of different hyperparameters, compare dDGMs and dDGM"s s for all datasets, and try many product manifold combinations. Referring back to 2 we can see that product manifolds consistently outperform latent graph inference systems which only leverage single model space for
modeling the embedding space. Also note, that unlike in the work by Kazi et al. (2022), we do find single hyperbolic model spaces to often outperform inference systems that use the Euclidean plane
as embbeding space. This shows that indeed mapping the Euclidean output features of the GNN layers hyperbolic space using the exponential map before computing distances is of paramount importance (Kazi et al. (2022 ignored the exponential maps required to map features to the Poincaré ball).
Table 2: Results for heterophilic and homophilic datasets combining GCN diffusion layers with the latent graph inference system. We display results using model spaces as well as product manifolds to construct the latent graphs. The First, Second and Third best models for each dataset are high- lighted in each table. & denotes the number of connections per node when implementing the Gumbel Top-k sampling algorithm. Additional values are tested in Appendix E.2 Note that the models which use the Euclidean plane (former dDGM) as embedding space, denoted with an E in the table, are equivalent to those presented in Kazi et al. (2022).
HE RETEROPHILC DALASETS
BUNKIPILL JC DAEAARESS
Tinoe
Wisceads
Churelles
Cara
Chiller
Pubhied
Plynic
CS
Honaekaly leve
0L11
0.21
0.21
Honagdaly len
0.51
0.14
(1.03
0:50
Tharaes
1,700
1.700
3,584
1/433
7,345
400
4415
6L915
190,475
9.275
4,506
247.62
11.554
Claric
Aereny Degre
5.25
1.21
Awary Deyre
54
14:18
Frense dMMM
Asazay
in
12:001s22
dUGM with Hkrazendas Gearatry and Stugle Madd Spaces (teen)
Made
Acorrdy [K) Standert Desurve
Model
Acceny (55) Stadlaed Divindoo
GCN -DCMP-
79 444aa ae
50 B
GEN-Dxaas
at Taus
(iii to
4BGM with Rinnetreee Geunetry and Product Morelall (Dan))
Modd
Accuncy [5]
Stadkr Devaiie
Modd
Acaryy (5) Staviad Deviades
GEN DEN-aDCNN-BR 4H
54.35110n
69 M0
GEN- sH
112raasa
52 20:00
uncart an
A1.07:785
65 575
363755
47.58:34
GEN 4D02511
67.41pa00
06.02:9.7
GEN CXX--DCC---
GEN (EN-40031s5
SL.
11806333
22 20300oss
16. k..4
GEN 4DCam 6u0
#1. 13:
77 6:
33 18
GEN 4bra-imt
42
75-422524
03
GCN-4DCN" -eH5
44
2
GCN-1DGN-ER
63.5
(806-217
30:90-109
Vaalia Antlisctum
Made GEN
Stanted Desurve
Modd
Accesay Suadaad Devirtos
58
41.6ano
24
GEN
58.001111
96
We have shown that the latent graph inference system enables GCN diffusion layers to achieve good performance for heterophilic datasets. We hypothesize that for this to be possible, it should be able to generate homophilic latent graphs, on which GCNs can easily diffuse. In Table 3 we display the homophily levels of the learned latent graphs, which corroborates our intuition. As we can see from the results all models are able to generate latent graphs with higher homophily than those of the original dataset graphs. The latent graph inference system seems to find it easier to increase the homophily levels of smaller datasets, which is reasonable since there is less information to reorganize. There is clear correlation between model performance in terms of accuracy (Table and the homophily level that the dDGM modules are able to achieve for the latent graphs (Table
Table 3: Homophily level of the learned latent graphs. Latent graph inference modules which use different manifolds to generate their respective latent graphs achieve different homophily levels. Also, depending on weight initialization, the inference system can converge to slightly different latent graphs.
Teme
Septrrl
Chamdion
Dituaall Eemopayy
Melil
Lautr Gropk Hemughtr
Stmarr
063 Jipue R
(E% wogurruuea
7

---

Published as a conference paper at ICLR 2023
For example, in the case of Texas achieve the highest homophily levels for the latent graphs of between 0.85 = 0.02 and 0.91 I 0.03, and also some the highest accuracies ranging from 73.88 + 9.95% to 81.67 I 7.05% For Wisconsin the homophily level is lower than that for Texas, but this can be attributed to the fact that = 10, inevitably creating more connections with nodes from other classes. Also, in Wisconsin there rest, meaning that a high accuracy can be achieved even if those are misclassified. On the other hand, for Squirrel, although the latent graph inference system still manages to increase homophily from 0.22 in the original graph to between 0.27 + 0.00 and 0.43 I 0.03 in the latent graph. the increase is not big as compared to the other datasets and we can see how this also has an effect on performance. In Table 2 the maximum accuracy for Squirrel is of 35.00 + 2.35%. Note that this still substantially better than using MLPP standard GCN, which obtain accuracies of 30.44+22.55 and 24.19 19-19-+2 2.56%, respectively. The same discussion applies to Chameleon. Figure displays how the graph connectivity is modified during the training process. This shows that the inference system is able to dynamically learn optimal connectivity structure for the latent graph based on the downstream task, and modify accordingly during training. Additional latent graph plots for the different datasets can be found in Appendix
classes with substantially less nodes than the
(a) Epoch 1, h 0.39.
(b) Epoch 5, h = 0.46.
(c) Epoch 10, h = 0.50.
(d) Epoch 100, / = 0.74.
(e) Epoch 500, / = 0.81.
(1) Epoch 1000, /: = 0.93.
Latent graph homophily level, h. evolution as a function of training epochs for Texas. The latent graphs are produced during the training process for the GCN-dDGM**ED model with k = 2.
Figure 2:
4.2 REAL-WORLD APPLICATIONS
Next, we test the latent graph inference system on real-world applications: on the TadPole dataset (Marinescu et al. (2020), which was also discussed by Kazi al. (2022), and the Aerothe- modynamics dataset, which we have created for this work. The TadPole dataset contains infor- mation about brain images for different patients and the task to classify each patient into three classes: Normal Control, Alzheimer's Disease and Mild Cognitive Impairment. On the other hand, the Acrothermodynamics dataset was inspired by recent research discussing potential applications of machine learning to aerospace engineering (Maheshwari et al. (0018) SSez de Ocáriz Borde et al. (20T)): de Ocáriz Borde et al. 2021)), and challenges networks to classify different regions a shock wave around a rocket (refer to Appendix D for more information on the dataset). Note that since neither of these datasets have a graph structure (they are pointclouds), only the dDGM can be utilized in this case. Results are given in Table 4 We use GAT diffusion layers and compare the performance using single model spaces and product manifolds. Almost all models using the latent graph inference system outperform the performance of the MLP. It is important to note that since the datasets do not provide an input graph it would not be possible to use GAT models without using dDGM modules. Again, we find that using product manifolds to model the latent space of potentially complex real-world datasets proves beneficial and boosts model accuracy.
In principle, the Aerothermodynamics datasets classifies shock regions based on the flow absolute velocity into 4 regions recorded in Table However, we tested increasing the number of classes by further subdividing the flow into a total of 7 regions, as shown in Figure 3 We found that interestingly, the latent graph inferred by the model does not only cluster nodes with similar labels together, but it actually organizes the latent graph in order based on the absolute velocities (which not explicitly given to the model: the velocities are used create the labels but values
8

---

Published as a conference paper at ICLR 2023
not provided to the model as input). This suggests that the graph generation system is organizing the latent graph based on some inferred high level understanding the physics of the problem. Additional latent graphs for these datasets are provided in Appendix
Nakes
Makii
Ascama
Devatiee
GAT 4DGE---
90. 31
20:30:1-4
GAR-IDO80--
09.50-0300
41
20.21
(AT 4nr20m--111
0AF-4EU00--23
99.35 00:36-214
50 00
CAR-DDG307-25
27 1888.. 9
GAT /DO.Y
47.50a330
Table 4: Results for the TadPole and the Aerothermodynamies datasets using GAT diffusion layers and different latent graph inference modules.
Figure 3: Latent graph obtained by the GAT- IDGM*-EHH model with k = 7 including more subclasses for different absolute velocity simulation regions for the Aerothermodynamics dataset.
4.3 SCALING TO LARGE GRAPHS
All datasets considered so far are relatively small. In this section we work with datasets from the Open Graph Benchmark (OGB) which contain large-scale graphs and require models to perform realistic out-of-distribution generalization. In particular,
use the OGB-Arxiv and the OGB- Products datasets. As discussed in Appendix [C..3] for training on these datasets we use graph subsampling techniques, and Graph Attention Network version 2 (GATv2) diffusion layers (Brody et al. (202T); since we do not expect overfitting we can use more expressive layers. OGB-Arxiv and OGB-Products have a total of 40 and 47 classes, respectively. Previous datasets only considered multi-class classification for between 3 to 15 classes. This, added to the fact that the datasets have orders of magnitude more nodes and edges, makes the problems in this section considerably more challenging. For OGB-Arxiv using MLP and GATv2 model without leveraging latent graph inference we obtain accuracies of 63.49 I 0.15% and 61.93 1.62%, respectively. The best model with latent graph inference, GATv2-dDGM" -EHSSS achieves an accurary of 65.06 + 0.09%. For OGB--roducts, the MLP and a GATv2 results are 66.05 + 0.20% and 62.02 + 2.60%, and for the best model, GATV2-dDGM-E, we record an accuracy of 66.59 + 0.30%. From the results (more in Appendix E.5). we conclude that latent graph inference is still beneficial for this larger datasets but there is substantial room for improvement. Graph subsampling interferes with embedding space learning.
5 DISCUSSION AND CONCLUSION
In this work we have incorporated Riemannian geometry to the dDGM latent graph inference mod- ule by Kazi et al. (2022). First, we have shown how to work with manifolds of constant arbitrary curvature, both positive and negative. Next, we have leveraged product manifolds of model spaces and their convenient mathematical properties to enable the dDGM module to generate a more com- plex homogeneous manifold with varying curvature which can better encode the latent data, while learning the curvature of each model space composing the product manifold during training.
We have evaluated our method on many and diverse datasets, and we have shown that using product manifolds to model the embedding space for the latent graph gives enhanced downstream perfor- mance as compared to using single model spaces of constant curvature. The inference system has been tested on both homophilic and heterophilic benchmarks. In particular, we have found that us- ing optimized latent graphs, diffusion layers like GCNs are able to successfully operate on datasets with low homophily levels. Additionally, we have tested and proven the applicability of our method to large-scale graphs. Lastly, we have shown the benefits of applying this procedure in real-world problems such brain imaging based data and aerospace engineering problems. All experiments

---

Published as a conference paper at ICLR 2023
discussed in the main text are concerned with transductive learning; however, the method is also applicable to inductive learning, see Appendix E.6
The product manifold embedding space approach has provided a computationally tractable way of generating more complex homogenous manifolds for the latent features' embedding space. Further- more, the curvature of the product components is learned rather than it being a fixed hyperparameter, which allows for greater flexibility. However, the number of model spaces to generate the product manifold must be specified before training. It would be interesting to devise an approach for the network to independently add more model spaces to the product manifold when needed. Also, we are restricting our approach to product manifolds based on model spaces of constant curvature due to their suitable mathematical properties. Such product manifolds do not cover all possible arbitrary manifolds in which the latent data could be encoded and hence, there could still be, mathematically speaking, more optimal manifolds to represent the data. It is worth exploring whether approaches to generate even more diverse and computationally tractable manifolds would be possible.
Future Work Lastly, there are a few limitations intrinsic to the dDGM module, irrespective of the product manifold embedding approach introduced in this work. Firstly, although utilizing symbolic matrices can help computational efficiency (Appendix C.3). the method still has quadratic complex- ity. Kazi et al. (2022) proposed computing probabilities in neighborhood of the node and using tree-based algorithms to reduce it to On n).. Moreover, the Gumbel Top-k sampling approach restricts the average node degree of the latent graph and requires manually adjusting the & value through testing. A possible solution could be to use a distance based sparse threshold approach in which unweighted edge is created between two nodes if they are within threshold distance of each other in latent space. This is similar to the Gumbel Top-k trick, but instead of choosing fixed connect all nodes within a distance. This could help better capture
number of closest neighbors, the heterogencity of the graph. However, we actually tested this approach and found it quite unsta- ble. Note that although we do have the & parameter anymore, we must still choose a threshold distance. Another avenue to help with scalability, improve computational complexity, and facili- tate working with large-scale graphs would be to use hierarchical perspective. Inspired by brain interneurons (Freund & Buzsáki (1996)), we could introduce fictitious connector inducing nodes in different regions of the graph, use those nodes to summarize different regions of large graphs, and apply the kNN algorithm or the Gumbel Top-k trick to the fictitious connector inducing nodes. This way the computational complexity would still be quadratic, but proportional to the number of interconnectors. Similar techniques have been applied to Gaussian Processes (Galy-Fajou & Opper 2021 : Wu et al. (202T) and Set Transformers (Lee et al. (2019).
REFERENCES
Uri Alon and Eran Yahav, On the bottleneck of graph neural networks and its practical implications. ArXiv, 2021.
Federico Barbero, Cristian Bodnar, Haitz Sáez de Ocáriz Borde, and Pietro Liò. Sheaf attention networks. In NeurlPS 2022 Workshop on Symmetry and Geometry in Neural Representations, 2022a. httttpp://ppenreeeeee.eeee//eeee
Federico Barbero, Cristian Bodnar, Haitz Sáez de Ocáriz Borde, Michael Bronstein, Petar Veličković, and Pietro Liò. Sheaf neural networks with connection laplacians. In Topological, Algebraic and Geometric Learning Workshops 2022, 2022b.
Gabriele Beltramo, Rayna Andreeva, Ylenia Giarratano, Miguel O. Bernabeu, Rik Sarkar, and Pri- moz Skraba. Fuler characteristic surfaces. ArXiv, 2021.
Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives, 2012.
Cristian Bodnar, Francesco Di Giovanni, Benjamin P. Chamberlain, Pietro Liò, and Michael M. Bronstein. Neural sheaf diffusion: A topological perspective heterophily and oversmoothing in GNNs, 2022.
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks?, 2021.
10

---

Heterogeneous manifolds for Published as a conference paper at ICLR 2023
Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur D. Szlam, and Pierre Vandergheynst. Ge- ometric deep learning: Going beyond euclidean data. IEEE Signal Processing Magazine, 34: 18-42, 2017.
Lawrence Cayton. Algorithms for manifold learning. 2005.
Benjamin P. Chamberlain, James Clough, and Mare Peter Deisenroth. Neural embeddings of graphs in hyperbolic space. ArXiv, 2017.
Ines Chami, Rex Ying, Christopher Ré, and Jure Leskovec. Hyperbolic graph convolutional neural networks, 2019.
Benjamin Charlier, Jean Feydy, Joan Alexis Glaunès, François- -avid Collin, and Ghislain Durif. Kerel operations on the gpu, with autodiff, without memory overflows. Journal of Machine Learning Research, 22(74):1-6, 2021.
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over- smoothing problem for graph neural networks from the topological view. In AAAI, 2020a.
Yu Chen, Lingfei Wu, and Mohammed J. Zaki. Iterative deep graph learning for graph neural networks: Better and robust node embeddings. ArXiv, abbs/2006.13009 2020b.
Luca Di Cosmo, Anees Kazi. Seyed- -reeadd Ahmadi, Nassir Navab, and Michael M. Bronstein. Latent-graph learning for disease prediction. MICCAI, 2020.
Calin Cruceru, Gary Bécigneul, and Octavian-Fugen Ganea. Computationally tractable riemannian manifolds for graph embeddings. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 35, pp. 7133-7141, 2021.
Haitz Sáez de Ocáriz Borde, David Sondak, and Pavlos Protopapas. Multi-task learning based con- volutional models with curriculum learning for the anisotropic reynolds stress tensor in turbulent duct flow. ArXiv, 2021.
Austin Derrow-Pinion, Jennifer She, David Wong, Oliver Lange, Todd Hester, Luis Perez, Mare Nunkesser, Seongjae Lee, Xueying Guo, Brett Wiltshire, Peter W. Battaglia, Vishal Gupta, Ang Li, Zhongwen Xu, Alvaro Sanchez-Gonzalez, Yujia Li, and Petar Veličković. ETA prediction with graph neural networks in google maps. In Proceedings of the 30th ACM International Conference on Information &amp; Knowledge Management. ACM, oct 2021.
Francesco Di Giovanni, Giulia Luise, and Michael Bronstein. curvature-aware graph embedding, 2022.
Charles Fefferman, Sanjoy K. Mitter, and Hariharan Narayanan. Testing the manifold hypothesis. arXiv: Statistics Theory, 2013.
T. Fetaya, Blias Wang, K. C. Welling, Michelle Zemel, Thomas Kipf, Ethan Fetaya, Kuan-Chieh Wang, Max Welling, and Richard S. Zemel. Neural relational inference for interacting systems. arXiv: Machine Learning, 2018.
Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning discrete structures for graph neural networks. In JCML., 2019.
Tamás F. Freund and György Buzsáki. Interneurons of the hippocampus. Hippocampus, 6, 1996.
Jean Gallier and Jocelyn Quaintance. Differential geometry and lie groups: computational per- spective, 2020.
Théo Galy-Fajou and Manfred Opper. Adaptive inducing points selection for gaussian processes. ArXiv, 2021.
Johannes Gasteiger, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. 2019.
11

---

Published as a conference paper at ICLR 2023
Jonathan Godwin, Michael Schaarschmidt, Alex Gaunt, Alvaro Sanchez-Gonzaler Yulia Rubanova, Petar Veličković, James Kirkpatrick, and Peter W. Battaglia. Simple GNN regularisation for 3D molecular property prediction & beyond, 2021.
Albert Gu, Frederic Sala, Beliz Gunel, and Christopher Ré. Learning mixed-curvature representa- tions in product spaces. In ICLR, 2019.
Jakob Hansen and Thomas Gebhart. Sheaf neural networks, 2020.
Yedid Hoshen. Vain: Attentional multi-agent predictive modeling. In NIPS, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. ArXiv, 2020.
Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, 2020.
Anees Kazi, Luca Cosmo, Seyed-Ahmad Ahmadi, Nassir Navab, and Michael Bronstein. Differ- entiable graph module (DGM) for graph convolutional networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 1-1, 2022.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. ArXiv, 2017.
Wouter Kool, Herke van Hoof, and Max Welling. Stochastic beams and where find them: The gumbel-top-k trick for sampling sequences without replacement, 2019.
Oldfich Kowalski, Franco Tricerri, and Lieven Vanhecke. Curvature homogeneous riemannian man- ifolds. Journal de Mathématiques Pures et Appliquées, 71:471-501, 1989.
Wolfgang Küihnel. Differential geometry: Curves surfaces manifolds, second edition, 2005.
Peter B. Ladkin and Stefan Leue. Interpreting message flow graphs. Formal Aspects of Computing, 7:473-509, 2005.
Juho Lee, Yoonho Lee, Jungtack Kim, Adam R. Kosiorek, Seungjin Choi, and Yee Whye Teh. Set transformer: A framework for attention-based permutation-invarian neural networks. In JCMI., 2019.
Shuangli Li, Jingbo Zhou, Tong Xu, Dejing Dou, and Hui Xiong. Geomgel: Geometric graph contrastive learning for molecular property prediction. ArXiv, 2021.
Qi Liu, Maximilian Nickel, and Douwe Kiela. Hyperbolic graph neural networks. In NeurlPS, 2019.
Qing Lu and Lise Getoor. Link-based classification. In Encyclopedia of Machine Learning and Data Mining, 2003.
Apoorv Maheshwari, Navindran Davendralingam, and Daniel DeLaurentis. A comparative study of machine learning techniques for aviation applications. 2018 Aviation Technology. Integration, and Operations Conference, 2018.
Razvan V. Marinescu, Neil P. Oxtoby, Alexandra L. Young, Esther E. Bron, Arthur W. Toga, Michael W. Weiner, Frederik Barkhof, Nick C. Fox, Arman Eshaghi, Tina Toni. Marcin Salaterski, Veronika Lumina, Manon Ansart, Stanley Durrleman, Pascal Lu, Samuel Iddi, Dan Li. Wesley K. Thompson, Michael Donohue, Aviv Nahon, Yarden Levy, Dan Halbersberg, Mariya Cohen, Huiling Liao, Tengfei Li, Kaixian Yu, Hongtu Zhu, Jose G. Tamez-Pena Aya Ismail, Timothy Wood, Hector Corrada Bravo, Minh Nguyen, Nanbo Sun, Jiashi Feng, B. T. Thomas Yeo, Gang Chen, Ke Qi, Shiyang Chen, Deqiang Qiu, Ionut Buciuman, Alex Kelner, Raluca Pop. Denisa Rimocea, Mostafa M. Ghazi, Mads Nielsen, Sebastien Ourselin, Lauge Sorensen, Vikram Venka- traghavan, Keli Liu, Christina Rabe, Paul Manser, Steven M. Hill, James Howlett, Zhiyue Huang, Steven Kiddle, Sach Mukherjee, Anais Rouanet, Bernd Taschler, Brian D. M. Tom, Simon R. White, Noel Faux, Suman Sedai, Javier de Velasco Oriol, Edgar E. V. Clemente, Karol Estrada,
12

---

Published as a conference paper at ICLR 2023
Leon Aksman, Andre Altmann, Cynthia M. Stonnington, Yalin Wang, Jianfeng Wu, Vivek De- vadas, Clementine Fourrier, Lars Lau Raket, Aristeidis Sotiras, Guray Erus, Jimit Doshi, Christos Davatzikos, Jacob Vogel, Andrew Doyle, Angela Tam, Alex Dlaz-Papkovich, Emmanuel Jam- meh, Igor Koval, Paul Moore, Terry J. Lynss, John Gallacher, Jussi Tohka, Robert Ciszek, Bruno Jedynak, Kruti Pandya, Murat Bilgel, William Engels, Joseph Cole, Polina Golland, Stefan Klein, and Daniel C. Alexander. The alzheimer's s disease prediction of longitudinal evolution (tadpole) challenge: Results after year follow-up, 2020.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: collection of benchmark datasets for learning with graphs, 2020.
Tristan Needham. Visual complex analysis, 1997.
C. Qi, Hao Su, Kaichun Mo, and Leonidas Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. 2017 IEEE Conference Computer Vision and Pattern Recog- nition (CVPR), pp. 77-85, 2017.
Raghunathan Ramakrishnan, Pavlo Dral, Matthias Rupp, and Anatole Von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific data, 1(1):1-7, 2014.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-Scale Attributed Node Embedding.
Journal of Complex Networks, 9(2), 2021.
Lars Ruddigkeit, Ruud Van Deursen, Lorenz C Blum, and Jean-Louis Reymond. Enumeration of 166 billion organic small molecules in the chemical universe database gdb-17. 17. Journal of chemical information and modeling, 52(1 1) 11:2664 2875, 2012.
Frederic Sala, Christopher De Sa, Albert Gu, and Christopher Ré. Representation tradeoffs for hyperbolic embeddings. Proceedings of machine learning research, 80:4460-4469, 2018.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi-Rad. Collective classification in network data. Al Mag., 29:93-106, 2008.
Oleksandr Shchur, Maximilian Mumme, Alcksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation, 2018
Hannes Stark, D. Beaini, Gabriele Corso, Prudencio Tossou, Christian Dallago, Stephan Gunne- mann, and Pietro Liò. 3d infomax improves GNNs for molecular property prediction. ArXiv, 2021.
Jonathan M. Stokes, Kevin Yang, Kyle Swanson, Wengong Jin, Andres Cubillos-Ruiz, Nina M. Donghia, Craig R. MacNair, Shawn French, Lindsey A. Carfrae, Zohar Bloom-Ackermann, Vic- toria M. Tran, Anush Chiappino-Pepe, Ahmed H. Badran, Ian W. Andrews, Emma Chory, George M. Church, Eric D. Brown, T. Jaakkola, Regina Barzilay, and James J. Collins. A deep learning approach to antibiotic discovery. Cell, 180:688-702.e13. 2020.
Haitz Sáez de Ocáriz Borde, David Sondak, and Pavlos Protopapas. Convolutional neural network models and interpretability for the anisotropic reynolds stress tensor in turbulent one-dimensional flows. Journal of Turbulence, 23:1 - 28, 2021.
Puoya Tabaghi, Eli Chien, Chao Pan, Jianhao Peng, and Olgica Milenković. Linear classifiers in product space forms, 2021.
Jake Topping. Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M.
Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature, 2021.
Ashish Vaswani, Noam M. Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. ArXiv, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. ArXiv, 2018.
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 (TOG), 38:1 12, 2019.
13

---

Published as a conference paper at ICLR 2023
Oliver Wieder, Stefan Kohlbacher, Mélaine Kuenemann, Arthur Garon, Pierre Ducrot, Thomas Sei- del, and Thierry Langer. A compact review of molecular property prediction with graph neural networks. Drug Discovery Today: Technologies, 37:1-12, 2020. ISSN 1740-6749.
Huijun Wu, Chen Wang. Yu. O. Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. Adversarial examples for graph data: Deep insights into attack and defense. In International Joint Conference on Artificial Intelligence, 2019.
Luhuan Wu, Andrew Miller, Lauren Anderson, Geoff Pleiss, David M. Blei, and John P. Cunning- ham. Hierarchical inducing point gaussian process for inter-domain observations. In AISTATS,
2021.
Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings, 2016.
Zaixin Zhang, Qi Liu, Hao Wang, Chengqiang Lu, and Chee-Kong Lee. Motif-based graph self- supervised learning for molecular property prediction. ArXiv, 2021.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. arXiv: Learning, 2020.
Yanqiao Zhu, Weizhi Xu, Jinghao Zhang, Qiang Liu, Shu Wu, and Liang Wang. Deep graph struc- ture learning for robust representations: survey. ArXiv, abs//1033.000.. 2021.
A RIEMANNIAN MANIFOLDS
In Riemannian geometry, we define Riemannian manifold or Riemannian space (M, g) as a real and differentiable manifold MM in which each tangent space has associated inner product g. that is, a Riemannian metric, which must vary smoothly when considering points the manifold. The Riemannian manifold M RN (lives in the ambient space RV) is collection of real vectors, and is locally similar to a linear space. The Riemannian metric generalizes inner products for Rie- mannian manifolds. It also allows define geometric notions lengths of curves, curvature, and angles to name a few. If the point Xp E M, then we can de- note the tangent space at X, T M, which has the same dimensionality collection of all tangent vectors at X3. Morcover, 9x, M x M - IR is given by a positive- definite inner product in the tangent space and depends smoothly on Xp. geodesic represents the shortest smooth path between two points in Riemannian manifold and generalizes the notion of a straight line in Euclidean space. The length of smooth continuously differentiable curve L - 7(1) M. e [0, 1] is given by
Riemannian manifold such as
M. M is the
L(>) (1)l Jo
Note that L(7) is unchanged by monotone reparametrization. The geodesic distance between two points Xp., Xp, E .M is defined as the infimum (greatest lower bound) of the length taken over all piecewise continuously differentiable curves, such that
Pxpa KP3
argmin L(7) (0) Xp,, 7(1 Xpy-
(6)
The norm of a tangent vector v E M is given by
|||| = V 1x, (v,
Moving from a point x, e M with initial constant velocity v Tx, M is formalized by the expo- nential map
14

---

Published as a conference paper at ICLR 2023
expx, M - M,
(8)
which gives the position of the geodesic at = 1 so that
expx, (v) 711)
(9)
There is unique unit speed geodesic 7 which satisfies 70) Xp and 7'(0) On the other hand, and less relevant to the work at hand, the logarithmic map is the inverse of the exponential map
logx, = =xTPx M T.
(10)
In geodesically complete Riemannian manifolds, both the exponential and logarithm maps are well- defined (Needham 1997)).
In general, it can be impossible to find solution for the geodesic between two points for an arbi- trary manifold. As discussed in the main text, we want to able to move beyond constant curvature spaces and compute the similarity measure for latent features which may reside in a more general and learnable manifold. This will enable us to more accurately model data which may comprise varying structure, beyond that which can be represented in Euclidean space, and also beyond hier- archical or cyclical data which can be linked to constant curvature hyperbolic and spherical spaces, respectively. That is, by varying structure patterns in different regions of space. Generating more complex manifolds we intend to minimize the distortion incurred in the data and to represent the points in more suitable manifold for the downstream task. However, we must still be able to map the Euclidean output features of the net- work to our learnable manifold and to compute distances between points. To generate plex and Iearnable manifold while still having a closed form solution for the exponential map and geodesics, we will introduce a product manifold embedding space composed of multiple copies of simple model spaces with constant curvature. Although product manifolds based on constant curva- ture models still fall under the homogeneous manifold category (Kowalski et al. (1989), they allow to model more complex embedding spaces for the dDGM module than those that can be represented using only constant curvature homogeneous spaces.
refer data which may present different underlying
com-
For example, the standard torus, which can be obtained by multiplying two spheres, is homoge- neous manifold. Nevertheless, some points on the manifold have positive Gaussian curvature (outer part of the torus, elliptic points), some have negative (inner part, hyperbolic points), and others have zero (parabolic points). This is because for the torus the Euler characteristic (Beltramo et al. (20TT) is zero it must always have regions of negative Gaussian curvature. This is to counterbalance the regions of positive curvature guaranteed Hilbert's 's theorem. The main point is that using product manifolds of constant curvature spaces we can generate manifolds with regions with different Gaus- sian curvature that can help us better represent data structures which may not be purely Euclidean, hyperbolic, or spherical.
For all points on the manifold, we can define a normal vector that is at right angles to the surface. By generating intersections between normal planes (that contain the normal vector) and the surface we can compute normal sections. In general, different normal sections will have different curvatures. We refer Kj and K2 as the principal curvatures. They correspond the maximum and minimum values that the curvature can take at given point (2055). The Gaussian curvature K is the product the two
K = K1Kg-
(11)
A Riemannian manifold is said to have constant Gaussian curvature if sec(P) = for all wwo-dimensional linear subspaces P M and for all Xp M. Manifolds can be classified into three classes depending on their curvature: flat space, positively curved space, and negatively curved space.
15

---

Published as a conference paper at ICLR 2023
B FURTHER DISCUSSION ON CURVATURE LEARNING
Next, we aim to provide more detailed explanation on the topic of curvature learning for product manifolds and the implemented procedure using learnable distance-metric metrre---tcci-iiingg coefficients. Let us discuss product manifolds which are solely generated based on Cartesian products of the same model spaces, such as
Pa
(12)
KM
which uses Cartesian products of hyperboloids. Likewise, taking Cartesian products of hyperspheres we would obtain
Rgg Ps
(13)
km
For these cases, although
all H
P1
P2
and
x()) Pi
x
are in practice computed all pz
using hyperboloids and hyperspheres with the same fixed curvature K 1, Vj. and K 1, Vk, the scaling coefficients control the curvature of the spaces individually.
ng
x(() ps )
Opp (Xp1, Xp2)
0 H
x PI
(14)
and,
(x(0) x
Dp, (xp: Xpx) =
(15)
That is, a and of scale the distances generated based on unit hyperboloids and hyperspheres, respectively. Using the scaled metries, we are effectively still computing Cartesian products of hyperboloids and hyperspheres with different curvatures, so that
PB
(16)
KH
P3
(17)
Kg
1=1
k=1
This guarantees we are retrieving equivalent values to those which would be generated by model spaces with different curvatures. This is done to avoid backpropagating through operators such as exponential maps and closed form solutions for distances in the different model spaces.
Considering again an arbitrary product manifold of all model spaces as in Equation 2 the curvature through the following derivatives
we can control
d0p
(18)
da H
for the hyperboloid terms, and
16

---

Published as a conference paper at ICLR 2023
@0p dok
(19)
for the hyperspheres. In the case of Euclidean space the curvature is always Kg 0, there is no need to learn it. Also, using a Cartesian product of Euclidean spaces would be equivalent to using a single Euclidean space of greater dimensionality
nly
P2
Edg Kg
(20)
where KT Kg - O, Vi, and dg d Hence, in Equation we used a single Euclidean space. The behavior described in Equation 20 can be better appreciated by comparing distance Pp
obtained using Pp. and d gde from Edg
2
(21)
P3
E
Egg
2
Pp
02
d2
2 TE
(22)
E
Considering that the equation for independent distances in each Euclidean space
Σ
Xpi
xp2
(23)
we obtain,
dp: Σ
Xpi
(a)
(a)
2
+
Σ
Xpi
(b)
Xp2
(b)
2
(2)
Xpa
(2)
(24)
which is analogous to taking the second power of the difference of two points in another Euclidean space with more dimensions, so that
Pp p
(25)
This behavior is only applicable to Euclidean space (Gu et al. (0119), when multiplying other model spaces
PE =
*
dh Ks
(26)
KB
ng
P8
S
(27)
R
Kg
k-1
even when the curvature is the same for all hyperboloids and hyperspheres, K Kg, Vj and
K Kg, Yk. For example, multiplying two hyperspheres will result in hypertorus, not higher- dimensional hypersphere.
As final remark, note that any loss function which is dependent the distance function induced by the Riemannian metric of a Riemannian manifold is locally smooth on M (where M could be product manifold P)) and be optimized by first order methods.
17

---

Published as a conference paper at ICLR 2023
C TRAINING PROCEDURE
In this appendix we discuss key concepts to train the dDGM module. We detail how to back- propagate through the discrete sampling method and introduce an additional loss term to make this possible. We also we provide additional implementation details for updating learnable distance- metric-scaling coefficients and dealing with distance functions during training. Lastly, we describe the two approaches used in this work to make training computationally tractable for larger graphs: symbolic handling of distance metrics and graph subsampling.
C.I BACKPROPAGATION THROUGH THE DDGM
The baseline node feature learning part the architecture is optimized based on the downstream task loss: for classification we use the cross-entropy loss and for regression the mean squared error loss. Nevertheless, we must also update the graph learning dDGM parameters. To do so, we follow the approach proposed by Kazi et al. (2022) and apply compound loss that rewards edges involved a correct classification and penalizes edges which result in misclassification. We define the reward function,
8 (yt, 9i) E(ac,) ac;
(28)
the difference between the average accuracy of the ith sample and the current prediction accuracy, where and ÿs are the predicted and true labels, and ac; = 1 if yi ft or 0 otherwise. Based on (ys, di) we obtain the loss employed to update the graph learning module
LGL Σ
8 (v.. 01)
Σ
Σ
log Pog
(29)
Lat's 's gradient approximates the gradient of the expectation
N
((g0,,...guu) (..,.gg))))(())).) .p..)..,PP..)
Σ
(vi, 0z),
(30)
with respect to the parameters of the graphs in all the layer lGL. So that,
dLGL d
N (yt, 96)
gug P(D))
(31)
d0GL
doGl
The expectation EE(cc)) (1) is calculated based on
E(ac,) (E(ac,)(tt)) (1 B))c2,
(32)
with 3 = 0.9 and (tac,)(t-0) = 0.5. For regression we use the R2 score instead of the accuracy.
C.2 UPDATING LEARNABLE DISTANCE- MEWRRC--SRALLEEEE COEFFICIENTS
The scaling metrics are learnable, so that we can indirectly adjust the curvature of each model space without having to backpropagate through the exponential map functions and the formulas for the distances. we simply take the derivative the graph loss and update the distance-metric--caling coefficients during training (t) = (t-1) - Ir بللاا by (Ir being the learning rate) this can result in negative values for the coefficients that multiply the distances in different model spaces, which would be mathematically incorrect since distances are by definition positive or zero. To solve this issue leam á, instead of a. The two related by the following equation,
(ā)). where bau b which means that S is the sigmoid function. So that (1) ((ā( S (ā(1-1) Ir eLot
18

---

Published as a conference paper at ICLR 2023
O < a<a( < 1. Using ReLU instead of S could allow (!)) to take arbitrarily large positive values, but we would have gradient problems if & becomes negative. Given that using the sigmoid function bounds the maximum value that the scaling metries can take, must multiply the Euclidean plane distance by its own scaling coefficient. Since the Gumbel Top-k trick selects the closest points to generate unweighted edges, rather than storing the actual geodesics, if we scale the Euclidean plane contribution down when necessary, this would equate to having other model spaces with much bigger curvature than that which is actually possible due to the scaling coefficient being now bounded by zero and one. For example, if we were to have a product manifold based on the Cartesian product of the Euclidean plane and a hypersphere, if the model learns a scaling metric close zero for the Euclidean plane geodesics, this would be equivalent to having a hypersphere with really large curvature since edges would only be generated based on the distances calculated on the hypersphere. Finally, note that in practice we use the Adam optimizer instead of simple gradient descent for training.
C.3 COMPUTATIONAL EFFICIENCY
In this section discuss some of the implementation techniques used to make computation more efficient. We cover two main topics: symbolic handling of distance metrics and graph subsam- pling. One of the main computational limitations of the approach described in this work is that we must compute distances between all points to generate the latent graph. Although the discrete graph sampling method used by dDGM more computationally efficient than its continuous coun- terpart, cDGM- - because it generates sparse graphs that make convolutional operators lighter we quickly run into memory problems for graph datasets with O11*)) nodes. Starting from a point- cloud, we must compute the distances between all points to determine whether connection should be established. This problematic, since the computational complexity scales quadratically as a function of the number of nodes in the graph, which can rapidly become intractable as we increase the size of our graph.
Most of the experiments were performed using NVIDIA Tesla T4 Tensor Core GPUs with 16 GB of GDDR6 memory. NVIDIA P100 GPUs with 16 GB of CoWoS HBM2 memory, or NVIDIA Tesla K80 GPUs with 24 GB of GDDR5 memory. All these GPUs have limited memories that are easily exceeded during backpropagation for datasets other than Cora and CiteSeer (Yang et al. (2016); Lu & Getoor (2003); Sen et al. (2008), which have 2,708 nodes and 3,327 nodes, respectively. For example, using the standard Py Torch Geometric implementation we are not able to backpropagate for the PubMed dataset which has 18,717 nodes.
C.3.1 SYMBOLIC HANDLING OF DISTANCE METRICS
To avoid memory overflows we resort to Kernel Operations (KcOps) (Charlier et al. (202 which makes it possible to compute reductions of large arrays whose entries are given by mathematical formula. We can classify matrices in three categories: dense, sparse, and symbolic.
Dense matrices are dense numerical arrays Mi = Mi. jl which put a heavy load on computer memory. When they increase in size, they can struggle to fit into RAM or GPU memory. This is what happens in our case, when calculating distances between points. Sparse matrices are typically used try to address this problem. Sparse matrices use lists of indices (In, jn) and associated values Mn. Hence, in sparse matrices we only store the values for non-zero entries. The main limitation of this approach is that the computing speedup obtained by using sparse matrices is highly dependent on sparsity. To obtain significant improvements in performance using sparse encoding, the origi- nal matrix should effectively be more than 99% empty (Charlier et al. (2021)). This significantly constrains the applicability of sparse encoding.
Alternatively, KeOps uses symbolic matrices, to represent matrices which can be summarized using an underlying common mathematical structure. In this setup the matrix entries Mi, are represented as a function of vectors x, and X,. so that
My = F(x;, Xy).
(33)
Even if these objects x; and Xj. which can result into large improvements in computational efficiency, avoiding memory overflow. In our case, the matrices we are working with are fully populated and using sparse tensors
necessarily sparse, they can be represented using only small data arrays
19

---

Published as a conference paper at ICLR 2023
would not enhance performance. On the other hand, the symbolic approach implemented using KeOps enables us to represent the original dense matrix containing all the distances between all the points in much more compact way, and to work with larger graphs than Cora and Citeseer (Yang et al. 2016); Lu & Getoor (2003): [Sen et al. (2008),, namely, PubMed, CS, and Physics (Shchur al. 2018)). Finally, note that in our case the function used by the symbolic matrix is the distance metric appropiate for whichever manifold we are using to construct the latent graph.
My x,),
(34)
C.3.2 QUANTITATIVE STUDY OF RUNTIME SPEEDUP
We quantify the runtime speedup obtained by using symbolic handling of the distance metries when generating latent graphs for Cora and CiteSeer. Note, however, that improved execution time is not the only benefit of symbolic handling. As discussed in Section C.3.1 symbolic matrices also help avoid memory overflow for larger graphs. Indeed, this is the reason we choose Cora and CiteSeer to conduct these experiments: using other datasets we experience GPU memory overflow when using dense matrices, and hence we cannot compare dense to symbolic matrix performance. It should also be highlighted that using both dense and symbolic matrices gives the same results in terms of accuracy since they are equivalent mathematically, the difference lies in the computational efficiency of each method.
We display the results in Ta and Table 6 in which we record execution times for 100 epochs using a NVIDIA P100 GPU. We evaluate the effect increasing the number of dDGM layers on the runtime. We also compare the dDGM module using Euclidean (GCN-dDGM-E) and a product manifold of Euclidean, hyperbolic, and spherical space (GCN-dDGM-ERL) EHM)) to generate the latent graphs.
Table 5: Results for runtime speedup quantification using symbolic as compared dense matrices. These results are for the GCN-dDGM-E model using h 3 and training for 100 epochs using NVIDIA P100 GPU.
Dataset
Runtime + Standard
Dense
Cora
1.9810.01
Symbollc
Cora
2.64:0.01
3.50g0.02
Symbolic
CiteSeer
2.732.0.02
Denie
Cora
4.87 10.10
GCN-IDGM-E
Symbolic
Cora
4.031.0.00
Dense
CiteSoer
6.1640.58
2
Symbolic
CiteSoer
4.13g9.02
Dense
Cora
6.5319.15
Symbolic
Cora
5,38g0.00
Dense
CiteSeer
8.4210.0
Symbolic
CiteSoer
5.51
Table 6: Results for runtime speedup quantification using symbolic as compared to dense matrices. These results are for the GCN-dDGM- EHS model using l 3 and training for 100 epochs using NVIDIA P100 GPU.
Model
No. dDGMs
Matrix
Dacaset
Runtime (s) Standard Deviation
Donse
Cora
6.17:0041
Symholic
Cor
4.27-000:
Dense
CiteSear
7.92=0.81
Symbolic
CiteSeer
4 4.38_00.2
2
Dense
Com
10.67_003
GCN-IDGM-ERS
2
Symbolic
Dense
CiteSeer
Cora
14.15
7.18-000
2
Symbolic
CiseSeer
7.48=0.16
Dense
15.922.013
3
Symbolic
Corn
10.09_00.s
3
Donse
CieeSeer
20.85=0042
Symholic
CheeSear
We can that add more dDGMs the difference between using dense and symbolic matri- ces becomes more substantial. Likewise, the benefit from using symbolic matrices becomes more apparent when using product manifolds, this is because more distances must be computed. The
20

---

Published as a conference paper at ICLR 2023
product manifolds are calculated based on the Cartesian product of three model spaces and hence, to obtain the overall distance between each of the nodes, we must compute geodesics in all constant curvature manifolds independently. Another observation that time for CiteSeer increases substantially as compared to Cora using dense matrices. CiteSeer only has 995 more nodes than Cora, yet using 3 dDGM--HS layers the execution time for 100 epochs increases by 5.53 seconds for dense matrices. This clearly shows that using dense matrices can quickly become hard scale for larger graphs, which can have orders of magnitude more nodes than CiteSeer. In line with the literature, using symbolic matrices is more computationally tractable for larger graphs Kazi et al. (2022).
make is that the computation
Also, we run some additional experiments to quantify the increase in computation time as function of k, that is, the number of edges per latent graph node when applying the Gumbel Top-k trick. As we can see in Table 7 and Table [ k does not seem to have statistically significant impact on the execution time. As before, we find that using symbolic matrices consistently more efficient.
Table 7: Results for runtime speedup quantification using symbolic as compared to dense matrices for different - 30. These results are for the GCN-dDGM-E model and training for 100 epochs using a Tesla T4 GPU.
GEN Jeca
Mitin
Ditedt
Restencti =n Sunkhri Dovadie
Sysball:
Orea
Synbalk::
Chedier
1000
Syrehik:
Ont
1s
Deau
Chedse
Sprehakk:
Orea
1
Desu
Clulzer
Desu
Coea
Deni
ballxur
Desie
Ouaa
Deaid
Cledeer
Syrehukk
10
Deaic
Ouea
10
Desie
Glafeer
Symbolk:
Cludee
1001
30
Desu
Gra
Desic
Cledee
31
Systuk::
Cluiserr
30
Desic
Ovea
Synbik::
Cres
1.21
30 Sysbul::
CleSee
3.300400
Table 8: Results for runtime speedup quantification using symbolic as compared to dense matrices for different l 1 30. These results are for the GCN-dDGMMEHS model and training for 100 epochs using a Tesla T4 GPU.
DDN CoO
Mitta
Rentencco
Deauz
Osea
Desiz
Clefeer
Symbhlkk:
Cludee
4.7
Desu
Gra
L-Faans
Desic
Cleden
Cluiper
Desve
Ore
Clulaer
Spreuul::
ClsSee
Deasz
Okea
Oue
Sprebalk:
Clufser
Deau
Orei
Syresikk
Clefser
In Spenoi::
10
Symbak::
Clacker
20 Symbak::
Ors
Desc
Clefser
Sinbil::
(Zeeaes
Desu
Cludser
21

---

Published as a conference paper at ICLR 2023
C.3.3 TRAINING ON LARGE GRAPHS
Although symbolic handling distance metrics is certainly necessary, for larger graphs such the graphs for node property prediction of the Open Graph Benchmark (OGB) (Hu et al. (2020) which
have O(109) (105)) nodes and O(10%) O(10)) edges, we must combine KeOps with graph subsampling techniques to make backpropagating computationally tractable.
We apply a neighbor sampler track message passing dependencies for the subsampled nodes. This allows computation to be more lightweight, Based on the message passing equation
(+11
(xx²)
(1) x
(xx xx)))
(35)
(BN(s))
to calculate x; ((+1) we must aggregate, and hence, have stored the node features of its neighbors when subsampling the graph. Note that unlike the original node prediction setup in which we give as input all the nodes and predict properties for all nodes in the complete graph, here we have different number of input and output nodes, which gives rise to a bipartite structure for multi-layer minibatch message passing. Such a bipartite graph, which samples only the necessary input and output nodes from the original graph, is called a message flow graph (Ladkin & Leue (2005).. For every node that we compute in given batch we will need to track its message flow graph alongside all relevant dependencies.
D THE AFROTHER DATASET
We generate a multi-class classification dataset based on Computational Fluid Dynamics (CFD) sim- ulations conducted for the rocket designs developed for the Karman Space Programme. Specifically, the dataset is generated based on the shock wave velocity distribution around the nose of a rocket at 10 degrees of angle of attack. The simulation meshgrid has varying degrees of resolution, and the shock wave is not symmetric due to the angle of attack. Although CFD software uses meshgrid discretize space and run the aerothermodynnmmies simulations, it can be challenging to extract the connectivity of the original graph, since most often the software is designed to only output a point- cloud. Moreover, given that across shock wave, the static pressure, temperature, and gas density increases almost instantaneously and there is abrupt decrease in the flow area, the original graph can present high heterophily. Hence, latent graph inference can be beneficial.
For the dataset, we only consider the shock region at the leading edge of the rocket. To obtain the class labels, we separate the shock flow absolute velocity into regions: < 300 m/s, 300 - -50 m/s, 450 650 m/s and > 650 m/s. The original simulation has 207,745 datapoints, but we only focus on the shock around the nose of the rocket and apply graph coarsening, see Figure
Figure 4: Pointcloud plot of shock intensity regions. The different regions represented using different colors which correspond to each target class. This the dataset after applying graph coarsening.
22

---

Published as a conference paper at ICLR 2023
The network input is pointeloud with pressure values. Note that the coordinates with respect to the rocket are not given to the network. The model is tasked with classifying the shock into four intensity regions which are based on the absolute velocity distribution. Table 9 summarizes the dataset.
Table 9: Summary of properties for Acrothermodynamics dataset
Aerothermodyuamics
Homophily level
N/A
Nodes
1,456
Features
Edges
N/A
Classes
Averuge Degree
N/A
Learning
Transductive
Task
Classification
Network Type
CFD simulation
E ADDITIONAL EXPERIMENTS AND RESULTS
In this appendix we include additional experiments for the latent graph inference system. In Sec- tion E. we explore using more than one latent graph inference system per GNN model. In Sec- tion we include additional results for the homophilic graph datasets in which we vary the value of k for the graph generation algorithm. In Section F.3 we experiment with using greater number of model spaces to generate product manifolds for the embedding space.
results for heterophilic datasets, Section E.5 for OGB, and Section [.6] for inductive learning. The First, Second and Third best models for each dataset are highlighted in each table.
E. NUMBER OF DDGM MODULES
In these experiments, we investigate whether there is any benefit in stacking multiple dDGM mod- ules. Using multiple dDGMs effectively means that within the model, the network layers would be learning based on different latent graphs. In principle, according to the results in Table [O]and and [T] there is no clear improvement in performance for Cora and CiteSeer. In fact, the accuracy of the models can decrease. It is only for PubMed that there is sometimes some improvement in the ac- curacy. These results align with previous studies by Kazi et al. (2022). Finally, we also run a few experiments for Physics and CS. Again, we find no substantial improvement using an additional aDGM module, see Table I2 Given our findings, we use a single dDGM module, since it is more computationally efficient.
Table 10: Results for Cora, CiteSeer, and PubMed using more than one dDGM* (taking a pointeloud input) latent graph inference module.
Cora
CiteSeer
PubMed
Model
Layers
Accuncy (%) Standard Devintion
GCN JDGM EE
dDGM' XCCNGCCNGGN
62. 482324
62. 22.47
83.8920.70
GON-dDGM".
dDGM' XGCNADGMM COONAIDMMGGNNGNN IGINGGN
54.221a.79
50.7612.3
15.74
GCN.
dDGM* GGNGGNNGGN
61.07
13, 2.19
86.67 10.00
GCN-IIGM* -IH-M -H
JDGM*
61,96:445
65.3646.36
L..19
GDG EHS
DDGM-GGCNGGCNCCCC
66.87
63. 2..80.2..4
87. 00000
GCN-dIXGM* -EHS
dDEM /GCNNDGMM KIUNGGG
30.861436
61.6643.
86.32.0.70
GCN-IDGM*
60.63g9.41
63.2 63.2849.36
80.52
GCN-IDGM" -B
JDGM LDGMMI/GCNDDOO BOCCADGMMGOOCCOOOO
52.15:421
56.16
79.01:444
GDG
dDGM* /CCNGGNGGGNN
61.50
86.90_1.16
(CN-dIXGM* -HH
JDGM XICNNIIIM XGUNNGGN
45. a5.30+0.06
61.69944.35
82.122554
GCN CDD EHS
dDGM JCCGGCNNNN
64. 64.82:3.68
64.
30.8520.07
GCN-DDGM* -HHS
dDGM XGCNNDGM KINNGGN
45.07.14.1
45.4213.00
22.992.044
MI.P*
N/A
Lincartl Innear Inear
58.92_.0.8
50.4819.34
85.7511.00
23

---

Published as a conference paper at ICLR 2023
Table 11: Results for Cora, CiteSeer, and PubMed using more than one dDGM (leveraging the original graph connectivity structure) latent graph inference module.
Cora
CiteSeer
PubMed
Model
k
Layers
Accuracy (%) Standard Deviation
GCN-IEGM-E
aDENIGCCWECNGGNN 10.44
10.1813.4
87.45
GUN-IDGGM-E
3
DDGMMGENNDGMGGNGGG
70.44:5.81
60.85
86.67 67
GCN JDGM-DGMRR EH
3
ADGMIGCN/GCVIGN
25.
72 12.89
87
OCN-IDGM-ER
71.301,.30
72.32,7.0
87.072
GCN-JDGM-ENI EER
3
ZDCAIGCCOCNCGCN
84.70=2.96
69 20.98
87.35
SCN-JDGM-ERNY ERS
ADGMISCNIDGMGGNNGNN
79.07
71,99e104
86, 96..9
ADGMEE
ADOMYGCN/CCVIGN
82.74
11.7813.00
GUN-IDGMM-
72.7069.0 08
68 68:25
86.30
GCN BEN-DDGM-ERE EH
5
ADGMIGCX/CCVGGN
52.32g471
73 73.56:22.75
87. 20.77
GCN-IDGM-EH
ADCM//GCNWDGMGGGEEEYY
76.041120
12.31
86.40
GON-IDGM-EHS
5
ADCMIGCNIGCNGGN
83.58.4.00
74.00.1.68
87. 07.12
GUN-IDGM-ERN
ADGMGGCNIDGMGGCNGGEN
76.67
70.42+1.00
82.37 +
NIA GENGGCNIGCN
g3.1
69.97
85.75ga.0
Table 12: Results for Physics and CS using two dDGM latent graph inference modules with a product manifold combining Euclidean, hyperbolic, and spherical model spaces.
Physies
Model
Layers
Accuracy (%) Standard Deviation
GCN-aDGM EDS OCN JDGM-DGMBBR ENS
IDGMNGCNNGNNGGNN
96.17 .0.50
92 06.0..0
ADGNICENNDDGMSNNNNN
96.18_0.31
87.00.4.00
N/A
GONGGNNGCN
96.51-0.54
28
E.2 HOMOPHILIC GRAPH DATASETS EXTENDED RESULTS
In this section we include extended results for the Cora, CiteSeer, PubMed, Physics, and CS datasets. presents results using single model spaces for the embedding space, and Table [4 and
Table 13
Table 15 using product manifolds. As discussed in the main text, the dDGM" does not use the original dataset graph as inductive bias, since it is only provided with a pointcloud. On the other hand, the dDGM does use the original graph. Different k values are applied.
E.3 MORE COMPLEX PRODUCT MANIFOLDS RESULTS
The main objective of this section is trying to test the limits of our approach. In Table [6 display the results multiplying up five model spaces for the CS dataset. From the results, we can that adding more product manifolds can result in improved performance. The SCN-dDGM-EHHR network with space based model GCN-dDGM-E with k- 5 which achieves result of only 87.88 + 2.55%.
obtains an accuracy of 93.10 0.74%, as compared the best single model
E.4 HETEROPHILIC GRAPH DATASETS EXTENDED RESULTS
In Table 17 we display the results using both the dDGM and the dDGM" module for heterophilic datasets. The dDGM module uses the original dataset graph as inductive bias for the generation of the latent graphs. As expected, this leads to worse results than those using the dDGM for heterophilic graphs, since the original graph not good for diffusion using GCNs. It is better to start directly from pointcloud and completely ignore the original adjacency matrix A (0) since it does not provide the model with good inductive bias.
E.5 RESULTS FOR LARGE GRAPHS FROM THE OPEN GRAPH BENCHMARK
Table 18 and Table I9 display results for the OGB-Arxiv and OGB-Product datasets. Although the OGB-Products dataset is considerably larger than the OGB-Arxiv both in terms of the number of nodes and edges, our models achieve slightly better performance. This may be due to the fact that the OGB-Produt dataset is undirected graph, whereas the OGB-Arxiv dataset is directed. The dDGM module generates undirected edges between nodes by construction (if we neglect the noise in the Gumbel Top-k trick), which may be affecting performance in the case of the OGB-Arxiv dataset.
24

---

Published as a conference paper at ICLR 2023
Table 13: Results for classical homophilic datasets combining GCN diffusion layers with the dDGM* and dDGM latent graph inference system and using single model spaces construct the latent graphs.
Corn
CiteSver
PubMid
Phyddos
Homephily
0.81
0.95
Nodes
2.708
3,327
15.717
34,493
18,333
Peatures
1.433
3,703
8,15
Edges
5.278
4,766
44,527
247.402
$1,394
3.9
14:38
Model
Acsumnay (86) Standand Deviation
OCN JDGM E
02. 48 3.24
02:47.33 2:20
63,59 1.70
76.00 16
OCN 4DGM H
63 82 1.00
63 70138.0 40
87.15:0.00
10, 24.44
78.26
OCN-IDEMM-
52.78
21.96gg 33
11.60
56.57
51.52g
OCN 4DGM E
63.25 1.35
86 86.82 0.09
00. 13 10.50
80.461234
OCN-IDEMM--
70
65,001
GCNJDGMM-
12.04gaun
22
40.38
70
70.07 07
62.
13.33
03
GCNJDDGM--
OCNJDGGM-S
41.71gias
OCN-IDGM--E
61 61.57
64 27
65.1824
01. K7as
81. 122
OCN-IDGM-H -H
10
61 61.68
63.0220
64 34.22
95 02
80.56ea
OCNJDGGM'S -8
10
$1.04geu
19,9
30
69 (0.55aa
MLP
N/A
59 Beg ua
85.75g on
87. 80
Coru
Cieeeer
PuhMed
Physies
CS
GCNJDGM-
50.44
10.18.1
08:5.41
OCN
50.3114.00
63/75.1554
65.70
05.20
80.00
GCN-DDGM.
71.30141
07.08.231
$1.39 1.0
01.00
76.76
JDGMEE
52.74
71.75.1
87.00:0m
87.66 87.88
JDN--DGM-H
40.50
07.63
67.58
87.05.2
OCN-IDGMM-
50.81
71.8121
77
16,
75a
DDN
52. 52
87.00 87.00.s1ar
DG, 1.
87.1 17.177am
OCN JDN
84 3..6
40:43:445 95
87.74.0.72
06 06 10.4.
68. 78:78
OCN-IDDEM-
50. 90.4
72 K..05 en
87.13ar oo
16. 7Mgg as
8621
JDGM-
10
72.64:2.1 51,675506
95 99:9.
88, 10:9.s
CCN-HIXIM--
10
83 15:3
11.54:1 as
87 080 ne
10 81
48-- 31
OCN-I
50.70gam
72.20gr
87.3853
96 030g
85, 85.90ga
NIA
63. 13.11:22.
09:07:244
85.76g:um
87.28
Table 14: Results for classical homophilic datasets combining GCN diffusion layers with the dDGM* module and using product manifolds to construct the latent graphs.
Cora
CiteSeer
PubMed
Physics
CS
Homophily level
0,81
0.74
0.50
0.93
0.80
Nodes
2,708
3,327
18,717
34,493
18,333
Features
1,433
3,703
500
8,415
6,805
Edges
5,278
4,676
44,327
247,962
$1,894
Classes
5
15
Averaee Degree
2.77
14.38
Model
A:
Accurasy (%) i Standard Deviation
GCN- SCN-IDGM".NM HHH
57.00g9.76
62.50
87.43:0.40
92. 32.20
74.88g4.0
GON-IDGM"
38.26-1051
24.201
41.50
54.40.110.00
GCN-IDGM--EE
81.07-3011
65.1312.1
16.6719.m
94.85_e.55
85.9112.1
GCN-IDGMM
62.07:106
64.31
86.85
95, 05.00=0055
78-07=4-41
GCN-IDGM*
59.55=10.30
63.95+2.55
8T 04:0079
76.55=9.00
GCN-IDGM" EHH
70. 40.85:4.30
68 2612.77
39 39.93
95 21 10.34
92: 22:2221100 1.00
GCN-JDGM" EBS
66.87
63,50 63,50
ST. 00.77
95. g5.00
88.0
GUN-IDGM*-HH
501033:
633
114.31
76.48
GCN-IDGM"
11 11.33=10.44
21. 58
40. 70
53. 13
58. 47
JCN- EH
63.67
611.9.
$6.90
91. 97.94_3.37
86.0 86.00
GCN-IDGM"
63
63.1019.11
86.83.9.4
90.92_9.0
11.86:11.19
GDN-
64.4414.0
62.8013.00
44.17
94.81 110
77.90
GON-IDGMM.PPE EHH
69. 700.74--.00 m9
66 81:2 0.
95 25:225:.000 on
90 40:46:110
GCN-IDGM" EHS
61.82g3.66
61.62
86 86.85
91.30122.0
88.45 187177777
GDN-
54.58130
12.1215.7
1o.s0
94.08
19.8815.77
GCN-IDGM -SS
40:222 18.00
20.54+9..4
41.499) 89
58 G7: 1
50 50.94+14.50
GCN-IDGM .HH
59 00.92:... se
64. 64.779.9.0
86.07
18.18
80.82:6033
GCN-IDGM"
86-18-23
71.81=124
GCN-IDGM SS
29.11
64 3.0000
25.21
94.72
83. 83.20
GCN-IDGM" FHH
70.37 4..2
02.7501111 4P
39.031 153
95.16 16.11.1..0
91. 158 11
GCN-IDGM"
63. 63.30+3.08
64.54+1.50
86
86 26.966-2.64
GCN-IDGM"-HE
10
57. 67.509e..0 do
30. 0..3335.u on
86, 13-33e30v0 70
92. 50.00=
73. 13:13:s
GCN-JDGM JDGM SS
10
36.3024.25
21.20
39 33.8311.11
501.2
53.85216.76
GCN-IDGM" -EH
58.63_11.1
65.49
84.5415.7
90.55_4.5
72.79.55m
GCN-IDGM -ES
63.04+421
62. 12.6544..o
86.71
74.85=7.00
JEN-JDGM'TAA HHS
10
61.21::.35
62. 73.7332.
85.21:-455
95.0 35.03
75.03
SCN-IDGM'-EED EHH
10
69.63:-4.0
61, 7054.1
39.93=
95. 02-4..0
83.81+11441
GCN JDGM
63.61gam1
64.5212.77
86.00g..00
90.03
84.52gg730
MLP
N/A
58.992+3.58
50, 48441842.14
85.75 m
94.91=6.0
87.80-1.51
25

---

Published as a conference paper at ICLR 2023
Table 15: Results for classical homophilic datasets combining GCN diffusion layers with the dDGM module and using product manifold to construct the latent graphs.
Cora
CiteSeer
Peb
Physies
CS
Homophily level
0.81
0.74
0.80
0.93
0.50
Nodes
2,708
18,717
18,533
Festures
1,433
3,703
500
8,415
6,805
Edges
5,278
4,676
44,327
247,962
81,894
Average Degroe
3.9
8.93
Model
Accuracy (%) Standard Deviation
MON-ADDGM-H
17-8215-46
T1.27
15.30.
g4.04
82.91
OON-JDGGM-SS
67,00+10.25
59.16es.10
83.8340..00
90.30
50.31=9.18
SCN-DDGM-EII EH
83,05519.25
72.8921.54
87 62
96.07
91.37=2.20
OCN-DDGM-B ES
81.1920.a5
:1.27
86. 17.50.0
95.52ea.44
90.87756.22
GCN HS
80.7012.96
72.77:2.7
10.25
10.000
OCN
N6.59 3.
76.42
28.17 17:17:111 19.39
96.066 se
9/2 Mi
GCN-IDGMMERRS
85 888-4
69 (0.99622.10
35.0.00
95. (0.966e..o
89. 39..9-33.01
GCN.DDGM-IH
16.09
72.65.12.2
17.3610.m
95.00
$0.73...0
CCN.JDGM. SS
65.96:29.8
65.17
29.77
90. 20..00
70.60
GCN-IDGGM-EH
82.32.1-71
73.56.9.75
87. 67
94.48 1.1.1.33
11.11:3..0
GON-IDGGM-S
96.11+0..0
GCN-JDGM-IIS
62.59
72.51
87. 79:19:11.00
18g1344
20.98_1.00
CON-IDGM-EHI
86.63 16.63.n.22
73.96
44.53 13..4 10.81
96, 1619.77
92 300
CCN-JDGMA EHS
63.5814.39
74.00.1.04
67.12
96. 00.300
92 92.06.0..5
OUN-JDGGMM-H
79.70++..5
71 30300..00
0845 is
95, 05,98ea0 64
GCN-JDGM-SS
63.02:19.35
61.39aa.44
87. 11.30.5
91.68 11.68
611.05-11.44
SON-JDGM. EH
12.80
71.8412.70
87. 1.
96. 06.061..52
91. 11.22
OUN-dDXGMM-E
71 11.08--4114
u5.24
80.21
MEN-IDGGM-HE
81. 78
72.41 on
87. 10.42
96.031.9.37
80.00
SON-IDGM-ERHE
(60+49.44
74 67
48. 04:00.0-00
96.
90.74--2.0 774-2..6
63.70:8.as
73.02g2.57
37.61.99.77
96.09ga.5e
90.64g3.20
10
82. 18
72.4779..5
87. 5..00.00..
g4.77 sa
86 08.488.0.0
OCN-JDGMN SS
10
66.15:1141
61 68.51
87. 82.822..00
90.72es.20
69 10.16221
OUN-IDDGM-E
81.44+8.44
90.9881116
GCN-JDGM-ER JDGM-ES
10
80.07:25.40
72.86:2.551
87.5020.06
95.41
90.255
GCN aDGM-HS
10
83.7813332
72.52
85.8014.20
96.8419.22
89. 2..64
GUN- JI---EH-MHHH
EHS
83.50.-.44
71.8211.6
87.0611.38
21
01.42.3..0
GCN
N/A
83. 28.11
69.9 09.97=2.00
85.7521.01
95.51g0.54
87.28
Table 16: Results using more complex product manifolds for the CS dataset. We multiply up to five model spaces to generate the product manifolds.
Model
Accuracy (%) Standard Deviation
GCN-IDGM-E
85 $5.98-2.om
GDN-A
85.95_2..e
GCN-IDGGM-S
76. 70:
BRN-DDGM-EH
91.37
GCN-aDGM.
90. $7_0..2
GCN-IDGM-FRH
92. 86.86-0000
GCN-JDGM-ERE
89 000.93-5.00
GCN-aDGM EHHH
GCN-ADGM-EBHIN
92. 70_.00000
GCN GDN. EHHIS
92. 96
GON-IDGMM
CCN-JDGM E
87. 17..8822.00
GCN.aDGM-H
87. 65
JDGM-
80. 23.
GCN-IDGMMERR
91. 11:0000
DCN-JDGM-ED ES
89. 01.311 39.31=2..51
GCN CCN-JDGM.L 4DGM-HS
90. _8..9
GUN-IDGM-ERI
02.
GCN-JDGM-EERS
92.066.0.00
GCN-JDGGM-ED MHHH
92. 63-63-0
GCN JDGM COOMEEHHS
02.52.1.54
GCN-JDGM-EREE EHHSH
92: 91. os
GON-IDGM-EEHHSS
93. 033.00+000
GUN
26

---

Published as a conference paper at ICLR 2023
Table 17: Results for heterophilic datasets combining GCN diffusion layers with the dDGM" latent graph inference system. We display results using model spaces as well as product manifolds to construct the latent graphs.
Wisconsin
Squirrel
Chameleon
Homophily level
0.11
0:21
0.22
0.23
Nodes
183
251
5,201
2:277
Features
1,703
1,703
2,089
2,325
Edges
295
466
198,498
31,411
Classes
5
5
5
Average Degree
3,22
3,71
76.33
27.60
Model
Accuracy (%) i: Standard Deviation
GON-dDGM"-E -E
80.00
86 .5.00
34.35,2.34
48.90,1.61
GON-dIXiM"-4
79.44:7.8
89 088
48.228:4.11
GCN-IDGM'-S
73.884995
85.3824.95
33. 12:.1222.2
48 63:9.11
GCN-DDGM*-HI
78.89
88 00:000
34.38=1.0
48 33:14.14
GCN-DDGM-SSS
13.80.8.42
74.86115.03
26.00022.3
GON-IDGM -HH
81 77
86.87
34. 11
47.58
GCN-IDGM* -ES
81.11
11.00
35. 36-
47. 19
GUN-IDGGM"
06
GCN-IDGM*-BND
81.11:5.00
33, 19:11
44.27
GCN.JDGM--ED
79.44
89.3 89.33 1.00
34.17.2.33
47.581455
GON-IDGM-EE
60.56+8..0
40.67+10.4
GCN-JDGM-II
28.89
72.00
29. 20.50
44.01
GCN-IDGM-S
59. 102842
02.66 12.
30 58.2 34
45. 1652.30
GON-IDGM-HI
15.22
10.00
30.29.1.r
1..1
GON-IDGMM-SS
49.33+1 90
30 30.16=2-44 40
45,29 15,
GCN BON--DGM-BB EH
62. 78:
65 35
30 30.00:2.00 38
13.09:1.42
GCN aDGM-ES
60.5611803
05
30 10.34
45.6812.00
GCN JDGM-II
57.78
72.00:3.22
30.06:2..6
GCN LIGM-EHH
17.77
44.80 44.80110:55
28. 46
41.01 17:1
GON-IDGM-EESS
58 68.88-27.5
76 26
30.27::2.6
41,15e9.54
MLP
77.78
85.30
30.44:2.55
40.35
GUN
41.664/1.79
47.20-1976
24.19 24.19:9950
32.56s3.0
Table 18: Results for OGB-Arxiv dataset using GATv2 diffusion layers and different latent graph inference modules.
OGB-Arxiv
169,343
Features
128
Edges
1,166.243
Classes
20
Model
Accuracy (%) : Standard Deviation
GADV--IDGM'.E
64.3410.to
GAIV2-DDGM*- -H
61.3040
GATV2-DDGM* SS
64.41 10.41
GAIV2-IDGM*-HH
64.2440.17
GATV2-IDGM"-S
61.0529.20
GATv2.dDGM*..D -EH
64-08111.0
GAIV2-IDGGM
GAIV2-DDGGM-HHS
64.4510.12
LATv2-IDGM--EBR
65.06-0.09
GATv2-IDGM-E
64.66 64.65_o.01
GAI---IDGMMH
05.05::011
GATv2-IDGM--S
61.029..00
GAT-2-IDGM-H
64, 51.0040..0
GAT dDGM-M
61.35g0.36
GAT JDGM-EH
64.0010.76
GAT V2--IDMM-ES
64.3750.04
GATV2-IDGGM-H
61.00:1.00
GATV2-IDGM-EHS
61.25+0.50
MLP*
63.4010.15
GATv2
27

---

Published as a conference paper at ICLR 2023
Table 19: Results for OGB-Products dataset using GATv2 diffusion layers and different latent graph inference modules.
OGB-Products
Nodes
2,449,029
Edges
61,859.140
Classes
47
Accuracy (%) Standard Deviation
GAIV2-DDEM--
66. 00.30
GAIV2-dDDGM-H
02.22_.625
GATV2-DDGM-EH
06.51=030
GATY2-DDGM-E
66, 06.25
GAIV2-dDXGM-H
GATV2-IDGM-EH
MLP
NIA
:0.20
GAT-2
NIA
62 02.02=2.00
E.6 INDUCTIVE LEARNING: RESULTS FOR THE QM9 AND ALCHEMY DATASETS
The datasets discussed in the main task were solely concerned with tranductive learning. For com- pleteness, we show that the latent graph inference system based on product manifolds is also ap- plicable to inductive learning. Molecules are naturally represented as graphs, with atoms as nodes and bonds as edges. Prediction of molecular properties is a popular application of GNNs in chem- istry Wiieder et al. (2020): Stark et al. (202)): Li et al. (202T); Godwin et al. (2021): 13 Zhang et al. (2021). Specifically, we work with the QM9 (Ramakrishnan et al. (2014); Ruddigkeit et al. (2012)) and Alchemy (Morris et al. (2020) datasets which are well known in the Geometric Deep Learning literature. Table[2)]isppaay the results. These tasks are substantially different to the ones previously discussed because they involve inductive learning and regression, whereas before all tasks focused on transductive learning and multi-class classification.
Table 20: Results for the QM9 and Alchemy datasets using the dDGM module.
QMO
Alcbme
Tuges
A
(=100) Standar
CON-DDGNT-E E
90.25
$6.11
GCN LEN-DD-NT- H
07.501
00.
22N-00653--55 -55
GEN-000330
07 78:
52
94033335
JDGM" EHS
06.751155
CCN 4DGME
07.79 1.34
56.10
06.0911.35
GCN 41N-816
W5.5g:
96
GEN-IIGSSS
95-1527337
50
06.00 06.0111
GCS JDGM
06.5111.3
56,20
OCN JEN.IGM..ER ERS
07 07:00.11.0
50.00:211
92.2013.0
56.16
F LATENT GRAPH LEARNING PLOTS
In this appendix include additional plots for the learned latent graphs for the heterophilic datasets discussed in the main text as well as for the TadPole and the Aerothermodynamics dataset.
F.1 LEARNED LATENT GRAPHI FOR HETEROPHILIC DATASETS
we display the original graphs provided by the heterophilic datasets, and compare them to the latent graphs generated by the dDGM modules. From the plots we can clearly see the high homophily levels of the Texas latent graph in Figure for which obtain four distinct clusters. In the case the bigger datasets in Figure and the algorithm is still able to create clusters but there is mixing between classes.
In Figure 5 6 7 and 8
28

---

Published as a conference paper at ICLR 2023
(a) Original graph, 0.11.
(h) Learndd latent graph, 0.93.
Figure 5: Texas, original learned latent graph. The learned latent graph displayed learned using the GCN-dDGM model with k 2 in the Gumbel Top-k trick.
(a) Original graph, h 0.21.
(b) Learned latent graph, h 0.64.
Figure Wisconsin, original vs learned latent graph. The learned latent graph displayed was learned using the GCN-dDGM* -EHS model with & = 10 in the Gumbel Top-k trick.
(a) Original graph, 0.22.
(b) Learned latent graph, h 0.32.
Figure 7:
Squirrel, original vs learned latent graph. The learned latent graph displayed was learned using the GCN-dDGM*-S model with & = in the Gumbel Top-k trick. Note that both graphs (a) and (b) have the same number of nodes, but in (a) nodes are displayed more closely packed due to connectivity structure of the graph.
(a) Original graph. h 0.23.
(b) Learned latent graph, h 0.42.
Figure 8: Chameleon, original vs learned latent graph. The learned latent graph displayed was learned using the GCN-IDGM* model with & = in the Gumbel Top-k trick. Note that both graphs (a) and (b) have the same number of nodes, but in (a) nodes are displayed more closely packed due to the connectivity structure of the graph.
29

---

Published as a conference paper at ICLR 2023
Note that the generated latent graphs are dependent both the downstream task and the diffusion layers we are using, that is, the GCNs. Since we have created a fully- dullydiiffreeniabll system the models are optimizing the latent graph generation together with the rest of the model parameters. Hence, if we were to change the downstream task or the diffusion layers we would expect different latent graphs.
In Figure 2 from Section we showed the latent graph learning evolution plots as a function of training epochs for the Texas dataset. We provide additional plots for other datasets. This shows that the latent graph inference system is applicable across a wide range of datasets and that is learns organize the connectivity of the latent graph during training.
(a) Epoch 1, h 0.34.
(b) Epoch 5, h = 0.43.
(c) Epoch 10, h 0.46.
(d) Epoch 100, / 0.52.
(e) Epoch 500, h 0.62.
(f) Epoch 1000. / 0.64.
Figure 9: Latent graph homophily level, h evolution as a function of training epochs for Wisconsin. The latent graphs are produced during the training process for the GCN-dDGM*-EII model with k == 10.
(a) Epoch 1, h 0.20. (b) Epoch 100, f 0.26. (c) Epoch 500, 1t = 0.31. (d) Epoch 1000, à 0.32.
Figure 10: Latent graph homophily level, h, evolution as a function training epochs for Squirrel using the GCN-dDGM* -S model with & 3. Recall that each node in the graph is represented with a point and each class is assigned a different color. In (a) there no structure, after 1,000 epochs in (d) the algorithm has been able to organize the graph structure separate some of the classes, but there is still a substantial amount of mixing.
(a) Epoch 1, h 0.19. (b) Epoch 100, h 0.36. (c) Epoch 500, h 0.40. (d) Epoch 1000, h 0.12.
Figure 11: Latent graph homophily level, h, evolution as function of training epochs for Chameleon using the GCN-dDGM*.ES model with ht =
30

---

Published as a conference paper at ICLR 2023
Lastly, we display the learned latent graphs using original heterophilic graph inductive bias for both the Texas and Wisconsin datasets. In Figure [2 and Figure [3] we compare the final inferred latent graphs for the datasets when the original heterophilic dataset graph is used inductive bias, against starting from pointeloud. Models that use the dDGM module, which makes use of the original graph, are not able achieve high homophily levels compared to those using the dDGM* module and ignoring the original graph. This explains the difference in performance in Table 17 from Appendix E.4
(a) 0.93.
(b) /1 0.60.
Figure 12: Comparison of final inferred latent graph (after 1,000 epochs of training) for the Texas dataset by (a) the GCN-dDGM*-E and (b) the GCN-dDGM-E model, both with k = 2.
0.65.
(b) h 0.36.
Figure 13:
Comparison of final inferred latent graph (after 1,000 epochs of training) for the Wiscon- sin dataset by (a) the GCN-IDGM**EERS and (b) the GCN-dDGM-EHS model, both with k 10.
F.2 LEARNED LATENT GRAPHS REAL-WOOT WORLD DATASETS
Next we displayed the learned latent graph for the TadPole and the Aerothermodynamics datasets, see Figure 14 Figure Figure 16 and Figure 17
G MODEL. ARCHITECTURES
For reproducibility, in this appendix include summary of all the models used to obtain the results discussed in this paper. This includes the GNN network archictectures as well as the internal structure of the dDGM modules.
G.1 NETWORK ARCIITECTURES
In this section we provide the neural network architectures used for the experimental validation as well as other training specifications.
G.1.1 NETWORKS FOR CLASSICAL. GRAPH DATASETS
All neural network models used for homophilic graph datasets, MLP, GCN, and GCN-dDGMs, follow the architecture depicted in Table 21 We apply a learning rate of ir 10 2 and a weight decay of udd 10-1, Models trained for about 1,500 epochs.
31

---

Published as a conference paper at ICLR 2023
(a) Epoch 1, 0.44.
(b) Epoch 5, 0.42.
(c) Epoch 0.46.
(d) Epoch 100, / 0.72.
(c) Epoch 400, h 0.88.
(f) Epoch 800, h 0.92.
Figure 14: Latent graph homophily level, h, evolution as a function of training epochs for TadPole. The latent graphs shown here were obtain using the GCN-dDGM model with k 3.
(a) Epoch 1, h 0.43. (b) Epoch 10, h 0.46. (c) Epoch 100, h = 0.65. (d) Epoch 800, h 0.90.
Figure 15: Latent graph homophily level, h, evolution as a function of training epochs for TadPole obtained using the GCN-dDGM*-ERL model with k 7. Nodes with different colors correspond to different target classes. Starting from a unstructured graph in (a), the algorithm is able to generate highly homophilic graph after 800 epochs in (d).
M
(a) Epoch 1, h 0.35. (b) Epoch 10, h 0.87. (c) Epoch 500, h 0.86. (d) Epoch 1000, à 0.88.
Figure 16: Latent graph homophily level, h, evolution as function of training epochs for Aerother- modynamics. The latent graphs shown here were obtain using the GAT-dDGM** -HHH model with k= 7.
Epach 1, 0.85. (b) Epoch 10, h 0.79. (c) Epech 500, h 0.84. (d) Epoch 1000. h 0.87.
Figure 17: Latent graph homophily level, ht evolution as function of training epochs for Aerother- modynamics. The latent graphs shown here were obtain using the GAT-dDGM model with k= == 7.
32

---

Published as a conference paper at ICLR 2023
Table 21: Summary of model architectures for experiments using classical graph datasets. Most experiments only use the first dDGM module.
Model
GCN
GCN-dDGM
No. Layer parameters
Activation
Layer type
NIA
N/A
dDGM
(No. features,
HLU
Graph Conv
Graphi Conv
NIA
N/A
dDGM
(32, 16)
ELU
Cincar
Graphi Coiv
Graph Conv
NIA
N/A
dDGM
(16, 35
ELU
Lineur
Graphi Conv
Graph Conv
(8. 8)
ELU
Linear
Lincar
Linear
(8, 8)
ELU
Lincar
Lincar
Lincar
(8. No. classes)
Linear
Lincar
Linear
G.1.2 NETWORKS FOR HETEROPHILIC GRAPH DATASETS
The networks used for heterophilic datasets follow the architecture summarized in Table 22 apply Ir = 10-2 and wd = 10-3, and we train the models for about 1,000 epochs.
We
Table 22:
Summary of model architectures for experiments using heterophilic graph datasets. The dDGM module uses different & values.
Model
MLP
GCN
GCN-dDGM
No. Layer purameters
BatchNorm
Activation
Layer type
N/A
N/A
dDGM
(No. features, 16)
No
ELU
Linear
Graph Conv
Graph Conv
(16, 8)
No
ELU
Lincar
Graph Conv
Gruph Conv
(8, 8)
Yes
ELU
Linear
Linear
Linear
(8, No. classes)
No
Lincar
Lincar
Linear
G.1.3 NETWORKS FOR OGB-ARXIV
Table 23 shows the networks used for the OGB-Arxiv dataset. We use ir = 10 wd = 0, and train for 100 epochs. For graph subsampling, sample up to 1,000 neighbours per node and use a batch size of 1,000.
Table 23: Summary of model architectures for experiments the OGB-Arxiv dataset using GATv2 diffusion layers. As specified in the table, k 20 is used for all experiments.
Model
MLP
GATv2
GATY2-DDGM
Layer parameters
BatchNorm
Activation
Layer type
N/A
N/A
dDGM
(No. features 128, 40)
No
SiLU
Linear
Graph Attention v2
Graph Attention
(40, 40)
No
SiLU
Lineur
Graph Atlention v2
Graph Atlention v2
(40. 40)
No
SiLU
Lineur
Graph Attention v2
Graph Attention v2
(40. 40)
Yes
SiLU
Linear
Linear
Linear
(40, 100)
Yes
SiLU
Lineur
Linear
Linear
(100, No. classes 40)
No
Lineur
Linear
Linear
1.4.4 NETWORKS FOR
Table 24 shows the networks used for the OGB-Produce dataset. We use br - wd 0. and train for 30 epochs. For graph subsampling, we sample up to 200 neighbors per node and use a batch size of 1,000.
33

---

Published as a conference paper at ICLR 2023
Table 24: Summary of model architectures for experiments for the OGB-Products dataset using
GATv2 diffusion layers, with l: = 3 for the dDGM module.
Model
MLP
GATv2
GATv2-DDGM
No. Layer parameters
BatchNorm
Activation
Layer type
N/A
N/A
dDGM 3)
(No. features = 100, 100)
No
SILU
Linčar
Graph Atteation v2
Graph Aitention V2
(100, 100)
No
SILU
Lincar
Graph Attention v2
Graph Attention v2
(100, 47)
No
SILU
Linear
Graph Attention
Graph Attention v2
(47, classes 47)
No
Lincar
Lincar
Lincar
G.1.5 NETWORKS FOR INDUCTIVE LEARNING
Table 25 summarizes the networks used for the QM9 and Alchemy datasets. We use ir 5 10 wd 3 and train for 30 to 60 epochs.
Table 25: Summary of model architectures for experiments for the QM9 and Alchemy datasets. These models incorporate global mean pool layer since predictions are at the graph level, rather than at the node level as in all other datasets.
Model
ML.P
GCN
GCN-dDGM
No. Layer parameters
BatchNorm
Activation
Laycr type
N/A
N/A
dDGM
(No. features, 20)
Yes (GraphNorm))
SiLU
Linear
Graph Conv"
Graph Conv
(20, 20)
Yes (GraphNorm)
SiLU
Linear
Graph Conv
Graph Conv
Global Mean Pool
(20,20) (20, 20)
No
SICU
Linear
Linear
Linear
SIL.U
Linear
Linear
Linear
(20, No. prediction targets)
No
Linear
Linear
Linear
G.1.6
NETWORKS FOR BRAIN IMAGING
Table 26
summarizes the networks used for the TadPole dataset. We use Ir 10-3 and wd
2 x 10 and train for about 800 epochs.
Table 26: Summary of model architectures for TadPole.
Model
MLP
GCN-dDGM
GAT-dDGM
No. Layer parameters
BatchNorm
Activation
Layer type
N/A
dDGM
dDGM
(No. features, 32)
No
ELU
Linear
Graph Conv
Graph Attention
(32, 16)
No
ELU
Linear
Graph Conv
Graph Attention
(16, 8)
No
ELU
Linear
Graph Cony
Graph Attention
(8, 8)
Yes
ELU
Linear
Linear
Linear
(8, 8)
Yes
ELU
Linear
Linear
Lincar
(8, No. classes)
No
Linear
Linear
Lincar
G.1.7 NETWORKS FOR AEROSPACE ENGINEERING
Table 27 summarizes the networks used for the Acrothermodynamics dataset. We use 1
and vd 0, and train for about 1 1,000 epochs.
34

---

Published as a conference paper at ICLR 2023
Table 27: Summary of model architectures for Aerothermoodynmiic.
Model
MLP
GCN-dDGM
GAT-dDGM
No. Layer parameters
BatchNorm
Activation
Layer type
N/A
dDGM
dDGM
(No. features, 32)
No
ELU
Linear
Graph Conv
Graph Attention
(32, 16)
No
ELU
Linear
Graph Conv
Graph Attention
(16,
Linear
Graph Conv
Graph Attention
(8, 8)
ELU
Linear
Linear
Linear
(8, 8)
Linear
Linear
Linear
(8, No. classes)
Linear
Linear
Linear
G.2 DDGM ARCHITECTURES
The dDGM and dDGM* internal parameterized mapping functions are slightly modified for differ- ent datasets. All architectures are recorded Table 28
29
30
31
32
33
and 34
Table 28: dDGM* and dDGM architectures for classical homophilic datasets.
dDGM
dDGM
No. Layer parameters
Activation
Layer type
(No. features, 32)
ELU
Linear
Linear
(32, 16 per model space)
ELU
Linear
Graph Conv
(16 per model space, 4 per model space)
Sigmoid
Linear
Graph Conv
Table 29: dDGM* and dDGM architectures for heterophilic datasets.
dDGM
dDGM
Layer parameters
BatchNorm
Activation
Layer type
(No. features, 32) (32, 4 per model space)
Yes
ELU
Linear
Linear
Yes (dDGM" Y No (dDGM) Yes (dDGM*) (dDGM)
ELU
Linear
Graph Conv
(4 per model space, per model space)
Sigmoid
Linear
Graph Conv
Table 30: dDGM and dDGM architectures for OGB-Arxiv.
dDGM
dDGM
No. Layer parameters
BatchNorn Yes
Activation
Layer type
(No. features, 40)
SiLU
Linear
Lincur
(40. 32 model space)
Yes (JDGM*) No (dDGM) Yes (dDGM" No (JDGM)
SiLU
Linear
Graph Conv
(32 per model space, 16 per model space)
SILU
Lincar
Graph Conv
Table 31: dDGM* and dDGM architectures for Produuuus
dDGM
dDGM
No. Layer parameters (No. features, 32 per model space) (32 per model spuce, per model space)
BatchNorm
Activation SiLU SILU
Layer type
Yes (dDGM"" No (dDGM) Yes (dDGM*M (dDGM)
Linear
Graph Conv
Linear
Graph Conv
Table 32: dDGM* and dDGM architectures for QM9 and Alchemy.
dDGM
dDGM
No. Layer parameters (No. features, 3 per model space) per model space, per model space)
BatchNorm
Activation
Layer type
Yes Yes
SILU
Linear
Graph Conv
SILU
Lincar
Graph Conv
35

---

Published as a conference paper at ICLR 2023
Table 33: dDGM* and dDGM architectures for TadPole.
dDGM
dDGM
No. Loyer parmmeters features, model space) spice, per space)
HoschiNocm
Activation
Layer
Yes IdDGM*y (dDGM) (IDGGM No (IDGM))
ELU Sigmoid (IDGM" (IDGM)
Lineu
Cony
Table 34: dDGM* R and dDGM architectures for Acrothermodynamics..
dDGMP
JDGM
No. Layer porandur
BackdNun No
Autiooiio
Layer
(Ao Iosuno, 321
E.D
Linse
Liaz
(32, 16 per model space)
Yos IDDUM No (dDGM) Yos WDDGM No (IDGMM)
BLU
Linear
Graph Coty
(10 per model spoce 4 per model specn)
Sigmovd (IDUM" BLU (DDMM)
Linex
Graph Cory
36


Reviews:
[{"review_id": "y6974tEc5W", "reviewer": "Reviewer_vGZV", "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 generalizes discrete Differentiable Graph Module (dDGM) to learn latent graphs in the product space of Euclidean planes, hyperboloids and hyperspheres of constant curvature. The learned graphs are then used for graph neural networks. Experiments are done on heterophilic and homophilic datasets, as well as some real-world data without a graph given as a prior.", "summary_of_the_review": "It's an interesting approach to latent graph learning that builds on prior work on differentiable Riemannian manifolds. The experimental results are promising.", "strength_and_weaknesses": "Strength: Modeling data points on different manifolds to embed more complicated relationship information into the graph is an interesting idea, and seems to work well for experiments with heterophilic datasets. Visualization of latent graph evolution in Figure 2 is intriguing. \n\nWeakness: Notations used in section 3.1. can be hard to understand. In section 4.2., if the data doesn't come with a graph and are just pointclouds, why would one decide to use GNNs in the first place?", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "rYvg518qSG", "reviewer": "Reviewer_R63Y", "summary": "", "questions": "", "limitations": "", "rating": 5, "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 aims to address the latent graph inference problem, i.e., inferring the intrinsic graph structure from point cloud-like data where connection is not available in the original data. Based on the discrete Differentiable Graph Module (dDGM) proposed by previous work, this paper extends dDGM with Riemannian geometry by calculating distance (which is used for edge modelling) in not only Euclidean space but also hyperboloid/hypersphere spaces. Extensive experiments are conducted to show the effectiveness of the proposed method.", "summary_of_the_review": "Clarity/Quality:\n\nAs is discussed in S2, the paper has good clarity and quality. In specific, the research problem and proposed method is well formulated. The paper is well written.\n\nNovelty:\n\nAs is discussed in W1, the novelty of this paper is limited. In specific, compared to the basic model dDGM, the technical improvement of the proposed method is relevantly minor. \n\nReproducibility:\n\nThis paper has great reproducibility. The experimental details are described. The source code is not provided.", "strength_and_weaknesses": "### Strengths:\n\nS1: A great number of experiments are conducted. \nThe authors conduct the experiments on various of datasets, including homophilic, heterophilic, and real-world application-based datasets. Visualization experiments are also used to exhibit the quality of the learned graph structure.\n\nS2: The paper is well presented and written.\nThe definitions and notations in the paper are explicit. The proposed method is clearly described. The paper is written in good quality.\n\n### Weaknesses:\n\nW1: The novelty of this paper is limited.\nAs is described by the authors, the proposed method is based on dDGM (Kazi et al. 2022). The main difference between dDGM and the proposed method is that, dDGM mainly learns on Euclidean, while the proposed method learns on both Euclidean and other non-constant curvature spaces. However, in Section 5.1.2 and Table 3 of paper (Kazi et al. 2022), this paper already discusses the potential of applying dDGM to non-Euclidean geometry latent space and conducts an experiment on Hyperbolic space. Such a previous discussion makes the contribution of this paper less significant. In this case, the authors are suggested to better clarify the novelty and contribution of this paper. \n\nW2: Some critical related works lack in the literature review.\nThis paper focuses on learning latent graph structure from raw data, which is described as “the latent graph inference problem” in this paper. However, in the community of GNNs, there is a branch of works aims to address “graph structure learning problem” which has a consistent learning target with this paper. In this case, it’s of great significance to review the related papers about graph structure learning and discuss the similarity/difference between the proposed method and these works. For this topic, the authors are suggested to refer recent survey [1] and some classic methods (e.g., LDS-GNN [2], IDGL [3], and ProGNN [4]). \n\n[1] Zhu, Yanqiao, et al. \"Deep graph structure learning for robust representations: A survey.\" arXiv preprint arXiv:2103.03036 (2021).\n\n[2] Franceschi, Luca, et al. \"Learning discrete structures for graph neural networks.\" International conference on machine learning. PMLR, 2019.\n\n[3] Chen, Yu, Lingfei Wu, and Mohammed Zaki. \"Iterative deep graph learning for graph neural networks: Better and robust node embeddings.\" Advances in neural information processing systems 33 (2020): 19314-19326.\n\n[4] Jin, Wei, et al. \"Graph structure learning for robust graph neural networks.\" Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining. 2020. \n\nW3: The experiments seriously lack baselines for comparison.\nIn the experiments, the proposed method is only compared to MLP and GCN, making the results not convincing enough. Readers may be curious about how the proposed method performs compared to state-of-the-art methods. At least, the authors should add the original dDGM for comparison (is that equal to GCN-dDGM-E?). Moreover, some representative reviewed methods (e.g., DGCNN and DGMs) and the graph structure learning methods (listed in W2) should also be considered.\n", "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": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "Ug_EBcDRFbi", "reviewer": "Reviewer_DMwU", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "In this paper, the authors proposed to generalize the discrete Differentiable Graph Module (dDGM) for latent graph learning, by incorporating the Riemannian geometry into the model and generating more complex embedding spaces. The authors further propose a computationally tractable approach to produce product manifolds of constant curvature model spaces that can encode latent features of varying structures. The numerical results demonstrate that the proposed method outperforms the original dDGM model.\n\n\n", "summary_of_the_review": "The authors present a new method to generalize the discrete differentiable graph module for learning latent graphs, which could be interesting to people working on graph neural networks. Such a method could provide a way to learn a better graph topology, which helps to improve the performance of graph neural networks in the downstream task. One concern to be solved is the scalability of the proposed method.", "strength_and_weaknesses": "Strength:\n\n1. The authors provide a novel method to generalize the discrete differentiable graph module for learning latent graphs.\n\n2. It is interesting to incorporate Riemannian geometry into the model to generate more complex embedding spaces. The resultant performance is improved. \n\nWeakness:\n\n1. It is unknown the scalability of the proposed method.\n\n", "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": "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": {}}]

Author rebuttal:

Decision: Accept: poster