Individual Fairness in Graph Decomposition
Authors: Kamesh Munagala, Govind S. Sankar
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We perform experiments on real-world planar graphs modeling precinct connectivity in redistricting applications in the states of North Carolina, Maryland, and Pennsylvania in the United States. |
| Researcher Affiliation | Academia | 1Computer Science Department, Duke University, Durham NC 27708-0129, USA. Correspondence to: Kamesh Munagala <kamesh@cs.duke.edu>, Govind S. Sankar <govind.subash.sankar@duke.edu>. |
| Pseudocode | Yes | The paper includes several clearly labeled algorithm blocks: 'Algorithm 1 KPR Decomposition (Klein et al., 1993)', 'Algorithm 2 KPR algorithm with random vertex weights', 'Algorithm 3 KPR algorithm with two cuts per phase', 'Algorithm 4 KPR algorithm with random diameter', and 'Algorithm 5 LDD via Euclidean Embedding'. |
| Open Source Code | No | The paper does not contain an explicit statement or a link indicating that the source code for the described methodology is publicly available. While it mentions the MGGG Lab GitHub for data, it does not offer code for their algorithms. |
| Open Datasets | Yes | We perform experiments on real-world planar graphs modeling precinct connectivity in redistricting applications in the states of North Carolina, Maryland, and Pennsylvania in the United States. [...] MGGG Lab. Mggg state shapefiles. https://github.com/mggg-states. Accessed January 2024. |
| Dataset Splits | No | The paper does not explicitly provide training/test/validation dataset splits (e.g., percentages, sample counts, or references to predefined splits) for reproducing the experiments. The experiments are conducted on entire graph datasets rather than split portions. |
| Hardware Specification | No | The paper states 'We implemented Algorithm 2' and 'We ran experiments' but does not provide any specific details about the hardware used, such as GPU/CPU models, memory, or cloud resources. |
| Software Dependencies | No | The paper does not list specific software dependencies with version numbers (e.g., 'Python 3.8', 'PyTorch 1.9', 'CPLEX 12.4') that would be necessary to replicate the experiments. |
| Experiment Setup | Yes | We implemented Algorithm 2 with parameter R = 5 and compared it with Algorithm 1 with the same R. We plot the histograms of the edge separation probabilities in Figure 2, showing clearly that Algorithm 2 is more individually fair than Algorithm 1. [...] We plot the number of clusters for 200 runs in Figure 3, and note that the empirically observed value is consistently smaller than n/R. [...] In our experiments, we choose the roots for the BFS trees uniformly at random. |