Overview

The Induced Subgraph algorithm is used to compute the induced subgraph of a given set of nodes in a graph. It provides a way to focus on the immediate connections and gain insights into the local structure and interactions within the selected subset of nodes.

Concepts

Induced Subgraph

An induced subgraph includes only the nodes from the given set and the edges that connect those nodes.

As this example shows, when specifying node set S = {A, B, I, K, L, M, N}, the induced subgraph is the graph whose node set is S and whose edge set contains all edges that have both endpoints in S.

Ultipa's Induced Subgraph algorithm returns all the 1-step paths in the induced subgraph.

Considerations

• The Induced Subgraph algorithm ignores the direction of edges but calculates them as undirected edges.

Example Graph

To create this graph:

// Runs each row separately in order in an empty graphset
create().edge_property(@default, "score", int32)
insert().into(@default).nodes([{_id:"A"}, {_id:"B"}, {_id:"C"}, {_id:"D"}, {_id:"E"}, {_id:"F"}, {_id:"G"}, {_id:"H"}, {_id:"I"}])
insert().into(@default).edges([{_from:"A", _to:"B", score:2}, {_from:"C", _to:"A", score:3}, {_from:"E", _to:"C", score:2}, {_from:"E", _to:"A", score:4}, {_from:"C", _to:"D", score:2}, {_from:"D", _to:"A", score:2}, {_from:"D", _to:"A", score:3}, {_from:"F", _to:"G", score:3}, {_from:"G", _to:"G", score:5}, {_from:"F", _to:"I", score:2}, {_from:"H", _to:"G", score:1}])

Creating HDC Graph

To load the entire graph to the HDC server hdc-server-1 as hdc_subgraph:

CALL hdc.graph.create("hdc-server-1", "hdc_subgraph", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
})

hdc.graph.create("hdc_subgraph", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
}).to("hdc-server-1")

Parameters

Algorithm name: subgraph

File Writeback

CALL algo.subgraph.write("hdc_subgraph", {
  params: {
    return_id_uuid: "id",
    ids: ['A','C','D','G']
  },
  return_params: {
    file: {
      filename: "paths"
    }
  }
})

algo(subgraph).params({
  projection: "hdc_subgraph",
  return_id_uuid: "id",
  ids: ['A','C','D','G']
}).write({
  file: {
    filename: "paths"
  }
})

Result:

_id
C--[102]--A
D--[107]--A
D--[106]--A
C--[105]--D
G--[109]--G

Full Return

CALL algo.subgraph("hdc_subgraph", {
  params: {
    return_id_uuid: "id",
    ids: ['A','C','D','G']
  },
  return_params: {}
}) YIELD r
RETURN r

exec{
  algo(subgraph).params({
    return_id_uuid: "id",
    ids: ['A','C','D','G']
  }) as r
  return r
} on hdc_subgraph

Result:

Stream Return

CALL algo.subgraph("hdc_subgraph", {
  params: {
    return_id_uuid: "id",
    ids: ['F','G']
  },
  return_params: {
    stream: {}
  }
}) YIELD p
FOR e1 IN pedges(p)
MATCH ()-[e2 WHERE e2._uuid = e1._uuid]->()
RETURN max(e2.score)

exec{
  algo(subgraph).params({
    return_id_uuid: "id",
    ids: ['F','G']
  }).stream() as p
  uncollect pedges(p) as e1
  find().edges({_uuid == e1._uuid}) as e2
  return max(e2.score)
} on hdc_subgraph

Result: 5