Add resource "The Weisfeiler-Lehman Isomorphism Test" Accepted
Changes: 9
-
Add The Weisfeiler-Lehman Isomorphism Test
- Title
-
- Unchanged
- The Weisfeiler-Lehman Isomorphism Test
- Type
-
- Unchanged
- Blog post
- Created
-
- Unchanged
- no value
- Description
-
- Unchanged
- Two graphs are considered isomorphic if there is a mapping between the nodes of the graphs that preserves node adjacencies. Here is the algorithm for the Weisfeiler-Lehman Isomorphism Test. It produces for each graph a canonical form. If the canonical forms of two graphs are not equivalent, then the graphs are definitively not isomorphic. However, it is possible for two non-isomorphic graphs to share a canonical form, so this test alone cannot provide conclusive evidence that two graphs are isomorphic.
- Link
-
- Unchanged
- https://davidbieber.com/post/2019-05-10-weisfeiler-lehman-isomorphism-test/
- Identifier
-
- Unchanged
- no value
Resource | v1 | current (v1) -
Add How Powerful are Graph Neural Networks?
- Title
-
- Unchanged
- How Powerful are Graph Neural Networks?
- Type
-
- Unchanged
- Paper
- Created
-
- Unchanged
- 2019-02-22
- Description
-
- Unchanged
- Despite GNNs revolutionizing graph representation learning, there is limited understanding of their representational properties and limitations. Here, we present a theoretical framework for analyzing the expressive power of GNNs to capture different graph structures. Our results characterize the discriminative power of popular GNN variants, such as Graph Convolutional Networks and GraphSAGE, and show that they cannot learn to distinguish certain simple graph structures. We then develop a simple architecture that is provably the most expressive among the class of GNNs and is as powerful as the Weisfeiler-Lehman graph isomorphism test.
- Link
-
- Unchanged
- http://arxiv.org/abs/1810.00826
- Identifier
-
- Unchanged
- no value
Resource | v1 | current (v1) -
Add Reversals in psychology
- Title
-
- Unchanged
- Reversals in psychology
- Type
-
- Unchanged
- Blog post
- Created
-
- Unchanged
- 2020-01-26
- Description
-
- Unchanged
- Psychology has in recent years been racking up reversals: in fact only 40-65% of its classic social results were replicated, in the weakest sense of finding ‘significant’ results in the same direction. (Even in those that replicated, the average effect found was half the originally reported effect.) The following are empirical findings about empirical findings; they’re all open to re-reversal. Also it’s not that “we know these claims are false”: failed replications (or proofs of fraud) usually just challenge the evidence for a hypothesis, rather than affirm the opposite hypothesis.
- Link
-
- Unchanged
- https://www.gleech.org/psych
- Identifier
-
- Unchanged
- no value
Resource | v1 | current (v1) -
Add Graph isomorphism problem
- Title
-
- Unchanged
- Graph isomorphism problem
- Description
-
- Unchanged
- The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic. The problem is not known to be solvable in polynomial time nor to be NP-complete, and therefore may be in the computational complexity class NP-intermediate. It is known that the graph isomorphism problem is in the low hierarchy of class NP, which implies that it is not NP-complete unless the polynomial time hierarchy collapses to its second level. At the same time, isomorphism for many special classes of graphs can be solved in polynomial time, and in practice graph isomorphism can often be solved efficiently.
- Link
-
- Unchanged
- https://en.wikipedia.org/?curid=1950766
Topic | v1 | current (v1) -
Add Graph convolutional networks (GCN) compared in How Powerful are Graph Neural Networks?
- Current
- compared in
Topic to resource relation | v1 -
Add Psychology cons given in Reversals in psychology
- Current
- cons given in
Topic to resource relation | v1 -
Add Graph convolutional networks (GCN) (detached) The Weisfeiler-Lehman Isomorphism Test
- Current
- (detached)
Topic to resource relation | v1 -
Add Graph isomorphism problem treated in The Weisfeiler-Lehman Isomorphism Test
- Current
- treated in
Topic to resource relation | v1 -
Add Graph convolutional networks (GCN) relates to Graph isomorphism problem
- Current
- relates to
Topic to topic relation | v1