Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Motif Cut Sparsifiers
 
conference paper

Motif Cut Sparsifiers

Kapralov, Michael
•
Makarov, Mikhail  
•
Silwal, Sandeep
Show more
January 1, 2022
2022 Ieee 63Rd Annual Symposium On Foundations Of Computer Science (Focs)
63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

A motif is a frequently occurring subgraph of a given directed or undirected graph G (Milo et al.). Motifs capture higher order organizational structure of G beyond edge relationships, and, therefore, have found wide applications such as in graph clustering, community detection, and analysis of biological and physical networks to name a few (Benson at al., Tsourakakis at al.). In these applications, the cut structure of motifs plays a crucial role as vertices are partitioned into clusters by cuts whose conductance is based on the number of instances of a particular motif, as opposed to just the number of edges, crossing the cuts. In this paper, we introduce the concept of a motif cut sparsifier. We show that one can compute in polynomial time a sparse weighted subgraph G' with only (O) over tilde( n/is an element of(2)) edges such that for every cut, the weighted number of copies of M crossing the cut in G' is within a 1 + is an element of factor of the number of copies of M crossing the cut in G, for every constant size motif M. Our work carefully combines the viewpoints of both graph sparsification and hypergraph sparsification. We sample edges which requires us to extend and strengthen the concept of cut sparsifiers introduced in the seminal works of Karger and Benczur et al. to the motif setting. The task of adapting the importance sampling framework common to efficient graph sparsification algorithms to the motif setting turns out to be nontrivial due to the fact that cut sizes in a random subgraph of G depend non-linearly on the sampled edges. To overcome this, we adopt the viewpoint of hypergraph sparsification to define edge sampling probabilities which are derived from the strong connectivity values of a hypergraph whose hyperedges represent motif instances. Finally, an iterative sparsification primitive inspired by both viewpoints is used to reduce the number of edges in G to nearly linear. In addition, we present a strong lower bound ruling out a similar result for sparsification with respect to induced occurrences of motifs.

  • Details
  • Metrics
Type
conference paper
DOI
10.1109/FOCS54457.2022.00044
Web of Science ID

WOS:000909382900036

Author(s)
Kapralov, Michael
Makarov, Mikhail  
Silwal, Sandeep
Sohler, Christian
Tardos, Jakab  
Date Issued

2022-01-01

Publisher

IEEE COMPUTER SOC

Publisher place

Los Alamitos

Published in
2022 Ieee 63Rd Annual Symposium On Foundations Of Computer Science (Focs)
ISBN of the book

978-1-6654-5519-0

Series title/Series vol.

Annual IEEE Symposium on Foundations of Computer Science

Start page

389

End page

398

Subjects

Computer Science, Theory & Methods

•

Mathematics, Applied

•

Computer Science

•

Mathematics

•

sparsification

•

framework

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
THL4  
Event nameEvent placeEvent date
63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

Denver, CO

Oct 31-Nov 03, 2022

Available on Infoscience
February 27, 2023
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/195201
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés