🤖 AI

Graph-Based Floor Separation Using Node Embeddings and Clustering of WiFi Trajectories

This paper presents a fully data-driven, graph-based framework that achieves blind vertical floor separation in multistory buildings by modeling Wi-Fi fingerprint trajectories as nodes, learning structural embeddings via Node2Vec, and applying K-Means clustering with automatic cluster estimation, all without requiring prior building metadata.

Original authors: Rabia Yasa Kostas, Kahraman Kostas

Published 2026-02-03

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Rabia Yasa Kostas, Kahraman Kostas

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are walking through a massive, multi-story shopping mall. You have no GPS signal, no map, and no idea which floor you are on. The Wi-Fi signals bouncing off the walls and furniture look almost identical whether you are on the 3rd floor or the 4th floor. This is the "vertical localization" problem: figuring out which floor you are on just by listening to Wi-Fi signals.

This paper proposes a clever, data-driven way to solve this puzzle without needing a building blueprint or knowing how many floors exist beforehand. Here is how they did it, explained simply:

1. The Problem: The "Signal Soup"

In big buildings, Wi-Fi signals are messy. They leak through floors, bounce off glass atriums, and get confused by furniture. If you just look at the signal strength at one single moment, it's like trying to guess which room you are in a house by smelling a single drop of coffee; it's too vague.

2. The Solution: Turning Signals into a "Social Network"

Instead of looking at signals one by one, the authors treat the whole journey as a social network.

The Nodes (People): Every time the phone records a Wi-Fi signal, it's like a person at a party.
The Edges (Friendships): If you walked from one spot to another, those two signals are "friends." If two signals are very similar (even if you didn't walk between them), they are also "friends."

By connecting all these signals, they build a giant map of friendships (a graph).

3. The Magic Trick: "Learning the Vibe" (Node2Vec)

Once they have this giant map, they use a technique called Node2Vec. Think of this as a detective who walks around the party, observing who hangs out with whom.

Instead of just looking at who is standing next to whom, the detective learns the "vibe" of different groups.
People on the 3rd floor might hang out in a specific circle, while people on the 4th floor hang out in a different circle, even if the room looks the same.
The algorithm turns these complex social circles into simple, short "ID cards" (vectors) that capture the essence of the floor.

4. Grouping the Clues (Clustering)

Once everyone has an "ID card," the computer uses a simple sorting tool (K-Means) to group people who have similar ID cards.

The Result: All the "3rd-floor people" end up in one pile, and all the "4th-floor people" end up in another.
The Cool Part: The computer figures out how many piles there are automatically. It doesn't need to be told, "There are 5 floors." It just looks at the data and says, "Ah, I see 5 distinct groups."

5. The Test: Did it Work?

The authors tested this on two different real-world datasets (one from a university challenge and one from a famous research benchmark).

The Comparison: They pitted their method against older, traditional ways of sorting data (like simple grouping or complex neural networks).
The Outcome: Their method was the clear winner.
- On the noisy, difficult dataset, their method got about 76% accuracy, while the next best method only got about 50%.
- On the other dataset, their method performed just as well as if they had used perfect, physical measurements (like knowing the exact height of every point), even though they only used Wi-Fi signals.

6. Why It's Special

No Blueprints Needed: You don't need to know the building's layout or how many floors it has. The system figures it out on its own.
No Extra Sensors: It doesn't need barometers (pressure sensors) or accelerometers; it just uses the Wi-Fi signals already on your phone.
Robustness: Even when the Wi-Fi signals are messy or the building has weird open spaces (like a giant atrium), this "social network" approach still manages to separate the floors correctly.

In a nutshell: The authors turned a messy pile of Wi-Fi signals into a social network, let an AI learn the "personality" of each floor, and then sorted them into groups. It's a way to tell which floor you are on just by listening to the Wi-Fi, without ever needing to see a map.

Technical Summary: Graph-Based Floor Separation Using Node Embeddings and Clustering of Wi-Fi Trajectories

Problem Definition
Vertical localization, specifically floor separation in multi-story indoor environments, remains a significant challenge for Indoor Positioning Systems (IPS). Unlike outdoor GPS-based systems, indoor environments suffer from signal obstructions, multipath interference, and signal leakage between floors (particularly in atriums and open spaces), leading to overlapping signal patterns. Traditional Wi-Fi fingerprinting methods often rely on supervised learning requiring extensive labeled data and prior building knowledge (e.g., floor plans or the number of floors). Furthermore, hardware-dependent solutions (barometric pressure, IMUs) face issues with calibration drift and scalability. This paper addresses the need for a fully data-driven, unsupervised approach to blind floor separation that requires no prior building information, no knowledge of the number of floors, and relies solely on Wi-Fi Received Signal Strength Indicator (RSSI) trajectories.

Methodology
The proposed framework formulates floor separation as an unsupervised graph clustering problem. The methodology proceeds through the following stages:

Graph Construction:
- Nodes: Each Wi-Fi fingerprint (a vector of RSSI values from visible Access Points) is represented as a node.
- Edges: Edges capture both signal similarity and sequential movement context.
  - Horizontal Edges: Connect sequential fingerprints within the same user trajectory to preserve temporal continuity.
  - Vertical/Synthetic Edges: In datasets lacking explicit vertical transition labels (e.g., UJIIndoorLoc), synthetic edges are introduced solely to ensure the graph remains a single connected component, without encoding floor identity or vertical supervision.
- Edge Weighting: Weights represent the proximity between fingerprints. The study evaluates three strategies:
  - Default: Noisy distance estimates provided in competition datasets.
  - WBDE (Wi-Fi-Based Distance Estimation): Distances recalculated using a supervised ML model trained on external horizontal positioning datasets (ensuring no data leakage from the floor classification task).
  - Geometric Gold Standard: Euclidean distances derived from ground-truth coordinates (used only for UJIIndoorLoc as a theoretical upper bound).
Node Embedding:
- The framework employs Node2Vec to learn low-dimensional vector embeddings (dimension $d=32$ ) of the nodes. Node2Vec utilizes biased random walks to balance Depth-First Search (DFS) and Breadth-First Search (BFS), capturing both local homophily and global structural equivalence.
- The study also benchmarks against Graph Neural Networks (GCN and GAT), though these rely on explicit feature aggregation which can be prone to over-smoothing in noisy Wi-Fi graphs.
Clustering and Estimation:
- The learned embeddings are clustered using K-Means.
- Automatic Cluster Estimation: To determine the number of floors ( $k$ ) without prior knowledge, the system uses the Calinski-Harabasz (CH) Index. The algorithm iteratively evaluates $k$ within a range of [3, 20] (based on Huawei Challenge constraints) and selects the $k$ that maximizes the ratio of inter-cluster to intra-cluster dispersion.
Evaluation:
- Since the method is unsupervised, a post-hoc majority voting scheme maps anonymous clusters to physical floor labels for metric calculation.
- Performance is measured using Mapped Accuracy, Weighted F1-Score, Adjusted Rand Index (ARI), Normalized Mutual Information (NMI), and Cluster Purity.
- Statistical robustness is ensured via 1,000 bootstrap iterations.

Datasets
The framework is evaluated on two distinct datasets:

Huawei University Challenge 2021: A large-scale dataset with continuous walking trajectories and noisy distance estimates.
UJIIndoorLoc: A benchmark dataset covering three buildings. The authors restructured this dataset to generate trajectories from discrete fingerprints, treating the Training and Validation subsets as independent experiments to test generalizability.

Key Results

Superiority over Baselines: The proposed Node2Vec + K-Means pipeline significantly outperformed traditional community detection algorithms (Louvain, Leiden, Infomap, Label Propagation, Fast Greedy) and GNN-based models (GCN, GAT).
- On the Huawei dataset (using WBDE distances), the proposed method achieved 76.60% accuracy (95% CI [0.739, 0.806]), decisively beating the best baseline (GAT at 50.2%).
- On the UJIIndoorLoc dataset, the method achieved 66.1% accuracy on the Training subset and 59.4% on the Validation subset, substantially outperforming baselines which often fell below 25% on the Validation set.
Impact of Distance Estimation: Replacing noisy default distances with WBDE-based estimates significantly improved performance (from 69.3% to 76.6% on Huawei), confirming that cleaner graph topology is critical for clustering.
Equivalence to Geometry: A major finding is that on the UJIIndoorLoc dataset, the clustering performance using purely signal-derived distances (WBDE) was statistically indistinguishable from the "Gold Standard" results obtained using ground-truth geometric distances. This suggests the method can recover physical structural layouts solely from RSSI data.
Structural Integrity: While traditional algorithms achieved high Cluster Purity (often >90%), they suffered from severe over-segmentation (near-zero ARI), failing to identify coherent floor-level communities. The Node2Vec approach maintained high ARI scores (e.g., 0.669 on Huawei), indicating it successfully captures global structural consistency.

Significance and Claims
The paper claims that its primary contribution is a scalable, hardware-independent solution for vertical localization that eliminates dependence on building-specific metadata or labeled training data.

Unsupervised Capability: The method successfully performs blind floor separation, estimating the number of floors and partitioning trajectories without prior knowledge of the building's layout.
Robustness to Noise: By leveraging graph representation learning (Node2Vec) rather than direct feature aggregation (GNNs) or local modularity optimization, the framework is robust to the high noise and signal fluctuations inherent in Wi-Fi environments.
Generalizability: The approach demonstrates consistent performance across different architectural scales and data collection methodologies (continuous trajectories vs. reconstructed discrete fingerprints).
Practicality: The framework relies only on standard Wi-Fi fingerprint data, making it applicable to existing wireless infrastructure without requiring additional sensors (like barometers) or complex calibration.

The authors conclude that while distance estimation quality (via WBDE) enhances performance, the core value lies in the ability of the embedding-based framework to autonomously recover the structural layout of multi-story buildings from noisy signal data alone.