Order of edges in FeaturedGraph

Specific Domains Machine Learning
1

Hi,

I am trying to understand FeaturedGraph from GraphSignals.jl. I am puzzled with the documentation, which says that features of edges are stored in matrix, where each column corresponds to a feature of one edge, but the documentation does not say, how edges are ordereded. I have created a workarround, where I first create a FeaturedGraph without any features and then iterate over edges to figure out the order.

using GraphSignals, Graphs
N = 4
ug = Graph(N)
add_edge!(ug, 1, 2); add_edge!(ug, 1, 3); add_edge!(ug, 1, 4);
add_edge!(ug, 2, 3); add_edge!(ug, 3, 4);
epmap = Dict([e => i for (i,e) in enumerate(edges(ug))])
fg = FeaturedGraph(ug)
ef = zeros(Float32, 5, ne(ug));
for (i, (vi, vj)) in edges(fg)
	e = (vi < vj) ? Edge(vi, vj) : Edge(Int64(vj), Int64(vi))
	ef[epmap[e], i] = 1
end
fg = FeaturedGraph(ug; ef)

But this construction seems to me a bit bizarre and I would consider it to be more like a work-around rather than a proper construction. Does someone knows the answer?

Thanks a lot in advance.
Tomas

2 
julia> using GraphSignals, Graphs

julia> N = 4
4

julia> ug = Graph(N)
{4, 0} undirected simple Int64 graph

julia> add_edge!(ug, 1, 2); add_edge!(ug, 1, 3); add_edge!(ug, 1, 4);

julia> add_edge!(ug, 2, 3); add_edge!(ug, 3, 4);

julia> fg = FeaturedGraph(ug)
FeaturedGraph:
	Undirected graph with (#V=4, #E=5) in adjacency matrix

julia> edgeidx, dst, src = collect(edges(fg))
(UInt32[0x00000001, 0x00000002, 0x00000004, 0x00000001, 0x00000003, 0x00000002, 0x00000003, 0x00000005, 0x00000004, 0x00000005], UInt32[0x00000002, 0x00000003, 0x00000004, 0x00000001, 0x00000003, 0x00000001, 0x00000002, 0x00000004, 0x00000001, 0x00000003], UInt32[0x00000001, 0x00000001, 0x00000001, 0x00000002, 0x00000002, 0x00000003, 0x00000003, 0x00000003, 0x00000004, 0x00000004])

julia> edge_index(graph(fg), 1, 2)
0x00000001

collect(edges(fg)) could collect all the index of edges and edges in pair of vertices. You can use to index edge features.
For specific edge, there is edge_index available for SparseGraph in order to get the edge index from a pair of vertex indices.

3

This is similar to solution we did. I was wondering if we can get the indicies of edges without constructing the FeaturedGraph, because we need those indices to construct feature matrix for edges. Or, is construction of FeaturedGraph so cheap, that it does not matter?

Thanks for reply.

4

I think it’s cheap to construct FeaturedGraph for taking indices for edge features.
It costs O(N) time, where N is number of nodes, for constructing FeaturedGraph from graph objects from JuliaGraphs, so maybe not cost much time when graph size is lower than or around thousnad.

1 Like
5

Thanks.