Cross-Network Learning with Partially Aligned Graph Convolutional Networks

We study on two types of graphs and related tasks about learning, classifying, or predicting links between nodes.

For example, collaboration networks are weighted graphs. The weight is the frequency of collaborations between two person nodes. So, it is a positive integer when the link exists. The task of link prediction is to predict whether the value of $w(u_{i},u_{j})$ is positive or what the value is, given a pair of nodes $u_{i},u_{j}\in\mathcal{U}$.

Knowledge graphs are typical relational graphs, where the relational links need to be learned and completed. The task of relation classification is to predict the type of relation between two nodes (i.e., entities) $u_{i},u_{j}$ from the relation schema $\mathcal{R}$ so that a link $e=(u_{i},u_{j},r)$ is likely to exist in the graph.

The fundamental problem of both tasks is node representation learning that learns low-dimensional vectors of nodes to preserve the graph’s information. Take link prediction as an example – formally, it is to learn a mapping function: $\vec{u}=f(u,\mathcal{G},\Theta)\in\mathbb{R}^{d}$, where $\Theta$ is the node representation learning model’s parameters and $d$ is the number of dimensions of node representations. Then the value of $w(u_{i},u_{j})$ is assigned as $\sigma(\vec{u_{i}}^{\top}\vec{u_{j}})$, where $\sigma$ is sigmoid. Simple predictive functions can be specified for the other two tasks.

Graph convolutional network (GCN) is one of the most popular models for node representation learning (Kipf and Welling, 2017). Let us continue using link prediction as the example. We denote the number of nodes in graph $\mathcal{G}$ by $n=|\mathcal{U}|$. Suppose $A\in\mathbb{R}^{n\times n}$ is the adjacency matrix of $\mathcal{G}$ and $X\in\mathbb{R}^{n\times m}$ has the nodes’ raw attribute values, where $m$ is the number of the raw attributes. A two-layer GCN generates the matrix of node representations as follows:

where $\Theta=\{W_{(1)}\in\mathbb{R}^{m\times d},W_{(2)}\in\mathbb{R}^{d\times d}\}$ has layer-specific weight matrices. We choose two layers as most of existing studies suggest. The pre-processing step includes (1) $\tilde{A}=A+I_{n}$, (2) $\tilde{D}_{ii}=\sum_{j}\tilde{A}_{ij}$, and (3) $\hat{A}=\tilde{D}^{\frac{1}{2}}~{}\tilde{A}~{}\tilde{D}^{\frac{1}{2}}$. Graph reconstruction is used to inform the GCN to learn $\Theta$ to generate effective $U$:

The loss function can be written as follows:

where $\vec{u_{i}}$ and $\vec{u_{j}}$ are the $i$-th and $j$-th rows in matrix $U$. It is worth noting that one can easily extend our study from two-layer GCN to $l$-layer GCN ($l>2$).

One GCN can be built for one graph. What if we have multiple graphs which overlap each other to perform the same type of tasks? The overlapping parts, referred as network alignment serve as bridge for transferring knowledge across multiple GCNs so that they can mutually enhance each other. Without loss of generality, we focus on the cases that have two graphs $\mathcal{G}^{[A]}$ and $\mathcal{G}^{[B]}$. We denote by $A^{[A,B]}\in{\{0,1\}}^{n_{A}\times n_{B}}$ the adjacency matrix of network alignment between the two graphs: $A^{[A,B]}_{ij}=1$, if node $u^{[A]}_{i}$ and node $u^{[B]}_{j}$ are aligned; where $n_{A}=|\mathcal{U}^{[A]}|$ and $n_{B}=|\mathcal{U}^{[B]}|$. Usually the graphs are partially aligned, leading to missing alignment links and the sparsity of the alignment matrix.

Recall that a two-layer GCN on graph $\mathcal{G}^{[A]}$ has parameters $\Theta^{[A]}=\{W^{[A]}_{1}\in\mathbb{R}^{m_{A}\times d_{A}},W^{[A]}_{2}\in\mathbb{R}^{d_{A}\times d_{A}}\}$. Same goes for graph $\mathcal{G}^{[B]}$.

Suppose $d_{A}\neq d_{B}$. None of the parameters can be directly shared.

Suppose $d_{A}=d_{B}$. The second-layer weight parameters can be shared: $W_{2}=W^{[A]}_{2}=W^{[B]}_{2}$. So, we can perform joint GCN training:

where $\alpha^{[A]}$ and $\alpha^{[B]}$ are per-graph weight of the training procedure. When we have two graphs, $\alpha^{[A]}+\alpha^{[B]}=1$.

Suppose $m_{A}=m_{B}$ and $d_{A}=d_{B}$. The weight parameters of both layers can be shared across GCNs. We omit the equation for space – it simply replaces $W^{[A]}_{(1)}$ and $W^{[B]}_{(1)}$ in Eq.(5) by $W_{(1)}$. However, the multiple graphs can hardly have the same raw attribute space. So, when $d=d_{A}=d_{B}$ but $m_{A}\neq m_{B}$, we assume that linear factorized components of $W^{[A]}_{(1)}$ and $W^{[B]}_{(1)}$ can be shared. We denote the shared component by $W_{(1)}\in\mathbb{R}^{\hat{m}\times d}$, where $\hat{m}=\mathrm{min}\{m_{A},m_{B}\}$ or a smaller value. Then the loss function of joint training is as follows:

where $Q^{[A]}\in\mathbb{R}^{m_{A}\times\hat{m}}$ and $Q^{[B]}\in\mathbb{R}^{m_{B}\times\hat{m}}$ are linear transformation matrices on raw feature spaces for aligning the first-layer weight parameter matrices.

When the number of graphs is two, we can perform alternatives to save one linear transformation matrix. Alternative 1 is to use $Q^{[A\rightarrow B]}\in\mathcal{R}^{m_{A}\times m_{B}}$ to align $\mathcal{G}^{[A]}$’s raw attribute space to $\mathcal{G}^{[B]}$’s:

And alternative 2 is to use $Q^{[B\rightarrow A]}\in\mathcal{R}^{m_{B}\times m_{A}}$ to align $\mathcal{G}^{[B]}$’s raw attribute space to $\mathcal{G}^{[A]}$’s.

The training strategy presented in the above section is joint training or referred as multi-task learning. The weights of the tasks, i.e., $\alpha^{[A]}$ and $\alpha^{[B]}$, are determined prior to the training procedure. The other popular training strategy is called pre-training, that is to define one task a time as the target task and all the other tasks as source tasks. Take the method of sharing $W_{(2)}$ as an example. The loss function of joint training was given in Eq.(5). Now if learning graph $\mathcal{G}^{[B]}$ is the target task, then learning graph $\mathcal{G}^{[A]}$ is the source task. The pre-training procedure has two steps. Their loss functions are:

Each step still minimizes Eq.(5): specifically, the first step uses $\alpha^{[A]}=1$ and $\alpha^{[B]}=0$; and the second step uses $\alpha^{[A]}=0$ and $\alpha^{[B]}=1$. The first step warms up the training of the shared $W_{(2)}$ on $\mathcal{G}^{[A]}$ so that the “fine-tuning” step on $\mathcal{G}^{[B]}$ can find more effective model parameters than starting from pure randomization. When the source and target are swapped, the two steps are swapped.

Besides sharing model parameters, an idea of bridging the gap between two GCNs is to align their output representation spaces. Given GCNs trained on two graphs $\mathcal{G}^{[A]}$ and $\mathcal{G}^{[B]}$, if two nodes $u^{[A]}_{i}$ and $u^{[B]}_{j}$ are aligned, we assume that their representations, $\vec{u}^{[A]}_{i}\in\mathbb{R}^{d_{A}}$ and $\vec{u}^{[B]}_{j}\in\mathbb{R}^{d_{B}}$ are highly correlated. For example, one named entity (person, location, or organization) in two different knowledge graphs should have very similar representations. The same goes for one researcher in two collaboration networks (as an investigators in projects or an author in papers).

We add the network alignment information as two types of regularization terms into the loss function. The first type is Hard regularization. It assumes that the aligned nodes have exactly the same representations in the two output spaces. This requires the two spaces to have the same number of dimensions: $d_{A}=d_{B}$. The term is written as:

The entire loss function is as below:

where $\beta$ is the weight of the regularization task.

The second type is Soft regularization which is designed for more common cases that $d_{A}\neq d_{B}$. It assumes that the aligned nodes’ representations from one GCN can be linearly transformed into the ones in the other GCN’s output space:

where $R^{[A\rightarrow B]}\in\mathbb{R}^{d_{A}\times d_{B}}$ is the transformation matrix. Note that $R^{[A\rightarrow B]}$ is treated as model parameters in the loss function.

When the two graphs are partially aligned, the network alignment information is usually sparse and incomplete. To address this issue, we treat the alignment information as a bipartite graph $\mathcal{G}^{[A,B]}$ and learn to reconstruct and complete the graph. Given the node representations $U^{[A]}\in\mathbb{R}^{n_{A}\times d_{A}}$ and $U^{[B]}\in\mathbb{R}^{n_{B}\times d_{B}}$, can we reconstruct the adjacency matrix of observed alignment data $\mathcal{G}^{[A,B]}$, i.e., $I^{[A,B]}\odot A^{[A,B]}\in\mathcal{R}^{n_{A}\times n_{B}}$, where $I^{[A,B]}$ is the indicator matrix of the observations? We introduce $R^{[A,B]}\in\mathbb{R}^{d_{A}\times d_{B}}$ and minimize the following optimization term:

The entire loss function optimizes on three graph reconstruction tasks ($\mathcal{G}^{[A]}$, $\mathcal{G}^{[B]}$, and $\mathcal{G}^{[A,B]}$), by replacing $h$ in Eq.(10) with the above equation. The learning procedure transfers knowledge across the three tasks to find effective representations $U^{[A]}$ and $U^{[B]}$.

Suppose we have $K>2$ GCNs. All the above methods (i.e., loss functions) can be easily extended from $2$ to $K$ GCNs. For example, the loss of joint multi-GCN training with shared $W_{2}$ can be written as below (extended from Eq.(5)):

And the loss of joint multi-GCN training with shared $W_{1}$ and $W_{2}$ can be written as below (extended from Eq.(6)):

When using the network alignment information, the soft regularization term is written as below (extended from Eq.(11)):

where $\gamma^{[i\rightarrow j]}$ is the regularization weight of aligning representation spaces between graphs $\mathcal{G}^{[i]}$ and $\mathcal{G}^{[j]}$.

The optimization term for alignment reconstruction and completion can be written as below (extended from Eq.(16)):

Schlichtkrull et al. proposed neural relational modeling that uses GCNs for relation classification on relational graphs (Schlichtkrull et al., 2018). The output node representations from two-layer GCN are given as below:

Clearly, it can be derived from Eq.(1) by making these changes:

• •

  The relational graph $\mathcal{G}_{rel}=\{\mathcal{U},\mathcal{E},\mathcal{R}\}$ is denoted as a three-way tensor $A\in{\{0,1\}}^{n\times n\times n_{R}}$, where $n=|\mathcal{U}|$ is the number of entity nodes and $n_{R}=|\mathcal{R}|$ is the number of relation types;

• •

  The model parameters are two three-way tensors:
  $\Theta=\{{W_{r,(1)}}|_{r\in\mathcal{R}}\in\mathbb{R}^{m\times d},{W_{r,(2)}}|_{r\in\mathcal{R}}\in\mathbb{R}^{d\times d}\}$;

• •

  $c_{r}$ controls the weight of relation type $r$.

Relation classification can be considered as relational link prediction if we apply the prediction on all the possible entity-relation triples. The full prediction matrix is:

where $D\in\mathbb{R}^{d\times d\times n_{R}}$ is a three-way core tensor. For each relation type $r$, $D_{:,:,r}$ is a $d\times d$-diagonal matrix. The loss function is below:

All the proposed methods for partially aligned GCNs in the previous sections can be applied here. The key differences are (1) a three-way tensor data for reconstruction and (2) additional parameters $D$.

The task of graph reconstruction is to use the node representations $U\in\mathbb{R}^{n\times d}$ to recover the adjacency matrix $A\in\mathbb{R}^{n\times n}$. With singular value decomposition, we have $A\simeq\hat{U}~{}\Sigma~{}\hat{U}^{\top}$, where $\hat{U}\in\mathbb{R}^{n\times\mathrm{rank}(A)}$ and $\Sigma$ is square diagonal of size $\mathrm{rank}(A)\times\mathrm{rank}(A)$. So, the loss function in Eq.(3) can be approximated as the squared loss:

where $B\in\mathcal{R}^{d\times\mathrm{rank}(A)}$. It transforms the $n\times n$ classification tasks (for link prediction) into $\mathrm{rank}(A)$ regression tasks.

We apply the theory of positive transfer in multi-task learning (MTL) (Wu et al., 2019) into cross-GCNs learning. If the cross-GCNs training improves over just training the target GCN on one particular graph, we say the source GCNs on other graphs transfer positively to the target GCN. (Wu et al., 2019) proposed a theorem to quantify how many data points are needed to guarantee positive transfer between two ReLU model tasks. By the above section, it is necessary to limit the capacity of the shared model parameters to enforce knowledge transfer. Here we consider $d=1$ and $m=m_{A}=m_{B}$ to align with the theorem in (Wu et al., 2019). We have a theorem for positive transfer between two one-layer GCNs that share the first-layer model parameters $W_{(1)}$:

Soft regularization: We transfer knowledge across two GCNs’ representation spaces by optimizing Eq.(10) where $h$ is specified as Eq.(11). The optimal solution is

So, if $\beta=0$, $U^{[A]\star}=\hat{U}^{[A]}\sqrt{\Sigma^{[A]}}$ may overfit the graph data $\mathcal{G}^{[A]}$; if $\beta\in(0,1]$, the information transferred from $\mathcal{G}^{[B]}$ via the alignment $A^{[A,B]}$, i.e., $A^{[A,B]}U^{[B]\star}R^{[A\rightarrow B]}$, can have positive impact on link prediction on $\mathcal{G}^{[A]}$.

Graph neural network (GNN) is a type of neural network that operates on graph structure to capture the dependence of graphs via message passing between the nodes of graphs (Zhang et al., 2020; Wu et al., 2020). Kipf et al. proposed graph convolutional networks that use a spectral graph convolution to capture the spatial dependency (Kipf and Welling, 2017). Velivckovic et al. considered the interaction between nodes in the graph convolution measured as graph attention weight (Veličković et al., 2017). Hamilton et al. implemented the graph convolution as an efficient aggregation and sampling algorithm for inductive node representation learning (Hamilton et al., 2017a).

Recently, GNN techniques have been applied for learning representations on relational graphs, specifically knowledge graphs (Sadeghian et al., 2019; Zhang et al., 2019c; Ren and Leskovec, 2020). Relational GNNs perform significantly better than conventional knowledge graph embeddings (Schlichtkrull et al., 2018). Most techniques suffer from the issue of data sparsity and our proposed methods address it with knowledge transfer across networks.

In this paper, we discussed weighted graph, relational graph, and bipartite graphs; however, heterogeneous graphs are ubiquitous and have unique essential challenges for modeling and learning (Wang et al., 2020; Luo et al., 2020; Liu et al., 2020; Wang et al., 2019a; Wang et al., 2019b). We have been seeing heterogeneous GNNs (Dong et al., 2017; Liu et al., 2018; Zhang et al., 2019b; Fu et al., 2020) and heterogeneous attention networks for graphs (Wang et al., 2019c; Yang et al., 2020; Hu et al., 2020a; Yao et al., 2020; Hu et al., 2020b). Extending our proposed cross-network learning to heterogeneous graphs and enabling inductive learning in the framework are very important. These two points are out of the scope of our work but worth being considered as future directions.

The alignment of nodes between two or more than two graphs has been created and/or utilized in at least three categories of methods (Jiang et al., 2012, 2015; Vijayan and Milenković, 2017; Chen et al., 2017; Qin et al., 2020; Gu and Milenković, 2020). First, Kong et al. inferred anchor links between two social networks by matching the subgraphs surrounding the linked nodes (Kong et al., 2013). Emmert et al. wrote a comprehensive survey on the algorithms of graph matching (Emmert-Streib et al., 2016). Second, Zhang et al. used graph pattern mining algorithms for node alignment on incomplete networks (Zhang et al., 2017) and multi-level network (Zhang et al., 2019d). Nassar et al. leveraged the multimodal information for network alignment (Nassar and Gleich, 2017). The third line of work learned node representations and trained the supervised models with node pairing labels (if available) (Du et al., 2019; Ye et al., 2019; Nassar et al., 2018). A matrix factorization-based model has demonstrated that cross-network or cross-platform modeling can alleviate the data sparsity on a single platform (Jiang et al., 2016).