> For the complete documentation index, see [llms.txt](https://csse-uwa.gitbook.io/data-warehousing-lab-sheets/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://csse-uwa.gitbook.io/data-warehousing-lab-sheets/week-12-graph-data-science.md).

# Week 12 - Graph Data Science

{% hint style="info" %}
We recommend attempting to install Neo4j Desktop to do this lab if possible, as it makes things a bit easier. If you are not able to use Neo4j Desktop you can try

<https://sandbox.neo4j.com/>

and create a Graph Data Science sandbox. Please be aware that this sandbox **will expire in 3 days after creation.**
{% endhint %}

## A. Search Algorithms

**Scenario**: Siri is currently in Arad, and she wants to drive to Bucharest.

<figure><img src="https://374096590-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FE6tM8okJTaOtct7O9mvr%2Fuploads%2F4iaI8DByGiXIF79Vo51w%2Fimage.png?alt=media&amp;token=bf9fecaf-040d-4cf5-a7b0-1ab264b6314e" alt=""><figcaption></figcaption></figure>

{% hint style="warning" %}
Your Turn:&#x20;

1. What is the solution for BFS?
2. What is the solution for A\*? The heuristic function is the straight-line distance to Bucharest.
   {% endhint %}

## B. Neo4j

Now, let's play with the search functions in Neo4j. In the lecture, the demo graph version is 5.3.0 with Graph Data Science Library is 2.4.6.&#x20;

### Dataset

The dataset we are using is a database of countries. Each country has a `latitude` and `longitude`, and are connected by a "road" with a `distance property` (just like the transport graph from the lectures, though this one is `ROAD` rather than `EROAD` and is much larger).

{% file src="/files/J1UECei7Y4AgmNik4rQz" %}

{% file src="/files/bxkNbemuBjlCdGs9mEAA" %}

* `countries.csv`: Each row represents a country, with a `country_code`, `latitude`, `longitude`, and `name`.
* `roads.csv`: Each row connects `country_1` with `country_2` and stores the `distance` between them (in km).

The dataset is sourced from both Google and Wikipedia:

* Country data was sourced from [Google](https://developers.google.com/public-data/docs/canonical/countries_csv). Some minor preprocessing was done on some of the country names to convert them to the same names in Wikipedia.
* Roads data was generated via a Python script. To do this we obtained a list of bordering countries from [Wikipedia](https://en.wikipedia.org/wiki/List_of_countries_and_territories_by_land_borders), did some cleaning/preprocessing etc, and used the `geopy` Python library to calculate the geodesic distance between each bordering country.

Please note the data may not be completely accurate and is just for demonstration purposes.

### Task 1. Creating a graph DB and enabling Graph Data Science <a href="#id-2.-creating-a-graph-db-and-enabling-graph-data-science" id="id-2.-creating-a-graph-db-and-enabling-graph-data-science"></a>

First, create a new instance for this week in Neo4j. Once you've created it, you'll need to activate the Graph Data Science (GDS) plugin.

<figure><img src="https://374096590-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FE6tM8okJTaOtct7O9mvr%2Fuploads%2FVIJW3ArTYxubhdvEaZ2T%2Fimage.png?alt=media&amp;token=4c776282-deba-4bc4-a60c-a34e073ac9ef" alt=""><figcaption></figcaption></figure>

The Graph Data Science library should be in the plugins list - click on it, then click "Install".

<figure><img src="https://374096590-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FE6tM8okJTaOtct7O9mvr%2Fuploads%2F0VNyT1O2hi5OI5cVXXT5%2Fimage.png?alt=media&amp;token=6b670550-a5c6-49b2-ae4d-625df54429ff" alt=""><figcaption></figcaption></figure>

After installing, restart the instance.

### Task 2. Exploring the data and loading it into Neo4j <a href="#id-3.-exploring-the-data-and-loading-it-into-neo4j" id="id-3.-exploring-the-data-and-loading-it-into-neo4j"></a>

Before we run any graph data science algorithms, we need to load our data into Neo4j. Remember, you'll need to place the csv files into the `import` directory of your Neo4j database.

Next, you'll need to write `LOAD CSV` statements to import both countries and roads into your database. Here is one for countries to get you started:

```cypher
// LOAD DATA FROM CSV
LOAD CSV WITH HEADERS FROM "file:///countries.csv" AS row
CREATE (c:Country)
SET c.country = row.country,
    c.name = row.name,
    c.latitude = toFloat(row.latitude),
    c.longitude = toFloat(row.longitude)
```

Note how we have converted `row.latitude` and `row.longitude` to floats - this is important, otherwise Neo4j will treat them as strings.

{% hint style="warning" %}
Your turn: write a `LOAD CSV` statement that imports the roads into your database. Remember, the Countries have already been created, so after `LOAD CSV` you'll need to run a `MATCH` statement to find the countries listed in each row of `roads.csv`, and only `CREATE` a road between those two countries. Don't forget the `distance` property, which should also be a **float**.
{% endhint %}

### Task 3. Projecting our graph for GDS <a href="#id-4.-projecting-our-graph-for-gds" id="id-4.-projecting-our-graph-for-gds"></a>

Before we can run any GDS algorithms, we must first *project* our graph for the Graph Data Science library. Here is the syntax for the projection:

<pre class="language-cypher"><code class="lang-cypher">// PROJECT GRAPH FOR GDS
CALL gds.graph.project("Countries", "Country",
    { ROAD: {orientation: "UNDIRECTED"} },
<strong>    { relationshipProperties: "distance",
</strong>    nodeProperties: ["latitude", "longitude"] }
    )
</code></pre>

* The first argument, "Countries", is the name of our GDS graph.
* The second argument, "Country", is the name of the node label types we want to project.
* The third argument specifies options for the relationships. In this case, we want the `ROAD` relationship to be undirected (as roads are two-way).
* The fourth argument specifies the properties that we want to include in our GDS graph. We need the `distance` property from the road relationships, and the `latitude` and `longitude` from the countries, for the pathfinding algorithms.

Note: If you ever need to delete your projection and start over, you can run:

```
// DELETE GRAPH
CALL gds.graph.drop("Countries")
```

### Task 4: Running Graph Data Science Algorithms

### 4.1 Breath First Search and Depth First Search

Let's try running the Breadth First Search and Depth First Search algorithms on our data.

Here is an example BFS query:

```cypher
// BFS
MATCH (source: Country {name: "Spain"})
CALL gds.bfs.stream("Countries", {
    sourceNode: source
    })
YIELD path
RETURN path
```

Try running this query in Neo4j. If the resulting graph visualisation looks a bit messy because of the roads between countries, uncheck the `connect result nodes` option in the Options list and run the query again. You should see multiple Country nodes connected by an orange relationship called `NEXT`.

{% hint style="warning" %}
Your turn: change the query to be a depth-first search (DFS) and run it. Are the results the same, or different - and why?
{% endhint %}

### 4.2 **A\* Source-target Shortest Path** <a href="#id-6.-running-some-pathfinding-algorithms" id="id-6.-running-some-pathfinding-algorithms"></a>

{% hint style="warning" %}
Your turn: try running the A\* source-target shortest path algorithm to find the shortest path between Spain and India. You can see the syntax in the lecture slides or read the following documentation page:
{% endhint %}

{% embed url="<https://neo4j.com/docs/graph-data-science/current/algorithms/astar/>" %}

Now try deleting the `relationshipWeightProperty: "distance"` line in the query and run the algorithm again. Has the shortest path changed now that the algorithm is fully relying on a heuristic?

### **4.3 Minimum Spanning Tree**

The final algorithm we'll be running today is Minimum Spanning Tree (MST), which starts from a given node and finds all its reachable nodes and the set of relationships that connect the nodes together with the minimum possible weight.

Here's the syntax for MST taken from Neo4j documentation:

{% embed url="<https://neo4j.com/docs/graph-data-science/current/algorithms/minimum-weight-spanning-tree/>" %}

```cypher
//Minimum Spanning Tree Example
MATCH (n:Place{id: 'D'})
CALL gds.beta.spanningTree.write('graph', {
  startNode: id(n),
  relationshipWeightProperty: 'cost',
  writeRelationshipType: 'MINST',
  writeProperty: 'writeCost'
})
YIELD preProcessingMillis, computeMillis, writeMillis, effectiveNodeCount
RETURN preProcessingMillis,computeMillis, writeMillis, effectiveNodeCount;
```

{% hint style="warning" %}
Your turn: Create relationships of the type `MINST` between Canada and every country reachable from Canada. Write a Cypher query to display the minimum spanning tree. Hint: the relationship type is `MINST`, not `ROAD`!.
{% endhint %}