2.5. Distance Pruning and Topology Refinement

Distance pruning and topology refinement aim to further improve the performance of node embedding. The distance constraint D indicates the existence of edges and non-edges between some node pairs, whereby clamping the edge probability of these node pairs leads to a clearer network topology GD. Then, we take GD instead of GL, and repeat the edge probability learning process to gradually refine the node embedding matrix H.

Given the distance constraint D, we may calculate two deterministic sets: an edge set ED⊂MZ and a non-edge set ED∅⊂MZ. The calculation is based on Observation 1 and Observation 2 [11].

For any given nodes u, v and w in an undirected and unweighted graph GV,E, if |duv−duw|≥2, then w,v∉E holds.

Let Lui={v|duv=i,v∈N} be the sets of nodes with the same distance i from u. For two given nodes v∈Lui and w∈Lui+1, if for any node x∈Lui\v, x,w∉E, then v,w∈E holds.

Note that Observation 2 needs u observed distances to all the other nodes in G, which cannot be met under our assumption. Therefore, ED only contains the observed direct neighbors of the distance monitor nodes VOD.

After the calculation of ED and ED∅, we clamp the probability of edges in ED to 1, and the probability of non-edges in ED∅ to 0. Let Mnon−edge=mw,v∈0,1N×N denote the non-edge mask matrix where mw,v=1 if w,v∈ED∅. Then, the distance pruning process can be represented as follows:

Then, we assign the adjacency matrix AGD of GD as the masked AGX. We ignore ED in LFD-NC as ED≪ED∅.

We summarize our algorithm in Algorithm 1.

The time complexity of LFD-NC is the same as that of GCN. The complexity of line 1 in Algorithm 1 is O(|MZ|). In GCN, it is usually satisfied that F>F1≥F2; thus, the complexity of line 3 is ON2F+NF2. The complexity of lines 4 and 5 is O(|MZ|). Since |MZ|<N2, the total complexity of LFD-NC is dominated by GCN.

AGL=AO+WL

forrin 1,2,…,R

H=fAGL,X

AGX=AO+PX

AGXMnon−edge =0

AGL=AGD=AGX

end for

outputAGD