• We updated the non-gpu environment in e0b89bc, so once #29 and #31 have finished running we should update the gpu environment
• Also after #29 has finished running, rename the output files so they include the feature noise scale (as introduced by beba46b)
• finish Git-LFS history rewrite for all branches
• recreate a PR to replace #12 which got closed by the history rewrite
• remove issue-3-mini-batching-with-features if possible
• remove or check history rewrite of issue-6-sensitivity-analysis
• find out git-lfs quota on gitlab.com and on Inria's gitlab, as we are reaching the quota here

This tests if the poor adjacency reconstruction we're seeing in #31 comes from the weighing of losses.

Simpler version of #40.

In representing the network at the level of ξ, both network and feature structure can count, and they might not agree. Some networks e.g. in #8 might be better described by giving more weight to adjacency reconstruction (p_adj_loss), and some more to feature reconstruction (p_v_loss).

• One way to explore is to simply weigh α × p_adj_loss + β × p_v_loss with α + β = 1, and explore the output for different values for α and β. But for comparisons to be made, we need a quality measure which is other than the total loss (which we affect when changing α and β).
• Another way is to directly train α and β (use them as trainable parameters in the learning process), and see if different synthetic data sets give different best values.

Run the training only for 2000 epochs, as most of the final quality seems to be reached there already.

• Use the Bernoulli decoder for features
• Use changes from #38
• Remove u from embedding parameters

Work branched out from #19.

LeCun et al., 1998, "Efficient backprop" gives many tips and tricks for good neural networks.

For instance, some people on SO say that ReLU is not a good activation for auto-encoders as it loses more information than, say, tanh. Check if LeCun has opinions about this and more.

What happens when features do not correlate to the network structure, i.e. when there are more complex dependencies between features and network structure? What do the embeddings look like, can we influence them?

There are preliminary explorations in the projects/behaviour/feature-network-dependencies.ipynb notebook.

E.g. nettack.

It should work at least as well as full batch training in this case.

When the features correlate a little to the network structure, even random weights seem to separate the distribution of ξ (i.e. the representation layer in the VAE) into communities. This is, as Thomas Kipf explains in his post on GCNs, because "a GCN model [can be interpreted] as a generalized, differentiable version of the well-known Weisfeiler-Lehman algorithm on graphs". It also makes sense as you basically average features from community neighbours, therefore recovering any local average that is consistent with network structure.

The upshot is that even without training, in some cases the distribution of ξ seems to reflect network structure. So what's the use of training, apart from getting a generative model (i.e. training the layers that come after the ξ layer)?

Sub-questions:

• How does such a random ξ behave with non-random features that do not correlate to network structure (e.g. feature communities have lower, or higher, or displaced granularity compared to network communities): does one structure win over the other, or does it simply mess up the picture? The answer to this probably lies in criticisms of Label-propagation algorithms for community detection (e.g. Raghavan, Albert, & Kumara, 2007, "Near linear time algorithm to detect community structures in large-scale networks" ).
• What is a "good" ξ distribution (i.e. a good representation model), independently of its use in the generative model? One that visually reproduces the feature- or network-structure (or both)? Can we build of measure of how good a given ξ is? Maybe there are answers to this in the pro-con arguments about why t-SNE is a good visualisation method (see e.g. How to Use t-SNE Effectively).

Go back to simple manual exploration of the effect of the current minibatch strategy on a small (200-500 nodes) network.

Try out other sampling strategies. First for the case where we know the graph generation parameters. Then for the case where we don't know the graph model.

In #8 we're applying the current code to the BlogCatalog dataset: 10,312 nodes, 333,983 edges, and it is SLOW: about 20s per mini-batch, so about 7 minutes per epoch. Some profiling insights:

On grunch, fit_generator_feed() using n_epochs=1, batch_size=500, max_walk_length=200 and neighbour_samples=30 spends > 52% of its time in the batch-generation code.

On grunch again, same parameters, looking only at the batch-generation code:

• 4.4% time spent in jumpy_walks()
• 94.6% time spent in _compute_batch() (21 calls, one per mini-batch), of which
  • 21% (of the 94.6%) time spent in _layer_csr_adj() (4 calls per call to _collect_layers_crops())
  • the rest is at the root of _compute_batch() (i.e. not in nested functions)

Hottest lines:

And inside _compute_batch() (loop unfurled):

Finally, note the slightly different numbers on keon (my machine):

• 6.3% time spent in jumpy_walks()
• 92% time spent in _compute_batch() (21 calls, one per mini-batch), of which
  • 49% (of the 92%) time spent in _layer_csr_adj() (4 calls per call to _collect_layers_crops())
  • the rest is at the root of _compute_batch() (i.e. not in nested functions)

Steps to improve:

• Create tests for batching.py to make sure nothing breaks
• Use a sparse adjacency matrix across all the functions
• Profile again

i.e. with an identity matrix as features. Maybe extend that to training with BlogCatalog node features to which an identity matrix is concatenated, to make sure the model has enough information to separate the nodes based on features.

This tests if the bad adjacency reconstruction we're seeing in #31 comes from not being able to separate nodes based on their features.

Note that a mini-batch with convolutions needs access to all the neighbouring nodes it will include in convolutions, on top of the nodes in the mini-batch for which we compute an update.

We had a good chat with @jaklevab about that a few days back, I'll be jotting down things here as we flesh it out.

For now, these two papers were mentioned:

• A Kernel Independence Test for Geographical Language Variation
• Diffusion of Lexical Change in Social Media

This is a test issue to see if it shows up in slack

Test the following parameters:

• node features: exact network communities, noisy network communities, noisy network communities with redundancy, random
• dim_ξ: [2, ..., 10]
• dim_l1: [dim_ξ, ..., 16]
• n_ξ_samples: [1, 5, 10]
• bias in all layers: True/False

For each run, save:

• the original and final-predicted adjacency and/or features
• the evolution of the training losses
• ξ distribution plots before and after training (for dim_ξ ≥ 2, use a dimension reduction technique such as t-SNE)

The PSMN uses Sun Grid Engine, which is now Univa Grid Engine (see wikipedia).

Univa has a recent blog post on how to integrate SGE with Tensorflow, which requires some admin intervention: https://blogs.univa.com/2018/04/integrating-distributed-tensorflow-with-grid-engine/. It's worth talking to the PSMN people about this.

There's also some conversation about this over at TensorFlow: tensorflow/tensorflow#7068

This is the follow-up to point 2 of question 1 here.

In short, when using the straightforward cross-entropy value for adjacency reconstruction, we give equal weight to neighbours and non-neighbours in the prediction accuracy. Ideally, what we'd like to do is predict, for each node, the set of neighbours and the set of non-neighbours, without penalising our prediction loss by the fact that there are (usually) many more non-neighbours than there are neighbours.

The current solution (in #10, soon to be merged) is to scale the items in the KL loss so that, for a given node, its neighbours contribute 1/2 on average, and its non-neighbours contribute 1/2 on average. We then average over all nodes to get a loss that contributes 1, but weighs neighbours and non-neighbours equally.

Another way would be to upscale true positives and true negatives, and downscale false positives and false negatives.

And update results notebooks so they still run.

From question 3 here:

In the case where we have a sparse network, mini-batching with randomly selected nodes will almost always select nodes that are not directly connected, such that the adjacency matrix restricted to the mini-batch will almost always be the identity matrix. So training on this is bound to be very bad.

The best option now is probably to randomly sample a small number s of seeds, then make a random walk of length l around each of those seeds to also have nodes connected between each other, such that the mini-batch size is s * l.

On the current synthetic data the features are dense, so there's no immediate gain for this. But once we use real-world data it will become necessary.

This could also be a root cause behind the problems of #36, #37, #38.

Work branched out from #19.

For adjacency, this should be the standard link prediction metric (look it up in one of the reference papers).

I'm not sure what we should use for feature reconstruction yet.

This is a step further than #37.

To make sure we understand what's going on during training. A notebook to make animations can be found in projects/behaviour/ae-animations.ipynb.

Then:

• check that performance is comparable to gae (cf #44, we left at .4618 for gae vs. .4701 for nw2vec)
• check that the implementations of the adj loss in gae and what we have (esp. weighing) match

This means implementing the saving/loading logic in the custom Keras layers in nw2vec/layers.py.

Blocked on #2 #3.

With synthetic data:

• increase network size
• increase the number of features

For real data we can use a subset of the Twitter data, but better than that (at least for starting) the Colorado Index of Complex Networks has lots of good small data sets, e.g.:

• Malaria var DBLa HVR networks
• French financial elites (1990)
• BlogCatalog, Flickr, YouTube (2009)

To see if that's the limiting factor in why the embeddings currently don't look good at all. (See here.)

Four things, each to be visualised using downscaling and projections (the paper doesn't specify the method used to produce their 2D figure from 16D embeddings):

• run their gae implementation directly to reproduce their own procedure
• run our implementation with their parameters:
  • no u parameter for embedding covariance matrix (remove the layer, and set u to 0 in the codec)
  • simple scalar product decoder
  • intermediate layer 32 dims, embedding layer 16 dims
  • train for 200 iterations
  • get the loading code from their gae implementation
• reactivate kernel in scalar product
• add the 2-layer decoder we've been using
• add the u term in the embedding covariance matrix

Note that the current implementation mimics their gae closer than what we'll have after implementing #7, so do this before.

So that we have the training history, not only the checkpoint.

None of these are necessary, I'm just listing them to keep track of all the possible small-ish changes that might improve performance or reduce the need for resources:

Normalizations:

• Batch normalization
• Self-normalization

Connections:

• Residual connections

Reduction of necessary parameters and resources:

• Mini-batching
• Small sampling of neighbourhoods

Noise for training:

• Dropout
• Denoising, adapted to Variational Autoencoders

Removing unneeded left-overs:

• Bayesian compression

Different models:

• Generative Adversarial Networks
• Adversarial Variational Bayes: Unifying Variational Autoencoders and Generative Adversarial Networks

• What licenses are authorised by Inria?
• Who holds the copyright to this software?
• What licenses are compatible with what we ship?

Problem

In the current mini-batch approach being worked on in #10, we sample the nodes that will be part of the mini-batch, then sample their neighbourhoods to define which nodes will be used in the last layer's convolution, then walk back the convolution layers to sample, for each convolution, the neighbourhoods of the nodes that are necessary at the layer after the current one. Therefore:

• if our mini-batch computes a loss for B nodes,
• and we sample M nodes at each layer,
• and the network architecture is L convolutions deep,

in the worst case we need B * M^L nodes to compute that mini-batch, which can be a lot if L grows.

Available solution

Chen, Ma, & Xiao, 2018, "FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling" show that for dense graphs, it may not be necessary to recursively sample this way. At any given convolution layer in the neural network, they estimate a node u's value by sampling on the whole graph proportionally to ||A(u, :)||² (where A is the (normalised?) adjacency matrix), irrespective of the nodes that are used in preceding and following layers in the neural network (this is the importance sampling part). With the notations above, the worst case then uses B * M * L nodes to compute a given mini-batch. Much better. And the authors show that this method achieves prediction accuracy equivalent to GraphSAGE on several well-tested data sets.

Caveat

This supposes that an importance sampling on the whole graph can provide enough nodes to estimate any node's value at a convolution layer. In other words, this works if the importance sampling provides enough nodes in the neighbourhood of any node in the graph.

Hamilton notes this in the review linked to above:

The idea of sampling vertices at each layer makes sense in small graphs or dense graphs. However, I think it might become problematic in massive, sparse graphs. For example, in industry applications with 1+ billion nodes (or sparse graphs with many disconnected components), I would think the odds of a node in a batch having a neighbor in the sampled set will get quite small, unless the sampled set grows proportionally large in size.

Resulting question

The question then becomes: how do we know when this can be useful, i.e. when our graph is dense enough to warrant this sampling method?

Possible answers I see:

• define a threshold on graph sparsity, and see if we need this for the Twitter data
• discard this as a premature optimisation concern, or an engineering-level improvement that we don't wish to spend time on