Towards Higher-order Topological Consistency for Unsupervised Network Alignment

So far, most network alignment approaches are supervised. Supervisory data are required so as to refine embedding space either in the form of partial ground truth (e.g. PALE [19], CENALP [24]) or prior alignment matrix (e.g. IsoRank [14], FINAL [17]). Due to the expensive cost of manual labeling, unsupervised methods are more suitable and desirable in some real-life applications.

Another noticeable trend is that more and more methods try to leverage both structural and attribute information so as to better capture the information of the network nodes (such as FINAL[17] and REGAL [18]). Recently, some work has taken advantage of the natural strength of GCN in integrating both network topology and node attributes and has empirically shown the great potential of GCN for alignment tasks [10, 25]. A wide variety of structural metrics are proposed and utilized for formulating corresponding topological consistency, like node degree [18], connectivity [19], and co-occurrence in random walks [20]. Besides, some methods pay attention to a broader neighborhood of nodes, such as stacking more GCN layers [10] or aligning triangular structures [26]. Even so, most previous work essentially just models the edge-indiscriminative topological pattern, and hence their corresponding topological consistencies remain low-order. Unlike previous work, we formulate the high-order topological consistency based on different orders of edge pattern. It should be emphasized that larger neighborhoods and higher-order consistency cannot be simply equalized. The experimental results also empirically demonstrate that our proposed higher-order topological consistency performs far better than simply considering a larger neighborhood, such as introducing diffusion matrices[27].

High-order patterns of network structure such as graphlets and motifs have been demonstrated to be very informative and helpful for different tasks in many fields. For instance, graph motifs are utilized in [28] for classifying directed CORA citation networks. Graphlet patterns are taken into consideration to obtain better performance in the semi-supervised node classification task [29]. In [30], the use of motifs enables the perception of high-order semantics in heterogeneous graphs. In more detail, each node or edge can be differentiated at the level of orbit [31, 32]. Some network alignment techniques, such as H-GRAAL [33], GREAT [34], GraphletAlign [35], etc., treat the graph degree vectors as node/edge features and then quantify the corresponding topological similarity for network alignment. By contrast, we define high-order topological consistency based on the constructed graph orbit matrix, which is injected into the aggregation process of GCN in order to further extract and integrate useful information. In this way, we are capable of obtaining abstract features of nodes for similarity computation.

Compared with other node embedding techniques like Node2Vec [36], DeepWalk [37], and LINE [38], GCN [39] is naturally capable of integrating both structure and attribute information due to its special encoding mechanism and has shown its effectiveness in processing graph-structured data [40]. To address the issue that GCN treats every edge equally without distinction, Graph Attention Network and its variants are proposed, which generally need labels to train extra parameters [41, 29]. However, by using higher-order topological patterns, we can distinguish edges without introducing additional training-required parameters, which is a great merit for unsupervised learning.

Auto-Encoder and its variants have important applications in many fields. For example, Wang et al. [42] use variational autoencoder with dynamic extensions to successfully address the dynamic interaction problem of latent variables. As a special variant, Graph Autoencoder (GAE) [23] is proposed for unsupervised learning on graph-structured data. Inspired by such an encoder-decoder paradigm, we train our GCN encoder to be multi-orbit-aware by sharing encoding parameters among different orders of orbit topology. Hence, it can be expected to prevent the model from relying on any single topological pattern.

We first construct graphlet orbit matrix and define the higher-order topological consistency based on it.

Graphlet is a term used to denote a connected network with a small number of nodes [22]. Any induced subgraph can be grouped into a certain type of graphlet if they are isomorphic. $G^{\prime }=(V^{\prime },E^{\prime })$ is an induced subgraph of $G=(V,E)$ if and only if $V^{\prime }\in V$ and $E^{\prime }=\left\{\right(u,v)\in E|u,v\in V^{\prime }\}$. Furthermore, the edges of each graphlet can be clustered into orbits with respect to the graphlet automorphisms [32]. For instance, there are 9 graphlets and 13 edge orbits for subgraphs with 2-4 nodes as shown in Fig. 4. Orbits define the “roles” of edges within the graphlet. As an example, in the graphlet of a three-edge chain, one edge represents the bridge and the remaining two edges can be connected through the bridge; the edges of this graphlet thus form two different orbits (numbered 4 and 3, respectively). Moreover, edges around a node can be distinguished by comparing their occuring frequency on multiple orbits, as in the illustrative example shown in Fig. 5.

We construct a set of graphlet orbit matrix (GOM), denoted as $O=\{O_0,O_1,\cdots ,O_K\}$, where $K$ matrices correspond to $K$ orbits. Each GOM contains the frequency of edges on the corresponding orbit. Formally, given a graph $G$ with a vertex set of size $n$ and any two vertices $i$ and $j$ of it, the $k$th GOM $O_k\in N^{n\times n}$ is defined as follows:

The greater the value of $O_k(i,j)$ is, the stronger the connection between node $i$ and node $j$ is with respect to the orbit $k$. In addition to the above weighted definition, GOM can also be binary, in which $O_k(i,j)$ equals to 1 as long as the edge $(i,j)$ is observed on orbit $k$ for at least one time, otherwise the value of $O_k(i,j)$ is 0. In the binary case, the distinctions between edges are weakened. Referring to the example in Fig. 5, the value of edge $(b,c)$ on orbit 1 would be 1, which is the same as that of edge $(a,b)$ if using binary setup. Hence, in this paper, we mainly consider the weighted form of GOM.

Taking the value of each entry in GOM as the weight of the corresponding edge, GOMs exactly represent different levels of induced networks, as shown in Fig. 1. Therefore, we can mathematically define higher-order topological consistency based on GOMs:

To integrate attribute consistency and higher-order topological consistency, we elegantly merge higher-order topological information into the aggregation process of GCN. Instead of treating all edges equally, we respect the fact that edges playing different roles in each high-order structure should be given different weights when passing messages.

Weighted aggregation. We naturally assign the orbit-defined weight to an edge for passing information between nodes. Formally, the feature of node $i$ on $l$th layer and $k$th orbit can be obtained by:

which can be performed efficiently in matrix formulation: $H_k^l=f\left(O_k{H}_k^{l-1}{W}^{l-1}\right)$, where $H\in R^{n\times d^{l-1}}$ is a feature matrix, $f$ is a nonlinear activation function, and $W^{l-1}\in R^{d^{l-1}\times d^l}$ is a trainable weight matrix for node representation encoding.

Modified self-connection. In Eq. (2), only information from neighbors is considered to generate a node’s feature. To include the information from a node itself, we need to add self-connections. Note that the values of a weighted orbit matrix denote the frequency of edges occuring on a certain orbit, which may be far bigger than 1. In this case, using a typical identity matrix as the self-connection matrix is likely to result in the issue that the impact of self-connection is significantly weakened compared with its neighbors. Here, we define a more appropriate self-connection matrix with respect to orbit $k$ as follows:

where ${max}_{1\le j\le n}{O}_k(i,j)=0$ means that node $i$ is not connected to any other node on orbit $k$. Intuitively, this matrix allows a node to either assign an importance to itself that is in line with that of its most important neighbor, or just consider its own information if there are no neighbors around it. Hence, the orbit matrix can be modified by ${\tilde{O}}_k=O_k+C_k$.

Normalized Laplacian. According to the aggregation mechanism of GCN, nodes with large values in ${\tilde{O}}_k$ will have large values in their feature representation, and vice versa. This may cause vanishing or exploding gradients [39]. Hence, in practice, the procedure of normalization is required. The symmetric normalized Laplacian matrix on orbit $k$ can be obtained by ${\tilde{L}}_k={\tilde{F}}_k^{-\frac{1}{2}}{\tilde{O}}_k{\tilde{F}}_k^{-\frac{1}{2}}$, where ${\tilde{F}}_k(i,i)={\sum }_{j=1}^n{\tilde{O}}_k(i,j)$ is a diagonal frequency matrix.

Forward encoding. Say the GCN encoder contains $L$ hidden layers, the output embeddings of two graphs, denoted as $H_{s,k}^L$ and $H_{t,k}^L$ respectively, can be obtained through the forward encoding process:

where the non-linear activation functions $F=\{f^0,f^1,\cdots ,f^{L-1}\}$ and the weight parameters $W=\{W^0,W^1,\cdots ,W^{L-1}\}$ are shared between source and target graphs.

Theoretical Analysis. We mathematically prove that high-order structural consistency and attribute consistency will lead to identical node embeddings across two networks through our proposed encoding mechanism. First, we have the following lemma.

Actually, Lemma 1 indicates that orbit-defined aggregation inherits the characteristics of the typical aggregation manner of GCN that attribute and topology similarity of nodes can be transformed into the similarity of node embeddings. To leverage the power of orbit-weighted aggregation for alignment tasks, we extend Lemma 1 to the scenario of two networks and obtain the following proposition.

The key factor in extending Lemma 1 to Proposition 1 is the sharing of GCN encoder between two networks, which guarantees that nodes in two networks are embedded by the same mapping mechanism. Therefore, the consistency constraints of alignment can be transformed into the similarity of node embeddings and an extra step for aligning feature space can be omitted, which is claimed to be necessary in some previous embedding-based methods [43].

As opposed to just using the trivial edge-defined topology information, multiple higher-order topological patterns give us more comprehensive information for aligning nodes.

Orbit-reconstruction loss. Without alignment labels, we adopt auto-encoder scheme to train the model parameters $W$. We reconstruct each orbit Laplacian matrix using generated representations. The matrix of source graph on orbit $k$ is rebuilt by:

The reconstructed Laplacian matrix of target graph ${\hat{L}}_{t,k}$ can also be obtained in a similar way. The orbit-reconstruction loss for orbit $k$ is further computed as follows:

where ${\parallel \cdot \parallel }_F$ denotes the Frobenius norm which is used to measure the difference between the original Laplacian matrix ${\tilde{L}}_{\cdot ,k}$ and the reconstructed one ${\hat{L}}_{\cdot ,k}$. By minimizing $los{s}_k$, the GCN encoder can be regarded as kth-orbit-aware since the useful information required for reconstructing the $k$th orbit matrix is captured.

To be multi-orbit-aware, all orbit-reconstruction loss items are added up to the overall objective:

As $\Gamma$ is minimized by gradient descent optimizers, like Adam [44], the similarity of the embeddings generated by the encoder is able to reflect the corresponding topological and attribute consistency. The multi-orbit-aware process is summarized in Algorithm 1.

In this subsection, we use $h_s$ and $h_t$ to denote the embeddings of source graph and target graph output by the last hidden layer on any orbit, omitting the superscripts $L$ and subscripts $k$ for brevity.

Hubness problem. By Lemma 1 and Proposition 1, both potential anchor nodes across different graphs and nodes with similar attributes and structure in the same graph will have embeddings as similar as possible. In high dimensional embedding space, these similar embeddings will be located closely. As a result, some nodes, called hubs [45], tend to be disproportionally nearest neighbors of many other nodes in the other graph. Direct nearest-neighbor rule favors these hubs, while at most, one of all the nearby nodes around a hub is a true anchor node. Thus, to diminish the hubness problem and identify nodes that are more isolated and more trustworthy to align with other nodes, we introduce the locally isolated similarity index (LISI).

Locally isolated similarity index. Due to the properties of translation invariance and scale invariance, we use Pearson correlation coefficient to measure the similarity between the embeddings of two nodes $h_s\in H_s$ and $h_t\in H_t$:

where ${\overline{h}}_s$, ${\overline{h}}_t$ is the mean value of $h_s$ and $h_t$.

We consider a bi-partite neighborhood graph, in which each node of a given graph is connected to its $m$ nearest neighbors in the other graph. Using $N_t\left(h_s\right)$ to denote the neighborhood of node embedding $h_s$ on target graph space, the hubness degree of node $h_s$ is measured by computing its mean similarity to its target neighborhood as follow:

According to the definition, the larger $D_t\left(h_s\right)$ is, the more likely $h_s$ is to be a hub. Similarly, denoted by $D_s\left(h_t\right)$, the mean similarity between $h_t$ and its source neighborhood can be computed. They are used to calculate the similarity measure LISI:

Here, a bigger value of LISI can be obtained when these two embeddings are similar enough to each other (the first item is large) while they are as less similar as possible to their neighbors in the other graph (the latter two items are small). In other words, LISI aims to identify two similar embeddings that are locally isolated rather than being hubs of dense areas.

Trusted pairs. The LISI values of node pairs across source graph and target graph are computed as the alignment matrix $M$. If two nodes are each other’s nearest neighbors with respect to LISI, they are regarded as a trusted pair. Mathematically, a trusted pair $⟨h_s,h_t⟩$ satisfies the following conditions:

Aggregation coefficient fine-tuning. According to topology consistency, if two nodes are connected in a network, then their anchor nodes (if both exist) are likely to maintain connectivity in another network. In other words, if node $A$ and node $a$ form an anchor link across source graph and target graph, then potential anchor links are likely to exist across the neighborhood of node $A$ and that of node $a$. To find them, we have the following proposition.

In fact, assigning bigger aggregation coefficients to trusted anchor nodes means that their neighboring potential anchor nodes can receive more similar information. The more trusted nodes around potential anchor nodes, the easier they can be identified. Formally, two vectors $r_s\in R^{n_s}$ and $r_t\in R^{n_t}$ are maintained to update the reinforcement factors for nodes in source graph and target graph respectively. At the beginning, both of them are initialized to all-one vectors. If node $i\in V_s$ and node $j\in V_t$ are identified as trusted pairs, their corresponding reinforcement factors are updated as follows:

where $\beta >1$ is the reinforcement rate.

The aggregation scheme of GCN is modified as:

where $R_s$ is a diagonal reinforcement matrix in which $R_s(i,i)=r_s\left(i\right)$. Likewise, the embeddings of target network are generated by introducing reinforcement matrix $R_t$.

The fine-tuning process is iteratively conducted as shown in Fig. 3. Each loop contains four steps: (a) identify trusted pairs from the alignment matrix; (b) update aggregation coefficients of trusted pairs; (c) generate new node embeddings; (d) compute new alignment matrix. We also need to track the number of trusted pairs $T$ in every loop. The objective is to maximize the number of trusted pairs identified based on each level of consistency. If the number stops growing, the loop is terminated (the loops for different orbits are independent of each other). The fine-tuning algorithm is summarized in Algorithm 2.

After refinement procedure is done on each orbit, corresponding alignment matrices $M=\{M_0,M_1\cdots ,M_K\}$ are obtained. Each of them contains the alignment score of all node pairs, focusing on a specific order of topological consistency. To integrate those scores and produce the final alignment matrix, we consider an alignment-related index: the number of trusted pairs identified in different orders of topological consistency. The motivation is that the more trusted nodes that can be identified, the higher the corresponding embedding quality.

We denote the weight of $M_k$ by ${\gamma }_k$, which is defined as:

where $T_i$ denotes the number of trusted pairs identified based on orbit $i$. Then the final alignment matrix is the weighted sum of each orbit-specific matrix: $M={\sum }_k{\gamma }_k\cdot M_k$.

Given the final alignment matrix, for each node in source graph, the node with the highest score in target graph is regarded as the most possible anchor node.

Without loss of generality, we denote the number of nodes by $n$, the number of edges by $e$ (non-zero entries of adjacency matrix), the maximal node degree by $D$, and the dimension of hidden features by $d$.

Time complexity. There are mainly three steps to analyze:

• Orbit matrix construction. In this work, we use orbits in graphlets with not more than 4 nodes. Thanks to the scalable Orca algorithm [46, 47], edge orbit counting can be done in $O\left(e{D}^2\right)$ for 4-node graphlets, which allows us to count orbits on graphs with millions of edges within a second. And constructing orbit-based Laplacian matrices takes $O\left(e\right)$.

• Multi-orbit-aware embedding. The propagation of GCN encoder takes $O\left(Ke{d}^L\right)$ where the numbers of orbits $K$ and hidden layers $L$ are usually small constants.

• Trusted-pair based fine-tuning. Identifying trusted-pairs takes $O\left(K{n}^2\right)$, and refining the aggregation coefficients takes $O\left(n\right)$.

Therefore, the first two steps take $O\left(e\right)$ and the third step takes $O\left(n^2\right)$. Note that $O\left(n^2\right)$ is dominated by the global alignment task itself ($M\in R^{n_s\times n_t}$), and most operations, such as trusted-pair identification, can be efficiently implemented through matrix manipulation. Also, considering the practical running time shown in Fig. 8, the overall time cost of our approach is less than or comparable to that of most benchmark methods.

Space complexity. We analyze space complexity from three aspects:

• Orbit-relevant storage. Due to the increasing sparsity of higher-order orbits, there are at most $O\left(e\right)$ non-zero entries in each orbit matrix. Therefore, the worst-case space complexity for storing $K$ sparse orbit Laplacian matrices is $O\left(Ke\right)$.

• Embedding-relevant storage. It takes $O\left(L{d}^2\right)$ to store trainable parameters in $L$ GCN layers, and the space required for storing the features of $n$ nodes in $L$ hidden layers is $O\left(Lnd\right)$.

• Alignment-relevant storage. In the fine-tuning stage, the LISI matrix is computed for identifying trusted pairs and can be released from memory once the identification process is done. Hence, it takes $O\left(n^2\right)$ to store the LISI matrix in the whole refinement process. As for the weighted integration stage, a cumulative approach can be adopted, which only requires maintaining a main matrix and iteratively adding each orbit-specified score matrix, and thus it also takes $O\left(n^2\right)$, the same as most alignment methods.