GraphSAD: Learning Graph Representations with Structure-Attribute Disentanglement
Authors: Minghao Xu
Hang Wang
Bingbing Ni
Wenjun Zhang
Jian Tang
Venue:  (2021)
Keywords: Graph Representation Learning
Disentangled Representation Learning

Abstract: Graph Neural Networks (GNNs) learn effective node/graph representations by aggregating the attributes of neighboring nodes, which commonly derives a single representation mixing the information of graph structure and node attributes. However, these two kinds of information might be semantically inconsistent and could be useful for different tasks. In this paper, we aim at learning node/graph representations with Structure-Attribute Disentanglement (GraphSAD). We propose to disentangle graph structure and node attributes into two distinct sets of representations, and such disentanglement can be done in either the input or the embedding space. We further design a metric to quantify the extent of such a disentanglement. Extensive experiments on multiple datasets show that our approach can indeed disentangle the semantics of graph structure and node attributes, and it achieves superior performance on both node and graph classification tasks.

Under review as a conference paper at ICLR 2021
GRAPHSAD: LEARNING GRAPH REPRESENTATIONS WITH STRUCTURE- ATTRIBUTE
STRUCTURE-ATTRIBUTE DISENTANGLEMENT
Anonymous authors
Paper under double-blind review
ABSTRACT
Graph Neural Networks (GNNs) learn effective node/graph representations by aggregating the attributes of neighboring nodes, which commonly derives a sin- gle representation mixing the information of graph structure and node attributes. However, these two kinds of information might be semantically inconsistent and could be useful for different tasks. In this paper, we aim learning node/graph representations with Structure-Attribut Disentanglement (GraphSAD). We pro- pose to disentangle graph structure and node attributes into two distinct sets of representations, and such disentanglement can be done in either the input or the embedding space. We further design a metric to quantify the extent of such dis- entanglement. Extensive experiments can indeed disentangle the semantics of graph structure and node attributes, and it achieves superior performance on both node and graph classification tasks.
multiple datasets show that our approach
INTRODUCTION
Representing nodes or entire graphs with informative low-dimensional feature vectors plays crucial role many real-world applications and domains, e.g. user analysis in social networks (Tan al., 2011; Yan et al., 2013), relational inference in knowledge graphs (Bordes et al., 2013; Trouillon al., 2016; Sun al., 2019), molecular property prediction in drug/material discovery (Gilmer et al., 2017: Wu al., 201 8) and circuit response prediction in circuit design (Zhang et al., 2019). Recently, Graph Neural Networks (GNNs) (Kipf Welling, 2017; Velickovic et al., 2018: Xu al., 2019) have shown their superiority in many different tasks. In general, the essential idea of these methods to learn effective node representations (or graph representations with an additional graph pooling) through aggregating the attributes of each node and its neighbors in iterative and nonlinear way.
For an attributed graph, GNNs commonly encode the information of its graph structure and node attributes into a single representation. This might be problematic, since the semantic space of graph structure and node attributes might not be well aligned, and these two types of information could be useful for different tasks. For example, predicting the health condition of user mainly depends his/her profile information, and the social network does not provide too much meaningful informa- tion; in another case, the prediction of a user's social class mainly relies on his/her social network structure. Therefore. a more reasonable solution is to disentangle these two types of information into two distinct sets of representations, and the importance of which can be further determined by downstream tasks. Such disentangled representation has been proved to be beneficial to model's generalization ability and interpretability (Chen et al., 2016; Higgins al., 2017; Alemi al., 2017).
Recently, DisenGNN (Ma et al., 2019) studied disentangled node representation learning by group- ing the neighbors of each node different channels, and each channel corresponds a different latent factor. In other words, DisenGNN focuses on disentangling the various latent factors of graph structure. By contrast, our work intends to disentangle the representations of graph structure and node attributes, which is orthogonal to their work and also more general.
In this paper, we aim to learn node/graph representations with Structure-Attrinn Disentanglement (GraphSAD). As naive trial, we first attempt to conduct disentanglement in the input space, named as Input-SAD, which separates a graph into a structure and an attribute component and then encodes these two components respectively. However, since graph structure and node attributes are not completely independent, is better to suppress the dependency these two factors in the embedding space, instead of directly separating the input graph. Inspired by this fact, we propose distill

---

Under review as a conference paper at ICLR 2021
graph's 's structure and attribute information into the distinct channels of embedding vectors, named as Embed-SAD. Concretely, for each node embedding, half of its elements capture the graph structure through edge reconstruction, and the other half extracts the attribute information by minimizing the mutual information with the structure counterpart and, at the same time, preserving semantic discriminability. In addition, devise metric to quantitatively evaluate graph representation structure-attribut disentanglement, denoted as SAD-Metric, which measures the sensitivity of a model when varying either the graph structure or node attributes of an input graph.
We summarize our contributions as follows:
We study structure-attribute disentangled node/graph representation learning through sep- arating graph structure and node attributes either the input or the embedding space.
We design a quantitative metric measure the extent of cructure-attribute disentangle- ment, which is novel on its graph-specifer data processing scheme.
Through combining the proposed disentangling techniques with various GNNs, we empir- ically verify our method's superior performance both the node and graph classification benchmark datasets. Also, we analyze the disentangled graph representations via the pro- posed metric and qualitative visualization.
2 PROBLEM DEFINITION AND PRELIMINARIES
2. PROBLEM DEFINITION
We study learning node representations (e.g. social networks) or whole-graph representations (e.g. molecular graphs) of attributed graphs. Formally, we denote an attributed graph as (V, A). y denotes the set of nodes. & = {u,, v, buv)] is the set of edges with luo as the type of the edge connecting node u and (e.g. different types of bonds in molecular graphs). A (A.|u E V} represents the set of node attributes.
Our goal is to learn meaningful representations for each node or the whole graph. Existing GNNs typically mix both the graph structure and node attributes into unified representation through neu- ral message passing. However, in practice, these two types of information may encode different semantics and be useful for different tasks. Take the prediction
social networks When predicting the social class users, the graph structure plays a more important role than user attributes, while attributes are definitely more informative than graph structure when forecasting users' health conditions. It is therefore desirable to disentangle the information of graph structure and node attributes into different sets of representations and use the downstream task determine their importance. Specifically, we define our problem as follows:
example.
Node/Graph Representation Learning with Structure-Attributt Disentanglement. Given an attributed graph g = (V, E, A), we aim to learn node (or whole-graphe representations by disentan- gling the semantics of graph structure S [V and node attributes AA into two distinct sets of representations, í.e. = [ Ar.A] (or 2ς = s. A). The importance of the two kinds of representations is further determined by the downstream task such as node or graph classification.
2.2 PRELIMINARIES
Graph Neural Networks (GNNs). A GNN maps each node v E V to an embedding vector &, and also encodes the entire graph as vector zg- For I.-layer GNN, the L-hop information surrounding each node is captured via a neighborhood aggregation mechanism. Formally, the I-th GNN layer can be defined as:
COMBINE!") " AGGREGATEE (((=(11))
(1-1), fwo) MEN(w)))):
where (Vv) is the set of node v's neighbors, tue denotes edge attribute, (0) denotes the represen- tation of u at the I-th layer, and (!) initialized by the node attribute A... Using all the node embeddings in graph, the entire graph's 's embedding can be derived by permutation innvariaion-invaiiantt
readout function:
2g (DOUU((EEUE) v)).
2

---

Under review as a conference paper at ICLR 2021
(a) Input-SAD
GNN
Zy
sup
FCN
A
(b) Embed-SAD
2/.55
KEAKOOT
kg,5 ZV.A
Sup
GNN
45.4
9
Lecon
Is.A
Figure I: (a) Input-SAD model disentangles graph into structure and attribute component and encodes them separately. (b) Embed-SAD model distills the structure and attribute information of a graph into two distinct channels of embedding vectors.
Mutual Information Estimator. Mutual information (MI) quantifies the mutual dependency be- tween two random variables. Some recent works (Belghazi et al., 2018; Hjelm et al., 2019) studied neural-network-basse MI estimators. Among which, the Noise-Contrastive Estimation (NCH) (Gut- mann & Hyvärinen, 2010; 2012) was first employed as a lower bound of MI by van den Oord al. (2018), and we also adopt this estimator in our method for its effectiveness and concision. In prac- tice, for two random variables X1 and X2, given one positive pair (xī xx) ~ p(X1; X²) and K distractors (xt= X2.j) ~ p(x1)p(x22) (j = 1,2, K)), the NCE estimation of MI defined as:
exp (T(xT ,x,))
INCE (xt,xt [x2,) = log( K K+1)+log
(3)
exp (T(xi x5)) + Σラ exp (T(xi x2.)))
where -): parameterized discriminator function which outputs a scalar value for a pair of input samples, and its architecture is detailed in Sec.
3 LEARNING GRAPH REPRESENTATIONS WITH STRUCTURE-ATRIIUTT DISENTANGLEMENT
3.1 INPUT-SAD:
DISENTANGLEMENT FOR INPUTS
As an initial attempt, we seek to learn structure-attribute disentangled node/graph representations by separating a graph into structure and an attribute component and then encoding them respectively, as shown in Fig. I(a). Concretely, given an attributed graph g (V, these two components are constructed and encoded as follows.
The structure component extracts the graph structure and forms another graph Gs (Vs,Es, As As), in which the node and edge sets remain unchanged, i.e. Vs = =V, Es = E, and the out-degree of each node serves its attribute, i.e. As {d(u)lu E Vs) (d(-) denotes the out-degree function). GNN maps this component to 5-dimensional embedding space:
(zv,s: =0 &s.
where žy.s = (žv,slu E V} E B denotes the node embeddings derived only by the graph structure, and zg.s IR is the embedding of the entire structure component.
The attribute component is formed as a feature matrix U E R x where the feature vector U, E
RD a D-dimensional embedding node attribute A,,. For this component, fully-connected network and a readout function (e.g. mean pooling in our implementation) are used for encoding:
zV.A FCN(U), Zg.A READOUT(2y.A),
(5)
where zV.4 AZv,Alo V} E IR vix6 denotes the attribute embeddings of the nodes in graph G. and =g.4 E T embeds the whole attribute component.

---

Under review as a conference paper at ICLR 2021
The complete information of graph g is restored by concatenating the structure and attribute embed- ding for each node and for entire graph:
zy = [ Ze Re v v} R V x26
2g = |2g.s, 2g.Al E R
(6)
where [;: denotes the concatenation operation. Upon these concatenated node/graph embeddings, the prediction task (e.g. node/graph classification) is performed by a task-specific network C, which defines the supervised loss foup for model optimization:
min GNN,CON,C
Lsup-
3.2 EMBED-SAD: STRUCTURE- ATTRIBBUTE DISENTANGLEMENT FOR EMBEDDINGS
The explicit separation of an input graph into structure and attribute components forces the indepen- dent encoding of graph structure and node attributes. However, these two factors are not completely independent. For example, in a social network, the social connections of a person can provide use- ful information about his/her character, and vice versa. Therefore, the representations derived by Input-SAD may not fully capture the structure and attribute information of graph. To tackle this shortcoming, we seek to perform encoding on the original graph and distill its structure and attribute information into distinct channels of embedding vectors, illustrated in Fig. 1(b).
For an attributed graph g = A,) a GNN is employed to map the graph to a 26-dimensional embedding space:
(zv, zg) = GNN(VV A),
where zv = {zole E V} E IR V|26 denotes node embeddings, and 2g E R22 is the embedding of entire graph. We further divide these emheddings into two channels:
2g = [2g.s: =G.A); 2p ( A), Ae V,
where 2v Z (zg,s, AC,A) R are the structure and attribute embedding of node v (the whole graph 9). In order to distill the structure and attribute information to the corresponding channel, we propose two learning schemes.
Learning structure embedding by edge reconstruction. The node embeddings fully capturing the graph structure are supposed to be capable of reconstructing the edges of this graph. Specifically, using the structure embeddings of pair of nodes, we expect to predict the existence and type of the edge between them, which defines the reconstruction constraint for learning structure embeddings:
No
Creeon Eun
[ta.==]]
log ply = ilzu,S, Ze,
(10)
where Py denotes the uniform distribution over V, 1 [tu.=]] is the indicator function judging whether the edge (u, v) belongs to type i (i- = denotes there is no edge), N; is the number different edge types, and p(y|zu,s, 2v is modeled by neural network F which is detailedly discussed in Sec. B.
This objective function relates to the ones proposed in VGAE (Kipf & Welling, 2016) and Graph- SAGE (Hamilton et al., 2017), while it additionally constrains the reconstruction of edge type, which enables the structure embeddings to adequately capture the information of graph structure.
Learning attribute embedding by mutual information (MI) minimization. Now that the struc- ture embedding is obtained, we would like to derive the attribute embedding which extracts the information of node attributes and suppresses that of graph structure. To achieve this goal, we employ a neural-network-bann simultaneously, minimize the dependency between structure and attribute embedding.
MI estimator (i.e. the NCE estimator in Sec. 2.2) to estimate and,
In specific, we denote the structure and attribute latent factor as two random variables, 2s and Z,A- and regard the structure and attribute embedding of each node the sample from the corresponding marginal distribution, i.e. 2 p(zs), Ze,A ~ p(zA) (v E V). For computing the NCE estimation of MI, we define the structure and attribute embedding of the same node as positive pair, i.e. (2v.s, 2v.A) ~ p(zs, 2A) (u E V), and the embedding pair constituted by two different nodes serves as distractor, i.e. (Zn.S, Am..)) ~ p(=s) p(==)p(=A)) (v + w. U, w E V). With these notions, the estimated MI between two latent factors is defined as:
ISSA Ep
INCE(EN,S, Rn,As {
(11)
4

---

Under review as a conference paper at ICLR 2021
Algorithm 1:
Evaluation procedure for SAD-Metric.
Input:
Evaluation set ID (G the model to be evaluated M. The evaluation score for SAD-Metric.
Output:
Initialize the counter: c 0;
for /= to N do
yG; - RandomSample ((0, 1})
# Sample binary label
Ugg = then
9 < ModifyAttrribtee (G:)
# Modify the attribute factor of graph Modify the structure factor of graph
else
L 9 +- ModifyStructure((()
=g. + M(G.). =g; + MM(g))
# Infer graph embeddings Compute embedding difference
Aeg. 1zg. 20:
Predict the binary label Uc.- arg max, Azg.) if ÚØ, yo, then
c c+1;
Return Acc c/N x 100%:
# Compute prediction accuracy as SAD-Metric
where Py and (v) denote the uniform distribution over the node set with and without node v, and INCE(-,", .) is the NCE estimation function defined in Eq. 3.
Through minimizing this estimated MI, both the linear and nonlinear dependency between struc- ture and attribute embeddings can be suppressed, which facilitates node/graph representations. Note that, such learning mechanism relates to the information bottle- neck (IB) principle (Tishby al., 2000; Tishby & Zaslavsky, 2015; Alemi et al., 2017), while, compared with IB, the proposed approach intends to separate two different sources of information instead of pursuing the maximal compression about the input.
disentangled
Model optimization. We perform the prediction task (e.g. node/graph classification) by appending a task-specific network C upon the disentangled node/graph embeddings (i.e. zy or zg), which defines a supervised loss Csup intended to be minimized. This supervised task also guarantees that the meaningful semantic information not eliminated by the MI minimization scheme. For structure- attribute disentanglement, on one hand, the reconstruction loss Lrecon is minimized to distill the information of graph structure into structure embeddings. On the other hand, the MI minimization is conducted in adversarial manner, in which the discriminator T (defined in Eq. 3) is trained to maximize Is.,A, while the GNN encoder seeks to minimize that term. The overall objective is:
min max Loup + A1 + AgIs.
(12)
GNN.F.C
where A and X2 are the trade-off parameters balancing between different objectives.
3.3 SAD-METRIC: STRUCTURE-ATTRIES DISENTANGLEMENT METRIC
In order to quantify the extent of structure-attribute disentanglement achieved by various models, we devise a classifier-based metric to measure the learnt graph representations. Inspired by a previous work (Higgins et al., 2017), we focus on two desired properties of the disentangled representations: (1) independence: representation vector is expected to be divided into several channels whose interdependency as low as possible; (2) interpretabilliy: each of these channels corresponds to a single latent factor of the data.
To derive such metric, for a given graph G, we first sample a binary label yg from the uniform distribution over (0, 1}. According to this label, either the graph's structure or attribute is modified under the other factor fixed (gg = 0: fix G's structure; Bg 1: fix G's attribute), which forms the counterpart graph g'. In practice, we modify graph's 's structure through randomly dropping one of its edge (Rong et al., 2019), and the graph's 's attribute modified by randomly altering the attribute of a node (implementation details are stated in Sec. B). Using the model to be evaluated, the embeddings of graph G and G' (i.e. 2g and ) are inferred, and we denote the absolute difference between these two embeddings Azg (i.e. Aag lag zg. When the structure and attribute
5

---

Under review as a conference paper at ICLR 2021
attribute node normal node
= (V.V. Ex)
9. = (V,
g (V.Va.E.
Figure 2: Divide attributed graph 9 into bipartite graph G and unattributed graph Gs.
information are disentangled in graph embeddings (i.e. independence and interpretability holds), the elements corresponding to the fixed factor should possess lower values in Azg, which makes easier to predict Vg with a low capacity classifier (e.g. linear classifier) upon Agg Based on this fact, we employ the prediction accuracy of yı on set of graphs as structure-attribute disentanglement metric (SAD-Melric) The whole evaluation procedure is summarized in Algorithm 1.
In order to measure the extent arructue-attrriuue disentanglement in node embeddings, we further design node-centric metric, named as Mode-SAD-Menie The detailed definition and experimental results for this metric are presented in Sec.
3.4 THEORETICAL ANALYSIS
In this section, we theoretically illustrate that the disentanglement of structure and attribute repre- sentation is able to ease the burden of model optimization by shrinking the solution space.
For an attributed graph G = (V, A),, we can regard each type of node attribute as an attribute node, which transforms graph G into another form, g (V. VA.& &, EA) (V.a: the of all attribute nodes, E the edges connecting normal and attribute nodes), as shown in Fig. 2(a). This graph can be divided into two parts: (1) bipartite graph reflecting attribute information, G (V, VA. EA) (Fig. 2(b)) and (2) an unattributed graph depicting graph structure, Gs = (V, E") (Fig. 2(c)).
We first give the definitions of topological space and the spaces for graph GA and Gs. Definition 1. A topological space T (x,)(x)) is composed of set X and neighborhood function (zz) mapping each X to subset of X.
Definition 2. The topological space for graph GA TA (VUVA.NNalv)) and the topological space for graph Gs is Ts = (V,Ns(u)).
We consider two ways of graph embedding. The first way embeds graph GA and 9s common embedding space, i.e. learning a function TA x Ts + Z, while the second way embeds two graphs to separate embedding spaces, iee learning a function f TA Ts - ZA x Zs When the dimension of embedding space is identical these two ways, we propose that the dimension of the solution space of function smaller.
Proposition 1. it holds that (Z) dim( + dim we have dim( & dim(J).
The detailed proof of this proposition is provided in Sec. A. Proposition I tells that the structure- attribute disentanglement of graph representation narrows the solution space of the model, which enables us to train the graph encoder more effectively.
4 RELATED WORK
Graph Representation Learning. The early efforts towards learning low-dimensional embeddings of nodes/graphi focused on optimizing the objectives induced by random walk statistics (Perozzi et al., 2014: Tang et al., 2015; Grover Leskovee, 2016) or matrix factorization (Cao et al., 2015; Wang et al., 2016). By contrast, the Graph Neural Networks (GNNs) (Scarselli et al., 2008) de- rive embedding vectors via a neighborhood aggregation mechanism. Gilmer et al. (2017) suggested that most GNNs perform Message Passing and Readout phase, and different techniques (Kipf & Welling. 2017; Hamilton et al., 2017; Velickovic et al., 2018; Ying et al., 2018; Zhang et al., 2018; Xu et al., 2019) have been explored enhance the effectiveness of these two phases. Un-

---

Under review as a conference paper at ICLR 2021
like these methods which mix the information of graph structure and node attributes into a single representation, our approach aims to disentangle these two factors in node/graph representations.
Learning Disentangled Representations, A disentangled representation is expected to separate the distinct and informative factors of variation in the data (Bengio et al., 2013). Some previous works sought to achieve this goal under the guidance of weak supervision (Hinton al., 2011; Kulkarni et al., 2015; Siddharth et al., 2017). On another line of research, representation disentanglement is pursued by various unsupervisedd/sllf-spevvvee 2017; Kim & Mnih, 2018; Chen et al., 2018). For graph-structured data, a recent work (Ma et al., 2019) disentangled the latent factors of graph structure via a neighborhood routing mechanism. The proposed structure-attriben disentanglement is orthogonal to their work and also more general.
techniques (Chen et al., 2016; Higgins et al.,
Measuring Disentangled Representations. The quantitative measurement of representation dis- entanglement is essential to compare different disentangling algorithms. Given the true factors of variation, various disentanglement metries have been designed based on classifier (Karaletsos al., 2016; Higgins et al., 2017; Kim & Mnih, 2018), mutual information estimation (Chen et al., 2018; Ridgeway & Mozer, 2018) or distribution entropy (Eastwood & Williams, 2018). The proposed SAD-Metric follows the mmbedding-based evaluation protocol as previous works, while it is novel on its data processing scheme which is tailored for graph traph--tructured data.
5
EXPERIMENTS
5.1 EXPERIMENTAL SETUP
Model configurations. For all approaches evaluated Secs. 5.2 and 5.3, we equip them with a GCN (Kipf& & Welling, 2017) (hidden units' dimension: 300, readout function: mean pooling) with two/three layers for node/graph classification, respectively. The performance on other GNNs, i.e. GraphSAGE (Hamilton et al., 2017), GAT (Velickovic et al., 2018) and GIN (Xu et al., 2019), is reported in Sec. 5.5. For the Input-SAD model, a two-layer fully-connecter network (hidden units' dimension: 300, activation function: ReLU) is adopted to encode the attribute component of graph. For the Embed-SAD SAD model, the discriminator of the NCE estimator is built as an encoder-and-dot architecture: T T(x1, X2)
(xx)" where (() is modeled by two linear layers and ReLU nonlincarity in between, and it projects the original feature vector to an inner-product space.
Training details. In node classification experiments, an Adam optimizer (Kingma & Ba, 2015) (learning rate: 1 x 10-3) is employed to train the model for 1000 epochs, and, for graph clas- sification tasks, we use an Adam optimizer (learning rate:
10-3, batch size: 32) to perform optimization for 100 epochs. For the negative sampling in NCE estimator (Eq. 3), we utilize all the nodes other than the selected one as negative samples (i.e. K = | - 1), while, on three large networks (i.e. PubMed, Coauthor-CS and Coauthor-Physse Unless otherwise stated, trade-off parameters X and X are set as and 0. (sensitivity analysis in Sec. 5.5), which is determined by the grid search the validation sets of three citation networks.
3000 nodes serve as negative samples.
Performance comparisons. We combine the proposed Input-SAD and Embed-SAD model with four kinds of GNNs (GCN, GraphSAGE, GAT and GIN) to verify their effectiveness. Furthermore, we compare our method with five existing approaches that seek to promote GNNs' representation learning capability, i.e. Multi-task (Tran, 2018), GraphMix (Verma et al., 2019), DropEdge (Rong et al., 2019), DisenGNN (Ma et al., 2019) and InitRes (Chen et al., 2020) (detailed settings are in Sec. B). Among which, Multi-task and DisenGNN relate to our method: the former performs link prediction and node/graph classification simultaneously; the latter disentangles node representations based on different generative causes of edges.
5.2 EXPERIMENTS OF NODE CLASSIFICATION
Datasets. We employ three citation networks (i.e. Cora, CiteSeer and PubMed (Sen et al., 2008)) and two larger coauthor networks (i.e. Coauthor-CS and Coauthor-Physic (Shchur et al., 2018)) for semi-supervised node classification (20 labeled nodes per category). The node attributes of three citation networks are the ofr-odswordds representation of the document, and the nodes in two coauthor networks are featured by the paper keywords for each author's papers. Edge attributes are not included in these datasets. The details about dataset statistics, dataset split and evaluation protocol are provided in Sec. C.
7

---

Under review as a conference paper at ICLR 2021
Table 1: Node classification accuracy (mean + std %) on citation and coauthor networks.
Method
Cora
CiteSeer
PuhMed
Coamhor-CS
Coauthor-
GCN-baseline (Kipf & Welling, 2017)
81,23 + 0.62
70.31
0.57
78.50 = 0.47
90.98 = 0.50
93.10 = 0.07
Multi-task (Tran, 2018)
81.68 + 0.92
70.46 0.65
78.81 = 0.74
91.08 = 0.41
93.69 + 0.07
GraphMix (Verma al., 2019)
82.05 0.67
71.50 +
78.92
91.65 + 0.53
93.59
DropEdge (Rong
2019)
81.47 0.96
70.70
0.61
77.27
0.69
89.56 1 0.55
91.81 0.92
DiscuGNN (Ma et al., 2019)
81.95 0.66
70.81 = 1.30
78.19 + 0.53
90.83 = 0.69
93.55 + 0.73
InitRes (Chen al., 2020)
81.51 +: 0.80
70.47 0.36
78.60
0.30
91.70
+ 0.52
93.91 0.41
Input-SJi
1
70.96
89.79
Embed-SAD (w/o Creco))
81.92 + 0.70
70.38 1 0.98
78.32 + 0.63
91.57 = 0.40
93.55 0.64
Embed-SAD (w/o IS.A)
81.41 + 0.69
71.02 0.88
78.92 + 0.43
91.08 = 0.57
93.34 + 0.50
Embed-SAD
83.01 0.42
71.23 1.22
79.56 1.00
91.85 0.79
94.03 0.58
Table 2: Test ROC-AUC (mean + std %) on molecular graph classification benchmarks.
Method
BBBP
Tox21
ToxCast
SIDER
ClinTox
MUV
HIV
BACE
Avg
GCN-haseline (2017)
68.1 0.3
0.3
74.0
0.1
0.1
61.2 0.1
0.3 61.6 = 0.6 74.8 0.2
0.2
79.3 0.1 69.5
Multi-task (2018)
71.31:011
0.1
618
76.4
77.4
70.1
GraphMix (2019)
67.5 73.7
0.2
63.2
61.5
0.5
62.5 126 0,3
73.1
0.4
0.7
69.3
Dropládge (2019)
70.7 0.2 73.7
0.4
63.3
63.8
0.3 66.5 388
0.4
75.4
79.1
70,9
DisenGNN (2019)
69.
0.1
61.2
61.1
73
7..
0.3 72.0
InitRes (2020)
71.9 0.9
74.5
0.4
63.9
63.4
63.0
71.8
7..
75.1
0.5 70.0
Input-SAD
69.9 0.7
74.3
0.2
63.
639
74.0
00,6
74.2
8.
Embed-SAD (woo Crecou
71. 0.3
75.5
63.
615
0.4
76.0
75.4
80.7
71.4
Embed-SAD (w/o x
72.3 0.2
64.
1.
63.3 0.3
67.2
0.7
75. 0.3
80.4
71.5
Embed SAD
73.0 1 0.2
75.6
0.2
64.4 0.3 63.3
0.2 74.1
1.1 76.1
0.2 76.9 0.4 81.3
1
0.1 73.1
Table 3: SAD-Metric score (mean std %) on molecular graph datasets.
Method
BBBP
Tox21
ToxCast
SIDER
ClinTox
MUV
HIV
BACE
Avg
random-GCN (2017)
75.5
73.9
82.1 0.4
6. 76.3
82.2 0.6
GCN-baseline (2017)
82.5 03.5000 0.2
88.9
0.1
0.1
86.0 04.9
92.4
83.1 93.2
94.7
0.5
89.1
DiscuGNN (2019)
92.3 - 0.8
88.4
0.2
9.44
95.6
95.0
08.8002
93.9
0.3
93.2
Input-SAD
93.3 2
94.5
00.0
98.6
96.4
08.2
94.1
0.4
Embed SAD
95.9 0.2
98.7
0.6
98.6
1 0.9 97.3 0.1
95.0 0.6
98.5 1 0.1
95.2 0.2
97.8
0.8
97.1
Results. Tab. 1, we report the performance of different methods on five standard node classifica- tion benchmarks. Based on two-layer GCN model, the proposed Embed-SAD achieves the highest test accuracy on four of five tasks among all approaches. The performance of Input-SAD is inferior on these tasks, which, think, is mainly ascribed to its failure in fully capturing the structure and attribute information of each node.
5.3 EXPERIMENTS OF GRAPH CLASSIFICATION
Datasets. For graph classification, we adopt eight single-taskmmuile MoleculeNet (Wu et al., 2018), and, following previous findings (Chen et al., 2012), scaffold split scheme utilized for dataset split. For each molecular graph sample, the type and chirality of atom serve as the node attributes, and the type and direction of bond constitute the edge attributes. For evaluation, five independent runs with distinct random seeds are conducted, and the average performance reported. More dataset statistics are in Sec. C.
classification datasets in
Results. Tab. shows the comparisons between our methods and existing techniques. Embed-SAD outperforms DisenGNN, closely related work, six of eight datasets, and 1.1% performance gain is achieved in terms average ROC-AUC, which illustrates the effectiveness structure- attribute disentanglement. Input-SAD performs well on this graph classification benchmark and obtains superior performance on SIDER and BACE datasets, which, we think, is because the graph pooling operation is able to supplement the missing structure attribute information of each node from other nodes.
5.4 QUANTITATIVE EVALUATION OF STRUCTURE- PERUCCURE-ATTRIBUTEE ATTRIBUTE DISENTANGLEMENT
Evaluation details. We employ the same datasets and dataset split scheme as in Sec. 5.3. We use GCN model with random parameters Handom-GCN) and GCN model pre-trained by graph clas- sification (GCN-baseline SAD and Embed-SAD) also establish appropriate priors by performing graph classification on the training set. linear binary classifier is built upon the model to be evaluated, and the classifier is
baseline models. Three disentanglement models (DisenGNN, Input-
8

---

Under review as a conference paper at ICLR 2021
70
Publied
84
74
RONSAA 540
Aveurccy (%g
80
Accuracy
78
70
Avomas
68
GCN Grugh SAGE QAT
CIN
A1
0.1)
Ag
(1
(b)
(c)
Figure 3: (a) Performance comparisons on four GNNs. (b)&(c) Sensitivity analysis of X and A2.
Pediie sregle
Soattee anbakkkg anbhakin
GCN-GGaselinn
(b) InD
(c)
EmD
(d) Inpat-SAD
(e) Embed-SAD
Figure 4: Visualization of correlation matrix and embedding distributions
BBBP's training set.
trained with the graphs in the training set and evaluated by test graphs. All results are averaged over five independent runs.
Results. We report the SAD-Metric score of five methods in Tab. 3. The poor performance of random-GCN shows that it can hardly disentangle the structure and attribute information of graph, and the graph classification pre-training endows the GCN-baseline model with better disentangle- ment capability. Compared to DisenGNN, the proposed Input-SAD and Embed-SAD model better disentangle graph's 's structure and attribute information. The Embed-SAn model achieves the best disentangiement of graph representations on seven of eight datasets.
5.5 ANALYSIS
Effect of two objectives Embed-SAD. In Tabs. 1 and 2, analyze the effect of reconstruction loss and cruuctue-attriburt mutual information minimization. When removing any of these two objectives, the model's performance is impaired, which demonstrates their complementary relation.
Results of different GNNs. In Fig. 3(a), we combine three representation disentanglement tech- niques with four kinds of GNNs, and the average test ROC-AUC over eight datasets of MoleculeNet plotted (detailed results are in Sec. D). Embed-SAD performs best on all four configurations, and the performance of SAD and DisenGNN is comparable with each other.
Sensitivity of trade-off parameters Å₁ Az- Figs. 3(b), (c) show the performance of Embed-SAD on citation networks using different trade-off weights. We can observe that stable performance gain is obtained when the values of X and X2 are around 1 and 0.1, respectively.
Visualization. In Figs. 4(a), (b), (c), we visualize the absolute values of the correlations between the learnt graph embedding's elements on BBBP dataset. Among three models, Embed-SAD sup- presses the correlation between structure and attribute embedding to the greatest extent. We further visualize the embedding distributions using t-SNE (Maaten & Hinton, 2008) in 4(d), (e). Both Input-SAD and Embed-SAl separate two kinds of embeddings into distinct spaces, and attribute embeddings possess stronger semantic discriminability compared to the structure counterparts.
CONCLUSIONS AND FUTURE WORK
We study node/graph representation learning with ftructure-Atrrbuut Disentanglement (GraphSAD) in both the input and the embedding space. We further design a quantitative metric to measure such disentanglement. On node and graph classification benchmark datasets, we empirically verify our method's 's superior performance over existing techniques.
Our future explorations will involve improving the learning manners for structure-attribun disen- tangled representations, evaluating the proposed models on more tasks (e.g. regression-basee tasks) and disentangling graphs in other ways.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Alexander A. Alemi, lan Fischer, Joshua V. Dillon, and Kevin Murphy, Deep variational information bottleneck. In International Conference on Learning Representations, 2017.
Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeswar, Sherjil Ozair, Yoshua Bengio, R. De- von Hjelm, and Aaron C. Courville. Mutual information neural estimation. In International Conference Machine Learning, 2018.
Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE Transactions Puttern Analysis and Machine Intelligence, 35(8) 1828, 2013.
Antoine Bordes, Nicolas Usunier, Alberto García-Durán, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Advances in Neural Information Processing Systems, 2013.
Maurice Bruynooghe. Solving combinatorial search problems by intelligent backtracking. Informa- fion Processing Letters, 12(1))36-39, 1981.
Shaosheng Cao, Wei Lu, and Qiongkai Xu. Grarep: Learning graph representations with global structural information. In ACM International Conference on Information and Knowledge Man- agement, 2015.
Bin Chen, Robert P Sheridan, Viktor Horakk, and Johannes Voigt. Comparison of random forest and pipeline pilot naive bayes in prospective qsar predictions. Journal of Chemical Information and Modeling, 52(3):792-803, 2012.
Hubie Chen, Carla Gomes, and Bart Selman. Formal models of heavy-tailed behavior in combinato- rial search. In International Conference on Principles and Practice of Constraint Programming, 2001.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning. 2020.
Tian Qi Chen, Xuechen Li, Roger B. Grosse, and David Duvenaud. Isolating sources of disen- tanglement in variational autoencoders. Advances in Neural Information Processing Systems, 2018.
Xi Chen, Yan Duan, Rein Houthooft, John Schulman, Ilya Sutskever, and Pieter Abbeel. Infogan: Interpretable representation learning by information maximizing generative adversarial nets. In Advances in Neural Information Processing Systems, 2016.
Cian Eastwood and Christopher K. I. Williams. A framework for the quantitative evaluation of disentangled representations. In International Conference on Learning Representations, 2018.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, 2017.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In ACM
SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016.
Michael Gutmann and Aapo Hyvärinen. coise-contrastive estimation: new estimation principle for unnormalized statistical models. In International Conference on Artificial Intelligence and Statistics, 2010.
Michael Gutmann and Aapo Hyvärinen. Noise-contrastive estimation of unnormalized statistical models, with applications to natural image statistics. Journal of Machine Learning Research, 13: 307-361, 2012.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, 2017.
10

---

Under review as a conference paper at ICLR 2021
Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner. beta-vae: Learning basic visual concepts with constrained variational framework. In International Conference Learning Representations, 2017.
Geoffrey E. Hinton, Alex Krizhevsky, and Sida D Wang- Transforming auto-encoders. In Interna- tional Conference on Artificial Neural Networks, 2011.
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, 2019.
Karan Grewal, Philip Bachman, Adam
Theofanis Karaletsos, Serge J. Belongie, and Gunnar Rätsch. Bayesian unsupervised representation learning with oracle constraints. In International Conference on Learning Representations, 2016.
Hyunjik Kim and Andriy Mnih. Disentangling by factorising. In International Conference on Machine Learning. 2018.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
Thomas N. Kipf and Max Welling. Variational graph auto-encoders. CoRR, 0tbps//11.073000 2016.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. In International Conference on Learning Representations, 2017.
Lars Kotthoff. Algorithm selection for combinatorial search problems: A survey. In Data Mining
and Constraint Programming. 2016.
Tejas D Kulkarni, William F Whitney, Pushmeet Kohli, and Josh Tenenbaum. Deep convolutional inverse graphics network. In Advances Neural Information Processing Systems, 2015.
Jianxin Ma, Peng Cui, Kun Kuang, Xin Wang, and Wenwu Zhu. Disentangled graph convolutional networks. In International Conference on Machine Learning, 2019.
Laurens Van Der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of Machine Learning Research, 9(2605):259--6605 2008.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: online learning of social represen- tations. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2014.
Karl Ridgeway and Michael C. Mozer. Learning deep disentangled embeddings with the f-statistic loss. In Advances Neural Information Processing Systems, 2018.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks node classification. In International Conference on Learning Repre- sentations, 2019.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2008.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad Collective classification in network data. Al Magazine, 29(3):33-93, 2008.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprini arXiv: 1ttf::://1...88000 1.05688, 2018.
Narayanaswamy Siddharth, Brooks Paige, Jan- Willem Van de Meent, Alban Desmaison, Noah Goodman, Pushmeet Kohli, Frank Wood, and Philip Torr Learning disentangled representations with semi superviee deep generative models. In Advances in Neural Information Processing Systems, 2017.
11

---

Under review as a conference paper at ICLR 2021
Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. In International Conference on Learning Representations, 2019.
Chenhao Tan, Lillian Lee, Jie Tang, Long Jiang, Ming Zhou, and Ping Li. User-level sentiment analysis incorporating social networks. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2011.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. LINE: large-scale information network embedding. In International Conference World Wide Web, 2015.
Naftali Tishby and Noga Zaslavsky. Deep learning and the information bottleneck principle. In 2015 IEEE Information Theory Workshop, 2015.
Naftali Tishby, Fernando C Pereira, and William Bialek. The information bottleneck method. arXiv preprint physics/00044057, 2000.
Phi Vu Tran. Multi-task graph autoencoders. arXiv preprint arXiv: 1 1.02998, 2018
Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Com- plex embeddings for simple link prediction. International Conference on Machine Learning. 2016.
Aäron den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predic- tive coding. CoRR, abs/1807. 00111187000777 .0744,, 2018.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Vikas Verma, Meng Qu, Alex Lamb, Yoshua Bengio, Juho Kannala, and Jian Tang. Graphmix: Regularized training of graph neural networks for semi-supervised learning. arXiv preprint arXiv: 11715, 2019.
Daixin Wang, Peng Cui, and Wenwu Zhu. Structural deep network embedding. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016.
Zhengin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S Pappu, Karl Leswing, and Vijay Pande. Moleculenet: A benehmark for molecular machine learn- ing. Chemical Science, 922::113-330 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations, 2019.
Qiang Yan, Lianren Wu, and Lan Zheng. Social network based microblog user behavior analysis.
Physica A: Statistical Mechanics and Its Applications, 392(7):1112-1723, 2013.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International Conference on Machine Learning. 2016.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William I. Hamilton, and Jure Leskovec. Hierarchical graph representation learning with diffcrentiable pooling. In Advances in Neural Information Processing Systems, 2018.
Guo Zhang, Hao He, and Dina Katabi. Circuit-gnn: Graph neural networks for distributed circuit design. In International Conference on Machine Learning, 2019.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In AAAI Conference on Artificial Intelligence, 2018
12

---

Under review as a conference paper at ICLR 2021
A PROOF OF PROPOSITION 1
Considering the search of embedding function as a combinatorial search problem (Bruynooghe, 1981; Chen al., 2001; Kotthoff, 2016), we derive the dimension of the solution space for two types of embedding functions, i.e. f TA Ts + Z and f TA Ts + Z Zs, follows:
dim(f) diim(TA + (Ts)
(13)
dim(Z)
(Ti((Ta) (dim(Ts) Ts)
dim(f) dimm (Z,))))))a))))))))))))
(14)
(dim( (Zs)
Under the condition that dim (Z) = dim (Z + dim( dim(Zs), the basic property of combinations gives the following inequality:
dim Ta)
(Tm(Ts)
(dim((a) + dim dimm(s)) dim(Z)
(7s))
<
(15)
dim ZA)
(dim(Zs)
which deduces that:
dim & din(J).
(16)
This conclusion shows that the solution space of the graph embedding function with structure- attribute disentanglement is narrower than that of the entangled counterpart.
B MORE IMPLEMENTATION DETAILS
Modeling conditional distribution for edge reconstruction. For the graphs that only provide the existence of edges (i.e. N₂ = 1), we utilize an inner-product decoder for edge prediction:
p Su ; 2u s)) 11 (=H Su, ply 1zzu,S St o 20,s),
(17)
where (-) denotes the sigmoid function.
For the graphs owning more than one type of edges (i.e. N₁ 1). we concatenate the embedding vectors of two nodes and use a linear classifier to predict the type of the edge between them:
ply|zu,s, sv ((
(18)
where F : R + N. is the edge prediction function modeled by linear classifier network.
Attribute modification for SAD-Metric. To modify the attribute of graph, we randomly select node in this graph and alter its attribute. Specifically, for a graph sample (i.e. molecule) in the datasets of MoleculeNet, we modify its attribute by randomly selecting an atom and resetting the atom's type and chirality to other valid values. Such technique can be applied any graph dataset in which node attributes are discretely represented.
Detailed settings for compared methods. In the experiments. we compare our method with five existing techniques that aim to improve graph representation learning, í.e. Multi-task (Tran, 2018), GraphMix (Verma et al., 2019), DropEdge (Rong et al., 2019). DiscnGNN (Ma et al., 2019) and InitRes (Chen et al., 2020). The detailed settings of these approaches are as follows:
Multi-task. Node embeddings employed for both node classification and link prediction, and the loss term for link prediction possesses the weight of O.1.
GraphMix. this approach, parameter a controls the Beta distribution from which mixup ratios are sampled, and we fix this parameter as 1.0 in all experiments.
Edge During training, 10% edges of each graph are randomly dropped to mitigate the over-fitting and over-smoothing problems.
DisenGNN. For each GNN layer, the feature vector of each node is divided into 5 channels, and iterations of neighborhood routing are performed.
InitRes. This method constructs residual connection from the initial node representations to each GNN layer. We set the residual ratio as 0.2, such that the final representation of each node retains least 20% of the input feature.
13

---

Under review as a conference paper at ICLR 2021
C
MORE EXPERIMENTAL DETAILS
Table 4: Dataset statistics for citation and coauthor networks.
Dataset
# Nodes
# Edges
# Features
# Classes
# Training
Validation
# Test
Cora
2,708
5,429
1,433
7
140
500
1,000
CiteSeer
3,327
4,732
3,703
6
120
500
1,000
PubMed
19,717
44,338
500
3
60
500
1,000
Coauthor-CS
18,333
81,894
6,805
15
300
450
17,583
Seauthor-Physice
34,493
247,962
8,415
5
100
150
34,243
Table 5: Dataset statistics for molecule datasets.
Dataset
BBBP
Tox21
ToxCast
SIDER
ClinTox
MUV
HIV
BACE
Molecules
2,039
7,831
8,575
1,427
1,478
93,087
41,127
1,513
Tasks
1
12
617
27
2
17
1
Avg Nodes
24.06
18.57
18.78
33.64
26.16
24.23
25.51
34.09
Avg Edges
25.95
19.29
19.26
35.36
27.88
26.28
27.47
36.86
Citation networks. In Tab. 4, provide the detailed information about three citation networks, in which 20 labeled nodes per category are used for training, and there are 500 and 1000 nodes for validation and test, respectively. We adopt the standard dataset split proposed in Yang et al. (2016) for all experiments on citation networks. All the reported results are averaged over 100 independent runs using different random seeds.
Coauthor networks. The statistics of two coauthor networks are listed in Tab. 4. Following Shchur al. (2018), we use 20 labeled nodes per category as the training set, 30 nodes per category as the validation set, and the rest the test set. The reported accuracy is averaged over 30 random train/validation/test splits, and, for each split, 50 independent runs are performed.
Molecule datasets. In Tab. 5, we present the detailed statistics of eight molecule datasets in Molecu- leNet (Wu et al., 2018). On each dataset, model intends to predict one or multiple properties of various molecules, where the prediction of each property binary classification task.
D MORE RESULTS ON MOLECULENET
In Tabs. 6, and 8, we combine different techniques with three GNNs (i.e. GraphSAGE (Hamilton et al., 2017), GAT (Velickovic et al., 2018) and GIN (Xu et al., 2019)) and evaluate various models' performance on MoleculeNet, which set the number of attention heads for GAT. For all the three experiments, the Embed-SAD model outperforms other methods in terms of average test ROC-AUC. The Input-SAD model achieves superior performance on ClinTox and BACE datasets, and its overall performance is comparable with DisenGNN.
E NODE-SAD-METRIC' NODE-CENTRIC STRUCTURE-ATTRIUUTE DISENTANGLEMENT METRIC
E. DEFINITION
The node-SAD- SAD-Metric measures the extent of cruuctre-attribuc disentanglement in node embed- dings. Similar with the graph-level SAD-Metric, this node-level disentanglement metric evaluate two properties node embeddings, iee independence and interpretability (detailed definitions re- ferring to Sec. 3.3). In this case, after structure and attribute modification, the nodes of a graph are classified into three types: (1) the nodes whose one-hop structure is modified, (2) the nodes whose attribute is modified and (3) the nodes without one-hop structure or attribute modification. In practice, we first randomly drop 20% edges 20% of the rest nodes whose one-hop structure have not been modified. Similar in SAD-Metric (Sec. 3.3), we employ the absolute difference between the node embeddings before and after the above modification to perform three-way classification. Upon such embedding difference,
graph and then randomly modify the attributes of
14

---

Under review as a conference paper at ICLR 2021
Table 6: Test ROC-AUC (mean + std %) on MoleculeNet using the GraphSAGE architecture.
Mothod
BBBP
Tox21
ToxCast
SIDER
ClinTox
MUV
HIV
BACE
Ave
GripSSGFF-hselinee (2017)
70.9 = 1.0
74.3 0.1 0.2 60.5
66.4#0.22
78.2
0.6
74.6
0.5
76.0
0.8
70.6
Multi task (2018)
71.3 73.7
63.2
64.8
GraphMix (2019)
70.9 0.5 0.3
63.7
62.5
0.9
73.9
T5.4
0.6
77.5
0.7
70.1
DropEdge (2019)
71.3 0.3 74.7
6..6
63.
66.1
66.
76.2
0.3
75.9
1.4
76.7
0.3
70.8
DisciGNN (2019)
72.4 75.2
0.3
61.5
6. 75.7
0.7
T3.1
0.7
80.2
71.5
TnitRes (2020)
71.5 75.0
63.4
63.
64.6
73.7
0.3
75.0
75.3
70.3
Input-SAD
69.2 0.7
73.4
0.4
6.2 0.5
7..4
76.2
0.6
74.2 -
0.8
82
71.
Embed SAD
74.4 0.3
74.5
0.3 64.3
1 0.1 63.9 1 70.7 1.4 78.4
1 0.2 76.7
0.5
78.7
0.7 72.7
Table 7: Test ROC-AUC (mean std %) on MoleculeNet using the GAT architecture.
Method
BBBP
Tox21
ToxCas
SIDER
ClinTox
MUV
IIIV
BACE
Avg
GAT-baseline (2018)
70.0 0.2
67.0 = 0.1
61.6 0.3
62.6
61.6
0.5
65.6
72.3
1.3
66.6
Multi-task (2018)
68.2
0..
58.2
0.5
0.2
64.3 0.6
63.7
66.5
0.9
69.0
2.3
64.6
GraphMix (2019)
68.7
65.9
59.5
6..81.04
6.7
67.911
66.3
1.1
71.9
65.7
DropEdge (2019)
0.3
0.3
6..7
0.3
6..7
65.5
0.3
7.3
66.7
DisenGNNN (2019)
10.0::0.5
6..
60.9
6..4
63.1
70.1
71.
0.9
70.3
0.5
66.7
InitRes (2020)
70.3 + 0.3
0.7
63.0
0.1
0,.9
09.
0.
7L5
71.8
67.9
Input-SAD
68.0
39.9
70.8
Embed-SAD
71.5 = 0.6
70.9
= 0.3
60.8
0.2
09.5 6.1
1.6
70.3
68.7
72.6 0.6
68.4
Table 8: Test ROC-AUC (mean + std %) on MoleculeNet using the GIN architecture.
BBBP
Tox21
ToxCast
ClinTox
MUV
Avg
buselin (2019)
72.1
75.3
62.4
122100
79.9
70.9
Multi-task (2018)
72.0 1.4
0.2
0.2
0.5
1.0
7.6
7
77.0 0.7
71.2
GraphMix (2019)
71.4 0.7
0.2
0.1
623
6.1
77.5
76.8
0.2
79.9 1.3
71.0
DropEdge (2019)
12.
0.44
63.5
0.7
6..2
73.9
75.7
71.4
DisenGNN (2019)
71.8
0.3
6..0
61.4
1.5
76.0
76.4
80.0
72.0
InitRes (2020)
72.2 0.8
1.5
638111
61.8
0.7
69.14..3
0.3
1.7
76.1
16.1177
80.1 + 0.1
71.3
Inp
69.7 1 0.2
73.2
0.3
63.2
0.6
6221044
0.4
75.1
1 2.5
74.0
1..6
76.1
1
0.7
83.5
72.1
Fmhed-SAD
73.6
75.9
0.3
63.5
0.2
1.6
77.6
2 1.2
Table 9: The node-SAD-Medd score (mean + std %) on molecular graph datasets.
Method
BBBP
Tox21
ToxCast
SIDER
ClinTox
MUV
HIV
BACE
Avg
Fandom GCN (2017)
77.4 0.6
78.0
0.6
78.6 1 0.5 80.2 0.2.0..7 78.1 1. 0.3
83.9 1
0.8 81.1
0.3
76.5
1.0
79.2
GCN-baseline (2017)
89.7
87.5
90.6
8.2
86.9
92.2
0.7
DisenGNN (2019)
92.0 0.9
91.2
0.6
0..
0.7
94.3
0.5 93.6
0.4
91.3
0.7
92.3
Input-SAD
93.4 1
1.0
92.8
0.6
95.8 1 0.3 93.7 08.7 0.7
93.3 0.4
96.7
1 0.8
96.4
0.8
92.9
0.7
94.4
Fmhed-SAD
95.8 0.5
95.1
97.2 +
# 0.5
96.5 + 0.3
0.7
96.1
linear classifier trained to classify which type of modification is performed on a node, and the prediction accuracy of such node classification task serves the Made-SAD-Metric
E.2 EXPERIMENTAL RESULTS
Setups. As in Sec. 5.4, we use the MoleculeNet dataset (Wu et al., 2018) and the scaffold split scheme (Chen al., 2012) for this experiment. Also, the settings of five studied models are identical with those in Sec. 5.4. A linear classifier is trained with the graphs in the training split and evaluated by the graphs the test split. All results are averaged over five independent runs using different random seeds.
Results. Tab. reports the tiructure-attribue disentanglement performance of five models in terms of node-SAD- MeMric... The random-GGC bascline poorly disentangle the structure and attribute information node embedding, and GCN-baseline performs better by pre-training on graph classifi- cation task. Among three methods for disentangled representation learning, the Embed-SAD model achieves the best performance on seven of eight tasks.
15


Reviews:
[{"review_id": "YIEFBKzXWg_", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "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 focuses on disentangling embeddings of the structure and the attribute of graph. \bThe authors' key idea is that the structure and attribute information should be split in GNN. Based on this, the authors try to disentangle the structure embedding and the attribute embedding. With two different components, two different kinds of embeddings can be captured at the input stage.   In addition, these two different kinds of embeddings can be obtained by reconstructing the edge and minimizing the mutual information. At last, the authors propose a metric to evaluate the disentanglement. The models in this paper outperform baselines in node classification and graph classification task. \n\nThe pros of this paper is as following:\n1, The motivation/intuition of this paper is good. Current GNNs tend to aggregate the attribute information by graph structures, but ignore the relation between the structure and attribute information.\n2, This paper brings out two models to disentangle the structure and attribute information, at the input stage and the embedding stage-INPUT-SAD and EMBED-SAD, which seem reasonable to some extent. \n3, The experimental results are good on both node classification task and graph classification task.\n\nThe cons of this paper:\n1, Key weakness: the authors raise the problem that aggregation way of structure and attribute in current GNNs but not analyze the problem theoretically. For example, the true relation of structure and attributes and how the model in this paper can be derived naturally. The makes the novelty of the paper incremental.\n2, The authors use degree serves as attribute in INPUT-SAD. As I know, degree is a usually used attribute in graph. This design is contradictory to the authors' claim.   \n\nQuestion for authors: If some theoretical analysis about why the disentanglement is essential can be added into this paper. I may consider changing my reviews.", "extra_scores": {}, "extra_text": {}}, {"review_id": "T3zcW-yfJw", "reviewer": "AnonReviewer3", "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": "This paper describes a graph representation learning method which disentangles structure information and feature information, and combines them for downstream tasks. Generally speaking, I think this is a good paper. But some design choices and explanations are not very convincing. Details are as follows.\n\n\n[Pros]\n(1)\tThis paper is well written and easy to follow.\n(2)\tThe proposed problem is novel and the solution is intuitive.\n(3)\tExperiments are thorough.\n\n[Cons]\n(1)\tRegarding the SAD-Metric, why do you choose the undirect scheme based on a classifier? The goal is to minimize the change of structure (attribute) part of the embedding when altering the attributes (edges) of the graph. Using a classifier is a undirect measure about this, and would lead to misunderstanding when the classifier treats some elements for the structure (attribute) part as those for the attribute (structure) part. Imagine that such elements are coincidentally correlated with the opposite part. In that case, the accuracy could also be high. I think here it could be better to design a measure directly to reflect the above goal. Another question is, why do you define the measure on the graph embedding level, rather than the node embedding level, where the node is the one affected by the modification. I think this scheme could lead to more sensitive measures.\n(2)\tThe authors argue that the previous metrics for measuring disentangled representations are mainly designed for images, while the proposed SAD-Metric is tailored for graph-structured data. However, this is not convincing since the proposed measure is based on the learned embeddings (i.e., there is no graph structures). I think the general problem is still the same with the previous work. Hence, the novelty of SAD-Metric seems to be limited.\n\nMinor:\n-For model optimization, what does the $F$ stand for in Eq. (12)?\n-The examples in the second paragraph of section 2.1 are redundant.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "ET0uJIPi_JQ", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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": "Summary: This paper presents a novel method called Embed-SAD (as well as Input-SAD) to learn graph/node representations to disentangle structure and attribute information. Input-SAD is a simple baseline that tries to get structure-attribute disentanglements by individually processing graph structures and node attributes. For structure, the original node attibutes are replaced by out-degrees only, and passed to GNNs, while for attibutes, the node attibutes are passed to fully-connected networks. Embed-SAD is a more elaborate method to disentangle the GNN embeddings by posing two types of additional losses, i.e., the edge-reconstruction loss for structures, and the Noise-Contrastive Estimation (NCE) loss to maximize the mutual information against the structure-encoding vectors, in addition to the original loss for supervision. The paper also develops an interesting evaluation metric called SAD-Metric where node attibutes or graph structures are exclusively perturbed for each graph, and prediction for whether that perturbation is for structure or for attibutes made by the element-wise absolute differences between embedded vectors before and after the perturbation. This SAD-Metric can quantify the extent to which the obtained representation can detect which perturbation, that for structures or that for attibutes, is made for each sample graph. The experimental results also demonstrated that the structure-attibute disentanglement by Embed-SAD learning strategy actually improved the prediction performance of many off-the-shelf GNNs over many different graph- or node-level tasks.\n\nComments:\nThe paper is well-written and easy to follow since the intention and corresponding ideas are quite clear. The combined loss fo Embed-SAD also has ablation study results that was also informative. Basically I liked the idea and have not too much to say, but here are some  comments:\n\n- The SAD-metric would be more carefully evaluated since it includes \"training\" and we might be able to get zero-training error if embedding vectors are sufficiently high dimensional or we can use a strong predictor here for memorization. Even for a simple linear classifier (a \"low capacity\" classifier), I think it's better to replace this part by cross validation, or at least, a simple training-test split. \n\n- This study would depend on what node attibutes (i.e. \"featurization\") we use, and it should be more clearly described in the main body what node attibutes are used in each benchmarking experiment. In particular, we often include \"structure-derived features\" such as degrees (or the number of attached hydrogens in the case of molecular data) to the node attributes of GNNs, and how this practice affects the disentanglement would be informative in the paper's context. In particular, for Input-SAD.\n\n- Also, we need more information on the baselines of Table 3 for evaluating the SAD-metric. What is \"Random-GCN (2017)\"? (GCN with random node attibutes?) What is the intention to include this one here? Even Random-GCN had around 90% accuracy, and we need an additional baseline that clearly fails to disentangle structure and attibute information.\n\n- First, I personally felt that Input-SAD is actually not for \"disentanglement\" and a bit confusing, rather it's a simple baseline to see what if we input structure- and attibute- information separetely in the first place. However, to my surprise, the performance of Input-SAD was not that bad for molecular graph classification benchmark, in a sharp contrast to those for citation and coauthor network cases. Actually, Input-SAD was better than Embed-SAD for SIDER and BACE. Are there any possible explanations on this?\n\n- For eq (2), t_uv seemed undefined (though we can guess it). Do GIN, GAT, GraphSage use the edge attibutes?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "2KZlXB-KMXb", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "1. I am confused on the motivation part. Although the authors provide two examples (the prediction of a user’s social class mainly relies on his/her social network structure) to illustrate the benefits of disentangled representation for certain downstream tasks and I agree on the statement, it raises another question that what kind of representation, structure component or attribute component should be used for a specific task. \n2. If we take a further through on the relationship between structure component and attribute component, it should be separated into three parts, a common part, structure-specific part and attribute-specific part. In my eyes, the authors put the common part and structure-specific part together. Why? What is the benefit? So, the name \"structure/attribute component \" is not accurate. \n3. I do not see too much novelty in the technical part (edge reconstruction and mutual information minimizing). I am fine with this. But I do not see a deep insight of the problem-solving philosophy, either.\n4. It is nice to see the performance gain in the experimental part. But  I want to know the authors use one type or two types of representation.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, the authors propose a method to find disentangling embeddings of the structure and the attribute of the graph. Overall, this is an interesting paper and the paper is well-written and easy to follow, and the paper has some merits. However, the reviewers were still not convinced by the response, and the paper is still below the acceptance threshold.  I encourage authors to revise the paper based on the reviewer's comments and resubmit it to a future venue. 


Decision: Reject