常用概念

交叉网络节点分类问题：给定一个全部标记或者部分标记的 source network 和 一个部分标记或者完全未标记的 Target network。希望利用 source network 的标记信息，辅助 Target network 节点的分类。如 Fig. 1 所示。
如果Target network中的节点完全未标记，这个问题为无监督学习；
如果Target network中的节点有部分被标记，这个问题为半监督学习。

交叉网络节点分类实例

1. 蛋白质网络分类。一些researcher发现了蛋白质相互作用网络，一个节点代表一个蛋白质，一条边代表两个蛋白质之间相互作用，并且已知每个蛋白质的Attribute，但是label未知。希望用其他相似或者相关网络的分类信息，实现网络数据上的迁移学习。
2. 引文网络节点分类。在每个数据库中都存在引文网络，一个节点代表一篇论文，一条边代表两篇论文之间存在引用关系，并且已知每篇论文的Attribute（可以将论文的key words或者Abstract中的单词作为Attribute），但是label未知（可以将论文所属类别作为label）。希望用其他数据库中引文网络的分类信息，实现网络数据上的迁移学习。

交叉网络节点分类面临的挑战

1. 在 source network 和 target network 间可能存在很大的不同，他们可能没有许多共同的 attribute。
2. 没有从 source network 到 target network间的 cross-network edge 传递信息。
3. 只有小部分 node 被标记。

Domain Adaptation
Domain Adaptation 是迁移学习（transfer learning）的一个子话题，旨在消除从source network 到 target network 知识迁移中 domian drift 的有害影响。

Adversarial-based method
Adversarial-based method 是 Domain Adaptation 中的一种方法。
Adversarial-based method 的基本思想（假设）：当算法无法识别给定的 representation 的域时，这种 representation 对于 knowledge transfer 是好的。

Network embedding
在网络中，对于每个节点学习一个低维嵌入向量。它可以保存嵌入空间的结构和性质的相似性，并且可以下游的机器学习任务，例如 node classification

Network Transfer Learning via Adversaria Domain Adaptation with Graph Convolution ——AdaGCN算法笔记

AdaGCN 基本思想

本文提出的新的网络转移学习框架 AdaGCN利用 adversarial domain adaptation 和 graph convolution，由两部分组成：

1. a semi-supervised learning component。在给定source network 和 target network 中 label 信息时，学习类别判断节点的表达。
2. an adversarial domain adaptation component。减缓邻域和目标域之间的分布差异，促进知识迁移。

Representation learner GCN作为生成器，学习域不变节点表示。Domain critic 作为判别器，来辨别 source network 和 target network 的节点表示。

AdaGCN 基本定义及符号说明

source network 和 target network 中可能包含不同的 attribute。 因此需要重构 feature matrix 。
记 X s \mathcal{X^s} Xs和 X t \mathcal{X^t} Xt分别为 G s G^s Gs和 G t G^t Gt中 node attribute 的集合。令 X = X s ∪ X t \mathcal{X}=\mathcal{X^s} \cup \mathcal{X^t} X=Xs∪Xt， C = ∣ X ∣ C= \vert \mathcal{X} \vert C=∣X∣ 为全部 attribute 的数量。重构 feature matrix： X s ∈ R n s × C X^s \in R^{n^s \times C} Xs∈Rns×C , X t ∈ R n t × C X^t \in R^{n^t \times C} Xt∈Rnt×C ， X i k r ( r ∈ { s , t } ) X^{r}_{ik} (r \in \{ s,t \}) Xikr​(r∈{s,t}) 代表在 G r G^r Gr 中 node i 的 第 k 个 attribute 数值。
在 source network 和 target network 之间存在 domain divergence ( D s ≠ D t ) (D^s \neq D^t) (Ds​=Dt)，但是 label space 相同 Y = { 1 , … , L } \mathcal{Y}=\{ 1, \dots, L \} Y={1,…,L} 相同。

AdaGCN 基本框架

在论文中AdaGCN的框架如下图所示。

我们将它简化以后，AdaGCN的框架如下。

1. 首先利用图卷积网络来整合 network topology 和 node attribute，用于学习网络表示。 本文采用了两种图卷积网络来学习 network representation。
   记 GCN 为
   H g r = f g ( A r , X r ; θ g ) ， r ∈ { s , t } H_g^r= f_g(A^r, X^r; \theta_g)， r \in \{ s,t \} Hgr​=fg​(Ar,Xr;θg​)，r∈{s,t}
   其中A为 adjacency matrix，X 为 feature matrix， θ g \theta_g θg​ , H g r H_g^r Hgr​ 为 output node representation。

   1. 在 feature extractor 中 第k个卷积层的 hidden representation 为
      H g ( k ) = σ ( A ^ H g ( k − 1 ) W g k ) H_g^{(k)}=\sigma (\hat{A} H_g^{(k-1)} W_g^{k} ) Hg(k)​=σ(A^Hg(k−1)​Wgk​)
      其中 A ^ \hat{A} A^ 为带有 self-loop 的 adjacency matrix。
      W g ( k ) W_{g}^{(k)} Wg(k)​ 为带有 trainable parameter 的 projection matrix。在网络中使用GCN 学习 node representation 时共享 ( W g ( k ) ) (W_{g}^{(k)}) (Wg(k)​)，以帮助网络间的知识迁移。
      σ ( ⋅ ) \sigma (\cdot) σ(⋅) 为**函数。
   2. improved GCN (IGCN) 。在 feature extractor 中 第k个卷积层的 hidden representation 为
      H g ( k ) = σ ( A ^ n I H g ( k − 1 ) W g k ) H_g^{(k)}=\sigma (\hat{A} ^{n_I} H_g^{(k-1)} W_g^{k} ) Hg(k)​=σ(A^nI​Hg(k−1)​Wgk​)
      其中 n I n_I nI​ 为 A ^ \hat{A} A^ 的指数，为平滑参数。

2. 然后将GCN学习到的 node representation 输入到 label prediction 的分类器中，形成半监督学习。
   Classifier 可以为单独的 logistic regression classifier 或者 multi-layer perception。记网络节点的预测值为 Y ^ r = f c ( H g r ; θ c ) , r ∈ { s , t } . \hat{Y}^r=f_c(H^r_g; \theta_c), r \in \{ s,t \}. Y^r=fc​(Hgr​;θc​),r∈{s,t}.
   Y ^ i , k r \hat{Y}_{i,k}^{r} Y^i,kr​ 代表 node i 在 class k 中的 prediction score。
   分类的 loss function 为 （cross-entropy error）：
   L c = − 1 n s l ∑ i = 1 n s l ∑ k = 1 L Y i k s l log ⁡ ( Y ^ i k s l ) L_c= -\frac{1}{n^{sl}} \sum_{i=1}^{n^{sl}} \sum_{k=1}^{L} Y_{ik}^{sl} \log (\hat{Y}_{ik}^{sl}) Lc​=−nsl1​i=1∑nsl​k=1∑L​Yiksl​log(Y^iksl​)
   其中 Y ^ s l \hat{Y}^{sl} Y^sl 为 labeled node V s l V^{sl} Vsl 的 prediction score matrix。
   则学习分类正确的节点表达可以化为 minimum problem:
   min ⁡ θ g min ⁡ θ c L c \min_{\theta_g} \min_{\theta_c} L_c θg​min​θc​min​Lc​

3. 同时采用 adversarial domain adaptation 技术，减少两个网络间的 distribution discrepancy。
   基本思想（假设）： 当一个算法不能判别给定的representation 的 domain 时，它们对于 domain 之间的知识转移是有利的。
   ——模仿GAN的思想（ f g ( A , X ; θ g ) f_g(A, X; \theta_g) fg​(A,X;θg​) ~ generator；domain critic ~ discriminator）
   网络结构： 使用全连接 neural network；input： node representation；output： real number；Denote： f d ( h ; θ d ) f_d(h; \theta_d) fd​(h;θd​)。
   loss function 为 两个网络分布 P h s P_{h^s} Phs​ 和 P h t P_{h^t} Pht​ 之间的 Wasserstein distance
   W 1 ( P h s , P h t ) = sup ⁡ ∥ f d ∥ L c ≤ 1 E P h s [ f d ( h ; θ d ) ] + E P h t [ f d ( h ; θ d ) ] W_1(P_{h^s}, P_{h^t})= \sup_{\Vert f_d \Vert_{L_c} \leq 1} E_{P_{h^s}} [f_d(h; \theta_d)] + E_{P_{h^t}} [f_d(h; \theta_d)] W1​(Phs​,Pht​)=∥fd​∥Lc​​≤1sup​EPhs​​[fd​(h;θd​)]+EPht​​[fd​(h;θd​)]
   其中 ∥ f d ∥ L c ≤ 1 \Vert f_d \Vert_{L_c} \leq 1 ∥fd​∥Lc​​≤1 为 Lipschitz continuity constraint。
   估计的 empirical Wasserstein distance 为
   L d = 1 n s ∑ i = 1 n s f d ( [ f g ( A s , X s ; θ g ) ] i ; θ d ) − 1 n t ∑ i = 1 n t f d ( [ f g ( A t , X t ; θ g ) ] i ; θ d ) L_d=\frac{1}{n^s} \sum_{i=1}^{n^s} f_d([f_g(A^s, X^s; \theta_g)]_i; \theta_d) - \frac{1}{n^t} \sum_{i=1}^{n^t} f_d([f_g(A^t, X^t; \theta_g)]_i; \theta_d) Ld​=ns1​i=1∑ns​fd​([fg​(As,Xs;θg​)]i​;θd​)−nt1​i=1∑nt​fd​([fg​(At,Xt;θg​)]i​;θd​)
   L g r a d ( h ) = ( ∥ ▽ h f d ( h ; θ d ) ∥ 2 − 1 ) 2 L_{grad}(h) =(\Vert \bigtriangledown_h f_d(h; \theta_d) \Vert_2 -1 )^2 Lgrad​(h)=(∥▽h​fd​(h;θd​)∥2​−1)2
   其中 L g r a d L_{grad} Lgrad​为估计的 Lipschitz constraint ，也就是 gradient penalty。
   则学习网络不变的节点表达可以化为 minimax problem:
   min ⁡ θ g max ⁡ θ d { L d − γ L g r a d } \min_{\theta_g} \max_{\theta_d} \{ L_d -\gamma L_{grad} \} θg​min​θd​max​{Ld​−γLgrad​}

4. 综上所述，总体损失函数可以写为
   min ⁡ θ g , θ c { L c + λ max ⁡ θ d { L d − γ L g r a d } } \min_{\theta_g, \theta_{c}} \{ L_c + \lambda \max_{\theta_d} \{ L_d - \gamma L_{grad} \}\} θg​,θc​min​{Lc​+λθd​max​{Ld​−γLgrad​}}
   具体训练过程如下图所示：
   训练过程先训练判别器再更新生成器&分类器，使用 full-batch training 和 gradient descent。并且在训练判别器时，使用构造了部分新样本。
   损失函数应该写为
   min ⁡ θ g { min ⁡ θ c { L c } + λ max ⁡ θ d { L d − γ L g r a d } } \min_{\theta_g} \{ \min_{\theta_c} \{L_c\} + \lambda \max_{\theta_d} \{ L_d - \gamma L_{grad} \}\} θg​min​{θc​min​{Lc​}+λθd​max​{Ld​−γLgrad​}}
   训练过程应该先同时训练判别器和分类器，然后再训练生成器（GCN）。

实验

在三个引文网络 DBLPv7，Citationv1 和ACMv9（视为无向网络）上进行知识迁移学习。

DANE: Domain Adaptive Network Embedding——DANE算法笔记

DANE 基本思想

解决的问题——Domain Adaptive Network Embedding。 设计一个网络嵌入算法，它可支持在不同网络上的转化下游模型。
具体而言：给定两个 domain compatible network G A G_A GA​ 和 G B G_B GB​，旨在以无监督的方式学习一个网络嵌入 f G : N A ∪ N B → R d f_G: N_A \cup N_B \to R^d fG​:NA​∪NB​→Rd，以支持从 G A G_A GA​ 到 G B G_B GB​ 以及 G B G_B GB​ 到 G A G_A GA​ 双向的 domain adaptation，并且可以用于下游的任务。

解决的方法： 提出一个无监督的网络嵌入框架 DANE，可以通过 GCN 和 adversarial learning 解决 embedding space drift 和 distribution drift 的问题。

1. 网络中的节点通过 Shared Weight Graph Convolution Network 被编码为向量，来取得图的嵌入空间平行，保存交叉网络节点对之间的结构相似性。
2. 使用了Adversarial Learning Regularization 来保证不同网络中嵌入向量分布的平行，

不是所有的网络对都可以进行双向的 domain adaptation。本文主要处理边为同质的，点的特征具有相似意义的网络。称这种网络为 domain compatible networks.

DANE 符号表示

定义

Domain Adaptation on Networks. Domain adaptation on networks 旨在通过最小化在 G s r c G_{src} Gsrc​ 上的 loss function 训练一个机器学习模型 M, 为下游任务服务。并且需要确保当我们将M迁移到 G t g t G_{tgt} Gtgt​ 上解决相同的问题时，M 的表现仍然很好。因此，需要满足如下两个约束：

• Embedding Space Alignment.
  将 G s r c G_{src} Gsrc​ 和 G t g t G_{tgt} Gtgt​ 的点投影到一个共享的嵌入空间 Z 中。 其中结构相似的点有相似的表达向量，即使它们来自于不同的网络，以致于 M 可在 G t g t G_{tgt} Gtgt​ 和 G s r c G_{src} Gsrc​ 之间转移。—— p ^ s r c ( z ∣ y ) \hat{p}_{src} (z \vert y) p^​src​(z∣y) 与 p ^ t g t ( z ∣ y ) \hat{p}_{tgt}(z \vert y) p^​tgt​(z∣y) 相近。

• Distribution Alignment.
  在 V s r c V_{src} Vsrc​ 和 V t g t V_{tgt} Vtgt​ 有相似的分布。—— p s r c ( z ) p_{src}(z) psrc​(z) 和 p t g t ( z ) p_{tgt}(z) ptgt​(z) 相近。

DANE 基本框架

DANE 框架如图所示

我们将它简化以后，DANE 的框架如下。

1. 首先使用 Shared Weight Graph Convolutional Network 对网络的拓扑结构和节点的 feature vector 进行整合，生成网络节点的表示向量。
   每一层的 representation 为
   H ( l + 1 ) = σ ( D ^ − 1 2 A ^ D ^ − 1 2 H ( l ) W l ) H^{(l+1)} = \sigma ( \hat{D}^{-\frac{1}{2}} \hat{A} \hat{D}^{-\frac{1}{2}} H^{(l)} W_l ) H(l+1)=σ(D^−21​A^D^−21​H(l)Wl​)
   其中 A ^ = A + I N \hat{A}=A+I_N A^=A+IN​； D ^ i i = ∑ j A ^ i j \hat{D}_{ii}=\sum_{j} \hat{A}_{ij} D^ii​=∑j​A^ij​； H ( 0 ) = X H^{(0)}=X H(0)=X； σ \sigma σ 为**函数； W l W_l Wl​ 为可学习参数，使用的 shared parameter set θ s = { W 1 , W 2 , …   } \theta_{s} =\{ W_1, W_2,\dots \} θs​={W1​,W2​,…}。
   使用 multi-task loss function：
   L g c n = L G s r c + L G t g t L_{gcn} = L_{G_{src}} + L_{G_{tgt}} Lgcn​=LGsrc​​+LGtgt​​
   其中 G s r c G_{src} Gsrc​ 代表在 source network 上的 loss function， G t g t G_{tgt} Gtgt​ 代表在 target network 上的 loss function。我们使用 LINE 中的 first-order loss function：
   L G = − ∑ ( i , j ) ∈ E log ⁡ σ ( v j ⋅ v i ) − Q ⋅ E k   P n e g ( N ) log ⁡ σ ( − v i ⋅ v k ) . L_G= - \sum_{(i,j) \in E} \log \sigma(v_j \cdot v_i) - Q \cdot E_{k~P_{neg} (N)} \log \sigma(-v_i \cdot v_k). LG​=−(i,j)∈E∑​logσ(vj​⋅vi​)−Q⋅Ek Pneg​(N)​logσ(−vi​⋅vk​).
   本文中没有具体解释这个公式，我认为这应该是图的无监督学习的一个 loss function。
2. Adversarial Learning Regularization。训练一个 discriminator 来辨别一个 embedding vector 来自哪里，并且训练 Shared Weight Graph Convolutional Network 来迷惑 discriminator。（ P ( v ∈ V s r c ∣ v = z ) P(v \in V_{src} \vert v=z) P(v∈Vsrc​∣v=z) 与 P ( v ∈ V t g t ∣ v = z ) P(v \in V_{tgt} \vert v=z) P(v∈Vtgt​∣v=z) 接近）
   网络结构： 在最后一层没有 activation function 的多层感知器。
   loss function：
   我们希望
   D ( x ) = { 0 x ∈ V s r c 1 x ∈ V t g t D(x)=\begin{cases} 0 & x \in V_{src}\\ 1 & x \in V_{tgt} \end{cases} D(x)={01​x∈Vsrc​x∈Vtgt​​
   因此 discriminator 的 loss function 为
   L D = E x ∈ V s r c [ ( D ( x ) − 0 ) 2 ] + E x ∈ V t g t [ ( D ( x ) − 1 ) 2 ] . L_D=E_{x \in V_{src}} [(D(x)-0)^2] + E_{x \in V_{tgt}} [(D(x)-1)^2] . LD​=Ex∈Vsrc​​[(D(x)−0)2]+Ex∈Vtgt​​[(D(x)−1)2].
   对抗训练的 loss function 为
   L a d v = E x ∈ V s r c [ ( D ( x ) − 1 ) 2 ] + E x ∈ V t g t [ ( D ( x ) − 0 ) 2 ] . L_{adv}=E_{x \in V_{src}} [(D(x)-1)^2] + E_{x \in V_{tgt}} [(D(x)-0)^2] . Ladv​=Ex∈Vsrc​​[(D(x)−1)2]+Ex∈Vtgt​​[(D(x)−0)2].
3. 综上所述，DANE 的全部 loss function （包括 GCN 的损失以及迷惑对抗训练的损失）为
   L = L g c n + λ L a d v . L=L_{gcn} + \lambda L_{adv} . L=Lgcn​+λLadv​.
   训练： 在每次迭代中，首先训练 k 步 discriminator， 优化 L D L_D LD​；接着训练 1 步 embedding model， 优化 L L L。

理论分析

说明嵌入空间和分布越平行，当 source network 点的分类误差很小时，target network 点的分类误差也会很小。

实验

实验中使用的数据集为 Paper Citation Network 和 Co-author Networks （collected from Aminer database [Tang, 2016]）。
我们在 node classification 的任务中测试 DANE，基于 L2-regularized logistic regression、SGD 算法和从 source network 中得到的 embedding 训练分类器，并且直接在 target network 中测试分类器的性能。
因为在训练 GCN 的时候 未使用到 target network 的 label 信息，DANE 的改进结果一般。
但是 DANE 可以作为一个不依赖于下游任务的图嵌入算法，更加具有灵活性。