Learning Stochastic Equivalence based on Discrete Ricci Curvature

1 Introduction

Role is a sociological concept at first, and is introduced into network science later to indicating the functions or behaviors of nodes in a network [Zhao et al., 2013]. Learning roles has crucial importance for network mining and analysis, since roles have great potential for shedding light on the underlying characteristics of nodes and the evolution mechanism of networks. Therefore, role has gradually shown its importance on a number of tasks such as node classification [Ribeiro et al., 2017], link prediction [Ahmed et al., 2019] and visualization [Rossi et al., 2018].

It is believed that nodes in the same role have highly similar node-centric connectivity patterns [Rossi and Ahmed, 2014]. A simple example is shown in Fig. 1, in which the nodes are partitioned into different roles noted by their colors. In this example, nodes 6, 7, 8, and 9 are clustered into the same roles with only 1-hop neighborhood structures considered. These nodes are all star-edge-like, but they are significantly different when more hops of neighborhoods are considered. To practically capture higher-order node-centric structural similarity, early graph-based methods defined and leveraged different role equivalences including structural equivalence [Lorrain and White, 1971], automorphic equivalence [Holland and Leinhardt, 1981], regular equivalence [White and Reitz, 1983] and stochastic equivalence [Holland and Leinhardt, 1981; Nowicki and Snijders, 2001]. In specific, two nodes are structurally equivalent if they are connected to the same neighbors. Obviously, structural equivalence is too strict and only effective for nodes very close to each other (For example, nodes 1 and 2 in Fig. 1 are assigned into a role while nodes 11 and 12 are assigned into another role). Automorphic equivalence is a relaxation of structural equivalence as it is based on whether two nodes' node-centric subgraphs are isomorphic. Regular equivalence is relaxed further, as it states that nodes in the same role are connected to role-equivalent neighbors. Thus, regular equivalence is often used through recursive approximate manners [Jin et al., 2011]. Both automorphic equivalence and regular equivalence can be used to distinguish node 6, 9 and node 7, 8 in Fig. 1. However, they make the role of each node strictly tied to neighbors' identities and roles, which leads to low generalization ability. Stochastic equivalence states that nodes in the same role have the same probability distribution of edges or node roles in their neighborhoods. With the distributions, stochastic equivalence reveals more essential structural traits of nodes and is more robust to noises than the other equivalences.

∗Contact Author

Recently, roles have been getting much more attention in the field of network embedding, as those classic methods only preserve proximity [Perozzi et al., 2014; Grover and Leskovec, 2016] and can't work well for role/structure-based tasks. Though not all the role-based network embedding algorithms explicitly define role equivalence, most of their methods of acquiring structural similarity can be analogized to the above role equivalences. Some methods capture structural similarity via higher-order structural features. For example, RolX [Henderson et al., 2012] leverages a feature extraction method that recursively aggregates simple structural features of neighbors for each node. Struc2vec [Ribeiro et al., 2017] biases random walks by constructing a hierarchical network in which the weight of edges are transformed from the degree-based distances between nodes. Role2vec [Ahmed et al., 2019] uses motif-based features instead of node ids to generate sequences as input of Skip-Gram [Mikolov et al., 2013] . Since these methods calculate similarity and map it into embedding space in different ways, it could be considered that they can capture a relaxation automorphic equivalence in different degrees. Besides the aforementioned methods, a few methods that leverage graph kernels to measuring structural similarities between node-centric subgraphs [Ma et al., 2019; Nikolentzos and Vazirgiannis, 2019] can also be regarded as implements of automorphic equivalence. There are also some methods capturing regular equivalence. DRNE [Tu et al., 2018] proposes a layer normalized LSTM to learn regular equivalence by recursive aggregating neighbors' representations for each node. Struc2gauss [Pei et al., 2020] applies RoleSim [Jin et al., 2011], a metric method satisfies Axiomatic Role Similarity Properties and regular equivalence. In summary, almost all the network embedding methods could achieve capturing role equivalences that are stricter than stochastic equivalence and more relaxed than the automorphic equivalence. As far as we know, there are so few previous network embedding methods satisfying a stochastic equivalence criterion, which could be more flexible and robust for role-based tasks.

Therefore, we introduce stochastic equivalence into network embedding algorithms. The key is to choose a proper representation method of edges, which should satisfy the following properties: (1) The representation of an edge can concisely generalize its local topology. (2) The representations are easy to utilize for learning latent role distributions of nodes. To meet above two requirements, we choose discrete Ricci curvature [Chung and Yau, 1996; Ollivier, 2009; Lin et al., 2011] to represent edges. Ricci curvature of an edge is a real value that measures its importance to the closeness of the two neighborhoods. Thus, Ricci curvature can be used to distinguish edge roles such as near-clique edges, bridge edges, and star edges. Specifically, we leverage αRicci-curvature [Lin et al., 2011] (as denoted by edge color in Fig. 1) for it can not only generalize local topology but also use a balance parameter α to control the influence of neighbors. To further take advantages of α-Ricci-curvature, we use a Variational Auto-Encoder (VAE) [Kingma and Welling, 2014] to learn the latent representations of role distributions for each node while a contrastive learning regularizer and a degree-guided regularizer [Tu et al., 2018; Zhang et al., 2021] are applied to enhance its robustness and ability of discrimination. Therefore, we can preserve the stochastic equivalence into embedding space with this framework called Curvature-based Network Embedding with Stochastic Equivalence (CNESE) 1 .

Our main contributions can be summarized as follows:

• We first explicitly propose the idea of bestowing network embedding with the ability to capture stochastic equivalence. We are also the first to introduce discrete Ricci curvature to capture stochastic equivalence and elucidate why discrete Ricci curvature works.
• We propose a framework CNESE based on a Variational Auto-Encoder regularized by both a contrastive learning regularizer and a degree-guided regularizer. It can effectively leverage α-Ricci-curvature to generating highquality role-based embeddings.
• Extensive experiments on real-world datasets demonstrate that our proposed method CNESE achieves stateof-the-art performance.

2 Preliminaries

2.1 Notations and ProblemDefinition

An unweighted undirected network is usually represented as a graph G = (V, E), where V = {v1, ..., vn} is the set of nodes and E ⊆ V ×V is the set of edges. For each node v ∈ V , the set of its neighbors is represented as Γ(v) = {u|(v, u) ∈ E} and its degree is kv = |Γ(v)|.

Role-based network embedding aims to learning a function mapping nodes in G to into a low-dimensional space, denoted as f : V → Z ∈ Rn×d , where Zi is the embedding of node vi preserving its node-centric connectivity patterns.

2.2 Discrete Ricci Curvature on Graphs

In this paper, we use the notion of coarse Ricci curvature introduced by Ollivier [Ollivier, 2009]. Given probability measures mu and mv : V → [0, 1] for nodes u, v ∈ V with mass 1 respectively, a mass-preserving transportation plan between them A : V ×V → [0, 1] meets ∑y∈V A(x, y) = mu(x) and ∑x∈V A(x, y) = mv(y). The transportation distance between the two probability distributions mu and mv is defined as the Wasserstein distance between them, i.e., the minimum average traveling distance via any transportation plan:

where d(x, y) is the graph distance between x and y. Then Ollivier's coarse Ricci curvature for any two nodes u, v ∈ V is defined as:

By comparing the transportation distance and the graph distance between node u and v, Ricci curvature measures how important the shortest path between the two nodes is for making them closer.

1 https://github.com/cspjiao/CNESE

We follow [Lin et al., 2011] to define the probability distribution for node v ∈ V with a parameter α ∈ [0, 1]:

Through (3) we can define α-Ricci-curvature for any u, v ∈ V as κα(u, v) = 1-W(mαu , mαv )/d(u, v). We can tune α to balance the influence of node v itself and its neighborhood. It make sense for real-world networks as the role of an node depends on both itself and its relations to neighbors.

For an edge in G, α-Ricci-curvature can measure not only its importance for the closeness between the endpoints' neighborhoods but also the endpoints' degrees. α-Riccicurvature not only concisely generalizes the local topology of an edge, but also allows for easy estimation of the role distributions as a real value. Thus, we leverage it to capturing stochastic equivalence.

3 Method

In this section, our proposed framework Curvature-based Network Embedding with Stochastic Equivalence (CNESE) is introduced. An overview of CNESE is illustrated in Fig. 2.

3.1 Computation of Ricci Curvature

We efficiently and effectively compute W(mαu ,mαv ) via linear programming as in [Ni et al., 2015]:

where the matrix ρ represents the transportation plan. Then, we can obtain the α-Ricci-curvature for all the edges in G. To capture stochastic equivalence, we estimate the distributions of Ricci curvatures using a fuzzy but effective method, histogram, on the connected edges for all the nodes.

3.2 Variational Auto-Encoder

To preserve stochastic equivalence into low-dimensional vector space, we utilize a Variational Auto-Encoder through reconstructing Ricci curvature histograms.

We assume that the latent representation Zi of node vi ∈ V is an d-dimensional independent random vector matching a multivariate Gaussian distribution N(µi,Σi). The diagonal entries of Σi is represented as a vector σi. Then we generate Zi as follows:

where H is the Ricci curvature histogram matrix for all the nodes.

The mean vector µi and variance vector σi are learned as follows:

Here, MLP means a multi-layer perceptron model. Thus our variational encoder G(·) is composed of (5) and (6).

We also use a multi-layer perceptron as our decoder to reconstruct H:

The loss of reconstruction is:

where ‖·‖F denotes the Frobenius norm.

3.3 Degree-Guided Regularizer

The Ricci curvature histograms could be a double-edged sword on embeddding generation sometimes. Though the fuzziness of histograms makes estimating stochastic equivalence easier, it could abate the structure information contained in Ricci curvatures. This problem is particularly prone to occur on very small or sparse networks. To mitigate this problem, we leverage a degree-guided regularizer as in DRNE [Tu et al., 2018]. In detail, we use a multi-layer perceptron as an Approximator, i.e., A(·) = MLPapp(·), to approximate the degree of each node. Our degree-guided regularizer is designed as follows:

Thus, the degree-guided regularizer can bestow the embeddings with guidance information of degrees.

3.4 Contrastive Learning Regularizer

To generate more robust embeddings, we construct a contrastive learning regularizer for our framework. We build a Discriminator using a multi-layer perceptron, i.e., D(·) = MLPdis(·), which is essentially a binary classifier for distinguishing negative samples Z- and latent representations generated by G(Hi). As many negative samples are sampled from the standard Gaussian distribution q(Zj ) = N(0, I) as positive samples (node embeddings). The objective of the contrastive learning regularizer is as follows:

The Discriminator D(·) is trained as follows:

In total, we embed Ricci curvature histogram matrix H into a low-dimensional vector space by minimizing a combined loss function as follows:

where β and γ are the weights of the degree-guided regularizer and the contrastive learning regularizer.

4 Experiments

In this section, we want to validate the role discrimination ability of our CNESE through experiments on role-based node classification, bot detection and visualization.

4.1 Experimental Setup

Datasets and Baselines

We conduct the role-based node classification experiments on Air-traffic networks (USA, Brazil, and Europe) [Ribeiro et

• † - means no activation function is applied.

‡ The second activation function is applied on the last layer, while the first is applied on the other layers.

Table 2: Configuration of multi-layer perceptrons.

al., 2017], Actor co-occurrence network [Ma et al., 2019], Reality phone call network [Guo et al., 2020], and Enron email network [Klimt and Yang, 2004]. We also do an experiment to detect bot users in two Wikipedia user interaction networks (br-Wiki-talk and cy-Wiki-talk) [Sun et al., 2016]. Some statistics of these datasets are provided in Table 1.

We compare our CNESE with a set of baselines including classic (community-based) and the state-of-the-art rolebased network embedding methods. For classic methods, we use DeepWalk [Perozzi et al., 2014] and node2vec [Grover and Leskovec, 2016]. For role-based methods, we use RolX [Henderson et al., 2012], struc2vec [Ribeiro et al., 2017], GraphWave [Donnat et al., 2018], DRNE [Tu et al., 2018] and struc2gauss [Pei et al., 2020]. The parameters of all these methods are well tuned for the best performance.

Model Configuration

MLPs with different layer numbers and different activation functions are applied on different parts of CNESE accord- To save space, Micro-F1 and Macro-F1 are shortly denoted as Micro and Macro respectively. OM indicates out-of-memory error.

Table 3: Node classification average F1 score (%) on different networks.

ing to their different purposes, as shown in TABLE 2. The bin number of curvature histograms is set to 80. The width of MLPs and embedding dimension are set to 64. We apply Adam SGD optimizer [Kingma and Ba, 2015] with learning rate 0.001 and batch size 32 for at most 50 epochs. L2 regularization with weight 0.001 is adopted to avoid overfitting. In later experiments, unless otherwise stated, parameter α of α-Ricci-curvature is set as 0.05, and 0.5 on Brazil and the other datasets respectively. β is set to 5 and γ is set to and 2.

4.2 Role-based Node Classification

We conduct node classification tasks on 6 datasets: Brazil, Enron, Europe, USA, Reality, and Actor. Specifically, a linear logistic regression classifier is trained and tested on embeddings for each dataset. We sample 70% node embeddings as a training set and the other embeddings are used as the test set. We run all the baselines and CNESE 25 times on each network and calculate the average of micro-averaged F1 score (Micro-F1) and macro-averaged F1 score (Macro-F1) for every method. We report the results in TABLE 3 and the best results are indicated in bold.

From these results, we can observe that all the role-based network embedding methods outperform classic methods on almost all the networks except for Enron network. On most datasets, results of role-based methods are at least 10% higher than those of DeepWalk and node2vec. This demonstrates that methods preserving node proximity are not appropriate to role-based node classification tasks.

Our proposed CNESE achieves better performance than the other role-based methods on most datasets. CNESE performs very closely to the best results in the cases where CNESE is not the top. This demonstrates the stability and effectiveness of our CNESE. On Brazil dataset, DRNE gives the best results, because the network is too small to estimate the equivalence between distributions while node labels and node degrees are highly correlated. RolX yields the best results on USA network as the roles are more similar to automorphic equivalence. On Enron network, DeepWalk and node2vec perform closely to some role-based methods. This is because node labels in Enron denote real employee titles unlike those of the other networks based on specific function measures. In this case, methods capturing automorphic equivalence and regular equivalence lose effectiveness while CNESE and GraphWave still perform greatly. Thus, our CNESE shows its wide applicability.

4.3 Bot Detection

In this section, we investigate whether our CNESE is able to find the nodes playing rare roles. We carry out a bot detection experiment on the two Wikipedia user interaction networks. First, we exert network embedding methods to generate representations for all the users. Then we calculate the euclidean distance between users and take out K closest users for each bot. Finally, we compute the P@K, i.e., the average precision on the selected K users for all bots. The results are given in TABLE 4 and the best results are indicated in bold.

On br-Wiki-talk network, all results of role-based methods are at least twice as good as those of DeepWalk and node2vec. Our results are even three times as precise as theirs. These results demonstrate that bots in br-Wiki-talk network are strongly structurally similar to each other and our CNESE is better at capturing this structural similarity. As for cy-Wiki-talk network, the results of DeepWalk and node2vec improve while those of role-based methods deteriorate. Some role-based methods perform worse than DeepWalk and node2vec but CNESE still achieves the best results. It shows that bots in cy-Wiki-talk network are less structurally identical and our CNESE have favorable adaptability on the task with weaker structural characteristics.

4.4 Parameter Sensitivity Analysis

Here, we investigate the influence of parameters including the balance parameter of α-Ricci-curvature α, the weights of two regularizers β and γ, and the dimension of embeddings d. We conduct role-based node classification on Brazil, Europe, USA, and Reality networks and report only the MicroF1 score in Fig. 4 for brevity. We set α = 0.5 (α = 0.05 on Brazil), β = 1, γ = 1, and d = 64 when they are control variables. In Fig. 4(a), the performance deteriorates firstly and then raises slightly when α increases on Brazil. The opposite trend is shown on other networks. This indicates that nodes express their functions not only on the relations to their neighbors but also on themselves. As shown in Fig. 4(b) and Fig. 4(c), we illustrate the influence of the weights of two regularizers β and γ. As β gets larger, the performance of CNESE gets better, while on Brazil, it gets the best performance at β = 3. It demonstrates that node degree can help capture stochastic equivalence, but when it is large enough, the original information may lose. In Fig. 4(c), the performance jumps up to the best at γ = 2 and drops when γ is larger on Brazil network. The reason is that contrastive learning with negative samples can prevent CNESE learning wrong distributions. It may mislead the learning process on small size networks like Brazil, since too few positive samples can be used for training. And for embedding dimension d shown in Fig. 4(d), the performance raises when d increases, and we can obtain good enough result with d = 64.

We also take ablation analysis of the contrastive learning and degree-guided regularizer. In Fig. 4(b), when the parameter β is set to 0, it denotes the model CNESE without regularizer of node degree. We observe a noticeable increase when this regularizer is added to our model, which means that degree has a significant contribution to the role of nodes, and the process of extracting features and encoding loses the information. As for the part of contrastive learning, we report the effectiveness in Fig. 4(c) when γ = 0. In this situation, the model only consists of VAE and degree-guided regularizer, and we find that the performance decreases firstly but gets best when γ = 2.

4.5 Visualization

In this section, we compared our CNESE with baselines on visualization tasks. We apply t-SNE to reduce the dimension of embeddings learned by different methods. All the embeddings on Brazil network are mapped as two-dimensional vectors. The results are illustrated in Fig. 3. Each node is represented by a point while the node label is denoted by the color of the corresponding point. Ideally, the points in the same color should be close to each other and those in different colors should be far from each other. From the subfigures of DeepWalk and node2vec, it can be observed that the points in four colors are mixed together. In the subfigures of rolebased methods, the points form areas based on color. Furthermore, GraphWave, DRNE, struc2gauss, and our CNESE achieve more ideal results. However, the points generated by GraphWave, DRNE, and struc2gauss are almost lined up. This indicates that these methods may overfit only one structural property. For example, DRNE could be over-dependent on degree guidance. Though we leverage a degree-guided regularizer to CNESE as well, our method can contain more structure information as Ricci curvature does.

5 Conclusion

In this paper, we provide and explain the idea of preserving stochastic equivalence into network embeddings. To implement the idea, we leverage Ricci curvature to generalize local topology and explain why it works. Then we construct a role-based embedding framework CNESE that combines Variational Auto-Encoder with a degree-guided regularizer and a contrastive learning regularizer and treat Ricci curvature histograms as input. Finally, we verify the effectiveness of CNESE with extensive experiments. Though we design our CNESE for undirected networks, it is easy to extend it on directed networks.

Acknowledgements

This work was supported by the National Natural Science Foundation of China (61902278).