I am trying to implement Antithetic Sampling to sample vertices of the graph and train the downstream graph convolutional network (GCN) model on the sampled graph.
Antithetic Sampling is a variance reduction technique that involves generating pairs of random samples and their corresponding antithetic counterparts to cancel out fluctuations, leading to more accurate estimates.
Below is my code and function '_Antithetic_sampling(...)' is main function to implement the logic of Antithetic Sampling.:
import math
import torch
import numpy as np
import scipy.sparse as sp
from scipy.sparse.linalg import norm as sparse_norm
class Antithetic_Sampler(Sampler):
def __init__(self, pre_probs, features, adj, **kwargs):
super().__init__(features, adj, **kwargs)
col_norm = sparse_norm(adj, axis=0)
self.probs = col_norm / np.sum(col_norm)
def sampling(self, v):
"""
Inputs:
v: batch nodes list
"""
all_support = [[]] * self.num_layers # Initialize empty list for all layers
cur_out_nodes = v
for layer_index in range(self.num_layers - 1, -1, -1): # Start from the last layer and move backwards
cur_sampled, cur_support = self._Antithetic_sampling(cur_out_nodes, self.layer_sizes[layer_index]) # sample nodes and collect support
all_support[layer_index] = cur_support # for corresponding layer, Store current support in all_support
cur_out_nodes = cur_sampled # Update nodes
all_support = self._change_sparse_to_tensor(all_support) # Convert support to tensor representation
sampled_X0 = self.features[cur_out_nodes] # Extract features of the sampled nodes
return sampled_X0, all_support, 0
# Perform Antithetic Sampling
def _Antithetic_sampling(self, v_indices, output_size):
support = self.adj[v_indices, :]
neis = np.nonzero(np.sum(support, axis=0))[1]
# Create two sets of random sampling weights
p1 = self.probs[neis]
p1 = p1 / np.sum(p1) # Normalize probability
p2 = 1 - p1
p2 = p2 / np.sum(p2)
# Sample the first set of neighbors
sampled_1 = np.random.choice(np.arange(np.size(neis)), output_size, True, p1)
u_sampled_1 = neis[sampled_1]
support_1 = support[:, u_sampled_1]
sampled_p1 = p1[sampled_1]
support_1 = support_1.dot(sp.diags(1.0 / (sampled_p1 * output_size)))
# Sample the second set of neighbors with opposite weights
sampled_2 = np.random.choice(np.arange(np.size(neis)), output_size, True, p2)
u_sampled_2 = neis[sampled_2]
support_2 = support[:, u_sampled_2]
sampled_p2 = p2[sampled_2]
support_2 = support_2.dot(sp.diags(1.0 / (sampled_p2 * output_size)))
# Average two sets of sampled neighbors
u_sampled = (u_sampled_1 + u_sampled_2) // 2
support = (support_1 + support_2) / 2
#print("U samples: ", u_sampled)
#print("Support: ", support)
return u_sampled, support
Output of this code is:
epchs:0~9 => test_loss: 1.882, test_acc: 0.319
epchs:10~19 => test_loss: 1.879, test_acc: 0.319
epchs:20~29 => test_loss: 1.876, test_acc: 0.319
epchs:30~39 => test_loss: 1.879, test_acc: 0.319
epchs:40~49 => test_loss: 1.871, test_acc: 0.319
epchs:50~59 => test_loss: 1.873, test_acc: 0.319
It can be observed that test accuracy is not changing, which indicates that there might be a logical mistake in my implementation of Antithetic Sampling. Comments in the code provide details of each step, and I've included links to relevant sources for reference. I'm looking for help to identify the mistake in my implementation.
More details about Antithetic Sampling can be found here and here (section 8.2).