CGNF: Conditional Graph Neural Fields
CGNF: Conditional Graph Neural Fields
CGNF Method
The CGNF Model
embedding还是按照经典的GCN model来
$$ H=f(X,A) = Softmax(\hat A ReLU (\hat A X W^0) W^1)
$$
这里有两个问题： 1. GCN的training过程中，node之间是conditionally independent 2. label correlation是忽略的
为了填补这个空白，我们将label correlation整合到GCN model。energy based model，比如CRF，可以很好的定义变量之间的依赖性。所以在一个general graph中，同时考虑node feature和label dependency，我们将energy function定义为
$$ E(Y,X,A) = Ec (Y_c, X_c, A) = \sum_i \psi (y_i, x_i) + \sum{(i,j) \in E} \phi (yi, y_j, A{ij})
$$
其中$$c$$是clique。$$\psi(\cdot), \phi(\cdot)$$分别是unary potential和pairwise potential。有了这个energy function，可以得到Gibbs distribution
$$ P(Y|X,A) = \frac{\exp(-E(Y, X, A))}{\sum_{Y'\in Y} \exp (-E(Y', X, A))} = \frac{\exp(-E(Y, X, A))}{Z(X,A)}
$$
其中$$E$$是energy function，是在相对应的clique中的relationship上的likelihood的indicator function。energy越大，likelihood越小。我们的目标就转换成了最大化conditional probability。
energy function可以改写为
$$ E(Y,X,A) = \sumi \psi(y_i, h_i) + \sum{(i,j) \in E} \phi (yi, y_j, \hat A{ij})
$$
其中 $$h_i$$是node i的embedding。如果将每一个node的energy分开来算，我们可以进一步地表达energy function （如下）：
$$ E(Y,X,A) = \sumi \Big( \psi(y_i, h_i) + \frac{\gamma}{2} \sum{j \in N(i)} \phi(yi, y_j, \hat A{ij}) \Big)
$$
我们将unary potential 定义为prediction loss，$$\psi(yi, h_i)$$。而pairwise potential 主要受到两个因素影响 1. normalized edge weights $$\hat A{ij}$$ 2. label correlation weights $$U_{y_i, y_j}$$ 两个potential function可以如下表示
$$ \psi(yi, h_i) = - \log p(y_i | h_i) = - \sum_k y{ik} \log h{i,k}\ \phi(y_i, y_j, \hat A{ij}) = -2 \hat A{ij} U{y_i, y_j}
$$
其中$$yi, y_j$$是对应的label。而$$U{y_i, y_j} \in U$$是learnable correlation/transition weight。
像一个传统的CRF，一个通常的做法是使用negative log likelihood作为objective function，来找到optimal parameter $$W^0, W^1, U$$
$$
- \log P(Y|X,A)\ = E(Y,X,A) + \log Z(X,A)\ = E(Y,X,A) + \log_{y'} (-E(Y', X, A)) $$
由这个式子可以得到$$P(Y|X,A) \propto \exp(-E(Y,X,A))$$(?)，所以可以等价于求解$$\min_Y E(Y,X,A)$$。
Parameter Optimization
上述的式子是computationally intractable，因此我们考虑使用有效的估算方法，pseudo likelihood method。pseudo likelihood方法提供了有效的joint distribution的估算。
$$ P(Y|X,A) \approx PL(Y|X,A) = \prodi P(y_i| y{N(i)}, X, A)
$$
pseudo likelihood的优势是在于它只需要normalizing over the possible labels at one node。可以有效减少normalizer的计算复杂度。
每一个点的conditional probability，给定neighborhood时，是如下计算
$$ P(yi|y{N(i)}, X, A) \ = \frac{\exp \big( -\psi(yi, h_i) - \gamma \sum{j \in N(i)} \phi(yi, y_j, \hat A{ij} ) \big)}{\sum{y'} \exp\big( -\psi(y_i', h_i) - \gamma \sum{j \in N(i)} \phi(yi', y_j, \hat A{ij} ) \big) }\ = \frac{\exp \big( -\log(yi|h_i) - 2\gamma \sum{j \in N(i)} \hat A{ij} U{yi, y_j} \big)}{\sum{y'} \exp\big( -\log(yi'|h_i) - 2\gamma \sum{j \in N(i)} \hat A{ij} U{y_i', y_j} \big) }
$$
因此有
$$
- \log PL(Y|X,A)\ = \sumi -\log P(y_i | y{N(i)}, X, A)\ = \sumi \big( \psi(y_i, h_i) + \sum{j \in N(i)} \phi(yi, y_j, \hat A{ij}) + \log \sum{y' \in Y} \exp \big( -\psi(y_i', h_i) - \phi(y_i', y_j, \hat A{ij}) \big) \big)\ = -\sum{i,j}(Y\odot H){i,k} - 2 \gamma \sum{i,j,i\ne j} (\hat A \odot (YUY^T)){i,j} + \sumi \log \sum_k (H \odot exp(2\gamma \hat A Y U)){i,k} $$
Inference of Test Labels for CGNF
当训练了model parameter之后，下一步就是对new label进行inference。可以这么操作
$$ \min{\hat Y{te}} E(\hat Y{te}, X, A, Y{tr}) = \min{\hat Y{te}} \big[ -\log p(\hat Y{te} | H) - \gamma \sum{i\ne j}(\hat A \odot(\hat Y U \hat Y^T))_{i,j} \big]
$$
tr表示train，te表示test。$$\hat Y = [Y{train}, \hat Y{test}]$$。为了找到最小值，我们要找到“最优”的test labels，但复杂度是exponential。这里我们使用两种inference方法来估计。
最简单的方法是不直接考虑test label之间的关系，而是使用training label来每一次推断一个test label。
$$ yi = \arg \min{yj} E(y_i, Y{tr}, X, A) = \arg \min{j}[-\log(h_i) - 2 \gamma \hat A{tr} Y U^T ]_j
$$
或者，可以用DP。随便选择一个test node作为起始点，然后随机排列其他的test node。然后沿着permuted test nodes的顺序进行beam search。重复T次，在所有T个beam search里面选择最好一个（根据energy）。
Inductive Learning Across Graphs
顺着GCN的框架，node classification认为就是一个semi-supervised learning task。但有时候我们会有几张图相互之间有所关联。这个时候就采用inductive learning for CGNF。与semi-supervised设定不同的是，inductive learning在training阶段是不知道test nodes。训练期间的目标函数没有变。
而test label的inference，因为我们不知道train nodes和test nodes之间的连接，所以training labels无法直接影响test label的inference。我们可以构造出一个adjacency matrix $$A$$，但是train nodes和test nodes之间的link都是0，potential function也是0。所以simplest inference方法不可用，而只能用DP。