Random walks are widely used for mining networks due to the computational
efficiency of computing them. For instance, graph representation learning
learns a d-dimensional embedding space, so that the nodes that tend to co-occur
on random walks (a proxy of being in the same network neighborhood) are close
in the embedding space. Specific local network topology (i.e., structure)
influences the co-occurrence of nodes on random walks, so random walks of
limited length capture only partial topological information, hence diminishing
the performance of downstream methods. We explicitly capture all topological
neighborhood information and improve performance by introducing orbit
adjacencies that quantify the adjacencies of two nodes as co-occurring on a
given pair of graphlet orbits, which are symmetric positions on graphlets
(small, connected, non-isomorphic, induced subgraphs of a large network).
Importantly, we mathematically prove that random walks on up to k nodes capture
only a subset of all the possible orbit adjacencies for up to k-node graphlets.
Furthermore, we enable orbit adjacency-based analysis of networks by developing
an efficient GRaphlet-orbit ADjacency COunter (GRADCO), which exhaustively
computes all 28 orbit adjacency matrices for up to four-node graphlets. Note
that four-node graphlets suffice, because real networks are usually
small-world. In large networks on around 20,000 nodes,
GRADCOcomputesthe28matricesinminutes. Onsixrealnetworksfromvarious domains, we
compare the performance of node-label predictors obtained by using the network
embeddings based on our orbit adjacencies to those based on random walks. We
find that orbit adjacencies, which include those unseen by random walks,
outperform random walk-based adjacencies, demonstrating the importance of the
inclusion of the topological neighborhood information that is unseen by random
walks.

通过引入轨道连接来捕捉所有拓扑邻域信息，我们提出了一个新的网络嵌入方法，与基于随机游走的方法相比，能够更好地预测节点标签，证明了包括随机游走无法捕捉到的拓扑邻域信息的重要性。