Searching for polarization in signed graphs: a local spectral approach
- URL: http://arxiv.org/abs/2001.09410v1
- Date: Sun, 26 Jan 2020 06:30:16 GMT
- Title: Searching for polarization in signed graphs: a local spectral approach
- Authors: Han Xiao, Bruno Ordozgoiti, Aristides Gionis
- Abstract summary: This paper formulates the problem of finding local polarized communities in signed graphs as a locally-biased eigen-problem.
We show that the locally-biased vector can be used to find communities with approximation guarantee with respect to a local analogue of the Cheeger constant on signed graphs.
- Score: 16.384728228938574
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Signed graphs have been used to model interactions in social net-works, which
can be either positive (friendly) or negative (antagonistic). The model has
been used to study polarization and other related phenomena in social networks,
which can be harmful to the process of democratic deliberation in our society.
An interesting and challenging task in this application domain is to detect
polarized communities in signed graphs. A number of different methods have been
proposed for this task. However, existing approaches aim at finding globally
optimal solutions. Instead, in this paper we are interested in finding
polarized communities that are related to a small set of seed nodes provided as
input. Seed nodes may consist of two sets, which constitute the two sides of a
polarized structure.
In this paper we formulate the problem of finding local polarized communities
in signed graphs as a locally-biased eigen-problem. By viewing the eigenvector
associated with the smallest eigenvalue of the Laplacian matrix as the solution
of a constrained optimization problem, we are able to incorporate the local
information as an additional constraint. In addition, we show that the
locally-biased vector can be used to find communities with approximation
guarantee with respect to a local analogue of the Cheeger constant on signed
graphs. By exploiting the sparsity in the input graph, an indicator vector for
the polarized communities can be found in time linear to the graph size.
Our experiments on real-world networks validate the proposed algorithm and
demonstrate its usefulness in finding local structures in this semi-supervised
manner.
Related papers
- Graph Out-of-Distribution Generalization via Causal Intervention [69.70137479660113]
We introduce a conceptually simple yet principled approach for training robust graph neural networks (GNNs) under node-level distribution shifts.
Our method resorts to a new learning objective derived from causal inference that coordinates an environment estimator and a mixture-of-expert GNN predictor.
Our model can effectively enhance generalization with various types of distribution shifts and yield up to 27.4% accuracy improvement over state-of-the-arts on graph OOD generalization benchmarks.
arXiv Detail & Related papers (2024-02-18T07:49:22Z) - Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
This paper proposes a novel Deep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE) for attributed graph data.
The proposed method surpasses state-of-the-art baseline algorithms by a significant margin on different downstream tasks across popular datasets.
arXiv Detail & Related papers (2024-01-12T17:57:07Z) - PARTNER: Level up the Polar Representation for LiDAR 3D Object Detection [81.16859686137435]
We present PARTNER, a novel 3D object detector in the polar coordinate.
Our method outperforms the previous polar-based works with remarkable margins of 3.68% and 9.15% on and ONCE validation set.
arXiv Detail & Related papers (2023-08-08T01:59:20Z) - On the Complexity of the Bipartite Polarization Problem: from Neutral to
Highly Polarized Discussions [1.5675763601034223]
The Bipartite Polarization Problem is an optimization problem where the goal is to find the highest polarized bipartition on a weighted and labelled graph.
We introduce an instance generation model where a single parameter controls the polarization of the instances in such a way that this correlates with the average complexity to solve those instances.
arXiv Detail & Related papers (2023-07-21T14:40:41Z) - Curvature-based Clustering on Graphs [14.136746708037402]
We study algorithms, which exploit the geometry of the graph to identify densely connected substructures, which form clusters or communities.
Our method implements discrete Ricci curvatures and their associated geometric flows, under which the edge weights of the graph evolve to reveal its community structure.
arXiv Detail & Related papers (2023-07-19T17:35:08Z) - Unveiling the Sampling Density in Non-Uniform Geometric Graphs [69.93864101024639]
We consider graphs as geometric graphs: nodes are randomly sampled from an underlying metric space, and any pair of nodes is connected if their distance is less than a specified neighborhood radius.
In a social network communities can be modeled as densely sampled areas, and hubs as nodes with larger neighborhood radius.
We develop methods to estimate the unknown sampling density in a self-supervised fashion.
arXiv Detail & Related papers (2022-10-15T08:01:08Z) - Interpolation-based Correlation Reduction Network for Semi-Supervised
Graph Learning [49.94816548023729]
We propose a novel graph contrastive learning method, termed Interpolation-based Correlation Reduction Network (ICRN)
In our method, we improve the discriminative capability of the latent feature by enlarging the margin of decision boundaries.
By combining the two settings, we extract rich supervision information from both the abundant unlabeled nodes and the rare yet valuable labeled nodes for discnative representation learning.
arXiv Detail & Related papers (2022-06-06T14:26:34Z) - Integrating Network Embedding and Community Outlier Detection via
Multiclass Graph Description [15.679313861083239]
We propose a novel unsupervised graph embedding approach (called DMGD) which integrates outlier and community detection with node embedding.
We show the theoretical bounds on the number of outliers detected by DMGD.
Our formulation boils down to an interesting minimax game between the outliers, community assignments and the node embedding function.
arXiv Detail & Related papers (2020-07-20T16:21:07Z) - Learning Representations using Spectral-Biased Random Walks on Graphs [18.369974607582584]
We study how much a probabilistic bias in this process affects the quality of the nodes picked by the process.
We succinctly capture this neighborhood as a probability measure based on the spectrum of the node's neighborhood subgraph represented as a normalized laplacian matrix.
We empirically evaluate our approach against several state-of-the-art node embedding techniques on a wide variety of real-world datasets.
arXiv Detail & Related papers (2020-05-19T20:42:43Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs.
We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions.
Our methods are scalable to sparse graphs consisting of millions of nodes.
arXiv Detail & Related papers (2020-02-14T11:42:16Z)
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.