FastGCN论文总结及实现(Tensorflow2.0)

 

 FastGCN论文总结及实现(Tensorflow2.0)

 

 


 

1.utils.py

import numpy as np
import pickle as pkl
import networkx as nx
import scipy.sparse as sp
from scipy.sparse.linalg.eigen.arpack import eigsh
import sys
from scipy.sparse.linalg import norm as sparsenorm
from scipy.linalg import qr
import math


def parse_index_file(filename):
    """Parse index file."""
    index = []
    for line in open(filename):
        index.append(int(line.strip()))
    return index


def sample_mask(idx, l):
    """Create mask."""
    mask = np.zeros(l)
    mask[idx] = 1
    return np.array(mask, dtype=np.bool)


def load_data(dataset_str):
    """Load data."""
    names = ['x', 'y', 'tx', 'ty', 'allx', 'ally', 'graph']
    objects = []
    for i in range(len(names)):
        with open("data/ind.{}.{}".format(dataset_str, names[i]), 'rb') as f:
            if sys.version_info > (3, 0):
                objects.append(pkl.load(f, encoding='latin1'))
            else:
                objects.append(pkl.load(f))

    x, y, tx, ty, allx, ally, graph = tuple(objects)
    test_idx_reorder = parse_index_file(
        "data/ind.{}.test.index".format(dataset_str))
    test_idx_range = np.sort(test_idx_reorder)

    if dataset_str == 'citeseer':
        # Fix citeseer dataset (there are some isolated nodes in the graph)
        # Find isolated nodes, add them as zero-vecs into the right position
        test_idx_range_full = range(
            min(test_idx_reorder), max(test_idx_reorder)+1)
        tx_extended = sp.lil_matrix((len(test_idx_range_full), x.shape[1]))
        tx_extended[test_idx_range-min(test_idx_range), :] = tx
        tx = tx_extended
        ty_extended = np.zeros((len(test_idx_range_full), y.shape[1]))
        ty_extended[test_idx_range-min(test_idx_range), :] = ty
        ty = ty_extended

    features = sp.vstack((allx, tx)).tolil()
    features[test_idx_reorder, :] = features[test_idx_range, :]
    adj = nx.adjacency_matrix(nx.from_dict_of_lists(graph))

    labels = np.vstack((ally, ty))
    labels[test_idx_reorder, :] = labels[test_idx_range, :]

    idx_test = test_idx_range.tolist()
    idx_train = range(len(ally)-500)
    idx_val = range(len(ally)-500, len(ally))

    train_mask = sample_mask(idx_train, labels.shape[0])
    val_mask = sample_mask(idx_val, labels.shape[0])
    test_mask = sample_mask(idx_test, labels.shape[0])

    y_train = np.zeros(labels.shape)
    y_val = np.zeros(labels.shape)
    y_test = np.zeros(labels.shape)
    y_train[train_mask, :] = labels[train_mask, :]
    y_val[val_mask, :] = labels[val_mask, :]
    y_test[test_mask, :] = labels[test_mask, :]

    return adj, features, y_train, y_val, y_test, train_mask, val_mask, test_mask


def load_data_original(dataset_str):
    """Load data."""
    names = ['x', 'y', 'tx', 'ty', 'allx', 'ally', 'graph']
    objects = []
    for i in range(len(names)):
        with open("data/ind.{}.{}".format(dataset_str, names[i]), 'rb') as f:
            if sys.version_info > (3, 0):
                objects.append(pkl.load(f, encoding='latin1'))
            else:
                objects.append(pkl.load(f))

    x, y, tx, ty, allx, ally, graph = tuple(objects)
    test_idx_reorder = parse_index_file(
        "data/ind.{}.test.index".format(dataset_str))
    test_idx_range = np.sort(test_idx_reorder)

    if dataset_str == 'citeseer':
        # Fix citeseer dataset (there are some isolated nodes in the graph)
        # Find isolated nodes, add them as zero-vecs into the right position
        test_idx_range_full = range(
            min(test_idx_reorder), max(test_idx_reorder)+1)
        tx_extended = sp.lil_matrix((len(test_idx_range_full), x.shape[1]))
        tx_extended[test_idx_range-min(test_idx_range), :] = tx
        tx = tx_extended
        ty_extended = np.zeros((len(test_idx_range_full), y.shape[1]))
        ty_extended[test_idx_range-min(test_idx_range), :] = ty
        ty = ty_extended

    # features (2708,1433)  labels (2708,7)
    features = sp.vstack((allx, tx)).tolil()
    features[test_idx_reorder, :] = features[test_idx_range, :]
    adj = nx.adjacency_matrix(nx.from_dict_of_lists(graph))

    labels = np.vstack((ally, ty))
    labels[test_idx_reorder, :] = labels[test_idx_range, :]

    idx_test = test_idx_range.tolist()
    idx_train = range(len(y))
    idx_val = range(len(y), len(y)+500)

    train_mask = sample_mask(idx_train, labels.shape[0])
    val_mask = sample_mask(idx_val, labels.shape[0])
    test_mask = sample_mask(idx_test, labels.shape[0])

    y_train = np.zeros(labels.shape)
    y_val = np.zeros(labels.shape)
    y_test = np.zeros(labels.shape)
    y_train[train_mask, :] = labels[train_mask, :]
    y_val[val_mask, :] = labels[val_mask, :]
    y_test[test_mask, :] = labels[test_mask, :]

    return adj, features, y_train, y_val, y_test, train_mask, val_mask, test_mask


def sparse_to_tuple(sparse_mx):
    """Convert sparse matrix to tuple representation."""
    def to_tuple(mx):
        if not sp.isspmatrix_coo(mx):
            mx = mx.tocoo()
        coords = np.vstack((mx.row, mx.col)).transpose()
        values = mx.data
        shape = mx.shape
        return coords, values, shape

    if isinstance(sparse_mx, list):
        for i in range(len(sparse_mx)):
            sparse_mx[i] = to_tuple(sparse_mx[i])
    else:
        sparse_mx = to_tuple(sparse_mx)

    return sparse_mx


def nontuple_preprocess_features(features):
    """Row-normalize feature matrix and convert to tuple representation"""
    rowsum = np.array(features.sum(1))
    r_inv = np.power(rowsum, -1).flatten()
    r_inv[np.isinf(r_inv)] = 0.
    r_mat_inv = sp.diags(r_inv)
    features = r_mat_inv.dot(features)
    return features


def preprocess_features(features):
    """Row-normalize feature matrix and convert to tuple representation"""
    rowsum = np.array(features.sum(1))
    r_inv = np.power(rowsum, -1).flatten()
    r_inv[np.isinf(r_inv)] = 0.
    r_mat_inv = sp.diags(r_inv)
    features = r_mat_inv.dot(features)
    return sparse_to_tuple(features)


def normalize_adj(adj):
    """Symmetrically normalize adjacency matrix."""
    adj = sp.coo_matrix(adj)
    rowsum = np.array(adj.sum(1))
    d_inv_sqrt = np.power(rowsum, -0.5).flatten()
    d_inv_sqrt[np.isinf(d_inv_sqrt)] = 0.
    d_mat_inv_sqrt = sp.diags(d_inv_sqrt)
    return adj.dot(d_mat_inv_sqrt).transpose().dot(d_mat_inv_sqrt).tocoo()


def nontuple_preprocess_adj(adj):
    """ 返回对称归一化的邻接矩阵 type:csr """
    adj_normalized = normalize_adj(sp.eye(adj.shape[0]) + adj)
    return adj_normalized.tocsr()


def column_prop(adj):
    """ detail reference:
    https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.linalg.norm.html#scipy.sparse.linalg.norm 
    等价于array形式:
    arr = np.array([[1, 4, 7],
                    [2, 5, 8],
                    [3, 6, 9]])
    column_norm = np.linalg.norm(arr, axis=0) 对每一列求二范数
    print column_norm
    >>> [ 3.74165739  8.77496439 13.92838828] => [sqrt(1^2+2^2+3^2)  sqrt(4^2+5^2+6^2) sqrt(7^2+8^2+9^2)]
    norm_sum = sum(column_norm) # 归一化
    print(column_norm/norm_sum) 
    >>> [0.14148822 0.33181929 0.52669249]
    """
    column_norm = sparsenorm(adj, axis=0)
    # column_norm = pow(sparsenorm(adj, axis=0),2)
    norm_sum = sum(column_norm)
    return column_norm/norm_sum


def mix_prop(adj, features, sparseinputs=False):
    adj_column_norm = sparsenorm(adj, axis=0)
    if sparseinputs:
        features_row_norm = sparsenorm(features, axis=1)
    else:
        features_row_norm = np.linalg.norm(features, axis=1)
    mix_norm = adj_column_norm*features_row_norm

    norm_sum = sum(mix_norm)
    return mix_norm / norm_sum


def preprocess_adj(adj):
    """Preprocessing of adjacency matrix for simple GCN model and conversion to tuple representation."""
    adj_normalized = normalize_adj(sp.eye(adj.shape[0]) + adj)
    return sparse_to_tuple(adj_normalized)


def dense_lanczos(A, K):
    q = np.random.randn(A.shape[0], )
    Q, sigma = lanczos(A, K, q)
    A2 = np.dot(Q[:, :K], np.dot(sigma[:K, :K], Q[:, :K].T))
    return sp.csr_matrix(A2)


def sparse_lanczos(A, k):
    q = sp.random(A.shape[0], 1)
    n = A.shape[0]
    Q = sp.lil_matrix(np.zeros((n, k+1)))
    A = sp.lil_matrix(A)

    Q[:, 0] = q/sparsenorm(q)

    alpha = 0
    beta = 0

    for i in range(k):
        if i == 0:
            q = A*Q[:, i]
        else:
            q = A*Q[:, i] - beta*Q[:, i-1]
        alpha = q.T*Q[:, i]
        q = q - Q[:, i]*alpha
        q = q - Q[:, :i]*Q[:, :i].T*q  # full reorthogonalization
        beta = sparsenorm(q)
        Q[:, i+1] = q/beta
        print(i)

    Q = Q[:, :k]

    Sigma = Q.T*A*Q
    A2 = Q[:, :k]*Sigma[:k, :k]*Q[:, :k].T
    return A2
    # return Q, Sigma


def dense_RandomSVD(A, K):
    G = np.random.randn(A.shape[0], K)
    B = np.dot(A, G)
    Q, R = qr(B, mode='economic')
    M = np.dot(Q, np.dot(Q.T, A))
    return sp.csr_matrix(M)


def construct_feed_dict(features, support, labels, labels_mask, placeholders):
    """Construct feed dictionary."""
    feed_dict = dict()
    feed_dict.update({placeholders['labels']: labels})
    feed_dict.update({placeholders['labels_mask']: labels_mask})
    feed_dict.update({placeholders['features']: features})
    feed_dict.update({placeholders['support'][i]: support[i]
                      for i in range(len(support))})
    feed_dict.update({placeholders['num_features_nonzero']: features[1].shape})
    return feed_dict


def chebyshev_polynomials(adj, k):
    """Calculate Chebyshev polynomials up to order k. Return a list of sparse matrices (tuple representation)."""
    print("Calculating Chebyshev polynomials up to order {}...".format(k))

    adj_normalized = normalize_adj(adj)
    laplacian = sp.eye(adj.shape[0]) - adj_normalized
    largest_eigval, _ = eigsh(laplacian, 1, which='LM')
    scaled_laplacian = (
        2. / largest_eigval[0]) * laplacian - sp.eye(adj.shape[0])

    t_k = list()
    t_k.append(sp.eye(adj.shape[0]))
    t_k.append(scaled_laplacian)

    def chebyshev_recurrence(t_k_minus_one, t_k_minus_two, scaled_lap):
        s_lap = sp.csr_matrix(scaled_lap, copy=True)
        return 2 * s_lap.dot(t_k_minus_one) - t_k_minus_two

    for i in range(2, k+1):
        t_k.append(chebyshev_recurrence(t_k[-1], t_k[-2], scaled_laplacian))

    return sparse_to_tuple(t_k)


def view_bar(message, num, total, loss, train_acc, val_acc, test_acc, times):
    rate = num / total
    rate_num = int(rate * 40)
    rate_nums = math.ceil(rate * 100)
    r = 'r%s:[%s%s]%d%%t%d/%d - loss:%.3f - train_acc:%.3f - val_acc:%.3f - test_acc:%.3f - time:%.2fs' % (message,
                                                                                                              "=" * rate_num,
                                                                                                              " " *
                                                                                                              (40 - rate_num),
                                                                                                              rate_nums,
                                                                                                              num,
                                                                                                              total,
                                                                                                              loss,
                                                                                                              train_acc,
                                                                                                              val_acc,
                                                                                                              test_acc,
                                                                                                              times)
    sys.stdout.write(r)
    sys.stdout.flush()

2.layers.py

import tensorflow as tf
from model.inits import *
from model.utils import *


def sparse_dropout(x, keep_prob, noise_shape):
    """Dropout for sparse tensors."""
    random_tensor = keep_prob
    random_tensor += tf.random.uniform(noise_shape)
    dropout_mask = tf.cast(tf.floor(random_tensor), dtype=tf.bool)
    pre_out = tf.sparse.retain(x, dropout_mask)
    return pre_out * (1./keep_prob)


def dot(x, y, sparse=False):
    """Wrapper for tf.matmul (sparse vs dense)."""
    if sparse:
        res = tf.sparse.sparse_dense_matmul(x, y)
    else:
        res = tf.matmul(x, y)
    return res


class Layer(object):
    def __init__(self, **kwargs):
        self.vars = {}

    def _call(self, params):
        """implement the layer operation """
        return params

    def __call__(self, params):
        outputs = self._call(params)
        return outputs


class Dense(Layer):
    def __init__(self, name, input_dim, output_dim, dropout=0.0,
                 sparse_inputs=False, act=tf.nn.relu, bias=False, **kwargs):
        super(Dense, self).__init__(**kwargs)
        self.name = name
        self.dropout = dropout
        self.act = act
        self.out_dim = output_dim

        # bool
        self.bias = bias
        self.sparse_inputs = sparse_inputs  # params['features'] sparse or not
        # define params
        self.vars['weight'] = glorot([input_dim, output_dim],
                                     name=self.name+'weight')
        if self.bias:
            self.vars['bias'] = zeros([output_dim],
                                      name=self.name+'bias')

    def _call(self, params):
        """params: features support """
        x = params['features']

        # dropout x
        if self.sparse_inputs:
            x = sparse_dropout(x, 1-self.dropout,
                               params['num_features_nonzero'])
        else:
            x = tf.nn.dropout(x, 1-self.dropout)

        output = dot(x, self.vars['weight'], sparse=self.sparse_inputs)

        if self.bias:
            output += self.vars['bias']
        return self.act(output)


class GraphConvolution(Layer):
    def __init__(self, name, input_dim, output_dim, dropout=0.0,
                 sparse_inputs=False, act=tf.nn.relu, bias=False, **kwargs):
        super(GraphConvolution, self).__init__(**kwargs)
        self.name = name
        self.dropout = dropout
        self.act = act
        self.out_dim = output_dim

        # bool
        self.bias = bias
        self.sparse_inputs = sparse_inputs  # params['features'] sparse or not

        # define params
        self.vars['weight'] = glorot([input_dim, output_dim],
                                     name=self.name+'weight')
        if self.bias:
            self.vars['bias'] = zeros([output_dim],
                                      name=self.name+'bias')

    def _call(self, params):
        x = params['features']
        support = params['support']
        # dropout x
        if self.sparse_inputs:
            x = sparse_dropout(x, 1-self.dropout,
                               params['num_features_nonzero'])
        else:
            x = tf.nn.dropout(x, 1-self.dropout)

        # x is sparse
        pre_sup = dot(x, self.vars['weight'],
                      sparse=self.sparse_inputs)  # x.dot(w)

        # support is sparse
        output = dot(support, pre_sup, sparse=True)  # Axw

        if self.bias:
            output += self.vars['bias']
        return self.act(output)

3.models.py

from model.layers import *
from model.metrics import *
import numpy as np


class Model(object):
    def __init__(self):
        self.vars = []
        self.layers = []

    def forward(self):
        raise NotImplementedError

    def _update(self):
        raise NotImplementedError

    def _loss(self):
        raise NotImplementedError


class GCN(Model):
    """ kipf & welling """

    def __init__(self, placeholders, sparse_inputs=False):
        super(GCN, self).__init__()
        self.input_dim = placeholders['in_dim']
        self.hid_dim = placeholders['hid_dim']
        self.output_dim = placeholders['out_dim']
        self.weight_decay = placeholders['weight_decay']
        self.dropout = placeholders['dropout']
        self.lr = placeholders['lr']
        self.sparse_inputs = sparse_inputs  # params['features'] sparse or not
        self.build()

    def build(self):
        """构建2 layer GCN, 并保存参数到vars中
           第一层需要sparse_inputs 如果features是sparse,则features x W 要sparsedot
           第二层不需要sparse_inputs 因为H0是dense的"""

        self.layers.append(GraphConvolution(name='GCN_0',
                                            input_dim=self.input_dim,
                                            output_dim=self.hid_dim,
                                            dropout=self.dropout,
                                            act=tf.nn.relu,
                                            sparse_inputs=self.sparse_inputs))
        self.layers.append(GraphConvolution(name='GCN_1',
                                            input_dim=self.hid_dim,
                                            output_dim=self.output_dim,
                                            dropout=self.dropout,
                                            act=lambda x: x,
                                            sparse_inputs=False))

        for layer in self.layers:
            for var in layer.vars.values():
                self.vars.append(var)

        self.op = tf.optimizers.Adam(self.lr)

    def forward(self, params):
        # params: features  support
        for layer in self.layers:
            hidden = layer(params)
            params.update({'features': hidden})
        return hidden

    def _update(self, tape, loss):
        gradients = tape.gradient(target=loss, sources=self.vars)
        self.op.apply_gradients(zip(gradients, self.vars))

    def _loss(self, outputs, labels, labels_mask):
        loss = masked_softmax_cross_entropy(outputs,
                                            labels,
                                            labels_mask)
        for var in self.vars:
            loss += self.weight_decay*tf.nn.l2_loss(var)
        # Cross entropy error
        return loss


class FASTGCN(Model):

    def __init__(self, placeholders, sparse_inputs=False):
        super(FASTGCN, self).__init__()
        self.input_dim = placeholders['in_dim']
        self.hid_dim = placeholders['hid_dim']
        self.output_dim = placeholders['out_dim']
        self.weight_decay = placeholders['weight_decay']
        self.dropout = placeholders['dropout']
        self.lr = placeholders['lr']
        self.sparse_inputs = sparse_inputs  # params['features'] sparse or not
        self.build()

    def build(self):
        """构建2 layer GCN, 并保存参数到vars中
           第一层需要sparse_inputs 如果features是sparse,则features x W 要sparsedot
           第二层不需要sparse_inputs 因为H0是dense的"""

        self.layers.append(Dense(name='Dense_0',
                                 input_dim=self.input_dim,
                                 output_dim=self.hid_dim,
                                 dropout=self.dropout,
                                 act=tf.nn.relu,
                                 sparse_inputs=self.sparse_inputs))

        self.layers.append(GraphConvolution(name='GCN_1',
                                            input_dim=self.hid_dim,
                                            output_dim=self.output_dim,
                                            dropout=self.dropout,
                                            act=lambda x: x,
                                            sparse_inputs=False))

        for layer in self.layers:
            for var in layer.vars.values():
                self.vars.append(var)

        self.op = tf.optimizers.Adam(self.lr)

    def forward(self, params):
        # params: features  support
        for layer in self.layers:
            hidden = layer(params)
            params.update({'features': hidden})
        return hidden

    def _update(self, tape, loss):
        gradients = tape.gradient(target=loss, sources=self.vars)
        self.op.apply_gradients(zip(gradients, self.vars))

    def _loss(self, outputs, labels):
        # batch outputs
        loss = softmax_cross_entropy(outputs,
                                     labels)
        for var in self.vars:
            loss += self.weight_decay*tf.nn.l2_loss(var)
        # Cross entropy error
        return loss

4.metrics.py

import tensorflow as tf


def masked_softmax_cross_entropy(preds, labels, mask):
    """Softmax cross-entropy loss with masking."""
    loss = tf.nn.softmax_cross_entropy_with_logits(logits=preds, labels=labels)
    mask = tf.cast(mask, dtype=tf.float32)
    mask /= tf.reduce_mean(mask)
    loss *= mask  # element-wise 把其它节点遮掉,只用train nodes来训练
    return tf.reduce_mean(loss)


def masked_accuracy(preds, labels, mask):
    """Accuracy with masking."""
    correct_prediction = tf.equal(tf.argmax(preds, 1), tf.argmax(labels, 1))
    accuracy_all = tf.cast(correct_prediction, tf.float32)
    mask = tf.cast(mask, dtype=tf.float32)
    mask /= tf.reduce_mean(mask)
    accuracy_all *= mask
    return tf.reduce_mean(accuracy_all)


def softmax_cross_entropy(preds, labels):
    loss = tf.nn.softmax_cross_entropy_with_logits(logits=preds, labels=labels)
    return tf.reduce_mean(loss)


def accuracy(preds, labels):
    correct_prediction = tf.equal(tf.argmax(preds, 1), tf.argmax(labels, 1))
    accuracy_all = tf.cast(correct_prediction, tf.float32)
    return tf.reduce_mean(accuracy_all)

5.inits.py

import tensorflow as tf
import numpy as np


def uniform(shape, scale=0.05, name=None):
    """Uniform init."""
    initial = tf.random.uniform(
        shape, minval=-scale, maxval=scale, dtype=tf.float32)
    return tf.Variable(initial, name=name)


def glorot(shape, name=None):
    """Glorot & Bengio (AISTATS 2010) init."""
    init_range = np.sqrt(6.0/(shape[0]+shape[1]))
    initial = tf.random.uniform(
        shape, minval=-init_range, maxval=init_range, dtype=tf.float32)
    return tf.Variable(initial, name=name)


def zeros(shape, name=None):
    """All zeros."""
    initial = tf.zeros(shape, dtype=tf.float32)
    return tf.Variable(initial, name=name)


def ones(shape, name=None):
    """All ones."""
    initial = tf.ones(shape, dtype=tf.float32)
    return tf.Variable(initial, name=name)

6.main.py

from model.utils import *
from model.metrics import *
from model.models import FASTGCN
import tensorflow as tf
from scipy.sparse import csr_matrix
import time


def iterate_minibatches_listinputs(inputs, batchsize, shuffle=False):
    """ 对inputs: [normADJ_train, y_train]进行切片"""
    assert inputs is not None
    numSamples = inputs[0].shape[0]  # 训练节点个数
    if shuffle:
        indices = np.arange(numSamples)
        np.random.shuffle(indices)
    """ 步长为batchsize,如果需要shuffle 则对indices进行切片.否则直接按顺序切片. """
    for start_idx in range(0, numSamples - batchsize + 1, batchsize):
        if shuffle:
            excerpt = indices[start_idx:start_idx + batchsize]
        else:
            """slice(start, stop, step)
               => start -- 起始位置 stop -- 结束位置 step -- 间距 """
            excerpt = slice(start_idx, start_idx + batchsize)
        """ print(len(excerpt))
            >>> 250 (batch_size)
            [input[excerpt] for input in inputs] =>
            inputs由normADJ_train和y_train组成,
            input相当于normADJ_train或y_train,即分别对二者切片 """
        yield [input[excerpt] for input in inputs]


def construct_params(features, support):
    params = dict()
    params.update({'support': tf.cast(tf.SparseTensor(
        support[0], support[1], support[2]), tf.float32)})
    params.update({'features': tf.cast(tf.SparseTensor(
        features[0], features[1], features[2]), tf.float32)})
    params.update({'num_features_nonzero': features[1].shape})
    return params


if __name__ == "__main__":

    (adj, features,
     y_train, y_val, y_test,
     train_mask, val_mask, test_mask) = load_data('cora')
    """np.where 找出mask中为true的下标 """
    train_index = np.where(train_mask)[0]
    y_train = y_train[train_index]
    val_index = np.where(val_mask)[0]
    y_val = y_val[val_index]
    test_index = np.where(test_mask)[0]
    y_test = y_test[test_index]

    """print(adj_train.shape, y_train.shape, y_test.shape, y_val.shape)
       >>> (1208, 1208) (1208, 7) (1000, 7) (500, 7) """

    train_val_index = np.concatenate([train_index, val_index], axis=0)
    train_test_idnex = np.concatenate([train_index, test_index], axis=0)

    """preprocessing csr adj && features:
    print(csr_normADJ_train.shape, csr_normADJ_val.shape, csr_normADJ_test.shape)
    print(csr_features_train.shape,csr_features_val.shape, csr_features_test.shape)
    >>> (1208, 1208) (1708, 1708) (2208, 2208)
    >>> (1208, 1433) (1708, 1433) (2208, 1433)"""
    csr_normADJ_train = nontuple_preprocess_adj(
        adj[train_index, :][:, train_index])  # (1208, 1208)
    csr_normADJ_val = nontuple_preprocess_adj(
        adj[train_val_index, :][:, train_val_index])    # (1708, 1708)
    csr_normADJ_test = nontuple_preprocess_adj(
        adj[train_test_idnex, :][:, train_test_idnex])  # (2208, 2208)

    csr_features_train = nontuple_preprocess_features(
        features[train_index])
    csr_features_val = nontuple_preprocess_features(
        features[train_val_index])
    csr_features_test = nontuple_preprocess_features(
        features[train_test_idnex])

    y_val = np.vstack((y_train, y_val))
    y_test = np.vstack((y_train, y_test))
    """ 计算每个节点的概率: q(u) = ||A(: , u)||^2 / sum(||A(: , v)||^2) """
    p0 = column_prop(csr_normADJ_train)

    epochs = 200
    samplesize = 50

    placeholders = {'in_dim': 1433,
                    'hid_dim': 32,
                    'out_dim': 7,
                    'weight_decay': 5e-4,
                    'dropout': 0.5,
                    'lr': 0.01}

    dense_AXfeatures_train = csr_normADJ_train.dot(
        csr_features_train.todense())
    dense_AXfeatures_val = csr_normADJ_val.dot(
        csr_features_val.todense())
    dense_AXfeatures_test = csr_normADJ_test.dot(
        csr_features_test.todense())

    """print(dense_AXfeatures_train.shape, dense_AXfeatures_val.shape, dense_AXfeatures_test.shape)
    >>> (1208, 1433) (1708, 1433) (2208, 1433)"""

    # transform into tuple
    tuple_AXfeatures_train = sparse_to_tuple(
        csr_matrix(dense_AXfeatures_train))
    tuple_AXfeatures_val = sparse_to_tuple(
        csr_matrix(dense_AXfeatures_val))
    tuple_AXfeatures_test = sparse_to_tuple(
        csr_matrix(dense_AXfeatures_test))

    model = FASTGCN(placeholders, sparse_inputs=True)
    cost_val = []
    t = time.time()
    for epoch in range(epochs):
        for batch in iterate_minibatches_listinputs([csr_normADJ_train, y_train], batchsize=1024, shuffle=True):
            [normADJ_batch, y_train_batch] = batch

            """get support_batch(tuple), features_inputs(tuple). """
            if samplesize == -1:
                support_batch = sparse_to_tuple(normADJ_batch)
                features_inputs = sparse_to_tuple(
                    csr_matrix(dense_AXfeatures_train))
            else:
                distr = np.nonzero(np.sum(normADJ_batch, axis=0))[1]
                if samplesize > len(distr):
                    q1 = distr
                else:
                    q1 = np.random.choice(
                        distr, samplesize, replace=False, p=p0[distr]/sum(p0[distr]))  # 根据概率p0选出rank1个顶点
                support_batch = sparse_to_tuple(normADJ_batch[:, q1].dot(
                    sp.diags(1.0 / (p0[q1] * samplesize))))
                if len(support_batch[1]) == 0:
                    continue
                features_inputs = sparse_to_tuple(
                    csr_matrix(dense_AXfeatures_train[q1, :]))

            """print(support_batch[2], features_inputs[2])
            >>> (200, 50) (50, 1433)"""

            # support_batch used at 2nd layer
            params = construct_params(
                features_inputs, support_batch)

            with tf.GradientTape() as tape:
                logits = model.forward(params)
                loss = model._loss(logits, y_train_batch)
            model._update(tape, loss)

        train_logits = model.forward(construct_params(
            tuple_AXfeatures_train, sparse_to_tuple(csr_normADJ_train)))
        train_acc = accuracy(train_logits, y_train)

        val_logits = model.forward(construct_params(
            tuple_AXfeatures_val, sparse_to_tuple(csr_normADJ_val)))
        val_acc = accuracy(val_logits, y_val)

        test_logits = model.forward(construct_params(
            tuple_AXfeatures_test, sparse_to_tuple(csr_normADJ_test)))
        test_acc = accuracy(test_logits, y_test)

        view_bar('epoch', epoch+1, epochs, loss, train_acc,
                 val_acc, test_acc, time.time()-t)