Breaking Cycles in Noisy Hierarchies - Description
Taxonomy graphs that capture hyponymy or meronymy relationships through directed edges are expected to be acyclic. However, in practice, they may have thousands of cycles, as they are often created in a crowd-sourced way. Since these cycles represent logical fallacies, they need to be removed for many web applications. In this paper, we address the problem of breaking cycles while preserving the logical structure (hierarchy) of a directed graph as much as possible. Existing approaches for this problem either need manual intervention or use heuristics that can critically alter the taxonomy structure. In contrast, our approach infers graph hierarchy using a range of features, including a Bayesian skill rating system and a social agony metric. We also devise several strategies to leverage the inferred hierarchy for removing a small subset of edges to make the graph acyclic. Extensive experiments demonstrate the effectiveness of our approach.
Keywords: Directed Acyclic Graph, Graph Hierarchy, TrueSkill, Social Agony, Cycle Edges
- Last update: 14, July, 2017
- Corresponding Paper: Breaking Cycles in Noisy Hierarchies
- The 9th International ACM Web Science Conference 2017, WebSci'17
- If you use this code, please consider to cite this paper: BibTex Download
- Author Homepage
It's worth mentioning that this code has been used in "Project Ruprecht", developed by Wikimedia Foundation. The project aims to measure the tangledness of PHP code and provides clean codebase. Thanks for Daniel Kinzler (Principal Software Engineer, Wikimedia Foundation) for letting us know that our work can not only fix messy ontologies but also works well for cleaning up messy codebase. updated: 2019.05.10.
0. Requirements
- Python 2.7
- Lib: networkx 1.1/2.x
If you have ran errors like DiGraph has no attributes of nodes_iter() or edges_iter(), please changes nodes_iter() to list(nodes()) and edges_iter() to list(edges()).
Please go to networkx to see differences between different version of networkx.
1. Generate Random Graphs (DAGs)
python generate_random_dag.py -n 300 -m 2500 -g data/gnm_300_2500.edges
- n: number of nodes
- m: number of edges
- g: file path used to save the generated random graph
2. Introduce Cycles to DAG
python introduce_cycles_to_DAG.py -g data/gnm_300_2500.edges -k 300 -l 0
- -g: target DAG edges list file
- -k: number of extra edges introduced to make DAG have cycles
- -l: threshold to control path length, if l <=0, no constraints on path length, else: path length < l (cycle length <= l)
output:
- extra_edges_file (Ground Truth Edges): gnm_300_2500_extra_300_path_len_0.edges
- graph_with_extra_edges_file : gnm_300_2500_graph_w_extra_300_path_len_0.edges
3. Breaking Cycles by DFS
python remove_cycle_edges_by_dfs.py -g data/gnm_300_2500_graph_w_extra_300_path_len_0.edges
You can specificity a edges list of file as ground truth (edges should be removed to break cycles) by using '-t'. It will report precision, recall and F-1 score.
python remove_cycle_edges_by_dfs.py -g data/gnm_300_2500_graph_w_extra_300_path_len_0.edges -t data/gnm_300_2500_extra_300_path_len_0.edges
Performance will be:
4. Breaking Cycles by MFAS
Local greedy implementation of Minimum feedback arc set problem.
python remove_cycle_edges_by_minimum_feedback_arc_set_greedy.py -g data/gnm_300_2500_graph_w_extra_300_path_len_0.edges
You can specificity a edges list of file as ground truth (edges should be removed to break cycles) by using '-t'. It will report precision, recall and F-1 score.
python remove_cycle_edges_by_minimum_feedback_arc_set_greedy.py -g data/gnm_300_2500_graph_w_extra_300_path_len_0.edges -t data/gnm_300_2500_extra_300_path_len_0.edges
5. Breaking Cycles via Hierarchy, inferred by PageRank
Graph hierarchy is inferred from PageRank.
python remove_cycle_edges_by_hierarchy.py -s pagerank -g data/gnm_300_2500_graph_w_extra_300_path_len_0.edges
- -s pagerank: use pagerank to infer graph hierarchy
You can also specify the ground truth file path as ground_truth_edges_file by using '-t'
python remove_cycle_edges_by_hierarchy.py -s pagerank -g data/gnm_300_2500_graph_w_extra_300_path_len_0.edges -t data/gnm_300_2500_extra_300_path_len_0.edges
6. Breaking Cycles via Hierarchy, inferred by TrueSkill
- External Library Requirement: TrueSkill install
python remove_cycle_edges_by_hierarchy.py -g data/gnm_300_2500_graph_w_extra_300_path_len_0.edges -s trueskill
- -s trueskill: use TrueSkill to infer graph hierarchy
You can also specify the ground truth file path as ground_truth_edges_file by using '-t'.
python remove_cycle_edges_by_hierarchy.py -g data/gnm_300_2500_graph_w_extra_300_path_len_0.edges -s trueskill -t data/gnm_300_2500_extra_300_path_len_0.edges
It will report performance of TS_G, TS_B, TS_F, and TS_Voting (ensembling of TS_G, TS_B and TS_F).
7. Breaking Cycles via Hierarchy, inferred by SocialAgony
The code for computing Social Agony has been put in /agony. You have to compile it first. To compile it sucessfully, you may have to install some packages. Detailes can be viewed at /agony/README.md.
Social Agony computation code is from Tatti
After that run:
python remove_cycle_edges_by_hierarchy.py -g data/gnm_300_2500_graph_w_extra_300_path_len_0.edges -s socialagony
- -s socialagony: use SocialAgony to infer graph hierarchy
You can also specify the ground truth file path as ground_truth_edges_file by using '-t'.
python remove_cycle_edges_by_hierarchy.py -g data/gnm_300_2500_graph_w_extra_300_path_len_0.edges -s socialagony -t data/gnm_300_2500_extra_300_path_len_0.edges
It will report performance of SA_G, SA_B, SA_F, and SA_Voting (ensembling of SA_G, SA_B and SA_F).
8. Breaking Cycles via Hierarchy, Ensembling Approach
Ensembling TS_G, TS_B, TS_F, SA_G, SA_B and SA_F.
python remove_cycle_edges_by_hierarchy.py -g data/gnm_300_2500_graph_w_extra_300_path_len_0.edges -s ensembling
- -s ensembling: ensembling all above 6 apprpaches
You can also specify the ground truth file path as ground_truth_edges_file by using '-t'.
python remove_cycle_edges_by_hierarchy.py -g data/gnm_300_2500_graph_w_extra_300_path_len_0.edges -s ensembling -t data/gnm_300_2500_extra_300_path_len_0.edges
- This can also report performances of TS_G, TS_B, TS_F, SA_G, SA_B and SA_F individually, these performance may have slightly difference with running them individually.
- It can report performance of H_Voting (ensembling of SA_G, SA_B, SA_F, TS_G, TS_B and TS_F)
9. Test on Synthetic Graphs
Instead of testing above methods individually, you can simply run below code to compare performance of all methods on Synthetic Graphs (random generated graphs).
python synthetic_performance.py --dir data/ -n 300 -m 2500 -k 300 -l 0
- --dir: directory to save all results, 'data/' is in current directory
- -n: number of nodes in the generated random graph
- -m: number of edges in the generated random graph
- -k: number of extra edges to introduce cycles to the generated random graph
- -l: control parameter of path length
It will do:
- generate a random DAG with n nodes and m edges
- introduce k extra edges to this DAG to make it have cycles (l is used to control generated cycle size, if l == 0, it has no constraints on cycle size)
- run all methods to break cycles and report performance
10. Test on Real Datasets
If you already have a graph with cycles, you can run:
python break_cycles.py -g data/gnm_300_2500_graph_w_extra_300_path_len_0.edges
- -g data/gnm_300_2500_graph_w_extra_300_path_len_0.edges : to specify edgeslist file
And if you have ground truth, you can run below commands to report performances:
python break_cycles.py -g data/gnm_300_2500_graph_w_extra_300_path_len_0.edges -t data/gnm_300_2500_extra_300_path_len_0.edges
- -t data/gnm_300_2500_extra_300_path_len_0.edges : to specify ground truth of edges to be removed
11. Visualization
Visualize peroformance of different methods.
python plot_recallPrecision.py --input data/performance.txt --title "RG(1.5K,15K)"
- --input data/performance.txt
file format:
method_name precision recall f-1Score(optional) numEdgesRemoved(optional)
(columns are separated by whitespace)
First 3 columns must be: method_name, precision, and recall.
Other columns are optional, such as f-1score and numEdgesRemoved in data/performance.txt.
- --title "RG(1.5K,15K)": file will be saved at: performance_RG(1.5K,15K).pdf
For example, we test algorithms on a random graph (1500,15000) with 500 extra edges added, and get performance saved as:
DFS 0.0140 0.1820 0.0259 6516
PR 0.2298 0.7400 0.3507 1610
MFAS 0.4464 0.9320 0.6036 1044
SA_G 0.8993 0.9640 0.9305 536
SA_F 0.5946 0.9620 0.7349 809
SA_B 0.5975 0.9680 0.7389 810
SA_Voting 0.9282 0.9560 0.9419 515
TS_G 0.8274 0.9300 0.8757 562
TS_F 0.5145 0.9580 0.6695 931
TS_B 0.5010 0.9700 0.6608 968
TS_Voting 0.8654 0.9260 0.8947 535
H_Voting 0.9369 0.9500 0.9434 507
- first column, such as DFS: method name
- second column, such as 0.0140: precision
- third column, such as 0.1820: recall
- forth column, such as 0.0259: f-1 score (optional, will compute f-1 automatically)
- fifth column, such as 1044: number of edges to be removed
visualization will be saved as: performance_RG(1.5K,15K).pdf
Licence and Acknowledgement
BSD Licence.
This work is supported by the National Science Foundation of United States under grant CCF-1645599 and IIS-1550302. All content represents the opinion of the authors, which is not necessarily shared or endorsed by their respective employers and/or sponsors.
Cite
If you use this code, please consider to cite this paper:
@inproceedings{Sun:2017:BCN:3091478.3091495,
author = {Sun, Jiankai and Ajwani, Deepak and Nicholson, Patrick K. and Sala, Alessandra and Parthasarathy, Srinivasan},
title = {Breaking Cycles In Noisy Hierarchies},
booktitle = {Proceedings of the 2017 ACM on Web Science Conference},
series = {WebSci '17},
year = {2017},
isbn = {978-1-4503-4896-6},
location = {Troy, New York, USA},
pages = {151--160},
numpages = {10},
url = {http://doi.acm.org/10.1145/3091478.3091495},
doi = {10.1145/3091478.3091495},
acmid = {3091495},
publisher = {ACM},
address = {New York, NY, USA},
keywords = {cycle edges, directed acyclic graph, graph hierarchy, social agony, trueskill},
}