PyGOD for community detection on large similarity graphs

[kinsvater]

Hello PyGOD community,

I have a graph of roughly 1 Mio nodes and a function, which assigns a similarity score between any two nodes. I create an edge between two nodes if that function scores above a threshold, say, T=0.5. Scores below that threshold result in disconnected pairs (no edge). This way, I end up with a graph consisting of tens of thousands of small connected components.

The problem is that this function is an estimate and some of the connections are false positives (in classification terms). I want to detect those false positives by flagging them as anomalies and removing them. A typical false positive looks like in the illustration below:

I want to detect those reds like the one between nodes (x, y), and remove them so that this single connected component is split into two. Those two typically are densely connected components A and B.

Now my question:

• Considering the size of the graph, what would be your go-to class of algorithms to detect such anomalous edges?
• My preference would be to start with simple (and fast) sacrificing detection quality. Which ones would you recommend specifically?

Many thanks,
Paul

[kayzliu]

Thank you for your interest to PyGOD. Currently, most of the algorithms in PyGOD are still focusing on detecting anomalies at node level. Although we provide some utility function pygod.utils.to_edge_score to convert the node level score to edge level score, its detection capability is not fully tested.

In your case, the anomalies are somewhat similar to contextual anomalies we defined in our benchmark paper. Based on the results shown in the paper, GCNAE is good at detecting this type of anomalies. You may try pygod.detector.GAE along with pygod.utils.to_edge_score. A simpler solution may be pygod.detector.SCAN, a non-deep cluster-based detector. However, instead of using the decision_score_, hub_score_ may be more accurate in your scenario.

[kinsvater]

Many thanks for the response.

The "contextual outlier" is somewhat similar to my situation as it detects dissimilar neighboring nodes. It is different from mine, because I typically do not have those outlier nodes surrounded by otherwise similar nodes.

Your answer is still helpful as I am more convinced now that graph outlier detection is not the right tool for this job. I will head over to community detection on graphs.

Thanks!