Proposed projects for students

On partially labeled data, semi-supervised learning methods have been studied profoundly by expressing the relations between the data entities within weighted graph representations [1]. The inpainting task, on the other hand, is usually defined on the domains accompanying a signal content, which has been addressed with graph signal representations and operations [2]. Most of these studies focus on one type of relationship between the pair of data points during the construction of the graph structure. However, the connections between the entities may possess different types of relationships, which can be represented better by multiple graph structures. The objective of this project is to extend semi-supervised clustering and inpainting tasks on multi-layer graph settings, where each graph layer signifies a particular type of relation between vertices. This yields the same number of vertices in each graph layer, yet the topology (i.e., weight matrix) is different due to the difference between the focus of each layer.


[1] Belkin, Mikhail, and Partha Niyogi. “Semi-supervised learning on Riemannian manifolds.” Machine learning 56.1-3 (2004): 209-239.

[2] Perraudin, Nathanaël, and Pierre Vandergheynst. “Stationary signal processing on graphs.” IEEE Transactions on Signal Processing 65.13 (2017): 3462-3477.

[3] Davide Eynard, Klaus Glashoff, Michael M Bronstein, and Alexander M. Bronstein. Multimodal diffusion geometry by joint diagonalization of laplacians.arXiv preprint arXiv:1209.2295, 2012.

[4] Xiaowen Dong, Pascal Frossard, Pierre Vandergheynst, and Nikolai Nefedov. Clustering on multi-layer graphs via subspace analysis on grassmann manifolds. IEEE Transactions on signal processing, 62(4):905–918, 2014.

[5] Xiaowen Dong, Pascal Frossard, Pierre Vandergheynst, and Nikolai Nefedov. Clustering with multi-layer graphs: A spectral perspective. IEEE Transactions on Signal Processing, 60(11):5820–5831, 2012.

Requirements:  Python, basics of Graph signal processing: graphs signal filtering and spectral clustering (covered in EE-558 Network Tour of Data Science).

Airborne Laser Scanning is a well-known remote sensing technology, which provides quite dense and highly accurate, yet unorganized point cloud descriptions of the earth surface. Weighted graphs are very convenient tools for representing such irregular and 3D data types, moreover, spectral graph based methods provide spectral analysis of signals residing on the weighted graph representations. With this in mind, one can consider the airborne LIDAR data as unstructured elevation signal so that it can be processed on an appropriate graph structure.

The goal of this project is to discover the spectral attributes of various objects in a LIDAR scene, such as buildings and vegetation, through the graph signal processing. Instead of calculating the geometric primitives such as normals, slopes and curvatures for each point on a scene and thresholding them, this approach aims to transpose classical signal processing tools to analyze 3D aerial LIDAR point clouds.

In particular, the points on the breakline of the buildings constitute some features which can be detected and discriminated from the other objects by augmenting the spectral information on the graph. This could be achieved by formulating a spectral descriptor on the detected points and then, yielding a classification problem to discriminate the ones existing on the buildings. On a building extraction problem, the later step is to retrieve whole body of the building objects.


[1] Michaël Defferrard, Lionel Martin, Rodrigo Pena, & Nathanaël Perraudin. (2017, October 6). PyGSP: Graph Signal Processing in Python (Version v0.5.0). Zenodo.

[2] ISPRS, “Isprs test project on 3d semantic labeling contest,”2017,

[3] Blomley, R., and M. Weinmann. “USING MULTI-SCALE FEATURES FOR THE 3D SEMANTIC LABELING OF AIRBORNE LASER SCANNING DATA.” ISPRS Annals of Photogrammetry, Remote Sensing & Spatial Information Sciences 4 (2017).

Requirements:  Python, basics of Graph signal processing: graphs signal filtering (covered in EE-558 Network Tour of Data Science), familiarity with basic machine learning tools.