Repository: alibaba/GraphScope (language: python)

Issue:
[BUG] wrong result of clustering function
**Describe the bug**
I use `nx.clustering(G)` to compute the clustering coefficient value. But the result is wrong (even negative).

**To Reproduce**
```python
import graphscope
import graphscope.nx as nx
# import networkx as nx

G = nx.Graph()
G.add_nodes_from([1,2,3])
G.add_edges_from([(1,2),(2,3),(3,1)])
print(nx.clustering(G))
print(nx.average_clustering(G))
```
the result is
```
{1: -4.0, 2: -4.0, 3: -4.0}
-4.0
```
but expected result is
```
{1: 1.0, 2: 1.0, 3: 1.0}
1.0
```

**Screenshots**
![image](https://github.com/alibaba/GraphScope/assets/54880260/a752fabc-69ed-4dde-973c-1747fccba644)


**Environment (please complete the following information):**
 - GraphScope version: 0.27.0
 - OS: Linux
 - Version: Red Hat 4.8.5-44

[BUG] wrong result of clustering function
**Describe the bug**
I use `nx.clustering(G)` to compute the clustering coefficient value. But the result is wrong (even negative).

**To Reproduce**
```python
import graphscope
import graphscope.nx as nx
# import networkx as nx

G = nx.Graph()
G.add_nodes_from([1,2,3])
G.add_edges_from([(1,2),(2,3),(3,1)])
print(nx.clustering(G))
print(nx.average_clustering(G))
```
the result is
```
{1: -4.0, 2: -4.0, 3: -4.0}
-4.0
```
but expected result is
```
{1: 1.0, 2: 1.0, 3: 1.0}
1.0
```

**Screenshots**
![image](https://github.com/alibaba/GraphScope/assets/54880260/a752fabc-69ed-4dde-973c-1747fccba644)


**Environment (please complete the following information):**
 - GraphScope version: 0.27.0
 - OS: Linux
 - Version: Red Hat 4.8.5-44



Discussion / hints:
Thanks for opening your first issue here! Be sure to follow the issue template! And a maintainer will get back to you shortly!
Please feel free to contact us on [DingTalk](https://h5.dingtalk.com/circle/healthCheckin.html?dtaction=os&corpId=dingb4b76e0fa9ccd8d516fd0f0acdf19f55&68e71190=0fe34ec0&cbdbhh=qwertyuiop), WeChat account(graphscope) or [Slack](http://slack.graphscope.io/). We are happy to answer your questions responsively.

triangle number `print(nx.triangles(G))` is correct:
```
{1: 1, 2: 1, 3: 1}
```
hi, @Spockkk0225, thanks for the report, I will take a look.
https://github.com/alibaba/GraphScope/blob/82a4ea6b393f3bc70fd0da0c24c1bdcf936d2338/analytical_engine/apps/clustering/clustering.h#L29-L30

the clustering seems to only support directed graph, I will try to implement for both directed and undirected graph.

the alternative solution would raise error if the graph is undirected in python client.
Thanks for opening your first issue here! Be sure to follow the issue template! And a maintainer will get back to you shortly!
Please feel free to contact us on [DingTalk](https://h5.dingtalk.com/circle/healthCheckin.html?dtaction=os&corpId=dingb4b76e0fa9ccd8d516fd0f0acdf19f55&68e71190=0fe34ec0&cbdbhh=qwertyuiop), WeChat account(graphscope) or [Slack](http://slack.graphscope.io/). We are happy to answer your questions responsively.

triangle number `print(nx.triangles(G))` is correct:
```
{1: 1, 2: 1, 3: 1}
```
hi, @Spockkk0225, thanks for the report, I will take a look.
https://github.com/alibaba/GraphScope/blob/82a4ea6b393f3bc70fd0da0c24c1bdcf936d2338/analytical_engine/apps/clustering/clustering.h#L29-L30

the clustering seems to only support directed graph, I will try to implement for both directed and undirected graph.

the alternative solution would raise error if the graph is undirected in python client.

Fix patch:
diff --git a/analytical_engine/apps/clustering/clustering.h b/analytical_engine/apps/clustering/clustering.h
index 1daf5605c0cc..6d22d62a2ba7 100644
--- a/analytical_engine/apps/clustering/clustering.h
+++ b/analytical_engine/apps/clustering/clustering.h
@@ -26,8 +26,8 @@ limitations under the License.
 
 namespace gs {
 /**
- * @brief An implementation of Clustering Coefficient for vertices, which only
- * works on directed graphs. For undirected graphs, see grape::LCC.
+ * @brief An implementation of Clustering Coefficient for vertices. Support both
+ * directed and undirected graph.
  *
  * This app inherits ParallelAppBase. Messages can be sent in
  * parallel to the evaluation. This strategy improve performance by overlapping
@@ -56,8 +56,12 @@ class Clustering
     messages.InitChannels(thread_num());
     ctx.stage = 0;
     ForEach(inner_vertices, [&messages, &frag, &ctx](int tid, vertex_t v) {
-      ctx.global_degree[v] =
-          frag.GetLocalOutDegree(v) + frag.GetLocalInDegree(v);
+      if (frag.directed()) {
+        ctx.global_degree[v] =
+            frag.GetLocalOutDegree(v) + frag.GetLocalInDegree(v);
+      } else {
+        ctx.global_degree[v] = frag.GetLocalOutDegree(v);
+      }
       if (ctx.global_degree[v] > 1) {
         messages.SendMsgThroughEdges<fragment_t, int>(
             frag, v, ctx.global_degree[v], tid);
@@ -97,12 +101,15 @@ class Clustering
             auto u = e.get_neighbor();
             is_rec[u.GetValue()]++;
           }
-          es = frag.GetIncomingAdjList(v);
-          for (auto& e : es) {
-            auto u = e.get_neighbor();
-            is_rec[u.GetValue()]++;
-            if (is_rec[u.GetValue()] == 2) {
-              ctx.rec_degree[v]++;
+
+          if (frag.directed()) {
+            es = frag.GetIncomingAdjList(v);
+            for (auto& e : es) {
+              auto u = e.get_neighbor();
+              is_rec[u.GetValue()]++;
+              if (is_rec[u.GetValue()] == 2) {
+                ctx.rec_degree[v]++;
+              }
             }
           }
 
@@ -136,21 +143,11 @@ class Clustering
             }
           }
 
-          es = frag.GetIncomingAdjList(v);
-          for (auto& e : es) {
-            auto u = e.get_neighbor();
-            if (ctx.global_degree[u] < ctx.global_degree[v]) {
-              std::pair<vid_t, uint32_t> msg;
-              msg.first = frag.Vertex2Gid(u);
-              if (is_rec[u.GetValue()] == 1) {
-                msg.second = 1;
-                msg_vec.push_back(msg);
-                nbr_vec.push_back(std::make_pair(u, 1));
-              }
-            } else if (ctx.global_degree[u] == ctx.global_degree[v]) {
-              u_gid = frag.Vertex2Gid(u);
-              v_gid = frag.GetInnerVertexGid(v);
-              if (v_gid > u_gid) {
+          if (frag.directed()) {
+            es = frag.GetIncomingAdjList(v);
+            for (auto& e : es) {
+              auto u = e.get_neighbor();
+              if (ctx.global_degree[u] < ctx.global_degree[v]) {
                 std::pair<vid_t, uint32_t> msg;
                 msg.first = frag.Vertex2Gid(u);
                 if (is_rec[u.GetValue()] == 1) {
@@ -158,6 +155,18 @@ class Clustering
                   msg_vec.push_back(msg);
                   nbr_vec.push_back(std::make_pair(u, 1));
                 }
+              } else if (ctx.global_degree[u] == ctx.global_degree[v]) {
+                u_gid = frag.Vertex2Gid(u);
+                v_gid = frag.GetInnerVertexGid(v);
+                if (v_gid > u_gid) {
+                  std::pair<vid_t, uint32_t> msg;
+                  msg.first = frag.Vertex2Gid(u);
+                  if (is_rec[u.GetValue()] == 1) {
+                    msg.second = 1;
+                    msg_vec.push_back(msg);
+                    nbr_vec.push_back(std::make_pair(u, 1));
+                  }
+                }
               }
             }
           }
@@ -251,7 +260,12 @@ class Clustering
         } else {
           int degree =
               global_degree[v] * (global_degree[v] - 1) - 2 * rec_degree[v];
-          ctx_data[v] = degree == 0 ? 0.0 : 1.0 * tricnt[v] / degree;
+          // Refer to https://en.wikipedia.org/wiki/Clustering_coefficient
+          if (frag.directed()) {
+            ctx_data[v] = degree == 0 ? 0.0 : 1.0 * tricnt[v] / degree;
+          } else {
+            ctx_data[v] = degree == 0 ? 0.0 : 2.0 * tricnt[v] / degree;
+          }
         }
       }
     }


Test patch:
diff --git a/python/graphscope/nx/algorithms/tests/builtin/test_cluster.py b/python/graphscope/nx/algorithms/tests/builtin/test_cluster.py
index 5f14199d97d4..115605228b5e 100644
--- a/python/graphscope/nx/algorithms/tests/builtin/test_cluster.py
+++ b/python/graphscope/nx/algorithms/tests/builtin/test_cluster.py
@@ -130,6 +130,81 @@ def test_triangle_and_edge(self):
         assert nx.builtin.clustering(G)[0] == 1.0 / 6.0
 
 
+@pytest.mark.usefixtures("graphscope_session")
+class TestClustering:
+    @classmethod
+    def setup_class(cls):
+        pytest.importorskip("numpy")
+
+    def test_clustering(self):
+        G = nx.Graph()
+        assert list(nx.builtin.clustering(G).values()) == []
+        assert nx.builtin.clustering(G) == {}
+
+    def test_path(self):
+        G = nx.path_graph(10)
+        assert list(nx.builtin.clustering(G).values()) == [
+            0,
+            0,
+            0,
+            0,
+            0,
+            0,
+            0,
+            0,
+            0,
+            0,
+        ]
+        assert nx.builtin.clustering(G) == {
+            0: 0,
+            1: 0,
+            2: 0,
+            3: 0,
+            4: 0,
+            5: 0,
+            6: 0,
+            7: 0,
+            8: 0,
+            9: 0,
+        }
+
+    def test_cubical(self):
+        G = nx.cubical_graph()
+        assert list(nx.builtin.clustering(G).values()) == [0, 0, 0, 0, 0, 0, 0, 0]
+        assert nx.builtin.clustering(G, 1) == 0
+        assert list(nx.builtin.clustering(G, [1, 2]).values()) == [0, 0]
+        assert nx.builtin.clustering(G, 1) == 0
+        assert nx.builtin.clustering(G, [1, 2]) == {1: 0, 2: 0}
+
+    def test_k5(self):
+        G = nx.complete_graph(5)
+        assert list(nx.builtin.clustering(G).values()) == [1, 1, 1, 1, 1]
+        assert nx.builtin.average_clustering(G) == 1
+        G.remove_edge(1, 2)
+        assert list(nx.builtin.clustering(G).values()) == [
+            5 / 6,
+            1,
+            1,
+            5 / 6,
+            5 / 6,
+        ]
+        assert nx.builtin.clustering(G, [1, 4]) == {1: 1, 4: 0.83333333333333337}
+
+    def test_k5_signed(self):
+        G = nx.complete_graph(5)
+        assert list(nx.builtin.clustering(G).values()) == [1, 1, 1, 1, 1]
+        assert nx.builtin.average_clustering(G) == 1
+        G.remove_edge(1, 2)
+        G.add_edge(0, 1, weight=-1)
+        assert list(nx.builtin.clustering(G, weight="weight").values()) == [
+            1 / 6,
+            -1 / 3,
+            1,
+            3 / 6,
+            3 / 6,
+        ]
+
+
 @pytest.mark.usefixtures("graphscope_session")
 class TestDirectedWeightedClustering:
     def test_clustering(self):
diff --git a/python/graphscope/nx/tests/test_ctx_builtin.py b/python/graphscope/nx/tests/test_ctx_builtin.py
index 889ab3af1f8e..b7526b29aed4 100644
--- a/python/graphscope/nx/tests/test_ctx_builtin.py
+++ b/python/graphscope/nx/tests/test_ctx_builtin.py
@@ -245,6 +245,13 @@ def test_clustering(self):
         ans = nx.builtin.clustering(self.p2p)
         self.assert_result_almost_equal(ans, self.p2p_clus_ans)
 
+    def test_clustering_undirected(self):
+        # test undirected graph
+        G = nx.Graph()
+        G.add_nodes_from([1, 2, 3])
+        G.add_edges_from([(1, 2), (2, 3), (3, 1)])
+        nx.builtin.clustering(G) == {1: 1.0, 2: 1.0, 3: 1.0}
+
     def test_triangles(self):
         ans = nx.builtin.triangles(self.p2p_undirected)
         self.assert_result_almost_equal(ans, self.p2p_triangles_ans)