# A Multiview Representation Learning Framework for Large-Scale Urban Road Networks
## 3 Methodology
### Large-Scale Road Network Organization  
To effectively optimize the calculation efficiency and memory usage of the random walk algorithm for large-scale urban road networks, we develop a data organization method that is inspired by the Fast Newman concept [22]. The method comprises three steps: optimal partition, subgraph repair, and walk index calculation. Optimal partitioning aims to partition the complete multigraph \(G\) into \(N_{s}\) independent subgraphs, which satisfy \(V(i)\subseteq V\) and \(V(1)\cap\ V(2)\cap\ldots\cap\ V(N_{s})=\varnothing\). To ensure the quality of the subgraphs, we can define the partition process as an optimization problem with objective function \(Q\):  
\[\left\{G(1),G(2),\ldots,G(N_{s})\right\}=argmax\ Q, \tag{1}\]  
The optimal graph partition result of this task should satisfy the following two properties:  
* The complexity of each subgraph \(G(i)\) should be approximately uniformly distributed. * The subgraphs should meet the needs of parallel computing and lossless random walks. * Hence, we can define the objective function \(Q\) as: \[Q=\frac{1}{2N}C^{T}\bigg{[}W-\frac{1}{2N}(W\mathbf{1})(W\mathbf{1})^{T}\bigg{]}C,\] (2) where matrix \(C=\left[c_{ij}\right]\in\mathbb{R}^{N\times N_{s}}\) denotes the subgraph to which each node belongs. For instance, if \(v_{i}\in G(j)\), then \(c_{ij}=1\); otherwise, \(c_{ij}=0\). \(\mathbf{1}\in\mathbb{R}^{N\times N_{s}}\) is a vector of all of them. When the objective function is maximized, the partition result is optimal. Under the optimal partition, the nodes within a single subgraph are the most compact, and the nodes between multiple subgraphs are the sparsest. To solve the optimization problem and obtain the optimal subgraph partition result, a bottom-up step-by-step iterative optimization strategy is adopted here. The specific steps are as follows:First, all the nodes are treated as independent subgraphs, representing the results of first-step partition \(\{G(1),G(2),\ldots,G(N_{s})\}_{1}\), and the objective function \(Q_{1}\) is calculated in the first step. 2. Then, two random subgraphs \(G(i)\) and \(G(j)\) are merged that satisfy \((\exists e_{mn}=1\), \(v_{m}\in G(i),v_{n}\in G(j))\) based on the previous partition result, and the objective function \(Q_{l}(i,j)\) is calculated after the corresponding merge operation in this step. 3. The subgraph set corresponding to the maximization of \(Q_{l}(i,j)\) is selected as the result of this partition step \(\{G(1),G(2),\ldots,G(N-1)\}_{t}\), and the objective function is updated to \(Q_{l+1}=\underset{i,j}{max}Q_{l}(i,j)\). 4. The above two steps are repeated. When the number of partition steps reaches \(N\), the partition result \(\{G(1),G(2),\ldots,G(N_{s}-k+1)\}_{k}\) is selected, where k satisfies \(k=\underset{k}{argmax}Q_{k},\ k\in[0,\ 1]\), as the optimal subgraph partition result. After the optimal partition is obtained, to ensure that the random walk process between subgraphs can perfectly simulate the information of the complete road network, it is necessary to perform a subgraph repair of the partition results \(\{G(1),G(2),\ldots,G(N_{s}-k+1)\}_{k}\). \(N_{k}^{G}(v)\) is defined as the topological \(k\)-order neighborhood set of node \(v\) in graph \(G\). Based on the topology of the complete multigraph \(G\), all nodes in all subgraphs are filtered. Specifically, if \(N_{k}^{G}(v_{i})\
eq N_{k}^{G(j)}(v_{i})\), node set \(V_{patch}(j)=N_{k}^{G}(v_{i})-N_{k}^{G(j)}(v_{i})\) is then added as a patch to subgraph \(G(j)\), and a new subgraph \(\hat{G}(j)\) is formed. Furthermore, to improve the efficiency of the path query operation in the random walk process, we coupled the topology and geospatial relationship of nodes to establish the fast inter- and intrasubgraph indexes. Specifically, for each original subgraph \(G(i)\), we established the intrasubgraph index based on the corresponding submulti-edge \(E(i)\).