Efficient and Practical Clustering of Variables in Causal Graphs
Organizations: Department of Mathematics and Statistics, FI-40014 University of Jyvaskyla, Finland
Abstract
Clustering variables in a graph may improve visual clarity and simplify causal inference. Harnessing the full potential of clustering requires an automated method to detect useful clusters in a graph. We introduce a novel class of clusters called conduits, and present a sound, complete and efficient algorithm for detecting all conduits in the graph. In addition to algorithmic detectability, conduits appear naturally in causal graphs stemming from real-world applications, enabling substantial size reduction. Furthermore, the structure of conduits enables the application of known identifiability results regarding clustering. We demonstrate these properties in a simulation study with real-world graphs.
Figures & tables
| Graph | Bidirected edges | Algorithm | All clusters | Invariant clusters | Reduction |
| PATHFINDER | none | FindConduits | 60 (42, 88) | 60 (42, 88) | 12 (11, 14) |
| FindTrClust | 2 (1, 2) | 2 (1, 2) | 2 (1, 2) | ||
| few | FindConduits | 42 (34, 59) | 42 (34, 58) | 11 (10, 12) | |
| FindTrClust | 1 (1, 2) | 1 (1, 2) | 1 (1, 2) | ||
| moderate | FindConduits | 35 (28, 44) | 34 (27, 43) | 10 (9, 11) | |
| FindTrClust | 1 (1, 2) | 1 (1, 2) | 1 (1, 2) |
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
| Graph | Algorithm | All clusters | Invariant clusters | Reduction | Time (s) |
| ALARM , | FindConduits | 28 (25, 32) | 28 (25, 32) | 14 (13, 16) | 1.4 (1.0, 1.9) |
| FindTrClust | 4 (2, 4) | 4 (2, 4) | 4 (3, 4) | 2.5 (1.7, 3.0) | |
| ARTH150 , | FindConduits | 52 (44, 59) | 52 (44, 59) | 19 (18, 21) | 8.7 (6.2, 11.3) |
| FindTrClust | 4 (2, 4) | 4 (2, 4) | 3 (2, 3) | 5.2 (3.7, 6.5) | |
| BARLEY , | FindConduits | 84 (77, 91) | 84 (77, 91) | 25 (23, 26) | 2.6 (1.6, 3.4) |
| FindTrClust | 5 (3, 5) | 5 (3, 5) | 6 (4, 6) | 6.7 (4.2, 8.3) |
| Graph | Algorithm | All clusters | Invariant clusters | Reduction | Time (s) |
| ALARM , | FindConduits | 26 (23, 29) | 23 (18, 27) | 12 (11, 14) | 0.8 (0.6, 1.0) |
| FindTrClust | 3 (2, 4) | 2 (2, 4) | 3 (2, 4) | 1.1 (0.9, 1.3) | |
| ARTH150 , | FindConduits | 42 (36, 51) | 39 (31, 48) | 17 (15, 18) | 7.8 (5.8, 10.6) |
| FindTrClust | 3 (2, 4) | 3 (2, 4) | 2 (2, 3) | 2.8 (2.1, 3.2) | |
| BARLEY , | FindConduits | 75 (68, 82) | 62 (50, 73) | 21 (19, 24) | 1.8 (1.3, 2.4) |
| FindTrClust | 3 (2, 5) | 3 (1, 5) | 5 (3, 6) | 3.3 (2.5, 3.9) |
| Graph | Algorithm | All clusters | Invariant clusters | Reduction | Time (s) |
| ALARM , | FindConduits | 25 (22, 28) | 18 (14, 23) | 11 (9, 12) | 0.3 (0.3, 0.5) |
| FindTrClust | 2 (1, 3) | 2 (1, 3) | 2 (1, 3) | 0.4 (0.3, 0.4) | |
| ARTH150 , | FindConduits | 37 (30, 43) | 31 (24, 39) | 15 (13, 17) | 9.4 (6.7, 12.7) |
| FindTrClust | 2 (1, 4) | 2 (1, 4) | 2 (1, 3) | 2.4 (1.6, 2.8) | |
| BARLEY , | FindConduits | 69 (63, 76) | 46 (37, 57) | 18 (16, 20) | 0.8 (0.6, 1.2) |
| FindTrClust | 2 (1, 4) | 2 (1, 3) | 3 (1, 5) | 1.0 (0.9, 1.1) |
Graph Clustering
Graph clustering groups network nodes by connectivity, attributes, or shared roles to reveal communities and other mesoscale structure.
See all 87 papers