Learning Graph Neural Network Topologies
Authors: Avishkar Saha
Oscar Mendez Maldonado
Chris Russell
Richard Bowden
Venue: Submitted to ICLR 2023 (2023)

Abstract: Graph convolutional networks (GCNs) enable end-to-end learning on graph structured data. However, many works begin by assuming a given graph structure. As the ideal graph structure is often unknown, this limits applicability. To address this, we present a novel end-to-end differentiable graph-generator which builds the graph topology on the fly. Our module can be readily integrated into existing pipelines involving graph convolution operations, replacing the predetermined or existing adjacency matrix with one that is learned, and optimised, as part of the general objective. As such it is applicable to any GCN. We show that integrating our module into both node classification and trajectory prediction pipelines improves accuracy across a range of datasets and backbones.

Under review as a conference paper at ICLR 2023
LEARNING GRAPH TOPOLOGIES
NEURAL
NETWORK
Anonymous authors Paper under double-blind review
ABSTRACT
Graph convolutional networks (GCNs) enable end-to-end learning on graph struc- tured data. However, many works begin by assuming given graph structure. As the ideal graph structure is often unknown, this limits applicability. To address this, we present novel end-to-end differentiable graph-generator which builds the graph topology on the fly. Our module can be readily integrated into existing pipelines involving graph convolution operations, replacing the predetermined or existing adjacency matrix with one that is learned, and optimised, as part of the general objective. As such it is applicable to any GCN. We show that integrating our module into both node classification and trajectory prediction pipelines improves accuracy across range of datasets and backbones.
INTRODUCTION
The success of Graph Neural Networks (GNNs) (Duvenaud al. 2015 Bronstein et al. 2017 Monti ct al. 2017). has led to surge in the use of graph-based representation learning. GNNs provide an efficient framework to learn from graph-structured data, making them widely applicable in any domain where data can be represented as a relation or interaction system. They have been successfully applied in wide range of tasks including particle physics (Choma et al., (208)), protein science (Gainza al. 2020) and many others (Monti et al.) 2019), (Stokes et al. 2020))
In GNN, each node iteratively updates its state by interacting with its neighbors, typically through message passing. However, fundamental limitation of such architectures is the assumption that the underlying graph provided. While node or edge features may updated during message passing, the graph topology remains fixed, and its choice may be suboptimal for various reasons. For instance, when classifying nodes on a citation network, an edge connecting nodes of different classes diminish classification accuracy. These edges can degrade performance by causing irrelevant information to be propagated across the graph. When no graph is explicitly provided, one common practice to generate k-nearest neighbor (k-NN) graph. In such cases, k hyperparameter and tuned to find the model with the best performance. For many applications, fixing A: is overly restrictive as the optimal choice of k may vary for each node in the graph. While there has been an emergence of approaches which learn the graph structure for use in downstream GNNs (Zheng et al. 2020 Kazi al. 2020 Kipf al. 2018), all of them treat the node degree
fixed hyperparameter.
We propose a general differentiable graph-generator (DGG) module for learning graph topology with or without an initial edge structure. This module can be placed within any graph convolutional network, and jointly optimized with the rest of the network's 's parameters, learning topologies which favor the downstream task without hyperparameter selection or indeed any additional training signal. The primary contributions of this paper are as follows:
1.
We propose novel, differentiable rraph-generator (DGG) module which jointly optimizes both the neighbourhood size, and the edges that should belong to each neighbourhood. Note that existing approaches (Zheng et al. 2020: Kipf et al.) 2018 Kazi et al.) 2020) do not allow for learnable neighbourhood sizes.
Our DGG module is directly integrable into any pipeline involving graph convolutions, where either the given adjacency matrix is noisy, is not explicitly provided and must be determined heuristically. In both cases, our DGG generates the adjacency matrix as part of the GNN training and can be trained end-to-end optimize performance the downstream task. Should good graph structure be known, the generated adjacency matrix can be learned to remain close to while optimizing performance.

---

Under review as a conference paper at ICLR 2023
3. To demonstrate the power of the approach, we integrate DGG within range of SOTA pipelines without modification - across different datasets in trajectory prediction and node classification and demonstrate improvements in model accuracy.
2 RELATED WORK
Graph Representation Learning: GNNs (Bronstein al. 2017) provide powerful class of neural architectures for modelling data which can be represented as set of nodes and relations (edges), Most use message-passing to build node representations by aggregating neighborhood information. common formulation is the Graph Convolution Network (GCNs) which generalizes the convolution operation to graphs (Kipf & Welling 2017; Defferrard et al. 2016; Wu et al., 2018: Hammiton et al. 2017). More recently, the Graph Attention Network (GAT) (Veličković et al., 2018)) utilizes self-attention mechanism to aggregate neighborhood information. However, these works assumed that the underlying graph structure is predetermined, with the graph convolutions learning features that describe preexisting nodes and edges. In contrast, we simultaneously learn the graph structure while using our generated adjacency matrix in downstream graph convolutions. The generated graph topology of our module is jointly optimized alongside other network parameters with feedback signals from the downstream task.
Graph Structure Learning: In many applications, the optimal graph is unknown, and a graph is constructed before training a GNN. One question to ask is: "Why isn't 't fully-comnected graph suitable?" Constructing adjacency matrices weighted by distance or even an attention mechanism (Veličković et al., 2018) over a fully-connected graph incorporates many task-irrelevant edges, even their weights are small. While an attention mechanism can zero these out - i.e., discover subgraph within the complete graph- - discovering this subgraph is challenging given the combinatorial complexity of graphs. A common remedy is to sparsify complete graph by selecting the k-nearest neighbors (A-NN), Although this can prevent the propagation of irrelevant information between nodes, the topology of the constructed graph may have relation to the downstream task. Not only can irrelevant edges still exist, but pairs of relevant nodes may remain unconnected and can lead GCNs to learn representations with poor generalization (Zheng al. 2020).
This limitation has led to works which learn a graph's 's structure within a deep learning framework. Some methods (Shi et al. 2019 Liu et al. 2020) take fixed adjacency matrix input and then learn a residual mask over it. Since these methods directly optimize the residual adjacency by treating each element as a learnable parameter, the learned adjacency matrix is not linked to the representation space and only works in tasks where the training nodes are the same as that at test time. To overcome this, recent approaches (Zheng et al. 2020; Kipf et al. 2018 Luo et al. 2021 Kazi et al. 2020) generate graph structure by sampling from discrete distributions. As discrete sampling is not directly optimizable using gradient descent, these methods use the Gumbel--Sfttaa reparameterization trick (Jang et al.] (016) to generate differentiable graph samples. The Gumbel-Softman approximates an argmax over the edges for each node, and sampling in these approaches is typically performed times to obtain the top-k edges. Here, k is specified hyperparameter that controls the node degree for the entire graph/dataset. Unlike these works, we generate edge samples by selecting the top-k in a differentiable manner, where we learn distribution over the edges and over the node degree k. This allows the neighborhood and its size to be individually selected for each node. Additionally, a known 'ideal' graph structure can be used intermediate supervision further constrain the latent space.
3 METHOD
In this section, we provide details of our differentiable graph generation (DGG) module. We begin with notation and the statistical learning framework guiding its design, before describing the module, and how it is combined with graph convolutional backbone architectures.
We represent a graph of N nodes as G (V, F): where V is the set of nodes or vertices, and E the edge set. A graph's 's structure can be described by its adjacency matrix A, with ag = 1 an edge connects nodes and j and a.j- 0 otherwise. This binary adjacency matrix A is directed, and potentially asymmetrical.
Notation
Problem definition. We reformulate the baseline prediction task based a fixed graph with an adaptive variant where the graph is learned. Typically, such baseline tasks make learned predictions y given set of input features X and a graph structure A of node degree k:
Y Qx(X) A),
2

---

Under review as a conference paper at ICLR 2023
TYPICAL PREDICTION TASK
OUR REFORMULATION
Y
Q)(X,A)
P(Y (10A
X
(X)
Y
X
(x(x,4) -Y
k-
A
A
KEY
Differentiable pathway
Qa(k(x)
Qu(A[X,A)
differentiable
Non-diferentiable
Figure 1: (Left) typical prediction task using graphs Y Co(X, A) where and k are prede- termined. (Right) Our reformulation P(Y = ExEx Qo (X, ()), which learns a distribution over and l alongside the downstream task.
where Qs is an end-to-end neural network parameterized by learnable weights c. These formulations require predetermined graph-structure A, typically based on choice of node degree k, and take A as additional input to the model. In contrast, we learn both A and in an end-to-end manner, and use them to make predictions Y. As graphs inherently binary, with edges either present absent, they are not directly optimizable using gradient descent. Instead, we consider distribution of graphs, G, which then induce distribution of labels, V, in the downstream task. This distribution takes the factorized form:
P(Y Σ Σ E (O(XX,)))(AX
AEG KENIVI
where P(k|X) is the distribution of node degree k given X (i.e., the choice of k in K-NN), P(A k) the distribution of graph structures A conditioned on the learned h and input X, and P(Y the downstream distribution of labels conditioned on data X. For clarity, the adjacency A represents subgraph of a complete graph over X, and a multidimensional variable controlling the number of top-k neighbors for each node individually. To avoid learning individual probabilities for each possible graph A in an exponential state space, we further assume that P(A k) has a factorized distribution where each neighborhood is sampled independently, i.c. P(A[X, k) Ilev P(a,|X, k).
We approximate the distributions over adjacencies A and with tractable functions:
P(YIX) R ΣΣ E (0A
where Qa and Qo are functions parameterized by and to approximate P(A k) and P(].X), respectively. In Fig. I. we illustrate the functions of our method compared to the typical prediction task in Eq. [
Using this formulation, we train the entire system end-to-end to minimize the expected loss when sampling Y. This can be efficiently performed using stochastic gradient descent. In the forward pass, we first sample a subgraph/set of nodes X from the space of datapoints, and conditioning on X sample A and compute the associated label Y. When computing the gradient step, update Qx(X, A) as normal and update the distributions using two standard reparametrization tricks: one for discrete variables (Jang et al., 2016) such that Qa( AA|., X, k) can generate differentiable graph samples A', and another for continuous variables (Kingma & Welling 2013) of drawn from (k (X):
P(YIX) EEQo(X,A)) where A' Qa(A[X, and k (x(X)).
A' K'
As both the graph structure A' and variable k' samplers differentiable, DGG module can be readily integrated into pipelines involving graph convolutions and jointly trained end-to-end.
3.1 DIFFERENTIABLE GRAPH GENERATION Our differentiable graph-generator (DGG) takes a set of nodes V = (V1, ..., UN with d-dimensional features X Ie N x and generates asymmetric adjacency matrix A R This adjacency matrix can be used directly in any downstream graph convolution operation (see Module Instatiation below). As illustrated by Fig. 2 the DGG module consists of four components:
1. Encoder: this component projects the input node features X R to latent representation
X Nxd and forms the primary representation space for the model.
3

---

Under review as a conference paper at ICLR 2023
X
MATTER
A
civ (1
8
8
DEFE TOP- SELOCTOR
Qo (E
Gumbel(0,
Our differentiable graph-generator (DGG) takes input nodes X and generates an adjacency matrix A. It consists of: (1) Degree-estimator: generates samples of k; for each node, (2) Edge- generates edge samples e; for each node and (3) Top-k selector: takes k; and edge samples e, and selects top-k elements in a differentiable manner to output a final adjacency A.
Figure 2:
ranker:
2. Edge ranking:
this takes the latent node features X E R N and generates a matrix representing stochastic ordering of edges E E NNN drawn from a learned distribution over the edge- probabilities (A' ~ (e k') from Eq.
Degree estimation: this component estimates the number of neighbors each individual node connected to. takes as input the latent node features X E R.Nxd' and generates random samples k E RN drawn from learned distribution over the node degree (k' ~ Qp (k(x) from Eq. 4 4. Differentiable top-k edge selector: takes i and the edge-samples e and performs a soft thresh- olding that probabilistically selects the most important elements, based on the output of the Edge-ranking to output an adjacency matrix A E NNN
We describe each component below.
Encoder. We construct single latent space from the input node features, and use it for edge ranking and degree estimation. We first map input node features X E RRN into latent features X E N using multi-layer perceptron (MLP) fo with weights &: X (X).. These latent features form the input for the rest of the module. Furthermore, they are output by the DGG and passed to the GCN downstream to prevent vanishing gradients.
Edge ranking. The edge ranking returns an implicit distribution of edge orderings, from which we sample the neighborhood for each node. For each node u, it draws a set of scores e, {eyy J quantifying its relevance to all nodes v, E V. including itself. To generate differentiable edge samples e,, we the Gumbel-Softmax (Jang al. 2016).
Without loss of generality, we focus on a single node v, E V, with latent features &, E Rd. We implement the approximation function (Al k)) of the Edge-ranker as follows:
1. Using latent node features x; E X, calculate pairwise edge probabilities pa E R between pairs of auxiliary node features (X,, x));
p = (exp(-1(c,)l)))) E N},
(5)
where č;₁ = x; x, is the difference between node features. Each element ptj P, represents a similarity measure between the latent features of node and uj. In practice, any distance measure can be used here, including learnable approaches.
2. Using Gumbel-Softman over the edge probabilities Ps R.N. we generate differentiable samples e, E R with Gumbel noise g: exp((log(pn)) + 9:) + Vj E J Gumbel 1)
}.9
e;
(6)
Σ, exp((log(re)) + si) +7)
where 7 a temperature hyperparameter controlling the interpolation between a discrete one-hot categorical distribution and continuous categorical density. When r -> 0, the edge energies Eij E e, approach a degenerate distribution. The temperature T is important for inducing sparsity, but given the exponential function, this results in single element in e, given much more weighting than the rest, i.e., it approaches a one-hot argmax over e; Instead, we want a variable number of edges to be given higher importance, and others to be close to zero. Hence, select higher temperature and use the top-k selection procedure (detailed below) to induce sparsity. This has the added benefit of avoiding the high-variance gradients induced by lower temperatures.
4

---

Under review as a conference paper at ICLR 2023
Degree estimation. A key limitation of existing graph generation methods (Kazi al. 2020 Kipf et al. 2018 Zheng et al. 2020) is their use of a fixed node degree across the entire graph. This can be suboptimal mentioned previously. In our approach, rather than fixing & for the entire graph, sample it per node from a learned distribution. Focusing on a single node as before, the approximation function (k) X) of the Degree-estimator works as follows:
1. We approximate the distribution of latent node features x; E Rd following the a VAE-like formulation (Kingma & Welling 2013). We encode its mean 14, R and variance o; E R' using two MLPs Mp and Sp, and then reparametrize with noise to obtain latent variable 2; E R4.
Mú M,(
2: = 14 t
(O,
2. Finally, we concatenate each latent variable E Rd with the Ll-norm of the edge samples h, = |eyl|la and decode it into a scalar k E R with another MLP Dp. representing a continuous relaxation of the neighborhood size for node 2y:
Dz(z; h.).
(8)
Since h, summation of node's edge probabilities, it can be understood as representing an initial estimate of the node degree which is then improved by combining with a second node representation z; based entirely on the node's features. Using the edge samples estimate the node degree links these representation spaces back to the primary latent space of node features X.
Top-k Edge-Selector. Having sampled edge weights, and node degrees k, this function selects the top-k edges for each node. The top-k operation, i.e. finding the indices corresponding to the largest elements a set of values, is a piecewise constant function and cannot be directly used in gradient-based optimization. Previous work (Xie et al. 2020) frames the top-k operation as an optimal transport problem, providing a smoothed top-k approximator. However, as their function is only defined for discrete values of I it cannot be optimized with gradient descent. As alternative that is differentiable with respect to k; we relax the discrete constraint on k, and instead use it to mooothed-Heaviiidee function (Fig. 3) For
control the æ-axis value of the inflection point node e2 E V, of smoothed degree kę E TR and edges e, E R.W. our Top-k Edge Selector outputs an adjacency vector a, R where the k largest elements from e, are close 1, and the rest close O.
Focusing on a single node U, as before, the implementation is as follows:
1. Draw ID input points d; {I,...,N N where N is the number of nodes in V.
2. Pass d, through hyperbolic tangent (tanh) which serves as smooth approximation of the Heaviside function:
h 0.5 (1 tanh(A -d-
here X >> 0 is a temperature parameter controlling the gradient of the function's 's inflection point.
As A + the smooth function approaches the Heaviside step function. The first-k values in h; = [hiyy) will now be closer to 1, while the rest closer to O.
3. Finally, for each node we sort its edge-energies e, = {eg 1 in descending order, multiply by
h; = {h 1/ and then restore the original order obtain the final adjacency vector a, {aiz Ij
Stacking a, over all nodes v2 V then creates the final adjacency matrix E RNN.
Straight through Top-k Edge Selector, To make our final adjacency matrix A E NxN discrete, we follow the trick used in the Thright-Through Gumbel Softmax (Jang et al. (016): we output the discretized version of in the forward pass and the continuous version in the backwards pass. For the discretized version in the forward pass, we simply replace the smooth-Heaviside function in Eq. with step function.
The DGG module can be easily combined with any graph convolution operation. A typical graph convolution (Kipf & Welling 2017) is defined as follows: X' = D 1/2 1- AD 1/2xe. Here, A = A + denotes the adjacency matrix with inserted self-loops, D its diagonal degree matrix and O its weights. To use this graph convolution with the DGG, we simply use our module generate the adjacency matrix A.
Module Instantiation:
5

---

Under review as a conference paper at ICLR 2023
MULE
AA
HOSTORE
a
SORT
Figure 3: The differentiable Top-k Edge Selector. This component the node degree k; output by the Degree Estimator to control the inflection point on a select the top edges from e, output by the Edge Ranker. This produces adjacency vector a; for each node, and stacking a; across all nodes produces the final adjacency matrix A.
function and uses it to
4 EXPERIMENTS
We evaluate our DGG on node classification and trajectory prediction tasks. We chose these tasks as the former has an input graph structure, while the latter does not, demonstrating the flexibility of our module. Furthermore, we integrate our module into variety of GCN baselines, not only for their state-of-the-ar (SOTA) performance, but as they all use different graph convolution operations.
4.1 NODE CLASSIFICATION
Beginning with node classification, we conduct ablations examining the behaviour of different parts of the DGG, followed by comparisons to other ofte-of-theearr graph-topology learning approaches. In the appendix we include experiments investigating the effect of the DGG on downstream models under the addition of noisy edges input graphs. We perform these experiments under both transductive and inductive scenarios, as well as semi-supervised and fully-supervised settings.
Transductive datasets. We evaluate on the three citation benchmark datasets Cora, Citeseer and Pubmed (NLM 2022) introduced by Yang et al. (2016). Each citation graph contains nodes corresponding documents and edges indicating citations. Node features are bag-of- ofg-offwords features and node labels are categorized by topic. We follow the semi-supervised setting in Yang et al. (2016) and Kipf & Welling) (2017) along with their train/test splits. Inductive datasets. In an inductive setting, we evaluate our approach on three datasets: 1. Flickr (Zeng et al. 2020) categorizing
images based on their descriptions;
Reddit (Zeng et al., (0200) predicting communities
of online posts from user comments. 3. PPI (Hamilton et al. 2017) classifying protein prootin
interactions. Further dataset details can be found in the appendix.
Baselines. We integrate our DGG into four representative GNN backbones: GCN (Kipf & Welling 2017). GraphSage (Hamilton et al., 2017). GAT (Veličković et al. 2018) and GCNII (Chen et al. 2020 On these backbones, we compare the effectiveness of DGG against other satte-o-thhe-ae graph sampling and sparsification methods: DropEdge (Rong et al.) 2020), NeuralSparse (Zheng et al. 2020 and PTDNet (Luo et al. (002))
Implementation details. We integrate our DGG into the official publicly available code of all baselines, without architectural modification. Models are trained and evaluated as their original implementation. See appendix for further details.
Training details. A node classification model partitions the latent space of node embeddings into separate classes. However, when message-passing there is one phenomenon of the input graph that can limit classification accuracy: two nodes with different classes but similar features and an edge connecting them. Classifying these nodes is challenging as their feature similarity can be compounded by passing messages between them. The goal of the DGG to move such nodes apart in the latent space such that there is no edge and communication between them. However, traversing the loss landscape from the initial random initialization of the network to one where the model able to discriminate between these nodes can take several iterations using only the downstream classification loss. To speed up training, we add an intermediate loss to further partition the latent space. We do this by supervising the adjacency matrix generated by the DGG to remove all edges between classes and only maintain those within class. We then anneal this loss over the training cycle, eventually leaving only the downstream classification loss. We provide more details in the appendix.

---

Under review as a conference paper at ICLR 2023
4.1.1 ABLATIONS
In Table D we explore the effect of disabling different components of our DGG module when integrated into GCN (Kipf & Welling, 2017) for node classification: 1. DGG without Degree Estimation and Differentiable Top-k Edge Selection - we remove the Degree Estimator and instead fixe l to select the top-k stochastically ordered edges. 2. DGG with deterministic Edge Ranking we remove the noise in Eq. of the Edge Ranker. 3. DGG with deterministic Degree Estimation we remove the noise in Eq. 7 of the Degree Estimator. We perform this under the transductive, semi-supervised setting on Cora and omit the annealed intermediate loss during training.
Table 1: Ablation study. DGG integrated into a GCN for node classification on Cora.
Model
Accuracy
Fixed node degree, = (1. 5, 10. 100}
{49.7, 78.9, 55.0, 37.0} 82,4
With deterministic Edge Ranking and Degree Estimation
With deterministic Edge Ranking
82.7
With deterministic Degree Estimation
82.8
DGG
83.2
Table shows the benefit of learning distribution over the node degree. When learning it determinis- tically, the accuracy decreases by 0.5%. This becomes significantly worse when the node degree is fixed for the entire graph rather than learned per node. Note also, the sensitivity with respect to choice of k. A fixed node degree of k = 10 or k = 1 reduces accuracy by almost 30% vs a graph of 5. This is due to the graph convolution operation: as it has no adaptive weighting mechanism for a node's neighborhood, each of the neighbors is given the same weight. Naturally, this leads to information sharing between unrelated nodes, reducing the quality of node representation after message- paassang.... In contrast, by learning a distribution over the node degree we are able to select only the most relevant neighbors, even though these are then weighted equally in the graph convolution. Finally, the inclusion of noise in any of the DGG components does increase accuracy, but only by about 0.5% - demonstrating both its benefit and the robustness of the DGG without
4.1.2 COMPARISON TO
In Table 2 we compare our method to DropEdge (Rong et al. 2020 ) which randomly sparsifies the input graph, and those which learn better graph structures (NeuralSparse (Zheng et al. (2020) and PTDNet[Luo et al. (20TT). ) For fair comparison with the literature, we present two versions of our method: DGG-wl trained with the downstream loss only and DGG* trained with both the downstream and intermediate loss.
DGG improves performance over the original model across all baselines and datasets. Against other approaches, DGG-wI generally outperforms the -fate-of-the-art NeuralSparse and PTDNet-wl (both trained with only the downstream loss). The accuracy difference can be attributed to our method for modelling sparsity, which explicitly lets each node to select the size of its neighborhood based on the downstream training signal. This training signal helps partition the node representation space, while the estimated node-degree additionally prevents communication between distant nodes. Although PTDNet-wl does this implicitly through its attention mechanism, discovering this sparse subgraph of the input graph is challenging given its complexity. NeuralSparse on the other hand selects k for its entire generated subgraph, which is both suboptimal and requires additional hyperparameter tuning.
Comparing methods which enforce additional constraints on the adjacency matrix, DGG* demon- strates larger accuracy gains than PTDNet* PTDNet* regularizes its adjacency matrix to be of low-rank, as previous work (Savas & Dhillon 2011) has shown that the rank of an adjacency matrix can reflect the number of clusters. This regularizrr reasons about the graph's 's topology globally. While this may aid generalization, the accuracy difference may then be attributed to our intermediate loss providing stronger signals to discriminate between nodes with similar features but different classes (and therefore remove the edges between them). Furthermore, their regularizer uses the sum of the top-k singular values during training, where & again is a hyperparameter tuned to each dataset individually. Our method requires additional parameters to be chosen.
We observe that there may be cases where tuning the node degree k can assist accuracy, as seen by NeuralSparse's 's performance on Reddit. However this requires hyperparameter search over Reddit's large graph, and is ultimately outperformed when intermediate supervision is applied to the DGG's adjaceney matrix (shown by the DGG* method).
7

---

Under review as a conference paper at ICLR 2023
Table 2: Semi-supervised node classification compared other SOTA graph-topology learning
methods. We compare against prior methods reported in (Luo et al. 2021 al. 2020). using the official results where available.
Zheng et al. 2020 Chen
Backbone
Method
Cora
Citeseer
Pubmed
Reddit
PPI
GCN
Original
81.1
70.3
79.0
92.2
53.2
DropEdge
80.9
72.2
78.5
96.1
54.8
NeuralSparse
82.1
71.5
78.8
96.6
65.1
PTDNet-wl
82.4
71.7
79.1
75.2
DGG-wl
82.7
72.4
80.1
96.5
76.7
PTDNet-wl low rank
82.8
72.7
79.8
80.3
DGG*
83.9
74.9
83,9
97.2
81.5
GraphSage
Original
79.2
67.6
76.7
93.8
61.8
DropEdge
78.7
67.0
74.8
96.3
61.0
NeuralSparse
79.3
67.4
75.1
96.7
62.6
PTDNet-wl
79.4
67.8
77.0
64.5
DGG-wl
79.4
68.2
77.6
96.7
65.1
PTDNet-wl low rank
80.3
67.9
77.1
64.8
DGG*
80.4
70.6
80.1
96.9
67.3
GAT
Original
83.0
72.1
79.0
97.3
DropEdge
83.2
70.9
77.9
85.1
NeuralSparse
83.4
72.4
78.0
92.1
PTDNet-wl
83.7
72.3
79.2
97.8
DGG-wI
84.2
73.0
79.5
97.3
PTDNet-wl low rank
84.4
73.7
79.3
98.0
DGG*
85.1
76.3
81.8
97.5
GCNII
Original
85.3
73.2
80.2
99.5
DropEdge
84.9
73.4
79.4
99.0
DGG-wl
86.8
74.4
81.2
99.5
DGG*
87.7
75.8
81.9
99.7
Table 3: Adjacency matrix constraints: our intermediate annealed loss vs. PTDNet's low rank regularizer Luo et al. (202T) for semi-supervised node classification with GCN backbone.
Method
Cora
Citeseer
Pubmed
Reddit
PPT
Ours-wl wl
82.7
72.4
80.1
96.1
76.7
Ours-wl + low rank
83.3
73.1
81.0
96.1
80.6
Ours-wl wl + int. loss
83.9
74.9
83.9
97.2
81.5
Ours-wl wl + int. loss low rank
84.0
75.1
84.2
97.2
81.8
Finally in Table we compare the low-rank constraint PTDNet with our intermediate annealed loss. Our intermediate loss ("Ours-wl + int. loss') outperforms the low-rank constraint ("Ours-wl wl + low rank'). ). However, using both constraints ('Ours-wl + int. loss + low rank') increases classification accuracy further, suggesting the edges removed by both methods complementary.
4.2 TRAJECTORY PREDICTION
We consider four datasets covering range of scenarios from baseketball crowded urban envi- ronments. On each, we integrate our DGG into state-of-the-ar -frt trajectory prediction method and compare results to another state-of-the-arr graph-topology learning approach DGM (azii al. 2020).
Datasets. We evaluate on four trajectory prediction benchmarks. 1. ETH (Pellegrini et al. 2009 and STATS
UCY (Lerner et al. 2007) - subsets widely used real-world pedestrian trajectories.
Vp (Sport
multiple NBA scasons tracking trajectories of basketball players Stanford Drone Dataset (SDD) (Robicquet et al. 2016) top-down scenes across multiple areas at Stanford University, consisting of different agents from pedestrians to cars. Further details these datasets can be found in the appendix.
game.
We integrate our DGG module into two ofate-of-the-an trajectory prediction pipelines: Social-STGCNN (Mohamed et al.] (2020) built upon spatio-tempon convolutional network using graphs represent pedestrian trajectories and DAGNet (Monti al. 2021) built upon VAE
Baselines.
8

---

Under review as a conference paper at ICLR 2023
Table ADE/FDE metries on the ETH UCY datasets using Social-STGCNN, For DGM, =
Dataset
Original
DGM
DGM
Gain
Ours
Our Gain
ADE
FDE
ADE J
FDE
ADE
FDEt
ADE
FDE 4
ADE 1
FDE 1
ETH
0.64
1.11
0.62
1.04
2.4%
6.4%
0.60
0.89
6.3%
20%
Hotel
0.49
0.85
0.42
0.69
14.2%
18.9%
0.38
0.54
22.4%
36.5%
Univ
0.44
0.79
0.41
0.76
6.2%
3.5%
0.40
0.70
9.1%
11.3%
Zaral
0.34
0.53
0.33
0.46
3.8%
13.7%
0.32
0.42
5.9%
20.8%
Zara2
0.30
0.48
0.29
0.43
5.0%
5.0%
0.27
0.40
10.0%
16.7 %
Mean
0.44
0.75
0.41
0.68
6.3%
10.6%
0.39
0.59
11.4%
21.3%
Table 5: ADE/FDE metrics on the SportVU Basketball dataset using DAGNet. For DGM, k
Original ADE
DGM
DGM Gain
Ours
Our Gain
Split
Team
FDE
ADE
FDE
ADE
FDE
ADE
FDE
ADE
FDE
10-40
ATK
2.74
4.29
2.75
4.30
-0.4%
-0.2%
2.62
4.11
4.4%
4.2%
DEF
2.09
2.97
2.10
2.97
-0.5%
-0.1%
1.95
2.87
6.8%
3.3%
20-30
ATK
2.03
3.98
2.03
3.98
0.1%
0.1%
1.92
3.75
5.6%
5.8%
DEF
1.53
3.07
1.53
3.06
0.2%
0.3%
1.24
2.56
18.7%
16.6%
40-10
ATK
0.81
1.71
0.80
1.69
1.3%
0.9%
0.70
1.48
13.6%
13.5%
DEF
0.72
1.49
0.71
1.48
0.8%
0.8%
0.66
1.29
8.3 %
13.4%
Mean
1.65
2.92
1.7
2.9
0.3%
0.3%
1.51
2.68
9.6%
9.5%
backbone (Kingma & Welling 2013) with graph attention network modelling agent interactions across a fully- cully-connected graph. Our DGG placed within both networks to generate the adjacency matrix the fly and forms part of its forward and backward pass. To integrate the DGG with DAGNet's attention mechanism, the adjacency generated is multiplied by the attention weights.
Implementation details. We integrate DGG into the publicly available code of each method, without any architectural modification. We use the same DGG hyperparameters as for node classification except the intermediate loss is disabled and the training signal is entirely from the downstream task. Evaluation metrics. Model performance is measured with Average Displacement Error (ADE) and Final Displacement Error (FDE). ADE measures the average Euclidean distance along the entire predicted trajectory, while the FDE is that of the last timestep only.
4.2.1 RESULTS
In T the integration of our DGG into Social-STGCNN reduces ADE/EDE compared to both the baseline and the integration of DGM. In Table 5 andd 6 our DGG displays similar gains over DGM when integrated into DAGNet. First, this shows the benefit of inducing sparsity when cressage-passing over distance weighted adjacency matrix like
or even an attention- attention-mechanism mechanism like DAGNet. The larger eтror reduction of our DGG compared to DGM may be attributed to DGM's use of fixed node-degree across its learned graph. While this can prevent the propagation of irrelevant information across the graph in some cases, in others it might limit the context available to certain nodes. the other hand, trying to discover the subgraph entirely through attention makes optimization challenge. Instead, constraining the model by allowing each node to select its neighborhood and size cases optimization and can still be done entirely from the downstream training signal. We provide further qualitative analysis for these results in the appendix.
5 CONCLUSION
We have presented novel approach for learning graph topologies, and shown how it obtains state- of-the-art performance across multiple baselines and datasets for node classification and trajectory prediction. The principal advantage of our approach is that can be combined with any existing approach using graph convolutions on an automatically generated graph, such as a neneetttt neighbor graph.
Table ADE/FDE metries on the Stanford Drone Dataset using DAGNet. For DGM, 2.
Split
Original
DGM
DGM
Gain
Ours
Our Gain
ADE
FDE
ADE
FDE
ADE
FDE
ADE
FDE
ADE
FDE
8-12
0.53
1.04
0.52
1.01
1.9%
3.0%
0.48
0.96
10.4 %
8.3 %

---

Under review as a conference paper at ICLR 2023
REFERENCES
Alexandre Alahi, Kratarth Goel, Vignesh Ramanathan, Alexandre Robicquet, Li Fei-Fei, and Silvio Savarese. Social Istm: Human trajectory prediction in crowded spaces. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 961-971, 2016.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18-42 2017.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, pp. 1725-1735. PMLR, 2020.
Nicholas Choma, Federico Monti, Lisa Gerhardt, Tomasz Palczewski, Zahra Ronaghi, Prabhat Prabhat, Wahid Bhimji, Michael Bronstein, Spencer R Klein, and Joan Bruna. Graph neural networks for icecube signal classification. In 2018 17th IEEE International Conference on Machine Learning and Applications (ICMLA), pp. 386-391. IEEE, 2018.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29:
2016.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. Advances in neural information processing systems, 28, 2015.
Pablo Gainza, Freyr Sverrisson, Frederico Monti, Emanuele Rodola, D Boscaini, MM Bronstein, and BE Correia. Deciphering interaction fingerprints from protein molecular surfaces using geometric deep learning. Nature Methods, 17(2):184 192, 2020.
Agrim Gupta, Justin Johnson, Li Fei-Fei, Silvio Savarese, and Alexandre Alahi. Social gan: Socially acceptable trajectories with generative adversarial networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp.
2018.
William I. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning large graphs In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 1025-1035, 2017.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterizatioo with gumbel-softmax arXiv preprint arXiv: 1.0/ 144, 2016.
Anees Kazi, Luca Cosmo, Nassir Navab, and Michael Bronstein. Differentiable graph module (dgm) for graph convolutional networks. arXiv preprint arXiv:2002.04999, 2020.
Diederik P Kingma and Max Welling. 1312.61 14, 2013.
Auto-encoding
variational bayes. arXiv preprint
Thomas Kipf, Ethan Fetaya, Kuan-Chieh Wang, Max Welling, and Richard Zemel. Neural relational inference for interacting systems. In International Conference on Machine Learning, pp. 2697-2697. PMLR, 2018.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Reprexentations, ICLR 2017, Toudon, France, April 24- 26, 2017, Conference Track Proceedings. OpenReview.net, 2017. WtRl.tttps:.. ptttt:::://ppeeevviie net / Eorum? 2immmiid-Saae SJJAnayy-SJ
Alon Lerner, Yiorgos Chrysanthou, and Dani Lischinski. Crowds by example. In Computer graphics forum, volume 26, pp. 655-664. Wiley Online Library, 2007.
Ziyu Liu. Hongwen Zhang, Zhenghao Chen, Zhiyong Wang, and Wanli Ouyang. Disentangling and unifying graph convolutions for skeleton- based action recognition. In Proceedings of the IEFF/CV conference on computer vision and pattern recognition, pp. 143-152, 2020.
10

---

Under review as a conference paper at ICLR 2023
Dongsheng Luo, Wei Cheng, Wenchao Yu, Bo Zong, Jingchao Ni, Haifeng Chen, and Xiang Zhang. Learning to drop: Robust graph neural network via topological denoising. In Proceedings of the 14th ACM International Conference Web Search and Data Mining, pp. 779-787, 2021.
Abduallah Mohamed, Kun Qian, Mohamed Elhoseiny, and Christian Claudel. stgennn: A social spatio-temporal graph convolutional neural network for human trajectory prediction. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pp. 14424-14432, 2020.
Alessio Monti, Alessia Bertugli, Simone Calderara, and Rita Cucchiara. Dag-net: Double attentive graph neural network for trajectory forecasting. In 2020 25th International Conference on Pultern Recognition (ICPR), pp. 2551-2555 IEEE, 2021.
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 5115-5124, 2017.
Federico Monti, Fabrizio Frasca, Davide Eynard, Damon Mannion, and Michael M Bronstein. Fake news detection on social media using geometric deep learning. arXiv preprini arXiv: 1902.06673. 2019.
NLM 2022. Pubmed. courtesy of the us national library medicine.
Stefano Pellegrini, Andreas Ess, Konrad Schindler, and Luc Van Gool. You'll never walk alone: Modeling social behavior for multi-target tracking. In 2009 IEEE 12th international conference on computer vision, pp. 261-268. IEEE, 2009.
Alexandre Robicquet, Amir Sadeghian, Alexandre Alahi, and Silvio Savarese. Learning social etiquette: Human trajectory understanding in crowded scenes. In European conference on computer vision, pp. 549-565. Springer, 2016.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convo- lutional networks on node classification. In International Conference on Learning Representations, 2020. URL
net http:///www....oooooooooooooooo.
qkrKPr
Tim Salzmann, Boris Ivanovic, Punarjay Chakravarty, and Mareo Pavone. Trajectron++:: Dynamically- feasible trajectory forecasting with heterogeneous data. In Computer Vision-ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XVIII 16, pp. 683-700. Springer, 2020.
Berkant Savas and Inderjit S Dhillon. Clustered low rank approximation of graphs in information science applications. In Proceedings of the 2011 SIAM International Conference on Data Mining, pp. 164 175. SIAM, 2011.
Lei Shi, Yifan Zhang, Jian Cheng, and Hanqing Lu. Two-stream adaptive graph convolutional networks for skeleton based action recognition. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pp. 12026-12080 2019.
SportVU. Sportvu basketball, Sep 2019.
URL
team
Jonathan M Stokes, Kevin Yang. Kyle Swanson. Wengong Jin, Andres Cubillos-Ruiz Nina M Donghia, Craig R MacNair, Shawn French, Lindsey A Carfrae, Zohar deep learning approach to antibiotic discovery. Cell, 180(4))688-702, 2020.
et al. A
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S Pappu, Karl Leswing, and Vijay Pande. Moleculenet: benchmark for molecular machine learning. Chemical science, 92):5133-300 2018.
11

---

Under review as a conference paper at ICLR 2023
Yujia Xie, Hanjun Dai, Minshuo Chen, Bo Dai, Tuo Zhao, Hongyuan Zha, Wei Wei, and Tomas Pfister. Differentiable top-k with optimal transport. Advances in Neural Information Processing Systems, 11-20520-20533 2020.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting remi-supervised learning with graph embeddings. In International conference on machine learning. pp. 40-48. PMLR, 2016.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- SAINT: Graph sampling based inductive learning method. In International Conference Learning Representations, 2020. URL
Cheng Zheng, Bo Zong, Wei Cheng, Dongjin Song, Jingchao Ni, Wenchao Yu, Haifeng Chen, and Wei Wang. Robust graph representation learning via neural sparsification. In International Conference on Machine Learning, pp. 11458-14 1146. PMLR, 2020.
A NODE CLASSIFICATION EXPERIMENTS
A.1 I DATASET DETAILS
In Table 7 we provide dataset statistics on the node classification datasets used in this paper.
Table Dataset statistics. 's' stands for single class classification and 'm' for multi-class.
Dataset
Nodes
Edges
Features
Classes
Train Val / Test
Cora 2,708
5,429
1,433
(s)
140 500 / 1,000
Citeseer
3,327
4,732
3,703
(s)
120 / 500 / 1,000
PubMed
19,717
44,338
500
(s)
100 500 / 1,000
PPI
56,944
81,8716
50
121 (m)
44,906 6,514 5,524
Flickr 89,250
899,756
500
7 (s)
44,760 22.312 / 22,312
Reddit
232.965
11,606,919
602
41 (s)
153,756 / 23,295 55,911
A.2 IMPLEMENTATION DETAILS
In our DGG, all MIPs use signle fully-connected layer of dimension 64. In DGG, all MLPs use single fully-connected layer of dimension 64. We use a Gumbel-Softmax temperature of 2.5. When adding Gumbel noise the edge pog--obbabilities, diagonal of the edge probability matrix). During training, we keep the Gaussian and Gumbel noise on, but turn it off during inference. While in practice it can left on, we found does not significantly impact the results.
not add any the self-loops (i.e. the
A.3 TRAINING DETAILS
We train the entire network end-to-end using the classification loss from the downstream model and an annealed MSE loss on the adjacency matrix generated by the DGG:
M
Liotal = Lelass +
9.)
(10)
M
where the first term is the classification loss from the downstream GCN, the second term is the MSE loss applied to every element dJ of the adjacency matrix E NxN for which we have node label, and is loss weight. The model can be trained by annealing smoothly in step-wise manner. In practice we keep a constant for the first 100 epochs and then set it to zero for the rest of the training schedule (where the total number of epochs determined by schedule of the downstream GCN).
12

---

Under review as a conference paper at ICLR 2023
A.4 ROBUSTNESS TO NOISE
We test the effect of the DGG when the input graph has random edges added across it. We do this by adding edges between previously unconnected nodes. Broadly, the results in Fig. [ demonstrate the detrimental effects of noisy edges on classification accuracy, but the inclusion of the DGG can mitigate this. Interestingly, the state-of-the-arr GCNII Chen et al. 2020) demonstrates the largest drops in accuracy as the noise increases, which may be attributed to the depth of their graph convolution layers. In such deeper message-passing models, the edge structure even more significant, highlighting the importance of learning structure that prevents the propagation of irrelevant information.
Cora
Citeseer
70
Aucunacy
00
60-
Nutey edge (76)
Noday orlges (71)
Flickr
GCN
55-
GCN DGG
30-
GCNIT
GCNIT w DGG
45
35
Nukey eday (76)
Figure 4: Node classification accuracy with noisy edges added the input graph of different datasets.
B TRAJECTORY PREDICTION EXPERIMENTS
B. DATASET DETAILS
ETH and UCY. ETH (Pellegrini et al. 2009) and UCY Lerner et al. 2007) are two common
benchmarks for pedestrian trajectory prediction. These datasets consist of subsets of widely used
real-world pedestrian trajectories (Alahi et al. 2016 Gupta et al., 2018 Mohamed et al., 2020 Salzmann et al. 2020). The primary challenge in these datasets are the frequent interactions of agents in very crowded scenes. Furthermore, the number of pedestrians varies considerably. Some frames contain only 2 pedestrians, while many have over 50.
SportVU. The STATS SuortVu (SportVU) is tracking dataset composed of multiple NBA seasons. Each scene consists of two teams of 5 players, with each team categorized as either making an offensive or defensive play in particular game. Each play contains 50 timesteps sampled at 5Hz, with the player trajectories expressed in (z, y, 2) coordinates.
Stanford Drone. The Stanford Drone Dataset (SDD) (Robicquet et al. 2016) is large dataset with 20 different top-down scenes across multiple areas at Stanford University. Each scene consists of agents of different types, from pedestrians and skaters cars and buses. Trajectories recorded at 2.5Hz and expressed in (z. y) world coordinates. Despite the heterogeneity of agents, the maximum number of agents in any one scene is 21.
13

---

Under review as a conference paper at ICLR 2023
B.2 QUALITATIVE RESULTS
In Fig. we plot the node-degree distribution learned by our DGG across multiple datasets. While on average, a pedestrian may only look at their 2 nearest neighbors in crowded scenes such Zara and Univ, this can increase to almost 5 nearest neighbors in some cases. This suggests that both fully-connected graph, or one with a fixed node-degree like DGM (Kazi al. 2020 are both suboptimal.
Nodoodgeer diseriltiion
10.
F117
Toat
02
Figure 5: Distribution of the learned node degree lo over the test split for different trajectory prediction datasets.
Figure compares our predicted trajectories DGM (Kazi et al. 2020), on the VU dataset. As shown, our trajectories are closer to the ground truth. We illustrate this further in Fig. 7 which shows the graph generated by our DGG for different basketball players in a game. The figure demonstrates how our DGG lets each player look at different number of neighbours, while DAGNet Monti et al, (202T) forces each player to look at others in the game.
Figure 6: Qualitative results for trajectory prediction the VU dataset. Orange: ground truth; Blue: DGM prediction; Red: our prediction.
14

---

Under review as a conference paper at ICLR 2023
DAGNet: Player
DAGNet: Player B
DAGNet: Player C
DAGNet: hist, over
1.0
0.8
0.0
Fixed neighborhood players. graph fully-coomected. Each player alway's
2
5
players.
fully
-cotmeeted graph,
degros always
Ours: Player
Ours: Player
Ours: Player C
Ours: hist.
0.4
Our neighborhood selection for different players. Each player can select their nrighborhood and ibs size. Datted bloe show redundant edges neighours
Aa mevtibod latas each playeer select their neighborhood and the mode varies.
selected).
Figure 7: Graph topology visualisation in baskethall players on the Vu dataset: ours vs. DAGNet (Monti et al. 2021). We display the selected neighborhood for different players and histogram of the node-degree ls accumulated over the dataset/scene. First row: DAGNet's 's fully-comnected graph, second row: our DGG.
15


Reviews:
[{"review_id": "qPgkvPOwyO", "reviewer": "Reviewer_Ds7V", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The paper introduces a method for learning a graph topology that can be integrated in any GNN framework. The proposed probabilistic method is built on a differentiable graph operator that is able to decide the size of the neighbourhood of each node (i.e., degree of each node), as well as the corresponding edges. Experimental results on i) different GNN architectures and ii) a wide set of datasets are provided. ", "summary_of_the_review": "Overall, this is a well-written paper addressing an interesting topic. Although there is quite a lot of work in learning the connectivity matrix in a GNN framework, this paper brings one additional solution to the problem. Thus, the problem itself is not novel, but the proposed solution is valid. \n\nSome additional comments that could hopefully help the authors are the following:\n\n1) In Eq. (8), the dimensionality of $z_i$ and $h_i$ does not seem to be the same. The former is $d$ and the later is 1. Could you please explain and clarify?\n2) Can you discuss on the type of edges that you learn? If I understand correctly the learned graph is directed. Is it possible to extend it to an undirected graph, which might be more suitable for some applications?\n3) In the training details, the authors mention that \"to speed up training, we add an intermediate loss...\". Can you please elaborate on that? It seems that the loss promotes a specific class of graphs that consists of community structures. Is that correct? Please clarify. \n4) Related to the previous comment, it would be useful to understand more the properties of the learned graph. Can the method be extended to unsupervised settings?\n\nSome examples typos that should be fixed: \n- p.7: 'fixe k': remove e \n- p.12: 'signle': single ", "strength_and_weaknesses": "Strength: The topic is of interest to the (graph) machine learning community. Updating/learning/rewiring graphs for a final end-task is an open problem with some approaches already proposed. This work builds on those approaches and improves some of those aspects. The paper is very clearly written and easy to follow. \n\nWeaknesses:  I don't see a strong weaknesses of the paper expect from the fact that is it incremental in comparison to the existing literature. ", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "g5uT-qrz6ca", "reviewer": "Reviewer_CYQs", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 proposes an end-to-end differentiable graph generator that builds the graph topology simultaneously as learning for a downstream task. The proposed idea extends the applicability of GNNs to cases where a graph topology is not readily available. The experimental results show that the proposed model improves the performance of node classification ad trajectory prediction tasks.", "summary_of_the_review": "**Questions**\n\nTable 2: It is not clear to me what is used as input to DGG for this experiment. Is the original graph structure for Cora, Citeseer, ... used in this experiment? Also, as mentioned earlier, many baselines are missing here.\n\n\nThe intermediate loss: Why adding the intermediate loss can help? Why doesn't the downstream task loss do the same thing as encouraging nodes in the same class to be connected and nodes in a different class to be disconnected?", "strength_and_weaknesses": "\n**Strengths**\n\nThe proposed method helps create a similarity graph with a learnable node degree for each node in the graph.\n\n**Weaknesses**\n\nThe proposed method does not discuss or compare with a large body of related work for learning a graph topology on the fly (e.g., [1, 2, and 3]). Without comparing with the existing works, the contribution of the proposed method is not measurable.\n\nThe time complexity of the proposed approach is not discussed. For the edge ranking step, the similarity of each pair of nodes should be computed and later used in the Gumbel-Softmax. This means O(n**2) time complexity with n as the number of nodes in the graph. \n\nThe datasets used in this paper are relatively small compared to the current benchmarks (e.g., OGB graphs [4])\n\n[1] Learning discrete structures for graph neural networks, ICML 2019.\n\n[2] Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings, NeurIPS 2020.\n\n[3] SLAPS: Self-supervision improves structure learning for graph neural networks, NeurIPS 2021.\n\n[4] Open graph benchmark: Datasets for machine learning on graphs, NeurIPS 2020.\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": {}}, {"review_id": "BcfUsaZz90T", "reviewer": "Reviewer_9Mc3", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "In this paper, a joint topology and graph representation learning framework is proposed to tackle the adjacency matrix missing scenarios. The method could also be applied to the given graph topology to improve the emirical performance. The distinguishing point is the incorporation of adapative number of neighbors k which could be differentiably learnt via a Gumbel-softmax trick. However, the paper lacks more detailed discussion and experiment with recent graph structure learning models.", "summary_of_the_review": "This paper studies an important problem. However, the proposed method lacks enough novelty, especially quite a few proposed components have already been explored by prior art in the same direction. Also, an important line of related works are missing without any comparison, which makes the technical contributions of this work not convincing.", "strength_and_weaknesses": "Strengths:\n\n1. The paper aims to optimize a graph model that jointly learns the topology and graph representation in an end-to-end differentiable manner. The cases where adjacency matrix is not provided are supported, as well as refine the given adjacency to improve the topology for better performance\n\n2. A framework is proposed that can plugs in a wide range of existing GNN methods\n\n3. An insight of this work is that it considers the variable number of neighbors in the graph topology learning. The differentiablity is implemented by a combination of degree estimator and top-k neighbor selector.\n\n\nWeaknesses:\n\n1. An important line of related works are missing. The paper claims that it is the first to consider differentiable end-to-end learning of graph topology, and however, it is wrong. Differentiable graph structure learning has been explored by quite a few existing studies, e.g. [1-5]. In particular, [1] uses bi-level optimization for learning structures/representations as the outer/inner loop, [2, 3] harnesses variational inference for joint learning topology and node representations, [4] considers iterative learning of the two things and [5] proposes a scalable model that learns optimal topology with Gumbel trick in each representation layer. A detailed comparison with these works are needed to illuminate the differences and novelty.\n\n2. The experiment only compares with the methods which drops edges from the orignal graph, instead of the more related and strong competitors that learn the graph structure, especially the works that involve graph topology and representation joint learning, e.g. the above-mentioned models.\n\n3. The proposed method seems to have O(N^2) complexity w.r.t. node numbers and not scalable enough for large datasets. The experiments are only conducted on small datasets, instead of the larger ones, e.g., from OGB. \n\n4. The paper claims that the framework fits with any “graph convolutional networks”, are there any reasons that other spatial GNNs based on message passing do not fit here?\n\n5. The paper uses Gumbel-softmax for edge probabilty estimation. However, the pairwise edge probability is estimated independently of each other. Under this assumption, the dependencies among edges are not taken into account. Are there some jusfitication of this assumption?\n\n[1] Learning Discrete Structures for Graph Neural Networks, ICML19\n\n[2] Variational Inference for Graph Convolutional Networks in the Absence of Graph Data and Adversarial Settings, NeurIPS20\n\n[3] Variational Inference for Training Graph Neural Networks in Low-Data Regime through Joint Structure-Label Estimation, KDD22\n\n[4] Iterative Deep Graph Learning for Graph Neural Networks - Better and Robust Node Embeddings, NeurIPS21\n\n[5] NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification, NeurIPS22", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "6xUQO42TeI4", "reviewer": "Reviewer_ob93", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 proposes a differentiable graph-generator that builds the graph topology on the fly.\n", "summary_of_the_review": "Overall, this paper proposes yet another method for applying Graph Neural Networks to datasets without explicitly relational structure through inferring latent graphs. While the proposed method is technically sound, it lacks technical novelty. Also, the empirical performance is weak, and the method is not scalable.", "strength_and_weaknesses": "Strength:\n- The paper is clearly written.\n- The approach is technically sound.\n\nWeakness:\n- The idea of learning the graph structure for GNN is not novel. I have read several papers with similar ideas, for example, http://proceedings.mlr.press/v97/franceschi19a/franceschi19a.pdf\n- The proposed method is only evaluated with basic GNN models - the reported number is far below the state-of-the-art performance, on the classic benchmark datasets being used.\n- The approach is clearly not going to scale to large graphs. And I did not find discussions regarding the scalability of the method.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject