Learning over graphs

graph learning
embeddings
anomaly detection
robustness
Fast spectral embeddings for graphs that evolve over time, inference of the network topology itself, and robust learning when the graph is corrupted or attacked. Supported by the NSF project Robust Learning over Graphs.

Overview

Data from social, biological, and infrastructure networks come with a graph that describes how entities are connected, and that graph often changes over time. This project develops methods that exploit graph structure for dimensionality reduction and embedding, methods that infer the graph itself from data when it is not observed, and methods that remain reliable when parts of the graph are corrupted. Part of this work is supported by the National Science Foundation project Robust Learning over Graphs, with S. Aviyente and G. B. Giannakis.

Evolving graphs

Graphs that change over time must be re-embedded as they evolve, and recomputing a spectral embedding from scratch at every snapshot is wasteful. With collaborators we develop subspace projection and resolvent-based updates that refresh embeddings and signal estimates efficiently as edges appear and disappear.

Two small graphs side by side labeled G_t and G_t+1 with different edges.

Two snapshots of a dynamic graph: the node set stays fixed while edges change over time.

Topology inference and nonlinear embeddings

When the graph is not given, it has to be inferred from the data, for example through structural equation models, including in multilayer networks. A related line of work adapts nonlinear dimensionality reduction to data that live on a graph.

Robust learning over graphs

Methods that learn over graphs usually assume the graph is trustworthy. In practice, edges can be missing, spurious, or deliberately injected, and a handful of corrupted nodes can distort what is inferred about the whole network. We detect anomalous edges through link sampling and consensus, in the spirit of our earlier randomized methods, and extend this to detect anomalous nodes and edges simultaneously. A related idea appears in our crowdsourcing work, where colluding adversaries form a dense subgraph of an annotator similarity graph.

A small graph with one node and two edges highlighted in red as anomalous.

Anomalous nodes and edges distort inference over a network.

Key papers

Evolving graphs and embeddings

  1. M. Eini, A. Karaaslanli, V. Kalantzis and P. A. Traganitis, “Subspace Projection Methods for Fast Spectral Embeddings of Evolving Graphs,” IEEE Transactions on Signal and Information Processing over Networks (submitted). arXiv
  2. A. Karaaslanli, M. Eini, P. A. Traganitis and V. Kalantzis, “Efficient Spectral Embeddings of Graph Edges,” Proc. of EUSIPCO, Bruges, Belgium, 2026.
  3. M. Eini, A. Karaaslanli, V. Kalantzis and P. A. Traganitis, “Efficient Estimation of Time-varying Signals over Evolving Graphs,” Proc. of Asilomar Conf. on Signals, Systems, and Computers, 2026.
  4. V. Kalantzis and P. A. Traganitis, “Matrix Resolvent Eigenembeddings for Dynamic Graphs,” Proc. of ICASSP, Rhodes, Greece, 2023.
  5. G. Kollias, V. Kalantzis, L. Horesh, S. Ubaru and P. A. Traganitis, “Counting Triangles of Graphs via Matrix Partitioning,” Proc. of IEEE MLSP, London, UK, 2024.

Robustness and anomalies

  1. A. Karaaslanli, S. Aviyente and P. A. Traganitis, “Simultaneous Detection of Anomalous Nodes and Edges in Graphs,” Proc. of Asilomar Conf. on Signals, Systems, and Computers, 2025.
  2. A. Karaaslanli, P. A. Traganitis and S. Aviyente, “Identifying Anomalous Edges with Link Sampling and Consensus,” Proc. of Asilomar Conf. on Signals, Systems, and Computers, 2024.
  3. A. Karaaslanli, P. A. Traganitis and A. Konar, “Dense Subgraph Detection for Crowdsourcing with Colluding Adversaries,” IEEE Transactions on Signal Processing (submitted).

Topology inference and dimensionality reduction

  1. Y. Shen, P. A. Traganitis and G. B. Giannakis, “Graph-Adaptive Nonlinear Dimensionality Reduction,” IEEE Transactions on Signal Processing (submitted).
  2. Y. Shen, P. A. Traganitis and G. B. Giannakis, “Nonlinear Dimensionality Reduction on Graphs,” Proc. of CAMSAP, 2017. (Invited; student paper award finalist) arXiv
  3. V. N. Ioannidis, P. A. Traganitis, Y. Shen and G. B. Giannakis, “Kernel-Based Semi-Supervised Learning Over Multilayer Graphs,” Proc. of SPAWC, Kalamata, Greece, 2018.
  4. P. A. Traganitis, Y. Shen and G. B. Giannakis, “Network Topology Inference via Elastic Net Structural Equation Models,” Proc. of EUSIPCO, Kos, Greece, 2017.
  5. P. A. Traganitis, Y. Shen and G. B. Giannakis, “Topology Inference for Multilayer Networks,” Proc. of Intl. Workshop on Network Science for Communications, 2017.