LA/Opt Seminar: Numerical Methods for Gremban's Expansion of Signed Graphs, Dr Alyson Fox, Lawrence Livermore National Laboratory

LA/Opt Seminar

Title: Numerical Methods for Gremban's Expansion of Signed Graphs
Speaker:Dr Alyson Fox, Lawrence Livermore National Laboratory
Date: December 7, 2017
Time: 4:30pm
Location: Y2E2 111

Abstract:

Recently a new dimension of graphs has manifested in the network
science community that goes beyond the traditional notion of
connections and disconnections to include both favorable and adverse
relationships. We show that there exists a direct relationship
between a signed graph and its unsigned variant by Gremban's expansion
[K. Gremban, Combinatorial Preconditioners for Sparse, Symmetric,
Diagonally Dominant Linear Systems, PhD thesis and Tech Report
CMU-CS-96-123, School of Computer Science, Carnegie Mellon University,
Pittsburgh, 1996]. Fairly robust solvers for unsigned, undirected
graph Laplacians have been developed, but these solvers are not
directly applicable to general, signed graphs. Gremban's expansion is
used to transform the signed, undirected graph Laplacian into an
unsigned, undirected graph Laplacian with twice the number of unknowns.
The solution to the linear system of the expanded matrix yields the
solution of the original linear system. Thus, using Gremban's
expansion, we can extend the current Laplacian solvers' robustness to
signed graph Laplacians. We show that the error of the solution of
the original linear system can be tightly bounded by the error of the
expanded system. Both manufactured and real-world signed, undirected
graph Laplacians are tested with various solvers to show that the
expansion is numerically stable.

Furthermore, we hope to motivate data analysts to use signed graph
models by exploiting the relationship of Gremban's expansion to the
signed and unsigned variant. Methods that have been applied for
unsigned graphs could then be applied to signed graphs in a meaningful
way. We conduct a preliminary investigation into the application of
traditional ranking and clustering using Gremban's expansion matrix.
The rankings using Gremban's expansion for a user-movie rating graph
change considerably if a signed graph Laplacian is used, indicating
that applications such as recommendation systems would attain
different and possibly better recommendations if a signed graph were
used instead. For spectral clustering, initial tests indicated that
the eigenvectors associated with Gremban's expansion are better at
differentiating between clusters than the signed variant, no matter
the sign structure.

Bio:

Alyson Fox has a PhD in Applied Math from University of Colorado
Boulder, 2017. Her doctoral thesis concerns the study of Algebraic
Multigrid solvers for signed and directed graph Laplacian systems.
She won the 2017 student paper competition at Copper Mountain
Conference, Multigrid Methods and was asked to speak at the 2017
Applied Math Department graduation. She was instrumental in the
startup of the Association of Women in Math chapter at CU Boulder and
her efforts have contributed to the fraction of incoming female PhD
students rising to 50%. She started her postdoc at Lawrence Livermore
National Laboratory in August 2017, and is now working on error analysis
of lossy compression algorithms.

Date: 
Thursday, December 7, 2017 - 4:30pm to 5:30pm
location: 
Jerry Yang and Akiko Yamazaki Environment and Energy Building (Y2E2), 473 Via Ortega, Stanford, CA 94305, USA