TopoTER: Unsupervised Learning of Topology Transformation Equivariant Representations
Authors: Xiang Gao
Wei Hu
Guo-Jun Qi
Venue:  (2021)
Keywords: Unsupervised learning
node representations
mutual information

Abstract: We present the Topology Transformation Equivariant Representation (TopoTER) learning, a general paradigm of unsupervised learning of node representations of graph data for the wide applicability to Graph Convolutional Neural Networks (GCNNs). We formalize the TopoTER from an information-theoretic perspective, by maximizing the mutual information between topology transformations and node representations before and after the transformations. We derive that maximizing such mutual information can be relaxed to minimizing the cross entropy between the applied topology transformation and its estimation from node representations. In particular, we seek to sample a subset of node pairs from the original graph and flip the edge connectivity between each pair to transform the graph topology. Then, we self-train a representation encoder to learn node representations by reconstructing the topology transformations from the feature representations of the original and transformed graphs. In experiments, we apply the TopoTER to the downstream node and graph classification tasks, and results show that the TopoTER outperforms the state-of-the-art unsupervised approaches.

Under review as a conference paper at ICLR 2021
TOPOTER: UNSUPERVISED LEARNING OF TOPOLOGY TRANSFORMATION EQUIVARIANT REPRESENTATIONS
Anonymous authors
Paper under double-blind review
ABSTRACT
We present the Topology Transformation Equivariant Representation (TopoTER) learning, a general paradigm of unsupervised learning of node representations of graph data for the wide applicability to Graph Convolutional Neural Networks (GCNNs). We formalize the TopoTER from an information -hheooetttt perspec- tive, by maximizing the mutual information between topology transformations and node representations before and after the transformations. We derive that maximizing such mutual information can be relaxed to minimizing the cross en- tropy between the applied topology transformation and its estimation from node representations. In particular, we seek to sample a subset of node pairs from the original graph and flip the edge connectivity between each pair to transform the graph topology. Then, we self-train a representation encoder to learn node repre- sentations by reconstructing the topology transformations from the feature repre- sentations of the original and transformed graphs. In experiments, we apply the TopoTER to the downstream node and graph classification tasks, and results show that the TopoTER outperforms the state-of-the-art unsupervised approaches.
INTRODUCTION
Graphs provide a natural and efficient representation for non-Euclidean data, such as brain networks, social networks, citation networks, and 3D point clouds. Graph Convolutional Neural Networks (GCNNs) (Bronstein et al., (017)) have been proposed to generalize the CNNs to learn representa- tions from non-Euclidean data, which has made significant advances in various applications such as node classification (Kipf & Welling, 2017, Veličković et al., 2018: Xu et al., (019a) and graph classification (Xu et al., (019b). However, most existing GCNNs are trained ion, requiring large amount of labeled data for network training. This limits the applications of the GCNNs since it is often costly to collect adequately labeled data, especially on large-scale graphs. Hence, this motivates the proposed research to learn graph feature representations in unsuper- vised fashion, which enables the discovery of intrinsic graph structures and thus adapts to various downstream tasks.
supervised fash-
Auto-Encoder (AEs) and Generative Adversarial Networks (GANs) are two most representative un- supervised learning methods. Based on the AEs and GANs, many approaches have sought to learn transformation equivariant representations (TERs) to further improve the quality of unsupervised representation learning. assumes that the learned representations equivarying to transformations are able to encode the intrinsic structures of data such that the transformations can be reconstructed from the representations before and after transformations (Qi et al., 2019b). Learning TERs traces back to Hinton's 's seminal work on learning transformation capsules (Hinton et al., 2011). and em- bodies a variety of methods developed for Euclidean data (Kivinen & Williams, [20TT] Sohn & Lenc & Vedaldi 2015 2013
Lee 2012: Schhidt& & Roth 2012 [Skibbe
2013
& Domingos 2014]
Dieleman et al., 2015; 2016 Zhang et al. 2019 Qi et al., (019a)) Further, [Gao et al. (2020) ex- non-Euulidean domain, which formalizes Graph Transformation Equivariant Representation (GraphTER) learning by auto-encoding node- wise transformations in unsupervised fashion. Nevertheless, only transformations node fea- tures are explored, while the underlying graph may vary implicitly. The graph topology has not been fully explored yet, which however is crucial in unsupervised graph representation learning.
tend transformation equivariant representation learning
To this end, we propose the Topology Transformation Equivariant Representation (TopoTER) learn- ing to infer unsupervised graph feature representations by estimating topology transformations. In-

---

Under review as a conference paper at ICLR 2021
stead of transforming node features as in the GraphTER, the proposed TopoTER studies the trans- formation equivariant representation learning by transforming the graph topology, i.e. adding or removing edges to perturb the graph structure. Then the same input signals are attached to the sultant graph topologies, resulting in different graph representations. This provides an insight into how the same input signals associated with different graph topologies would lead equurly representations enabling the fusion of node feature and graph topology in GCNNs. Formally, we propose the TopoTER from an information-theoreti perspective, aiming to maximize the mutual in- formation between topology transformations and feature representations with respect to the original and transformed graphs. We derive that maximizing such mutual information can be relaxed the cross entropy minimization between the applied topology transformations and the estimation from the learned representations of graph data under the topological transformations.
equivariant
Specifically, given an input graph and its associated node features, we first sample a subset of node pairs from the graph and flip the edge connectivity between each pair at a perturbation rate, lead- ing to a transformed graph with attached node features. Then, we design graph-convolutional auto-encoder architecture, where the encoder learns the node-wise representations over the origi- nal and transformed graphs respectively, and the decoder predicts the topology transformations of edge connectivity from both representations by minimizing the cross entropy between the applied and estimated transformations. Experimental results demonstrate that the proposed TopoTER model outperforms the state-of-the-an unsupervised models, and even achieves comparable results to the (semi-)sup (emmi-ssuperviedd approaches in node classification and graph classification tasks at times.
Our main contributions are summarized as follows.
We propose the Topology Transformation Equivariant Representation (TopoTER) learning to in- fer expressive node feature representations in an unsupervised fashion, which can characterize the intrinsic structures of graphs and the associated features by exploring the graph transformations of connectivity topology.
We formulate the TER from an cottmaatioonthooettii perspective, by maximizing the mutual information between feature representations and topology transformations, which can be relaxed to the cross entropy minimization between the applied transformations and the prediction in an end-to-end graph-convolutional auto-encoder architecture.
Experiments demonstrate that the proposed TopoTER model outperforms the state-of-the-art un- supervised methods in both node classification and graph classification.
RELATED WORK
Graph Auto-Encoders (GAEs) are the most representative unsupervised methods. GAEs encode graph data into feature space via an encoder and reconstruct the input graph data from the encoded feature representations via decoder. GAES are often used to learn network embeddings and graph generative distributions (Wu et al., 2020). For network embedding learning, GAEs learn the feature representations of each node by reconstructing graph structural information, such as the graph adjacency matrix (Kipf & Welling (016) and the positive pointwise mutual information (PPMI) matrix (Cao et al., [ methods generate nodes and edges of a graph alternately (You et al. (2018). while other methods output an entire graph (Simonovsky & Komodakis 2018 Ma al. 20188] De Cao & Kipf 2018).
Graph Auto-Encoders.
al. 2016)). For graph generation, some
Graph Contrastive Learning. An important paradigm called contrastive learning aims to train an encoder to be contrastive between the representations of positive samples and negative sam- ples. Recent contrastive learning frameworks can be divided into two categories (Liu et al.) 2020): contexi-instance contrast and contexi-contexl contrast. Context-instance contrast focuses on mod- eling the relationships between the local feature of sample and its global context representation. Deep InfoMax (DIM) (Hjelm al. 2018) first proposes to maximize the mutual information be- tween a local patch and its global context through a contrastive learning task. Deep Graph InfoMax (DGI) /Velickovic et al. 2019) proposes to learn node-level feature representation by extending DIM to graph-structured data, while InfoGraph (Sun et al.) (020a) aims to use mutual information maximization for unsupervised representation learning on entire graphs. Peng et al. (2020) pro-
pose a Graphical Mutual Information (GMI) approach to maximize the mutual information of both features and edges between inputs and outputs. In contrast to context-instance methods, context- context contrast studies the relationships between the global representations of different samples. M3S (Sun et al. 2020b) adopts a supe--sue pre-traine pre-training paradigm as in DeepCluster (Caron et al. 2018 for better semi-supervised prediction in GCNNs. Graph Contrastive Coding (GCC)
2

---

Under review as a conference paper at ICLR 2021
Original Graph
Perturbed Graph
0
Topology Transformation
8
3
-1
0
-1
2
-1
unchanged edge added edge
removed edge
Figure 1: An example of graphs before and after topology transformations.
QQu et al. 2020) designs the pre-training task as subgraph instance discrimination in and across networks empower graph neural networks to learn the intrinsic structural representations.
Transformation Equivariant Representation Learning. Many approaches have sought to learn transformation equivariant representations. Learning transformation equivariant representations has been advocated in Hinton's 's seminal work on learning transformation capsules. Following this, variety of approaches have been proposed to learn transformation equivariant representations (Gens) & Domingos] 2014 Dieleman et al. 2015] 2016 Cohen & Welling, 2016; Lenssen et al., 2018)
To generalize to generic transformations, Zhang et al. (2019) propose to learn unsupervised feature representations via Auto-Encoding Transformation (AET) by estimating transformations from the learned feature representations of both the original and transformed images, while Qi et al. (201 2019a) extend AET from an information theorretic perspective by maximizing the lower bound of mutual in- formation between transformations and representations. Wang et al. (2020) extend the AET to Gen- erative Adversarial Networks (GANs) for unsupervised image synthesis and representation learning- Gao et al. (2020) introduce the GraphTER model that extends AET to graph-structured data, which formalized by auto-encoding node-wise transformations in an unsupervised manner. de Haan et al. (2220) propose Gauge Equivariant Mesh CNNs which generalize GCNNs to apply anisotropic gauge equivariant kernels. Fuchs et al. (2020) introduce self-attention mechanism specifically for 3D point cloud data, which adheres to equivariance constraints, improving robustness to nuisance transformations.
3 METHOD
3.1 PRELIMINARY
We consider undirected graph G = (V, E, A} composed of a node set V of cardinality [V] = N. an edge set & connecting nodes cardinality [|] = M. is a real symmetric N N matrix that encodes the graph structure, where a, 1 if there exists an edge (i,j) between nodes i and j, and as.j = 0 otherwise. Graph signal refers to data that reside on the nodes of a graph G, denoted by X E NC with the i-th row representing the C-dimensionall graph signal on the i-th node of V.
3.2 TOPOLOGY TRANSFORMATION
We define the topology transformation t as adding or removing edges from the original edge set E in graph G. This can be done by sampling, i.i.d., switch parameter ai,j as in (Velickovic et al. 2019). which determines whether to modify edge (i,j) in the adjacency matrix. Assuming Bernoulli distribution B(p), where p denotes the probability of each edge being modified, we draw a random matrix Σ = {oIJ)NNN from B(p), i.e., Σ~ B(p). We then acquire the perturbed adjacency matrix as
where @ is the exclusive OR (XOR) operation. This strategy produces transformed graph through the topology transformation t, i.e., A t(A). Here, the edge perturbation probability of p 0 corresponds to a non-transformed adjacency matrix, which a special case an identity transfor- mation to A.
The transformed adjacency matrix can also be written as the sum of the original adjacency matrix A and topology perturbation matrix AA:
Ā A AA
3

---

Under review as a conference paper at ICLR 2021
where AA {dat,} NxN encodes the perturbation of edges, with da,,; [-1,0,1}, 13. As shown in Fig. [ when dag.j = 0, the edge between node and node j keeps unchanged (i.e., black solid lines); when òي..j -1 or 1, it means removing (i.e., orange dotted lines) or adding (L.e. blue solid lines) the edge between node and node j. respectively.
3.3 THE FORMULATION OF TOPOTER
Definition 1 Given pair of graph signal and adjacency matrix (X, A), and pair of graph signal and transformed adjacency matrix (X,A) by a topology transformation t(-). function E(-) is transformation equivariant if satisfies
E(X,A) = E(X,(A) p(t) ((t))
(3)
where p(t)({] is a homomorphism of transformation in the representation space.
Let us denote H A), and H A). We seek learn an encoder E (X, H: (X. + H that maps both the original and transformed sample to representations (H, H) equivariant to the sampled transformation t, whose information thus be inferred from the rep- resentations via a decoder D (H, H) ~ A as much as possible. From an information-then -ethorrtcc perspective, this requires (H, A should jointly contain all necessary information about H.
Then natural choice formalize the topology transformation equivariance is the matual infor- mation (H, AA; H) between (H, AA) and H. The larger the mutual information is, the more knowledge about AA can be inferred from the representations {H, H). Hence, we propose to max- imize the mutual information learn the topology transformation equivariant representations as follows:
T(H, AA; H),
where 8 denotes the parameters of the auto-encoder network.
Nevertheless, it is difficult to compute the mutual information directly. Instead, we derive that maximizing the mutual information can be relaxed to minimizing the cross entropy, as described in the following theorem.
Theorem The maximization of the mutual information I(H, AA; can be relaxed to the min- imization of the cross entropy (pp || q) between the probability distributions p(AA, H, H) and
q( (H.
min H (P(AA, H. H) (AAAH,
E ((AHHH
log a( H,
(5)
0
Proof By using the chain rule of mutual information, have
AH, H) ((A;:HHH) ((H H) 2 T(AA;
Thus the mutual information I(AA; H)) the lower bound of the mutual information [H, AA; H) that attains its minimum value when (H; 0.
Therefore, relax the objective to maximizing the lower bound mutual information 1(AA; H between the transformed representation and the topology transformation AA:
1 (AA; H = ((АA)) (AAA H),
where H(-) denotes the conditional entropy. Since AA and H are independent, we have H(A H = H(AA). Hence, maximizing I(AA; H[H) becomes
min H H(
(6)
8
According to the chain rule of conditional entropy, we have
H H(AA, H H H) < (/A,,H,H)

---

Under review as a conference paper at ICLR 2021
Encoder E())
Decoder D
(X, A)
GCNN
H E MRF
sharednweights
Minus
AH RN
Construct Edge
Linear
AA
Representation
(x, A)
GCNN
H E PXP
Figure 2: The architecture of the proposed TopoTER.
where the conditional entropy
H, H) upper bounded by the joint entropy H(AA, H. H).
Thus, the minimization problem in Eq. 6 becomes
min H,
We next introduce a conditional probability distribution q( Q(AA H) approximate the intractable posterior 7( ((A) H, H) with an estimated AA. According to the definition of the Kullback-Leibler divergence, we have
H(AA,H,H) H()) = H( 1l - (x (1 S (pp g).
where (K q) denotes the Kullback-Leibler divergence of and q that is non-negative, and (p ll q) is the cross entropy between p and q. Thus, Eq. (6) is converted to minimizing the cross entropy the upper bound:
min H (P(AA, ( (
E
log 7( H))
Hence, relax the maximization problem in Eq. (4) to the optimization in Eq. 5
Based on Theorem 1, we train the decoder to learn the distribution q( (AAHH H) so as esti- mate the topology transformation ÁA from the encoded (H, H}. where the input pairs of original and transformed graph representations {H, H} as well as the ground truth target AA can be sam- pled tractably from the factorization of p( AA, H. H) & (P) AA H). This allows us to minimize the cross entropy between p AA H. H) and (AA H as in ( with the training triplets (H, H; AA) drawn from the tractable factorization of p (AA H. H). Hence, we formu- late the ToRoTER as the joint optimization of the representation encoder E and the transformation decoder D.
3.4 THE ALGORITIM
We design graph-convolutional auto-encoder network for the TopoTER learning, as illustrated in Fig. 2 Given graph signal X associated with graph g = (V, E, A}, the proposed unsuper- vised learning algorithm for the TopoTER consists of three steps: 1) topology transformation, which samples and perturbs some edges from to acquire transformed adjacency matrix A; 2) repre- sentation encoding, which extracts the feature representations of graph signals before and after the topology transformation; 3) transformation decoding, which estimates the topology transformation parameters from the learned feature representations. We elaborate the three steps follows.
Topology Transtormation. We randomly sample a subset of edges from for topology certurbation-addee
removing edges, which not only enables to characterize local graph struc- tures at various scales, but also reduces the number of edge transformation parameters to estimate for computational efficiency. In practice, each iteration of training, we sample all the node pairs with connected edges S,, and randomly sample a subset of disconnected node pairs So, i.e.,
So (i.j) = 0) S₁ {ii.))aa. = =}.
(8)
where Sol |S1| = M. Next, we randomly split Sn and S into two disjoint sets, respectively, i.e.
S. = (1) ((2) ( ( s.S!") us!²) = S., (S r r.:S:. iE (0,
(9)
5

---

Under review as a conference paper at ICLR 2021
where is the edge perturbation rale. Then, for each node pair (i in 56" and s we slip the corresponding entry in the original graph adjacency matrix. That is, if dij = 0, then we set
Ji 1; otherwise, we set āi, O. For each node pair (i.j) j) in S and s we keep the original connectivities unchanged, i.e., 0i.j = Dz,j
This leads the transformed adjacency matrix A, as well the sampled transformation parameters by accessing A at position (i.j) from So and Sj. Also, we can category the sampled topology transformation parameters into four types:
add an edge to disconnected node pair, ie., (t: (z.j =., {
2. delete the edge between connected node pair, i.e., {t 01j 1 1 - 0, (1.5) E s(
3. keep the disconnection between node pairs in s/²) i.e. {t aij = 0 ã., 0, (i.j) E }
4. keep the connection between node pairs in ((2) L.e. {t ai. = 1 ر.ةة = 1, (i.j) s(
Thus, we cast the problem of estimating transformation parameters in AA from (H, H) as the classification problem of the transformation parameter types. The percentage of these four types is r: rr:: (1 r1-r): r1-
Representation Encoder. We train encoder F (X FXX,, A) encode the feature representations of each node in the graph. As demonstrated in Fig. 2 we leverage GCNNs with shared weights to extract feature representations of each node in the graph signal. Taking the GCN (Kipf & Welling 2017) as an example, the graph convolution in the GCN is defined as
(10) where D is the degree matrix of A I, W E RCF is a learnable parameter matrix, and H [hi,... ..., hy] T E RxF denotes the node-wisg wise feature matrix with F output channels. Similarly, the node feature of the transformed counterpart is follows with the shared weights W.
= = - IA+IID XW,
E = - + DD XXW
(11)
= F (A IJD Xww + - AAD XwW.
We thus acquire the feature representations H and H of graph signals before and after topology transformations.
Transformation Decoder. Comparing Eq. 10 and Eq. IT.. the prominent difference between H and H lies in the second term of Eq. 11 featuring AA. This enables to train decoder D (H, H) + AA estimate the topology transformation from the joint representations before and after transformation. We first take the difference between the extracted feature representations before and after transformations along the feature channel,
AH = H H [ōh]..., ōhN]T E N
(12)
Thus, we can predict the topology transformation between node and node j through the node-wise feature difference AH by constructing the edge representation
exp (5h; oh,) o (ōh; oh,)} E RR,, v(i.j) E S. US, e exp Jh @ (ōh, 8h,)
(13)
where @ denotes the Hadamard product of two vectors to capture the feature representation, and || || is the f--orrm of vector for normalization. The edge representation ei, of node i and is then fed into several linear layers for the prediction of the topology transformation,
Vi.j = softmax (l)near(e),)),
v(i,)) E SoUS,
(14)
where softmax(() an activation function.
According to Eq. (5) the entire auto-encoder network is trained by minimizing the cross entropy
3
L =
E
Σ
( Vi
log v Vij.
(15)
(8J))8,US)
1=0
where / denotes the transformation type (/ 10, (0 or 1) for each transformation parameter type.
2, 3)), and y is the ground-truth binary indicator

---

Under review as a conference paper at ICLR 2021
Table I: Node classification accuracies (with standard deviation) in percentage three datasets.
X, A, Y denote the input data, adjacency matrix and labels respectively.
Method
Training Data
Cora
Citeseer
Pubmed
Semi-Supervised Methods
GCN
(Kipf
X.
81.5
MoNei Monti al
7
X. A Y
0.5
78.8 0.3
GAT Varekovee at 2018)
X.
0.7
72.5 0.7
79.0 0.3
SGC Wa et al 2019
X. A. Y
8.0
71.9
78.9 + 0.0
GWNN Xu el X7 9u
X. A,
82.8
71.7
79.1
MixHop
2019
X. A,
0.4
0.8
0..
DFNel Wigesinghe & Wang 2019)
X, A, Y
85.2 1: 0.5
74.2 a 0.3
84.3 d. 0.4
Unsupervised Methods
Raw Features Velickovic
X
0.4
49.3
69.1 0.3
DeepWalk Perezzi et al 2014
A
67.2
43.2
65.3
DeepWalk Fealures Velickovic
X.
0.6
GAF
Kinf & Welling 2016
X, A
4.4
66.7 0.4
77.1 + 0.7
VGAE Kapt & Welling 2016
X.
80.0
64.1
76.9 0.1
DGI Velickovic
2019
X.
A
81.1 0.1
71.4
77.0 1 0.2
GMI (Pegg ctall 2021
X,
82.2
0.5
78.5 0.1
TopoTER
X.
83.7
7.11 0.5
Table 2: Model size comparison DGI, GMI, and the proposed TopoTER.
Model
DGI
GMI
TopoTER
of Parameters
906, 354
730,
736, 260
4 EXPERIMENTS
4.1 NODE CLASSIFICATION
Datasets. We adopt three citation networks to evaluate model: Cora, Citeseer, and Pubmed (Sen et al. 2008), where nodes correspond to documents and edges represent citations. We follow the standard train/test split in (Kipf & Welling, 2017) conduct the experiments.
Implementation Details. In this task, the auto-encoder network is trained via Adam optimizer, and 10-4 We the same early stopping strategy as DGI (Velickovic al. 2019) on the observed training loss, with patience of 20 epochs. We deploy one Simple Graph Convolution (SGC) layer (Wu et al.] 2019) as our encoder, and the order of the adjacency matrix is set to 2, while we will study the order of the adjacency matrix in Appendix A The LeakyReLU activation function with a negative slope of 0.1 employed after the SGC layer. Similar to DGI Velickovic et al.) 2019), we set the output channel F = 512 for Cora and Citeseer dataset, and 256 for Pubmed dataset due to memory limitations. After the encoder, we use one linear layer to classify the transformation types. We set the edge perturbation rate in Eq. (9) as {0.7, 0.4, 0.7) for Cora, Citeseer, and Pubmed, respectively. The analysis of the edge perturbation rate will be presented in Appendix B
the learning rate
During the training procedure of the classifier, the SGC layer in the encoder is used to extract graph feature representations with the weights frozen. After the SGC layer, apply one linear layer to map the features to the classification scores.
Experimental Results. We compare the proposed method with five unsupervised methods, includ- ing one node embedding method DeepWalk, two graph auto-encoders GAE and VGAE (Kipf & Welling 2016), and two contrastive learning methods DGI (Velickovic al. 2019) and GMI (Peng et al. 2020). Additionally, we report the results of Raw Features and Deep Walk alk Features (Perozzi al. 2014) under the same settings. For fair comparison, the results of all other unsupervised meth- ods are reproduced by using the same encoder architecture of the TopoTER except DeepWalk and Raw Features. We report the mean classification accuracy (with standard deviation) on the test nodes for all methods after 50 runs of training. As reported in Tab. 1 the TopoTER outperforms all other competing unsupervised methods on three datasets. Further, the proposed unsupervised method also achieves comparable performance with semi-supervised results. This significantly closes the gap between unsupervised approaches and the semi-supervised methods.
Moreover, compare the proposed TopoTER with two contrastive learning methods DGI and GMI in terms of the model complexity, as reported in Tab. 2 The number of parameters in our model is less than that of DGI and even less than half of that of GMI, which further shows the TopoTER model is lightweight.
7

---

Under review as a conference paper at ICLR 2021
Table 3: Graph classification accuracies (with standard deviation) in percentage 6 datasets. ">
Day" represents that the computation exceeds 24 hours. "OOM" is out of memory error.
Dataset
MUTAG
PTC-MR
RDT-B
RDT-M5K
IMDR-B
IMDB-M
(No. Graphs)
2000
4999
1000
1500
(No. Classes)
5
Graph Kernel Methods
RW
83.72 = 1.50
57.85 + 1.30
0OM
0OM
50.68 0.26
31.65
: 0.19
SP
85.22 1 2.43
56.24 1: 2.44
64.11
0.14
39.55
0.22
55.60 + 0.22
37.99
1 0.30
GK
81.66
2.11
57.26
1: 1.41
77.34
1: 0.18
41.01
0.17
65.87 0.98
43.89
1: 0.38
WL
80.72
3.00
57.97
0.49
68.82
0.41
46.06
0.21
72.30
3.44
46.95
- 0.46
DGK
87.44 1 2.72
60.08
1: 2.55
78.04 1 0.39
41.27
0.18 Day
66.96 1. 0.36
44.55
1 0.52
MLG
87.94 4: 1.61
63.26 + 1.48
Day
66.55 0.25
41.177 + 0.03
Supervised Methods
GCN
85.6
61.2 133
50.0 = 0.0
20.0 0.0
71.0 3.0
51.9 3.8
GraphSAGE
63.9 7.7
GIN.0
89.4 5.6
64.6 +: 7.0
92.4 + 2.5
57.5 4: 1.5
76. + 5.1
52.3 1 2.8
GIN-c
89.0 6.0
63.7 +: 8.2
92.2 2.3
$7.0 :: 1.7
74.3 5.1
52.1 + 3.6
Unsupervised Methods
node2vec
72.63 10.20
58.58 + 8.00
sub2vec
61.05
15.80
59.99 - 6.38
71.48 0.41
36.08 0.42
55.26 + 1.54
36 + 0.83
graph2vec
83.15 + 9.25
60.17 = 6.86
75.78
= 1.03
17.86
0.26
71.10 = 0.34
50.44 + 0.87
InfoGraph
89.01 + 1.13
61.65 + 1.43
82.50
= 1.42
53.46 1.03
73.03
0.87
49.69 + 0.53
TopoTER
64.59
84.93
0.18
73.46
4.2 GRAPH CLASSIFICATION
Datasets. We conduct graph classification experiments on six well-known graph benchmark datasets (Yanardag & Vishwanathan 2015)): MUTAG, PTC, REDDIT-BINARY, REDDIT-MULTI- 5K,
and IMDB-MULTI.
Implementation Details. In this task, the entire network is trained via Adam optimizer with a batch size of 64, and the learning rate is set to 10-3, For the encoder architecture, we follow the same encoder settings in the released code of InfoGraph (Sun et al.) (220a)), i.e. three Graph Isomorphism Network (GIN) layers (Xu et al. 2019b) with batch normalization. We also use one linear layer to classify the transformation types. We set the sampling rate 0.5 for datasets.
During the evaluation stage, the entire encoder will be frozen to extract node-level feature repre- sentations, which will go through global add pooling layer to acquire global features. We then use LIBSVM to classify these global features to classification scores. We adopt the same procedure of previous works (Sun al., 2020a) to make a fair comparison and use 10-fold cross validation accuracy to report the classification performance, and the experiments repeated five times.
Experimental Results. We take six graph kernel approaches for comparison: Random Walk (RW) Gärtner et al. 2003). Shortest Path Kernel (SP) (Borgwardt & Kriegel, 2005), Graphlet Kernel Sub-tree Kernel (WL) (Shervashidze et al. 2011). Deep Graph Kernels (DGK) (Ynarrdag & Vishwanathan 2015). and Multi-Scale Laplacian Kernel (MLG) (Kondor & Pan 2016). Aside from graph kernel methods, we also compare with three unsupervised grael representation learning methods: node2vec (Grover & Leskoved 2016), sub2vec (Adhikari et al. 2018)) and graph2vec (Narayanan et al. (2077), and one contrastive learning method: InfoGraph (Sun et al. 2020a).. The experimental results of unsupervised graph classification are preseted in Tab. The proposed TopoTTRR outperforms all unsupervised bascline methods on the first five datasets, and achieves comparable results on the other dataset. Also, the proposed approach reaches the performance of supervised methods at times, thus validating the effectiveness of the TopoTER model.
(GK)
SServvsshidze et al.) 2009). Weisfeiler-
CONCLUSION
We propose Topology Transformation Equivariant Representation (TopoTER) for learning unsu- pervised representations on graph data. By maximizing the mutual information between topology transformations and feature representations before and after transformations, the TopoTER enforces the encoder learn intrinsic graph feature representations that contain sufficient information about structures under applied topology transformations. We apply the TopoTER model to node classifi- cation and graph classification tasks, and results demonstrate that the Topo outperforms state- of-the-art unsupervised approaches and reaches the performance of supervised methods at times.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Sami Abu-EI-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In Proceedings of the 36th International Con- ference on Machine Learning (ICML), pp. 21-29, 2019.
Bijaya Adhikari, Yao Zhang, Naren Ramakrishnan, and B Aditya Prakash. Sub2vec: Feature learn- ing for subgraphs. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp. 770-182. Springer, 2018.
Karsten M Borgwardt and Hans-Peter Kriegel. Shortest-path kernels graphs. In IEEE Interna- tional Conference on Data Mining (ICDM), pp. 8-pp. IEEE, 2005.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geomet- ric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18-44 2017.
Shaosheng Cao,, Wei Lu, and Qiongkai Xu. Deep neural networks for learning graph representations. In Proceedings of the AAAI Conference Artificial Intelligence (AAAI), volume 16, pp. 1145- 1152, 2016.
Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for unsu- pervised learning of visual features. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 132-149, 2018.
Taco Cohen and Max Welling, Group equivariant convolutional networks. Proceedings of the 33rd International Conference on Machine Learning (ICML), pp. 2990-2999, 2016.
Nicola De Cao and Thomas Kipf. MolGAN: An implicit generative model for small molecular
graphs. In International Conference on Machine Learning Workshop on Theoretical Foundations and Applications of Deep Generative Models, 2018.
Pim de Haan, Maurice Weiler, Taco Cohen, and Max Welling. Gauge equivariant mesh cnns: Anisotropic convolutions geometric graphs. arXiv preprint arXiv:2003.0544 2020.
Sander Dieleman, Kyle Willett, and Joni Dambre. Rotation-invariaal convolutional neural net- works for galaxy morphology prediction. Monthly Notices of the Royal Astronomical Society, 450
(2):1441-1459, 2015.
Sander Dieleman, Jeffrey De Fauw, and Koray Kavukcuoglu. Exploiting cyclic symmetry in convo- lutional neural networks. In International Conference on Machine Learning (ICML), pp. 1889- 1898, 2016.
Fabian B Fuchs, Daniel E Worrall, Volker Fischer, and Max Welling, Se tranfffrrrr::::::: 3d roto- translation equivariant attention networks. arXiv preprint arXiv:2006. 20X0:00006.1003,, 2020.
Xiang Gao, Wei Hu, and Guo-Jun Qi. GraphTER: Unsupervised learning of graph transforma- tion equivariant representations via auto-encoding node-wise transformations. In Proceedings of IEEE/CVF Conferences Computer Vision and Pattern Recognition (CVPR), 2020.
Thomas Gärtner, Peter Flach, and Stefan Wrobel. On graph kernels: Hardness results and efficient alternatives. In Learning Theory and Kernel Machines, pp. 129-143. Springer, 2003,
Robert Gens and Pedro M Domingos. Deep symmetry networks. In Advances Neural Information Processing Systems (NIPS), pp. 2537-2545, 2014.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 855-864, 2016.
Geoffrey E Hinton, Alex Krizhevsky, and Sida D Wang. Transforming auto-encoders. Interna- fional Conference on Artificial Neural Networks (ICANN), pp. 1.-5ingrringer 2011.

---

Under review as a conference paper at ICLR 2021
R Devon Hjelm, Alex Fedorov, Samuel Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. In International Conference on Learning Representations (ICLR), 2018.
Karan Grewal, Phil Bachman, Adam
Thomas N Kipf and Max Welling. Variational graph auto-encoders. In Proceedings of the NIPS
Workshop on Bayesian Deep Learning, 2016.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. In International Conference on Learning Representations (ICLR), 2017.
Jyri J Kivinen and Christopher KI Williams. Transformation equivariant boltzmann machines. In International Conference Artificial Neural Networks (ICANN), pp. 1-9. Springer, 2011.
Risi Kondor and Horace Pan. The multiscale laplacian graph kernel. In Advances in Neural Infor- mation Processing Systems (NIPS), pp. 2990-2998, 2016.
Karel Lenc and Andrea Vedaldi. Understanding image representations by measuring their equivari- ance and equivalence. In Proceedings of the IEEE Conference on Computer Vision and Patlern Recognition (CVPR), pp. 991-999, 2015.
Jan Bric Lenssen, Matthias Fey, and Pascal Libuschewski. Group equivariant capsule networks. In Advances in Neural Information Processing Systems (NIPS), pp. 8844-8853, 2018.
Xiao Liu, Fanjin Zhang, Zhenyu Hou, Zhaoyu Wang, Li Mian, Jing Zhang, and Jie Tang. Self- supervised learning: Generative or contrastive. arXiv, pp. arXiv-2006, 2020.
Tengfei Ma, Jie Chen, and Cao Xiao. Constrained generation of semantically valid graphs via regularizing variational autoencoders. In Advances in Neural Information Processing Systems (NIPS), pp. 7113-7124. 2018.
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model enns. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 5115-5124, 2017.
Annamalai Narayanan, Mahinthan Chandramoban, Rajasekar Venkatesan, Lihui Chen, Yang Liu, and Shantanu Jaiswal. graph2vec: Learning distributed representations of graphs, In Proceedings of the 13th International Workshop on Mining and Learning with Graphs (MLG), 2017.
Zhen Peng, Wenbing Huang, Minnan Luo, Qinghua Zheng, Yu Rong, Tingyang Xu, and Junzhou Huang. Graph representation learning via graphical mutual information maximization. In Pro- ceedings of The Web Conference, pp. 259-270, 2020.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 701-710, 2014.
Guo-Jun Qi, Liheng Zhang, Chang Wen Chen, and Qi Tian. AVT: Unsupervised learning of transfor- mation equivariant representations by autoencoding variational transformations. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2019a.
Guo-Jun Qi, Liheng Zhang, and Xiao Wang. Learning generalized transformation equivariant rep- resentations via autoencoding transformations. arXiv preprint arXiv: /906. 08628, 2019b.
Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang, Ming Ding, Kuansan Wang, and Jie Tang. Gcc: Graph contrastive coding for graph neural network pre-training. In Pro- ceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 1150-1160, 2020.
Uwe Schmidt and Stefan Roth. Learning rotation-awart features: From invariant priors to equivari- ant descriptors. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recog- nition (CVPR), pp. 2050-2057. IEFF, 2012.
10

---

Under review as a conference paper at ICLR 2021
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rads. Collective classification in network data. Al magazine, 29(3):93 93, 2008.
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mchlhorn, and Karsten Borgwardt. Ef- ficient graphlet kernels for large graph comparison. In Artificial Intelligence and Statistics, pp. 488-495, 2009.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borg- wardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. In International Conference on Artificial Neural Networks (ICANN), pp. 412-422. Springer, 2018.
Henrik Skibbe. Spherical Tensor Algebra for Biomedical Image Analysis. PhD thesis, Verlag nicht ermittelbar, 2013.
Kihyuk Sohn and Honglak Lee. Learning invariant representations with local transformations. In International Conference on Machine Learning (ICML), pp. 1339-1346, 2012.
Fan-Yun Sun, Jordan Hoffmann, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi- supervised graph-level representation learning via mutual information maximization. In Interna- fional Conference on Learning Representations (ICLR), 2020a.
Ke Sun, Zhouchen Lin, and Zhanxing Zhu. Multi-stage self-supervised learning for graph convo- lutional networks graphs with few labeled nodes. In Proceedings of the AAAI Conference Artificial Intelligence (AAAI), pp. 5892-5899, 2020b.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations (ICLR), 2018.
Petar Velickovic, William Fedus, William Hamilton, Pictro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In International Conference Learning Representations (ICLR), 2019.
Daixin Wang, Peng Cui, and Wenwu Zhu, Structural deep network embedding. In Proceedings of the 22nd ACM SIGKDD International Conference Knowledge Discovery and Duta Mining, pp. 1225-1234, 2016.
Jayy Wang, Wengang Zhou, Guo-Jun Qi, Zhongqian Fu, Qi Tian, and Houqiang Li. Transforma- tion gan for unsupervised image synthesis and representation learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 472-481, 2020.
WOK Asiri Suranga Wijesinghe and Qing Wang- Dfnets: Spectral cnns for graphs with feedback- looped filters. In Advances in Neural Information Processing Systems (NIPS), pp. 6009-6020 2019.
Felix Wu, Tianyi Zhang. Amauri Holanda de Souza Jr. Christopher Fifty, Tao Yu. and Kilian Q Weinberger. Simplifying graph convolutional networks. In Proceedings of the 36th International Conference on Machine Learning (ICML), pp. 6861-6871, 2019.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Yu Philip. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2020.
Bingbing Xu, Huawei Shen, Qi Cao, Yunqi Qiu, and Xueqi Cheng. Graph wavelet neural network. In International Conference on Learning Representations (ICLR), 2019a.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations (ICLR), 2019b.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1374-1374, 2015.
11

---

Under review as a conference paper at ICLR 2021
Jiaxuan You, Rex Ying, Xiang Ren, William L Hamilton, and Jure Leskovec. Graphrnn: Generat- ing realistic graphs with deep rege-seeressive models. In Proceedings of the 35th International Conference on Machine Learning (ICML), pp. 5694-5703, 2018.
Liheng Zhang, Guo-Jun Qi. Liqiang Wang, and Jiebo Luo. AET AED: Unsupervised represen- tation learning by auto-encoding transformations rather than data. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2547-2555, 2019.
12

---

Under review as a conference paper at ICLR 2021
A EXPERIMENTS ON DIFFERENT ORDERS OF THE ADJACENCY MATRIX
As presented in Sec. 3.2 we perturb the 1-hop neighborhoods via the proposed topology transfor-
mations, leading to possibly significant changes in the graph topology. This increases the difficulties of predicting the topology transformations when using one-layer GCN (Kipf & Welling. 2017) by aggregating the 1-hop neighborhood information. Therefore, we employ one Simple Graph Con- volution (SGC) layer (Wu et al., 2019) with order k as our encoder E(.), where the output feature representations aggregate molti-hop neighborhood information. Formally, the SGC layer is defined
H = FXX, A) = (D (A (D- (AA XW,
(16)
where is the degree matrix of A + I, W E RCXF is a learnable parameter matrix, and is the order of the normalized adjacency matrix.
To study the influence of different orders of the adjacency matrix, we adopt five orders from 1 to 5 to train five models the node classification task. Fig. 3 presents the node classification curacy under different orders of the adjacency matrix for TopoTER and DGI respectively. As we can see, the proposed TER achieves best classification performance when k 2,3 on the three datasets respectively. When k: = 1, our model still achieves reasonable results although it is difficult to predict the topology transformations from 1-hop neighborhood information: when k > 1, our proposed TER outperforms DGI by a large margin on Cora and Pubmed dataset, and achieves comparable results to DGI on Citeseer dataset. This is because DGI adopts feature shuffling to generate negative samples, which is insufficient to learn contrastive feature represen- tations when aggregating multi-hop neighborhood information, while TopoTER takes advantage of multi-hop neighborhood information predict the topology transformations, leading to improved performance.
86
73
ToPoTER
TopaTER
DGI
DGI
84
72
Accuracy
Accuracy
71
82
70
80
694
78
68
Order
Order
(a) Cora
(b) Citeseer
85
TEpoTER
DGI
Accuracy
88
75
70
2
Order
(c) Pubmed
Figure 3: Node classification accuracies under different orders of the adjacency matrix the Cora, Citeseer, and Pubmed datasets.
13

---

Under review as a conference paper at ICLR 2021
B EXPERIMENTS ON DIFFERENT EDGE PERTURBATION RATES
Further, we evaluate the influence of the edge perturbation rate in Eq. on the node classification task. We choose 11 edge perturbation rates from 0.0 1.0 an interval of 0.1 to train the proposed ToPoTER. We use one SGC layer as our encoder EC-), where the order of the adjacency matrix is set to As presented in Fig. the blue solid line with error bar shows the classification accuracy of our TopoTTRR under different edge perturbation rates. We also provide the classification accuracy on feature representations of graphs from randomly initialized encoder E-.), denoted Random Init,, which serves as the lower bound of the performance.
As we can see, the classification performance reaches the best when the graph perturbed under reasonable edge perturbation rate, e.g. r {0.6, 0.5, 0.6} for the Cora, Citeseer, and Pubmed dataset, respectively. When the edge perturbation rate r 0.0, the unsupervised training task of TopoTER becomes link prediction, which cannot take advantage of the proposed method by predicting the topology transformations; when the edge perturbation rate r 1.0, our TopoTER still achieves reasonable classification results, which shows the stability of our model under high edge perturbation rates. At the same time, we observe that the proposed TopoTER outperforms Random Init. by large margin, which validates the effectiveness of the proposed unsupervised training strategy.
TopoTER
I
Topo TER
85
Random
75
Random
Accurccy
Accuracy
70
80
65
75
60
70
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Perturbation Rate
Perturbation Rate
(a) Cora
(b) Citeseer
TopoTER Random Inil.
85
Accuracy
80
75
70
0.0
0.2
0.4
0.6
0.8
1.0
Perturbation Rate
(c) Pubmed
Figure 4: Node classification accuracies under different edge perturbation rates the Cora, Cite- seer. and Pubmed datasets.
14


Reviews:
[{"review_id": "rOxLjEneEyt", "reviewer": "AnonReviewer4", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper develops a framework for unsupervised learning of graphs. The goal is to build graph representation using an encoder that is useful for downstream tasks such as graph classification. The representation is computed with an encoder $E$ applied to a graph data $(X,A)$, containing vertex data $X$ and adjacency matrix $A$. Given a graph $(X,A)$ and a perturbed version of its adjacency matrix $(X,\\tilde{A)}$, the decoder $D$ is tasked with minimizing the conditional entropy, $h(\\Delta A \\vert H,\\tilde{H})$, of the perturbation $\\Delta A = A-\\tilde{A}$ when given the two representations $H=E(X,A)$ and $\\tilde{H}=E(X,\\tilde{A})$. \n\nThis feels as a solid paper, however it is very similar to GraphTER (Gao et al. 2020), which as far as I can tell is a previous work. Let me detail the similarities. The GraphTER paper already defines the same encoder-decoder structure and training the decoder to infer the perturbation in the graph. The GraphTER  considers perturbation of node data $X$, but also perturbation of adjacency matrix since they define the adjacency matrix as a function of the node data, that is $\\tilde{A}=f(\\tilde{X})$. The current paper focuses only on adjacency perturbations. A second difference is that GraphTER uses the decoder to predict the perturbation directly, while the current paper asks the conditional entropy of the perturbation given the representations of the graph or its perturbation to be as small as possible (or the mutual information formulation). I don't see the benefit in the new loss formulation - if there is such a benefit it should be highlighted and demonstrated. Anyway, these two differences between the papers seem rather minor. \n\nOther comments/questions:\n\n-- What can be said about the equivariance of the learned encoder? Is there a way to quantify how equivariant is it? Why, if the loss that is optimized is equation 6, one would even expect equivariance? I mean, low entropy could maybe imply some unknown transformation of the perturbation. This should be explained. \n\n-- Why not formulate the loss directly as in equation 6 (conditional entropy of the perturbation) if this is in practice what is optimized? What is the benefit in going through the mutual information formulation?\n\n-- In the experiments part: how is the linear classifier in section 4.1 trained (after fixing the encoder)? Same question about the SVM in section 4.2? If indeed these classifiers are trained with labeled data - why is this method is called unsupervised? I am confused by that part. For example, in Table 1 it is emphasized that TopoTER does not use labels $Y$.\n\n-- Is the encoder only one layer of GNN as in equation 11? Did you try with deeper architectures? \n\nUPDATE: I would like to thank the authors for their rebuttal. I have read it, however unfortunately, I am not convinced the indicated differences from previous work is sufficient to warrant publication at ICLR. I am also not completely clear about the equivariance point. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "G0NfFyS15d-", "reviewer": "AnonReviewer2", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents the Topology Transformation Equivariant Representation (TopoTER) as a learning method for the (uncommonly) unsupervised learning of node representations  in graphs, with applicability to Graph Convolutional Neural Networks.\nThe paper falls well within the scope of the conference.\nIts writing could be improved and would benefit from a thorough language revision.\nThe contribution is well grounded, the state-of-the-art is appropriately identified and even though its novelty is somehow incremental, its value seems beyond doubt.\nTo the best of my knowledge, and not being an expert on graph data analysis, the maths seem sound.\nThe experimental work, including comparison with alternative approaches is quite detailed (and well-informed of the competition).\nAdding extra experiments as an appendix ... I guess it verges on cheekiness, but given, the particularities of accepted formats, assume it is fine.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "AkGMoxqEFiD", "reviewer": "AnonReviewer1", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "#### Goal\n\n- This work considers the graph task of learning node representations that are invariant to small edge perturbations. It achieves this through a data augmentation procedure that samples new “fake” edges and regularizes the GNN equivariant representations to be unable to predict these fake edges. Overall it is an interesting idea.\n\n#### Quality\n\nThe paper is reasonably well written, except for the introduction, which throws too much jargon around without being concrete about the work’s goals. \n\nMathematically, I have doubts about the correctness of the work (see Cons)\n\n\n#### Clarity\n\nIt is a little confusing how we can obtain the fake/deleted edge probabilities p. Earlier in the paragraph there is a connection with GAT but GAT has an attention mechanism to obtain \\p_{ij}. While the first paragraph of 3.2 states the fake “edges” are given by a random matrix \\Sigma obtained from a Bernoulli distribution with parameter p. I am not sure what that means. The elements of \\Sigma are i.i.d. samples from a Bernoulli distribution? I am not familiar with Bernoulli distributions that sample entire random matrices.\n\n\nThe graph is defined with an edge set, \\mathcal{E}, and an adjacency matrix A. It is unclear why we need these structures to define a single graph. Isn’t A fully determined by \\mathcal{E}? If not, why not? It would be good to clarify.\n\n- The transformation $t$ and its homomorphism \\rho are given in Def 1 but not given a formal definition later in the paper. In the proposed algorithm in Section 3.4, what are t and \\rho?\n \n#### Originality\n\nThere is some level of originality, although there are too many papers in GNNs doing similar things to know for sure. It claims to be an edge extension of a previous work for nodes.\n\n\n#### Significance\n\nOverall, the work does not really bring much to the table. Robustness to a certain type of edge noise could be interesting, but the choice of noise process is probably very important. The noise process is not discussed in depth. Data augmentation (just adding the new perturbed graph as a data example) is the main competitor to this approach. The difference between what the authors did and data augmentation should be front and center at the experimental evaluation.\n\n\n#### Pros\n\n- The paper central idea applies invariant representations to make the GNN representation more robust to noise\n\n#### Cons\n\n- Predicting edges with equivariant node representations is provably impossible (Srinivasan & Ribeiro, 2020). The Representation Encoder looks like an equivariant node representation to me. Hence, the “Transformation Decoder” is attempting a provably impossible task. Remark 1 in (Srinivasan & Ribeiro, 2020) gives an interesting comment to why GraphSAGE is successful even if it was trying the same impossible task. The authors need to give a solid theoretical reason for their approach, otherwise it is not believable.\n\nThe main competitor of this approach is data augmentation. GraphSAGE has an unsupervised version that also adds fake edges at random as a form of data augmentation. \n\nSrinivasan, Balasubramaniam, and Bruno Ribeiro. \"On the Equivalence between Positional Node Embeddings and Structural Graph Representations.\" In International Conference on Learning Representations. 2020.\n\n\n#### Other comments\n\n- In Franceschi et al., 2019,  the authors also want to learn the underlying graph (which edges are fake, which are true). It seems that their approach could be applied in the framework of this work, and would maybe give a better way to sample the fake edges. \n\nFranceschi, Luca, Mathias Niepert, Massimiliano Pontil, and Xiao He. \"Learning discrete structures for graph neural networks.\" ICML (2019).\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "0AsbYbsOHe8", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper propose an unsupervised method for self-training of graph-neural-networks (GNNs). The authors provide information-theoretic justification to their method using maximization of the lower bound of the mutual information on their objective. Their approach is based on maximizing the mutual information between a perturbed graph topology and its node representation.\n\nStrong points:\n- very good results (some of the results are comparable to supervised method and the improvement achieved on the other unsupervised methods is significant)\n- simple approach with theoretical justification\n- paper is nicely written and easy to follow", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper is concerned with learning transformation equivariant node representation of graph data in an unsupervised setting. The paper extends prior work in this topic by focusing on equivariance under topology transformations (adding/removing edges) and considering an information theoretic perspective. Reviewers highlighted the promising ideas of the approach, its relevance for the ICLR community, and the promising experimental results (although improvements over prior work are not necessarily significant on all benchmarks).

However, reviewers raised concerns regarding the novelty of the method and the clarity of presentation with respect to key parts of the method. These aspects connect also to further concerns raised, e.g., related to mathematical correctness as well as the significance of the proposed loss function, the benefits of motivating it from MI, and the improvements over GraphTER. The rebuttal didn't fully clarify these points. While the paper is mostly solid, I agree with the reviewers' concerns and -- currently -- the paper doesn't clear the bar for acceptance; it would require another revision to improve upon these points. However, I'd encourage the authors to revise and resubmit their work with considering this feedback.
Decision: Reject