Embedding the GitHub contribution graph

About me

• Data Scientist, Machine Learning @ source{d}
• Education: robotics
• Switched to ML/DS in 2013

Plan

goo.gl/gtZbyc

1. Motivation
2. Dataset description
3. Algorithms
4. Algorithms: Swivel & node2vec
5. Training details
6. Results

Motivation

1. Labeled data is expensive
2. Unlabeled data is available
3. Most of the data has some structure
4. In most of the cases: item & context
5. This structural information can be represented as embeddings
6. We want to encode
   • developer-repository relations in continuous vectors

Where to take the data?

Commit datasets:

• GHTorrent (145M)
• commits table in Google BigQuery - equivalent to GHTorrent
• GitHub Archive (stream, unknown)
• source{d}'s 452M dataset with de-fuzzy-forking

BigQuery will charge you money.

Dataset description

• 16.6M repositories
• 6.6M developers
• 452M commits
• Bipartite graph - developers & repositories
• Non planar graph

Graph visualization

How this was drawn.

Adjacency matrix

C_ij is the number of commits done by developer i to repository j

C_ij = C_ji

Non-zero elements: <10^-7

Algorithms

• Word2Vec: CBOW & SGNS
• GloVe
• Swivel
• node2vec
• fastText
• Semantic hashing
• Random projections
• Autoencoders, RBM, t-SNE, PCA, etc.

What to use: Swivel

Description
• Complexity: O(co-occurrence matrix) - useful on huge corpuses
• Handling unobserved co-occurences: identity matching
• Parallelism: co-occurence matrix -> shards
• Quality: best results (according to paper)

What to use: node2vec + fastText

Description
• Complexity: O(size of the corpus)
• Handling unobserved co-occurences: character ngram
• Parallelism: like word2vec

Training details:

Dataset is skewed
• Filter out repositories with less than 6 contributors:
  • 222k repositories
  • 1.2M developers

Training details

Swivel pipeline
1. Filtering
2. Graph -> corpus
3. Corpus -> co-occurrence matrix
4. Co-occurrence matrix -> shards
5. Random init
6. Iterative approximation of PMI

Training details

node2vec pipeline
1. Filtering
2. Graph -> corpus
3. Random init
4. Iterative approximation of PMI

Training details

Swivel pipeline: Graph to text corpus
• for repo in repos:
  • for dev in repo.developers:
  • create pair (repo, dev)
  • repeat pair n_commits time
  dump to file
• result: "repo dev_1 repo dev_1 repo dev_2"
• result: ≈2 GB corpus

Training details

node2vec pipeline: Graph to text corpus
• def random_walk(node, max_len):
  • # There could be many random walk strategies
  • # Our case: probability n1 -> n2 ~ n_commits(n1, n2) / n_commits(n2)
  • return __alg__(node, max_len)

Training details

node2vec pipeline: Graph to text corpus
• for node in graph:
  • for _ in range(n_random_walks):
  • path = random_walk(node, max_len)
  • dump to file
• result: "repo1 dev1 repo42 dev137 repo167 dev42"
• result: 10 random walks * 80 max_len ≈6 GB corpus

Training details

• Hardware:
  • 2 * Titan X 2016
  • 2 * GTX 1080 Ti
  • (Brewery)

Training details

• Swivel:
  • Embedding: 100
  • Epochs: 40
  • Duration: ≈0.5 hour preprocessing + ≈24 hours training
• node2vec:
  • Embedding: 100
  • Epochs: 40
  • Duration: ≈6 hours preprocessing + ≈2 hours fastText

Results: similar to tensorflow/tensorflow

Results: similar to torch/nn

Results: similar to zmatsh/Docker

Results: similar to BeerWithMe/beer-finder

Questions?

Contact information:
• mail: egor@sourced.tech
• LinkedIn: www.linkedin.com/in/egor-bulychev-028237118
• GitHub: github.com/EgorBu
• Twitter: twitter.com/egor_bu