Repository: graspologic-org/graspologic-native (language: python)

Issue:
"Invalid" starting communities fails
Our Leiden implementation allows you to provide a starting dictionary of node -> communities. 

The problem that @JonathanLarson found is that if you provide a community dictionary with nodes that have no direct edge relationship to anything in that community, the algorithm as-is falls apart. Leiden's enhancement to Louvain guarantees that partitions/clusters will only be made up of nodes that have some connection to each other - meaning that every node in that partition MUST contain an edge to another node in that partition - with the noted exception of clusters with only a single node.

We presumed that this would always be true within our leiden impl, but we didn't guarantee it if a user provided us a starting community mapping.  By happenstance @JonathanLarson was running leiden repeatedly over monthly snapshots of nodes and using the previous month's partitions as a starting point for generating the new partitions.  We ran into the one and only `panic! at the macro` in graspologic native because while two nodes were in this partition, they did not share an edge, and thus the subnetwork was "empty".


Discussion / hints:

Fix patch:
diff --git a/packages/network_partitions/src/leiden/leiden.rs b/packages/network_partitions/src/leiden/leiden.rs
index 31cef05..9e15474 100644
--- a/packages/network_partitions/src/leiden/leiden.rs
+++ b/packages/network_partitions/src/leiden/leiden.rs
@@ -1,11 +1,12 @@
 // Copyright (c) Microsoft Corporation.
 // Licensed under the MIT license.
 
+use std::collections::{HashMap, HashSet};
 use std::iter;
 
 use rand::Rng;
 
-use crate::clustering::Clustering;
+use crate::clustering::{ClusterItem, Clustering};
 use crate::errors::CoreError;
 use crate::log;
 use crate::network::prelude::*;
@@ -81,6 +82,9 @@ where
 
     let mut clustering: Clustering =
         clustering.unwrap_or(Clustering::as_self_clusters(network.num_nodes().clone()));
+
+    guarantee_clustering_sanity(network, &mut clustering)?;
+
     let mut improved: bool = false;
 
     log!(
@@ -230,9 +234,74 @@ fn initial_clustering_for_induced(
     return Clustering::as_defined(clusters_induced_network, next_cluster_id);
 }
 
+fn guarantee_clustering_sanity(
+    network: &CompactNetwork,
+    clustering: &mut Clustering,
+) -> Result<(), CoreError> {
+    // verify initial clustering provided is in a sane state for leiden to operate
+    // any node in a cluster must either be a singleton in that cluster or be connected to at least
+    // one other node in that cluster
+    let mut node_neighbors: HashMap<CompactNodeId, HashSet<CompactNodeId>> = HashMap::new();
+    for CompactNodeItem { id: node, .. } in network.into_iter() {
+        let mut neighbors: HashSet<CompactNodeId> = HashSet::new();
+        for neighbor in network.neighbors_for(node) {
+            neighbors.insert(neighbor.id);
+        }
+        node_neighbors.insert(node, neighbors);
+    }
+    let mut cluster_membership: HashMap<ClusterId, HashSet<CompactNodeId>> = HashMap::new();
+    for ClusterItem { node_id, cluster } in clustering.into_iter() {
+        let cluster_members: &mut HashSet<CompactNodeId> =
+            cluster_membership.entry(cluster).or_insert(HashSet::new());
+        cluster_members.insert(node_id);
+    }
+
+    for (_cluster, cluster_members) in &cluster_membership {
+        if cluster_members.len() > 1 {
+            // we are only trying to move non-singletons if they don't have a possible connection
+            for cluster_member in cluster_members {
+                let neighbors = node_neighbors.get(cluster_member).unwrap();
+                if neighbors.is_disjoint(cluster_members) {
+                    // we have no reason to be in this partition, because we have no links to anyone
+                    // else in it. we should make our own partition, with ___ and ___.
+                    let new_cluster: ClusterId = clustering.next_cluster_id();
+                    clustering.update_cluster_at(*cluster_member, new_cluster)?;
+                }
+            }
+        }
+    }
+    return Ok(());
+}
+
 #[cfg(test)]
 mod tests {
     use super::*;
+    use super::{LabeledNetwork, LabeledNetworkBuilder};
+
+    // todo: this is common to LabeledNetwork and here, and probably should just be written in one place?
+    fn edge_list() -> Vec<Edge> {
+        let edges: Vec<Edge> = vec![
+            ("a".into(), "b".into(), 2.0),
+            ("a".into(), "d".into(), 1.0),
+            ("a".into(), "e".into(), 1.0),
+            ("b".into(), "a".into(), 2.0),
+            ("b".into(), "c".into(), 6.0),
+            ("b".into(), "e".into(), 1.0),
+            ("b".into(), "f".into(), 4.0),
+            ("b".into(), "g".into(), 3.0),
+            ("c".into(), "b".into(), 6.0),
+            ("c".into(), "g".into(), 3.0),
+            ("d".into(), "a".into(), 1.0),
+            ("d".into(), "h".into(), 11.0),
+            ("e".into(), "a".into(), 1.0),
+            ("e".into(), "b".into(), 1.0),
+            ("f".into(), "b".into(), 4.0),
+            ("g".into(), "b".into(), 3.0),
+            ("g".into(), "c".into(), 3.0),
+            ("h".into(), "d".into(), 11.0),
+        ];
+        return edges;
+    }
 
     #[test]
     fn test_initial_clustering_for_induced() {
@@ -246,4 +315,36 @@ mod tests {
         assert_eq!(actual, expected);
         assert_eq!(actual.num_nodes(), 20);
     }
+
+    #[test]
+    fn test_guarantee_clustering_sanity() {
+        let edges = edge_list();
+        let mut builder: LabeledNetworkBuilder<String> = LabeledNetworkBuilder::new();
+        let labeled_network: LabeledNetwork<String> = builder.build(edges.into_iter(), true);
+        let compact_network: &CompactNetwork = labeled_network.compact();
+        let mut clustering: Clustering = Clustering::as_self_clusters(compact_network.num_nodes());
+        // node 'a' and node 'h' do not share an edge
+        let a_compact = labeled_network.compact_id_for("a".into()).unwrap();
+        let h_compact = labeled_network.compact_id_for("h".into()).unwrap();
+        clustering
+            .update_cluster_at(a_compact, clustering.next_cluster_id())
+            .expect("Updating this known cluster for a should work");
+        clustering
+            .update_cluster_at(h_compact, clustering[a_compact])
+            .expect("Updating this known cluster for h should work");
+        clustering.remove_empty_clusters();
+        assert_eq!(clustering[a_compact], clustering[h_compact]);
+        guarantee_clustering_sanity(&compact_network, &mut clustering)
+            .expect("guarantee clustering sanity should not throw an error");
+        assert_ne!(clustering[a_compact], clustering[h_compact]);
+        let isolate_clusters: Vec<ClusterId> = vec![clustering[a_compact], clustering[h_compact]];
+        let mut isolates: HashSet<ClusterId> = HashSet::new();
+        isolates.extend(isolate_clusters);
+        clustering
+            .into_iter()
+            .filter(|item| item.node_id != a_compact && item.node_id != h_compact)
+            .for_each(|item| {
+                assert!(!isolates.contains(&item.cluster));
+            })
+    }
 }
diff --git a/packages/pyo3/Cargo.toml b/packages/pyo3/Cargo.toml
index bd009d0..91590ed 100644
--- a/packages/pyo3/Cargo.toml
+++ b/packages/pyo3/Cargo.toml
@@ -1,6 +1,6 @@
 [package]
 name = "graspologic_native"
-version = "1.0.1"
+version = "1.1.0"
 authors = ["dwpryce@microsoft.com"]
 edition = "2018"
 license = "MIT"
@@ -8,8 +8,8 @@ description = "Python native companion module to the graspologic library"
 readme = "README.md"
 
 [package.metadata.maturin]
-maintainer = "Dwayne Pryce"
-maintainer-email = "dwpryce@microsoft.com"
+maintainer = "Dax Pryce"
+maintainer-email = "daxpryce@microsoft.com"
 requires-python = ">=3.6,<3.11"
 project-url = {"Github" = "https://github.com/microsoft/graspologic-native", "Graspologic"="https://github.com/microsoft/graspologic"}
 classifier = ["Development Status :: 3 - Alpha", "License :: OSI Approved :: MIT License", "Programming Language :: Python :: Implementation :: CPython", "Programming Language :: Python :: 3.6", "Programming Language :: Python :: 3.7", "Programming Language :: Python :: 3.8", "Programming Language :: Python :: 3.9", "Topic :: Scientific/Engineering :: Mathematics"]
diff --git a/packages/pyo3/src/lib.rs b/packages/pyo3/src/lib.rs
index 9de6499..f568ab3 100644
--- a/packages/pyo3/src/lib.rs
+++ b/packages/pyo3/src/lib.rs
@@ -102,9 +102,6 @@ impl PyObjectProtocol for HierarchicalCluster {
 /// :rtype: Dict[str, int]
 /// :raises ClusterIndexingError:
 /// :raises EmptyNetworkError:
-/// :raises InvalidCommunityMappingError: The starting communities dictionary either did not include
-///     a community for each node in the edge list or the edge list did not contain a node present
-///     in the starting community mapping.
 /// :raises InternalNetworkIndexingError: An internal algorithm error. Please report with reproduction steps.
 /// :raises ParameterRangeError: One of the parameters provided did not meet the requirements in the documentation.
 /// :raises UnsafeInducementError: An internal algorithm error. Please report with reproduction steps.
@@ -197,9 +194,6 @@ fn leiden(
 /// :rtype: List[HierarchicalCluster]
 /// :raises ClusterIndexingError:
 /// :raises EmptyNetworkError:
-/// :raises InvalidCommunityMappingError: The starting communities dictionary either did not include
-///     a community for each node in the edge list or the edge list did not contain a node present
-///     in the starting community mapping.
 /// :raises InternalNetworkIndexingError: An internal algorithm error. Please report with reproduction steps.
 /// :raises ParameterRangeError: One of the parameters provided did not meet the requirements in the documentation.
 /// :raises UnsafeInducementError: An internal algorithm error. Please report with reproduction steps.
diff --git a/packages/pyo3/src/mediator.rs b/packages/pyo3/src/mediator.rs
index 2c03aa2..c22b76d 100644
--- a/packages/pyo3/src/mediator.rs
+++ b/packages/pyo3/src/mediator.rs
@@ -188,29 +188,36 @@ fn communities_to_clustering(
     network: &LabeledNetwork<String>,
     communities: HashMap<String, usize>,
 ) -> Result<Clustering, PyLeidenError> {
-    // if node not found in internal network, bounce
-    // if max(communities) > len(set(communities)), collapse result
-    // if all nodes are mapped, cool
-    // if not all nodes are mapped, generate integers for each new value
-
-    let mut clustering: Clustering = Clustering::as_self_clusters(network.num_nodes());
-
-    let mut all_communities: HashSet<usize> = HashSet::new();
+    // best effort for using a provided community mapping and keeping generated singleton ids
+    // otherwise
+
+    let mut clustering: Clustering = match communities.values().max() {
+        Some(max_community_id) => {
+            // if we have values, we have the max community id, which means we'll actually create
+            // a cluster mapping where every node gets a singleton cluster starting after the actual
+            // last max cluster.
+            let mut cluster_mapping: Vec<usize> = Vec::with_capacity(network.num_nodes());
+            let start: usize = max_community_id + 1;
+            let end: usize = start + network.num_nodes();
+            cluster_mapping.extend(start..end);
+            Clustering::as_defined(cluster_mapping, end)
+        }
+        None => Clustering::as_self_clusters(network.num_nodes()),
+    };
 
     for (node, community) in communities {
-        all_communities.insert(community);
-        let mapped_node: CompactNodeId = network
-            .compact_id_for(node)
-            .ok_or(PyLeidenError::InvalidCommunityMappingError)?;
-        clustering
-            .update_cluster_at(mapped_node, community)
-            .map_err(|_| PyLeidenError::InvalidCommunityMappingError)?;
+        let mapping: Option<CompactNodeId> = network.compact_id_for(node);
+        if mapping.is_some() {
+            let compact_node_id: CompactNodeId = mapping.unwrap();
+            clustering
+                .update_cluster_at(compact_node_id, community)
+                .map_err(|_| PyLeidenError::ClusterIndexingError)?;
+        }
     }
 
-    if clustering.next_cluster_id() != all_communities.len() {
-        // we have some gaps, compress
-        clustering.remove_empty_clusters();
-    }
+    // we can't easily know if there are empty clusters, so we'll just presume there are
+    // and compress any gaps
+    clustering.remove_empty_clusters();
 
     return Ok(clustering);
 }


Test patch:
diff --git a/packages/pyo3/tests/test_leiden.py b/packages/pyo3/tests/test_leiden.py
index b5fea5e..c8a245b 100644
--- a/packages/pyo3/tests/test_leiden.py
+++ b/packages/pyo3/tests/test_leiden.py
@@ -1,14 +1,15 @@
 import os
-import graspologic_native as gpn
+import graspologic_native as gcn
 import unittest
 
 sbm_graph = os.path.join("..", "network_partitions", "tests", "sbm_network.csv")
+simple_path = os.path.join("..", "network_partitions", "tests", "simple_org_graph.csv")
 seed = 12345
 
 
-def _get_edges():
+def _get_edges(path):
   edges = []
-  with open(sbm_graph, "r") as sbm_graph_io:
+  with open(path, "r") as sbm_graph_io:
     for line in sbm_graph_io:
       source, target, weight = line.strip().split(",")
       edges.append((source, target, float(weight)))
@@ -17,8 +18,8 @@ def _get_edges():
 
 class TestLeiden(unittest.TestCase):
     def test_leiden(self):
-        edges = _get_edges()
-        modularity, partitions = gpn.leiden(edges, seed=seed)
+        edges = _get_edges(sbm_graph)
+        modularity, partitions = gcn.leiden(edges, seed=seed)
 
     def test_reiterative_leiden(self):
         """
@@ -31,9 +32,37 @@ def test_reiterative_leiden(self):
 
         So instead we just test that the modularity and partitions produced where trials=10 is superior
         """
-        edges = _get_edges()
-        single_modularity, single_partitions = gpn.leiden(edges, seed=seed)
+        edges = _get_edges(sbm_graph)
+        single_modularity, single_partitions = gcn.leiden(edges, seed=seed)
 
-        repetitive_modularity, repetitive_partitions = gpn.leiden(edges, seed=seed, trials=10)
+        repetitive_modularity, repetitive_partitions = gcn.leiden(edges, seed=seed, trials=10)
         self.assertTrue(single_modularity < repetitive_modularity)
 
+    def test_provided_clusters(self):
+        edges = _get_edges(simple_path)
+        # this graph has two connected components, so first we'll try it with a reasonable clustering, and then we'll
+        # try it with an invalid clustering
+        communities = {
+            "dwayne": 0,
+            "nick": 0,
+            "jon": 0,
+            "carolyn": 0,
+            "bryan": 0,
+            "patrick": 0,
+            "chris": 1,
+            "david": 1,
+            "amber": 1,
+            "nathan": 1
+        }
+
+        gcn.leiden(edges, starting_communities=communities, seed=seed) # we just want to make sure it runs, not
+        # inspect values
+
+        # this is a bug we found, and we're testing for it
+        communities["dwayne"] = 2
+        communities["nathan"] = 2
+        # these two have no edges, and shouldn't really be in the same community as per leiden, but they can
+        # absolutely be put in there due to other reasons, so we should presume it's possible
+
+        _, partitions = gcn.leiden(edges, starting_communities=communities, seed=seed)
+        self.assertNotEqual(partitions["dwayne"], partitions["nathan"])