Published
Edited
Dec 5, 2020
InputData = DummyList
SampleCount = 1000 // Should be 1000000, reduced to 1000 for demonstration purposes
NegativeTableSize = 1000 // Should be 100000000, reduced to 1000 for demonstration purposes
function GetVerts() {
let verts = new Map();
for (let i = 0; i < EdgeCount; i++)
{
const vert0 = InputData[i][0];
const vert1 = InputData[i][1];
const weight = InputData[i][2];
InsertVert(verts, vert0, weight);
InsertVert(verts, vert1, weight);
}
return verts;
}
function GetAliasProbTables() {
// Calculate norm prob table
let sum = 0;
let normProb = new Array(EdgeCount);
for (let i = 0; i < EdgeCount; i++) sum += InputData[i][2];
for (let i = 0; i < EdgeCount; i++) normProb[i] = (InputData[i][2] * EdgeCount) / sum;
// Calculate small block and large block tables
let smallBlock = [];
let largeBlock = [];
for (let i = EdgeCount-1; i >= 0; i--) (normProb[i] < 1) ? smallBlock.push(i) : largeBlock.push(i);
// Calculate alias and prob tables
let aliasTable = new Array(EdgeCount);
let probTable = new Array(EdgeCount);
let smallBlockIter = smallBlock.length;
let largeBlockIter = largeBlock.length;
while (smallBlockIter != 0 && largeBlockIter != 0) {
let smallBlockValue = smallBlock[--smallBlockIter];
let largeBlockValue = largeBlock[--largeBlockIter];
probTable[smallBlockValue] = normProb[smallBlockValue];
aliasTable[smallBlockValue] = largeBlockValue;
normProb[largeBlockValue] += normProb[smallBlockValue] - 1;
if (normProb[largeBlockValue] < 1)
smallBlock[smallBlockIter++] = largeBlockValue;
else
largeBlock[largeBlockIter++] = largeBlockValue;
}
while (largeBlockIter != 0) probTable[largeBlock[--largeBlockIter]] = 1;
while (smallBlockIter != 0) probTable[smallBlock[--smallBlockIter]] = 1;
return [aliasTable, probTable];
}
function InitEmbeddedTables() {
let embVertex = new Array(VertexCount * Dimensions);
let embContext = new Array(VertexCount * Dimensions);
for (let i = 0; i < Dimensions; i++) {
for (let j = 0; j < VertexCount; j++) {
embVertex[j * Dimensions + i] = (Math.random() - 0.5) / Dimensions;
embContext[j * Dimensions + i] = 0;
}
}
return [embVertex, embContext];
}
function GetNegTable() {
let sum = 0, curSum = 0, por = 0, vid = 0;
let negTable = new Array(NegativeTableSize);
let degrees = new Array();
const samplingPower = 0.75;
function GetVertex(value, key, map) { degrees.push(value[0]); }
Vertices.forEach(GetVertex);
for (let i = 0; i < VertexCount; i++) sum += Math.pow(degrees[i], samplingPower);
for (let i = 0; i < negTable.length; i++) {
if ((i + 1) / negTable.length > por) {
curSum += Math.pow(degrees[vid], samplingPower);
por = curSum / sum;
vid++;
}
negTable[i] = vid - 1;
}
return negTable;
}
function InitSigmoidTable() {
let sigTable = new Array(1001);
for (let i = 0; i < (sigTable.length - 1); i++) {
const x = 2.0 * SigmoidBound * i / (sigTable.length - 1) - SigmoidBound;
sigTable[i] = 1 / (1 + Math.exp(-x));
}
return sigTable;
}
function SampleEdge() {
let edge = Math.floor(EdgeCount * Math.random())
return Math.random() < AliasProbTables[1][edge] ? edge : AliasProbTables[0][edge];
}
function FastSigmoid(x) {
if (x > SigmoidBound) return 1;
else if (x < -SigmoidBound) return 0;
return SigmoidTable[Math.floor((x + SigmoidBound) * (SigmoidTable.length - 1) / SigmoidBound / 2)];
}
function Update(u, v, label, error, rho) {
let x = 0;
for (let i = 0; i < Dimensions; i++) x += u[i] * v[i];
let g = (label - FastSigmoid(x)) * rho;
for (let i = 0; i < Dimensions; i++) error[i] += g * v[i];
for (let i = 0; i < Dimensions; i++) v[i] += g * u[i];
}
function Train() {
let vecError = new Array(Dimensions);
//let embVertices = [0.170094, 0.205824, -0.052809, -0.151224, 0.141550, -0.082389, 0.149220, 0.134115];
let embVertices = EmbTables[0].slice();
let embContexts = EmbTables[1].slice();
let lastRhoUpdate = 0;
let rho = InitRho;
for (let i = 0; i < SampleCount + 2; i++) {
if (i - lastRhoUpdate > 10000) {
rho = InitRho * (1 - (i / (SampleCount + 1)));
if (rho < InitRho * 0.0001) rho = InitRho * 0.0001;
lastRhoUpdate = i;
}
const edge = SampleEdge();
const u = Vertices.get(InputData[edge][0])[1];
const v = Vertices.get(InputData[edge][1])[1];
const lu = u * Dimensions;
vecError.fill(0);
let target = v, label = 1;
for (let j = 0; j < NegSampleCount; j++) {
if (j > 0) {
target = NegTable[Math.floor(NegTable.length * Math.random())];
label = 0;
}
const lv = target * Dimensions;
// Choose first or second order here
// For now we are only doing second
let embVector = embVertices.slice(lu, lu + Dimensions);
let embContext = embContexts.slice(lv, lv + Dimensions);
Update(embVector, embContext, label, vecError, rho);
for (let k = 0; k < Dimensions; k++) embContexts[lv + k] = embContext[k];
}
for (let j = 0; j < Dimensions; j++) embVertices[lu + j] += vecError[j];
}
return embVertices;
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
