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

arXiv:2505.08088 · cs.NI, cs.AI, cs.CR, cs.LG, cs.RO · Submitted 2025-05-12 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "Graph-Based Floor Separation Using Node Embeddings and Clustering of WiFi Trajectories".

Jane: Vertical localization, particularly floor separation, remains a major challenge in indoor positioning systems operating in GPS-denied multistory environments.

Tom: First, who's behind it and why it matters.

Title and authors: Tom: So, we're looking at the paper "Graph-Based Floor Separation Using Node Embeddings and Clustering of WiFi Trajectories" today, and the title itself tells us exactly what they are trying to achieve. It’s about using graph embeddings and clustering to separate floors without any pre-existing building information.

Jane: That’s a big deal because usually, you need a map or some way to know the structure before you can even begin locating someone vertically. This paper suggests we can bypass that entirely by looking only at the signal patterns people create as they walk around.

Lu: The authors are presenting a framework where Wi-Fi fingerprints become nodes in a trajectory graph, and they use Node2Vec embeddings to learn structural representations of those signals <ref:2505.08088#pg0>.

Meng: So, instead of relying on fixed assumptions about the building's height or layout, this AI learns the vertical structure directly from the movement data captured by the signal strength indicators. How does that translate into actual floor identification?

Lalam: It means we can develop a system that identifies floors autonomously based purely on signal topology and sequential movement context, which is pretty powerful for creating more flexible indoor location services <ref:2505.08088#pg1>.

The paper's summary: Tom: To summarize what the paper says, the core idea is to treat user Wi-Fi fingerprints as nodes and connect them based on signal similarity and movement sequence. Then, they use Node2Vec to create low-dimensional vectors for these nodes, which captures the structural consistency across floors <ref:2505.08088#pg2>.

Jane: That’s a clever way to handle the noise; by learning those embeddings, the system can distinguish between signals that look similar but belong to different vertical levels in the building. They then use K-Means clustering on these embeddings to group trajectories into distinct floor partitions <ref:2505.08088#pg0>.

Lu: They also introduced a way to handle connectivity issues by adding synthetic vertical edges when the trajectory data is too sparse, ensuring the graph stays connected even without perfect sequential continuity <ref:2505.08088#pg2>.

Meng: I see; so they are not just looking at where someone is right now, but how their movement pattern relates to other signals across the entire structure to define those floors. That’s a lot of structural inference for an AI to do from raw data <ref:2505.08088#pg2>.

Lalam: It moves us toward systems that can infer the physical organization of environments dynamically, which could fundamentally change how we design smart buildings and navigation apps <ref:2505.08088#pg1>.

The paper's improvements: Tom: One major improvement they focus on is how they handle the distance estimation between nodes in their graph; they compare different ways to calculate these distances, like using the default estimates versus a model called Wi-Fi-Based Distance Estimation or WBDE <ref:2505.08088#pg2>.

Jane: The improvement here is that they test if recalculating those distances based only on raw RSSI measurements can give a much more accurate picture of proximity than using the original, noisy distance values from the competition data <ref:2505.08088#pg1>.

Lu: The key finding they highlight is that using the WBDE model allows them to achieve results that are statistically indistinguishable from those obtained using actual geometric distances on a benchmark called UJIIndoorLoc <ref:2505.08088#pg2>.

Meng: That equivalence with ground truth distances is significant because it suggests their method can recover the layout autonomously, without needing any physical reference points like floor plans or known distances beforehand <ref:2505.08088#pg1>.

Lalam: That capability to work purely from signal strength measurements to achieve accuracy levels matching real-world measurements is a huge step toward building truly robust indoor positioning tools <ref:2505.08088#pg1>.

Conclusion: Tom: So, wrapping up the discussion on "Graph-Based Floor Separation Using Node Embeddings and Clustering of WiFi Trajectories," we’ve seen how this framework uses Node2Vec embeddings and K-Means clustering to blind floor separate multistory buildings using only Wi-Fi data.

Jane: The main implication is that we can develop systems that perform vertical localization in any GPS-denied environment without needing a pre-existing map or any prior knowledge about the building's structure.

Lu: Furthermore, they showed that by improving the edge weights with WBDE estimates, they can achieve performance levels comparable to ground truth geometric distances on benchmarks like UJIIndoorLoc <ref:2505.08088#pg2>.

Meng: From an engineering standpoint, the robustness they found across different datasets suggests this approach could be practical for deploying indoor localization in various complex settings where floor plans aren't readily available <ref:2505.08088#pg1>.

Lalam: This work means we are moving closer to creating truly autonomous indoor navigation and localization solutions that adapt to the specific environment they are in, making our AI systems much more context-aware <ref:2505.08088#pg1>.

cs.NI, cs.AI, cs.CR, cs.LG, cs.RO

Submitted: 2025-05-12

Updated: 2026-10-07

Code: https://github.com/kahramankostas/DetectFloor

Project page: https://rykostas.github.io

Importance score: 76/100

The gist: Vertical localization, particularly floor separation, remains a major challenge in indoor positioning systems operating in GPS-denied multistory environments.

Key concepts

Graph Construction
The system builds a network where each Wi-Fi signal measurement is a 'node.' Connections (edges) are drawn between sequential signals within a user's path (horizontal edges) and synthetic connections added to ensure the entire graph is connected, regardless of missing data.
Node2Vec Embeddings
This technique transforms complex Wi-Fi signal data into low-dimensional numerical vectors. It learns meaningful representations of each signal node by simulating random walks across the graph, effectively capturing both local neighborhood details and broader structural relationships within the building layout.
K-Means Clustering
This unsupervised learning method groups the nodes (fingerprints) based on their learned embeddings. The goal is to partition these clusters such that all signals belonging to a single physical floor are grouped together, allowing for automatic floor identification.

Terminology

Summary

Vertical localization, particularly floor separation, remains a major challenge in indoor positioning systems operating in GPS-denied multistory environments. The gist: A fully data-driven, graph-based framework using Node2Vec embeddings and K-Means clustering can effectively capture the intrinsic vertical structure of multistory buildings from Wi-Fi fingerprint trajectories without requiring prior building information. This method provides a scalable and practical solution for vertical localization by leveraging only received signal strength data.

Problem Formulation and Data Representation

The fundamental objective is to perform blind floor separation in multistory indoor environments by formulating the task as an unsupervised graph clustering problem. A set of user trajectories, where each trajectory consists of time-stamped Wi-Fi fingerprints, is partitioned into disjoint clusters such that all trajectories within a cluster belong to the same physical floor. The inputs for this problem are Received Signal Strength Indicator (RSSI) values from visible Access Points (APs), Sequential continuity information, and optionally, Sparse elevation hints.

Graph Construction and Edge Weighting

The framework constructs a graph where each node corresponds to a Wi-Fi fingerprint. Edges are weighted based on signal similarity or contextual transitions. The construction pipeline involves several steps:

  1. Trajectory Generation: Raw fingerprints are grouped into trajectories using a temporal threshold of ∆t = 600s to segment distinct walking sessions.

  2. Node Definition: Each valid Wi-Fi fingerprint is represented as a node, filtering out weak signals where RSSI ≠ 100.

  3. Edge Types: The graph includes Horizontal Edges connecting sequential fingerprints within the same trajectory to preserve temporal continuity, and Synthetic Vertical Edges introduced solely to ensure global graph connectivity in datasets lacking explicit trajectory continuity.

The quality of the edge weights is critical. The study investigates three distinct distance estimation strategies:

(Scenario IDs are referenced in Table I)

(HW-Def)

Default Estimates (Baseline): Utilizes original, noisy distance values from the competition dataset.

(HW-WBDE and UJI-WBDE)

WBDE-Based Estimates (Proposed): Distances are recalculated using the proposed Wi-Fi-Based Distance Estimation (WBDE) model, which infers proximity solely from raw RSSI measurements.

Graph Embedding and Clustering Pipeline

To extract meaningful representations from the graph structure, a two-stage process is employed:

  1. Structural Node Embeddings: Node2Vec is applied to learn low-dimensional vector embeddings of nodes. This technique balances local and global structural information through biased random walks. Alternative methods explored include Graph Neural Networks (GCN) and Graph Attention Networks (GAT), which explicitly leverage the adjacency matrix for neighborhood aggregation.

  2. Clustering: The resulting embeddings are then clustered using the K-Means algorithm. To eliminate manual selection of the number of floors, an automatic cluster number estimation method is used, specifically the Calinski-Harabasz (CH) Index to select the optimal number of clusters, k.

Evaluation Framework and Metrics

Since the task is unsupervised, performance is rigorously evaluated using a three-stage framework:

  1. Cluster-to-Floor Mapping: A post-hoc majority voting scheme maps each anonymous cluster to the physical floor label by finding the most frequent true label within that cluster. This allows for calculating Mapped Accuracy and Mapped F1-Score.

  2. Standard Clustering Metrics: Structural quality is assessed using metrics such as the Adjusted Rand Index (ARI), which measures similarity adjusted for chance, and Normalized Mutual Information (NMI).

  3. Statistical Validation: The reliability of results is confirmed via the bootstrap method, where 1,000 bootstrap samples are generated to report mean values and their 95% Confidence Intervals (CI).

Key Findings on Robustness

The experiments demonstrated that the proposed approach effectively captures vertical structure. On the Huawei dataset, improving edge weights via WBDE resulted in a mean accuracy of 76.60%, significantly outperforming baselines like GAT (50.2%). Crucially, on the UJIIndoorLoc benchmark, performance was achieved using purely signal-derived distances (UJI-WBDE) that were statistically indistinguishable from that obtained using groundtruth geometric distances (UJI-Geo). This equivalence validates that the framework can autonomously recover the structural layout of a building without requiring physical reference points or floor plans. Furthermore, analysis revealed that traditional methods often suffer from severe oversegmentation, whereas the Node2Vec-based method preserves global structural consistency, achieving substantially higher ARI scores. The study also noted that GNN models (GCN and GAT) showed consistently weaker performance than Node2Vec due to the inherent challenges of high-dimensional, noisy node features in Wi-Fi graphs.

Improvements for AI systems

Here are specific improvements for AI systems derived from this research, categorized by the capability they would gain:

) Use a fully unsupervised, data-driven approach to determine floor separation in GPS-denied indoor environments solely from Wi-Fi Received Signal Strength Indicator (RSSI) trajectories, eliminating the need for prior building metadata or manual floor labeling.

This system can perform real-time vertical localization in any multistory building, such as shopping malls or offices, without requiring a pre-existing map of the building's architecture.

) Implement a graph-based framework that models Wi-Fi fingerprints as nodes and captures both signal similarity (edge weights) and sequential movement context (trajectory edges).

This capability allows the system to understand not just where a user is, but how they are moving, allowing it to infer vertical transitions based on signal topology rather than relying on absolute location data.

) Integrate Node2Vec or Graph Neural Networks (GNNs like GCN/GAT) for structural node embeddings before applying K-Means clustering for floor partitioning.

This advanced system can learn low-dimensional, semantically rich vector representations of signal patterns, allowing it to distinguish between floors that might have similar raw RSSI values due to environmental noise or interference.

) Develop an adaptive cluster number estimation mechanism using the Calinski-Harabasz (CH) Index to automatically determine the optimal number of floors without human intervention.

The improved AI system can dynamically adjust its vertical resolution based on the complexity of the signal data, ensuring that whether dealing with a small office or a large campus, it finds the most meaningful floor boundaries.

) Utilize a supervised Wi-Fi-Based Distance Estimation (WBDE) model as an external module to calculate accurate inter-fingerprint distances from raw RSSI measurements.

This enhancement ensures that the graph topology is built on physically meaningful proximity estimates derived directly from signal strength, significantly reducing errors caused by multipath interference and signal leakage between floors.

) Employ a multi-dataset validation strategy (using both Huawei Challenge 2021 and UJIIndoorLoc) to guarantee the generalizability of floor separation across diverse architectural scales.

This makes the resulting AI system robust; it will perform accurately whether deployed in a small, dense environment or a large, complex structure with varying AP densities.

) Integrate post-hoc classification metrics (Mapped Accuracy, ARI, NMI) alongside standard clustering metrics to rigorously evaluate the quality of the inferred floor partitions against ground truth.

This allows for verifiable proof of performance; the system's output can be quantitatively measured and compared against known accurate floor layouts.

Related papers