# Adversarial Graph Disentanglement

Shuai Zheng, Zhenfeng Zhu, Zhizhe Liu, Shuiwang Ji,
Jian Cheng, and Yao Zhao S. Zheng, Z. Zhu, Z. Liu, and Y. Zhao are with the
Institute of Information Science, Beijing Jiaotong University, Beijing 100044,
China, and also with the Beijing Key Laboratory of Advanced Information
Science and Network Technology, Beijing 100044, China (e-mail:
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>yzhao@bjtu.edu.cn).J. Cheng is with the National Laboratory of Pattern
Recognition, Institute of Automation, Chinese Academy of Sciences and
University of Chinese Academy of Sciences, Beijing 100190, China (e-mail:
jcheng@nlpr.ia.ac.cn).S. Ji is with the Department of Computer Science and
Engineering, Texas A&M University, College Station, TX 77843. (e-mail:
sji@tamu.edu.).Manuscript received April 19, 2005; revised August 26, 2015.

###### Abstract

A real-world graph has a complex topological structure, which is often formed
by the interaction of different latent factors. Disentanglement of these
latent factors can effectively improve the robustness and expressiveness of
node representation of graph. However, most existing methods lack
consideration of the intrinsic differences in relations between nodes caused
by factor entanglement. In this paper, we propose an Adversarial Disentangled
Graph Convolutional Network (ADGCN) for disentangled graph representation
learning. Specifically, a component-specific aggregation approach is proposed
to achieve micro-disentanglement by inferring latent components that caused
the links between nodes. On the basis of micro-disentanglement, we further
propose a macro-disentanglement adversarial regularizer to improve the
separability among component distributions, thus restricting the
interdependence among components. Additionally, to reveal the topological
graph structure, a diversity-preserving node sampling approach is proposed, by
which the graph structure can be progressively refined in a way of local
structure aware. The experimental results on various real-world graph data
verify that our ADGCN obtains more favorable performance over currently
available alternatives.111Code is available at https://github.com/SsGood/ADGCN

###### Index Terms:

Graph representation learning, Graph neural networks, Adversarial learning,
Disentanglement.

##  I Introduction

Graph is a general description of data and their relations, which can model a
variety of scenarios, from biomedical networks to citation networks, or other
things defined by relations. There are a variety of graph-based applications
in the machine learning field, such as link prediction [1], node
classification [2, 3], and recommendation [4, 5]. As an important part of
graph analysis, graph representation learning is the basis for graph data to
be processed by conventional machine learning methods. In recent years, a
great deal of work has greatly promoted the development of graph
representation learning.

Most graph representation learning methods can be broadly classified into two
categories: proximity-based methods and neural network based methods.
Proximity-based methods, such as DeepWalk [4], node2vec [5], and LINE [6],
focus on extracting the patterns from the graph data. These methods tend to
learn the node representation with various order proximity preserving by
constructing the node paths through random walk or local neighborhood.
Besides, [7] demonstrated that matrix factorization methods [8] are also
equivalent to proximity-based approaches. While neural network-based methods
usually apply graph convolution to aggregate neighborhood information [9, 10,
11], or use autoencoder to merge structure and node features [1, 2, 12].

Figure 1: A simple example in a citation network. A paper $u$ for visual
question answering (VQA) may simultaneously have citation relationships with
papers in the fields of ML, NLP, and CV because of the related researches it
involves. Through differentiated aggregation, the learned separable
representation by graph disentanglement can reveal more about the latent
semantics among different neighborhoods.

Significant progress in graph representation learning has been made recently,
especially the emergence of graph convolutional networks (GCNs) [13].
Nevertheless, most of the existing methods learn node representation by
treating local neighborhood or node path as a whole, ignoring the subtle
differences between node neighbors. Actually, such practices make model prone
to learning over-smoothed representations when network goes deeper [14]. In
general, a real-world graph is relatively complex and formed by the
interaction of a variety of latent factors. In other words, links between a
node and its neighbors may be caused by different components, which is why
nuances are presented between node neighbors. However, these nuances are often
overlooked by existing methods, limiting the expressiveness of learned node
representations. Instead, we would like to consider the distinction of node
neighbors and disentangle the node representation towards discovering those
distinct latent components with richer information, i.e., graph
disentanglement.

As an example shown in Fig. 1, unlike traditional undifferentiated aggregation
of neighboring nodes by an aggregation function, graph disentanglement aims to
learn the node representation that consists of some distinct latent components
with each containing a certain semantic. Thus, how to disentangle the node
representation into multiple components with distinct latent semantics is of
great significance for graph representation learning, which will also be
helpful for improving the robustness and interpretability of graph neural
network.

In the field of image analysis and understanding, disentanglement learning has
been successfully applied to a variety of tasks, such as foreground separation
and visual reasoning [15, 16]. However, less focus has been put on
disentangled representation learning of graph [17, 18, 19]. Different from
those holistic methods like GCN [9], [17] and [18] have put focus on finding
the difference of latent semantic among node neighborhood information, and
utilized a neighborhood routing mechanism to infer the latent factors by
iteratively analyzing the clusters of component spaces formed by nodes and
their neighbors, thereby learning the disentangled components of node as
representation.

Despite of the essential exploration by [17] and [18], there are still some
key issues that should be addressed: (i) the existing methods attempt to
perform micro-disentanglement by projecting node’s neighborhoods into specific
multiple component spaces, but they lack consideration for the correlations of
them within the component. Inevitably, it will cause the aggregated
representation to be none representative of the latent semantics associated
with the component; (ii) In addition to the micro-disentanglement at the node
level, the components should also be macro-separable at the component
distribution level, while DisenGCN neglects to restrict interdependence among
components; (iii) The disentangled representations should be inversely further
reveal the intrinsic graph structure on the basis of the given initial
adjacency matrix.

To address the above key issues, we propose in this paper an adversarial
disentangled graph convolutional network for graph disentanglement, named as
ADGCN. Specifically, to infer multiple latent factors that originate from the
complex links among graph nodes, we consider simultaneously the intra-
component correlation and inter-component separability to achieve component-
specific aggregation for the micro-disentanglement of the node. Furthermore,
adversarial learning is adopted to restrict the interdependence among
components for the macro-disentanglement of the graph. Besides, the learned
disentangled representation is also used to explore the underlying structure
of the graph progressively. To achieve efficient graph refinement, we propose
a diversity-preserving node sampling method to guided the local structure
aware graph refinement, and further to spread to the overall graph.

We summarize the main contributions as follows:

  * •

We propose a novel Adversarial Disentangled Graph Convolutional Network
(ADGCN), for disentangled graph representation learning, thus to unveil the
associated multiple latent components.

  * •

To achieve micro-disentanglement for each node, a component-specific
aggregation with dynamic assignment mechanism is proposed, which ensures the
compactness of the component space and allocates the neighbors of the target
node to the corresponding component space to realize micro-disentanglement.

  * •

For the purpose of implementing macro-disentanglement at the component
distribution level, we propose an adversarial regularizer to improve the
separability among component distributions, thus learning the more distinct
components.

  * •

To refine the global graph structure in a progressive way, we propose a
diversity-preserving node sampling approach to perform local structure aware
refinement. Hence, the latent global topological graph stucture can be well
reveiled to benefit graph disentanglement.

Figure 2: Architecture overview of a single-layer ADGCN. $A^{(t)}$ represent
the refined adjacency at epoch $t$. $\mathbf{X}$ and $\mathbf{W}_{k}$ denote
the node raw feature and the projection matrix to $k$-th component space
respectively. $\\{\mathbf{h}^{k}_{u}\\}^{K}_{k=1}$ represent the components of
node $u$ and $\mathbf{h}^{(t)}_{u}$ as the output denotes the disentangled
representations at epoch $t$, where $\mathbf{h}^{(t)}_{u}$ is used to update
$A^{(t)}$ to $A^{(t+1)}$ through sample-based graph refinement. ’$+$’ and
’$-$’ represent the real and fake samples that are sampled from
$\mathbf{h}^{(t)}_{u}$ and $\mathbf{c}^{(t)}_{u}$, respectively.

##  II Related Work

###  II-A Graph convolutional networks

Based on graph signal processing theory, some early GNNs [20, 21] implement
graph Fourier transformation [22] in the spectral domain, i.e., spectral
convolution. To reduce the computational cost, the linear filter instead of
the spectral graph convolution was applied in the later work GCN [9], which is
just similar to the message passing in [23]. In addition, the direct graph
convolution in spatial domain was also investigated [11, 24, 10]. However,
these methods are commonly plagued with over-smoothing problem when deeper
model is involved. [14] systematically analyzed the causes of the problem in
GCNs and points out that the propagation process is a special form of Laplace
smoothing. In addition, the expressiveness of GCNs was also further discussed
by [25].

Recently, many works have been proposed to overcome these problems of GCNs in
the aspect of improving propagation methods or aggregation functions. JK-Net
[26] adopted jump connection and layer aggregation mechanism to adaptively
merge features aggregated from different hop subgraphs for each node. Inspired
by PageRank [27], APPNP [27] proposed to separate the transformation from the
propagation. Then, [28] and [29] proposed different adaptive propagation
schemes based on APPNP to capture information from large receptive fields.
However, most of the existing methods ignore the complex genesis of a graph,
which is influenced by multiple factors. Their direct aggregation of
neighboring nodes induces further entanglement of different factors, degrading
the expressiveness of the model. Essentially GAT [10] is also a holistic
approach, although it learns weights for different neighbors. Currently, there
are still less studies on disentangled representation learning of graph data.
DisenGCN [17] first studied the problem of graph disentanglement at node
level. On this basis, IPGDN [18] enhanced the independence constraint of graph
disentanglement by using HSIC [30]. Besides, [19] proposed graph-level
disentangling for graph classification. In contrast to [17] and [18], ADGCN
not only consider the disentanglement of individual nodes, but also impose
constraints at the component distribution level.

###  II-B Adversarial learning on graph

As a powerful generative model, Generative adversarial network has been
proposed by Goodfellow et al. [31]. Then, [32] and [33] successfully applied
adversarial learning to handle graph data for graph generation task. Besides,
The success of [34, 35] shows that GAN and adversarial learning also have
excellent capability for data understanding. Hence, some studies have also
applied adversarial learning to the field of graph representation learning.
[36] and [37] generated node pairs to approximate the linkage distribution,
enhancing the structure-preserving capability of the node representation. And
[38] also proposed to sample sub-graph to learn node embedding for signed
network based on the adversarial learning. Another common practice, as in ARGA
[12] and DBGAN [39], is to utilize adversarial learning as regularizer to
constrain the representation distribution of nodes, thereby improving the
generalization ability of the representations. AIDW [40] adopted similar form
to introduce adversarial learning to [4]. In addition, DGI [41] constructed
degraded graphs for adversarial learning with the original graph. [42]
maintained consistency of node representation between multiple graphs through
adversarial learning. Different from the above works, we apply an adversarial
regularizer to control the separability between component distributions for
graph disentanglement.

##  III Methodology

###  III-A Problem Formulation and Overview of Framework

To begin with some definitions, an undirected graph is given as
$\mathcal{G}=(V,E)$, where $V$ consists of the set of nodes with $|V|=n$, and
$E$ is the set of edges among nodes. To represent the link strength
(similarity) among graph nodes, we use $\mathbf{A}\in R^{n\times n}$ to denote
the adjacency matrix222For a graph with hard link, we have $\mathbf{A}_{i,j}$
= 1 if there exists an edge $(i,j)\in E$, otherwise $\mathbf{A}_{i,j}=0$., and
$\mathbf{D}=diag([\mathbf{d}_{u}]_{u=1,\cdots,n})$ to denote the corresponding
degree matrix with $d_{u}=\sum_{i=1}^{n}\mathbf{A}_{u,i}$. Meanwhile, let
$\mathbf{X}=[\mathbf{x}_{1},\cdots,\mathbf{x}_{n}]\in\mathbb{R}^{n\times f}$
denote the node feature matrix with $\mathbf{x}_{u}\in\mathbb{R}^{f}$,
$u=1,\cdots,n$, representing the raw feature of the $u$-th node, and
$\mathbf{H}=[\mathbf{h}_{1},\cdots,\mathbf{h}_{n}]\in\mathbb{R}^{n\times d}$
the node representation matrix. In addition, $\mathbf{N}(u)$ is defined as a
node subset containing neighbors of node $u$ and
$\tilde{\mathbf{N}}(u)=\mathbf{N}(u)\cup\\{u\\}$.

##### Micro-Disentanglement

Assuming that the graph $\mathcal{G}$ is formed by $K$ latent factors
corresponding to $K$ component spaces. For a specific node $u$, we want to
decompose its latent representation $\mathbf{h}_{u}\in\mathbf{H}$ into $K$
component representations
$\\{\mathbf{h}^{1}_{u},\mathbf{h}^{2}_{u},\cdots,\mathbf{h}^{K}_{u}\\}$, where
$\mathbf{h}^{k}_{u}\in\mathbb{R}^{\frac{d}{K}}$ corresponds to the $k$-th
factor.

##### Macro-Disentanglement

On the basis of micro-disentanglement, for all nodes $V$ in the given graph,
we still expect the component representations lying on different component
spaces are far away from each other, i.e., the difference between any two
component distributions should be evident.

##### Overview of Framework

The overall illustration of the proposed ADGCN model is shown in Fig. 2. For a
specific node $u$ and its neighbors in the given graph, the initial embeddings
$\\{\mathbf{c}^{k}_{i}\\}^{K}_{k=1}$ are first obtained from $\mathbf{x}_{i}$
through projection matrices
$\mathbf{W}=\\{\mathbf{W}_{1},\mathbf{W}_{2},\cdots,\mathbf{W}_{K}\\}$, where
$i\in\tilde{\mathbf{N}}(u)$. Then, through the component-specific aggregation,
$\\{\mathbf{c}^{k}_{i}\\}_{i\in\tilde{\mathbf{N}}(u)}$ are aggregated into
$\mathbf{h}^{k}_{u}$ in the $k$-th component space, and the concatenation of
$\\{\mathbf{h}^{k}_{u}\\}^{K}_{k=1}$ is
$\mathbf{h}_{u}=\textrm{concat}(\mathbf{h}^{1}_{u},\mathbf{h}^{2}_{u},\cdots,\mathbf{h}^{K}_{u})$.
For adversarial learning, $\mathbf{c}^{k}_{u}$ and $\mathbf{h}^{k}_{u}$ are
input into the discriminator $D$ where $\mathbf{c}^{k}_{u}$ and
$\mathbf{h}^{k}_{u}$ are regarded as a ”fake” sample and a ”real” sample
respectively. In addition, $\mathbf{h}_{u}$ is used for graph refining to
update $\mathbf{A}^{(t-1)}$ to $\mathbf{A}^{(t)}$.

###  III-B Component-Specific Aggregation for Micro-Disentanglement

Figure 3: Illustration of component-specific aggregation based on dynamic
assignment. The proposed dynamic assignment iteratively allocates the neighbor
nodes to different component spaces according to the hubness score
$p^{k}_{u\to v}$. Meanwhile, according to the authority score $q^{k}_{v\to u}$
of node $v$ in each component space,
$\\{\mathbf{c}^{k}_{i}\\}_{i\in\tilde{\mathbf{N}}(u)}$ are aggregated into
$\tilde{\mathbf{h}}^{k}_{u}$. Here, only three component spaces are
considered.

Based on an important assumption, i.e., the links between nodes are formed by
the interaction of different latent factors, our DBGAN learn disentangled
components by aggregating the different neighborhood information of the node
to achieve the micro-disentanglement.

Intuitively, if node $u$ and its neighbor node $v$ are similar in the $k$-th
component space, the link between the two nodes is likely caused by the factor
$k$. Furthermore, for a subset $\mathbf{N}_{k}(u)\subseteq\mathbf{N}(u)$, if
all nodes in $\mathbf{N}_{k}(u)$ are connected to node $u$ due to factor $k$,
these nodes should also be similar and form a cluster with $u$ in the $k$-th
component space. It is worth noting that the above two points correspond to
the first-order proximity and the second-order proximity respectively in the
topological structure formed by the factor $k$, respectively [6]. Based on
these two points, DisenGCN [17] proposed a neighborhood routing mechanism,
which was also followed by [18]. However, neighborhood routing mechanism
merely considers the restriction on the separability of inter-component and
constrains that each neighbor should belong to only one component space,
ignoring multi-relations among nodes.

Motivated by the observations mentioned above, we propose a dynamic assignment
mechanism as shown in Fig. 3 to achieve component-specific aggregation for
micro disentanglement. Particularly, to characterize the interactive
relationship between node $u$ and its neighbor node $v\in\mathbf{N}(u)$ in
each component space, we define the hubness score $p^{k}_{u\to v}$ and the
authority score $q^{k}_{v\to u}$ of node $u$ and $v$ in the $k$-th component
space as follows:

$p^{k}_{u\to
v}=\frac{\mathrm{exp}(s^{k}_{uv})}{\sum_{k=1}^{K}\mathrm{exp}(s^{k}_{uv})}$
(1)

$q^{k}_{v\to
u}=\frac{\mathrm{exp}(s^{k}_{uv})}{\sum\limits_{v\in\mathbf{N}(u)}\mathrm{exp}(s^{k}_{uv})}$
(2)

where $s^{k}_{uv}=\cos(\mathbf{h}^{k}_{u},\mathbf{c}^{k}_{v})$ denotes the
similarity between the target node $u$ and its neighbor $v\in\mathbf{N}(u)$ in
the $k$-th component space333To avoid numerical instability caused by
inconsistent norms between different component spaces, $l_{2}$-normalization
is adopted for $h^{k}_{u}$ and $c^{k}_{v}$ to facilitate the calculation of
similarity..

In fact, as a bidirectional information interaction between node $u$ and its
neighbor $v$, the hubness score $p^{k}_{u\to v}$ means the probability that
$v$ is connected to $u$ by factor $k$, and the authority score $q^{k}_{v\to
u}$ refers to the aggregation importance of $v$ for $u$ in the $k$-th
component space. In particular, for a specific neighbor node $v$, the higher
the hubness score $p^{k}_{u\to v}$, the more effective information between $v$
and $u$ have about factor $k$, therefore $v$ will tend to be allocated to the
$k$-th component space for the aggregation of $u$. Meanwhile, a high authority
score $q^{k}_{v\to u}$ means a high similarity between $u$ and $v$ in the
$k$-th component space.

Based on $p^{k}_{u\to v}$ and $q^{k}_{v\to u}$, the proposed dynamic
assignment mechanism can be implemented in an iterative way to obtain the
aggregated representation $\mathbf{h}_{u}^{k}$ by:

${\mathbf{h}^{k}_{u}}=\underbrace{\tilde{\mathbf{h}}^{k}_{u}+\alpha\sum_{v\in\mathbf{N}(u)}q^{k}_{v\to
u}\mathbf{c}^{k}_{v}}_{intra-
component}+\underbrace{\beta\sum_{v\in\mathbf{N}(u)}p^{k}_{u\to
v}\mathbf{c}^{k}_{v}}_{inter-component}$ (3)

where $\tilde{\mathbf{h}}^{k}_{u}$ denotes the aggregated $\mathbf{h}^{k}_{u}$
in previous iteration, $\alpha$ and $\beta$ are trade-off coefficients. The
intra-component part with $q^{k}_{v\to u}$ ensures that $\tilde{h^{k}_{u}}$
tends to be aggregated into the densest area in $k$-th component space, and
the inter-component part with $p^{k}_{u\to v}$ constrains the separability
between $\\{\mathbf{h}^{k}_{u}\\}^{K}_{k=1}$. Meanwhile, different from the
restricted single-relation constraint in [17, 18], the co-aggregation of
intra-component and inter-component also allows for the existence of multiple
relationships between nodes.

To make the proposed ADGCN be capable of inductive learning, we take the
similar way as in [11] by randomly sampling the neighboring nodes of $u$ to
get $\mathbf{N}(u)$ with fixed size. It should be noted that the average
sampling is used for unweighted graphs, and probability sampling based on edge
weights is applied for weighted graphs. The pseudocode of the component-
specific node representation aggregation is summarized in Alg. 1.

Algorithm 1 Procedure of the component-specific aggregation for Micro-
disentanglement

1:$\left\\{\mathbf{x}_{i}\in\mathbb{R}^{f}\right\\}$: the set of node feature
vectors, $i\in\tilde{\mathbf{N}}\left(u\right)$, projection matrices
$\mathbf{W}=\\{\mathbf{W}_{k}\\}_{k=1}^{K}$;

2:$\mathbf{h}_{u}$, $\mathbf{c}_{u}$;

3:$K$: number of component. $\tilde{T}$: iterations of dynamic assignment.
$\alpha,\beta$: trade-off coefficients.

4:for $i\in\tilde{\mathbf{N}}\left(u\right)$ do

5: for $k=1$ to $K$ do

6:
$\mathbf{c}^{k}_{i}\leftarrow\sigma\left(\mathbf{W}_{k}\mathbf{x}_{i}\right)$

7:
$\mathbf{c}^{k}_{i}\leftarrow\frac{\mathbf{c}^{k}_{i}}{\left\|\mathbf{c}^{k}_{i}\right\|_{2}}$

8: end for

9:end for

10:initialize $\tilde{\mathbf{h}}^{k}_{u}=\mathbf{c}^{k}_{u}$

11:for iteration $\tilde{t}=1$ to $\tilde{T}$ do

12: for $v\in\mathbf{N}\left(u\right)$ do

13: $s^{k}_{v}(u)\leftarrow\cos(\mathbf{h}^{k}_{u},\mathbf{c}^{k}_{v})$,
$\forall k=1,\cdots,K$.

14: Calculate $p^{k}_{u\to v}$ and $q^{k}_{v\to u}$ by
Eq.$\left(\ref{p}\right)$ and Eq.$\left(\ref{q}\right)$

15: end for

16: for $k=1$ to $K$ do do

17:
${\mathbf{h}^{k}_{u}}=\tilde{\mathbf{h}}^{k}_{u}+\alpha\sum_{v\in\mathbf{N}(u)}q^{k}_{v\to
u}\mathbf{c}^{k}_{v}+\beta\sum_{v\in\mathbf{N}(u)}p^{k}_{u\to
v}\mathbf{c}^{k}_{v}$

18:
$\mathbf{h}^{k}_{u}=\frac{{\mathbf{h}}^{k}_{u}}{\left\|{\mathbf{h}}^{k}_{u}\right\|_{2}}$

19: $\tilde{\mathbf{h}}^{k}_{u}\leftarrow\mathbf{h}^{k}_{u}$

20: end for

21:end for

22:$\mathbf{c}_{u}\leftarrow$
$\textrm{concat}(\mathbf{c}^{1}_{u},\mathbf{c}^{2}_{u},\cdots,\mathbf{c}^{K}_{u})$

23:$\mathbf{h}_{u}\leftarrow\textrm{concat}(\mathbf{c}^{1}_{u},\mathbf{c}^{2}_{u},\cdots,\mathbf{c}^{K}_{u})$

###  III-C Adversarial Learning for Macro-Disentanglement

Figure 4: The iterative adversarial training tends to progressively improves
the separability among component distributions.

In essence, the goal of disentangled representation learning is to make a
specific component be only sensitive to the variation in the corresponding
factor, while not affected by the one in other factors [43]. In practice, in
addition to the micro-disentanglement mentioned above, there should exist only
weak correlation, or strong separability in other words, among component
distributions corresponding to different factors. To attain the above
objective, we propose an adversarial regularizer to achieve macro-
disentanglement at component distribution level by explicitly imposing
constraints on the interdependence among components.

Specifically, we introduce a discriminator $D$ with two branches $D_{src}$ and
$D_{cls}$. The discrimination branch $D_{src}$ treats the disentangled
component representation $\mathbf{h}^{k}_{u}$ as the ”real” sample, and the
projected representation $\mathbf{c}^{k}_{u}$ as the ”fake” sample. The
auxiliary classification branch $D_{src}$ is added to incorporate factor
information into the discriminator, which allows a single discriminator to
control multiple factors. Thus, the discriminator $D$ not only discriminates
whether the input sample is a disentangled component or not, but also
distinguishes which component distribution it comes from. Here,
$\mathbf{h}^{k}_{u}$ and $\mathbf{c}^{k}_{u}$ are taken as the ”real” sample
and the ”fake” sample for disentanglement, respectively. In order to confuse
the discriminator $D$ as much as possible, $\\{\mathbf{W}_{k}\\}^{K}_{k=1}$
will try to project $\mathbf{x}_{u}$ onto the distributions of the
disentangled components $\\{\mathbf{h}^{k}_{u}\\}^{K}_{k=1}$, , where
$\\{\mathbf{W}_{k}\\}^{K}_{k=1}$ can be regarded as the generator $G$ in GAN.
As shown in Fig. 4, it means that the distributions of
$\\{\mathbf{c}^{k}_{u}\\}^{K}_{k=1}$ will become mutually independent as
training progresses, i.e., $\mathbf{c}^{k}_{u}$ will obey the distribution in
the specific $k$-th component space and be independent of each other.

Therefore, similar to ACGAN [44], the total loss for macro disentanglement is
composed of the adversarial loss and the component classification loss, and
given by:

$\mathcal{L}_{adv}=\mathbb{E}_{\mathbf{h}}[\mathrm{log}D_{src}(\mathbf{h})]+\mathbb{E}_{\mathbf{c}}[\mathrm{log}(1-D_{src}(\mathbf{c}))]$
(4)
$\mathcal{L}_{cls}=\mathbb{E}_{k,\mathbf{h}}[-\mathrm{log}D_{cls}(k|\mathbf{h})]+\mathbb{E}_{k,\mathbf{c}}[-\mathrm{log}(D_{cls}(k|\mathbf{c}))]$
(5)

In essence, $D$ tries to maximize $\mathcal{L}_{adv}$ to distinguish between
$\\{\mathbf{c}^{k}_{u}\\}^{K}_{k=1}$ and $\\{\mathbf{h}^{k}_{u}\\}^{K}_{k=1}$,
while $\\{\mathbf{W}_{k}\\}^{K}_{k=1}$ tries to confuse $D$ by minimizing
$\mathcal{L}_{adv}$ to fit $\\{\mathbf{c}^{k}_{u}\\}^{K}_{k=1}$ to the
distributions of $\\{\mathbf{h}^{k}_{u}\\}^{K}_{k=1}$. By this way, it can
also accelerate the convergence of Algorithm 1. Furthermore, by using
auxiliary classifier to minimize $\mathcal{L}_{cls}$, $D$ can learn to
classify $\mathbf{c}^{k}_{\cdot}$ and $\mathbf{h}^{k}_{\cdot}$ to the
corresponding $k$-th component space. And $\\{\mathbf{W}_{k}\\}^{K}_{k=1}$
also tries to minimize $\mathcal{L}_{cls}$ since $\mathbf{h}^{k}_{u}$ is
derived from $\\{\mathbf{c}^{k}_{i}\\}_{i\in\tilde{\mathbf{N}}(u)}$, it will
be beneficial of boosting the separability among component spaces and making D
to be with stronger discrimination ability. Thereby, we can capture the
multiple disentangled component distributions with weak correlation to each
other to achieve macro-disentanglement.

Since $\mathbf{h}^{k}_{u}$ and
$\\{\mathbf{c}^{k}_{i}\\}_{i\in\tilde{\mathbf{N}}(u)}$ are dynamically
correlated, the conventional GAN training method [31] is not suitable for such
case. Thus, an iterative adversarial training is applied to progressively
improve the separability among component spaces via an EM-like formulation
given by Alg. 3. In fact, the process of aggregating
$\\{\mathbf{c}_{i}\\}^{n}_{i=1}$ into $\\{\mathbf{h}_{i}\\}^{n}_{i=1}$ is
equivalent to the E-step, where $\\{\mathbf{h}_{i}\\}^{n}_{i=1}$ can be seen
as achieving the ‘expectation’. Then, the separability between components is
expected to be maximized by means of adversarial learning, i.e., the
‘maximization’ of the M-step.

###  III-D Local Structure Aware Graph Refinement Based on Diversity-
preserving Node Sampling

Algorithm 2 Local structure aware graph refinement in the $t$-th epoch

1:$\mathcal{G}=(V,E)$,
$\mathbf{H}^{(t-1)}=\left[\mathbf{h}_{1}^{(t-1)},\cdots\mathbf{h}_{n}^{(t-1)}\right]$,
$\mathbf{A}^{(0)}$;

2:$\mathbf{A}^{(t)}$;

3:: $m$, $K$, $\gamma$

4:Initialization: $J_{s}=\phi$ /* Degree-based Node Sampling with Diversity
Preserving */

5:for $u\in V$ do

6: $\mathbf{d}_{u}\leftarrow\sum_{v}^{|V|}\mathbf{A}^{(0)}_{u,v}$

7: $p_{s}(u)\leftarrow\frac{\mathbf{d}_{u}}{\sum_{i=1}^{n}\mathbf{d}_{i}}$

8:end for

9:for $1$ to $m$ do

10: Take a sampling on node $u_{s}$ from $V$ according to $p_{s}(u_{s})$

11: while $v\in\tilde{\mathbf{N}}\left(u_{s}\right)$ do

12: Calculate
$\Delta_{u_{s},v}=\|\mathbf{h}_{u_{s}}^{(t-1)}-\mathbf{h}_{v}^{(t-1)}\|_{2}$

13: $p_{s}(v)\leftarrow p_{s}(v)\cdot f(\Delta_{u_{s},v})$

14: end while

15: $J_{s}\leftarrow J_{s}\cup\\{u_{s}\\}$

16:end for/* Graph Refinement */

17:while sample node $u_{s}\in J_{s}$ do

18: for $k=1$ to $K$ do

19: Select $\mathcal{k}$ nearest neighbors of $\mathbf{h}^{(t-1),k}_{u_{s}}$
as ${\mathbf{N}^{\prime}}\left(u_{s}\right)$

20:
$\tilde{\mathbf{A}}^{(t-1),k}_{u_{s},{\mathbf{N}^{\prime}}\left(u_{s}\right)}\leftarrow\cos(\mathbf{h}^{(t-1),k}_{u_{s}},\mathbf{h}^{(t-1),k}_{{\mathbf{N}^{\prime}}\left(u_{s}\right)})$

21: end for

22:end while

23:$\tilde{\mathbf{A}}^{(t-1)}\leftarrow\textrm{maxpooling}(\tilde{\mathbf{A}}^{(t-1),1},\tilde{\mathbf{A}}^{(t-1),2},\cdots,\tilde{\mathbf{A}}^{(t-1),K})$

24:Obtain the refined $\mathbf{A}^{(t)}$ by Eq.(6).

Algorithm 3 EM-like procedure of the proposed ADGCN

1:$\mathcal{G}=\\{V,E\\}$, $\mathbf{X}$, $A$.

2:$\mathbf{H}$: the node disentangled representation matrix of the given graph

3:: $K$, $\tilde{T}$, $T$, $m$, $\alpha$, $\beta$, $\gamma$, $\lambda$, $\eta$

4:Initialization: $\mathbf{W}=\\{\mathbf{W}_{k}\\}_{k=1}^{K}$: projection
matrix $\theta_{D}$: parameters of the discriminator $D$.

5:for epoch $t=1$ to $T$ do

6: E-step: Obtain $\left\\{\mathbf{h}_{i}^{(t-1)}\right\\}_{i=1}^{n}$ and
$\left\\{\mathbf{c}_{i}^{(t-1)}\right\\}_{i=1}^{n}$ through Alg. 1. Obtain
$A^{(t)}$ through Alg. 2 for graph refinement.

7: M-step: Sample the ”real” components from
$\left\\{\mathbf{h}_{i}^{(t-1)}\right\\}_{i=1}^{n}$. Sample the ”fake”
components from $\left\\{\mathbf{c}_{i}^{(t-1)}\right\\}_{i=1}^{n}$. Update
$\mathbf{W}_{k}$,$k=1,\cdots,K$ by minimizing Eq. (7). Update $\theta_{D}$ by
minimizing Eq. (8).

8:end forreturn
$\mathbf{H}=\left[\mathbf{h}_{1}^{(T-1)},\cdots,\mathbf{h}_{n}^{(T-1)}\right]$.

Figure 5: Illustration of the diversity-preserving graph refinement. Since the
initially given adjacency matrix $\mathbf{A}$ is extremely sparse, we have
marked the existing edges $\mathbf{A}_{ij}$ using a circle for more clear
presentation.

For the real-world graph data, the complex relationship between nodes is often
represented as a hard binary link (i.e., 0 or 1). Obviously, it is a discrete
and simplified form of continuous relationship between nodes, which seriously
limits the expressibility of the learned node representation. On the other
hand, the node representation obtained in the embedding space can in turn be
used to reveal the intrinsic relationship between nodes. To better
characterize the node relationships and further facilitate the learning of
node representation, an intuitive way is to refine the originally given graph
structure with the embedded node representations [45]. However, such global
refinement of the relationships among all nodes without distinction will
inevitably lead to some noisy edges, which may further confuse the training of
the node representation learning model. In addition, it also has scalability
problems on large graphs. To address these issues, we propose a local
structure aware graph refinement as shown in Fig. 5 to progressively reveal
the latent relationships of nodes, thus to achieve efficient and robust graph
refinement.

The key of achieving local structure aware graph refinement is how to obtain a
diversified core subset $J_{s}\subset V$ for local refinement, so as to
maintain the global coverage of the graph as much as possible. Determinant
Point Process (DPP) [46] is a classical algorithm for diversity-preserving
sample selection. However, the high computational cost of DPP is somewhat the
opposite of what we intended. Hence, for local structure aware graph
refinement, we propose an degree-based node sampling method with good
diversity preserving to serve as an efficient approximation of DPP sampling on
graph data.

Considering the characteristics of the graph structure, the normalized degree
centrality indicating the importance of a node is used as the sampling
probability $p_{s}(\cdot)$ for node selection, that is to say, we have
$p_{s}(u)=\frac{\mathbf{d}_{u}}{\sum_{i=1}^{n}\mathbf{d}_{i}}$ for $u$-th
node. Let $J_{s}\subset{V}$, $|J_{s}|=m$, denote the core set to be selected
for local aware graph refinement. To realize the diversity of the selected
core set $J_{s}$, we propose a sequential node selection method by the means
of soft-deflation. Specifically, for a node $u_{s}\in J_{s}$ that has been
selected, a soft-deflation is applied to its each neighbour
$v\in\tilde{\mathbf{N}}\left(u_{s}\right)$, i.e., we will have $p_{s}(v)\cdot
f(\Delta_{u_{s},v})\rightarrow{p_{s}(v)}$, where $f(\cdot)\in[0,1)$ is the
soft-deflation function and $\Delta_{u_{s},v}$ denotes the distance between
$u_{s}$ and its neighbor $v$. Here, we follow the definition of $f(\cdot)$ in
[47] and consider $f(\Delta)=\sin^{2}(\Delta/\tau)$, where $\tau$ is the
scaling factor to keep $\Delta/\tau$ ranging in $[0,\pi/2)$. Through the soft-
deflation in sequential node selection, we can ensure that, for each node in
the associated neighborhood node set $\Psi(J_{s})=\bigcup_{u_{s}\in
J_{s}}\tilde{\mathbf{N}}(u_{s})$, it will be further selected into the core
set with less probability in the subsequent node selection. By this way, it
means that the finally obtained core set $J_{s}$ can achieve the maximum
coverage of the graph to a certain extent.

Then, with the assistance of the diversity-preserving core subset $J_{s}$, the
local structure aware graph refinement can be carried out as follows:

$\displaystyle\mathbf{A}^{(t)}_{u_{s},{\mathbf{N}}\left(u_{s}\right)}=(1-\gamma)\mathbf{A}^{(0)}_{u_{s},{\mathbf{N}}\left(u_{s}\right)}+\gamma\tilde{\mathbf{A}}^{(t-1)}_{u_{s},{\mathbf{N}}\left(u_{s}\right)}$
(6)

where $u_{s}\in J_{s}$, $\mathbf{A}^{(0)}$ represents the initial adjacency
matrix and $\tilde{\mathbf{A}}^{(t-1)}$ denotes the adjacency refining matrix
in the $t$-th epoch, and $\gamma$ is a trade-off coefficient.

As mentioned above, the link relationship between two nodes may come from a
certain component space. To capture the underlying topological structure of
graph, we first obtain $K$ component adjacency matrices
$\\{\tilde{\mathbf{A}}^{(t-1),k}\\}_{k=1}^{K}$ based on the associated node
representations $\\{\mathbf{h}^{(t-1),k}_{u}\\}_{u\in V}$ in $t$-th epoch, and
then an element-wise max pooling is applied to form a component sensitive
adjacency matrix
$\tilde{\mathbf{A}}^{(t-1)}=\mathbf{maxpooling}(\tilde{\mathbf{A}}^{(t-1),1},\tilde{\mathbf{A}}^{(t-1),2},\cdots,\tilde{\mathbf{A}}^{(t-1),K})$.
Essentially, the adopted max pooling plays a role of integrating the specific
structures of multiple latent components into an unified topological one, thus
to boost the link characteristics of nodes.

As a matter of fact, it is not difficult to find from Eq.(6) that the local
aware refinement guided by core set $J_{s}$ can spread to the overall graph,
thus achieving global refinement of graph structure. Meanwhile, it can not
only prevent the introduction of noisy edges in the refinement of graph, but
also help to learn more robust disentangled representations progressively with
the progress of training. The detail about local aware graph refinement with
diversity-preserving node sampling is illustrated in Alg. 2.

##  IV Optimization

We mainly conduct experimental evaluations on node classification task, and
the last layer of ADGCN is designed as a full-connected layer to output the
predicted class label of nodes. Besides, ReLU is used to for activation
following the transformation by the projection matrix
$\mathbf{W}=\\{{\mathbf{W}_{k}}\\}_{k=1}^{K}$. In view of node classification
tasks and macro-disentanglement adversarial regularizer, the overall loss of
ADGCN is as follows:

$\mathcal{L}=\mathcal{L}_{t}+\lambda(\mathcal{L}_{adv}+\eta\mathcal{L}_{cls})$
(7) $\mathcal{L}_{D}=-\mathcal{L}_{adv}+\eta\mathcal{L}_{cls}$ (8)

where $\mathcal{L}_{t}$ denotes the task-aware loss, $\lambda$ and $\eta$ are
hyper-parameters of the adversarial regularizer. For the semi-supervised node
classification task, $\mathcal{L}_{t}$ is the cross-entropy loss. The same as
[17], we use the multi-label soft margin loss as $\mathcal{L}_{t}$ for the
multi-label node classification task, which can be defined as follows:

$\displaystyle\mathcal{L}_{t}=-\frac{1}{C}\sum^{C}_{c=1}$
$\displaystyle[\mathbf{y}_{u}(c)\cdot\log[g(\hat{\mathbf{y}}_{u}(c))]$
$\displaystyle+(1-\mathbf{y}_{u}(c))\cdot\log[g(-\hat{\mathbf{y}}_{u}(c))]]$
(9)

where $g(\cdot)$ denotes the $\mathbf{sigmoid}$ function, $\mathbf{y}_{u}(c)$
and $\hat{\mathbf{y}}_{u}(c)$ denote the true label and the predicted label of
node $u$, respectively. And we optimize the proposed model with Adam optimizer
[48].

##  V Experimental Results and Analysis

###  V-A Evaluation Setup

####  V-A1 Datasets

TABLE I: Statistics of the used datasets. Dataset | Type | Nodes | Edges | Classes | Features | Edge Density | Multi-label
---|---|---|---|---|---|---|---
Citeseer [49] | Citation network | 3327 | 4552 | 6 | 3703 | 0.0008 | No
Cora [50] | Citation network | 2708 | 5278 | 7 | 1433 | 0.0014 | No
Pubmed [51] | Citation network | 19717 | 44324 | 3 | 500 | 0.0002 | No
Coauther CS [52] | Co-authorship network | 18333 | 81894 | 15 | 6805 | 0.0005 | No
Amazon Computers [52] | Co-purchase network | 13381 | 245778 | 10 | 767 | 0.0027 | No
Amazon Photo [52] | Co-purchase network | 7487 | 119043 | 8 | 745 | 0.0042 | No
Wikipedia [53] | Word co-occurrence | 4777 | 184812 | 40 | - | 0.0161 | Yes
Blogcatalog [54] | Social network | 10312 | 333983 | 39 | - | 0.0062 | Yes

In the following experiment, we adopt eight real-world graph datasets and the
statistics about them are summarized in Table I. On the evaluation of the
semi-supervised node classification and clustering, three citation networks
Cora [50], Citeseer [49], and Pubmed [51] are used, whose links and labels
represent citations and research fields, respectively. In addition, we take
three co-authorship and co-purchase graphs, i.e., Coauthor CS [52], Amazon
Computers [52], and Amazon Photo [52], for performance evaluation on the task
of semi-supervised node classification. For the case of multi-label node
classification, Wikipedia [5] and Blogdatalog [54] are used. Wikipedia is a
co-occurrence network whose labels represent the Part-of-Speech (POS) tags.
Blogdatalog is a social network, whose labels and links represent user
interests and social relations between users respectively. Since these two
datasets do not contain node features, we instead use the rows of the
adjacency matrix as node features.

####  V-A2 Comparison methods

To evaluate the performance of ADGCN, we select several baselines for
comparison, especially those that have achieved the state-of-the-art results
recently. Specifically, we mainly consider the following types of baselines:
(i) general baselines,including MLP, Label Propagation (LabelProp) [55],
Planetoid [56]; (ii) spectral convolution-based methods, including ChebNet
[57], GCN [9]; (iii) spatial convolution-based methods, including GAT [10],
MoNet [58], GraphSAGE [11], APPNP [59], SGC [60], AP-GCN [28], ARMA [61], and
IDGL [45]. Besides, we also compare the most related state-of-the-art works in
graph representation learning, i.e., DisenGCN [17] and IPGDN [18]. Due to the
good performance on multi-label node classification, three probabilistic
models DeepWalk [4], LINE [6], and node2vec [5] are also used for comparison.

####  V-A3 Implementation details

To detail the implementation, we define $\Delta d=\frac{d}{K}$ as the
dimension of node components, $K^{(l)}$ as the number of components in the
$l$-th layer, respectively. And $\tilde{T}$ denotes the iterations of the
dynamic assignment in the component-specific aggregation layer.

In semi-supervised node classification, we fix $K^{(l)}$ to $K=5$ for the
adopted six datasets and the dimension of $\mathbf{h}_{u}$ is set to be
$K\cdot\Delta d$. For multi-label node classification task, due to the large
number of tags, we follow the setting in DisenGCN. Specifically, the number
$K$ of the intermediate layers is set to gradually decrease to learn the
hierarchical disentangled representation, and we use skip-connection to
preserve the representation of different levels. As for the output dimension
of the first layer, it is set to $K^{(1)}\cdot\Delta d=128$, where
$K^{(1)}\in\\{4,8,\cdots,32\\}$, $K^{(l)}-K^{(l+1)}=\Delta K\in\\{0,2,4\\}$,
and $\Delta d$ is fixed to $\frac{128}{K^{(1)}}$. As hyper-parameters, both
$K^{(1)}$ and $\Delta K$ are searched through hyperopt [62]. For macro-
disentangled adversarial learning in the above two tasks, both $\lambda$ and
$\eta$ are set to 1. In addition, we tune the other hyper-parameters of ADGCN
using hyperopt. For each hyper-parameter combination, we run 200 epochs and
choose the best combination on the validation set. Then we report the averaged
results over 30 times of execution on each dataset.

TABLE II:  Results on citation datasets with both fixed and random splits in terms of semi-supervised node classification accuracy ($\%$). Models | Cora | CiteSeer | PubMed
---|---|---|---
Fixed | Random | Fixed | Random | Fixed | Random
MLP | $61.6\pm 0.6$ | $59.8\pm 2.4$ | $61.0\pm 1.0$ | $58.8\pm 2.2$ | $74.2\pm 0.7$ | $70.1\pm 2.4$
ChebNet [57] | $80.5\pm 1.1$ | $76.8\pm 2.5$ | $69.6\pm 1.4$ | $67.5\pm 2.0$ | $78.1\pm 0.6$ | $75.3\pm 2.5$
GCN [9] | $81.3\pm 0.8$ | $79.1\pm 1.8$ | $71.1\pm 0.7$ | $68.2\pm 1.6$ | $78.8\pm 0.6$ | $77.1\pm 2.7$
GAT [10] | $83.1\pm 0.4$ | $80.8\pm 1.6$ | $70.8\pm 0.5$ | $68.9\pm 1.7$ | $79.1\pm 0.4$ | $77.8\pm 2.1$
APPNP [59] | $83.3\pm 0.5$ | $\textbf{81.9}\pm 1.4$ | $71.8\pm 0.4$ | $69.8\pm 1.7$ | $80.1\pm 0.2$ | $79.5\pm 2.2$
SGC [60] | $81.7\pm 0.1$ | $80.4\pm 1.8$ | $71.3\pm 0.2$ | $68.7\pm 2.1$ | $78.9\pm 0.1$ | $76.8\pm 2.6$
DisenGCN [17] | $83.1\pm 1.1$ | $80.3\pm 2.0$ | $73.6\pm 0.8$ | $70.1\pm 1.8$ | $79.7\pm 0.7$ | $78.7\pm 1.7$
IPGDN [18] | $84.1$ | - | $74.0$ | - | 81.2 | -
AP-GCN [28] | - | $79.8\pm 3.2$ | - | $69.2\pm 3.0$ | - | $\textbf{79.2}\pm 1.6$
ADGCN | $\textbf{84.3}\pm 0.6$ | $80.8\pm 1.7$ | $\textbf{74.3}\pm 0.7$ | $\textbf{70.4}\pm 1.5$ | $\textbf{81.2}\pm 0.5$ | $\textbf{79.2}\pm 1.7$
ADGCN-R | $\textbf{84.5}\pm 0.7$ | $\textbf{81.0}\pm 2.0$ | $\textbf{74.5}\pm 0.8$ | $\textbf{71.0}\pm 1.4$ | $\textbf{80.4}\pm 0.4$ | $\textbf{79.9}\pm 1.3$
TABLE III:  Results on the other three datasets with random splits in terms of semi-supervised node classification accuracy ($\%$). Models |  | Coauthor
---
CS
| Amazon
---
Computers
| Amazon
---
Photo
MLP | $88.3\pm 0.7$ | $44.9\pm 5.8$ | $69.6\pm 3.8$
LabelProp [55] | $73.6\pm 3.9$ | $70.8\pm 8.1$ | $72.6\pm 11.1$
LabelProp NL [55] | $76.7\pm 1.4$ | $75.0\pm 2.9$ | $83.9\pm 2.7$
GCN [9] | $91.1\pm 0.5$ | $82.6\pm 2.4$ | $91.2\pm 1.2$
GAT [10] | $90.5\pm 0.6$ | $78.0\pm 19.0$ | $85.7\pm 20.3$
MoNet [58] | $90.8\pm 0.6$ | $83.5\pm 2.2$ | $91.2\pm 1.3$
GraphSAGE-mean [11] | $91.3\pm 2.8$ | $82.4\pm 1.8$ | $91.4\pm 1.3$
GraphSAGE-maxpool [11] | $85.0\pm 1.1$ | - | $90.4\pm 1.3$
GraphSAGE-meanpool [11] | $89.6\pm 0.9$ | $79.9\pm 2.3$ | $90.7\pm 1.6$
APPNP [59] | $\textbf{93.2}\pm 0.1$ | $80.1\pm 0.3$ | $89.3\pm 0.2$
DisenGCN [17] | $92.9\pm 0.2$ | $84.6\pm 0.9$ | $91.7\pm 0.7$
ARMA [61] | $92.4\pm 0.3$ | $80.7\pm 0.3$ | $89.4\pm 0.3$
ADGCN | $92.9\pm 0.3$ | $\textbf{84.7}\pm 1.1$ | $\textbf{91.7}\pm 0.4$
ADGCN-R | $\textbf{93.3}\pm 0.4$ | $\textbf{85.2}\pm 0.7$ | $\textbf{92.1}\pm 0.3$

###  V-B Semi-Supervised Node Classification

In view of semi-supervised node classification on Cora, Citeseer, and Pubmed
datasets, we use the same fixed dataset split as GCN with each dataset
containing only 20 labeled nodes for each class, 500 nodes for validation, and
1000 nodes for test. Meanwhile, we also conduct random split as [59], which
uses 20 labeled nodes per class as the training set, 500 nodes as the
validation set, and 1000 nodes as the test set for all models. For Coauthor
CS, Amazon Computers, and Amazon Photo, the random split is also adopted, that
is, 20 labeled nodes per class are taken as the training set, 30 labeled nodes
per class nodes as the validation set, and the rest nodes as the test set.

The comparison results are shown in Table II and Table III, respectively, in
which ADGCN-R denotes ADGCN with graph refinement. Compared with the holistic
approaches such as GAT and GCN, DisenGCN, IPGDN, and ADGCN achieve better
performance, which can be largely due to the disengagement analysis of the
graph structure. In particular, ADGCN outperforms over DisenGCN by about
$0.8\%$, $1.0\%$, and $0.9\%$ on Cora, Citeseer, and Pubmed datasets,
respectively. Besides, ADGCN-R also achieves the best performance on three co-
author/purchase datasets. This just verifies that ADGCN can further boost the
performance and the separability among component distributions, which benefits
from the combination of macro-disentanglement and micro-disentanglement.

###  V-C Multi-Label Node Classification

Following the experiment settings in [5] for multi-label node classification,
we report the performance of each method by increasing the number of nodes
labeled for training from 10 $\%$ to 80 $\%$ of the total number of nodes
$\left|V\right|$, and the other nodes are divided into two sets for
verification and testing. We used two indicators, Macro-F1 and Micro-F1, to
evaluate the performance of each model, and the performances on the two
datasets are shown in Fig.6. It can be observed that our ADGCN performs the
best compared to all baselines including DisenGCN, especially on Wikipedia
dataset. Meanwhile, in terms of Macro-F1, graph disentanglement methods
achieve higher score than other methods. It indicates that graph
disentanglement can facilitate the understanding of the relationship between
nodes, so as to be more robust to graph data with class imbalance.

(a) Macro-F1($\%$), Wikipedia

(b) Micro-F1($\%$), Wikipedia

(c) Macro-F1($\%$), Blogdatalog

(d) Micro-F1($\%$), Blogdatalog

Figure 6: Macro-F1 and Micro-F1 scores on the multi-label classification
tasks.

(a) Original node feature $\mathbf{X}$ (b) Learned representation $\mathbf{H}$
(c) 1st component space (d) 2nd component space

(e) 3rd component space (f) 4th component space (g) 5th component space

Figure 7: Visualization of the node representation similarity matrix on Cora
dataset. (a) the similarity matrix of node feature $\mathbf{X}$, (b) the
similarity matrix of learned node representations. (c), (d), (e), (f), and (g)
are the similarity matrix of node representations in different component
spaces. We use the red and blue box markers to show the entangled relationship
of nodes in different component spaces.

###  V-D Clustering Analysis

For the node clustering task, we use the K-means [63] to cluster the learned
representations as in [18]. The setting of the three citation datasets is the
same as in semi-supervised node classification task with fixed split. The
results of the node clustering are shown in Table IV. It can be observed that
the performance of graph disentangled methods show significant advantage over
other compared methods. Moreover, our ADGCN achieves the best performance
compared to DisenGCN and IPGDN. It means that the proposed macro and micro
disentanglement are greatly beneficial to exploring the inherent similarity
between nodes. Meanwhile, the excellent performance of these graph
disentanglement based methods also demonstrates that graph disentanglement can
indeed provide benefits in terms of graph clustering and community structure
detection.

TABLE IV: Node clustering results(%). Datasets | Metrics | DeepWalk[4] | Planetoid[56] | ChebNet[57] | GCN[9] | GAT[10] | DisenGCN[17] | IPGDN[18] | ADGCN
---|---|---|---|---|---|---|---|---|---
Cora | ACC | 62.2 | 67.2 | 71.9 | 73.5 | 75.2 | 75.5 | 76.1 | 81.0
NMI | 50.3 | 52.0 | 49.8 | 51.7 | 57.0 | 58.4 | 59.2 | 62.3
ARI | 40.8 | 40.5 | 42.4 | 48.9 | 54.1 | 60.4 | 61.0 | 62.1
Citeseer | ACC | 52.1 | 61.0 | 65.0 | 67.7 | 68.0 | 68.2 | 68.9 | 69.3
NMI | 30.5 | 41.2 | 42.6 | 42.8 | 43.1 | 43.7 | 44.3 | 46.6
ARI | 20.6 | 22.1 | 41.5 | 42.8 | 43.6 | 42.5 | 43.0 | 47.6
Pubmed | ACC | 65.2 | 64.6 | 75.2 | 75.6 | 76.3 | 77.0 | 77.8 | 78.4
NMI | 29.6 | 32.5 | 35.6 | 35.0 | 35.0 | 36.1 | 37.0 | 39.2
ARI | 36.6 | 33.9 | 38.6 | 40.9 | 41.4 | 41.6 | 42.0 | 44.1

###  V-E Analysis of Disentanglement

(a) DisenGCN (b) ADGCN

Figure 8: The component confusion matrix $C$ obtained by DisenGCN and ADGCN on
Cora dataset. Here, the group average similarity score is adopted to measure
the correlation between different component distributions. The smaller the
score, the weaker the correlation between the two component distributions.

To intuitively show the disentanglement achieved by ADGCN, we visualize the
similarity matrix of Cora dataset in both the original feature and the learned
representation spaces. In contrast to the original feature in Fig. 7(a), the
similarity matrix based on the learned representation has shown explicitly
block effect as we can see from Fig. 7(b) . It indicates that the
representation learned by our model is capabel of effectively capturing the
intra-class similarity and inter-class differences.

More importantly, to reveal the intrinsic entanglement between different
classes of nodes, we visualize the similarity matrices of the component level,
thus showing the correlations between nodes in different component spaces.
From Fig. 7 (c-g), it can be observed that each component does reflect certain
entangled information among different classes, and the complex entanglements
between different two classes can be well unveiled by the different
combinations of components. Taking the first three classes (marked in red box)
in Fig. 7 as an example, class 1 and class 2 are significantly entangled but
both can be well distinguished from class 3 in the 1st component space. These
three classes also exhibit other different entanglement relationships in the
2nd and 3rd component spaces, respectively. Similarly, the three classes
marked by the blue box also show various entanglement relations in different
component spaces.

As shown in Fig. 8, we also present the component confusion matrix $C$ to
illustrate the correlations among the distributions in different component
spaces. Here, we use the group average similarity to compute $C$.
Specifically, the correlation score between the $i$-th and $j$-th component
distributions is given by $C_{ij}=\frac{1}{|V|^{2}}\sum_{u,v\in
V}\cos(\mathbf{h}^{i}_{u},\mathbf{h}^{j}_{v})$. The smaller the score, the
weaker the correlation between the two component distributions. It’s obvious
that the representations in different component spaces learned by our ADGCN
have weaker correlations compared to DisenGCN [17], which means that ADGCN
indeed achieves macro disentanglement and also validates the effectiveness of
the proposed adversarial regularizer for macro-disentanglement.

###  V-F Evaluation on Progressively Refined Graph Structure

TABLE V: The semi-supervised node classification accuracies of different graph on three datasets. Graph | Datasets
---|---
Cora | Citeseer | Pubmed
$\mathbf{A}$ | 68.0 | 45.3 | 63.0
$\mathbf{A}_{k-NN}$ | 74.9 | 57.5 | 69.4
$\mathbf{A}^{(T)}$ | 77.3 | 63.5 | 72.6

As we know, the adjacency matrix reflects the structure information of graph.
Therefore, to verify the effectiveness of the local aware graph refinement
based on diversity preserving node sampling, the label propagation [55] is
applied to evaluate the ability of the refined adjacency matrix to
characterize node relationships in graph. The performance on the two datasets
is shown in Table.V, where $\mathbf{A}_{k-NN}$ and $\mathbf{A}^{(T)}$ denote
the adjacency matrix constructed by the learned representation $H^{(T)}$ and
the final adjacency matrix refined through progressive graph refinement,
respectively. As we can see that $\mathbf{A}^{(T)}$ performs better than both
$\mathbf{A}$ and $\mathbf{A}_{k-NN}$ by about $9.3\%$ and $2.4\%$,
respectively, on Cora dataset. The results show that the graph refinement
strategy can effectively boost the node representation and the graph structure
collaboratively.

(a) Cora (b) Citeseer

Figure 9: Effectiveness evaluation of Micro-D, Macro-D, and graph refinement
on two datasets, where w/o Micro-D and w/o Marco-D represents ADGCN without
micro disentanglement and ADGCN without macro disentanglement, respectively.
We use the results of semi-supervised node classification to verify the
effectiveness of each part.

###  V-G Ablation Study

Through the semi-supervised node classification on Cora and Citeseer datasets
with random split, we validate the effectiveness of different parts in our
models. As shown in the Fig.9, the proposed macro disentanglement, micro
disentanglement, and diversity-presevering graph refinement are equally
important to learn latent node representation. Here, the baseline model refers
to the GCN with multi-component. Specifically, both ADGCN w/o Macro-D and
ADGCN w/o Micro-D achieve better performance than the baseline, verifying the
usefulness of the two settings. More importantly, the performance of the
combination of Macro-D and Micro-D (i.e., ADGCN) verifies that both Macro-D
and Micro-D are mutually reinforcing. Besides, it’s can be seen that the
adoption of the progressive graph refinement has also provided a further
performance improvement.

###  V-H Hyper-parameter Sensitivity Analysis

Figure 10: Hyper-parameter sensitivity on Cora dataset with fixed split.

We finally study the effect of several hyper-parameters, including the number
of layers, the iterations of dynamic assignment $\tilde{T}$, and the dimension
of component, on Cora dataset with fixed split. The results in Fig.10
demonstrate that: (i) with the number of layers increasing, the performance of
our model tends to be stable without over-smoothing; (ii) due to the
application of the dynamic assignment mechanism, ADGCN can efficiently
complete the aggregation in the component space and achieve better performance
compared to DisenGCN.

##  VI Conclusion

In this paper, we propose an ADGCN model that takes both macro-disentanglement
and micro-disentanglement into account for graph representation learning. By
micro-disentanglement, it can achieve component-specific aggregation of inter-
component and intra-component through the dynamic assignment of node
neighborhood. Furthermore, we innovatively introduce the macro-disentanglement
adversarial regularizer to explicitly constrain the interdependence between
components. Meanwhile, we also propose a local structure aware graph
refinement based on diversity-preserving node sampling. With the training
going on, the global graph structure can be progressively refined to reveal
the latent relationships of nodes. Our ongoing research work will further
explore the interpretability of graph disentanglement and use it for more
realistic graph generation and explainable applications.

## References

  * [1] D. Wang, P. Cui, and W. Zhu, “Structural deep network embedding,” in _Proc. the 22nd ACM SIGKDD Int. Conf. on Knowl. Discovery Data Mining_ , 2016, pp. 1225–1234.
  * [2] T. N. Kipf and M. Welling, “Variational graph auto-encoders,” _arXiv preprint arXiv:1611.07308_ , 2016.
  * [3] L. Tang and H. Liu, “Leveraging social media networks for classification,” _Data Mining and Knowledge Discovery_ , vol. 23, no. 3, pp. 447–478, 2011\.
  * [4] B. Perozzi, R. Al-Rfou, and S. Skiena, “Deepwalk: Online learning of social representations,” in _Proc. 20th ACM SIGKDD Inf. Conf. on Knowl. Discovery Data Mining_ , 2014, pp. 701–710.
  * [5] A. Grover and J. Leskovec, “node2vec: Scalable feature learning for networks,” in _Proc. 22nd ACM SIGKDD Inf. Conf. on Knowl. Discovery Data Mining_ , 2016, pp. 855–864.
  * [6] J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei, “Line: Large-scale information network embedding,” in _Proc. 24th World Wide Web_ , 2015, pp. 1067–1077.
  * [7] J. Qiu, Y. Dong, H. Ma, J. Li, K. Wang, and J. Tang, “Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec,” in _Proc. the Eleventh ACM Int. Conf. on Web Search and Data Mining_ , 2018, pp. 459–467.
  * [8] S. Cao, W. Lu, and Q. Xu, “Grarep: Learning graph representations with global structural information,” in _Proc. 24th ACM on Conf. Inf. Knowl. Manage_ , 2015, pp. 891–900.
  * [9] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” _arXiv preprint arXiv:1609.02907_ , 2016.
  * [10] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio, “Graph attention networks,” in _Proc. Int. Conf. Learn. Represent._ , 2018.
  * [11] W. Hamilton, Z. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” in _Proc. Adv. Neural Inf. Process. Syst._ , 2017, pp. 1024–1034.
  * [12] S. Pan, R. Hu, G. Long, J. Jiang, L. Yao, and C. Zhang, “Adversarially regularized graph autoencoder for graph embedding,” _arXiv preprint arXiv:1802.04407_ , 2018.
  * [13] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and S. Y. Philip, “A comprehensive survey on graph neural networks,” _IEEE Trans. Neural Netw. Learn. Syst._ , 2020.
  * [14] K. Xu, W. Hu, J. Leskovec, and S. Jegelka, “How powerful are graph neural networks?” _arXiv preprint arXiv:1810.00826_ , 2018.
  * [15] H.-Y. Lee, H.-Y. Tseng, Q. Mao, J.-B. Huang, Y.-D. Lu, M. Singh, and M.-H. Yang, “Drit++: Diverse image-to-image translation via disentangled representations,” _Int. Journal of Comput. Vis._ , pp. 1–16, 2020.
  * [16] S. van Steenkiste, F. Locatello, J. Schmidhuber, and O. Bachem, “Are disentangled representations helpful for abstract visual reasoning?” in _Proc. Adv. Neural Inf. Process. Syst._ , 2019, pp. 14 245–14 258.
  * [17] J. Ma, P. Cui, K. Kuang, X. Wang, and W. Zhu, “Disentangled graph convolutional networks,” in _Proc. 36th Int. Conf. on Mach. Learn._ , 2019, pp. 4212–4221.
  * [18] Y. Liu, X. Wang, S. Wu, and Z. Xiao, “Independence promoted graph disentangled networks.” in _Proc. the AAAI Conf. on Artif. Intell_ , 2020, pp. 4916–4923.
  * [19] Y. Yang, Z. Feng, M. Song, and X. Wang, “Factorizable graph convolutional networks,” _arXiv preprint arXiv:2010.05421_ , 2020.
  * [20] J. Bruna, W. Zaremba, A. Szlam, and Y. LeCun, “Spectral networks and locally connected networks on graphs,” _arXiv preprint arXiv:1312.6203_ , 2013.
  * [21] M. Defferrard, X. Bresson, and P. Vandergheynst, “Convolutional neural networks on graphs with fast localized spectral filtering,” _arXiv preprint arXiv:1606.09375_ , 2016.
  * [22] D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst, “The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains,” _IEEE Signal Process. Mag._ , vol. 30, no. 3, pp. 83–98, 2013.
  * [23] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl, “Neural message passing for quantum chemistry,” in _Proc. 34th Int. Conf. on Mach. Learn._ , 2017, pp. 1263–1272.
  * [24] S. Kearnes, K. McCloskey, M. Berndl, V. Pande, and P. Riley, “Molecular graph convolutions: moving beyond fingerprints,” _Journal of Computer-Aided Molecular Design_ , vol. 30, no. 8, pp. 595–608, 2016.
  * [25] C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe, “Weisfeiler and leman go neural: Higher-order graph neural networks,” in _Proc. the AAAI Conf. on Artif. Intell_ , vol. 33, no. 01, 2019, pp. 4602–4609.
  * [26] K. Xu, C. Li, Y. Tian, T. Sonobe, K.-i. Kawarabayashi, and S. Jegelka, “Representation learning on graphs with jumping knowledge networks,” in _Proc. 35th Int. Conf. on Mach. Learn._ PMLR, 2018, pp. 5453–5462.
  * [27] L. Page, S. Brin, R. Motwani, and T. Winograd, “The pagerank citation ranking: Bringing order to the web.” Stanford InfoLab, Tech. Rep., 1999.
  * [28] I. Spinelli, S. Scardapane, and A. Uncini, “Adaptive propagation graph convolutional network,” _IEEE Trans. Neural Netw. Learn. Syst._ , 2020.
  * [29] M. Liu, H. Gao, and S. Ji, “Towards deeper graph neural networks,” in _Proc. the 26th ACM SIGKDD Inf. Conf. on Knowl. Discovery Data Mining_ , 2020, pp. 338–348.
  * [30] L. Song, A. Smola, A. Gretton, K. M. Borgwardt, and J. Bedo, “Supervised feature selection via dependence estimation,” in _Proc. 24th Int. Conf. on Mach. Learn._ , 2007, pp. 823–830.
  * [31] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio, “Generative adversarial nets,” in _Proc. Adv. Neural Inf. Process. Syst._ , 2014, pp. 2672–2680.
  * [32] N. De Cao and T. Kipf, “Molgan: An implicit generative model for small molecular graphs,” _arXiv preprint arXiv:1805.11973_ , 2018.
  * [33] A. Bojchevski, O. Shchur, D. Zügner, and S. Günnemann, “Netgan: Generating graphs via random walks,” in _Proc. 35th Int. Conf. on Mach. Learn._ , 2018, pp. 610–619.
  * [34] J. Donahue, P. Krähenbühl, and T. Darrell, “Adversarial feature learning,” _arXiv preprint arXiv:1605.09782_ , 2016.
  * [35] V. Dumoulin, I. Belghazi, B. Poole, O. Mastropietro, A. Lamb, M. Arjovsky, and A. Courville, “Adversarially learned inference,” _arXiv preprint arXiv:1606.00704_ , 2016.
  * [36] H. Wang, J. Wang, J. Wang, M. Zhao, W. Zhang, F. Zhang, X. Xie, and M. Guo, “Graphgan: Graph representation learning with generative adversarial nets,” in _Proc. 32nd AAAI Conf. on Artif. Intell_ , 2018.
  * [37] H. Gao, J. Pei, and H. Huang, “Progan: Network embedding via proximity generative adversarial network,” in _Proc. 25th ACM SIGKDD Int. Conf. on Knowl. Discovery Data Mining_ , 2019, pp. 1308–1316.
  * [38] Y.-C. Lee, N. Seo, K. Han, and S.-W. Kim, “Asine: Adversarial signed network embedding,” in _Proc. the 43rd Int. ACM SIGIR Conf. on Research and Development in Information Retrieval_ , 2020, pp. 609–618.
  * [39] S. Zheng, Z. Zhu, X. Zhang, Z. Liu, J. Cheng, and Y. Zhao, “Distribution-induced bidirectional generative adversarial network for graph representation learning,” in _Proc. IEEE Conf. on Comput. Vis. and Pattern Recognit._ , June 2020.
  * [40] Q. Dai, Q. Li, J. Tang, and D. Wang, “Adversarial network embedding,” in _Proc. 32nd AAAI Conf. on Artif. Intell_ , 2018.
  * [41] P. Veličković, W. Fedus, W. L. Hamilton, P. Liò, Y. Bengio, and R. D. Hjelm, “Deep graph infomax,” _arXiv preprint arXiv:1809.10341_ , 2018\.
  * [42] Q. Lu, N. de Silva, D. Dou, T. H. Nguyen, P. Sen, B. Reinwald, and Y. Li, “Exploiting node content for multiview graph convolutional network and adversarial regularization,” in _Proc. 28th Int. Conf. on Comput. Linguis._ , 2020, pp. 545–555.
  * [43] R. Suter, D. Miladinovic, B. Schölkopf, and S. Bauer, “Robustly disentangled causal mechanisms: Validating deep representations for interventional robustness,” in _Proc. 36th Int. Conf. on Mach. Learn._ , 2019, pp. 6056–6065.
  * [44] A. Odena, C. Olah, and J. Shlens, “Conditional image synthesis with auxiliary classifier gans,” in _Proc. 34th Int. Conf. on Mach. Learn._ , 2017, pp. 2642–2651.
  * [45] Y. Chen, L. Wu, and M. Zaki, “Iterative deep graph learning for graph neural networks: Better and robust node embeddings,” _Proc. Adv. Neural Inf. Process. Syst._ , vol. 33, 2020.
  * [46] J. B. Hough, M. Krishnapur, Y. Peres, B. Virág _et al._ , “Determinantal processes and independence,” _Probability surveys_ , vol. 3, pp. 206–229, 2006.
  * [47] C. Wachinger and P. Golland, “Diverse landmark sampling from determinantal point processes for scalable manifold learning,” _arXiv preprint arXiv:1503.03506_ , 2015.
  * [48] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _arXiv preprint arXiv:1412.6980_ , 2014.
  * [49] P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Galligher, and T. Eliassi-Rad, “Collective classification in network data,” _AI magazine_ , vol. 29, no. 3, pp. 93–93, 2008.
  * [50] Q. Lu and L. Getoor, “Link-based classification,” in _Proc. 20th Int. Conf. on Mach. Learn._ , 2003, pp. 496–503.
  * [51] G. Namata, B. London, L. Getoor, B. Huang, and U. EDU, “Query-driven active surveying for collective classification,” in _10th Int. Workshop on Mining and Learning with Graphs_ , 2012, p. 8.
  * [52] O. Shchur, M. Mumme, A. Bojchevski, and S. Günnemann, “Pitfalls of graph neural network evaluation,” _arXiv preprint arXiv:1811.05868_ , 2018.
  * [53] K. Toutanova, D. Klein, C. D. Manning, and Y. Singer, “Feature-rich part-of-speech tagging with a cyclic dependency network,” ser. NAACL ’03, 2003, p. 173–180.
  * [54] L. Tang and H. Liu, “Relational learning via latent social dimensions,” in _Proc. the 15th ACM SIGKDD Int. Conf. on Knowl. Discovery Data Mining_. New York, NY, USA: Association for Computing Machinery, 2009. [Online]. Available: https://doi.org/10.1145/1557019.1557109
  * [55] X. Zhu, Z. Ghahramani, and J. D. Lafferty, “Semi-supervised learning using gaussian fields and harmonic functions,” in _Proc. 20th Int. Conf. on Mach. Learn._ , 2003, pp. 912–919.
  * [56] Z. Yang, W. Cohen, and R. Salakhudinov, “Revisiting semi-supervised learning with graph embeddings,” in _Proc 33th Int. Conf. on Mach. Learn._ PMLR, 2016, pp. 40–48.
  * [57] M. Defferrard, X. Bresson, and P. Vandergheynst, “Convolutional neural networks on graphs with fast localized spectral filtering,” in _Proc. Adv. Neural Inf. Process. Syst._ , 2016, pp. 3844–3852.
  * [58] F. Monti, D. Boscaini, J. Masci, E. Rodola, J. Svoboda, and M. M. Bronstein, “Geometric deep learning on graphs and manifolds using mixture model cnns,” in _Proc. IEEE Conf. on Comput. Vis. and Pattern Recognit._ , 2017, pp. 5115–5124.
  * [59] J. Klicpera, A. Bojchevski, and S. Günnemann, “Predict then propagate: Graph neural networks meet personalized pagerank,” _arXiv preprint arXiv:1810.05997_ , 2018.
  * [60] F. Wu, A. Souza, T. Zhang, C. Fifty, T. Yu, and K. Weinberger, “Simplifying graph convolutional networks,” in _Proc. 36th Int. Conf. on Mach. Learn._ , 2019, pp. 6861–6871.
  * [61] F. M. Bianchi, D. Grattarola, L. Livi, and C. Alippi, “Graph neural networks with convolutional arma filters,” _IEEE Trans. Pattern Anal. Mach. Intell_ , 2021.
  * [62] J. Bergstra, D. Yamins, and D. Cox, “Making a science of model search: Hyperparameter optimization in hundreds of dimensions for vision architectures,” in _Proc. 30th Int. Conf. on Mach. Learn._ , 2013, pp. 115–123.
  * [63] S. Lloyd, “Least squares quantization in pcm,” _IEEE Trans. Info. Theory._ , vol. 28, no. 2, pp. 129–137, 1982.