# Pair-view Unsupervised Graph Representation Learning

Li You, Luo Binli, Gui Ning
School of Computer Science and Engineering
Central South University
Changsha, China 410083
youli.syvailgmail.com; ningguicsu.edu.cn

###### Abstract

Low-dimension graph embeddings have proved extremely useful in various
downstream tasks in large graphs, e.g., link-related content recommendation
and node classification tasks, etc. Most existing embedding approaches take
node as the basic unit for information aggregation, e.g., node perception
fields in GNN or con-textual node in random walks. The main drawback raised by
such node-view is its lack of support for expressing the compound
relationships between nodes, which results in the loss of a certain degree of
graph information during embedding. To this end, this paper pro-poses
PairE(Pair Embedding), a solution to use “pair”, a higher level unit than a
“node” as the core for graph embeddings. Accordingly, a multi-self-supervised
auto-encoder is designed to fulfill two pretext tasks, to reconstruct the
feature distribution for respective pairs and their surrounding context. PairE
has three major advantages: 1) Informative, embedding beyond node-view are
capable to preserve richer information of the graph ; 2) Simple, the solutions
provided by PairE are time-saving, storage-efficient, and require the fewer
hyper-parameters; 3) High adaptability, with the introduced translator
operator to map pair embeddings to the node embeddings, PairE can be
effectively used in both the link-based and the node-based graph analysis.
Experiment results show that PairE consistently outperforms the state of
baselines in all four downstream tasks, especially with significant edges in
the link-prediction and multi-label node classification tasks.

## Introduction

Graph-structured data are becoming ubiquitous across a broad spectrum of real-
world applications, e.g., the networks of molecules, social, biology, finance
[25] and etc. Low-dimensional vector embeddings of nodes in large graphs are
extremely useful for a wide variety of tasks such as prediction and graph
analysis. Substantial efforts have been committed to developing novel graph
embedding approaches. The idea behind graph embeddings usually employs
dimensionality reduction techniques to distill high-dimensional information
about one node’s neighborhood into a dense vector embedding so that the nodes
that are “close” in the input graph are also “close” in representation
space[8].In order to achieve high parallelizability and low computation
complexity, nodes are normally assumed to be independent of each other and the
complex relationships between nodes are largely ignored[3]. By this
assumption, the nodes are used as the independent cores for the information
condense. The complex information related to a node, e.g. node features,
relations, and local structures can be independently processed and condensed
into the node embeddings. However, during this embedding process, some complex
yet important relation information between nodes is inevitably lost. The
analysis tasks on edges, such as link prediction, cannot effectively recover
edge information with indirect node embeddings, and it is difficult to obtain
the best performance.[19].

Fig. 1 shows an example of the fact described above. As shown in Fig.1 (b),
the node U have two different relations corresponding to two connections with
nodes A and C: family and friends. Conventionally, the two peculiar relations
are aggregated by a unified function. The expression of unique characteristics
of different types of relationships is limited by the permutation-invariant
feature of aggregation operations. In other words, using a single-node view
for modeling and aggregating peripheral information into a single node loses
its multi-role information and multi-type relationship. Reference [19] also
points out that “representing edges in a direct approach is very important
because an edge representation vector generated from the embedding vectors of
its endpoints cannot preserve the complete properties of this edge”.

Figure 1: a) Node with multiple relationships(roles) b) node-view condense
results of the loss of information c) pair-view with explicit relation
representation d) Pair-view embeddings can be directly used in edge related
downstream tasks and translated to node embeddings when dealing with analysis
tasks on edges.

To preserve the relation-specific information during embedding, it is argued
that we should go beyond the localized node view and utilize higher-level
entities with richer expression powers. In this paper, the “pair”, a structure
naturally existing in graphs, is adopted as the basic unit for embedding. As
shown in Fig.1 (b), compared to the node, a unit of “pair” has much richer
information: the information two paired nodes, the relations between the
paired nodes, and the surrounding structural context. Meanwhile, this method
has high parallelism.

The main contributions are summarized as follows:

  * •

Breaking the shackles of node view, we innovatively propose the use of pair as
the basic modeling unit with a so-called “PairE” solution. Rather than
modeling from a node perspective with little internal structure, PairE
explicitly embedding the rich information in, between, and around its paired
nodes. The operations related to pair embedding, e.g., data aggregation, pair-
node embedding mapping and etc, are correspondingly defined.

  * •

A multi-task self-supervised auto-encoder is designed to encode information
for pairs, which fulfills two mutual-related pretext tasks: to reconstruct
both pair features and aggregated features from neighboring nodes. This design
allows for the seamless integration of nodes, intra-relations, and structural
information into one set of pair embeddings. This design is simple, fast and
it demands few hyper-parameters.

  * •

Experiment results show that PairE outperforms strong baselines in both the
link-related and node-related tasks, especially with significant edges in the
link-prediction and multi-label node classification tasks.

It is worth noting that PairE differs significantly with those approaches,e.g.
[1] that use existing node-based embedding method to obtain the embedding
vectors of edges by converting original graph into the so-called line
graph[2], representing the adjacencies between edges the graph. However, In
most graphs, edges normally contains little information and those approaches
generally fails to use rich information in nodes. Reference codes and the
introduced evaluation data-sets are attached in the Appendix for evaluation.

## Related Work

DeepWalk[14] constructs a semantic sequence to extract node representations
through the depth-first walk. To integrate more structural information,
node2vec[6] allows for the trading off between walks that are more akin to
breadth-first or depth-first search and learning embeddings that emphasize
community structures and local structure. Line [16] further considers two-hop
adjacency neighborhoods. Their approaches did not take the advantage of rich
side information, e.g., node features. Regarding the embedding with node
features, TADW[22] further incorporates text features of vertices into network
representation learning. SINE[13] learns the node embedding by enforcing the
alignment of the locally linear relationship between nodes and its K-nearest
neighbors on topology and attribute space. DANE[28] proposes the usage of
multiple graph networks to achieve transfer learning. LQANR[23] adopts the
usage of K-hop adjacent matrix to jointly learn the low-bit node
representations and the layer aggregation weights. To represent the structural
information, SDNE[20] uses the auto-encoder to extract both first-order and
second-order proximity. Those random walk-based approaches are from node view
and normally simplify the complicated relationship between nodes into the co-
occurrence probabilities, and can hardly represent complex relations.

GNN-based solutions typically adopt the so-called message mechanism to collect
neighboring information with general differences on how to design the function
of aggregation, combine, and readout functions[21]. GCN [12] uses a weighted
sum and a (weighted) element-wise mean. GraphSAGE[7] uses concatenation for
combination and adopts the element-wise mean, a max-pooling neural network,
and LSTMs aggregators. GAT [17] proposes the use of self-attention to evaluate
the different influences of neighboring nodes. GIN[21] analyzes the expressive
power of GNNs and proposes to use the sum aggregator to solve the graph
isomorphism test. DGI[18] relies on maximizing mutual information between
patch representations and corresponding high-level summaries of graphs.
Besides, in order to include more complex relationships with neighbors,
GraphAir[10] proposes the non-linear aggregation of the neighborhood
interaction. However, those solutions are still from a single node view and
difficult to model the mutual influence between nodes. In other words, these
practices decouple the interactive relationship of each node into independent
and distributed node representations, and still take node as the basic element
for information aggregation and might result in the loss of information during
aggregation.

Few recent researchers noticed the mutual influence between nodes. Splitter[5]
notices the multiple roles played by a node and proposes the usage of multiple
representations of the nodes in a graph. However, they still use the node as
the basic embedding unit. One recent approach, Edge2vec[19] proposes the
explicit use of the edge as basic embeddings units. However, this approach
considers only the structure information and provides no support on how to
translate edge embeddings to node-related tasks.

Figure 2: A conceptual diagram for multi-self-supervised auto-encoder

## PairE Methods

### Preliminaries

Let $G=(V;E)$ denote a directed graph, where $V$ is the node set and $E$ is
the edge set, with node feature vectors $X_{v}$ for $v\in V$. In order to
better differentiate node attributes and aggregated attributes, we generally
use $X_{v}^{self}$ to denote $X_{v}$.

Definition 1: (Pair). A pair is an ordered node pair $p=(u,v)$ starting from
the node u to the node v, where $u,v\in V$ and $(u,v)\in E$. Node u and v are
called the source node and the target nodes, respectively. We denote P(G) as
the set of all pairs in G.

Definition 2: (Pair neighborhood) we define the neighborhood of pair p=(u,v)
as a set of pairs adjacent to pair p

$N(p_{u,v})=\\{n\in P(G)\;|\ |p\cap n|=1\\}$

$N(p_{u,v})$ represents the pair set that has and has only one common node
with $p_{u,v}$,including all pairs with u, v as the source node or target
node.

Definition 3: (Pair embedding problem) The task of pair-based graph embedding
is to learn a low-dimensional vector $z_{u,v}$ to better represent the
original ordered node pair $p_{u,v}$ in the entire graph. In the embedding
process, two ordered nodes and their relationships and surrounding context
$N(p_{u,v})$ should be preserved as much as possible.

Definition 4: (Embedding Translation) To be compatible with different
downstream tasks, we define an appropriate translation function $T$ to map the
embedding of pairs to a different level of graph elements. In this paper, we
only focus on the translation from pair embedding to nodes. We defined a
$T(Z_{u,v})\,\rightarrow\,z_{u}$,$Z_{u,v}=\\{z_{u,v}|\ (u,v)\in N(p_{u,v})\\}$
. Due to the order free nature of edges, this function has to be permutation-
invariant.

### Multi-self-supervised auto-encoder

For PairE, the goal is to find an embedding in which the “similar” pairs in
the input graph are also “similar” in representation space. It is essential
that the learned embedding can best represent three types of information: the
nodes’ self-features, the relations between two paired nodes and the
structural information around the pair.

To learn graph representations from multiple perspectives, a novel multi-self-
supervised auto-encoder is designed to simultaneously learn a joint embedding
space with data from multiple perspectives. By this auto-encoder, two self-
supervised tasks are fulfilled: 1) starting from the pair itself, to fit the
features of paired nodes. 2) starting from the neighboring context of the
pair, to fit the features of surrounding nodes. These two tasks are inter-
correlated. Usually, learning these tasks jointly could improve performance
compared to learning them individually [29]. Fig. 2 describes the principal
structure of the auto-encoder.

Data preparation: As our pretexts are pair-based, the pair-based data is to be
prepared for processing. The pair-specific features are obtained by the direct
concatenation of feature vector of nodes $u$ and $v$,
${X_{u,v}^{self}=X_{u}^{self}}\|X_{v}^{self}$. For the neighboring
information, similar to the GNN-based solutions, an aggregation function,
$M\left(p_{u,v}\right)$, is defined to aggregate the local neighborhood
attribute information of $p_{u,v}$. There are multiple options for
aggregators. In the current solution,
$X_{u,v}^{agg}=X_{u}^{agg}\|X_{v}^{agg}$, which means pair aggregation is the
concatenation of the aggregated representation based on paired nodes. Detailed
discussion on aggregators can be found in Sec. 3.3.

Thus, the inputs for the autoencoder is $\\{X_{u,v}^{self},X_{u,v}^{agg}\\}\
\forall p_{u,v}\in E$.

Encoder: The encoder is on the right part of Fig. 2. The inputs of the encoder
are $X_{u,v}^{self}$ and $X_{u,v}^{agg}$ generated from the data preparation
process. Firstly, these two types of features pass the two dense layers
individually for processing. To prevent gradient disappearance and achieve
more stable performance, we adopt the “skip connection”, just like ResNet[9]
which skips one or more layers and concatenates the output from the front
layer to the back layer. The output of the two dense layers are concatenated
and enter the embedding layer.

Through enforcing the alignment of local relationships from paired self-
features and neighboring aggregated information, PairE learns a joint
embedding space from both sides simultaneously.

Decoder: The output of the two separated dense layers are $H^{self}$ and
$H^{agg}$, and the softmax activation function is used on the output to
reconstruct the probability distribution of $X_{u,v}^{self}$ and
$X_{u,v}^{agg}$. The original probability distributions of input features are
denoted as $P^{agg}$ and $P^{self}$, respectively, and the reconstructed
probability distributions are denoted as $Q^{agg}$ and $Q^{self}$. The
probability distribution of the $k$-th pair is calculated by Eq.(1).:

$\displaystyle Q_{k}^{self}(i)=\exp{\left(H^{self}_{k}(i)\right)}/$
$\displaystyle\sum_{j\ \in\ F}\exp{\left(H^{self}_{k}(j)\right)}$ (1)
$\displaystyle k\ \in\ E,i\ \in\ F$

Where, $Q_{k}^{self}(i)$ indicates the $i^{th}$ feature’s distribution
possibility. It is calculated by applying the standard exponential function to
each element $H^{self}_{k}(i)$ and the normalized values are divided by the
sum of all these exponents. $Q^{agg}$ is calculated in the same way.

The multi-self-supervised auto-encoder has several advantages: Firstly, the
data are processed in pairs, and therefore the relationships between nodes are
explicitly learned. Secondly, the multi-task processing is realized by
training two learning tasks parallelly with a shared embedding layer, and
therefore pair content and local neighboring are preserved simultaneously.
Meanwhile, the generalization achieved by using the domain-specific
information contained for related tasks in training signals is improved.
Thirdly, the two learning tasks are mutual-supported since a pair’s self-
features and its surrounding features are mutual-correlated. The impacts of
the corruption or missing certain features can be partially mitigated.

### Aggregator

As shown in the previous section, the inputs of the proposed model depend on
the aggregation operations M that produce the aggregated features from a pair’
respective neighboring nodes. For the pair $p_{u,v}$, the aggregated features
are the concatenation of the nodes $u$ and $v$’s aggregated features. For the
aggregation of node features, many existing solutions have been proposed,
e.g., mean, max, LSTM aggregator proposed in GraphSAGE [7] or the sum
aggregator in GIN [21]. Here, the mean aggregator is adopted as it displays
the most stable performance on almost tested datasets. Features of node $u$’s
neighbors are aggregated with the element-wise MEAN of the feature vector, as
shown in Eq.(2).

$\displaystyle X^{agg}_{u,v}\leftarrow Concat($ $\displaystyle M(X_{i},\forall
i\in N(u)),$ (2) $\displaystyle M(X_{j},\forall j\in N(v)))$

Where, $i$, $j$ indicate the neighbors for the paired node $u$ and $v$,
respectively. We currently define nodes within a node’s 1-hop neighborhood.
This operation can also be performed iteratively, similar to the aggregation
operations often used in many GNN solutions.

### Learning embedding

In order to make the learned embedding representation to recover the original
input features as comprehensively and effectively as possible, the Kullback-
Leibler (KL) divergence is used to measure the asymmetry of the difference
between the two the original probability distribution $P$ and the
reconstructed probability distribution $Q$. Therefore, the goals of the two
tasks are to minimize the KL divergence between $P^{self}$ and $Q^{self}$,
$P^{agg}$ and $Q^{agg}$, respectively.

$\displaystyle\operatorname*{arg\,min}$ $\displaystyle({\rm KL}_{agg})=$ (3)
$\displaystyle Min\sum_{i\ \in\ E}\sum_{j\ \in\
F}{P^{agg}_{i}\left(j\right)\ln(\frac{P^{agg}_{i}(j)}{Q^{agg}_{i}(j)})}$
$\displaystyle\operatorname*{arg\,min}$ $\displaystyle({\rm KL}_{self})=$ (4)
$\displaystyle Min\sum_{i\ \in\ E}\sum_{j\ \in\
F}{P^{self}_{i}\left(j\right)\ln(\frac{P^{self}_{i}(j)}{Q^{self}_{i}(j)})}$

It is worthy to note that rather than making pairs “close” in the topology of
the graph to have “close” representation in the embedding spaces, our solution
encodes the pairs with similar features and surrounding contexts to have
“close” embeddings. Thus, it is possible for two pairs with similar embeddings
are far way in the graph. Even in our solution, only the pairs constructed by
1-hop neighbors are trained, the designed encoder is capable of capturing a
certain degree of global similarities.

### Translator

As defined in definition 4, to support node-related downstream tasks, e.g.,
node classification and node clustering, a permutation-free translator
function is needed to translate pair embedding to node embeddings. Similar to
the aggregation function, several operations can be used: min, max, mean, and
sum. For instance, if the sum operation is adopted, the embedding of node $u$
is the sum of pair embedding with $u$ as a starting point as shown in Eq 5.
Sec. Results and Analysis compares the performances of different types of
translators regarding node classification tasks.

$z_{u}={Sum}\left(Z_{u,v}\right)$ (5)

### Computation complexity

According to Fig.2, the space-time complexity of PairE mainly relies on the
number of pairs $|E|$, and the dimension of learned pair features $d$. In the
data preparation section, for a given pair p, we only aggregate the
characteristics of the first-order neighbors of nodes u and v. Therefore, the
time complexity and the space complexity are expressed as $O(|E|)$,
$O(F\cdot|E|)$, respectively. Next, we discuss the complexity of neural
network computation, every pair is calculated O(epoch) times, then the total
computational complexity here is $O(epoch\cdot|E|)$ and the space complexity
corresponding to embedding vectors is $O(d\cdot|E|)$, which the dimension of
embedding vector. For the translator, the time complexity is expressed as
$O(|E|)$. Thus, PairE has an overall time complexity of
$O(|E|+epoch\cdot|E|+|E|)$ and the space complexity of
$O(F\cdot|E|+d\cdot|E|)$

## Experiments

The performances of PairE are tested on both link-related tasks and node-
related tasks to answer the following questions:

  * •

whether PairE, from experimental perspective, can encode important pairwise
information in its embeddings ?

  * •

whether the pair-based embeddings can be effectively translated for downstream
node-related tasks while keeps the multiple roles played by one node?

### Datasets

To investigate the learning ability of PairE towards the complex structures
from graphs in different application domains, a variety of the real-world
graph datasets from benchmarks are selected, i.e. three wildly used citation
datasets Cora, CiteSeer, and Pubmed111https://linqs.soe.ucsc.edu/data with one
graph, as well as two biological data set with many sub-graphs: Proteins(short
for Proteins_full) [11] and PPI(protein-protein interaction). Those datasets
are selected for evaluation due to their popularity and the general
performance of different methods was well demonstrated in the existing
literature. Especially, PPI is a multi-label graph. Each protein might have
multiple roles in the graph. Table 1 shows their basic properties.

Table 1: Basic features of compared datasets Dataset | Nodes | Edges | Attrs | Classes
---|---|---|---|---
Cora | 2708 | 5429 | 1433 | 7
Citeseer | 3327 | 4732 | 3703 | 6
Pubmed | 19717 | 88651 | 500 | 3
Proteins | 43471 | 81044 | 29 | 3
PPI | 56944 | 818716 | 50 | 121

### Baseline models

In terms of node classification and node clustering, the PairE is compared
with several state-of-the-art unsupervised baselines and two semi-supervised
baselines: DeepWalk[14], the first approach for learning latent
representations of vertices in a network with NLP.

TADW[22], a representative factorization-based approach that incorporates node
content features via inductive matrix factorization.

SINE[26], a network embedding algorithm with good capability for missing
attributes in an incomplete graph; NodeE, is selected for the ablation study.
It works on the node level embedding with the same multi-self-supervised auto-
encoder as PairE.

ProNE [27]: is a network embedding algorithm approach based on matrix
factorization without node features. It enhanced the embeddings by propagating
them in the spectrally modulated space.

GraphSAGE [7], an inductive framework that leverages node feature information
to generate node embeddings for previously unseen data; Here, the mean
aggregator is used.

DGI [18], a contrastive self-supervised approach via maximizing mutual
information between patch representations and corresponding high-level
summaries of graphs. A variant of DGI-GCN is used due to its superior
performance.

The implementation of ProNE, SINE are from Karateclub
[15]222https://github.com/benedekrozemberczki/karateclub, and GraphSage, DGI
algorithm are from stellargraph
[4]333https://github.com/stellargraph/stellargraph. These implementations have
matching with or even better performance than the original paper. The
implementations of DeepWalk and TADW are from their corresponding projects on
Github.

Table 2: Averaged ROC AUC values for Link prediction and Pairwise node classification tasks, values before / is for Link prediction and after for Pairwise node classification. Name | Cora | Citeseer | Pubmed | Proteins
---|---|---|---|---
DeepWalk | .8117/.8057 |  .8193/.7296 | .7995/.7201 |  .9310/.5411
TADW | .6591/.7526 | .6925/.7026 | .7054/.7350 | .5090/.7530
SINE | .7184/.8199 | .7671/.7367 | .7147/.7274 | .7491/.6207
ProNE |  .8475/.8090 | .8294/.7334 | .8371/.7626 | .9226/.5544
GraphSAGE | .8286/.8341 | .7902/.7169 |  .8648/.7193 | .8469/.6012
DGI-gcn | .6701/.8261 | .6725/.6804 | .7609/.7468 | .4751/.5788
PairE |  .9250/.8607 |  .9157/.7554 |  .9499 /.7926 |  .9352/.6003
Table 3: Node classification results for compared datasets, evaluated with average Micro-F1. Analogous trends hold for averaged Macro-F1 scores. Values for PPI are for the multi-label node classification task. Name | Cora | Citeseer | Pubmed | PPI
---|---|---|---|---
Ratio | 30% | 50% | 70% | 30% | 50% | 70% | 30% | 50% | 70% | 30% | 50% | 70%
DeepWalk | .8005 | .7939 | .8237 | .5602 | .5809 | .5907 | .7980 | .8016 | .7994 | .5283 | .5375 | .5433
TADW | .8202 | .8391 | .8475 | .7145 | .7336 | .7410 | .8155 | .8230 | .8289 | .4780 | .4905 | .4768
ProNE | .7747 | .7968 | .8137 | .5431 | .5550 | .5730 | .7858 | .7952 | .7970 | .5419 | .5501 | .5419
SINE | .7674 | .7740 | .7831 | .6263 | .6434 | .6727 | .8546 | .8683 | .8698 | .5046 | .5194 | .5013
GraphSAGE | .8018 | .8361 | .8290 | .7296 | .7337 | .7362 | .8382 | .8437 | .8383 | .6697 | .6642 | .6615
DGI-GCN | .8128 | .8257 | .8337 | .6894 | .6963 | .7126 | .8311 | .8328 | .8329 | .9567 | .9565 | .9618
PairE | .8651 | .8692 | .8728 | .7535 | .7492 | .7496 | .8857 | .8793 | .8828 | .9825 | .9834 | .9828

### Experimental setup

The link-related task including link prediction and pairwise node
classification tasks. The link prediction task is a classical problem for the
graph to predict whether a given edge which does not exist or will appear in
the future. The pairwise node classification task predicts whether a pair of
nodes belong to the same community/class and used in [24]. The node-related
tasks include both the widely used node classification task and the node
clustering task.

Inductive learning for link-related tasks We use a similar prepossessing step
in [6], which first employs the graph embedding method in the link prediction
task. We first remove 20% edges from the original network randomly while
maintaining graph connectivity. The edges in the residual network are treated
as positive samples in the training set and the removal edges are treated as
positive samples for the test sets. We sample node pairs that are not
connected in the residual network as negative training samples, and node pairs
that are not connected in the origin network as negative test samples. In the
corresponding set, the negative samples are with the same numbers of the
positive ones. Note that we do not allow the model to observe ground-truth
graphs at the training time. For the pairwise node classification task, we use
the setting in P-GNN [24] to predict whether a pair of nodes belong to the
same community/class. Due to the fact that there is lack of well-accepted
setting for multi-label pairwise node classification. PPI is not used for
link-related tasks.

Transductive setting for node-related tasks In the node-related tasks, the
transductive setting is adopted. During the embedding process, all the nodes
are used in the embedding generation processes. The embeddings of vertices
from different solutions are taken as the features to train classifiers with
different training ratios, from 30%, 50% to 70%, and classification accuracy
is evaluated with remaining data. For the node clustering task, node
representations learned by different solutions are fed into the K-means
clustering algorithm, and the respective categories are grouped with the
K-means algorithm. The average accuracy (ACC) and Normalized Mutual
Information(NMI) values are used for evaluation.

Experiment settings These embedding methods are all node-based, and thus we
need to generate vectors for edges according to the embedding vectors of its
source node and the target node. Here, the approaches in Node2Vec [6] with
Hadamard product of the two vectors are not appropriate as it generates the
same vector for pair (u, v) and (v, u) given the embedding vectors of u and v.
Thus, we concatenate the embedding vectors of u and v to generate the vector
representation of pair. The embedding dimension of both pair embeddings in
PairE and node embeddings for other baselines are all set to 128. Other
parameters are set as the default settings in the corresponding paper. For the
PairE, we set epoch 30 and batch size 1024. A classifier with Logistic
Regression (LR) algorithm is used with the one-vs-rest strategy. we report
results over 10 runs with different random seeds and train/validation splits
and the averaged ROC AUC/Micro-F1 score is reported. We fix model
configurations across all the experiments. Details for experiment settings are
provided in the Appendix.

### Results and Analysis

#### Link prediction

For the link prediction task, two nodes generally more likely to form a link,
if match the neighboring pattern existed in the graph. This neighboring
pattern can be whether they are close together or their features have certain
matches. Therefore, the task can largely benefit from pair-wise embeddings.
Results for the link prediction task are reported in Tab. 2. We observe that
Pair-E significantly outperforms other strong baselines across all datasets
over other baselines. For instance, it improves ROC AUC score by up to
40.3/12.6% over the best/worst compared baseline in Cora and 36.2/11.7% in
Citeseer and 34.6/11.0% in Pubmed. These results clearly show that PairE
benefits from preserving the pair structure of the graphs. For the Proteins
with many sub-graphs, The deepwalk based on the random walk strategy is
conducive to capturing sub-graph information, so it performs outstandingly on
the dataset.

#### Pairwise node classifications

For this task, it is important to model the relationship between two connected
nodes. Thus solutions that focus on learning node-view structure-aware
embeddings will not perform well in these tasks.

Tab. 2 summarizes the performance of all the compared solutions. In all the
well-studied citation datasets, PairE maintains considerable advantages over
other baselines. The only exception is Proteins. This dataset contains many
sub-graphs. TADW, based on the matrix factorization techniques, is comparably
easy to catch this sub-graph information.

#### Node classification

This task is a well-adopted node-based task. However, as shown in Tab. 3, even
some strong baselines are up-to-date, PairE outperforms by a significant
margin in four tested datasets. Moreover, PairE achieves very stably
performance within all training ratio ranges across different datasets, even
for the well-adopted three citation datasets. Specifically, in the multi-
labeled PPI dataset, PairE achieves the averaged F1 score to 0.98 range, up to
100% relative performance improvement. It shows that PairE can capture
multiple roles played by individual nodes. It is very important for many graph
analysis tasks.

Furthermore, PairE shows more significant performance advantages when the
training ratio is small. This fact clearly shows that the manifold obtained by
PairE is much clearer and much easier to be learned by classifier than other
baselines. Thus, the classifier can learn a model with a small portion of the
embeddings.

#### Node clustering

As a complement to node classification, node clustering experiments are
conducted to examine the embedding quality from other perspectives. Due to
pape limits, only results for Cora and Citeseer are reported in Tab. 4. It is
easy to see that PairE achieves the best performance in terms of both metrics
with a considerable edge. Similar performances have been achieved in other
datasets. Please refer to the Appendix for details.

Table 4: Node Clustering Results on Cora and Citeseer Name | Cora | Citeseer
---|---|---
Metrics | NMI | ACC | NMI | ACC
DeepWalk | .3259 | .4025 | .1960 | .3309
TADW | .4759 | .6027 | .3711 | .5987
SINE | .4858 | .6861 | .3519 | .6186
GraphSAGE | .5142 | .6961 | .3770 | .6299
DGI-GCN | .5504 | .6913 | .3576 | .6087
PairE | .5585 | .7149 | .4251 | .6501

### Comparisons of translators

In this section, the performance impacts of different translators in PairE,
i.e. sum, mean, max and min, are analyzed and evaluated based on the node
classification task.

(a) Cora

(b) CiteSeer

Figure 3: Translators comparisons on Cora and Citeseer with different
trainning ratios

As can be seen from Fig. 3, the sum translator generally achieves the best
performance, among the four compared translators. The sum translator performs
the embedding accumulation of all pairs starting from the node. To some
extent, the “sum” translator keeps certain information on the number of
connected edges. This peculiar feature might explain its comparably better
performance. The other three have comparably unstable performance. For
instance, the “mean” translator performs well in the Cora dataset while
relatively poor in the CiteSeer dataset. However, what operation should be
used to best translate pair embeddings to node embeddings with minimal
information loss remains a largely unexplored area and could be an interesting
direction for future work.

## Conclusion

The real-world networks usually contain complex relationships between nodes,
even in many so-called homogeneous networks. In order to preserve that
relationship information as much as possible, this paper proposes a novel
multi-self-supervised auto-encoder, so-called PairE, that is able to learn
graph embeddings from pair-view so as to avoid the information loss inevitably
occurred in the node-view embedding approaches. The seamless integration of
node self-features and nearby structural information is achieved with shared
layers in the multi-task auto-encoder design. We also design a systematic
approach to translate pair embeddings to node embeddings for node-related
graph analysis tasks. Four types of downstream tasks, including both link-
related and node-related tasks, are tested for validation. Extensive
experiments show that PairE outperforms strong baselines in all those tasks
with significant edges.

## References

  * [1] Sambaran Bandyopadhyay, Anirban Biswas, M Narasimha Murty, and Ramasuri Narayanam.  Beyond node embedding: A direct unsupervised edge representation framework for homogeneous networks.  arXiv preprint arXiv:1912.05140, 2019.
  * [2] Jørgen Bang-Jensen and Gregory Z Gutin.  Digraphs: theory, algorithms and applications.  Springer Science & Business Media, 2008.
  * [3] Peng Cui, Xiao Wang, Jian Pei, and Wenwu Zhu.  A survey on network embedding.  IEEE Transactions on Knowledge and Data Engineering, 31(5):833–852, 2018.
  * [4] CSIRO’s Data61.  Stellargraph machine learning library.  https://github.com/stellargraph/stellargraph, 2018.
  * [5] Alessandro Epasto and Bryan Perozzi.  Is a single embedding enough? learning node representations that capture multiple social contexts.  In The World Wide Web Conference, pages 394–404, 2019.
  * [6] Aditya Grover and Jure Leskovec.  node2vec: Scalable feature learning for networks.  In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855–864, 2016.
  * [7] Will Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  In Advances in neural information processing systems, pages 1024–1034, 2017.
  * [8] William L Hamilton, Rex Ying, and Jure Leskovec.  Representation learning on graphs: Methods and applications.  arXiv preprint arXiv:1709.05584, 2017.
  * [9] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [10] Fenyu Hu, Yanqiao Zhu, Shu Wu, Weiran Huang, Liang Wang, and Tieniu Tan.  Graphair: Graph representation learning with neighborhood aggregation and interaction.  arXiv preprint arXiv:1911.01731, 2019.
  * [11] Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Mutzel, and Marion Neumann.  Benchmark data sets for graph kernels, 2016.
  * [12] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  arXiv preprint arXiv:1609.02907, 2016.
  * [13] Weiyi Liu, Zhining Liu, Toyotaro Suzumura, and Guangmin Hu.  Sane: Scalable attribute-aware network embedding.  2018\.
  * [14] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena.  Deepwalk: Online learning of social representations.  In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701–710, 2014.
  * [15] Benedek Rozemberczki, Oliver Kiss, and Rik Sarkar.  Karate Club: An API Oriented Open-source Python Framework for Unsupervised Learning on Graphs.  In Proceedings of the 29th ACM International Conference on Information and Knowledge Management (CIKM ’20). ACM, 2020.
  * [16] Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei.  Line: Large-scale information network embedding.  In Proceedings of the 24th international conference on world wide web, pages 1067–1077, 2015.
  * [17] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  arXiv preprint arXiv:.10903, 2017.
  * [18] Petar Veličković, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm.  Deep graph infomax.  arXiv preprint arXiv:1809.10341, 2018.
  * [19] Changping Wang, Chaokun Wang, Zheng Wang, Xiaojun Ye, and Philip S Yu.  Edge2vec: Edge-based social network embedding.  ACM Transactions on Knowledge Discovery from Data (TKDD), 14(4):1–24, 2020.
  * [20] Daixin Wang, Peng Cui, and Wenwu Zhu.  Structural deep network embedding.  In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1225–1234, 2016.
  * [21] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?  arXiv preprint arXiv:1810.00826, 2018.
  * [22] Cheng Yang, Zhiyuan Liu, Deli Zhao, Maosong Sun, and Edward Chang.  Network representation learning with rich text information.  In Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015.
  * [23] Hong Yang, Shirui Pan, Ling Chen, Chuan Zhou, and Peng Zhang.  Low-bit quantization for attributed network representation learning.  In Twenty-Eighth International Joint Conference on Artificial Intelligence IJCAI-19. International Joint Conferences on Artificial Intelligence Organization, 2019.
  * [24] Jiaxuan You, Rex Ying, and Jure Leskovec.  Position-aware graph neural networks.  arXiv preprint arXiv:1906.04817, 2019.
  * [25] Daokun Zhang, Jie Yin, Xingquan Zhu, and Chengqi Zhang.  Network representation learning: A survey.  IEEE transactions on Big Data, 2018.
  * [26] Daokun Zhang, Jie Yin, Xingquan Zhu, and Chengqi Zhang.  Sine: Scalable incomplete network embedding.  In 2018 IEEE International Conference on Data Mining (ICDM), pages 737–746. IEEE, 2018.
  * [27] Jie Zhang, Yuxiao Dong, Yan Wang, Jie Tang, and Ming Ding.  Prone: fast and scalable network representation learning.  In Proc. 28th Int. Joint Conf. Artif. Intell., IJCAI, pages 4278–4284, 2019.
  * [28] Yizhou Zhang, Guojie Song, Lun Du, Shuwen Yang, and Yilun Jin.  Dane: Domain adaptive network embedding.  arXiv preprint arXiv:1906.00684, 2019.
  * [29] Yu Zhang and Qiang Yang.  A survey on multi-task learning.  arXiv preprint arXiv:1707.08114, 2017.