An official website of the United States government
The application of graph Laplacian eigenvectors has been quite popular in the graph signal processing field: one can use them as ingredients to design smooth multiscale basis. Our long-term goal is to study and understand the dual geometry of graph Laplacian eigenvectors. In order to do that, it is necessary to define a certain metric to measure the behavioral differences between each pair of the eigenvectors. Saito (2018) considered the ramified optimal transportation (ROT) cost between the square of the eigenvectors as such a metric. Clonginger and Steinerberger (2018) proposed a way to measure the affinity (or `similarity') between the eigenvectors based on their Hadamard (HAD) product. In this article, we propose a simplified ROT metric that is more computational efficient and introduce two more ways to define the distance between the eigenvectors, i.e., the time-stepping diffusion (TSD) metric and the difference of absolute gradient (DAG) pseudometric. The TSD metric measures the cost of "flattening" the initial graph signal via diffusion process up to certain time, hence it can be viewed as a time-dependent version of the ROT metric. The DAG pseudometric is the l2-distance between the feature vectors derived from the eigenvectors, in particular, the absolute gradients of the eigenvectors. We then compare the performance of ROT, HAD and the two new "metrics: on different kinds of graphs. Finally, we investigate their relationship as well as their pros and cons. Keywords: Graph Laplacian eigenvectors, metrics between orthonormal vectors, dual geometry of graph Laplacian eigenvectors, multiscale basis dictionaries on graphs, heat diffusion on graphs, Wasserstein distance, optimal transport
more »
« less
Bringing physics into the coarse‐grid selection: Approximate diffusion distance/effective resistance measures for network analysis and algebraic multigrid for graph Laplacians and systems of elliptic partial differential equations
Abstract In a recent paper, the author examined a correlation affinity measure for selecting the coarse degrees of freedom (CDOFs) or coarse nodes (C nodes) in systems of elliptic partial differential equations (PDEs). This measure was applied to a set of relaxed vectors, which exposed the near‐nullspace components of the PDE operator. Selecting the CDOFs using this affinity measure and constructing the interpolation operators using a least‐squares procedure, an algebraic multigrid (AMG) method was developed. However, there are several noted issues with this AMG solver. First, to capture strong anisotropies, a large number of test vectors may be needed; and second, the solver's performance can be sensitive to the initial set of random test vectors. Both issues reflect the sensitive statistical nature of the measure. In this article, we derive several other statistical measures that ameliorate these issues and lead to better AMG performance. These measures are related to a Markov process, which the PDE itself may model. Specifically, the measures are based on the diffusion distance/effective resistance for such process, and hence, these measures incorporate physics into the CDOF selection. Moreover, because the diffusion distance/effective resistance can be used to analyze graph networks, these measures also provide a very economical scheme for analyzing large‐scale networks. In this article, the derivations of these measures are given, and numerical experiments for analyzing networks and for AMG performance on weighted‐graph Laplacians and systems of elliptic boundary‐value problems are presented.
more »
« less
- Award ID(s):
- 1734727
- PAR ID:
- 10475183
- Editor(s):
- Vassilevski, Panayot
- Publisher / Repository:
- Numerical Linear Algebra with Applications
- Date Published:
- Journal Name:
- Numerical Linear Algebra with Applications
- ISSN:
- 1070-5325
- Subject(s) / Keyword(s):
- auto-correlation bootstrap multigrid correlation diffusion distance effective resistance graph Laplacians multigrid systems of elliptic partial differential equations variance
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Summary This article develops an algebraic multigrid (AMG) method for solving systems of elliptic boundary‐value problems. It is well known that multigrid for systems of elliptic equations faces many challenges that do not arise for most scalar equations. These challenges include strong intervariable couplings, multidimensional and possibly large near‐nullspaces, analytically unknown near‐nullspaces, delicate selection of coarse degrees of freedom (CDOFs), and complex construction of intergrid operators. In this article, we consider only the selection of CDOFs and the construction of the interpolation operator. The selection is an extension of the Ruge–Stuben algorithm using a new strength of connection measure taken between nodal degrees of freedom, that is, between all degrees of freedom located at a gridpoint to all degrees of freedom at another gridpoint. This measure is based on a local correlation matrix generated for a set of smoothed test vectors derived from a relaxation‐based procedure. With this measure, selection of the CDOFs is then determined by the number of strongly correlated connections at each node, with the selection processed by a Ruge–Stuben coloring scheme. Having selected the CDOFs, the interpolation operator is constructed using a bootstrap AMG (BAMG) procedure. We apply the BAMG procedure either over the smoothed test vectors to obtain an intervariable interpolation scheme or over the like‐variable components of the smoothed test vectors to obtain an intravariable interpolation scheme. Moreover, comparing the correlation measured between the intravariable couplings with the correlation between all couplings, a mixed intravariable and intervariable interpolation scheme is developed. We further examine an indirect BAMG method that explicitly uses the coefficients of the system operator in constructing the interpolation weights. Finally, based on a weak approximation criterion, we consider a simple scheme to adapt the order of the interpolation (i.e., adapt the caliber or maximum number of coarse‐grid points that a fine‐grid point can interpolate from) over the computational domain.more » « less
-
Graph Neural Networks (GNNs) are neural models that leverage the dependency structure in graphical data via message passing among the graph nodes. GNNs have emerged as pivotal architectures in analyzing graph-structured data, and their expansive application in sensitive domains requires a comprehensive understanding of their decision-making processes — necessitating a framework for GNN explainability. An explanation function for GNNs takes a pre-trained GNN along with a graph as input, to produce a ‘sufficient statistic’ subgraph with respect to the graph label. A main challenge in studying GNN explainability is to provide fidelity measures that evaluate the performance of these explanation functions. This paper studies this foundational challenge, spotlighting the inherent limitations of prevailing fidelity metrics, including Fid+, Fid−, and Fid∆. Specifically, a formal, information-theoretic definition of explainability is introduced and it is shown that existing metrics often fail to align with this definition across various statistical scenarios. The reason is due to potential distribution shifts when subgraphs are removed in computing these fidelity measures. Subsequently, a robust class of fidelity measures are introduced, and it is shown analytically that they are resilient to distribution shift issues and are applicable in a wide range of scenarios. Extensive empirical analysis on both synthetic and real datasets are provided to illustrate that the proposed metrics are more coherent with gold standard metrics. The source code is available at https://trustai4s-lab.github.io/fidelity.more » « less
-
Abstract In a recent article, one of the authors developed a multigrid technique for coarse‐graining dynamic powergrid models. A key component in this technique is a relaxation‐based coarsening of the graph Laplacian given by the powergrid network and its weighted graph, which is represented by the admittance matrix. In this article, we use this coarsening strategy to develop a multigrid method for solving a static system of nonlinear equations that arises through Ohm's law, the so‐called powerflow equations. These static equations are tightly knitted to the dynamic model in that the full powergrid model is an algebraic‐differential system with the powerflow equations describing the algebraic constraints. We assume that the dynamic model corresponds to a stable operating powergrid, and thus, the powerflow equations are associated with a physically stable system. This stability permits the coarsening of the powerflow equations to be based on an approximate graph Laplacian, which is embedded in the powerflow system. By algebraically constructing a hierarchy of approximate weighted graph Laplacians, a hierarchy of nonlinear powerflow equations immediately becomes apparent. This latter hierarchy can then be used in a full approximation scheme (FAS) framework that leads to a nonlinear solver with generally a larger basin of attraction than Newton's method. Given the algebraic multigrid (AMG) coarsening of the approximate Laplacians, the solver is an AMG‐FAS scheme. Alternatively, using the coarse‐grid nodes and interpolation operators generated for the hierarchy of approximate graph Laplacians, a multiplicative‐correction scheme can be derived. The derivation of both schemes will be presented and analyzed, and numerical examples to demonstrate the performance of these schemes will be given.more » « less
-
Graph Neural Networks (GNNs) are a popular machine learning framework for solving various graph processing applications. This framework exploits both the graph topology and the feature vectors of the nodes. One of the important applications of GNN is in the semi-supervised node classification task. The accuracy of the node classification using GNN depends on (i) the number and (ii) the choice of the training nodes. In this article, we demonstrate that increasing the training nodes by selecting nodes from the same class that are spread out across non-contiguous subgraphs, can significantly improve the accuracy. We accomplish this by presenting a novel input intervention technique that can be used in conjunction with different GNN classification methods to increase the non-contiguous training nodes and, thereby, improve the accuracy. We also present an output intervention technique to identify misclassified nodes and relabel them with their potentially correct labels. We demonstrate on real-world networks that our proposed methods, both individually and collectively, significantly improve the accuracy in comparison to the baseline GNN algorithms. Both our methods are agnostic. Apart from the initial set of training nodes generated by the baseline GNN methods, our techniques do not need any other extra knowledge about the classes of the nodes. Thus, our methods are modular and can be used as pre-and post-processing steps with many of the currently available GNN methods to improve their accuracy.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1002/nla.2539
