Currently, WPGraphQL Smart Cache does only "track" changes to posts, comments and some other types and purges the cached items related to those changes. This does not work with menu items and menus for queries like this one:

{
  menuItems(where: {location: MAIN_NAV}) {
    nodes {
      databaseId
      label
    }
  }
}

A nice feature for future version (or a simple DIY workaround) would be to add cache purging to the plugin when menu items or menu get updated.