Edge update by edges toward the tail node

[Nokimann]

The basic MessagePassing in Pyg helps update a node by connected edges and nodes.
But updating edge by other edges doesn't seem to be easy.

I'm looking for an easy way to update edge e_ji by using the edge features and indices of e_kj toward e_ji in a directed graph:

nodes: (k), (j), and (i)
edges: k->j and j->i (and their edge_attr)

(k)->(j)->(i)

Alternatively, finding predecessor nodes of (j), which is (k)s in the above graph.

[rusty1s]

You can perform MessagePassing on the LineGraph to achieve that.

[Nokimann]

@rusty1s Thank you a lot!

This is the clue for me.

And, I can think of a example more,

For a graph: a-b-c-d

We may get the k-th order hop connections by doing 1 to (k-1) LineGraph times?

[rusty1s]

Yes, that should work :)

[Nokimann]

I found another way from MXMNet

edge_index = torch.tensor([[0, 1, 1, 2, 2, 3, 2, 4, 3, 4],
                           [1, 0, 2, 1, 3, 2, 4, 2, 4, 3]], dtype=torch.long)
num_nodes=5
row, col = edge_index
value = torch.arange(row.size(0), device=row.device)
adj = SparseTensor(row=row, col=col, value=value,
                     sparse_sizes=(num_nodes, num_nodes))
adj_col = adj[col]

print(adj_col.storage.row()) # k->j
print(adj_col.storage.value()) # j->i (or j->k)

tensor([0, 0, 1, 2, 2, 2, 3, 3, 4, 4, 5, 5, 5, 6, 6, 7, 7, 7, 8, 8, 9, 9])
tensor([1, 2, 0, 3, 4, 6, 1, 2, 5, 8, 3, 4, 6, 7, 9, 3, 4, 6, 7, 9, 5, 8])

But cannot understood the adj_col = adj[col] part. What actually SparseTensor does with iterable indices, [col]?

---

@rusty1s

Using LineGraph, I found the directional information (order of indices) is not maintained.

Define directional graph because I need the directed info. (k)->(j)->(I) (not undirected info. i.e., k-j-i)

edge_index = torch.tensor([[0, 1, 1, 2, 2, 3, 2, 4, 3, 4],
                           [1, 0, 2, 1, 3, 2, 4, 2, 4, 3]], dtype=torch.long)
edge_attr = torch.transpose(edge_index, 0, 1)
#x = torch.tensor([[0], [1], [2], [3], [4]])
data = Data(edge_index=edge_index, num_nodes=5, edge_attr=edge_attr)
print(data)
print(data.is_undirected())

line_graph = LineGraph()
data_l = line_graph(data)
data_l

print(data_l.edge_index)
row, col = data_l.edge_index
print(torch.cat([data_l.x[row], data_l.x[col]], dim=-1))

which showing

Data(edge_index=[2, 10], edge_attr=[10, 2], num_nodes=5)
False
tensor([[0, 0, 1, 2, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 6, 7, 7, 8, 8, 8, 9, 9],
        [1, 2, 0, 3, 4, 5, 1, 2, 6, 7, 8, 9, 3, 4, 5, 8, 9, 3, 4, 5, 6, 7]])
tensor([[0, 1, 1, 0],
        [0, 1, 1, 2],
        [1, 0, 0, 1],
        [1, 2, 2, 1],
        [1, 2, 2, 3],
        [1, 2, 3, 2],
        [2, 1, 1, 0],
        [2, 1, 1, 2],
        [2, 3, 2, 4],
        [2, 3, 4, 2],
        [3, 2, 3, 4],
        [3, 2, 4, 3],
        [2, 4, 2, 1],
        [2, 4, 2, 3],
        [2, 4, 3, 2],
        [4, 2, 3, 4],
        [4, 2, 4, 3],
        [3, 4, 2, 1],
        [3, 4, 2, 3],
        [3, 4, 3, 2],
        [4, 3, 2, 4],
        [4, 3, 4, 2]])

I expected that the 2nd and 3rd columns must be the same.

[rusty1s]

Currently, for directed graphs, two edges are connected if their intersection is not empty, i.e. they share a common node. I think your desired condition only holds for undirected graphs. The code you listed above is an alternative formulation to get the line graph. Here, adj[col] means that we are indexing adj in the first dimension via col, resulting in an adjacency matrix shape of [num_edges, num_nodes].