Best Structure-based Node Features

[bardia-esmaeili]

Hello,

I have a set of directed graphs, each belonging to a single class out of 4 possible classes. I want to classify and also perform anomaly detection techniques on these graphs. There are no node-based or edge-based features, so I've relied on the following structure-based features measured by networkx for each node:
input degree, output degree, betweenness centrality, closeness centrality, and eigenvector centrality.
The reason for choosing these features is that they seemed to be the prominent features used by the community. My questions are as follows:

1. Networkx returns the normalized version of the features for each graph individually (e.g. the node degrees are divided by the number of nodes in that graph). I am not quite sure if that is a good idea. I assume that for two given nodes in two different graphs with similar local structures, the features should have similar values, but by dividing the value by the number of nodes in each graph we are scaling the features differently, resulting in distinct measurements. Isn't that right?
   If you think that this is not a good idea, should I pass the features unnormalized (e.g. input degree = 50 for a node), or should I do normalization in a different manner? if so, what normalization approach would you suggest?

(edit: I think that I definitely need to perform some sort of normalization since for some nodes the value of betweenness reaches 60,000 :) )

2. Are there any other node-level or even graph-level features that you have in mind which could help better differentiate between graphs from different classes?

Thank you

[rusty1s]

1. I think this is correct. In particular, I think your GNN model should ideally perform well agnostic to graph size. In my experience, node degree is best passed as a one-hot encoding (similar to transforms.OneHotDegree). If the number of neighbors is high such that one-hot encodings are infeasible, you can also consider bucketing them together, e.g., on a logarithmic scale. For other measures, e.g., betweenness centrality, I think it is important to normalize them based on all node value in all graphs.
2. I think this looks pretty good. You can draw more ideas from our LocalDegreeProfile transform.

[bardia-esmaeili]

1. After going through the graphs, it seems that the maximum number of neighbors is around 200.
   1.1. Can't we scale the node degree values by the maximum degree, just like the instance you mentioned for betweenness centrality? I mean is it not okay to do something similar for all of these features?
   1.2 Also between scaling by the maximum value among all nodes in a single graph or the maximum value among all nodes in all graphs, which do you think could work better?
2. This indeed seems like a really good feature.

[rusty1s]

1. Yes, sure you can do that, but the GNN will have a harder time to make more fine-grained decisions for nearly identical node degrees.
   1.2. This is hard to tell and depends on the task, probably a good idea to test out both. I would probably go for standard normalization though instead of min-max scaling.

[bardia-esmaeili]

I see. Now, I have just two remaining questions:

1. By standard normalization you mean X = (X - X_min)/ (X_max - X_min) or X = (X - mean) / std ?
2. Could you elaborate a bit on how that bucketing and logarithmic scale approach that you mentioned works or point me to a resource that I could learn about it more and whether it is supported in PyG?