Induced Subgraph

Overview

The Induced Subgraph algorithm computes the subgraph formed by a given set of nodes and the edges connecting them within the original graph. This enables focused analysis of local structure and interactions, providing insights into the immediate connections among the selected 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 1-step paths in the induced subgraph.

Considerations

• The Induced Subgraph algorithm treats all edges as undirected, ignoring their original direction.

Example Graph

Run the following statements on an empty graph to define its structure and insert data:

GQLUQL
ALTER EDGE default ADD PROPERTY {
  score int32
};
INSERT (A:default {_id: "A"}),
       (B:default {_id: "B"}),
       (C:default {_id: "C"}),
       (D:default {_id: "D"}),
       (E:default {_id: "E"}),
       (F:default {_id: "F"}),
       (G:default {_id: "G"}),
       (H:default {_id: "H"}),
       (I:default {_id: "I"}),
       (A)-[:default {score: 2}]->(B),
       (C)-[:default {score: 3}]->(A),
       (E)-[:default {score: 2}]->(C),
       (E)-[:default {score: 4}]->(A),
       (C)-[:default {score: 2}]->(D),
       (D)-[:default {score: 2}]->(A),
       (D)-[:default {score: 3}]->(A),
       (F)-[:default {score: 3}]->(G),
       (G)-[:default {score: 5}]->(G),
       (F)-[:default {score: 2}]->(I),
       (H)-[:default {score: 1}]->(G);

Creating HDC Graph

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

GQLUQL
CREATE HDC GRAPH my_hdc_graph ON "hdc-server-1" OPTIONS {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static"
}

Parameters

Algorithm name: subgraph

File Writeback

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

Result:

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

Full Return

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

Result:

Stream Return

UQL
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 my_hdc_graph

Result: 5