The f-Adjusted Graph Laplacian: a Diagonal Modification with a Geometric Interpretation
Authors: Sven Kurras, Ulrike Luxburg, Gilles Blanchard
ICML 2014 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We demonstrate this effect in an image segmentation task. The classical spectral clustering for image data on a d-dimensional grid (Shi & Malik, 2000) constructs an r-graph of radius r on the pixel positions. Figure 1 (bottom right) shows that this leads to the correct segmentation, whereas the biased segmentation provided by the original graph is not correct (bottom left). Consider the example in Figure 2. It shows two Gaussians (top left) that are underrepresented around x = 0 due to bias b(x, y) = min{1, (2 + 3|x|)/8} (top right). The minimum normalized cut of a graph built on the biased sample is misdirected by this bias to the wrong vertical clusters (middle left). However, the f-adjustment appropriately repairs the volumes and cut weights in the graph. Now the correct horizontal cut is revealed (bottom left). to illustrate this anomaly, we consider in Figure 3 the density p : [0, 1]2 -> R, p(x, y) = 2x. Let G = (V, E, W) denote the 200-NN graph built on 5000 sample points drawn from p with Gaussian weighted edges (sigma = 0.03). |
| Researcher Affiliation | Academia | Sven Kurras KURRAS@INFORMATIK.UNI-HAMBURG.DE Ulrike von Luxburg LUXBURG@INFORMATIK.UNI-HAMBURG.DE Department of Computer Science, University of Hamburg, Germany Gilles Blanchard GILLES.BLANCHARD@MATH.UNI-POTSDAM.DE Department of Mathematics, University of Potsdam, Germany |
| Pseudocode | No | The paper describes procedures in a step-by-step manner (e.g., in Section 2.1) but does not present them in a structured pseudocode block or algorithm format. |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code or links to a code repository for the methodology described. |
| Open Datasets | No | The paper describes using sample points for illustrative examples (e.g., "5000 sample points drawn from two Gaussians" or "5000 sample points drawn from p with Gaussian weighted edges"), but it does not specify a publicly available dataset with concrete access details (e.g., link, DOI, or formal citation with author/year for a benchmark dataset) for reproducibility. |
| Dataset Splits | No | The paper describes experimental results based on sample points but does not specify any training, validation, or test dataset splits (e.g., percentages, sample counts, or predefined split references). |
| Hardware Specification | No | The paper does not specify any hardware details (e.g., CPU, GPU, or cloud computing instance types) used for running the experiments. |
| Software Dependencies | No | The paper does not provide specific software dependencies with version numbers (e.g., libraries, frameworks, or operating systems) used for the experiments. |
| Experiment Setup | Yes | Consider a neighborhood graph, for example a k-nearest neighbor graph, that is constructed on sample points drawn according to some density p. Edge weights are defined by the products wij := sims(xi, xj) simv(ti, tj) of spatial similarities sims(xi, xj) := exp( 0.5 xi xj 2/σ2 s) and value similarities simv(ti, tj) := exp( 0.5 ti tj 2/σ2 v). Let G = (V, E, W) denote the 200-NN graph built on 5000 sample points drawn from p with Gaussian weighted edges (σ = 0.03). |