HashGNN

To clarify how HashGNN works, we will walk through a virtual example below of a three node graph for the reader who is curious about the details of the feature selection and prefers to learn from examples.

The HashGNN algorithm can only run on binary features. Therefore, there is an optional first step to transform (possibly non-binary) input features into binary features as part of the algorithm.

For a number of iterations, a new binary embedding is computed for each node using the embeddings of the previous iteration. In the first iteration, the previous embeddings are the input feature vectors or the binarized input vectors.

During one iteration, each node embedding vector is constructed by taking K random samples. The random sampling is carried out by successively selecting features with lowest min-hash values. Features of each node itself and of its neighbours are both considered.

There are three types of hash functions involved: 1) a function applied to a node’s own features, 2) a function applied to a subset of neighbors' features 3) a function applied to all neighbors' features to select the subset for hash function 2). For each iteration and sampling round k<K, new hash functions are used, and the third function also varies depending on the relationship type connecting to the neighbor it is being applied on.

The sampling is consistent in the sense that if nodes (a) and (b) have identical or similar local graphs, the samples for (a) and (b) are also identical or similar. By local graph, we mean the subgraph with features and relationship types, containing all nodes at most iterations hops away.

The number K is called embeddingDensity in the configuration of the algorithm.

The algorithm ends with another optional step that maps the binary embeddings to dense vectors.

The original HashGNN algorithm assumes that nodes have binary features as input, and produces binary embedding vectors as output (unless output densification is opted for). Since this is not always the case for real-world graphs, our algorithm also comes with options to binarize node properties, or generate binary features from scratch.

The parameter neighborInfluence determines how prone the algorithm is to select neighbors' features over features from the same node. The default value of neighborInfluence is 1.0 and with this value, on average a feature will be selected from the neighbors 50% of the time. Increasing the value leads to neighbors being selected more often. The probability of selecting a feature from the neighbors as a function of neighborInfluence has a hockey-stick-like shape, somewhat similar to the shape of y=log(x) or y=C - 1/x. This implies that the probability is more sensitive for low values of neighborInfluence.

The GDS implementation of HashGNN provides a new generalization to heterogeneous graphs in that it can distinguish between different relationship types. To enable the heterogeneous support set heterogeneous to true. The generalization works as the original HashGNN algorithm, but whenever a hash function is applied to a feature of a neighbor node, the algorithm uses a hash function that depends not only on the iteration and on a number k < embeddingDensity, but also on the type of the relationship connecting to the neighbor. Consider an example where HashGNN is run with one iteration, and we have (a)-[:R]→(x), (b)-[:R]→(x) and (c)-[:S]→(x). Assume that a feature f of (x) is selected for (a) and the hash value is very small. This will make it very likely that the feature is also selected for (b). There will however be no correlation to f being selected for (c) when considering the relationship (c)-[:S]→(x), because a different hash function is used for S. We can conclude that nodes with similar neighborhoods (including node properties and relationship types) get similar embeddings, while nodes that have less similar neighborhoods get less similar embeddings.

An advantage of running heterogeneous HashGNN to running a homogenous embedding such as FastRP is that it is not necessary to manually select multiple projections or creating meta-path graphs before running FastRP on these multiple graphs. With the heterogeneous algorithm, the full heterogeneous graph can be used in a single execution.

Heterogenous graphs typically have different node properties for different node labels. HashGNN assumes that all nodes have the same allowed features. Use therefore a default value of 0 for in each graph projection. This works both in the binary input case and when binarization is applied, because having a binary feature with value 0 behaves as if not having the feature. The 0 values are represented in a sparse format, so the memory overhead of storing 0 values for many nodes has a low overhead.

Choosing the right orientation when creating the graph may have a large impact. HashGNN works for any orientation, and the choice of orientation is problem specific. Given a directed relationship type, you may pick one orientation, or use two projections with NATURAL and REVERSE. Using the analogy with GNN’s, using a different relationship type for the reversed relationships leads to using a different set of weights when considering a relationship vis-à-vis the reversed relationship. For HashGNN’s this means instead using different min-hash functions for the two relationships. For example, in a citation network, a paper citing another paper is very different from the paper being cited.

Since binary embeddings need to be of higher dimension than dense floating point embeddings to encode the same amount of information, binary embeddings require more memory and longer training time for downstream models. The output embeddings can be optionally densified, by using random projection, similar to what is done to initialize FastRP with node properties. This behavior is activated by specifying outputDimension. Output densification can improve runtime and memory of downstream tasks at the cost of introducing approximation error due to the random nature of the projection. The larger the outputDimension, the lower the approximation error and performance savings.

It may be useful to generate node embeddings with HashGNN as a node property step in a machine learning pipeline (like Link prediction pipelines and Node property prediction). Since HashGNN is a random algorithm and inductive only when featureProperties and randomSeed are given, there are some things to have in mind.

In order for a machine learning model to be able to make useful predictions, it is important that features produced during prediction are of a similar distribution to the features produced during training of the model. Moreover, node property steps (whether HashGNN or not) added to a pipeline are executed both during training, and during the prediction by the trained model. It is therefore problematic when a pipeline contains an embedding step which yields all too dissimilar embeddings during training and prediction.

This has some implications on how to use HashGNN as a node property step. In general, if a pipeline is trained using HashGNN as a node property step on some graph "g", then the resulting trained model should only be applied to graphs that are not too dissimilar to "g".

If feature generation is used, most of the nodes in the graph that a prediction is being run on, must be the same nodes (in the database sense) as in the original graph "g" that was used during training. The reason for this is that HashGNN generates the node features randomly, and in this case is seeded based on the nodes' ids in the Neo4j database from whence the nodes came.

If feature generation is not used (featureProperties is given), the random initial node embeddings are derived from node property vectors only, so there is no random seeding based on node ids.

Additionally, in order for the feature propagation of the HashGNN message passing to be consistent between runs (training and prediction calls), a value for the randomSeed configuration parameter must be provided when adding the HashGNN node property step to the training pipeline.

The maximum number of hops between a node and other nodes that affect its embedding is equal to the number of iterations of HashGNN which is configured with iterations. This is analogous to the number of layers in a GNN or the number of iterations in FastRP. Often a value of 2 to 4 is sufficient, but sometimes more iterations are useful.

The embeddingDensity parameter is what the original paper denotes by k. For each iteration of HashGNN, k features are selected from the previous iteration’s embeddings for the same node and for its neighbors. The selected features are represented as a set, so the number of distinct selected features may be smaller than k. The higher this parameter is set, the longer it will take to run the algorithm, and the runtime increases in a linear fashion. To large extent, higher values give better embeddings. As a loose guideline, one may try to set embeddingDensity to 128, 256, 512, or roughly 25%-50% of the embedding dimension, i.e. the number of binary features.

The dimension parameter determines the number of binary features when feature generation is applied. A high dimension increases expressiveness but requires more data in order to be useful and can lead to the curse of high dimensionality for downstream machine learning tasks. Additionally, more computation resources will be required. However, binary embeddings only have a single bit of information per dimension. In contrast, dense Float embeddings have 64 bits of information per dimension. Consequently, in order to obtain similarly good embeddings with HashGNN as with an algorithm that produces dense embeddings (e.g. FastRP or GraphSAGE) one typically needs a significantly higher dimension. Some values to consider trying for densityLevel are very low values such as 1 or 2, or increase as appropriate.

The dimension parameter determines the number of binary features when binarization is applied. A high dimension increases expressiveness, but also the sparsity of features. Therefore, a higher dimension should also be coupled with higher embeddingDensity and/or lower threshold. Higher dimension also leads to longer training times of downstream models and higher memory footprint. Increasing the threshold leads to sparser feature vectors.

However, binary embeddings only have a single bit of information per dimension. In contrast, dense Float embeddings have 64 bits of information per dimension. Consequently, in order to obtain similarly good embeddings with HashGNN as with an algorithm that produces dense embeddings (e.g. FastRP or GraphSAGE) one typically needs a significantly higher dimension.

The default threshold of 0 leads to fairly many features being active for each node. Often sparse feature vectors are better, and it may therefore be useful to increase the threshold beyond the default. One heuristic for choosing a good threshold is based on using the average and standard deviation of the hyperplane dot products plus with the node feature vectors. For example, one can set the threshold to the average plus two times the standard deviation. To obtain these values, run HashGNN and see the database logs where you read them off. Then you can use those values to reconfigure the threshold accordingly.

As explained above, the default value is a reasonable starting point. If using a hyperparameter tuning library, this parameter may favorably be transformed by a function with increasing derivative such as the exponential function, or a function of the type a/(b - x). The probability of selecting (and keeping throughout the iterations) a feature from different nodes depends on neighborInfluence and the number of hops to the node. Therefore, neighborInfluence should be re-tuned when iterations is changed.

In general, there is a large amount of information to store about paths containing multiple relationship types in a heterogeneous graph, so with many iterations and relationship types, a very high embedding dimension may be necessary. This is especially true for unsupervised embedding algorithms such as HashGNN. Therefore, caution should be taken when using many iterations in the heterogeneous mode.

The random seed has a special role in this algorithm. Other than making all steps of the algorithm deterministic, the randomSeed parameter determines which (to some degree) hash functions are used inside the algorithm. This is important since it greatly affects which features are sampled each iteration. The hashing plays a similar role to the (typically neural) transformations in each layer of Graph Neural Networks, which tells us something about how important the hash functions are. Indeed, one can often see a significant difference in the quality of the node embeddings output from the algorithm when only the randomSeed is different in the configuration.

For these reasons it can actually make sense to tune the random seed parameter. Note that it should be tuned as a categorical (i.e. non-ordinal) number, meaning that values 1 and 2 can be considered just as similar or different as 1 and 100. A good way to start doing this is to choose 5 - 10 arbitrary integers (eg. values 1, 2, 3, 4 and 5) as the candidates for the random seed.

randomSeed codepends on several configuration parameters, and in particular on the neighborInfluence parameter which also directly influences which hash functions are used. Therefore, if neighborInfluence is changed, likely the randomSeed parameter needs to be retuned.

First off, we will estimate the cost of running the algorithm using the estimate procedure. This can be done with any execution mode. We will use the stream mode in this example. Estimating the algorithm is useful to understand the memory impact that running the algorithm on your graph will have. When you later actually run the algorithm in one of the execution modes the system will perform an estimation. If the estimation shows that there is a very high probability of the execution going over its memory limitations, the execution is prohibited. To read more about this, see Automatic estimation and execution blocking.

For more details on estimate in general, see Memory Estimation.

In the stream execution mode, the algorithm returns the embedding for each node. This allows us to inspect the results directly or post-process them in Cypher without any side effects. For example, we can collect the results and pass them into a similarity algorithm.

For more details on the stream mode in general, see Stream.

The results of the algorithm are not very intuitively interpretable, as the node embedding format is a mathematical abstraction of the node within its neighborhood, designed for machine learning programs. What we can see is that the embeddings have four elements (as configured using binarizeFeatures.dimension).

In this example the embedding dimension becomes 1 because without binarization it is the number of features which is 1 due to the single 'hipster' property.

And as we can see, each node has at least one feature active. The density is about 50%, and no node more than two features active (limited by the embeddingDensity).

The mutate execution mode extends the stats mode with an important side effect: updating the named graph with a new node property containing the embedding for that node. The name of the new property is specified using the mandatory configuration parameter mutateProperty. The result is a single summary row, similar to stats, but with some additional metrics. The mutate mode is especially useful when multiple algorithms are used in conjunction.

For more details on the mutate mode in general, see Mutate.

The graph 'persons' now has a node property hashgnn-embedding which stores the node embedding for each node. To find out how to inspect the new schema of the in-memory graph, see Listing graphs.

Perhaps the below example is best enjoyed with a pen and paper.

Let say we have a node a with feature f1, a node b with feature f2 and a node c with features f1 and f3. The graph structure is a—​b—​c. We imagine running HashGNN for one iteration with embeddingDensity=2. For simplicity, we will assume that the hash functions return some made up numbers as we go.

During the first iteration and k=0, we compute an embedding for (a). A hash value for f1 turns out to be 7. Since (b) is a neighbor of (a), we generate a value for its feature f2 which turns out to be 11. The value 7 is sampled from a hash function which we call "one" and 11 from a hash function "two". Thus f1 is added to the new features for (a) since it has a smaller hash value. We repeat for k=1 and this time the hash values are 4 and 2, so now f2 is added as a feature to (a).

We now consider (b). The feature f2 gets hash value 8 using hash function "one". Looking at the neighbor (a), we sample a hash value for f1 which becomes 5 using hash function "two". Since (c) has more than one feature, we also have to select one of the two features f1 and f3 before considering the "winning" feature as before as input to hash function "two". We use a third hash function "three" for this purpose and f3 gets the smaller value of 1. We now compute a hash of f3 using "two" and it becomes 6. Since 5 is smaller than 6, f1 is the "winning" neighbor feature for (b), and since 5 is also smaller than 8, it is the overall "winning" feature. Therefore, we add f1 to the embedding of (b). We proceed similarly with k=1 and f1 is selected again. Since the embeddings consist of binary features, this second addition has no effect.

We omit the details of computing the embedding of (c).

After the 2 sampling rounds, the iteration is complete and since there is only one iteration, we are done. Each node has a binary embedding that contains some subset of the original binary features. In particular, (a) has features f1 and f2, (b) has only the feature f1.