Blind Extraction of Equitable Partitions from Graph Signals
- URL: http://arxiv.org/abs/2203.05407v1
- Date: Thu, 10 Mar 2022 15:03:32 GMT
- Title: Blind Extraction of Equitable Partitions from Graph Signals
- Authors: Michael Scholkemper and Michael Schaub
- Abstract summary: We study a blind identification problem in which we aim to recover an equitable partition of a network without the knowledge of the network's edges.
We present a simple spectral algorithm to extract the relevant equitable partitions.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Finding equitable partitions is closely related to the extraction of graph
symmetries and of interest in a variety of applications context such as node
role detection, cluster synchronization, consensus dynamics, and network
control problems. In this work we study a blind identification problem in which
we aim to recover an equitable partition of a network without the knowledge of
the network's edges but based solely on the observations of the outputs of an
unknown graph filter. Specifically, we consider two settings. First, we
consider a scenario in which we can control the input to the graph filter and
present a method to extract the partition inspired by the well known
Weisfeiler-Lehman (color refinement) algorithm. Second, we generalize this idea
to a setting where only observe the outputs to random, low-rank excitations of
the graph filter, and present a simple spectral algorithm to extract the
relevant equitable partitions. Finally, we establish theoretical bounds on the
error that this spectral detection scheme incurs and perform numerical
experiments that illustrate our theoretical results and compare both
algorithms.
Related papers
- HeNCler: Node Clustering in Heterophilous Graphs through Learned Asymmetric Similarity [55.27586970082595]
HeNCler is a novel approach for Heterophilous Node Clustering.
We show that HeNCler significantly enhances performance in node clustering tasks within heterophilous graph contexts.
arXiv Detail & Related papers (2024-05-27T11:04:05Z) - Entropy Neural Estimation for Graph Contrastive Learning [9.032721248598088]
Contrastive learning on graphs aims at extracting distinguishable high-level representations of nodes.
We propose a simple yet effective subset sampling strategy to contrast pairwise representations between views of a dataset.
We conduct extensive experiments on seven graph benchmarks, and the proposed approach achieves competitive performance.
arXiv Detail & Related papers (2023-07-26T03:55:08Z) - A Sparse Graph Formulation for Efficient Spectral Image Segmentation [0.0]
Spectral Clustering is one of the most traditional methods to solve segmentation problems.
We adopt a sparse graph formulation based on the inclusion of extra nodes to a simple grid graph.
Applying the original Normalized Cuts algorithm to this graph leads to a simple and scalable method for spectral image segmentation.
arXiv Detail & Related papers (2023-06-22T19:06:27Z) - Rethinking Explaining Graph Neural Networks via Non-parametric Subgraph
Matching [68.35685422301613]
We propose a novel non-parametric subgraph matching framework, dubbed MatchExplainer, to explore explanatory subgraphs.
It couples the target graph with other counterpart instances and identifies the most crucial joint substructure by minimizing the node corresponding-based distance.
Experiments on synthetic and real-world datasets show the effectiveness of our MatchExplainer by outperforming all state-of-the-art parametric baselines with significant margins.
arXiv Detail & Related papers (2023-01-07T05:14:45Z) - Joint graph learning from Gaussian observations in the presence of
hidden nodes [26.133725549667734]
We propose a joint graph learning method that takes into account the presence of hidden (latent) variables.
We exploit the structure resulting from the previous considerations to propose a convex optimization problem.
We compare the proposed algorithm with different baselines and evaluate its performance over synthetic and real-world graphs.
arXiv Detail & Related papers (2022-12-04T13:03:41Z) - LoNe Sampler: Graph node embeddings by coordinated local neighborhood
sampling [0.7614628596146599]
Local graph neighborhood sampling is a fundamental computational problem that is at the heart of algorithms for node representation learning.
We present LoNe Sampler, a suite of algorithms for generating discrete node embeddings by Local Neighborhood Sampling.
arXiv Detail & Related papers (2022-11-28T08:04:26Z) - Spectral-Spatial Global Graph Reasoning for Hyperspectral Image
Classification [50.899576891296235]
Convolutional neural networks have been widely applied to hyperspectral image classification.
Recent methods attempt to address this issue by performing graph convolutions on spatial topologies.
arXiv Detail & Related papers (2021-06-26T06:24:51Z) - Line Graph Neural Networks for Link Prediction [71.00689542259052]
We consider the graph link prediction task, which is a classic graph analytical problem with many real-world applications.
In this formalism, a link prediction problem is converted to a graph classification task.
We propose to seek a radically different and novel path by making use of the line graphs in graph theory.
In particular, each node in a line graph corresponds to a unique edge in the original graph. Therefore, link prediction problems in the original graph can be equivalently solved as a node classification problem in its corresponding line graph, instead of a graph classification task.
arXiv Detail & Related papers (2020-10-20T05:54:31Z) - Offline detection of change-points in the mean for stationary graph
signals [55.98760097296213]
We propose an offline method that relies on the concept of graph signal stationarity.
Our detector comes with a proof of a non-asymptotic inequality oracle.
arXiv Detail & Related papers (2020-06-18T15:51:38Z) - Heterogeneous Graph Neural Networks for Malicious Account Detection [64.0046412312209]
We present GEM, the first heterogeneous graph neural network approach for detecting malicious accounts.
We learn discriminative embeddings from heterogeneous account-device graphs based on two fundamental weaknesses of attackers, i.e. device aggregation and activity aggregation.
Experiments show that our approaches consistently perform promising results compared with competitive methods over time.
arXiv Detail & Related papers (2020-02-27T18:26:44Z) - Graph matching between bipartite and unipartite networks: to collapse,
or not to collapse, that is the question [13.625395368083641]
We address the common setting in which one of the graphs to match is a bipartite network and one is unipartite.
We formulate the graph matching problem between a bipartite and a unipartite graph using an undirected graphical model.
We show how our methods can result in a more accurate matching than the naive approach of transforming the bipartite networks into unipartite.
arXiv Detail & Related papers (2020-02-05T05:24:54Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.