USER: Unsupervised Structural Entropy-based Robust Graph Neural Network
Unsupervised/self-supervised graph neural networks (GNN) are vulnerable to
inherent randomness in the input graph data which greatly affects the
performance of the model in downstream tasks. In this paper, we alleviate the
interference of graph randomness and learn appropriate representations of nodes
without label information. To this end, we propose USER, an unsupervised robust
version of graph neural networks that is based on structural entropy. We
analyze the property of intrinsic connectivity and define intrinsic
connectivity graph. We also identify the rank of the adjacency matrix as a
crucial factor in revealing a graph that provides the same embeddings as the
intrinsic connectivity graph. We then introduce structural entropy in the
objective function to capture such a graph. Extensive experiments conducted on
clustering and link prediction tasks under random-noises and meta-attack over
three datasets show USER outperforms benchmarks and is robust to heavier
randomness.
Yifei Wang, Yupan Wang, Zeyu Zhang, Song Yang, Kaiqi Zhao, Jiamou Liu
# USER: Unsupervised Structural Entropy-based Robust Graph Neural Network

###### Abstract

Unsupervised/self-supervised graph neural networks (GNN) are vulnerable to inherent randomness in the input graph data which greatly affects the performance of the model in downstream tasks. In this paper, we alleviate the interference of graph randomness and learn appropriate representations of nodes without label information. To this end, we propose USER, an unsupervised robust version of graph neural networks that is based on structural entropy. We analyze the property of intrinsic connectivity and define intrinsic connectivity graph. We also identify the rank of the adjacency matrix as a crucial factor in revealing a graph that provides the same embeddings as the intrinsic connectivity graph. We then introduce structural entropy in the objective function to capture such a graph. Extensive experiments conducted on clustering and link prediction tasks under random-noises and meta-attack over three datasets show USER outperforms benchmarks and is robust to heavier randomness. 1

Footnote 1: Full proof, experimental details, and code of our work is available at [https://github.com/wangyifeibeijing/USER](https://github.com/wangyifeibeijing/USER).

## 1 Introduction

Neural-based methods for processing complex graph data have become indispensable to a wide range of application areas from social media mining, recommender systems, to biological data analysis and traffic prediction. _Graph representation learning_ (GRL) plays a central role in these methods, providing vectorized graph encodings which are crucial for downstream tasks such as community detection, link prediction, node classification, and network visualization [14]. Among the many GRL methods that emerged in recent years, _graph neural network_ (GNN) [15, 16, 17, 18] provides a powerful paradigm that extracts graph encodings through a recursive aggregation scheme [16]. The aggregation scheme learns a node's embedding using both the feature of the node itself and aggregated feature of its neighbours, thereby capturing structural information of the graph. The advantage of GNN-based models has been attested by outstanding performance on many tasks [16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32].

Despite the successes above, the performance of a GNN-based model hinges on reliable input graph data [15, 16, 17]. More specifically, small perturbation on the input graph may ends in drastically different encodings after the recursive aggregation scheme (see Figure 1). However, The randomness of input graph is inevitable. As [17] discussed, the edges in the graph are formed randomly, following an underlying intrinsic connectivity distribution of nodes. [16] asserts that such distribution is highly inhomogeneous, with edges concentrated within some conglomerates of nodes, resulting in a community structure. Each conglomerate is called a community: they have dense inner-connections but sparse inter-connections. The community structure of a network can be interpreted in a probabilistic way: A fixed but unknown edge (probabilisty) distribution is presented between any pairs of nodes that determines a community structure, yet we only observe a _sample_ from this distribution. This inherent randomness triggers the perturbations in the input graph that interferes the recursive aggregation scheme.

It is therefore desirable to develop a model that captures the so-called "_intrinsic connectivity graph_", a graph that reflects the intrinsic connectivity in the dataset. A straightforward approach is to unravel the intrinsic connectivity graph from node labels that indicates the communities. However, ground truth labels are often not available in real-world applications. Our task is thus to develop an _unsupervised_ approach for unsupervised/self-supervised GNN. For this task, one needs to address the following three challenges: **(a)** The first challenge demands an operational criterion for alleviating the interference of graph randomness2. Since ground truth labels are not present, we need to find a new criterion to find a graph that mitigates the interference of graph randomness. **(b)** Given such a criterion in (a), the second challenge concerns how a graph that meets it can be learnt. More precisely, this challenge seeks for an objective function that guides to reveal a new graph that satisfies the crite
tion. **(c)** The third challenge seeks a framework to generate the new graph. Common GNN models generate graphs with the node embedding results. However, [14] assert that graphs generated from interfered node embeddings are unreliable. A desirable solution to this question would be learning embeddings and the new graph simultaneously.

For **(a)**, we will show in **Section 3** that there exist multiple "ininocuous graphs" for which GNN may produce the same embeddings as the desired intrinsic connectivity graph. We call these graphs _GNN-equivalent_. Thus any one of such innocuous graphs can help GNN mitigate the interference of randomness. As the number of groups in the intrinsic connectivity graph (the number of communities \(c\)) is known for many datasets, we justify two assertions about the innocuous graphs: For the innocuous graphs, the rank of its corresponding adjacency matrix is no less than the number of groups in the intrinsic connectivity graph. Then, if we partition innocuous graphs into groups with high concentrations of edges inside groups, and low concentrations between them, features of two nodes that in the same group should be relatively similar. These assertions direct our pursuit for innocuous graph.

For **(b)**, to reflects all assertions above, we develop a tool to learn a graph that satisfies the conditions above. In **Section 4**, we invoke structural information theory [10, 10, 11]. Through a class of _structural entropy_ measures, structural information theory recently emerges to capture intrinsic information contained within a graph structure and have been increasingly applied to graph learning. Here, we connect the notion of network partition structural information (NPSI), a type of structural entropy, with the rank of the adjacency matrix and show that minimizing structural entropy would facilitate the search for a innocuous graph.

For **(c)**, we combine the tools developed above and design a novel framework, called **U**nsupervised **S**tructural **E**ntropy-based **R**obust graph neural network (USER), to support GNN with a trainable matrix to learn the adjacency matrix of an innocuous graph. See **Section 5**. Our method makes it possible to learn the innocuous graph structure and the node embeddings simultaneously. As the embeddings are derived from the innocuous graph, rather than the input graph, they are tolerant to randomness.

We developed a series of experiments to validate our USER framework. These experiment results show that on both clustering and link prediction tasks, with the support of USER, even traditional GAE model surpasses state of the art baselines. We inject randomness into the graph. With \(50\%\) random noises, accuracy of USER improves from SOTA by up to \(14.14\%\) for clustering on well-known Cora dataset, while improvement for link prediction reaches \(13.12\%\) on Wiki dataset. Moreover, USER exhibits higher advantage in the presence of adversarial attacks. Facing \(20\%\) meta-attack [22], USER's improvements over SOTA is up to \(190.01\%\) for clustering on Citeseer. Our contributions can be summarized as follows:

* We are the first to introduce the notion of GNN-equivalent and innocuous graph. We utilize them for mitigating the interference of graph randomness;
* We proposed a structural entropy-based objective function that is suitable for learning the innocuous graph;
* We conduct extensive experiments, which show that USER performs effectively confronting randomness.

## 2 Related Work

**GRL and GNN.** Graph representation learning (GRL) generates vectorized encoding from graph data. Nowadays GRL is instrumental in many tasks that involves the analysis of graphs [1]. As a mainstream GRL paradigm, graph neural network (GNN) captures a node's structural information and node features by recursively aggregating its neighborhood information using an _information aggregation scheme_. Based on this idea, Graph Autoendoer (GAE) and Variational GAE (VGAE) [15] are developed to use GCN [15] as an encoder to learn node embeddings, and an inner product decoder to reconstruct the graph structure. As a variant of GAE, ARGA [13] trains an adversarial network to learn more robust node embeddings. To alleviate the high-frequency noises in the node features, Adaptive Graph Encoder (AGE) [16] utilizes a Laplacian smoothing filter to prepossess the node features. Different from reconstructing the graph structure, maximizing the _mutual information_ (MI) [12] is another well-studied approach for GRL. For example, the model DGI [17] employs GNN to learn node embeddings and a graph-level embedding, then maximize MI between them to improve the representations' quality. The model GIC [18] follows this idea and seeks to additionally capture community-level information of the graph structure.

Despite GNN's outstanding performance, studies have demonstrated that small perturbation on the input graph can fool the GNN [10, 11, 12]. However, the GNN-based approach is not only able to learn node embeddings, but also to learn node embeddings.

Figure 1: Modifying an edge causes more than half of the nodes’ embeddings to change after two rounds of aggregation
Kokel 2021; Wu et al. 2019b). These perturbations are inevitable, especially for unsupervised models. New learning paradigms are proposed to alleviate the influence of such perturbations. The model Cross-graph (Wang et al. 2020) maintains two autoencoders. Every encoder learns node embeddings and reconstructs adjacency matrix to be passed to the peer-autencoder as the input for the next iteration. _Graph contrastive learning (G-CL)_ models such as GCA (Zhu et al. 2021b) also improve the robustness of GNN. These methods construct data augmentation and negative pairs by modifying the input graph structure. However, none of these works explain how these perturbations were formed. In this paper, inspired by (Wang et al. 2019b; Fortunato 2010; Zhang et al. 2019; Wu et al. 2019a; Zhu and Koniusz 2020) we introduce the notion of innocuous graph to learn the embeddings same to these corresponding to the intrinsic connectivity graph, which helps GNN models to mitigate the impact of randomness.

**Structural entropy.** Structural entropy is a major tool utilized in our paper. An entropy measure has long been sought after in computer science to analyze the intrinsic information embodied in structures (Brooks Jr 2003). Several classical entropy measures have been designed for this purpose (Dehmer 2008; Anand and Bianconi 2009). In particular, the model infomap (Rosvall, Axelsson, and Bergstrom 2009) tries to analyze graphs with a form of entropy defined on random walks. In (Li and Pan 2016; Li et al. 2016), the authors re-invented structural information theory and proposed a hierarchy of _structural entropy_ to analyze networks. This notion has been utilized in several work, e.g., (Liu et al. 2019, 2022; Chen and Liu 2019), to adversarial graph learning. However, to date, no study has attempted to integrate structural entropy with enhance GNN's resilience to randomness in graph data.

## 3 Criteria to Mitigate Randomness

We use \(\vec{x},\vec{y},\ldots\) to denote vectors where \(x_{i}\) denotes the \(i\)th entry of \(\vec{x}\). We use capital letters \(X,Y,A,\ldots\) to denote real-valued matrices. For any matrix \(M\), \(M_{i}\) denotes the \(i\)th row vector and \(M_{ij}\) denotes the \((i,j)\)th entry of \(M\). In this paper, we focus on undirected, unweighted graphs where every node is associated a \(d\)-dimensional feature vector. Formally, such a graph can be denoted by \(\mathcal{G}=(\mathcal{V},\mathcal{E},X)\) where \(\mathcal{V}\) is a set of \(n\) nodes \(\{v_{1},\ldots,v_{n}\}\), \(\mathcal{E}\) is a set of edges \(\{v_{i},v_{j}\}\), and \(X\in\mathcal{M}_{n,d}(\mathbb{R})\) denotes the _feature matrix_ where \(X_{i}\) is the feature vector of node \(v_{i}\). The pair \((\mathcal{V},\mathcal{E})\) is represented by an _adjacent matrix_\(A\in\mathcal{M}_{n}(\{0,1\})\), where \(A_{ij}=1\) if \(\{v_{i},v_{j}\}\in\mathcal{E}\). Here we assume the graph does not contain any isolated node. Indeed, most studies on GNN omit isolated nodes before training (Kipf and Welling 2016; Mavro-matis and Karypis 2021). At last, we use \(\mathcal{C}_{0},\mathcal{C}_{1},\ldots\mathcal{C}_{c-1}\) to denote \(c\) sets of nodes. If they satisfy: \(k\neq m\Rightarrow\mathcal{C}_{k}\cap\mathcal{C}_{m}=\varnothing\) and \(\forall k<c\colon\mathcal{C}_{k}\neq\varnothing\), we call them partitions.

Taking input graph \(\mathcal{G}\), a _graph neural network (GNN)_ can be denoted by the function

\[\mathsf{GNN}\left(A,X,\left\{W^{(\ell)}\right\}\right)=H^{(t)} \tag{1}\]

where \(H^{(0)}=X\) and

\[H^{(\ell)}=\sigma(\text{agg}(AH^{(\ell-1)}W^{(\ell)}))\text{ for all }\ell\in(0,t],\]

\(H^{(\ell)}\in\mathbb{R}^{n\times d^{\ell}}\), \(W^{(\ell)}\in\mathbb{R}^{d^{(\ell-1)}\times d^{(\ell)}}\), and \(d^{(0)}=d\). Here \(H^{(\ell)}\) is the matrix learned by the \(\ell\)th information aggregation layer and \(H^{(0)}=X\), taking the original features as the input to the \(1\)st layer; \(\sigma(\cdot)\) is the activation function; \(\text{agg}(\cdot)\) is the aggregation; and \(W^{(\ell)}\) contains learnable parameters. GNN with non-injective \(\sigma(\cdot)\) and \(\text{agg}(\cdot)\) are inefficient when learning graph structures (Xu et al. 2019). Thus we only discuss GNN with injective \(\sigma(\cdot)\) and \(\text{agg}(\cdot)\) functions. By (1), in GNN models, the vector representation of a node is computed with not only its own features but also features of its neighbors accumulated recursively.

As mentioned above, a real-world input graph dataset is inherently random and unstable (Jin et al. 2020b). On the other hand, such datasets would reflect certain hidden but stable underlying _intrinsic connectivity_ distribution (Wang et al. 2019b; Fortunato 2010). (Fortunato 2010) asserts that for a dataset which can be naturally separated, say, into \(c\) partitions (or _classes_ in a node classificial task), intrinsic connectivity satisfies that nodes in the same partition are more likely to be connected than nodes in different partitions. We capture this intrinsic connectivity with the next definition.

**Definition 3.1** (Intrinsic connectivity graph): _For a dataset that contains \(c\) partitions, suppose \(\mathcal{G}_{I}=(\mathcal{V},\mathcal{E}_{I})\) satisfies: For any two nodes \(v_{i}\) and \(v_{j}\), there exists an edge \((v_{i},v_{j})\in\mathcal{E}_{I}\) iff \(v_{i}\) and \(v_{j}\) belong to the same partition. We call \(\mathcal{G}_{I}\) the intrinsic connectivity graph._

Let \(Rank(M)\) denote the rank of a matrix \(M\).

**Theorem 3.1** (Rank of \(\mathcal{G}_{I}\)'s adjacency matrix \(A_{I}\)): _For a dataset that contains \(c\) partitions, we have \(Rank(A_{I})=c\) where \(A_{I}\) is \(\mathcal{G}_{I}\)'s adjacency matrix._

Our aim is to extract a new graph from a real-world dataset to mitigate the interference of graph randomness. Without ground truth label, finding this intrinsic connectivity graph is impractical. However, we observe that, GNN may learn the same embeddings from different input graphs:

**Definition 3.2** (GNN-equivalent): _Let \(\mathcal{G}_{0}=(\mathcal{V},\mathcal{E}_{0},X)\) and \(\mathcal{G}_{1}=(\mathcal{V},\mathcal{E}_{1},X)\) be two graphs with the same set of nodes and adjacency matrices \(A_{0}\) and \(A_{1}\), respectively. Suppose we run GNN respectively on these two graph, and the following holds: for any feature matrix \(X\). in each layer \(\ell\), and any \(W_{0}^{(\ell)}\), there exist weights \(W_{1}^{(\ell)}\) such that:_

\[\sigma(\text{agg}(A_{0}H^{(\ell-1)}W_{0}^{(\ell)}))=\sigma(\text{agg}(A_{1}H^ {\ell-1})W_{1}^{(\ell)})).\]

_Then we call \(\mathcal{G}_{0}\) and \(\mathcal{G}_{1}\) GNN-equivalent._

By Def. 3.2, when \(\mathcal{G}_{1}\) is GNN-equivalent to \(\mathcal{G}_{0}\), a GNN with \(\mathcal{G}_{1}\) as input may learn the same embeddings as if \(\mathcal{G}_{0}\) is the input. Thus using graphs GNN-equivalent to intrinsic connectivity graph \(\mathcal{G}_{I}\) makes it possible for the GNN to learn the same embeddings as inputting \(\mathcal{G}_{I}\). We call such a graph _innovucous_.

**Definition 3.3** (innocuous graph): _Suppose \(\mathcal{G}_{I}\) is the intrinsic connectivity graph for a dataset. An innocuous graph \(\mathcal{G}^{\prime}\) is one that is GNN-equivalent to \(\mathcal{G}_{I}\)._
To search for such graphs, we introduce the necessary condition for being GNN-equivalent to a specific graph:

**Theorem 3.2** (necessary condition of GNN-equivalence): \(\mathcal{G}_{1}\) _is GNN-equivalent to \(\mathcal{G}_{0}\) only if \(\ Rank(A_{1})\geq Rank(A_{0})\)._

**Corollary 3.1** (necessary condition of innocuous graph): \(\mathcal{G}^{\prime}\) _is a innocuous graph only if \(Rank(A^{\prime})\geq Rank(A_{I})\)._

By Theorem 3.1 and Corollary 3.1, adjacency matrix \(A^{\prime}\) of innocuous graph \(\mathcal{G}^{\prime}\) satisfies \(Rank(A^{\prime})\geq c\).

Aside from the property above, we further remark on another commonly-used assumption [22, 23]: _In a graph over which a GNN may extract semantically-useful node embeddings, adjacent nodes are likely to share similar features than non-adjacent nodes._ This formulation, however, only considers information aggregation of GNN along a single edge. We now extend feature smoothness to group-level. Let \(f(\vec{x},\vec{y})\) be a function that evaluates similarity between learnt node embeddings, i.e., similarity between two embedding vectors \(\vec{x}\) and \(\vec{y}\) leads to a smaller \(f(\vec{x},\vec{y})\). We formulate group-level feature smoothness of a innocuous graph:

**Assumption 3.1** (group-level feature smoothness): _Suppose \(k\neq m\). Then for any three nodes \(v_{a},v_{b},v_{c}\) that satisfy \(v_{a}\in\mathcal{C}_{k}\), \(v_{b}\in\mathcal{C}_{k}\) and \(v_{c}\in\mathcal{C}_{m}\), we have \(f(X_{a},X_{b})\leq f(X_{a},X_{c})\)._

In the next section, we formulate an overall criterion for finding an innocuous graph, which incorporate a necessary condition (Corollary 3.1) and an auxiliary assumptions (Assumptions 3.1).

## 4 Structural Entropy-based Loss

As discussed above, our model need to learn a graph that satisfies necessary conditions (Corollary 3.1 and Assumptions 3.1) for obtaining an innocuous graph. In this section, we interpret these conditions using the language of structural information theory and formulate an optimization problem. Following recent progress on structural information theory [11], we invoke the notion of _network partition structural information (NPSI)_, which was not be used in GNN models before.

To explain NPSI, we firstly introduce the following notations: \(P(\mathcal{G})=\{\mathcal{C}_{0},\mathcal{C}_{1},\ldots\mathcal{C}_{r-1}\}\) is a _partition_ of \(\mathcal{G}\). Then, \(P(\mathcal{G})\) can be denoted by a matrix \(Y\in\{0,1\}^{n\times r}\), where \(Y_{ik}=1\) if \(v_{i}\in\mathcal{C}_{k}\) otherwise \(Y_{ik}=0\). We call \(Y\) the _indicator matrix_. Since \(\mathcal{C}_{k}\neq\varnothing\), \((Y^{T}Y)_{kk}>0\), and since \(\forall k\neq m,\mathcal{C}_{k}\cap\mathcal{V}_{m}=\varnothing\), if \(k\neq m\), \((Y^{T}Y)_{km}=0\).

For a graph \(\mathcal{G}\) and partition \(P(\mathcal{G})\), let \(vol_{k}\) be the number of edges with at least one node in \(\mathcal{C}_{k}\) and \(g_{k}\) be the number of edges with only one node in \(\mathcal{C}_{k}\). Then by [11], NPSI is:

\[NPSI_{GP(\mathcal{G})}=\sum_{k<r}\left(\frac{vol_{k}-g_{k}}{2|\mathcal{E}|} \log_{2}\frac{vol_{k}}{2|\mathcal{E}|}\right) \tag{2}\]

To utilize it in GNN models, we define a matrix form of NPSI. Note that \(vol_{k}-g_{k}\) is the number of edges with both nodes in \(\mathcal{C}_{k}\), which equals to the \(k\)-th diagonal element in \(Y^{T}AY\), while the \(k\)-th value in sum of column in \((AY)\) equals to \(vol_{k}\) and can be computed by the \(k\)-th diagonal element in \(\{1\}^{r\times n}AY\). Then let \(trace(\cdot)\) be the trace of input matrix,

\[NPSI(A, Y)=NPSI_{GP(\mathcal{G})}\] \[= \sum_{k<r}\left(\frac{vol_{k}-g_{k}}{2|\mathcal{E}|}\log_{2}\frac {vol_{k}}{2|\mathcal{E}|}\right)\] \[= \sum_{k<r}\left(\frac{(Y^{T}AY)_{kk}}{2sum(A)}\times\log_{2} \left(\frac{(\{1\}^{r\times n}AY)_{kk}}{2sum(A)}\right)\right)\] \[= \mathrm{trace}\left(\frac{Y^{T}AY}{2sum(A)}\otimes\log_{2}\left( \frac{\{1\}^{r\times n}AY}{2sum(A)}\right)\right)\]

With the definition above, \(NPSI(A,Y)\) can be incorporated into GNN. NPSI is designed to learn \(Y\) on a fixed \(\mathcal{G}\)[11]. However, if we fix an \(Y\in\{0,1\}^{n\times r}\) which satisfies \((Y^{T}Y)_{kk}>0\) and \((Y^{T}Y)_{km}=0\) for \(k\neq m\), we can learn a graph \(\mathcal{G}^{\prime}\) with corresponding adjacency matrix \(A^{\prime}\) satisfying \(Rank(A^{\prime})\geq r\):

**Theorem 4.1** (minimize \(NPSI\) with learnable \(A^{\prime}\)): \[\begin{split}\text{Suppose }A^{\prime}=&\arg\min_{A^{\prime}} \left(NPSI(A^{\prime},Y)\right),\\ & s.t.A^{\prime}_{ij}\geq 0\text{ and }A^{\prime}=A^{\prime T}, \end{split}\] (3)

\(A^{\prime}\) _satisfies: \(Rank(A^{\prime})\geq r\)_

Figure 2: The USER framework. To mitigate randomness-interference in observed graph, an innocuous graph is constructed. We optimize structural entropy-based \(\mathcal{L}_{N}\) to the learn innocuous graph.
Therefore, based on NPSI, if we set \(r=c\), we construct an objective function to learn an adjacency \(A^{\prime}\) which satisfies necessary condition Corollary 3.1. Besides this, [10] shows that by minimizing NPSI on fixed \(\mathcal{G}^{\prime}\), we can divide the graph into partitions with high inner-connectivity and sparse inter-connectivity. Specifically, when input \(\mathcal{G}^{\prime}\) is fixed, we can obtain the partition of such groups by optimizing:

\[\mathcal{C}_{k}= \{v_{i}|Y_{ik}\neq 0\}\text{ where,}\] \[Y= \arg\min_{Y}\left(NPSI(A^{\prime},Y)\right)\] \[s.t. Y\in\{0,1\}^{n\times r},\;(Y^{T}Y)_{km}\begin{cases}>0&\text{if }k=m \text{,}\\ =0&\text{otherwise.}\end{cases}\]

With the partition indicator \(Y\), we utilize the well known Davies-Bouldin index (DBI) to analyze the similarity of node features inside same group [10]:

\[\begin{split} DBI(X,Y)&=\frac{1}{r}\sum_{k<r}DI_{k}\\ \text{where: }DI_{k}&=max_{m\neq k}(R_{km})\text{, }R_{km}=\frac{S_{k}+S_{m}}{M_{km}} \\ S_{k}&=(\frac{1}{|\mathcal{C}_{k}|}\sum_{\forall i=1}(|X_{i}- \overline{X}_{k}|^{2}))^{\frac{1}{2}},\\ M_{km}&=(|\overline{X}_{k}-\overline{X}_{m}|^{2})^{\frac{1}{2}}\text{, } \overline{X}_{k}=\frac{\sum_{\forall i=1}X_{i}}{|\mathcal{C}_{k}|}.\end{split} \tag{4}\]

An adjacency matrix \(A^{\prime}\) satisfies Assumptions 3.1 would make \(DBI(X,Y)\) small. Therefore based on NPSI, we construct an objective function to learn an adjacency \(A\) which satisfies the necessary conditions (Corollary 3.1 and Assumptions 3.1) simultaneously. Let \(\beta\) be a hyper-parameter. The objective function is:

\[\begin{split}&\mathcal{L}_{N}=NPSI(A^{\prime},Y)+\beta DBI(X,Y) \\ & s.t. A^{\prime}_{ij}\geq 0,\;A^{\prime}=A^{\prime T},\\ & Y\in\{0,1\}^{n\times c},\;Y_{km}\begin{cases}>0&\text{if }k=m \text{,}\\ =0&\text{otherwise.}\end{cases}\end{split} \tag{5}\]

Then our overall criterion for finding a innocuous graph is formulated into an optimization problem of minimizing \(\mathcal{L}_{N}\) in (5), where \(Y\) and \(A^{\prime}\) are elements to be optimized.

## 5 Unsupervised Structural Entropy-based Robust Graph Neural Network

In this section, we propose new framework that facilitates GNN models to learn embeddings and innocuous graph simultaneously. This framework accomplishes robust learning task by optimizing loss in (5). Here we take classical GAE [11] as supported GNN model. We introduce it from two aspects: structure and optimization.

**Structure.** Let \(A\) denote the adjacency matrix of original input graph. To remove the effective of randomness, we construct an innocuous graph and use it as the input of the supported model instead of the original graph. We thus construct a learnable matrix \(A^{\prime}\in\mathbb{R}^{n\times n}\), and use it as the input of supported GNN model:

\[H=\mathsf{GNN}\left(A^{\prime},X,\left\{W^{(1)},W^{(2)}\right\}\right) \tag{6}\]

\(H\) is the learnt node embeddings. Besides the node embeddings, we add a softmax layer with learnable parameter matrix \(W^{Y}\in\mathbb{R}^{d^{(2)}\times c}\) to obtain the group indicator matrix \(Y\):

\[Y=softmax(HW^{Y}) \tag{7}\]

**Optimization.** Let \(\mathcal{L}_{S}\) be the loss function of supported model, e.g., for GAE:

\[\mathcal{L}_{S}= ||\hat{A}-A||_{F}^{2}, \tag{8}\]

where \(\hat{A}\) is reconstructed from learnt node embeddings by \(\hat{A}=sigmoid(HH^{T})\). Besides \(\mathcal{L}_{S}\), \(\mathcal{L}_{N}\) in (5) is employed to alleviate the interference of randomness. Thus, let \(\alpha\) be hyper-parameter, model is trained by minimizing \(\mathcal{L}\):

\[\mathcal{L}=\mathcal{L}_{N}+\alpha\mathcal{L}_{S}. \tag{9}\]

Although unsupervised, with structural entropy based \(\mathcal{L}_{N}\), this framework mitigate randomness-interference, making the supported model more capable. We call it Unsupervised Structural Entropy-based Robust Graph Neural Network (USER). The detailed structure is shown in Figure 2.

## 6 Experiments

In this section, we provide the experiments comparing the performance of USER supported GAE (denoted by USER) with other state-of-the-art baseline methods, case study, ablation study and parameter analysis.

\begin{table}
\begin{tabular}{l c c c c} \hline Dataset & \# Nodes & \# Edges & \# Features & \# Classes \\ \hline Cora & 2,708 & 5,429 & 1,433 & 7 \\ Citeseer & 3,327 & 4,732 & 3,703 & 6 \\ Wiki & 2,405 & 17,981 & 4,973 & 17 \\ \hline \end{tabular}
\end{table}
Table 1: Dataset statistics.

Figure 4: Parameter analysis on Citeseer and Wiki

Figure 3: Case study: the graph heat maps of Cora
### Experimental Settings

**Datasets**. We evaluate all models on three widely-used benchmark datasets: _Cora_, _Citeseer_, _Wiki_[12, 13]. _Cora_ and _Citeseer_ are citation networks where nodes represent publications and edges stand for citation links. Their node features are the bag-of-words vectors; _Wiki_ is a webpage network in which nodes are web pages, and edges represent hyperlinks. The node features in it are tf-idf weighted word vectors. The statistics of these datasets are in Table 1.

**Noises**. Besides the original graph in datasets, we inject noises into the graph to promote the graph randomness. In particular, we develop two types of noises: _random noise_ and _meta-attack noise_[22]. Random noise "randomly flips" the state of the chosen pair of nodes (i.e., if there is an edge between them, we remove it; otherwise we add an edge between them). The number of changed edges is the ratio of the total number of edges in original graph. In most cases, random noises are not very effective, so we create several poisoned graphs with noise ratio from \(0\%\) to \(50\%\) with a step of \(10\%\). Meta-attack noise can promote the graph randomness significantly [22]; jin2020explaining. Even for supervised models, meta-attack is hardly applied with a perturbation rate higher than \(20\%\)[13]. Thus, we create several poisoned graphs with meta-attack noise ratio from \(0\%\) to \(20\%\) with a step of \(5\%\).

**Baselines**. For **USER**, we use classical GAE [12] as its supported model. To evaluate the effectiveness, we compare it with \(10\) baselines retaining the default parameter settings in their original papers. [1] utilizes random walks

\begin{table}
\begin{tabular}{l|c c c c} \hline \hline Dataset & USER & w.o. NPSI & w.o. DB1 & Fix \(A^{\prime}\) \\ \hline cora & 54.38 & 14.82 & 52.54 & 40.11 \\ citeseer & 37.04 & 28.95 & 12.82 & 30.94 \\ wiki & 49.7 & 48.44 & 39.77 \\ \hline \hline \end{tabular}
\end{table}
Table 6: NMI of USER’s variants with \(10\%\) random-noise

\begin{table}
\begin{tabular}{l|c c c c c c c c c c c c c} \hline \hline Dataset & PU Rate (\%) & \multicolumn{1}{c}{degewalk} & GAE & VGAE & ARGA & GAE & DGI & GC & GAGE & GAGE\_CG & ARGA & USER \\ \hline \multirow{9}{*}{com} & 0 & 36.9\(\pm\)2.1 & 41.3\(\pm\)3.4 & 43.06 \(\pm\)2.6 & 34.3\(\pm\)2.8 & 40.52 & 36.1\(\pm\)1.3 & 38.2\(\pm\)1.0 & 52.16 \(\pm\)0.94 & 38.2\(\pm\)4.36 & 43.4\(\pm\)3.44 & 34.0\(\pm\)3.15 & **50.041 \(\pm\)2.77** \\  & 10 & 37.6\(\pm\)2.8 & 34.1\(\pm\)4.4 & 33.66 \(\pm\)3.6 & 34.3\(\pm\)1.7 & 39.5\(\pm\)1.14 & 37.7\(\pm\)3.63 & 36.5\(\pm\)1.11 & 34.07 \(\pm\)2.37 & 35.7\(\pm\)2.37 & 35.7\(\pm\)3.29 & 35.9\(\pm\)3.51 & **47.17 \(\pm\)3.22** \\  & 15 & 29.9\(\pm\)4.8 & 18.99 & 44.11 & 35.62 \(\pm\)1.0 & 38.59 \(\pm\)1.31 & 33.39 & 23.19 \(\pm\)3.29 & 21.54 \(\pm\)4.61 & 22.5\(\pm\)3.69 & 36.9\(\pm\)3.33 & **29.77 \(\pm\)3.88** \\  & 20 & 73.1\(\pm\)5.8 & 72.56 \(\pm\)2.5 & 72.90 & 7.81 \(\pm\)2.90 & 56.85 \(\pm\)3.55 & 10.11 \(\pm\)2.76 & 10.91 \(\pm\)3.97 & 30.10 \(\pm\)1.34 & 10.3\(\pm\)2.96 & **18.82 \(\pm\)2.9** \\ \hline \multirow{9}{*}{citeseer} & 30 & 10.7\(\pm\)2.1 & 22.3\(\pm\)3.4 & 22.79 \(\pm\)2.66 & 20.55 \(\pm\)2.20 & 34.06 \(\pm\)1.29 & 40.22 \(\pm\)1.89 & 39.51 \(\pm\)1.30 & 38.79 \(\pm\)3.51 & 22.67 \(\pm\)2.54 & 21.0\(\pm\)1.07 & 37.28 \(\pm\)2.04 \\  & 10 & 12.5\(\pm\)1.09 & 22.3\(\pm\)1.2 & 22.62 \(\pm\)1.62 & 21.56 \(\pm\)2.51 & 22.51 \(\pm\)2.71 & 22.51 \(\pm\)2.71 & 37.21 \(\pm\)2.62 & 13.89 \(\pm\)1.21 & 15.62 \(\pm\)2.90 & **15.60 \(\pm\)2.51** & **22.77 \(\pm\)3.31** \\  & 15 & 17.3\(\pm\)2.7 & 17.3\(\pm\)1.8 & 13.66 \(\pm\)1.95 & 13.94 \(\pm\)1.25 & 15.71 \(\pm\)2.68 & 17.68 \(\pm\)2.77 & 17.81 \(\pm\)2.68 & 12.61 \(\pm\)1.99 & 15.65 \(\pm\)2.35 & 15.61 \(\pm\)2.15 & **22.77 \(\pm\)3.31** \\  & 20 & 8.3\(\pm\)2.45 & 16.81 \(\pm\)2.01 & 37.11 \(\pm\)1.82 & 36.53 \(\pm\)1.74 & 39.11 \(\pm\)1.85 & 39.08 \(\pm\)2.17 & 7.08 \(\pm\)2.20 & 7.61 \(\pm\)2.12 & **22.42 \(\pm\)2.67** \\  & 30 & 36.7\(\pm\)1.74 & 15.00\(\pm\)1.79 & 12.92 \(\pm\)1.89 & 41.31 \(\pm\)1.85 & 39.21 \(\pm\)2.61 & 33.38 \(\pm\)1.39 & 15.82 \(\pm\)2.77 & 17.25 \(\pm\)3.05 & **36.44 \(\pm\)1.71** \\  & 10 & 29.6\(\pm\)2.74 & 17.69 \(\pm\)2.62 & 11.41 \(\pm\)3.52 & 12.48 \(\pm\)4.46 & 38.22 \(\pm\)2.02 & 22.31 \(\pm\)3.84 & 22.86 \(\pm\)2.65 & 25.86 \(\pm\)1.81 & 13.34 \(\pm\)6.03 & **10.84 \(\pm\)4.41** \(\pm\)**1.71** \\  & 15 & 14.3\(\pm\)1.8 & 1.09\(\pm\)2.99 & 4.31 \(\pm\)3.81 & 6.82 \(\pm\)3.45 & 40.99 & 12.72 \(\pm\)2.43 & 15.19 \(\pm\)3.93 & 20.14 \(\pm\)3.66 & 2.62 \(\pm\)2.81 & 1.70 \(\pm\)3.97 & **47.54 \(\pm\)1.53** \\  & 20 & 9.3\(\pm\)1.2 & 2.29\(\pm\)3.4 & 1.52 \(\pm\)3.09 & 4.51 \(\pm\)1.85 & 42.71 \(\pm\)0.98 & 12.72 \(\pm\)2.33 & 15.39 \(\pm\)3.97 & 3.11 \(\pm\)3.93 & 2.40 \(\pm\)2.21 & 7.04 \(\pm\)**4.15** \\ \hline \hline \end{tabular}
\end{table}
Table 4: Link prediction (AUC+Std) under random-noises

\begin{table}
\begin{tabular}{l|c c c c c c c c c c c c c} \hline \hline Dataset & PU Rate (\%) & degewalk & GAE & VGAE & ARGA & GAE & DGI & GC & GAGE\_CG & ARGA & O & USER \\ \hline \multirow{9}{*}{com} & 0 & 36.9\(\pm\)2.1 & 41.3\(\pm\)3.4 & 43.06 \(\pm\)2.6 & 43.4\(\pm\)2.5 & 41.2\(\pm\)3.4 & 26.4\(\pm\)3.1 & **37.2\(\pm\)1.0** & 52.16\(\pm\)0.94 & 38.2\(\pm\)3.4 & 43.4\(\pm\)2.69 & 43.18 \(\pm\)4.41 & 36.24 \(\pm\)1.88 \\  & 10 & 35.2\(\pm\)2.3 & 43.2\(\pm\)2
to learn embeddings. **GAE** and **VGAE**Kipf and Welling (2016) firstly leverage GCN Kipf and Welling (2017)for GRL. **ARGA**Pan et al. (2018) is an adversarial GNN model. **AGE**Cui et al. (2020) applies Laplacian smoothing to GNN. **DG1**Velickovic et al. (2019) trains GNN with MI. **GIC**Mavromatis and Karypis (2020) captures cluster-level information. **GCA**Zhu et al. (2021) is a Graph Contrastive learning GNN. **GAE_CG** and **ARGA_CG** are Cross-Graph Wang et al. (2020) models. GAE_CG is the GAE version while ARGA_CG maintains ARGA encoders. Please note that GCA and Cross-Graph are also unsupervised robust models. However we firstly introduce innocuous graph, which make USER more effective.

**Parameter Settings** We train USER for \(400\) epochs using Adam optimizer with a learning rate \(\eta\). The two hyperparameters \(\alpha\) and \(\beta\), are selected through a grid search regarding performance, a detailed analysis could be found in Subsection 6.5. The dimension \(d^{(1)}\), learning rate \(\eta\), \(\alpha\) and \(\beta\) are selected accordingly based on the parameter analysis.

**Evaluation Metrics** For node clustering, we employ popular normalized mutual information (NMI) and clustering accuracy (ACC) Aggarwal and Reddy (2014). For link prediction, we report area under the ROC (AUC) Bradley (1997), and average precision (AP) Su et al. (2015).

### Performance

**Clustering.** We compare the performance of all models in Table 2 and Table 3 All the experiments are conducted \(10\) times and the average NMI with standard deviation is reported. For each dataset, the best performance is in bold. From Table 2 and Table 3, we observe that: **(1) Original graph.** When the input graph is the original graph, the USER's improvement from GAE is significant. Different from classical GAE, the performances of USER are always close to the best. **(2) Random-noises.** When graph randomness is promoted by random noises, USER outperforms others (including GCA and Cross-Graph). Even under large noise rate e.g., \(50\%\), performance of USER only drop \(12\%\), \(3\%\), \(0.6\%\) on Cora, Citeseer and Wiki, compared with original graphs. **(3) Meta-attack.** Meta-attack seems to be more powerful, making effect of most models drop rapidly. However, USER is still more effective than others.

**Link prediction.** To compare the performances on link prediction tasks. We follow the settings in Kipf and Welling (2016): take out \(5\%\) edges from Citeseer and Wiki datasets to form the validation set and \(10\%\) edges for test set, respectively. Then we impose random-noises on the rest of the network. Classical GRL models such as GAE, ARGA and the corresponding Cross-Graph supported version are used as baselines. All the experiments are run \(10\) times and we report the AUC and AP with standard deviation in Table 4 and Table 5. The best performance is in bold. From the results, we observe that for link prediction, USER also outperforms other models. Classical models are rather unstable towards promoted randomness. Even robust model Cross-graph's performance drop drastically under large ratio noises (e.g. the ARGA_CG dropped \(3.617\%\) and \(10.400\%\) on citeseer and wiki when noise rate is \(50\%\)). USER demonstrates stability w.r.t. different noise levels (only \(0.881\%\) and \(2.085\%\) drop with \(50\%\) noise). It verifies that USER can accomplish different tasks facing graph randomness.

### Case Study

To show the graph learned by USER. We illustrate that the normalized adjacency matrix of Cora dataset without noise and rearranged vertices in Figure 3(a). It is clearly observable that most edges are in one of seven groups with few edges between them. On the other hand, the adjacency matrix with \(50\%\)-ratio random-noises of Cora (as shown in Figure 3(b)) have more inter-group edges and the boundaries of classes get visibly blurred. The learned graph structure by USER is shown in Figure 3(c). From Figure 3(c), we observe that the group-boundaries are much clearer. This demonstrates that USER can capture ideal innocuous graph.

### Ablation Study

To understand the importance of different components of our model in denoising, we conduct ablation studies on Cora, Citeseer and Wiki datasets with \(10\%\) random-noise. **NPSI:** From Table 6, USER without NPSI component loses its effectiveness on all three datasets. **DBI:** The performance of USER after removing DBI drops slightly on Cora but it is significantly affected on Wiki and Citeseer. This implies for these two datasets, feature information is more important. **Learnable \(A^{\prime}\):** If we fix \(A^{\prime}\) the same as the original input, the model tends to be disturbed by the graph randomness. The experimental result on all datasets show the effect. By incorporating all these components, USER can explore for innocuous graph and thus consistently outperforms baselines.

### Parameter Analysis

We illustrate the mechanism of USER and explore the sensitivity of the two hyper parameters. \(\alpha\) controls the influence of the objective function from supported model and \(\beta\) is used to adjust the influence of Assumption 3.1. We vary \(\alpha\) from \(0.003125\) to \(0.1\) and \(0.00625\) to \(0.2\), \(\beta\) from \(0.025\) to \(0.8\) and \(1.0\) to \(32.0\) in a \(\log\) scale of base \(2\) respectively. We report the experiment results on Wiki with \(10\%\) random-noise in Figure 4 as similar observations are made in other settings As we can see, USER's performance can be boosted when choosing appropriate values for all the hyper-parameters, but performance under values too large or too small drops slightly. This is consistent with our analysis.

## 7 Conclusion

We aim to alleviate the interference of graph randomness and learn appropriate node representations without label information. We propose USER, a novel unsupervised robust framework. Along designing it, we discovered the fact that there are multiple innocuous graphs with which GNN can learn the appropriate embeddings and introduced rank of adjacency plays a crucial role in discovering such graphs. We also introduce structural entropy as a tool to construct objective function to capture innocuous graph. In the future, we'll explore more about intrinsic connectivities of graph data.
## Acknowledgements

This research was supported by NSFC (Grant No. 61932002) and Marsden Fund (21-UOA-219). The first author and third author are supported by a PhD scholarship from China Scholarship Council.
