{'fraction_non_alphanumeric': 0.03315027174686282, 'fraction_numerical': 0.005463392425234043, 'mean_word_length': 4.751882160392799, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Learning Robust Representations with Graph Denoising Policy Network

Graph representation learning, aiming to learn low-dimensional representations which capture the geometric dependencies between nodes in the original graph, has gained increasing popularity in a variety of graph analysis tasks, including node classification and link prediction. Existing representation learning methods based on graph neural networks and their variants rely on the aggregation of neighborhood information, which makes it sensitive to noises in the graph. In this paper, we propose Graph Denoising Policy Network (short for GDPNet) to learn robust representations from noisy graph data through reinforcement learning. GDPNet first selects signal neighborhoods for each node, and then aggregates the information from the selected neighborhoods to learn node representations for the down-stream tasks. Specifically, in the signal neighborhood selection phase, GDPNet optimizes the neighborhood for each target node by formulating the process of removing noisy neighborhoods as a Markov decision process and learning a policy with task-specific rewards received from the representation learning phase. In the representation learning phase, GDPNet aggregates features from signal neighbors to generate node representations for down-stream tasks, and provides task-specific rewards to the signal neighbor selection phase. These two phases are jointly trained to select optimal sets of neighbors for target nodes with maximum cumulative task-specific rewards, and to learn robust representations for nodes. Experimental results on node classification task demonstrate the effectiveness of GDNet, outperforming the state-of-the-art graph representation learning methods on several well-studied datasets. Additionally, GDPNet is mathematically equivalent to solving the submodular maximizing problem, which theoretically guarantees the best approximation to the optimal solution with GDPNet.


I. INTRODUCTION
Recently, remarkable progress has been made toward graph representation learning, a.k.a graph/network embedding, which solves the graph analytics problem by mapping nodes in a graph to low-dimensional vector representations while effectively preserving the graph structure [1]- [4]. Graph neural networks (GNNs) have been widely applied in graph analysis due to the ground-breaking performance with deep architectures and recent advances in optimization techniques [5], [6]. Existing representation learning methods based on GNNs, e.g. GraphSAGE [7], Graph Convolution Networks (GCNs) [8], [9] and Graph Attention Networks (GATs) [10], rely on the aggregation of neighborhood information, which makes the model vulnerable to noises in the input graph.
Some examples of such noises are as follows: • In knowledge graphs or open information extraction systems, spurious information may produce erroneous links between nodes. Likewise, incomplete information may lead to missing links. • In task-driven graph analysis, mislabeled samples, or cross-class links can be viewed as noises in node classification task. • Node features such as user profiles in social networks are often missing, or filled with obsolete or incorrect values.
Good graph representations are expected to be robust to the erroneous links, mislabeled nodes and partial corrupted features in the input graph, and capture geometric dependencies among nodes in the graph. However existing approaches have limited efforts on robustness study in this regard. In order to overcome this limitation of graph representation learning in handling noisy graph data, we propose Graph Denoising Policy Network, denoted as GDPNet, to learn robust representations through reinforcement learning. GDPNet includes two phases: signal neighbor selection and representation learning. It first selects signal neighbors for each node, and then aggregates the information from the selected neighbors to learn node representations with respect to the down-stream tasks.
The major challenge here is on how to train these two phases jointly, particularly when the model has no explicit knowledge about where the noise might be. We address this challenge by formulating the graph denoising process as a Markov decision process. Intuitively, although we do not have an explicit supervision for the signal neighbor selection, we can measure the performance of the representations learned with the selected neighbors on tasks like node classification, then the task-specific rewards received from the representation learning phase can be used for trial-and-error-search. In the signal neighbor selection phase, as shown in Fig. 2, GDPNet optimizes the neighborhood for each node by formulating the process of removing the noisy neighbors as a Markov decision process and learning a policy with the task-specific rewards received from the representation learning phase. In the representation learning phase, GDPNet aggregates features from signal neighbors to generate node representations for downstream tasks, and provides task-specific rewards to the signal neighbor selection phase. In the representation learning phase, GDPNet trains a set of aggregator functions that accumulate feature information from the selected signal neighbors of each target node. Thus in the test time, the representations of unseen nodes can be generated with the trained GDPNet with graph structure and the associated node feature information. The task-specific rewards computed w.r.t the down-stream tasks are passed to the signal neighbor selection phase. These two phases are jointly trained to select optimal sets of neighbors for target nodes with maximum cumulative task-specific rewards, and to learn robust representations for nodes.
We evaluate GDPNet on node classification benchmark, which tests GDPNet's ability to generate useful representations on unseen data. Experimental results show that GDPNet outperforms state-of-the-art graph representation learning baselines on several well-studied datasets by a large margin, which demonstrates the effectiveness of our approach. In summary, our contributions in this work include: • We propose a novel model, GDPNet, for robust graph representation learning through reinforcement learning. GDPNet consists of two phrases, namely signal neighbor selection and representation learning, which enables GDPNet to effectively learn node representations from noisy graph data. • We formulate signal neighbor selection as a reinforcement learning problem, which enables the model to perform graph denoising just with weak supervision from the task-specific reward signals. • GDPNet is able to generate representations for unseen nodes in an inductive fashion, which leverages both graph structure and the associated node feature information. • GDPNet is proved to be mathematically equivalent to solving the submodular maximizing problem, which guarantees our model can be bounded w.r.t the optimal solution. The rest of this work is organized as follows. Section II reviews the preliminaries of graph neural networks and reinforcement learning. Section III formally defines the graph representation learning problem through reinforcement learning, along with the description of GDPNet. Section IV discusses the relations of GDPNet to submodular maximization problem. Section V evaluates GDPNet on node classification tasks using various real-world graph data. Section VI briefly surveys related work on graph representation learning and reinforcement learning on graph, followed by the conclusion in Section VII.

A. Graph Neural Network
Graph neural networks (GNNs) are utilized to encode nodes in a low-dimensional space so that similarity in this space approximates similarity in the original graph [6]. GNNs generate node representations based on local neighborhoods, that is, by aggregating information from their neighbors using neural networks. Mathematically, the basic GNN can be formulated as follows, where N (v) is the neighborhood set of node v, x v represents node feature vector, h k v represents k th layer embedding of node v, σ is the non-linear activation function (e.g. ReLU or tanh), W k and B k are the parameters to be learned.

B. Reinforcement Learning
The goal of reinforcement learning is to learn a policy which can obtain maximum cumulative reward by making multi-step decisions in a Markov decision process. Policy gradient is the main approach to solve reinforcement learning problems which directly optimizes this policy via calculating the gradient of the cumulative reward and making gradient ascent. Specifically, the policy is modeled as π θ (a|s). To estimate the parameter θ of π θ , policy gradient methods maximize the expected cumulative reward from the start state s 1 to the end of the decision process s T . The objective function of reinforcement learning is defined as follows: where τ is the trajectories generated by π θ which consists of state s t , action a t and reward r t , N is the number of trajectory samples, T is the length of the decision process. Policy gradient optimizes the parameter θ via gradient ascent where the gradient ∇ θ J(θ) is calculated by the policy gradient theorem [11]:

III. APPROACH
We formulate the robust graph representation learning problem as sequentially selecting an optimal set of neighbors for each node with maximum cumulative reward signals and aggregating features from nodes' optimal neighborhoods. In this part, we formally define the problem, the environment setting for signal neighbor selection, and the GDPNet model.

A. Problem Formulation
Given an attributed graph G = {E, V, X}, where E is the edge set and V is the node set. X ∈ R |V|×D collects the attribute information for each node where x v ∈ R D is a D-dimensional attribute vector of node v ∈ V. Note that we can simply use one-hot encoding for node features for a graph without attributes. Given a target node v, let We aim to find a lower-dimensional representation h v for node v ∈ V. Firstly, a function f : Then the node representations are generated based on the signal neighborhood set, h : Given an order of the neighbors u 1 , ..., u |N (v)| , we decompose the conditional probability ofN (v) given , a 1 , ..., a t−1 ) using chain rule [12], where a t = {0, 1}, a t = 1 indicates selecting u t as a signal neighbor while a t = 0 indicates action space, where at = 1 represents neighbor selection, and at = 0 represents neighbor removal π θ (at|st) the policy which maps the current state into the action distribution.
removing u t . We solve this signal neighbor selection problem by learning a policy π θ (a t |s t ) = p(a t |N (v), a 1 , ..., a t−1 ) with neighborhood set N (v) and the predicted action values The objective of signal neighbor selection is to select a subset of neighbors that maximize a given reward is the generated signal neighborhood set, r t is the task-specific reward used to evaluate the action a t , and R π is the cumulative reward function. The representation of node v can then be learned by aggregating the neighborhood information from the signal neighborsN (v).
Selecting an optimal subset from a candidate set by maximizing an objective function is NP-hard which can be approximatively solved by greedy algorithms with a submodular function [13]. With this observation, we design our reward function that satisfies submodularity, and show that the proposed GDPNet is mathematically equivalent to solving the submodular maximizing problem. Thus our solution can be bounded by

B. Signal Neighbor Selection Environment
We formulate the problem of selecting a set of signal neighbors from a given neighborhood set as a Markov decision process (MDP) (S, A, P, R, γ), where S is the state space, A is the action space, P is the state transition probability matrix that describes the transition probability of the state after taking an action, R is the reward function and γ is discount factor of the MDP. The signal neighbor selection process can be described by a trajectory withN (v) time steps s 0 , a 0 , r 0 , ..., s |N (v)| , a |N (v)| , r |N (v)| . MDP requires the state transition dynamics to satisfy the Markov property p(s t+1 |s t ). Thus we learn a policy π θ (a t |s t ) that only considers the current state s t .
In reinforcement learning, the agent learns a policy via interacting with the environment. The main components (i.e., state, action, and reward) in the signal neighbor selection environment are described as follows, h ut ] encodes the information from the current node v and the selected node u t , which is concatenation of the intermediate embeddings h t v and h ut of the target node v and the t th neighbor u t , respectively. The calculation of h t v and h ut are defined in Section III-C. Consequently, a newly selected neighbor u t will update the embedding of v from h t v to h t+1 v which can be viewed as state transition. • Action (A): Given an order of the neighbors u 1 , ..., u |N (v)| of node v, the policy π θ (a t |s t ) maps the state s t into an action a t = {0, 1} at each time step t, t = 1, ..., |N (v)|. a 1 = 1 indicates u 1 is selected as a signal neighbor, while a 1 = 0 means u 1 is not selected. • Reward (R): Our goal is to find an optimal set of signal neighborsN (v) from a finite neighborhood set N (v) to learn robust graph embedding for downstream tasks such as node classification, link prediction and node clustering. The downstream tasks can produce taskspecific scores as the reward signal for the signal neighbor selection phase. To ensure that the combination of the selected neighbors have maximum cumulative rewards. We employ the submodular function framework to define the marginal value reward function: where AGG(·) aggregates both the target node feature x v and the neighbors' features {x ut } to update the representations of the target node [7], and f c (·) returns the micro-averaged F1 score from the node classification task when considers u t as the neighbor. The environment updates the states from It can be considered as a state transition:

C. Graph Denoising Policy Network
With the definitions of the signal neighbor selection environment, we introduce the GDPNet model which includes two phases: signal neighbor selection and representation learning. Given a target node v, GDPNet first takes its neighborhood set N (v) as input and outputs a signal neighborhood subset N (v). Then the representations h v is learned by aggregating the information from the signal neighborhood subsetN (v).
1) Determine the Neighborhood Order: As aforementioned, we use chain rule to decompose the signal neighbor selection as a sequential decision making process. However, it requires an order to make decisions. Here we design a highlevel policy to learn an order [u 1 , ..., u |N (v)| ] for the policy π θ to take action.
We define a regret score l for each neighbor to help determine the order. A neighbor with large regret score indicates it will be selected with higher probability. At each time step, we calculate the regret score of each neighbor and sample one of the neighbor to be the t th neighbor. The regret score is described as follows: where u k is the k-th neighborhood in the neighborhood set N (v) with a random order and W 1 , W 2 are parameter matrices. To reduce the size ofN (v) for computational efficiency, we add an ending neighbor u e to N (v) for early stopping purpose. When u e is sampled, the neighborhood selection process of node v stops. We use the Softmax function to normalize the regret scores, and sample one neighbor from the distribution generated by Softmax to be the t th neighbor.
. l e indicates the regret score of the ending neighbor u e . After selecting a neighbor u t , we adopt the policy π θ to determine whether to select u t as a signal neighbor. Then u t will be removed fromN (v) c t . 2) Signal Neighbor Selection: Given the t th neighbor u t , GDPNet takes an action a t = {0, 1} at time step t to decide whether to select the u t . We will make |N (v)| decisions to select the signal neighbors for node v. Here the total number of signal neighbors can be automatically determined. As illustrated in Fig. 2, a policy π θ (a t |s t ) is learned to map the state s t to the action a t at time step t, t = 1, ..., |N (v)|, meanwhile the corresponding reward r t will be provided. Our goal is to maximize the total reward of all the actions taken during these time steps, which can be learned by the following policy network, where W 1 and W 2 are weight matrices shared with Eq. (7), and action a t is sampled from a Bernoulli distribution which is generated by π θ (a t |s t ).
3) Representation Learning: At each time step, GDPNet calculates the embeddings of the target node v and the t-th neighbor u t as follows, where AGG(x, {y i , ∀i ∈ I}) = σ(W · MEAN({x} ∪ {y i , ∀i ∈ I}), x v and x ut are the features of node v and u t respectively.
We computed the embedding of neighbor u t via its own feature x ut , because the goal is to evaluate the individual contribution of u t . In this work we only consider one-hop neighbors for simplicity. The GDPNet model can be easily extended to aggregate the information from multi-hop neighbors with an augmented candidate neighborhood set for selecting the signal neighbors.
As defined in Section III-B, the state at time step t,

4) Iteration-wise Optimization:
We consider an iterationwise optimization approach to optimize the GDPNet model, which optimizes the signal neighbor selection phrase and representation learning phrase iteratively to learn the policy π θ and the representations h v . As for representation learning phase, it aggregates the information from the signal neighbors selected by π θ to learn an embedding h v for target node v. Meanwhile, the policy π θ is trained with the states calculated by h v and the corresponding rewards. In this paper, π θ is optimized with Proximal Policy Optimization (PPO), one of the widely used policy gradient method [14].
where KullbackLeibler (KL) divergence penalty is used to control the change of the policy at each iteration to perform a trust region update with a threshold δ. q(a|s) and Q old = T i=t γr i are the policy and Q-value, respectively, which are saved before the current time step during training. ρ θ old is the discounted state distribution defined as,

IV. CONNECTION WITH SUBMODULAR MAXIMIZATION
The design of the reward function in GDPNet described in Section III-B is inspired by the submodular function. With this carefully designed reward function, we build the connections with submodular maximization problem, and show that the solution provided by GDPNet can be bounded by where N (v) * is the optimal neighborhood set. In this section we first introduce the key definitions related to submodular functions, followed by the proof of monotonicity and submodularity properties of the reward function in GDPNet.

A. Submodular Reward Function
In this section, we show that given a special form of reward function, the total reward function in GDPNet turns out to be submodular. Definition 2 (Submodular Maximization). Let w be an optimizer which maps a set Ω in to a subset A with size smaller than K: The submodular maximization problem is to find the best possible w * which satisfying: The reward function r t in GDPNet is denoted by r t = R π (N (v) ∪ {u t }) − R π (N (v)), which is also named marginal value. Specifically, the reward function in GDPNet can be expressed as: where AGG(x, {y}) = σ(W · MEAN({x} ∪ {y}). Given this reward function r t , we can prove that the cumulative reward function R π is a submodular function.
Proposition 1. The total reward function R π is a monotone function, where we have r t ≥ 0 based on Eq. (16). Therefore t B t=t A r t ≥ 0, and R π is monotone. Proposition 2. The total reward function R π satisfies the submodularity property. That is, Proof. We define, Then we need to show r t A ≥ r t B . Based on the reward definition in Eq. (16), we have, Assume , the above equations can rewritten as, We have F (t B ) − F (t A ) ≥ 0 based on the monotonicity property. Thus we have r t A ≥ r t B .

B. Equivalence between GDPNet and Submodular Maximization Problem
We will establish the following facts, which together imply the equivalence between GDPNet and submodular maximization problem, • The total reward function R π defined in the signal neighbor selection phase is a submodular function, which is equivalent to f s : 2 N → R. • The submodular maximization problem can be formulated as an MDP which is equivalent to GDPNet. • The objective function in GDPNet is equivalent to the counterpart in submodular maximization. Firstly, the goal of submodular maximization is to find the w * , with the objective function: where f s (A) is the cumulative value of each element in set A. Let A be the selected neighborhood setN (v), then R π (N (v)) = f s (N (v)). Secondly, the submodular maximization problem can be formulated as an MDP where the set A with the selected items indicates the state. After adding a new item c into A, the state is updated to A ∪ {c}.
Lastly, the objective function of GDPNet also aligns to the optimizer w in submodular maximization, where each π θ can be considered as an optimizer w in Equation (25): where A is equivalent to the signal neighbor setN (v) Theorem 1. Greedy gives a (1 − 1 e )-approximation for the problem of arg max θ E A R π (A) when R π (A) : 2 N → R is a monotone submodular function.
Proof. Based on the aforementioned equivalence between the objective functions of GDPNet and submodular maximization, we need to show that a (1 − 1 e )-approximation solution can be achieved for w * (Ω) = arg max A⊆Ω:|A|≤K f s (A) with a submodular function f s , which has been proved in [13].
V. EXPERIMENT Experiments are conducted to evaluate the robustness of the representations learned by the proposed GDPNet model. As for quantitative experiments, we focus on two tasks: (1) Robustness Evaluation, we use micro-averaged F1 score to evaluate our model against baselines on node classification task, and (2) Denoising Evaluation, we evaluate the denoising capability of GDPNet by comparing with baselines running on the denoised graph generated by GDPNet. We extract four datasets Cora, Citeseer, PubMed and DBLP followed by spliting them for training, test and validation with the supervised learning scenario which follows the previous work [7], [9], [10]. As for qualitative experiments, we conduct the embedding visualization which projects the learned high-dimension representations to a 2D space. In all these experiments, we separate out test data from training and perform predictions on nodes that are not seen during training.

A. Experimental Setup and Baselines
For all these tasks, we apply a two-layer policy network to select the signal neighbors. The architectural hyper-parameters are optimized on the Cora dataset and shared by the other datasets. The embedding dimension is 128. The size of the two hidden layers in policy network are 64 and 36, respectively, with active function ReLU. The batch size is 256. The discount factor is optimized as 0.95 for Cora and DBLP, 0.9 for PubMed and 1.0 for Citeseer. We compare our method with the following baselines: • LR: Logistic regression (LR) model which takes the node features as inputs, and ignores graph structure. • GCN [8]: GCN uses the local connection structure of the graph as the filter to perform convolution, where filter parameters are shared over all locations in the graph. We use inductive version of GCN in this paper for comparison • GAT [10]: GAT utilizes the attention mechanism to enhance the performance of the graph convolutional network by considering the entire neighborhoods. • FastGCN [9]: FastGCN considers graph convolutions as integral transforms of embedding functions, and samples the neighborhoods in each layer independently to addresses the recursive expansion of neighborhoods. • GraphSAGE [7] GraphSAGE extends the original graph convolution-style framework to the inductive setting. It randomly samples a fixed-size neighborhood of each node followed by performing a specific aggregator over it. Our proposed model is denoted as GDPNet. We also introduce a variant GDPNet RO which performs the signal neighbor selection with a random order of the neighbors.

B. Performance Comparison
In this section, we first visualize the node representations learned by different methods, followed by the performance comparison on node classification task. Additionally, we show the distributions of the selected signal neighbors with GDPNet on different dataset. 1) Embedding Visualization: Node representations are learned by GAT, GCN, GraphSAGE and GDPNet on test dataset of Cora, and visualized with t-SNE [15], as shown in Fig. 3. Different colors in the figure represent different categories in Cora. The following observations can be made from Fig. 3, • GDPNet correctly detects the classes in Cora, providing empirical evidence for the effectiveness of our method. This can be seen by the clear gap between samples with different colors. It also demonstrates that, removing the noisy neighbors can help nodes learn better representations. • GCN and GraphSAGE share similar "shape" in the 2D space. The reason is that in the inductive learning setting, GCN and GraphSAGE use the same methods in neighborhood sampling. GAT considers the entire neighborhoods which leads to a different visualization result from the others. It can be seen that the sampled neighbors have a profound effect on the representations. • GAT cannot effectively identify different classes as other methods, it might because it considers all the neighbors with attention weights, which is easily to introduce noisy neighbors.
2) Results on Node Classification: In this part, we compare the performance of GDPNet against the baselines on Cora, Citeseer, PubMed and DBLP. For all methods, we run the experiments with random seeds over 15 trials and record the mean and standard variance of the micro-average F1 scores. The results are summarized in Table III. From the table we observe that, • GDPNet consistently outperforms the other methods, which demonstrates there exists a set of noisy neighbors in each dataset on node classification task, and GDPNet can learn robust embeddings by effectively removing these noisy neighbors. • GCN, FastGCN and GraphSAGE show lower F1 scores.
The reason is that these methods randomly sample a subset of neighbors for representation learning, which is  hard to avoid the noisy neighbors. In addition, variance is higher via random sampling. • GAT learns the importance of the neighbors with attention weights, which is also sensitive to noisy data according to the reported results. • Another interesting observation is that Logistic regression achieves better performance than the other baselines on PubMed, which indicates that there would be less signal neighbors for the nodes in PubMed. This observation can also be verified in Fig.4. • GDPNet RO has a lower F1 score with higher variance than GDPNet, which demonstrates that the order of the decisions has an effect on the performance of representation learning. Thus learning an order for the neighbors is beneficial for selecting signal neighbors and robust graph representation learning. 3) Distribution of the Selected Neighbors: Fig. 4 shows the distribution of the selected neighbor percentages, where the x-axis indicates the percentage of the nodes been selected as signal neighbors, and the y-axis indicates the probability densities. We observe that most of the neighbors in Citeseer and DBLP are selected while only a few neighbors are selected in PubMed. The results show that there would be more "noisy" citations (e.g. cross-field citation) in PubMed than in Citeseer and DBLP. Interestingly, most of the research papers collected in Citeseer and DBLP are from computer science, while PubMed collects papers from biomedical.
C. Ablation Study 1) Node classification performance comparison on selected signal neighbors: In this part, we evaluate the effectiveness of denoising process in GDPNet. Specifically, we first utilize the policy learned by GDPNet to remove the noisy neighbors from Citeseer and PubMed. With the denoised graphs, we learn representations with GCN and GraphSAGE to see whether the performance can be improved on the denoised graphs. The results are summarized in Table IV, where the suffix " GDPNet " indicates the results on the denoised graphs generated by GDP-Net. As expected, both GCN  performance on the denoised graphs, which demonstrates the effectiveness of the denoising process in GDPNet.
2) Parameter Sensitivity Study: In Fig. 6, we vary the training percentage of nodes in Citeseer and PubMed to test the classification accuracy. We observe that, the performance of all the methods are improved with the increases of the training percentage. Additionally, it can be seen that GAT is very sensitive to the percentages of training data, and it requires larger proportion of training data in order to have a desirable performance. GraphSAGE, GCN and GDPNet achieve good performances on small training data, and GDPNet make more improvements as the training data percentage increases.
Discount factor γ balances the importance between instant reward and long-term reward. The large γ indicates the more important role of long-term reward. Fig. 5 shows that when γ = 1.0, Citeseer achieves the best performance, while PubMed achieves best performance when γ = 0.9. We can see that Citeseer is more sensitive to the discount factor than PubMed. Fig. 5 presents the analysis on the number of epochs for representation learning phase. It can be seen from the figure that, with the increase of epochs (between 10 and 80), the performances of PubMed and Citeseer are both improved. The epochs to achieve best performance are 80 and 100 for PubMed and Citeseer, respectively.
In Fig. 6, we vary the training percentage of nodes in Citeseer and PubMed to test the classification accuracy. We observe that, the performance of all the methods are improved with the increases of the training percentage. Additionally, it can be seen that GAT is very sensitive to the percentages of training data, and it requires larger proportion of training data in order to have a desirable performance. GraphSAGE, GCN and GDPNet achieve good performances on small training data, and GDPNet make more improvements as the training data percentage increases.
3) Convergence Analysis: Fig. 7 shows the convergence analysis of GDPNet on Citeseer and PubMed. We initialize the policy randomly when epoch equals 0, and the neighbors are randomly selected as signal neighbors. We observe that Citeseer converges faster than PubMed. One explanation would be that PubMed has more nodes than Citeseer, which requires more time to explore the policy for nodes.

VI. RELATED WORK
In this section, we briefly describe previous graph representation learning approaches including matrix factorization based methods and graph neural network based methods, and recent advancements in applying reinforcement learning on graph.

A. Graph Representation Learning
Graph representation learning tries to encode the graph structure information into vector representations. The main idea is to learn a mapping function from the nodes or entire graphs into an embedding space where the geometric relationships in the low-dimensional space coincide with the original graph. The methods can be grouped into two categories: matrix factorization based methods and graph neural network based methods [1].
1) Matrix Factorization based Embedding: Matrix factorization based methods learns an embedding look-up table which trains unique embedding vectors for each node independently. These methods largely focused on matrixfactorization approaches and random walk approaches [1]- [3], [16]. Matrix-factorization approaches utilize dimension reduction methodology to learn the representations [17]- [19] with the loss of node pair similarity. Inspired by the success of natural language processing [20], a set of methods use random walk to learn the node embeddings where the node similarity is calculated by co-occurrence statistics from sentence-like vertex sequences generated by random walks among connected vertices [21]- [25]. The random-walk based method have been verified to be unified into the matrix factorization framework [26].
2) Graph Neural Network based Embedding: A set of graph neural network based embedding methods are proposed recently for representation learning [27]- [30]. GCN [8] first proposes the first-order graph convolution layer to perform recursive neighborhood aggregation based on the local connection. Instead of utilizing full graph Laplacian during training in the GCN, GraphSAGE [7] considers the inductive setting to handle the large scale graph with batch training and neighborhood sampling. Followed by GraphSAGE, self-attention mechanism has been explored to enhance the representation learning performance [10], [31]. To accelerate the training of GCNs, [9] samples the nodes in each layer independently, while [32] samples the lower layer conditioned on the top one and the sampled neighborhoods are shared by different parent node. In this work, we propose to find an effective subset of neighbors for learning robust representations.

B. Reinforcement Learning on Graph
Reinforcement learning solves the sequential decision making problem with the goal of maximizing cumulative rewards of these decisions. A set of work used reinforcement learning to solve the sequential decision making problems in graph, such as minimum vertex cover, maximum cut and travelling salesman problem [33], [34]. You et al. [35] considered the molecular graph generation process as a sequential decision making process where the reward function is designed by non-differentiable rules. Dai et al. [36] utilized reinforcement learning to learn an attack policy to make multiple decisions (delete or add edges in the graph) to attack the graph.

VII. CONCLUSION
In this paper, we developed a novel framework, GDPNet, to learn robust representations from noisy graph data through reinforcement learning. GDPNet includes two phases: signal neighbor selection and representation learning. It learns a policy to sequentially select the signal neighbors for each node, and then aggregates the information from the selected neighbors to learn node representations for the down-stream tasks. These two learning phases are complementary and achieves significant improvement. We show that our method mathematically is equivalent to maximizing the submodular function with the carefully designed reward function, which guarantees our objective value can be bounded by (1 − 1 e )R(N (v) * ). Note that GDPNet is naturally an inductive model which can generate representations for unseen nodes. Experiments on a set of well-studied datasets provide empirical evidence for our analytical results, and yield significant gains in performance over state-of-the-art baselines.