Characterizing Attitudinal Network Graphs through Frustration Cloud
- URL: http://arxiv.org/abs/2009.07776v3
- Date: Tue, 17 Aug 2021 20:47:47 GMT
- Title: Characterizing Attitudinal Network Graphs through Frustration Cloud
- Authors: Lucas Rusnak and Jelena Te\v{s}i\'c
- Abstract summary: Attitudinal Network Graphs are signed graphs where edges capture an expressed opinion.
We propose to expand the measures of consensus from a single balanced state associated with the frustration index to the set of nearest balanced states.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Attitudinal Network Graphs are signed graphs where edges capture an expressed
opinion; two vertices connected by an edge can be agreeable (positive) or
antagonistic (negative). A signed graph is called balanced if each of its
cycles includes an even number of negative edges. Balance is often
characterized by the frustration index or by finding a single convergent
balanced state of network consensus. In this paper, we propose to expand the
measures of consensus from a single balanced state associated with the
frustration index to the set of nearest balanced states. We introduce the
frustration cloud as a set of all nearest balanced states and use a
graph-balancing algorithm to find all nearest balanced states in a
deterministic way. Computational concerns are addressed by measuring consensus
probabilistically, and we introduce new vertex and edge metrics to quantify
status, agreement, and influence. We also introduce a new global measure of
controversy for a given signed graph and show that vertex status is a zero-sum
game in the signed network. We propose an efficient scalable algorithm for
calculating frustration cloud-based measures in social network and survey data
of up to 80,000 vertices and half-a-million edges. We also demonstrate the
power of the proposed approach to provide discriminant features for community
discovery when compared to spectral clustering and to automatically identify
dominant vertices and anomalous decisions in the network.
Related papers
- BOURNE: Bootstrapped Self-supervised Learning Framework for Unified
Graph Anomaly Detection [50.26074811655596]
We propose a novel unified graph anomaly detection framework based on bootstrapped self-supervised learning (named BOURNE)
By swapping the context embeddings between nodes and edges, we enable the mutual detection of node and edge anomalies.
BOURNE can eliminate the need for negative sampling, thereby enhancing its efficiency in handling large graphs.
arXiv Detail & Related papers (2023-07-28T00:44:57Z) - Dual Node and Edge Fairness-Aware Graph Partition [25.808586461486932]
We propose a notion edge balance to measure the proportion of edges connecting different demographic groups in clusters.
We validate our framework through several social network datasets and observe balanced partition in terms of both nodes and edges along with good utility.
arXiv Detail & Related papers (2023-06-16T18:18:37Z) - 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) - Refined Edge Usage of Graph Neural Networks for Edge Prediction [51.06557652109059]
We propose a novel edge prediction paradigm named Edge-aware Message PassIng neuRal nEtworks (EMPIRE)
We first introduce an edge splitting technique to specify use of each edge where each edge is solely used as either the topology or the supervision.
In order to emphasize the differences between pairs connected by supervision edges and pairs unconnected, we further weight the messages to highlight the relative ones that can reflect the differences.
arXiv Detail & Related papers (2022-12-25T23:19:56Z) - A Graph Is More Than Its Nodes: Towards Structured Uncertainty-Aware
Learning on Graphs [49.76175970328538]
We propose novel edgewise metrics, namely the edgewise expected calibration error (ECE) and the agree/disagree ECEs, which provide criteria for uncertainty estimation on graphs beyond the nodewise setting.
Our experiments demonstrate that the proposed edgewise metrics can complement the nodewise results and yield additional insights.
arXiv Detail & Related papers (2022-10-27T16:12:58Z) - ImGAGN:Imbalanced Network Embedding via Generative Adversarial Graph
Networks [19.45752945234785]
Imbalanced classification on graphs is ubiquitous yet challenging in many real-world applications, such as fraudulent node detection.
We present a generative adversarial graph network model, called ImGAGN, to address the imbalanced classification problem on graphs.
We show that the proposed method ImGAGN outperforms state-of-the-art algorithms for semi-supervised imbalanced node classification task.
arXiv Detail & Related papers (2021-06-05T06:56:37Z) - Biased Edge Dropout for Enhancing Fairness in Graph Representation
Learning [14.664485680918725]
We propose a biased edge dropout algorithm (FairDrop) to counter-act homophily and improve fairness in graph representation learning.
FairDrop can be plugged in easily on many existing algorithms, is efficient, adaptable, and can be combined with other fairness-inducing solutions.
We prove that the proposed algorithm can successfully improve the fairness of all models up to a small or negligible drop in accuracy.
arXiv Detail & Related papers (2021-04-29T08:59:36Z) - A Thorough View of Exact Inference in Graphs from the Degree-4
Sum-of-Squares Hierarchy [37.34153902687548]
We tackle the problem of exactly recovering an unknown ground-truth binary labeling of the nodes from a single corrupted observation of each edge.
We apply a hierarchy of relaxations known as the sum-of-squares hierarchy, to the problem.
We show that the solution of the dual of the relaxed problem is related to finding edge weights of the Johnson and Kneser graphs.
arXiv Detail & Related papers (2021-02-16T08:36:19Z) - Interpretable Signed Link Prediction with Signed Infomax Hyperbolic
Graph [54.03786611989613]
signed link prediction in social networks aims to reveal the underlying relationships (i.e. links) among users (i.e. nodes)
We develop a unified framework, termed as Signed Infomax Hyperbolic Graph (textbfSIHG)
In order to model high-order user relations and complex hierarchies, the node embeddings are projected and measured in a hyperbolic space with a lower distortion.
arXiv Detail & Related papers (2020-11-25T05:09:03Z) - Spectral Embedding of Graph Networks [76.27138343125985]
We introduce an unsupervised graph embedding that trades off local node similarity and connectivity, and global structure.
The embedding is based on a generalized graph Laplacian, whose eigenvectors compactly capture both network structure and neighborhood proximity in a single representation.
arXiv Detail & Related papers (2020-09-30T04:59:10Z)
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.