So let me now tell you about position-aware
graph neural networks that are going to solve,
uh, part of the- part of the problem.
So imagine there are two types of tasks on the graphs, right?
There is what we are going to call
structure-aware tasks and there is position-aware tasks, and, again,
this is just to illustrate this concept, um,
about how graph structure may affect the underlying labels.
And in reality, in the real world, you know,
every task is a bit of a structure-aware and a bit of a
position-aware but some tasks will be more position-aware,
some will be more structure-aware,
and we'd like to have models that can operate in both regimes, right?
When structure-aware- in structure-aware tasks, uh, for example,
labeling of the nodes, uh,
for this simple, uh,
graph with two connected triangles,
if nodes are labeled according to these labels A and B here, then, um,
this is one way because the- the r- the structure
of the node and the neighborhood basically defines its label.
A different type of a task is what we call position-aware task,
where, for example, if you think about community detection,
community detection is a position-aware task right here, uh, you know,
nodes on one side have one label and nodes on
the other side have the other label even though their,
uh, uh, uh, local structures are,
uh, are comparable or iso- isomorphic, right?
Like, uh, Node 1 and Node, uh, 2,
um, they basically have the same neighborhood structure surrounding them.
So instructure-aware tasks, they should be labeled.
With the same label in position-aware,
they might be labeled with different labels because they
are in different parts, uh, of the network.
And, uh, the point is that the GNNs,
the graph neural networks,
the GCN, GraphSAGE, uh,
graph attention network, they work well for, uh, structure-aware tasks.
Right here, basically, we can differentiate v_1 and- and v_2, um,
because we are using- because they will have different,
uh, computational graphs as illustrated here, right?
v_1 has the following computation graph,
v_2 has a different computation graph just because v_2 has
three neighbors and v_1 has two neighbors even at the first hop so we are
able to distinguish them and meaning we are able to assign them different labels
because they'll have different embeddings because they have different computation graphs.
How about position-aware tasks where now we change the labeling of the nodes,
you know, let's say, according to the communities?
In this case, a plain GNN is going to fail because nodes v_1 and v_2, these, uh,
labeled here in the graph,
have the same computation graphs
because they're kind of symmetric with each other, right?
So the point is that now, um,
because they have the same computation graphs and, again,
because we are assuming there is no discriminative node feature information given to us,
the two nodes have the same, uh,
local neighborhood structure, they have the same computation graph,
which means they will be- they will have the same embedding,
which means they will- the classifier will have to assign them the same label.
Um, and in this case, we want them to,
uh, label them differently.
So the question is,
how can we extend graph neural networks,
deep learning methods that are- that would be able to, uh,
solve or work well in this, uh, you know,
toy example that kind of tries to
illustrate this notion of position-aware prediction tasks.
Um, and the key idea, uh,
for this part is the notion of an anchor
because the way you know your location is to- to know,
um, what is your position or,
uh, uh, against some reference point, right?
And we are going to call these anchors to be a reference points.
And if I know how far away from, uh,
reference points I am and you know kind of
how far away you are from different reference points,
then we can, uh, distinguish our locations.
It's almost like you wanna triangulate the position of the node inside
the graph by- by characterizing some kind of a distance to the anchor node.
So that's- that's the idea.
The idea is we wanna have a reference point, um,
and to quantify the location so we are going to use this notion of anchor,
uh, anchor nodes to give us these, uh, locations, right?
So we are going to basically pick these r- anchors at random and we are going to say,
let's pick a node,
let's say S_1 in this case, uh,
and let's call it an anchor node and then we are going to represent
the position of v_1 and v_2 by their relative distance to the, uh,
anchor node and because these two- this- the distance, uh,
of v_1 and v_2 in this case to the anchor node s_1 will be different, uh,
this basically means that we'll allow- this will allow us to
differentiate or distinguish v_1 from v_2, right?
So intuitively, the anchor node serves almost like as a reference point,
as a coordinate axis that tells us, um,
how far away from, uh,
each different nodes are and this basically allows us to, kind of,
triangulate or locate the position of the node, uh, in the graph.
Um, of course, we are not only- only going to use one anchor node,
we are actually going to use multiple anchor nodes
because if we can- if we use multiple anchor nodes,
we can better characterize the position of
a node in different region- regions on- of the graph.
So kind of if you have multiple anchor nodes,
we are able to better,
um, distinguish or, uh,
set, uh, our position.
Of course, we don't wanna have too many becomes- beco-
because then it becomes computationally hard, but, you know,
having some number of them and there is actually,
uh, a theory how many we wanna have, um,
then, uh, we can, uh,
characterize node's position in the network, uh, quite well.
Here, in this case, I- you know,
s_1 and s_2 are anchor nodes.
Um, v_1 and v_2 are nodes of interest and I'm simply saying, you know,
v_1 is one hop away from s_1 and two hops away from s_2,
while v_2 is two hops away from s_1 and one hop away from, uh, s_2.
And now, this kind of allows us to distinguish v_1 from, uh,
v_2 because they are at different distances from these, uh, anchor nodes.
Um, there is another, um,
generalization that turns out to be important is
that we don't wanna really only talk about anchor nodes,
we wanna talk about anchor sets, right?
So, uh, we are going to generalize this notion of
an anchor node from a single node to a set of nodes and then we
are going to define the distance between the node of interest and
the anchor set as the minimum distance to any of the nodes,
uh, in the anchor set, right?
Um, and the idea here is that, uh,
this will allow us to even triangulate the position of the node at
a much more fine-grained level because anchor sets will allow us,
uh, to provide more precise,
uh, position information, right?
Um, and it will allow us to keep the total number of anchors to be still small.
So what I mean by this is that, for example,
I could say, let's- let's have,
uh, now anchor sets.
I have, uh, anchor node s_1,
I have anchor node s_2,
but then also have an anchor set,
I'll denote it as s_3 that includes node v_3 and, uh, s_1.
And now, I'm going to characterize the distance of- uh,
of a given node,
uh, towards, uh, against that anchor set.
Um, and in this case,
for example, if I'm interested in position of v_3, uh,
v_3 will have a distance of 0 to the anchor set
s_3 because it is part of the anchor set while
v_2 is going to have a distance of 1 because
the closest node in the anchor set to v_1 is- is,
uh, one hop away.
Um, so, uh, what does this mean that,
um, for example, if we would, as we had before,
if I only use s_1 and s_2 as my anchor, uh,
nodes or anchor sets,
then v_3 and v- uh,
uh, v_1 cannot be differentiated with each other.
They have the same distances.
But now if I use this anchor set of Size 2,
I can actually just differentiate,
uh, v_1 and v_3.
And, again, there is a nice theory that says that it- it
is beneficial to use anchor sets of, uh,
different sizes because then the number of,
uh, anchor sets, the number of coordinates,
the number of reference points,
uh, you need, uh,
to locate a node in the graph is, uh, relatively small.
It's smaller than if you would just use, uh,
anchor nodes like s_1 and s_2 and add,
uh, multiple, uh, anchor nodes.
So what is the summary so far?
Uh, we are going to de- we have just developed
this positional encoding of a node in the graph,
where we are going to represent a node's position by
its distance to randomly selected anchor sets and each dimension in this,
um, in this, uh,
encoding will, uh, tell me the, uh,
the- will be tied to a given anchor set and will be
the minimum distance from a node of interest to any of the nodes in the anchor set.
Uh, that is the- that is the idea of how we are going to,
uh, uh, create this,
uh, positional, uh, encoding.
Now, uh, before I move on and use- how this position information is used,
the way- of course,
you can ask how many of these sets do you need and how big they need to be?
And what we are going to do is we are going to do the following.
We are going to have an e- expone- er,
anchor sets of exponentially increasing size,
but we are going to use exponentially fewer of them, right?
So we will have a lot of, uh,
anchor sets of Size 1,
we'll have half that number of anchor sets of Size 2,
we'll have, you know, uh,
half of that number of anchor sets of Size 4,
Size 8, Size 16, and so on.
Um, so this- this means we'll have, you know,
some relatively small number of anchor sets where
each next anchor set size is going to be doubled,
but the number of them will be half of what we had before.
And that's usually a good way how to generate these, uh,
anchor sets and the- the nodes that belong to anchor sets,
we simply select them, uh,
uniformly, uh, at random.
And then we charac- as I said, we characterize, uh,
this positional encoding of a node by simply the minimum distance from the node to the,
uh, any of the nodes,
uh, in the given, uh, anchor set.
So now, how do we use this positional information?
A simple way of using
the positional information is to use it as an augmented node feature.
And this works really well- well in practice.
So basically, we just enrich the feature descript- descriptor of a node with this,
uh, positional information, uh,
characterized by the shortest path distance,
uh, to the anchor sets.
Uh, the issue here is that since
each posi- dimension of position encoding is tied to a random anchor,
dimensions of positional encoding,
um, can be randomly permuted and the encoding, uh, could be,
uh, basically is semantically the same meaning,
um, er, er, without changing it- its meaning.
So, uh, and- and what this means, uh,
imagine you permute the input dimensions of a normal, uh, er, uh,
er, neural network, the output will, uh, change.
So what is, um,
what is a more rigorous solution than just using these positional encodings as they are
is to design a special set of neural network operators that can maintain this,
uh, permutational invariant property of positional encoding.
So basically, uh, that- the position encoding is order invariant,
which you can achieve through,
let's say, some kind of, uh,
some aggregator or, um,
uh, aggregators that are uh, order invariant.
Uh, because, uh, permuting the input feature dimension
will only result in the permutation of the ou- output dimension,
uh, but the value of each dimension shouldn't change.
And, uh, you know, there is a paper, er,
that introduces position-aware graph neural networks, uh,
to say how you can do this in a more rigorous way but the key here is this notion of
an anchor and the notion that you can
quantify the position of a node in the graph by the distance,
uh, to the anchor and that allows us to now improve the expressiveness of
graph neural networks because nodes won't
only know what is their local neighborhood structure around them,
but they will also know what is their location,
uh, or position, uh,
in the neural network.