Graph Ordering: Towards the Optimal by Learning

Given a graph $G=(V,E)$ where $V(G)$ is a set of vertices and $E(G)$ is a set of edges of $G$, the graph ordering problem is to find the optimal order for all vertices. In brief, let $\Phi(\cdot)$ be a permutation function which assigns a vertex a unique number in $[1..n]$ where $n=|V(G)|$. The problem is to find the optimal graph ordering $\Phi(\cdot)$ by maximizing a cumulated locality score $F(\cdot)$ (Eq. (1)) over a sliding window of size $w$.

Here, $u$, $v$ are two vertices ordered within a window of size $w$ in the permutation, and $\mathtt{S}(u,v)$ is a pair-wise similarity function to measure the closeness of $u$ and $v$. In (DBLP:conf/sigmod/WeiYLL16, ), $\mathtt{S}(u,v)$ is defined as $\mathtt{S}(u,v)=\mathtt{S}_{s}(u,v)+\mathtt{S}_{n}(u,v)$, where $\mathtt{S}_{s}(u,v)$ is the number of times that $u$ and $v$ are sibling, and $\mathtt{S}_{n}(u,v)$ is the number of times that $u$ and $v$ are neighbors.

In general, maximizing $F(\Phi)$ is a variant of maximum TSP (for $w=1$) with the sum of weights within a window of size $w>1$ and thus is NP-hard as proven in (DBLP:conf/sigmod/WeiYLL16, ).

Wei et al. in  (DBLP:conf/sigmod/WeiYLL16, ) proposed a greedy algorithm (named GO), as sketched in Algorithm 1, which iteratively extends a partial solution $S$ by a vertex $v^{*}$. The vertex $v^{*}$ is selected by maximizing a potential function ${\mathcal{Q}(S,v)}$, which measures the quality of the partial solution extended by a vertex $v$, based on the current partial solution $S$.

In details, in $i$-th iteration, it computes the cumulated weight $k(v)$ (Eq.2) for each vertex $v$ and inserts the one with maximum $k(v)$ in the permutation:

where $k(v)$ serves as the potential function $Q$, $\{v_{j}|j=max(1,i-w)\}$ are the last $max(1,i-w)$ inserted vertices. This procedure repeats until all the vertices in $G$ are placed. The total time complexity of GO is $O(wd_{max}n^{2})$, where $d_{max}$ denotes the maximum in-degree of the graph $G$. There are $n$ iterations, and in each iteration, it scans the remaining vertices in $O(n)$ and computes the score $k(v)$ for the scanned vertex $v$ in $O(wd_{max})$. The algorithm achieves $\frac{1}{2w}$-approximation for maximizing $F(\Phi)$. It can achieve high-quality approximations with small window size and its practical performance is close to the optimal in the experiments.

Inspired by universal approximation theorem (csaji2001approximation, ), deep reinforcement learning (DRL) learns a policy $\pi$ from states to actions that specifies what action to take in each state. We can formulate Algorithm 1 as MDP, which is composed by a tuple $(\mathcal{S},\mathcal{A},\mathcal{R},\mathbb{P},\gamma)$ : 1) $\mathcal{S}$ is a set of possible states, 2) $\mathcal{A}$ is a set of possible actions, 3) $\mathcal{R}=r(s_{t},a_{t})$ is the distribution of reward given state-action $(s_{t},a_{t})$ pair. 4) $\mathbb{P}=P(s_{t+1}|s_{t},a_{t})$ is the transition probability given $(s_{t},a_{t})$ pair. 5) $\gamma$ is the reward discount factor. The policy $\pi$ is a function $\pi$: $\mathcal{S}\to\mathcal{A}$ that specifies what action to perform in each state.

The objective of RL is to find the optimal policy $\pi^{*}$ which maximizes the expected cumulative discounted reward. This cumulative discounted reward can be defined by the Bellman Equation as below for all states recursively:

where $Q(s,a)$ and $Q(s^{\prime},a^{\prime})$ are the maximum expected cumulative rewards achievable from the state-action pair $(s,a)$ and the previous state-action pair $(s^{\prime},a^{\prime})$, respectively. To avoid exhaustively exploring the MDP, Monte Carlo simulation is used to sample the state-action trajectory $(s_{0},a_{0},r_{0},s_{1},a_{1},r_{1},\cdots,s_{T},a_{T},r_{T})$ to estimate the values of downstreaming state-action pairs. In this vein, DRL is adopted to solve the combinational optimization problem (DBLP:journals/corr/BelloPLNB16, ; DBLP:conf/nips/KhalilDZDS17, ), whose policy is learned by specific deep neural networks.

In a nutshell, the construction of the parametric model ${{\mathcal{\hat{Q}}}(S,{\bf v};\Theta)}$ and the efficient training in an exponential training space are two main challenges when we try to adopt the model-based framework to solve the graph ordering problem.

To find the optimal policy, there are two kinds of RL algorithms (DBLP:books/lib/SuttonB98, ). One is value-based, e.g., Q-learning, which learns the optimal state-action values in Eq. (3) and the corresponding optimal policy is to take the best action in any state. The other is policy-based, which learns the optimal policy directly from a collection of policies. Since the policy-based RL algorithm is more suitable for high dimensional action space and has better convergence properties, we use a model-free, policy-based RL algorithm to train the Policy Network directly. The objective is to find the optimal policy $\pi^{*}$ by maximizing the following expected accumulated and discounted rewards of Eq (9), which is estimated by sampling state-action trajectory $\varsigma$ $(s_{0},a_{0},r_{0},s_{1},a_{1},$ $...)$ of $T$ steps.

The gradient of the Eq. (9) is formulated using the $\mathsf{REINFORCE}$ algorithm (DBLP:journals/ml/Williams92, ) as given in Eq. (10).

Here, as the raw reward of a trajectory, $\Sigma_{t=0}^{t=T}\gamma^{t}r_{t}$, is always positive, a baseline function $b(s)$ is introduced to reduce the variance of the gradients. The formula $\Sigma_{t=0}^{t=T}\gamma^{t}r_{t}-b(s)$ indicates whether a reward is better or worse than the expected value we should get from state $s$. For the baseline function $b(s)$, we adopt the widely-used moving average of the historical rewards, i.e., the evaluation result of DON.

The training algorithm of the Policy Network is given in Algorithm 2. It takes a graph $G$, an initial and experience-based sampling probability ${\bf{{\mathsf{prob}}}_{0}}$, the evaluation set $D_{{\mathsf{E}}}$, and the learning rate of RL as input, and trains Policy Network $\Pi(s;\Theta^{\prime})$ by interacting with the training process of Deep Order Network ${{\mathcal{\hat{Q}}}(S,{\bf v};\Theta)}$. The intuition is if the reward of an action is positive, it indicates the action is good and the gradients should be applied to make the action even more likely to be chosen in the future. However, if the reward is negative, it indicates the action is bad and the opposite gradients should be applied to make this action less likely in the future.

We briefly explain the algorithm below. First, Policy Network $\Pi(s;\Theta^{\prime})$ is initialized (line 2). The training of policy gradient starts at line 3. Before that, the training of DON has started several steps to collect enough evaluation results for computing the baseline. In each RL step, the algorithm updates $\Pi(s;\Theta^{\prime})$ once by one Monte Carlo sampling of a trajectory of length $T$ (line 4). For each time $t$, it repeats the following 4 steps one by one. First, draw a random action ${\bf a_{t}}$ based on the probability output by Policy Network, i.e., $\pi_{\Theta^{\prime}}({\bf a_{t}}|{\bf{{\mathsf{prob}}}_{t}})$ (line 5). Instead of directly choosing the action with the highest probability, the random action manages a balance between exploring new actions and exploiting the actions which are learned to work well. Second, apply the action ${\bf a_{t}}$ on the state ${\bf{{\mathsf{prob}}}_{t}}$ by imposing an increment/decrement of $\lambda$ (line 6), to generate the next state ${\bf{{\mathsf{prob}}}_{t}}$. Third, generate the training data set $D_{t+1}$ of DON by sampling $G$ with probability ${\bf{{\mathsf{prob}}}_{t+1}}$, and feed $D_{t+1}$ to train ${{\mathcal{\hat{Q}}}(S,{\bf v};\Theta)}$ (line 7). Fourth, after training ${{\mathcal{\hat{Q}}}(S,{\bf v};\Theta)}$ in a certain number of steps, we use the evaluation set $D_{{\mathsf{E}}}$ to evaluate DON, and collect the evaluation result as reward $r_{t}$ (line 8). When a trajectory is simulated, we compute the cumulative rewards (line 11) and apply gradient ascent to update the Policy Network $\Pi(s;\Theta^{\prime})$ (line 12).

In addition, to validate the performance of our models on graphs with different structures explicitly, we generate six synthetic graphs by SNAP random graph generator: power-law and Erdös-Rényi. For power-law, we choose three power-law distributions with shape parameter $\gamma\in$ {1.6, 1.8, 2.0} and adopt Newman’s method (newman2001random, ) to generate three power-law graphs: PL10K_1.6, PL10K_1.8 and PL10K_2.0. For Erdös-Rényi, we utilize the parameter $p\in\{0.02,0.05.0.1\}$ which indicates the probability of edge existence between two vertices to generate three synthetic graphs with different densities, that are, ER10K_0.02,ER10K_0.05 and ER10K_0.1. All synthetic graphs have 10,000 vertices. Table 3 summarizes the information of these real and synthetic graphs.

The Policy Network is a multi-label classifier of two-layers MLP. The input is the state ${\bf{{\mathsf{prob}}}_{t}}\in(0,1)^{n}$ and the output layer predicts the probability to perform action ${\bf a_{t}}$, i.e., a vector $(0,1)^{n}$ by sigmoid activation. Similar to DON, the hidden units are activated by ReLU function.

Table 4 shows the hyper-parameters settings in the training. The models are learned with these parameters tuned in the corresponding experienced range. In Table 4, the global steps and RL steps are the numbers of parameter updating of DON and the Policy Network, respectively. For one RL step, a trajectory of length $T$ DON training is conducted. To this end, (global steps) / (RL steps $\times T$) DON steps are trained in one timestamp. For computing the rewards, we use the Root Mean Square Error (RMSE) as the evaluation metric of the evaluation set. The reward is defined as the opposite number of RMSE. We use the best neighbor heuristic to generate the evaluation set by randomly choose the first vertex with initial ${{\mathsf{prob}}}$, the degree distribution. A bare DON is trained by setting sampling probability as ${\bf{{\mathsf{prob}}}_{0}}$. In this section, we use DON and DON-RL to denote the bare DON model and DON with Policy Network respectively.

Table 5 shows the overall results of the $F$ score of the permutations generated by DON, compared with the baseline graph ordering algorithm GO (DBLP:conf/sigmod/WeiYLL16, ). As a preprocessing step, vertices on the trig of the graph, i.e., vertex whose degree is 1 are merged to one equivalent vertex as shown in Fig. 5. In Table 5, the column $|V^{\prime}|$ is the compacted vertex number of the graph. We can see that this trick compresses up to 17% vertices for real and power-low graphs but it is invalid for three Erdös-Rényi graphs due to their degree distribution. With regards to maximize $F$, the solutions of DON and DON-RL surpass that of the greedy algorithm significantly. For the real graphs, all the solutions of DON-RL outperform that of GO from 1.8% up to 8.2%. And the solution of DON, on the 3 reals graphs, Wiki-Vote, p2p and Cora, the improvements of $F$ are 7.6%, 4.7% and 2.8%, respectively. For the synthetic graphs, both the DON and DON-RL can generate solutions of much higher $F$ score than GO. The DON-RL performs best and its solutions surpass that of GO up to 35.0% for powerlaw graph, and 18.6% for ER graph. As the matrix visualization results shown in Fig. 1(b), the model-based approach DON-RL focuses on the overall performance and can optimize the permutation of the sub-significant vertices. The greedy heuristic is powerful for ordering the top significant vertices while for the sub-significant vertices, it fails to capture the global information as ordering them w.r.t. the common neighbor relations. It is easy for GO to stuck in forming local dense areas while incurring sparsity in the global scope. This phenomenon agrees with our intuition, that is, the greedy algorithm could neglect better solutions in the future scope.

In order to validate the effectiveness of the Policy Network, we perform A/B test to observe the effect of RL-based adaptive training, i.e, using the same hyper-parameters to train a DON model and a conjuncted DON-RL model. During the overall training process, we generate a solution after per 10% global training steps of DON ends. We directly observe the changes of objective function $F(\Phi)$ as the loss function of the model is not a direct reflection of the objection of this NP-hard problem. Fig. 6 presents the results over the 12 graphs in Table 3.

We observe that the performance of DON and DON-RL are different among different graphs during training. In general, imposing RL on the sampling probability adjustment improves the performance of DON in most cases. As shown in Fig. 6(a), 6(c), 6(e)-6(g) and 6(j)-6(l), DON-RL can achieve better results than DON in graphs with high density since the locality of vertices is significantly skew on the graph. On the other hand, for the graph with low density and flat degree distribution, such as Cora (Fig. 6(d)) and p2p (Fig. 6(b)), using RL does not make significant improvement during the training. We conjecture, in this scenario, the potential action space is relatively large so that it is difficult for RL algorithm to find an action trajectory with high reward, especially when the locality has been well captured by DON. In addition, due to the dynamic adjusting mechanism, DON-RL can make the training process robust and avoid over-fitting. As shown in Fig. 6(b) and 6(i), DON reaches its best effect much earlier than DON-RL then it goes worse as over-fitting. In contrast, DON-RL can rectify the over-fitting autonomously in Fig. 6(c) and 6(h). The performance of DON-RL increases constantly and surpasses DON in the end.

Therefore, the RL-based DON-RL is suitable for the graphs whose structures are highly skew. The results in Fig. 6 also confirms the effectiveness of the Policy Network in DON-RL.

In this section, we investigate the effect of the window size $w$ in Eq. (1). Fig. 7 shows for graph PL10K_1.6, the $F$ scores of 5 models training with $w$ is set to $\{4,5,6,7,8\}$. For these DON models, they perform stably better than GO as $w$ grows. In Fig. 7, DON-RL is the 5 models associated with RL training, which generates permutations of highest $F$. Recall that the approximate ratio of GO is $\frac{1}{2w}$, which means theoretically, the larger the $w$, the larger the gap between GO and the optimal solution, i.e., the improvement space of GO. Interestingly, in Fig 7, as $w$ grows, the increment of locality score of model-based approaches grow a little faster than that of GO. It implies that the model-based approaches can better take advantage of the gap to optimized the learned solution.

In addition, another interesting observation is that models trained with smaller $w$ have better performance than that of larger $w$. It indicates that we can use pre-trained models with small $w$ to generate different permutations of larger $w$.

In this section, we perform two case studies to demonstrate the power of DON-RL in solving real-world problems.

Fig. 8 demonstrates the compression cost ${{\mathsf{cost}}}_{r}(A,b)$ on the 5 real graphs in Table 3, when the block wide $b$ is $8$ (Fig. 8(a)), $16$ (Fig. 8(b)) and $32$ (Fig. 8(c)). We compare the compression performance with two methods: Degree permutes the vertex based on the decreasing degree. SlashBurn  (KangF11, ) is the graph ordering algorithm proposed for graph compression. We set $w=5$ for our method: DON-RL for all datasets. As shown in Fig. 8, DON-RL outperforms the other methods on three datasets (Wikivote, Facebook and Cora) and achieves comparable results on two datasets (p2p and PPI). For the number of nonempty blocks, DON-RL reduces the counts by $2.97\times$ and $2.25\times$ compared with the second best orderings on Facebook and Cora. Interestingly, Degree is a quite good heuristic ordering for the graph compression. It achieves the best performance on p2p and PPI. The results validate that our learned vertex order is a good potential criteria for graph compression.

Fig 9 shows the partitioning derives from DON-RL with $w=5$, and 5 other edge partitioning and graph ordering algorithms over Facebook. Here, Random  (DBLP:conf/kdd/BourseLV14, ) assigns each edge independently and uniformly to k partitions. The Greedy  (DBLP:conf/kdd/BourseLV14, ) heuristic preferentially assigns an edge to a partition already contains the two or one of its end vertices with trading off the balance. NE and SNE (DBLP:conf/kdd/ZhangWLTL17, ) are the state-of-the-art edge partitioning heuristic based on neighbor expansion. The replication factor of DON-RL is smaller than that of the widely used Greedy up to 37%. Also, as the number of partition increases, the replication factor of DON-RL increases much slower than Greedy and SlashBurn . It is interesting that a good partitioning derives from a high-quality ordering result.